概述

云游戲作為一種新興的游戲模式，將游戲的存儲、計算和渲染任務(wù)從本地終端遷移至云端服務(wù)器，使玩家無需配備高性能的硬件，僅通過網(wǎng)絡(luò)實時接收來自云端服務(wù)器的游戲音視頻流，即可暢玩各類大作。云游戲突破了設(shè)備性能的限制，讓“低配”玩家也能擁有“高配”體驗，但同時也對終端與云端服務(wù)器之間的網(wǎng)絡(luò)連接質(zhì)量提出了更高要求。

云游戲技術(shù)架構(gòu)概覽

為了保障云游戲玩家與云端服務(wù)器之間的網(wǎng)絡(luò)連接質(zhì)量，云游戲服務(wù)提供商通常會在全國范圍內(nèi)部署多個云端服務(wù)器節(jié)點。如下圖所示，當(dāng)玩家發(fā)起游戲請求時，調(diào)度系統(tǒng)會根據(jù)其地理位置、網(wǎng)絡(luò)運(yùn)營商等信息，從眾多候選節(jié)點中挑選出一個最合適的，隨后玩家與該節(jié)點建立連接并開始游戲?？梢哉f調(diào)度系統(tǒng)是連接玩家與云端服務(wù)器的關(guān)鍵中樞，它就像一位交通指揮員，為每一位玩家規(guī)劃出最快捷、最順暢的路徑。一般來講，同省同運(yùn)營商的節(jié)點與玩家之間的網(wǎng)絡(luò)連接質(zhì)量最優(yōu)。因此，除了用戶體驗評分之外，同省調(diào)度率也是衡量調(diào)度質(zhì)量的關(guān)鍵指標(biāo)之一。

云游戲用戶建聯(lián)過程

本文回顧了我們在過去一年中圍繞抖音云游戲調(diào)度系統(tǒng)展開的一系列思考和優(yōu)化實踐。具體而言，我們首先設(shè)計并實現(xiàn)了一套離線調(diào)度模擬器，能夠基于線上數(shù)據(jù)精準(zhǔn)模擬、復(fù)現(xiàn)不同調(diào)度策略的效果，助力算法的高效驗證與迭代。其次，我們提出一種基于最小費(fèi)用流的調(diào)度算法，力求在資源有限的條件下盡量逼近全局最優(yōu)調(diào)度。線上部署結(jié)果表明，我們所提出的優(yōu)化策略顯著提升了同省調(diào)度率與用戶體驗評分。從業(yè)務(wù)視角來看，這些優(yōu)化策略帶來了人均游戲時長1~2分鐘的增長，有效增強(qiáng)了云游戲玩家的粘性和整體業(yè)務(wù)表現(xiàn)。更重要的是，我們構(gòu)建了一套可持續(xù)迭代的調(diào)度優(yōu)化機(jī)制，為大規(guī)模云服務(wù)的調(diào)度系統(tǒng)設(shè)計提供了重要參考。

背景介紹

現(xiàn)有方法

目前，云游戲調(diào)度系統(tǒng)普遍采用基于靜態(tài)規(guī)則的服務(wù)器調(diào)度策略，典型方法包括“地理距離優(yōu)先”和“運(yùn)營商優(yōu)先”。簡單來說，就是靠一套預(yù)設(shè)的規(guī)則快速挑選出一個局部最優(yōu)的服務(wù)器節(jié)點。以“運(yùn)營商優(yōu)先”為例，調(diào)度系統(tǒng)通常按照以下優(yōu)先級為用戶分配節(jié)點：同省同運(yùn)營商 > 跨省同運(yùn)營商 > 同省跨運(yùn)營商 > 跨省跨運(yùn)營商，其核心目的是盡量避免因跨運(yùn)營商連接所帶來的網(wǎng)絡(luò)延遲和不穩(wěn)定問題。

??示例一

以“運(yùn)營商優(yōu)先”為例，假設(shè)用戶位于江蘇省，使用的是中國電信網(wǎng)絡(luò)，全國的服務(wù)器節(jié)點如下：

1. 廣西 - 聯(lián)通節(jié)點（跨省跨運(yùn)營商）
2. 湖北 - 移動節(jié)點（跨省跨運(yùn)營商）
3. 江蘇 - 電信節(jié)點（同省同運(yùn)營商）
4. 河北 - 移動節(jié)點（跨省跨運(yùn)營商）

根據(jù)“運(yùn)營商優(yōu)先”的調(diào)度規(guī)則，調(diào)度系統(tǒng)首先會為用戶分配同省且同運(yùn)營商的節(jié)點，即江蘇-電信節(jié)點。若該節(jié)點資源已全部耗盡，系統(tǒng)將依次考慮其他優(yōu)先級稍低的節(jié)點：湖北-移動節(jié)點、河北-移動節(jié)點和廣西-聯(lián)通節(jié)點。

說明：因為湖北在地理位置上與江蘇更近，所以湖北-移動節(jié)點的優(yōu)先級要高于河北-移動節(jié)點。

這類基于靜態(tài)規(guī)則的服務(wù)器調(diào)度策略實現(xiàn)簡單、部署方便，在傳統(tǒng)內(nèi)容分發(fā)網(wǎng)絡(luò)（CDN）或短連接類業(yè)務(wù)中表現(xiàn)尚可。然而，在云游戲場景中就有些“力不從心”了，面對有限的資源，它很難實現(xiàn)全局視角下的最優(yōu)調(diào)度。根本原因在于云游戲與CDN等短連接業(yè)務(wù)在調(diào)度需求上存在顯著差異，具體包括以下三方面：

• 網(wǎng)絡(luò)質(zhì)量要求高：云游戲?qū)W(wǎng)絡(luò)連接質(zhì)量的要求極高，任何輕微的延遲或抖動，都可能轉(zhuǎn)化為玩家的操作不跟手或卡頓，進(jìn)而導(dǎo)致游戲體驗的嚴(yán)重劣化。
• 并發(fā)服務(wù)量低：在CDN這類短連接場景中，一臺服務(wù)器通常可并發(fā)服務(wù)數(shù)百甚至上千名用戶。但云游戲就不一樣了，服務(wù)器需要為每位玩家單獨(dú)完成游戲畫面渲染與編碼，資源開銷極大，單臺服務(wù)器并發(fā)服務(wù)2至3人就已經(jīng)接近極限。
• 連接持續(xù)時間長：CDN的請求就像“打個醬油”——加載個網(wǎng)頁、播個視頻，可能持續(xù)幾秒鐘就搞定了。而云游戲是“長期作戰(zhàn)”——用戶一旦接入服務(wù)器就會持續(xù)連接數(shù)十分鐘甚至數(shù)小時。這意味著，調(diào)度系統(tǒng)一旦在開始時為玩家分配錯服務(wù)器，就會導(dǎo)致該玩家在整個游戲過程中體驗持續(xù)受損，甚至還可能連累到后續(xù)玩家的調(diào)度，出現(xiàn)更嚴(yán)重的問題（參考示例三）。

面臨的挑戰(zhàn)

當(dāng)然，哪怕有一套規(guī)則在手，想在抖音云游戲業(yè)務(wù)中把調(diào)度這件事做好，也遠(yuǎn)不是件容易的事。首先，全國范圍內(nèi)部署的云端服務(wù)器資源有限，且在各省之間分布極不均衡；其次，不同位置的玩家即使連接相同的服務(wù)器，所獲得的體驗評分也存在顯著差異，進(jìn)一步加劇了調(diào)度決策的復(fù)雜性。最后，不同時段發(fā)起的玩家調(diào)度請求數(shù)動態(tài)變化，對調(diào)度策略的適應(yīng)性提出了很大挑戰(zhàn)。基于對大量調(diào)度數(shù)據(jù)的分析，我們將當(dāng)前抖音云游戲調(diào)度系統(tǒng)存在的核心挑戰(zhàn)歸納為以下兩點：

云端服務(wù)器資源分布圖

用戶需求分布圖

服務(wù)器資源分布不均，與用戶需求不匹配。理論上，各省的云端服務(wù)器資源應(yīng)與本地用戶規(guī)模相匹配，這樣才能在地理位置上盡可能實現(xiàn)就近調(diào)度。然而現(xiàn)實往往不盡人意，受限于機(jī)房建設(shè)成本、帶寬容量與場地等因素，當(dāng)前的服務(wù)器資源在全國范圍內(nèi)呈現(xiàn)明顯的不均衡分布。如上圖所示（左圖為各省的云端服務(wù)器資源數(shù)，右圖為各省的用戶需求分布。請注意，所有數(shù)值均已按重慶資源總數(shù)進(jìn)行了歸一化處理），可以明顯看出廣東、江蘇等東部沿海省份具備相對充足的服務(wù)器資源，而中西部與東北地區(qū)則普遍存在資源緊張甚至無資源的情況，迫使大量用戶不得不被調(diào)度至外省。進(jìn)一步對比左右兩圖可以發(fā)現(xiàn)，當(dāng)前的資源供給與用戶需求之間存在嚴(yán)重的不匹配，這將顯著提升用戶跨省調(diào)度的發(fā)生概率。

????示例二

以“運(yùn)營商優(yōu)先”為例，假設(shè)用戶位于貴州省，使用的是中國聯(lián)通網(wǎng)絡(luò)，全國的服務(wù)器節(jié)點如下：

1. 廣西 - 聯(lián)通節(jié)點（跨省同運(yùn)營商）【資源緊張】
2. 湖北 - 移動節(jié)點（跨省跨運(yùn)營商）【資源充?！?/span>
3. 江蘇 - 電信節(jié)點（跨省跨運(yùn)營商）【資源充?！?/span>
4. 河北 - 移動節(jié)點（跨省跨運(yùn)營商）【資源充?！?/span>

因為貴州本省無資源，所以用戶必須被調(diào)度出省。根據(jù)“運(yùn)營商優(yōu)先”的規(guī)則，調(diào)度系統(tǒng)會優(yōu)先將用戶調(diào)度至廣西-聯(lián)通節(jié)點。

靜態(tài)規(guī)則缺乏全局資源協(xié)調(diào)能力，易引發(fā)資源搶占。基于靜態(tài)規(guī)則的調(diào)度策略主要關(guān)注用戶個體的連接屬性（如運(yùn)營商、地理距離等），缺乏對全局資源供需狀態(tài)的協(xié)調(diào)能力，容易導(dǎo)致跨省資源搶占，嚴(yán)重影響整體用戶體驗。此外，基于靜態(tài)規(guī)則的調(diào)度策略未考慮不同地域用戶連接同一節(jié)點時的體驗評分差異，難以實現(xiàn)全局視角下的最優(yōu)調(diào)度。更為嚴(yán)峻的是，在線用戶數(shù)呈現(xiàn)出明顯的波動性，部分地域高峰與低谷時段的在線用戶人數(shù)差距可達(dá)百倍，進(jìn)一步加劇了調(diào)度難度。

??????示例三

以“運(yùn)營商優(yōu)先”為例，假設(shè)用戶位于廣西省，使用的是中國聯(lián)通網(wǎng)絡(luò)。如前所述，基于靜態(tài)規(guī)則的調(diào)度策略會使大量云南、貴州、四川等地的聯(lián)通用戶都優(yōu)先調(diào)度至廣西-聯(lián)通節(jié)點，很容易就把廣西-聯(lián)通節(jié)點的資源消耗一空。在這種前提下，全國的服務(wù)器節(jié)點如下：

1. 廣西 - 聯(lián)通節(jié)點（同省同運(yùn)營商）【資源已耗盡】
2. 湖北 - 移動節(jié)點（跨省跨運(yùn)營商）【資源充裕】
3. 江蘇 - 電信節(jié)點（跨省跨運(yùn)營商）【資源充?！?/span>
4. 河北 - 移動節(jié)點（跨省跨運(yùn)營商）【資源充?！?/span>

此時，哪怕是廣西本省的聯(lián)通用戶，也不得不被調(diào)度到外省的節(jié)點，直接導(dǎo)致廣西用戶的體驗評分大打折扣。這就是靜態(tài)規(guī)則下缺乏全局協(xié)調(diào)能力所引發(fā)的資源搶占問題——本地用戶反而失去了本地資源。需要指出的是，如果調(diào)度規(guī)則優(yōu)先考慮“地理距離”，也會面臨類似的問題，這反映出靜態(tài)規(guī)則在資源緊張、需求起伏、體驗敏感的業(yè)務(wù)環(huán)境下的局限性。

創(chuàng)新概述

針對上述挑戰(zhàn)，我們從“策略驗證”和“調(diào)度優(yōu)化”兩個方面切入，提出兩項關(guān)鍵創(chuàng)新：一方面，我們設(shè)計并實現(xiàn)了一套離線調(diào)度模擬器，能夠支持調(diào)度策略的離線評估與快速迭代；另一方面，我們提出一種基于最小費(fèi)用流的調(diào)度算法，力求在資源受限的條件下實現(xiàn)全局視角下的最優(yōu)調(diào)度。

離線調(diào)度模擬器

工欲善其事，必先利其器。在策略驗證層面，我們設(shè)計并實現(xiàn)了一套離線調(diào)度模擬器，以更高效的解決云游戲調(diào)度系統(tǒng)存在的問題，其由三大核心模塊構(gòu)成：數(shù)據(jù)處理模塊、策略模擬模塊與結(jié)果評估模塊。

首先，數(shù)據(jù)處理模塊負(fù)責(zé)讀取用戶調(diào)度請求信息（包括時間戳、運(yùn)營商、地理位置等）、服務(wù)器節(jié)點信息（如運(yùn)營商、地理位置、資源上限等）以及用戶連接各節(jié)點所獲得的質(zhì)量信息（如體驗評分、平均游戲時長等），并按時間順序依次重放調(diào)度請求，構(gòu)建與線上類似的調(diào)度流程。需要說明的是，為了提升模擬效率，所有調(diào)度請求將以分鐘為粒度進(jìn)行批量處理。接著，策略模擬模塊將根據(jù)設(shè)定的調(diào)度策略為每位用戶選擇最合適的服務(wù)器節(jié)點，并實時更新節(jié)點資源狀態(tài)以及用戶連接信息。節(jié)點一旦被分配，其對應(yīng)資源容量會被立即扣減，并在用戶游戲時長結(jié)束后釋放，實現(xiàn)對資源狀態(tài)的動態(tài)更新。最后，結(jié)果評估模塊將在所有調(diào)度請求模擬完成后計算多項關(guān)鍵指標(biāo)，包括平均用戶體驗得分、同省調(diào)度率、資源使用率等，為各種策略的評估與對比提供數(shù)據(jù)支撐。

總之，該模擬器綜合考慮用戶分布、服務(wù)器資源容量以及用戶質(zhì)量等關(guān)鍵因素，不僅可以量化分析不同的服務(wù)器部署方案（如節(jié)點選址、資源分布）對調(diào)度結(jié)果的影響，還支持新策略的效果驗證與快速迭代，切實提升調(diào)度策略的優(yōu)化效率。

性能驗證

為評估離線調(diào)度模擬器的效果，我們在相同的資源配置與調(diào)度策略下，將其模擬結(jié)果與線上真實系統(tǒng)的運(yùn)行數(shù)據(jù)進(jìn)行了對比。下表展示了全國及部分省份在兩個核心調(diào)度指標(biāo)——平均用戶體驗評分、同省調(diào)度率上的對比情況。其中，藍(lán)色為模擬結(jié)果，綠色為真實數(shù)據(jù)。

從全國數(shù)據(jù)來看，平均用戶體驗評分的模擬值與真實值僅相差0.002，誤差極??；同省調(diào)度率的差異為1.64%，主要源于線上機(jī)房可能存在臨時維護(hù)或屏蔽等特殊情況，整體誤差處于可接受范圍之內(nèi)。

模擬結(jié)果與線上結(jié)果高度一致，說明所提出的離線調(diào)度模擬器具備高質(zhì)量的仿真性能，為后續(xù)調(diào)度系統(tǒng)的優(yōu)化與迭代提供了堅實基礎(chǔ)。

基于最小費(fèi)用流的調(diào)度算法

最小費(fèi)用流網(wǎng)絡(luò)結(jié)構(gòu)

在調(diào)度優(yōu)化層面，我們提出了基于最小費(fèi)用流的調(diào)度算法，將優(yōu)化目標(biāo)設(shè)定為用戶體驗評分與同省調(diào)度率的加權(quán)指標(biāo)，并通過線性規(guī)劃方法進(jìn)行求解以計算在資源受限場景下可實現(xiàn)全局視角下的理論最優(yōu)調(diào)度結(jié)果。如上圖所示，我們將每分鐘的調(diào)度過程建模為一個單源匯的最小費(fèi)用流網(wǎng)絡(luò)，網(wǎng)絡(luò)由三類節(jié)點組成。

在該網(wǎng)絡(luò)框架下，每位用戶只能被分配至一個服務(wù)器節(jié)點，且各節(jié)點的資源容量有限。值得一提的是，為了全面優(yōu)化調(diào)度效果，我們將優(yōu)化目標(biāo)設(shè)定為用戶體驗評分和同省調(diào)度獎勵分的加權(quán)值，確保這兩個關(guān)鍵指標(biāo)共同作用于調(diào)度決策。系統(tǒng)以分鐘為粒度，根據(jù)當(dāng)前在線的用戶與節(jié)點資源情況，動態(tài)求解理論最優(yōu)調(diào)度策略，并計算對應(yīng)的平均體驗評分和同省調(diào)度率，作為該時刻的理論最優(yōu)值。進(jìn)一步地，系統(tǒng)將所有時刻的最優(yōu)結(jié)果進(jìn)行求平均，即可計算出在當(dāng)前資源配置和用戶負(fù)載條件下可實現(xiàn)的理論性能上限。通過對比分析線上實際調(diào)度結(jié)果與理論最優(yōu)結(jié)果之間的差異，我們能夠識別調(diào)度策略的優(yōu)化空間，并基于此設(shè)計新的調(diào)度算法，逐步縮小實際與理論最優(yōu)值之間的差距，從而提升整體調(diào)度效果。

實踐案例

資源部署優(yōu)化

在現(xiàn)有調(diào)度系統(tǒng)中，云端服務(wù)器資源的空間分布與用戶需求存在明顯不匹配。為了緩解上述供需矛盾，并結(jié)合業(yè)務(wù)方的資源遷移需求，我們基于離線調(diào)度模擬器對當(dāng)前的資源部署情況進(jìn)行了系統(tǒng)性評估與優(yōu)化分析，提出一項資源遷移優(yōu)化策略：將福建省的部分服務(wù)器資源遷移至資源緊張的河北省，并保持其他省份的資源情況不變，預(yù)期可有效提升用戶體驗評分和同省調(diào)度率。

我們使用離線調(diào)度模擬器對該遷移方案進(jìn)行了仿真測試，為實際部署提供數(shù)據(jù)支撐和決策依據(jù)。

模擬結(jié)果 vs 線上結(jié)果

線上結(jié)果表明，資源部署優(yōu)化后全國的同省調(diào)度率提升了4.23%（58.31%->62.54%），這一趨勢與離線調(diào)度模擬器中的預(yù)測結(jié)果基本一致，驗證了模擬器在資源部署評估和優(yōu)化中的有效性與可靠性。

調(diào)度算法優(yōu)化

為進(jìn)一步提升調(diào)度系統(tǒng)的整體性能，我們圍繞“如何逼近理論最優(yōu)調(diào)度結(jié)果”這一核心問題，提出了調(diào)度算法優(yōu)化方案，其包括兩個關(guān)鍵步驟：

1. 求解理論最優(yōu)調(diào)度結(jié)果：使用基于最小費(fèi)用流的調(diào)度算法求解在當(dāng)前的資源配置和用戶負(fù)載條件下可達(dá)到的理論最優(yōu)調(diào)度結(jié)果
2. 計算線上調(diào)度優(yōu)先級策略（以終為始）：以理論最優(yōu)調(diào)度結(jié)果為目標(biāo)，反向計算各個省份用戶與各個云服務(wù)器節(jié)點的優(yōu)先級，使實際調(diào)度行為盡可能逼近最優(yōu)調(diào)度結(jié)果，縮小實際體驗與理論上界之間的差距，進(jìn)而優(yōu)化整體調(diào)度效果。

我們使用離線調(diào)度模擬器對優(yōu)化后的調(diào)度算法進(jìn)行了模擬，以評估其性能。

模擬結(jié)果 vs 線上結(jié)果

線上結(jié)果表明，優(yōu)化后的調(diào)度算法顯著提升了平均用戶體驗評分和同省調(diào)度率，證明新算法的有效性。同時，實際結(jié)果與離線模擬結(jié)果的預(yù)測趨勢高度一致，進(jìn)一步驗證了模擬器的準(zhǔn)確性。

總結(jié)

本文針對云游戲調(diào)度系統(tǒng)中資源分布不均、靜態(tài)規(guī)則低效等關(guān)鍵問題，提出了一套系統(tǒng)性的優(yōu)化方法論，包括離線調(diào)度模擬器的設(shè)計與基于最小費(fèi)用流的調(diào)度算法優(yōu)化。通過資源部署與調(diào)度策略的聯(lián)合優(yōu)化，顯著提升了調(diào)度效果，線上評估結(jié)果顯示，同省調(diào)度率和人均體驗評分均有顯著提升。

更重要的是，所提出的離線調(diào)度模擬器具備出色的仿真精度與泛化能力，能夠有效預(yù)估優(yōu)化方案的潛在收益，有助于調(diào)度策略的快速迭代。這不僅為云游戲調(diào)度系統(tǒng)的持續(xù)優(yōu)化奠定了堅實基礎(chǔ)，而且為大規(guī)模云服務(wù)調(diào)度系統(tǒng)的設(shè)計提供了重要參考。