멀티플레이 게임과 동기화

CAP 이론

---

개요

CAP 이론이란 분산 시스템 선택에 도움을 주는 정리이다.

Consistency(일관성) : 시스템에 접근하는 누구나 같은 결과를 봄
Availablity(가용성) : 누구나 언제든지 시스템에 접근(읽기/쓰기) 가능 => lock 거는 일이 없다.
Partition Tolerance (분할 용인) : 시스템을 분할할 수 있음 (병렬 처리, 멀티쓰레딩)

 

이며 CAP를 모두 충족하는 시스템은 없다는 것이 핵심이다.

 

IMG FROM : https://docs.deistercloud.com/content/Technology.50/NoSQL/index.xml

 

멀티 플레이와 CAP

멀티플레이 게임은 기본적으로 'P'를 충족해야 한다고 볼 수 있다. 

그러면 멀티플레이 동기화에 있어서 선택지는 두 개가 남는다. 'A'를 택할 것인지, 'C'를 택할것인지

 

 

 

멀티플레이의 동기화 방식

---

1. 비동기형

Clash of Clans 같은 게임이 해당된다.

이 경우에는 백엔드가 웹 서비스와 같은 형식이다. 

즉, 사용자가 요청하면 서버에서 해당 결과를 알려주는 방식이다.

 

이런 경우 구현이 쉬워질 것이다.

 

그러나 다음과 같은 제약이 있다.

• 동기화문제 : 동기화를 할 수 없다. 예를 들어, 콘서트 티켓팅할 때, 나한테는 보였는데 클릭하니까 매진이라고 뜨는 경우.
• 수동적 : 몬스터가 선공을 하는 등의 능동적인 AI 같은 건 불가능하다.

 

2. 서버 동기화 (PA + 최종 일관성)

최종 일관성이란?

PA는 CAP이론에 따라 일관성(C)을 보장할 수 없다. 따라서 나중에서라도 '보정'을 통해 일관성을 보장하는 것이 최종 일관성이다.

 

서버 동기화

서버 동기화는 서버가 게임 로직을 처리하고 동기화하는 것이다. 클라이언트들은 서버를 통해서 간접적으로 연결되어 있다.

서버에서 로직을 처리하므로 해킹에 대하여 비교적 안전하다.

 

주로 FPS, MMO, MOBA 등의 장르에서 사용하고, 가장 쉬운 방법 중 하나라고 한다.

 

전체적인 메커니즘은 서버가 로직을 처리해서 클라이언트들에게 broadcast 하는 방식.

 

문제

그러나 이런 방법은 문제가 있을 수 있다. 내가 보는 것이랑 실제 데이터(서버에서의 데이터)와 차이가 있을 수 있다는 것이다.

 

그리고 여러 사람이 모이면 당연히 컴퓨터가 빠른 애는 더 최신의 데이터를 보고, 느린 애는 옛 데이터를 볼 수밖에 없으므로, 공평하지 않을 수 있다는 문제가 있다.

 

또한 서버가 얼마나 자주 broadcast를 하냐에 따라서 사용자의 경험이 차이 날 수 있다. 

 

만약 서버의 방송 주기가 프레임보다 낮다면, 남은 프레임은 어떻게 처리할까? 

 

 

Dead Reckoning (DR, 추측항법)

가장 유명한 처리방법이며, 엄청나게 많은 방식의 dead reckoning 개선 방법이 있다.

 

핵심은 '서버에서 broadcast 패킷을 받지 않은 상태에서도 상대방의 행동을 예측하자' 이다.

 

서버에서는 다양한 액터들의 위치뿐 아니라 속도, 가속도 등도 클라에게 보내준다.

클라는 이런 정보를 바탕으로 액터들의 행동을 예측하여 시뮬레이션한다. 

 

따라서 서버로부터 broadcast 패킷을 받지 않아도 나머지를 시뮬레이션하여 부드러운 프레임을 보여줄 수 있는 것이다.

 

리그오브레전드도 이러한 방식을 사용할 수 있음을 알 수 있다. 게임 도중에 랜선을 뽑으면 미니언도 잘 행동하고 CS도 먹어진다. 그러나 적들은 왔던 방향으로 계속 이동한다. 그러다 임계 시간을 넘으면 네트워크 연결 끊김으로 게임이 꺼지는 것이다. 

 

서버 되감기, 롤백

DR을 이용한 시뮬레이션들은 어디까지나 예측이지, 서버의 실제 데이터가 아니다. 따라서 서버는 클라이언트의 상태를 받아 자신과 비교한 뒤, 서버의 데이터와 다른 경우 클라의 데이터를 보정해준다.

 

즉, 클라이언트가 DR을 통해 시뮬레이션한 결과를 서버가 허가해주는 구조라고 볼 수 있다.

 

만약 차이가 너무 나서 서버가 허가하지 않는다면 어떤 현상이 발생할까?

 

유명한 Rubber banding이라는 현상이 발생한다.

서버에서 허용하는 차이의 임계값을 넘어, 강제로 보정하면서 캐릭터가 순간 이동하는 현상이다. 

 

그래서 서버의 Tickrate가 매우 중요하다. (얼마나 자주 방송을 해줄지.)

이게 너무 낮다면 순간이동을 많이 할 거고, 높다면 돈이 많이 들 것이다.

 

서버 되감기 예

FPS에서야 말로 서버 되감기가 필수적이다. 내가 적을 향해 레이저 총(히트스캔 방식)을 쐈다고 쳐보자. 내가 쏘는 즉시 적이 맞아야 하므로, 적은 죽어야 한다. 

 

그러나 내가 보는 건 서버로부터 방송받은 과거의 데이터이다. 따라서 내가 쏜 적은 현재 서버에서는 다른 위치에 있으므로 죽지 않게 된다. 그렇다고 클라이언트의 데이터를 우선하자니, 안 맞아도 죽이는 핵 같은 게 나오겠지?

 

그래서 서버 되감기를 쓰는데, 클라이언트가 적을 향해 총을 쐈다고 서버에게 정보를 보내면, 서버는 클라이언트가 총을 쏜 시점의 데이터를 참고하여, 다시 시뮬레이션을 한다. 이때, 클라이언트의 시뮬레이션 결과 (적이 맞고 죽음)과 서버에서 시뮬레이션 결과가 같으면 적을 죽이도록 허가해주는 것이다.

 

그러나 피격자에게는 이러한 문제가 억울할 수도 있다. FPS 게임하다 보면 벽 뒤에서 총을 맞고 죽는 경우를 알 수 있는데 이런 게 바로 서버 되감기의 예이다. 

 

그래서 공격자와 피격자 둘 중 하나의 손을 들어줘야 하는데 FPS는 맞을 일보다 쏠 일이 많으니까 보통 공격자의 편을 들어준다. (재미를 위해서라도 더더욱)

 

Area Of Interest (AOI, 관심 영역)

어쨌든 이런 동기화도 패킷을 주고받는 것이므로, 최대한 필요한 정보만 보내는 것이 자원을 아끼는 방법이다.

즉, 클라에게 필요한 부분(= AOI)에 대해서만 패킷을 주고받아 자원을 아끼는 것.

 

이것은 보안 문제와도 관련이 있는데, 배틀그라운드의 ESP(위치핵) 같은걸 생각해보면 된다.

 

만약 배틀그라운드가 가시거리 10m에 칼만 사용할 수 있는 게임이라면 서버는 클라이언트의 주변 10m만 방송을 해주면 된다. 따라서 클라이언트는 반경 10m밖에 있는 정보들은 아예 알 수가 없다.

 

그러나 배틀그라운드는 초장거리 저격까지 하는 게임이고, 당연히 아주 멀리 있는 적들의 정보까지 서버가 보내줘야 한다. 즉, 클라이언트의 메모리에는 모든 적들의 정보가 존재하고 있다는 것이고... 이것을 가져다 쓰면 ESP를 만들 수 있는 것이다...  

 

발로란트가 이런 걸로 위치 핵 막겠다고 홍보를 하기도 했다.

 

 

 

3. 서버 동기화 (CP) 

락스텝

스타크래프트에서 쓴 동기화 방식이다.

 

C를 유지하기 위해 A를 포기한다. 즉, 인풋을 넣는다고 해서 그게 즉시 반영되는 게 아니라는 뜻이다. 

 

모든 유저들은 서로 Input을 동기화한다. 모든 유저들의 Input을 기다린 뒤에 (아무것도 누르지 않는 것도 Input이다. 패킷 받는 거 말하는 거) 각자 시뮬레이션을 한다. 그리고 이런 시뮬레이션들을 서버에 보내고, 서버는 이런 시뮬들을 비교한 뒤에 맞는지 아닌지를 테스트한다. 만약 불일치한다면 네트워크 세션이 폭파된다. 

 

이 경우, 클라이언트가 대부분의 로직을 처리하기에 해킹에 취약하다고 볼 수 있다. 그러나 어쨌든 서버에서 state를 비교하여 틀리면 폭파시키기 때문에... 스타의 드랍핵 같은 것도 이런 걸 이용한 거라고 예상해본다 (개인적 예상임)

 

이 경우 어떤 주기로 input을 취합하여 시뮬레이션할 것인지가 중요한다. 이러한 주기를 하나의 ROUND라고 칭한다. 즉 각각의 클라이언트들은 매 라운드마다 input(event)를 맞춰서 동기화하는 것이다. 이러면 당연히 일관성이 있겠지?

 

그러나 만약에 다른 클라로부터 응답이 없다면, 다른 클라이언트를 기다려야 한다... 

스타크래프트 하다가 다른 유저들을 기다리는 창이 뜨는 것이 바로 이것이다.

 

그래서 스타에서는 다양한 latency를 설정할 수 있도록 하는데, 만약 latency가 낮다면 다른 플레이어를 기다리는 창이 더 빈번하게 뜨겠지만 반응성이 좋고, latency가 높다면 다른 플레이어를 기다리는 창은 뜨지 않겠지만 반응성이 좀 떨어질 것이다.

 

극단적으로 글로벌 원 빌드를 사용하는 전략게임 같은 경우는 1라운드가 0.5초씩 이렇게 되는데 이 경우 내가 인풋을 눌러도 반응이 최대 0.5초 뒤에 오는 것을 예상해 볼 수 있다. (반응성 후짐)

 

Fixed Time Bucket Synchronization 

락스텝은 클라이언트 간의 Transmission Delay 때문에 Regular Rate로 게임을 진행할 수 없다는 문제가 있다. 이 경우 RTT를 이용해 delay를 통계적으로 추정하는 것이다. 그러면 대부분의 경우에 Regular rate로 게임을 할 수 있다. 

 

Optimistic Fixed Time Bucket

이건 optimistic 한 버전이다. '의도적으로 event를 늦게 일어난 것처럼 미룬다'. 

 

 

4. 트렌드

어쨌든 CP의 경우 누굴 기다린다? 이런 건 매우 불쾌한 경험이기에.. 제한적으로만 사용하고 대부분의 멀티플레이어 게임이 AP시스템에 서버 되감기를 이용하여 최종 일관성을 유지한다. 즉, AP와 최종 일관성(C)을 만족한다.

 

5. 주의 : 결정성

결정성 

결정성이란? 동일한 input에 대하여 동일한 output이 나오는 것이다. 

 

예를 들어, RPG 게임을 하는데 누가 체력 50인 몬스터를 쳤다. 그런데 이 유저의 공격이 1~100 사이의 값이고 랜덤이다.

 

그러면 누가 보기에는 몬스터가 죽고 누가 보기에는 안 죽는다. 즉, 결정성 때문에 동기화가 틀어진다.

 

물론 컴퓨터에서 난수 생성은 유사 난수라서 SEED값을 동기화한다면 난수도 동기화가 가능하다. (보통 시드는 서버 프레임을 사용)

 

다른 하나는 멀티 스레드인데, 각 스레드들의 호출 순서는 알 수 없으므로 (NP hard) 결정성이 틀어질 수 있다. 

 

또한 부동소수점의 사용도 조심해야 한다. (OS,컴파일러마다 다를 수 있음.. 특히 크로스 플랫폼은)