我們今天要講的，正是“數據中心”和“博弈游戲”的結合，但和在線游戲一點關系沒有。

 

今天的話題，是切實發生在數據中心的博弈——從共享的大量計算機和存儲系統中搶占資源。

 

即使是在算力最為充足的的公司——谷歌，員工們也常常進行這樣的博弈。

 

當要求提交任務的計算需求時，一些員工會夸大了他們對資源的請求，以減少與他人共享的數量。有趣的是，其他一些員工則會減少了他們的資源請求，假裝他們的任務可以輕松地在任何一臺計算機上完成。一旦他們在一臺機器上開始任務，相關的操作就會耗盡機器上所有可用的資源，并擠掉他們同事的任務。

 

這些伎倆看起來有點滑稽，但它直指一個真正的問題——效率低下。

 

2018年，全球數據中心耗電量為2050億千瓦時，幾乎和澳大利亞全境的用電量相當，約占世界總量的1%。由于服務器未被充分利用，因此大量能源被浪費掉了。一臺空閑服務器所浪費的電力相當于其峰值用電量的50%；而當服務器開始工作時，其固定的電力成本就將分攤到該工作上。

 

由于運行單個任務的用戶通常只占用服務器資源的20%到30%，因此多個用戶必須共享服務器以提高其利用率，從而提高其能源效率。共享還可以降低資本、運營和基礎設施成本。畢竟，不是每個人都有足夠的錢來建立自己的數據中心。

 

為了分配共享資源，數據中心部署有資源管理系統，根據用戶需求和系統自身目標，對可用的處理器內核、內存容量和網絡資源進行劃分。乍一看，這個任務應該很簡單，因為用戶經常有補充需求。但事實并非如此。共享在用戶之間產生了競爭，正如我們看到的谷歌員工，很可能會扭曲資源的使用。

 

因此，我們可以使用博弈論（game theory），即描述理性決策者之間戰略交互的數學模型，進行了一系列項目，以此來管理這些自私用戶之間的資源分配，同時最大化地提升數據中心的效率。在這種情況下，這種博弈還確實有利于解決資源分配問題。

 

貨幣兌換機制失效，博弈論登場

 

幫助一群理性和自私的用戶有效地共享資源并不僅僅是大數據時代的產物。經濟學家們幾十年來一直在這樣做。

 

在經濟學中，市場機制根據供求來決定資源的價格。實際上，目前不少公共數據中心就在這么做，比如Amazon EC2和Microsoft Azure。在那里，真實貨幣的轉移充當了一種工具，將用戶的動機(績效)與提供商的目標(效率)結合起來。

 

然而，在許多情況下，貨幣兌換機制是失效的。

 

讓我們考慮一個簡單的例子。

 

假設在你最好朋友的婚禮上，你得到了一張歌劇演出的門票，你決定把票給最喜歡該演出的人。所以你要進行所謂的第二價拍賣：讓你的朋友們為這張票出價，規定贏家支付給你第二高的出價。數學上已經證明，在這種拍賣中，你的朋友沒有動機去謊報他們對這張歌劇票的估價。

 

如果你不想要錢或不能讓你的朋友付你錢，你的選擇就會變得非常有限。如果你問你的朋友他們有多想去看歌劇，沒有什么能阻止他們夸大他們對門票的渴望。歌劇票只是一個簡單的例子，但在很多地方——比如谷歌的私人數據中心或學術計算機集群——金錢要不不能轉手，要不就是不該轉手，更不能以此來決定誰得到什么。

 

博弈論為這類問題提供了可行的解決方案——實際上它已被應用于計算機網絡和計算機系統。我們從這兩個領域獲得了靈感，但我們也必須解決它們的局限性。在計算機網絡中，有很多工作通過設計機制來管理自利的和不協調的路由器以避免擁塞。但是這些模型只考慮對單個資源網絡帶寬的爭用。在數據中心計算機集群和服務器中，有各種各樣的資源需要爭奪。

在計算機系統中，人們對考慮多種資源的資源分配機制產生了濃厚的興趣，特別是一種稱為支配資源公平性的機制。然而，這類工作僅限于性能模型和處理器與內存的比率，它們并不總是反映數據中心的真實場景。

 

“計算沖刺”引起“公地悲劇”

 

為了提出適用于數據中心的博弈論模型，我們深入研究了硬件架構的細節，從最小的層次開始：晶體管。

 

長期以來，晶體管在縮小體積的同時耗散的功率越來越小，部分原因是降低了工作電壓。然而，到2005年左右，這種被稱為登納德縮放比例的定律已被打破。

 

結果就是，對于固定的電力預算，處理器不再以我們習慣的速度變快。一個臨時的解決方案是將多個處理器核心放在同一塊芯片上，這樣大量的晶體管仍然可以在經濟上得到冷卻。然而，很明顯，你不可能同時全速運轉所有的核心，否則芯片會熔化。

 

2012年，計算機架構師提出了一種名為“計算沖刺”（computational sprinting）的變通方法。其概念是處理器核心可以在短時間間隔(稱為沖刺)內安全地突破它們的能量預算。在一次沖刺之后，處理器必須在下一次沖刺之前冷卻下來；否則芯片就會被熔毀。如果處理正確，“沖刺”可以使系統對工作負載的變化做出更快速的響應。“計算沖刺”最初是為智能手機等移動設備的處理器而提出的，因為這些處理器必須限制用電量，以節省電量，同時避免“燙傷”用戶。但“沖刺”很快就應用于數據中心來處理計算需求的激增。

 

這就是問題所在。假設自私的用戶們擁有啟用了帶有“沖刺”的服務器，這些服務器在數據中心中共享一個電源供應。用戶可以通過沖刺來提高處理器的計算能力，但如果大部分處理器同時沖刺，那么電力負荷將會激增。然后斷路器跳閘。這就迫使不間斷電源(UPS)中的電池在系統恢復時提供電力。在這樣的緊急情況之后，所有的服務器都必須在電池充電的時候以額定功率運行——不允許沖刺。

 

這種情形是經典的“公地悲劇”（tragedy of the commons）的一個版本，英國經濟學家威廉·福斯特(43.900, 2.11, 5.05%)·勞埃德(William Forster Lloyd)在1833年的一篇文章中首次提出了這一觀點。他描述了如下的情況：假設牧牛人共享一塊土地來放牧他們的牛。如果一個牧民把超過分配數量的牛放到公共草地上，這個牧民可以獲得邊際收益；但如果許多牧民這樣做，過度放牧將破壞土地，傷害所有人。

 

我們與當時杜克大學(Duke University)的博士生Songchun Fan一起，把“沖刺”戰略當作公地悲劇來研究。我們建立了一個關注兩個主要物理約束的系統模型。首先，對于服務器處理器，沖刺要求處理器在芯片散熱時等待，從而限制了未來的操作。其次，對于一個服務器集群，如果斷路器跳閘，那么所有的服務器和處理器必須在UPS電池充電時處于等待狀態。

 

我們設計了一個博弈游戲。在每一輪比賽中，用戶可能處于三種狀態中的一種:活躍狀態、沖刺后的冷卻狀態、緊急斷電后的恢復狀態。在每一輪游戲中，用戶唯一能決定的就是當他們的處理器處于活動狀態時是否進行沖刺。用戶希望優化他們的沖刺以獲得好處，比如提高吞吐量或減少執行時間。但也要注意，這些好處會隨著沖刺的發生時間而變化。例如，沖刺在需求量大的時候更有益。

 

考慮一個簡單的例子。在第5輪，你知道如果此時沖刺將獲得10個單位的收益，然而處理器必須冷卻幾個回合才能再次沖刺。假設現在你沖刺了，那么在第6輪，你會發現沖刺可以獲得20個單位的收益。另一種情況是，你將沖刺權保存到了下一輪但所有其他用戶都決定在第5輪時沖刺，這導致電力緊急情況，使你無法在后續幾輪中沖刺。更糟的是，到那時你的收益就不會那么高了。

 

短跑游戲中的“平均場博弈分析”

 

玩家們使用一個數據中心來共享信息。如果其中一個玩家選擇在第5輪沖刺，他們將獲得一定的收益，但他們必須要等處理器冷卻一段時間才能再次加速。如果他們等到第6輪或者之后再沖刺，他們會獲得更多收益。

 

如果太多的玩家同時沖刺，電流大幅度增加會導致斷電。在計算機集群的不間斷電源電池充電之前，任何人都不能再沖刺，即使是沒有沖刺的玩家4也不行。

 

所有用戶都必須權衡他們獲得的效用的多少和其他用戶的沖刺策略，之后再做出相應的決定。雖然少數用戶競爭的例子可能很有趣，但隨著競爭對手的數量增長到數據中心的規模，做出這些決定就變得非常棘手。

 

幸運的是，我們找到了這種叫做“平均場博弈分析”的方法，可以在在大型系統中優化每個用戶的策略。這種方法將所有用戶策略考慮為一個整體，避免了考慮每個競爭對手策略的復雜性。這種統計方法的關鍵在于假設任何單個用戶行為都不會顯著地改變系統的平均行為。正是由于這一假設，我們可以用單個平均效應來近似所有其他用戶對任何給定用戶的影響。

 

這有點類似于數百萬上班族試圖優化他們的日常出行。我們以文摘菌這樣一個上班族為例。雖然不能用她以一概全。但是，文摘菌的行為模式可以推斷出上班族這一總體在特定一天中希望到達的時間，以及他們的出行計劃會如何加劇道路擁堵等。

平均場分析允許我們找到沖刺游戲的“平均場平衡”。用戶會優化他們對群體的響應。這也意味著，在平衡狀態下，偏離他們對整體的最佳響應將沒有任何好處。

 

在交通情況中，文摘菌會根據對通勤人群平均行為的理解來優化通勤。如果優化后的計劃沒有產生預期的交通模式，她就會修正自己的預期并重新考慮自己的計劃。隨著每一個通勤者在幾天內的一次優化，交通收斂到一些重復的模式，通勤者的獨立行動產生一個平衡。

 

通過平均場平衡，我們制定了沖刺游戲的最優策略：當性能收益超過某個閾值時，用戶應該沖刺。

 

該閾值根據用戶的不同而不同。我們可以使用數據中心的工作負載及其物理特性來計算這個閾值。

 

當每個人都在平均場平衡下以他們的最優閾值運行時，系統將會受益良多。首先，數據中心的電源管理可以是分布式的，因為用戶可以實現他們自己的策略，而不需要向中心管理員請求加速許可。這種獨立性使得功率控制更加靈敏、節能。用戶可以在微秒或更少的時間內調節處理器的功耗。而如果他們必須等待幾十毫秒來獲得許可，才能通過數據中心，那么這種效果將難以實現。其次，用戶可以根據自己的工作負載需求來及時優化加速策略，使得均衡條件下可以完成更多計算工作。最后，當增益超過閾值時，用戶的策略就變成了簡單的沖刺。這是非常容易執行的。

 

貪得無厭必自斃：在沖刺游戲中，與“貪心”策略相比，使用平均場均衡策略可以用更少的力完成更多的功。

 

博弈論必將發揮巨大作用

 

“沖刺管理項目”只是我們在過去五年中開發的一系列數據中心管理系統中的一個。在每一款游戲中，我們都使用了硬件架構和系統的關鍵細節來設計游戲。而這樣利用這一管理機制使得，當參與者行為表現得過于自私利己時，系統依舊可以穩定運行。我們有理由相信，這樣的保證只會鼓勵共享系統的參與，并為節能和可擴展的數據中心奠定堅實的基礎。

 

盡管我們已經設法在服務器多處理器、服務器機柜和服務器集群級別解決了資源分配問題，但是將它們用于大型數據中心仍需要很多工作。一方面，你必須能夠生成數據中心的性能概要。因此，數據中心必須部署必要的基礎設施來監視硬件活動、評估性能結果和推斷對資源的偏好。

 

這類系統的大多數博弈論解決方案都要求分析階段離線進行。相反，構建可以從一些先驗知識開始，然后在執行過程中隨著特征變得更清晰，而更新其參數的在線機制可能干擾更小。在線機制甚至可能通過強化學習或另一種形式的人工智能來改進游戲。

 

還有一個現實問題就是：在數據中心，用戶可以隨時進出系統，任務可以在計算過程中隨意穿插，服務器可能會失敗并重新啟動。所有這些事件都需要重新分配資源，但是這些重新分配可能會破壞整個系統的計算，并要求對數據進行分流，從而耗盡資源。

 

在保持每個人公平競爭的同時，應付所有這些變化肯定需要更多的工作，但我們堅信博弈論必將發揮巨大作用。