퀘이크 3 소스 코드 리뷰: 네트워크 모델 (2012)

 (fabiensanglard.net)
1P by GN⁺ | ★ favorite | 댓글 1개
  • 빠른 FPS 환경에서는 늦게 도착한 상태 정보의 가치가 낮기 때문에, Quake 3는 UDP/IP 중심 설계로 지연을 줄이는 쪽을 택함
  • NetChannel은 손실 가능성이 있는 UDP 위에서 통신을 추상화하고, 서버는 클라이언트별 스냅샷 기록으로 필요한 상태 차이만 다시 계산함
  • 서버는 Master Gamestate, 최근 32개 gamestate, dummy gamestate를 함께 써서 전체 업데이트와 델타 업데이트를 같은 절차로 만듦
  • 클라이언트 ACK가 없으면 서버는 마지막으로 확인된 스냅샷과 현재 상태를 비교해, 누락된 변경과 새 변경을 한 메시지에 담음
  • C에 내장 인트로스펙션이 없어도 netField_t와 매크로로 필드 차이를 찾고, NetChannel은 1400바이트 사전 분할로 라우터 단편화를 피함

UDP/IP를 전제로 한 네트워크 모델

  • Quake 3의 네트워크 모델은 엔진에서 가장 우아한 부분으로 평가되며, 낮은 수준에서는 Quake World에서 처음 등장한 NetChannel 모듈로 통신을 추상화함
  • 빠른 게임에서는 첫 전송에서 놓친 정보가 곧 오래된 정보가 되므로, 다시 보내는 것보다 최신 상태를 보내는 편이 더 유리함
  • 이 때문에 엔진에는 TCP/IP 흔적이 없고, 신뢰 전송이 만드는 지연을 감수하기 어렵다고 봄
  • 네트워크 스택에는 서로 배타적인 두 계층이 추가됨
    • 사전 공유 키를 이용한 암호화
    • 사전 계산된 Huffman 키를 이용한 압축
  • 서버는 UDP datagram 크기를 줄이면서 비신뢰성을 보완함
    • 스냅샷 기록으로 델타 패킷을 생성함
    • 메모리 인트로스펙션 방식으로 변경된 필드만 찾아 보냄

서버와 클라이언트의 역할

  • 클라이언트 쪽 흐름은 단순함
    • 매 프레임 서버에 명령을 보냄
    • 서버에서 gamestate 업데이트를 받음
  • 서버는 각 클라이언트에 Master Gamestate를 전파하면서 손실된 UDP 패킷까지 고려해야 함
  • 핵심 메커니즘은 세 요소로 구성됨
    • Master Gamestate: 보편적으로 참인 게임 상태이며, 클라이언트 명령은 NetChannel을 통해 들어와 event_t로 바뀐 뒤 서버에서 게임 상태를 수정함
    • 클라이언트별 최근 32개 gamestate: 네트워크로 보낸 상태를 순환 배열에 저장하며, 스냅샷이라고 부름
    • dummy gamestate: 모든 필드가 0인 상태이며, 이전 상태가 없을 때 델타 생성 기준으로 쓰임
  • 서버는 이 세 요소로 NetChannel에 넘길 업데이트 메시지를 만듦
  • 클라이언트별 gamestate를 많이 유지해야 하므로 메모리 사용량이 커짐
    • 측정 기준으로 플레이어 4명에 8MB를 사용함

스냅샷으로 전체 업데이트와 부분 업데이트 만들기

  • 예시는 Client1에 업데이트를 보내는 상황에서, Client2의 상태가 pos[X], pos[Y], pos[Z], health 네 필드로 구성된 경우를 사용함
  • 통신은 UDP/IP로 이루어지며, 인터넷에서는 메시지가 자주 손실될 수 있음

  • 첫 번째 서버 프레임

    • 서버는 모든 클라이언트에서 받은 업데이트를 Master Gamestate에 반영한 뒤 Client1에 상태를 전파함
    • 네트워크 모듈은 매번 같은 절차를 따름
    • Master Gamestate를 클라이언트 기록의 다음 슬롯에 복사함
    • 복사된 스냅샷을 다른 스냅샷과 비교함
    • 첫 업데이트에서는 Client1 기록에 유효한 스냅샷이 없으므로 dummy snapshot과 비교함
    • dummy snapshot의 모든 필드가 0이므로 결과는 전체 업데이트가 됨
    • 각 필드 앞에는 변경 여부를 나타내는 비트 마커가 붙음
    • 예시 전체 업데이트는 132비트를 사용함
    • 형식은 [1 A_on32bits 1 B_on32bits 1 B_on32bits 1 C_on32bits]

  • 두 번째 서버 프레임

    • 다음 프레임에서 Client2가 Y축으로 이동해 pos[1] 값이 E가 됨
    • Client1은 이전 업데이트 수신을 ACK했으므로 Snapshot1이 ACK 상태가 됨
    • 서버는 Master Gamestate를 다음 기록 슬롯에 복사해 Snapshot2를 만들고, 유효한 Snapshot1과 비교함
    • 결과적으로 변경된 pos[1] = E만 네트워크로 전송됨
    • 각 필드에 비트 마커가 붙기 때문에 이 부분 업데이트는 36비트를 사용함
    • 형식은 [0 1 32bitsNewValue 0 0]

  • 세 번째 서버 프레임

    • 다음 프레임에서 Client2는 체력을 잃어 health = H가 됨
    • Client1은 마지막 업데이트를 ACK하지 않음
    • 서버의 UDP 패킷이 손실됐을 수도 있고, 클라이언트의 ACK가 손실됐을 수도 있음
    • 어느 경우든 해당 스냅샷은 사용할 수 없음
    • 서버는 Master Gamestate를 다음 슬롯에 복사해 Snapshot3을 만들고, 마지막으로 ACK된 Snapshot1과 비교함
    • 전송되는 메시지는 부분 업데이트이며, 이전 변경 pos[1] = E와 새 변경 health = H를 함께 포함함
    • Snapshot1이 너무 오래되어 사용할 수 없으면 엔진은 다시 dummy snapshot을 기준으로 전체 업데이트를 보냄

같은 절차로 손실을 보완하는 방식

  • 스냅샷 시스템의 단순함은 같은 알고리듬이 두 작업을 자동으로 처리한다는 데 있음
    • 전체 업데이트 또는 부분 업데이트 생성
    • 수신되지 않은 이전 정보와 새 정보를 한 메시지로 재전송
  • UDP 패킷 손실을 별도 복잡한 흐름으로 처리하지 않고, 마지막으로 ACK된 스냅샷과 현재 Master Gamestate의 차이를 계산해 보완함
  • 이전 상태가 없거나 사용할 수 없을 때는 dummy snapshot을 기준으로 전체 상태를 보내 복구함

C에서 필드 차이를 찾는 방식

  • Quake 3는 C 언어에 인트로스펙션이 없지만, 각 필드 위치를 netField_t 배열과 전처리 지시문으로 미리 구성함
  • netField_t는 필드 이름, offset, 비트 수를 담음
  • NETF(x) 매크로는 문자열화 연산자와 entityState_t에 대한 offset 계산을 이용해 필드 정보를 짧게 작성하게 함
  • 예시 구조는 다음과 같음
typedef struct { char *name; int offset; int bits; } netField_t;

// using the stringizing operator to save typing...
#define NETF(x) #x,(int)&((entityState_t*)0)->x

netField_t entityStateFields[] = {
    { NETF(pos.trTime), 32 },
    { NETF(pos.trBase[0]), 0 },
    { NETF(pos.trBase[1]), 0 },
    ...
}
  • 전체 구현은 MSG_WriteDeltaEntity의 일부에 있음
  • Quake 3는 비교 대상의 의미를 해석하지 않고, entityStateFields의 index, offset, size를 따라가며 차이를 네트워크로 전송함

1400바이트로 미리 나누는 이유

  • NetChannel 모듈은 UDP datagram의 최대 크기가 65507바이트임에도 메시지를 1400바이트 조각으로 나눔
  • 관련 코드는 Netchan_Transmit에 있음
  • 대부분의 네트워크 MTU가 1500바이트이므로, 1400바이트 분할은 인터넷 경로에서 라우터가 패킷을 단편화하지 않도록 하기 위한 선택임
  • 라우터 단편화를 피해야 하는 이유는 두 가지임
    • 네트워크에 들어갈 때 라우터가 패킷을 단편화하는 동안 패킷을 붙잡아야 함
    • 네트워크를 나갈 때 datagram의 모든 조각을 기다린 뒤 비용이 큰 재조립을 해야 함

반드시 전달되어야 하는 메시지

  • 스냅샷 시스템은 네트워크에서 손실된 UDP datagram을 보완하지만, 일부 메시지와 명령은 반드시 전달되어야 함
  • 플레이어가 종료하거나 서버가 클라이언트에 새 레벨 로드를 요구하는 경우가 여기에 해당함
  • 이 보장은 NetChannel이 추상화함

관련 읽을거리

함께 보면 좋은 글 β

GN⁺   [-]
Hacker News 의견들

  • 이전 글들처럼 이번 글도 흥미로웠지만, 읽고 나니 지금 하는 일이 이 내용에 비해 너무 지루해서 살짝 우울해짐
    하루나 한 주가 끝나면 취미 프로젝트를 할 에너지가 전혀 남지 않음

    • 나도 똑같은 상황이었고 번아웃 증상이 느껴져서 지난달 일을 그만두고 긴 휴식에 들어감
      쉬면서 몇 년간 미뤄둔 취미 프로젝트도 하려는 중이고, 몇 년 사이 한 결정 중 가장 잘한 결정임
      물론 누구나 일을 그냥 그만둘 수 있는 특권이 있는 건 아니지만, 다행히 저축이 충분했고 지출도 낮게 유지해 감당 가능했음
    • 나도 비슷하게 느꼈고 주말에 이런 걸 할 창작 에너지가 더 있었으면 했음
      그런데 생각해보면 나는 대부분의 사람보다 훨씬 창의적인 일을 하고 있고, 월요일부터 금요일 9시~6시에 그 에너지를 다 쓰고 있음. 영화 업계에서 일함
      TV 보기, 독서, 선형 스토리 게임처럼 딱히 창의적일 필요 없는 소비형 취미에서 훨씬 더 큰 평화와 즐거움을 찾았고, 책을 쓰거나 게임을 만드는 식으로 무언가를 생산하는 취미가 없다고 스스로를 몰아붙이지 않게 됨
      이상하게도 일이 한가해서 2~3개월 정도 창의적인 일을 덜 하면 다시 창작 취미를 잡고 싶어짐. 나에게는 만들 수 있는 대역폭과 소비할 수 있는 대역폭이 각각 정해져 있고, 둘이 시소처럼 맞물려 있는 것 같음

  • Q3 네트워크 코드에는 몇 가지 문제가 있음
    Potentially Visible Sets(PVS) 때문에 엔티티가 제거될 때, 플레이어가 vis brush 근처에서 충분히 빠르게 움직이면 지연 시간 때문에 허공에서 갑자기 나타나는 것처럼 보일 수 있음. 간단한 해결책은 QVM 코드가 플레이어 위치를 미래 프레임으로 외삽해 해당 엔티티를 제거할지 판단하는 것임
    원래 Q3 네트워크 코드는 히트스캔 무기에 지연 보정이 없어서, 제대로 맞히려면 조준점을 앞질러 두어야 했음. 이후 Unlagged 모드가 지연 보정을 도입하면서 이 문제가 해결됨
    입력 명령에는 손실된 입력 프레임을 처리하는 백 버퍼가 있었지만, 지연 적용하지 않고 엔티티에 즉시 적용했음. 그래서 연결 상태가 나쁜 플레이어의 엔티티가 다른 사람에게 가끔 끊겨 보였음
    그래도 거의 모든 핵심은 잘 잡았음: 엔티티가 포함된 스냅샷으로 게임 상태 갱신을 효율적으로 전달했고, 스냅샷 버퍼를 이용해 클라이언트에서 엔티티 이동을 보간했으며, 델타 인코딩으로 바뀐 엔티티 상태만 전송했고, 허프만 인코딩으로 스냅샷을 압축해 대역폭을 줄였음

  • 시리즈 첫 번째 글 링크: https://fabiensanglard.net/quake3/index.php

  • 거의 12년 전 C로 첫 웹 서버를 만들었음
    Linux From Scratch(LFS)를 돌리는 라우터/방화벽 장치용이었고, 커널 버전은 잘 기억나지 않지만 2.6.x였던 것 같음
    이 글을 읽으니 그때가 떠오르고, 기술 스택과 LLM 같은 새 기술이 많이 발전했어도 그냥 순수한 C 코드를 쓰는 데에는 큰 즐거움이 있다는 걸 다시 느낌
    나에게는 오래된 68년식 Mustang을 만지며 손에 기름을 묻히는 느낌이고, 정말 즐거움

  • 원래 Q3A 클라이언트의 네트워크 코드는 LAN에서는 잘 동작했지만 원격 플레이에서는 지연 시간에 민감했음
    Quake Live에서 흥미로웠던 변화 중 하나는 원격 플레이를 개선한 업데이트된 네트워크 코드였고, 시간이 지나며 인터넷 연결 자체도 전반적으로 좋아짐

    • 당시 대역폭을 감안하면 완벽하진 않았지만, 대부분의 Quake 호스팅 서버는 국내 플레이어에게 핑과 지연 시간이 훌륭했음
      진짜 문제는 세계 반대편에서 개인 컴퓨터로 서버를 여는 사람들이었고, 당연히 결과가 매우 나빴음
      나는 전 Quake 3 챔피언이고 Quake 3 서버를 다뤄본 경험이 많음

  • 지연 시간을 예측하고 보정하는 방식이고, 운영 변환(OT) 같은 복잡한 걸 쓰지 않는 점이 흥미로움
    실제로는 더 단순하고, 공유 상태가 공동 편집 문서가 아니라 독립적인 최종 진실 공급원이 필요하며, 개발이 더 빠르고 공유 서버로서 성능도 더 좋을 것 같음

    • FPS에서 OT는 지나치게 과한 방식이고, 어차피 Quake 3 시절에는 OT가 학계를 벗어나지도 않았을 것 같음
      클라이언트 상태가 갈라졌을 때 이를 조정하는 방식도 있을 수 없음. 서버가 유일한 진실 공급원이어야 하며, 그렇지 않으면 치팅과 익스플로잇이 생김
    • OT는 실시간 처리에는 너무 느림

  • FireWire가 나왔을 때 처음 듣기 시작한 등시성(isochronous) 이라는 용어가 떠오름
    UDP를 쓰는 이유를 설명하면서 그 부분을 암시하는 것 같음
    등시성 데이터 전송은 현재 USB/Thunderbolt 명세에서도 꽤 중요한 부분일 가능성이 높음

  • 실시간 게임 프로토콜의 현대적 접근을 배울 만한 자료가 있을까?

  • 요즘도 이런 용도의 확실한 오픈소스 미들웨어가 있나?

답변달기