多人網路連線遊戲程式開發之讀書筆記：同步遊戲資料，資料序列化與物件複製，處理網路延遲與伺服器安全性

王思元 2017-12-24 軟體工程 , 讀書筆記 , Backend

Multi-Player Game Programming by Joshua Glazer, Sanjay Madhav

Multi-Player Game Programming，這是一本介紹如何建置多人網路遊戲程式的書，提到許多關於網路遊戲傳輸的重要概念，例如如何同步遊戲世界資料，如何讓遊戲玩起順順不卡頓 (lag)等等，以及多人遊戲會遇到的困難與挑戰，有志朝網路遊戲程式設計可以閱讀看看的書籍。

不過關於自己最想了解的後端伺服器架構設計，如何動態橫向擴充伺服器之類的內容 (scalable)，倒是沒有提到多少細節就是了……。

Ch1 網路遊戲概觀

介紹網路遊戲類型的歷史，近年來比較重要的應該是這兩種：

Massively Multilayer Online Games, MMO
- MMO 類型的遊戲主要都是玩角色扮演，也被稱 MMORPGs
- MMO 遇到的系統架構挑戰較為複雜，書中有提到部分 (大量處理玩家要求…)
Mobile Networked Games
- 手機遊戲，回合制遊戲大多採用非同步模式 (asynchronous)，不像是 MMO 需要持續同步連線
- 隨著科技以及網路穩定度的進步，採取同步模式的遊戲應該會越來越多 (synchronous)

在開發網路遊戲之前，會先考慮選擇採用哪種通訊協定 (Communications protocol)，根據幾種類型資料：

不保證傳輸 (non-guaranteed data)
- 當網路不好時，第一時間會放棄同步的資料
保證傳輸 (guaranteed data)
- 例如如射擊遊戲–開槍的行為
最近狀態的資料 (“most recent sate” data)
- 假設最近發生的事件最重要
- 例如射擊遊戲–開槍擊中資料，五秒前到現在必須優先保證傳輸
保證並且快速傳輸 (guaranteed quickset data)
- 非常重要，得優先傳輸並且要快
- 例如射擊遊戲–玩家移動的資料

另外也會根據應用需求，決定連線架構 (network model)，可參考 Ch6。

Ch2 網際網路 Internet

介紹網路架構的基礎，複習已經計算機概論 (Introduction to computer science) 所學。不過這得開發到一定經驗後，再回來看這章才會比較有感覺吧，網路底層理論總是那麼的硬又無趣…。

TCP/IP suite
Physical layers
- Network layer
  - IPv4, IPv6,
  - Routeing
- Transport layer
  - TCP (Transmission control protocol)
    - 保證資料不遺失，收到資料順序等同於送出順序
    - 三次訊息交換建立連線 (three-way handshaking)
  - UDP (User datagram protocol)
- Application layer
  - DHCP (Dynamic host configuration protocol)
    - 區網內連線通訊協定，自動分配 IP 位置給用戶，管理區網內網路的手段
  - DNS (Domain name system)
    - 域名與 IP 位置對應的查詢服務協定
NAT (Network address translation)
- IPv4 有限 IP 的解決方案，修改來源或是目的的 IP 位置的技術

Ch3 Berkeley socket

Berkeley socket API，原先發布在 BSD 4.2，提供一套操作 TCP/IP 的基礎 API，後續被廣泛的移植到各家 OS 以及不同程式語言上。

這章介紹如何在 C++ 使用該 API，不過我的程式語言是 Golang 以及 C#，其標準函數庫中都已經包含期更高階的實作，因此很簡略翻翻這章的內容。

Ch4 Object serialization

網路多人遊戲中，需要同步遊戲物件資料到多個玩家中，如何將這些遊戲物件資料轉換成可傳送的格式 (format data) 的過程，即是物件序列化 (serialization)。

本章介紹如何在 C++ 操作記憶體區段來做到序列化，以下是示意的範例：

class Avatar : GameObject {
public:
   Avatar() : mHealth(100), mMagicpoint(100), mAttack(3), mDefend(1) {}
   
   void Write(MemoryStream& inStream) const;
   void Read(MemoryStream& inStream);
  
private:
   int32_t mHealth;
   int32_t mMagicpoint;
   int32_t mAttack;
   int32_t mDefend;
};
void Avatar::Write(MemoryStream& inStream) const {
   inStream.Write(mHealth);
   inStream.Write(mMagicpoint);
   inStream.Write(mAttack);
   inStream.Write(mDefend);
}
void Avatar::Read(MemoryStream& inStream) {
   inStream.Read(&mHealth);
   inStream.Read(&mMagicpoint);
   inStream.Read(&mAttack);
   inStream.Read(&mDefend);
}

其記憶體配置會是：

Address	Field	SourceValue
Bytes 0-3	mHealth	0x00000064 (100)
Bytes 4-7	mMagicpoint	0x00000064(100)
Bytes 8-11	mAttack	0x00000003(3)
Bytes 12-15	mDefend	0x00000001(1)

甚至有時候有對 bit 操作，看需求。

在不同平台 (platform) 的位元組順序的相容議題 (endian compatibility)，little-endian/ big-endian 需要做轉換，通常在跨平台同步資料才需要考慮這個議題，解決方案會直接寫在 MemoryStream 的實作中，如果傳輸資料的 endain 與該平台的 endian 不同時，MemoryStream 讀寫時會轉換處理。

壓縮議題，序列化資料可以再經過壓縮機制再傳輸，書中介紹幾種方式，都是非破壞性壓縮方式 (lossless compression)：

不過讀完本章，自己實務上卻不會這樣從底層開始寫起，序列化會採用通用的交換格式：

XML (overhead)
JSON
YAML

雖然需要花較多的時間序列化以及較大的資料量，但好處是有現成的函數庫 (library) 可以使用，拿到原始資料也容易人工偵錯。如果專案需求需要更快更小的序列化方法，那會直接考慮 Protocol buffers 的解決方案。

至於壓縮，則是採用 HTTP 常見支援的壓縮演算法，例如 gzip 或是 Deflate。

Ch5 Object replication

介紹遠端 (remote) 與本機 (local) 遊戲物件狀態同步的程式框架 (replication framework)，將各個玩家在遊戲世界的狀態互相同步。例如一位玩家開門開槍將殭屍殺死，其他玩家也要看到相同的狀態演出。

需要三個主要步驟：

標示送出的資料封包包含物件狀態 (object state)
同步物件需要有擁有唯一標示 (uniquely identity)
通知該物件類別同步其物件狀態 (replicated object state)

物件同步的程式架構範例與實作可參考書中細節，紀錄其中幾個要點：

Object create registry：註冊物件建立的函數對應表 (class id mapping)，使得網路模組知道怎麼建立新物件
Multiple objects per packet：有效率的傳輸是讓每次傳送封包大小 (packet) 接近 MTU (Maximum Transmission Unit, 1500 bytes in IEEE802.3)，因此可嘗試打包一次傳送多物件的狀態
Partial object state replication：部分物件屬性同步，只傳有改變需要同步的物件屬性
Remote procedure calls (RPCs)：將指令與參數資料包裝，當伺服器端 (host, or server) 發送該資料給用戶端 (client)，用戶端立即呼叫指令對應的函數，並且傳送其函數參數

Ch6 Network topologies

基礎架構，考慮多台電腦如何連線。

Client-server

主從式，多個遊戲用戶端 (client) 連到同一台伺服器 (server)
若存在 n 個遊戲用戶，其頻寬複雜度 (bandwidth) 為 O(n)
伺服器作為權威伺服器 (authoritative server)，驗證遊戲資料，用戶端得使用伺服器的遊戲資料狀態
計算連線同步延遲 (lag)，計算用戶端到伺服器資料傳輸的 round trip time (RTT)
- RTT < 100 ms 會有較好的連線品質

Peer-to-peer

點為點，多個用戶端互相連結
若存在 n 個遊戲用戶，其頻寬複雜度 (bandwidth) 為 O(n^2)
實作面通常採用 input sharing 機制，同步所有輸入操作 (actions)，然後每一個 peer 藉由這些輸入模擬世界狀況
需要確保遊戲狀態在不同 peers 上的一致性 (data consistency)，即是相同輸入應該要能模擬出相同結果
- 同步 random seeds，並採用 pseudo-random number generator (PRNG)
連線與斷線處理
- 新 peer 加入連線議題，需要得知其他 peers 的連線位置
  - 採用與配對伺服器 (matchmaking server) 取得 master peer 位置，再從該 peer 取得在該網絡中的其他 peer 連線位置
- 與伺服器斷線的問題不存在於 peer-to-peer 架構中，一般來說，若 peer 斷線，遊戲會有短暫暫停將該 peer 資料清空，然後其他 peers 再繼續模擬世界

Client-server

Pear-to-pear

另外該節提供這兩種架構的簡易範例遊戲，可參考書中內容。

Ch7 Latency, Jitter, Reliability

介紹遊戲中延遲 (latency) 原因，根據網路分成兩大部分介紹，並介紹如何計算網路延遲等資料。

非網路原因 (non-network latency)

Input sampling latency：輸入延遲，玩家按下實體按鍵與遊戲偵測到按下的以及延遲時間
- 處理方式：增加軟體與硬體取得輸入狀態的頻率，通常自製輸入硬體才需要考慮…
Render pipeline latency：繪製延遲，因 GPU 無法在指定時間內完成所有的 draw commands
- 處理方式：減少繪製物件數量，減少後製效果，合併 draw commands 等等
Multi-threaded render pipeline latency：遊戲多執行序延遲，當其中某個執行序無法在指定時間完成時，其他執行序需要等待 (想像一個執行序跑遊戲模擬，另一個執行序跑繪圖…)
VSync：顯卡與螢幕處理垂直同步造成的延遲，但不開 VSync 又可能會導致畫面撕裂 (see Wiki)
Display lag & Pixel response time：螢幕顯示造成的延遲，硬體因素遊戲軟體無解啊

網路原因延遲

Processing delay：軟體處理的延遲，傳送封包到另一個端點 (endpoint) 需要時間，例如處理 NAT or 封包加解密
- 處理方式：通常影響非常小，可忽略（routers 效能都很好）
Transmission delay：實體傳輸延遲，寫入到 cable 頻寬 (bandwidth) 不足
- 處理方式：減少傳輸量
Queuing delay router：網路介面忙碌的延遲，大量資料傳輸網路介面無法負荷時，會先放在傳輸佇列排隊等待
- 處理方式：減少傳輸量
Propagation delay：物理限制傳播延遲，物理上長距離的通訊會花比較長的時間（台灣連日本會比台灣連美國還要快一些）
- 處理方式：調整伺服器物理所在位置，越靠近目標用戶所在區域越好

Round trip time (RTT)

計算從用戶端 (client, 遊戲端) 發送要求到伺服器 (server)，直到收到伺服器的回應為止
該時間受到用戶端以及伺服器雙方的網路延遲影響
遊戲通常使用 RTT/2 來預估單向傳輸的時間 one-way travel time

Jitter

實際上的 RTT 會在平均預期的 RTT 數值跳動，稱為 jitter (抖動)
通常因為網路延遲 (network latency) 所造成
解決 jitter 方法為解決延遲的議題

Packet loss and Reliability

網路差容易導致網路封包遺失 (packet loss)
TCP 與 UDP 選擇，看遊戲需求
- TCP：保證收到順序與保證資料送達
  - 由於 TCP 保證資料順序，若前次封包沒有成功送達時，會讓後續封包排隊等待傳輸，可能會使用後續較重要的封包卡住 (例如 guaranteed quickset data)
- UDP：傳輸信任機制，封包順序不保證，且封包可能會遺失
  - 若要確保有成功送達，需要自行實作其通知演算法 (delivery notification)
  - 書中有一大章節介紹如何實作

Ch8 Improved latency handling

網路延遲無可避免，這章節中介紹一些遊戲實作技巧，使得即使在連線品質不好的情況下，能夠降低延遲帶來的影響，讓玩家玩起來感覺還是很順暢。關鍵都在於預測啊。

Dump terminals

由伺服器模擬所有的遊戲狀態，用戶端不知道如何遊戲狀態模擬的流程，僅負責傳送玩家的輸入到伺服器，再接收伺服器回應的結果並且直接顯示。

當網路延遲時，玩家體驗會非常的不好，可能會有角色瞬間移動抑或是輸入反應遲鈍的情況
以角色 (player avatar) 所在位置為例，伺服器說角色新位置在哪裡，直接移動到該位置，會有瞬間移動的體驗

Client side interpolation

收到伺服器結果不是直接顯示，而是以目前的資料，經由一段時間內差 (interpolation) 到新資料。

以角色所在位置為例，伺服器說角色新位置在哪裡，是以目前角色位置為基準，經過一段時間內差到新位置去，會感覺移動較為平滑

Client side prediction

用戶端根據玩家輸入預測模擬資料，收到伺服器資料後再使用內插修正資料

用戶端必須有與伺服器端一樣，相同的模擬遊戲狀態演算法，且是確定預測的 (deterministic)
真實玩家行為是不可被預測……
Dead reckoning (航位推測法)，根據已知移動方向，推測其位置
- 可能會因為其他玩家輸入操作，而導致可能會出現的累計誤差 (grown inaccurate)
  - 用戶端以之前資料預測 Avatar 位置，目前已到位置 A，但實際上伺服器已被修正在位置 B，這是因為網路同步延遲而造成預測誤差
    
    航位推測法預設誤差的示意圖
- 用戶端的修正方式
  - Instance state update，立刻將 Avatar 從 A 拉到 B 的位置，玩家可能會注意到該 Avatar 瞬間跳到 B 的位置。另外注意 B 位置為 RTT/2 的位置，應該要補足預測這時間的位移
  - Interpolation，花些一些些時間將 A 位置平滑內差到 B 位置，除了線性內插 (linear-interpolation) 外，也可以考慮使用曲線內差 (cubic spline interpolation)
  - Second-order state adjustment，內插通常是定速方式 (constant vielocity) 移動，可以多考慮加速度變化來位移移動，數學會變得更加複雜，但能夠使得整個修正過程更不容易被玩家注意到

Server side rewind

能夠接受遊戲狀態時間回溯，根據用戶端輸入重新模擬結果

Counter-Strike 射擊遊戲的狙擊槍行為，確保玩家瞄準開槍的目標，不會因為網路延遲遊戲狀態修改而沒有打中

Ch9 Scalability

原本以為會介紹伺服器的議題，如何佈署橫向擴展的伺服器架構，但這章節是介紹遊戲規模擴展的處理，用戶端在大場景以及超多玩家情況下，所會遇到的議題與解決方案。

Object Scope and Relevancy

問題：伺服器 (server) 遊戲狀態更新時，那些資訊需要立即通知給用戶端 (client)
- 大型遊戲中不可能全部的世界資訊都與用戶端同步
  - 考慮頻寬 (bandwidth) 以及處理時間 (processing time)
- 部分遊戲機制需要限制同步的資訊，否則玩家可能會資訊作弊 (information cheat，安全性保護)
  - 擁有戰爭迷霧 (fog of war) 設計的遊戲，例如世紀帝國 (Age of Empires)、星海爭霸 (StarCraft)、英雄聯盟 (League of Legends)
- 大部分解決方案為更新玩家所能看見 (visible by player) 或是有相關的資料 (relevancy)，採用 visibility culling 的概念來實作

其可能解決技術列於以下。

Static Zones，分靜態區域

MMORPGs 常採用，將世界分成是多個小地圖，例如城鎮、平原、森林等等
只同步在相同地圖的遊戲世界資訊
缺點：當玩家都集中在特定地圖時，可能會有不良好的體驗
- 沒有什麼怪物可以打
- 大量玩家的資料同步以及繪製 (rendering)，導致遊戲延遲
可能的解決方法
- 不讓玩家進入繁忙的地圖區域
- 建立分流系統 (see server partitioning)

View Frustum，根據可視區域

只同步可視區域的資料

只同步玩家 X 前方 view-frustum 內的區域資料，其中紅色點表示為敵人，淡紅點表示敵人，但資料並沒有同步到用戶端
通常也會同步一定半徑內距離的區域 (distance-based)，處理上述情況中，玩家突然進行 180 度轉向所可能造成的延遲議題

除了同步玩家 X 之 view frustum 內的區域資料外，也同步其所在位置一定範圍內區域資料，其中紅色點表示為敵人
關於 view frustum 的數學細節，可參考 Real-Time Collision Detection, by Ericson, 2004

Other visibility techniques

採用 Potentially visible set 切場景，根據遊戲場景設定，預先計算哪有些物件可見或是不可見

Relevancy when not visible

根據不同遊戲設計需求，有些資訊就算玩家角色目前在遊戲世界中看不見，還是得同步更新的資訊

Server partitioning (sharding)

分成多個伺服器模組服務，但還是共用相同的資料庫 (database)
- Action games: 不同房間，連到不同的遊戲伺服器
- MMORPGs: 不同地圖，連到不同的遊戲伺服器
在 MMORPGs 中，如果人太多集中於同一張地圖，該遊戲伺服器還有機會會超載
- 建立排隊系統 (wait in a queue)
- 看遊戲需求設計…

Instancing

簡單來說就是遊戲分流伺服器，不同分流伺服器各有自己一份遊戲世界狀態
- 不怕玩家找不到怪物殺
- 當過多人集中於同張地圖，同個分流還是有可能造成遊戲伺服器崩潰…
  - 例如自己尋找副本組隊，開店攤販系統等，會因人潮而有明顯優勢的遊戲機制，很容易造成玩家集中在一起

Ch10 Security

介紹網路遊戲安全性的保護機制，網路封包以及伺服器驗證，甚至物理機房等級的防護。

Packet sniffing

從封包下手的攻擊：

中間人攻擊 (Man in the middle attack)
- 傳送資料過程中被他人擷取資料 (例如在區網或是是 Wi-Fi 環境)
- 通常的保護措施：重要資料傳輸過程中需要加密 (encrypt)，例如帳號密碼登入
  - 可採用 Public key cryptography (RSA)
- 不重要的資料，不加密也沒差
Packet sniffing on a host machine
- 玩家可能會破解伺服器與用戶端 (server-client) 間的通訊，並利用伺服器給予的資料，來進行資訊作弊 (information cheat)
  - 例如破解遊戲中的戰爭迷霧…
- 通常的保護措施：伺服器應限制資料的給予，只傳用戶端目前能知道的資訊

Input validation

伺服器得永遠驗證輸入：

駭客可以破解並跳過用戶端的輸入保護，直接傳送要求給伺服器
伺服器應該永遠驗證玩家輸入軟體作弊偵測，Software cheat detection
防止修改遊戲記憶體作弊 (例如 map hacking)
防堵機器人 (BOT)

Securing the server

保護伺服器：

DDoS 防護 (distributed denial-of-service attack)
- 大量要求使得伺服器忙碌不能正常運行
- 可以使用 Cloud providers (AWS, GCP, or Azure etc…) 的防護措施
Bad data (malformed or improper packets)
- 用戶端亂送資料，可能因為伺服器程式 bug 導致內部狀態錯誤
- 執行 Fuzz testing，測試那寫得不是很好的程式碼

Timing attacks 時間差攻擊

一個範例

bool Compre(int a[8], int b[8])
{
   for (int i = 0; i < 8; i++)
      if (a[i] != b[i])
         return false;
   return true;
}

計算這個函數的執行回傳時間，來猜測 b[0], b[1], ..., b[8] 是怎樣的組合

該範例的解決方式，採用 XOR 判斷

bool Compre(int a[8], int b[8])
{
   int val = 0;
   for (int i = 0; i < 8; i++)
      val |= a[i] ^ b[i]
         return val == 0
   return val == 0;
}

Intrusions 使用者入侵伺服器
- 伺服器作業系統應該時常更新最新版本
- 注意 spear publishing 攻擊，駭客先入侵公司的個人電腦，然後藉由該電腦入侵伺服器
- 與員工培養好感情，避免內部員工搞鬼
- 減少被入侵損失
  - 定期資料備份 (backup)
  - 使用者密碼加密
    - 使用不可逆的加密演算法 (like Blowfish-derived algorithm)
    - 最好再加鹽 (Salt)，避免被預先計算的表破解 (rainbow table attack)

Ch11 Real-world engines

介紹 Unreal & Unity 的網路架構，以及遊戲引擎內的物件管理 (spawning objects and replication)。隨意翻一翻，若未來有需要應該會直接去看官方的文件資料。

Ch12 Gamer Services

本章節考慮遊戲外加的額外服務整合，並提供使用 Steamworks SDK 的 C++ 程式碼範例：

遊戲配對 (matchmaking)，遊戲大廳配對玩家分房系統
統計資訊 (player statistics)，統計玩家在遊戲中獲得的金錢、殺敵數等等資訊
成就系統 (achievements)，當玩家達成某個遊戲條件時，給予獎勵的成就系統
排行榜 (leaderboards)
雲端遊戲紀錄儲存 (cloud-based saves)，玩家可以在不同電腦上同步遊戲存檔
小額付費交易 (micro-transactions)，小額付費購買遊戲中商品
可下載內容 (DLC, downloadable content)

基於遊戲上架發行平台，考慮使用該台的服務：

Steam
GooglePlay
Xbox One Live
PlayStation

Ch13 Cloud hosting dedicated servers

這章節探討網路遊戲是否需要架設專有伺服器 (dedicated servers) 來營運，抑或是像 Minecraft 那樣由玩家自行架設。後續提到遊戲伺服器撰寫或是部屬伺服器的管理工具，覺得這章對於現在的我來說，比較沒有參考價值，簡略翻一翻。

在雲端平台上建立遊戲伺服器，需要考慮：

複雜度，考慮遊戲伺服器可能需要開一堆伺服器來一起運作，管理這些機器以及發布流程，會變得相當複雜。甚至得自己想 API 或是工具來管理
費用，在雲端平台 (AWS, GCP, or Azure etc…) 架設伺服器不全然是免費的，需要考慮前期成本以及持續維護的成本
- 現在各家平台都有新客戶試用方案 (2017-12 紀錄)
  - AWS free tier 一年免費
  - GCP 提供一年內 300 美元額度
  - Azure 提供三十天內 200 credits 或是一年 free services
未預期的設備調整，雲端平台可能會改變機器設備，需要花時間進行測試

多人網路連線遊戲程式開發之讀書筆記：同步遊戲資料，資料序列化與物件複製，處理網路延遲與伺服器安全性

Ch1 網路遊戲概觀

Ch2 網際網路 Internet

Ch3 Berkeley socket

Ch4 Object serialization

Ch5 Object replication

Ch6 Network topologies

Client-server

Peer-to-peer

Ch7 Latency, Jitter, Reliability

非網路原因 (non-network latency)

網路原因延遲

Round trip time (RTT)

Jitter

Packet loss and Reliability

Ch8 Improved latency handling

Dump terminals

Client side interpolation

Client side prediction

Server side rewind

Ch9 Scalability

Object Scope and Relevancy

Static Zones，分靜態區域

View Frustum，根據可視區域

Other visibility techniques

Relevancy when not visible

Ch10 Security

Packet sniffing

Input validation

Securing the server

Ch11 Real-world engines

Ch12 Gamer Services

Ch13 Cloud hosting dedicated servers

贊助廣告

粉絲專頁

網誌存檔

贊助廣告

全部標籤

多人網路連線遊戲程式開發之讀書筆記：同步遊戲資料，資料序列化與物件複製，處理網路延遲與伺服器安全性

Ch1 網路遊戲概觀

Ch2 網際網路 Internet

Ch3 Berkeley socket

Ch4 Object serialization

Ch5 Object replication

Ch6 Network topologies

Client-server

Peer-to-peer

Ch7 Latency, Jitter, Reliability

非網路原因 (non-network latency)

網路原因延遲

Round trip time (RTT)

Jitter

Packet loss and Reliability

Ch8 Improved latency handling

Dump terminals

Client side interpolation

Client side prediction

Server side rewind

Ch9 Scalability

Object Scope and Relevancy

Static Zones，分靜態區域

View Frustum，根據可視區域

Other visibility techniques

Relevancy when not visible

Ch10 Security

Packet sniffing

Input validation

Securing the server

Ch11 Real-world engines

Ch12 Gamer Services

Ch13 Cloud hosting dedicated servers

相關文章

贊助廣告

粉絲專頁

每周熱門

網誌存檔

贊助廣告

全部標籤