支援大型多人線上遊戲伺服器叢集的負載平衡策略的設計與實作

Load Balancing Policies for a Server Cluster Supporting Massively Multiplayer Online Games

陳弘勳(Hung-Hsun Chen)

指導教授 ： 姜美玲

國立暨南國際大學/管理學院/資訊管理學系/碩士(2016年)

摘要

現行的大型多人線上遊戲，為了能夠同時服務大量的玩家，且兼顧遊戲伺服器連線的品質，並且有效率地利用遊戲伺服器的資源，採用伺服器叢集系統(Server Cluster)為較佳的方式。將遊戲地圖切割並將玩家分流給不同的遊戲伺服器來進行服務的提供，可以分散遊戲的負載。玩家可以在不同的遊戲地圖之上進行活動，或者前進至不同的遊戲地圖，但是玩家並不一定會均勻地分佈於不同的地圖，因此熱門的遊戲地圖會造成熱點(Hotspot)的產生。如何有效率地利用伺服器資源，將遊戲地圖和玩家平均地分配於遊戲伺服器叢集的各個伺服器之上，為本論文主要探討的議題。

在Linux Virtual Server with Content-Aware Dispatching(LVS-CAD)遊戲伺服器叢集[11,12]中，實作了Kernel-Level的Game Connection Handoff機制[8,9]，成功地將單一伺服器架構的Open Source遊戲-Stendhal[10]轉變為Multi-Server架構。而將遊戲地圖分配給各個伺服器來服務的分配策略，會嚴重地影響整個伺服器叢集的負載平衡。

於本論文中，我們提出以eMPNM(expected Maximal Players on Neighboring Maps)負載平衡分配策略為主的三種負載平衡策略。在分配遊戲地圖至遊戲伺服器時，除了考量地圖的相鄰性外，並考量相鄰地圖上的玩家人數，以及從地圖之間的相鄰性來預期玩家移動至本地圖的機率，進而預期相鄰地圖上的玩家對伺服器的負載可能造成的影響，來動態地分配地圖至伺服器來服務。目的是要盡量維持伺服器所分配到的地圖的完整性，以減少系統執行Game Connection Handoff的次數，進而提升系統的效能。

我們的eMPNM策略是實作於LVS-CAD遊戲伺服器叢集[11,12]的Linux Kernel中，實驗中我們將eMPNM與GLARD[8]和GSLARD[9]等不同的動態分配策略進行效能的比較，並且分析遊戲地圖在伺服器叢集中分佈的情形，同時測量各種分配策略對於遊戲世界分配的完整性以及伺服器資源使用效率的影響。實驗結果顯示，eMPNM動態分配策略除了考量地圖的相鄰性外，並考量以相鄰地圖上玩家人數，以及預期相鄰地圖上的玩家移動至本地圖機率，它的效能會比起只有單純考慮伺服器負載情形的GLARD動態分配策略，以及只有考慮地圖相鄰性和伺服器負載情形的GSLARD動態分配策略，在地圖分配的完整性、伺服器叢集封包輸出情形、執行Game Connection Handoff的次數上，皆有較佳的表現。

關鍵字

多人線上遊戲 ； 伺服器叢集 ； 負載平衡 ； 遊戲地圖 ； Linux核心

並列摘要

In order to serve a large quantity of players and use game servers’ resource effectively, massively multiplayer online games (MMOGs) nowadays widely adopt the architecture of cluster-based server system. By dividing game maps and assigning players on them to different game servers, we can distribute game loads among game servers. During the game play, players can move freely on any game map. Hotspots thus appear in popular game maps. The aim of this paper is to assign game maps and players to game servers in the server cluster evenly, and use resources of game servers effectively.

In previous study[8], the kernel-level Game Connection Handoff mechanism is implemented in the Linux Virtual Server with Content-Aware Dispatching (LVS-CAD) game cluster [11,12], which successfully turns an open-source game – Stendhal [10] from a single-server architecture into a multi-server one. In this architecture, policies for dispatching game maps to servers greatly affect the load balancing and the performance of servers. In this paper, we propose a load balancing policy named eMPNM (expected Maximal Players on Neighboring Maps) to dynamically dispatch maps to servers. When selecting a target server to serve a certain map, eMPNM considers several factors such as the adjacency of maps, the amount of players on the neighboring maps, and the expected amount of players' moving to the map. The goal is to maintain the integrity of the maps assigned to each server, which alleviates the need to perform Game Connection Handoff and improves system performance.

We have implemented eMPNM in the Linux kernel of the LVS-CAD game cluster. We also compare the performance of eMPNM with GLARD [8] and GSLARD[9], and analyze the distribution of game maps to servers. Moreover, we measure the influence of map integrity due to map assignment and the resource utilization of the cluster using different load balancing policies. The experimental results demonstrate that eMPNM out performs GLARD, which considers load balancing only, and GSLARD, which takes both load balancing and map adjacency into account in assigning maps to servers.

並列關鍵字

Massively Multiplayer Online Game ； Server Cluster ； Load Balancing ； Game Maps ； Linux Kernel

參考文獻

[1] “Tree of Savior”, http://tos.nexon.com/, 2015.

[2] “Second Life”, http://secondlife.com/, 2015.

[3] “Ingress”, https://www.ingress.com/, 2015.

[4] “The King of Augmented Reality Street Fighting”, http://motherboard.vice.com/.

[5] Xinyu Zhuang, Ashwin Bharambe, Jeffrey Pang, and Srinivasan Seshan, “Player Dynamics in Massively Multiplayer Online Games”, http://reports-archive.adm.cs.cmu.edu/anon/2007/CMU-CS-07-158.pdf.