博弈論應有的作用

“數據中心”和“博弈”（其英文為game，亦有游戲之意）二詞可能會讓人聯想到《魔獸世界》等多人在線游戲。但數據中心內還上演著另一種博弈，即共享計算機和存儲系統(tǒng)對資源的搶占。 甚至數據量堪稱最大的谷歌公司的員工也曾進行過這樣的博弈。當要求提交某項工作的計算需求時，一些員工為了減少與他人共享的資源數量而夸大資源請求。

有趣的是，還有些員工會減少資源請求，假裝自己的任務可以在任何計算機中輕松完成。一旦他們的任務被提交到機器上，就會耗盡機器上所有可用的資源，擠兌其他任務。 這種伎倆看起來有點滑稽，實際上卻引發(fā)了真正的問題——效率低下。 2018年，全球數據中心耗電量達2050億千瓦時，差不多和澳大利亞全境的用電量相當，約占全世界總用電量的1%。因服務器未能滿負荷運行，大量能源被浪費。一臺服務器空閑時消耗的電力是其峰值運行時的50%，因為服務器運行任務時，其固定電力成本會分攤到該任務上。運行單任務的用戶通常只占用20%到30%的服務器資源，因此多個用戶必須共享服務器，以提高利用率，進而提升能源效率。共享服務器還可以降低資金、運營和基礎設施的成本。畢竟并非人人都有足夠的財力來建立屬于自己的數據中心。為了分配共享資源，數據中心部署資源管理系統(tǒng)，根據用戶需求和系統(tǒng)自身目標來分配可用的處理器內核、內存容量和網絡資源。乍一看，這項任務應當是簡單明了的，因為用戶往往會有互補需求。但事實并非如此。共享造成了用戶之間的競爭，就如谷歌投機取巧的員工那樣，這會扭曲資源的使用。因此，我們開展了一系列項目，采用博弈論，即描述理性決策者之間策略互動的數學模型，來管理利己用戶之間的資源分配，實現數據中心效率最大化。采用博弈論后，情況變得大為不同。

幫助一群理性而利己的用戶有效共享資源不是大數據時代的產物。幾十年來，經濟學家一直在這樣做。在經濟學中，市場機制根據供求來決定資源的價格。實際上，亞馬遜EC2和微軟Azure等公共數據中心中都部署了此類機制。在那里，真實的貨幣轉移作為一種工具，使用戶動機（性能）與提供商目標（效率）趨于一致。然而，很多情況下，貨幣交換并不起作用。

舉一個簡單的例子。假設你在最好朋友的婚禮上得到一張歌劇票，你決定把票贈送給最喜歡這場歌劇的人。因此你要進行所謂的第二價格密封拍賣：你讓朋友出價，規(guī)定贏家支付第二高的競價。數學上已經證明，在這場拍賣中，你的朋友沒有動機謊報對這張歌劇票的估價。如果你不想要錢或不讓朋友付給你錢，你的選擇就會變得非常有限。如果你詢問朋友想看歌劇的意愿，他們定會夸大想要歌劇票的愿望。歌劇票只是一個簡單的例子，但在很多地方，比如谷歌私人數據中心或學術計算機集群，金錢要么不能轉手，要么不該轉手，因此不能以此來決定歸誰所有。博弈論恰好為此類問題提供了實用的解決方案，并已實用于計算機網絡和計算機系統(tǒng)。我們可以從這兩個領域獲得靈感，但也不必解決其局限性。為避免計算機網絡擁塞，人們在設計管理機制方面做了很多工作，以此來管理自利和不協調的路由器。但是這些模型只考慮了對單個資源——網絡帶寬——的爭搶；而在數據中心計算機集群和服務器中，要爭奪的有各種各樣的資源。在計算機系統(tǒng)中，人們對考慮多種資源分配機制的興趣越來越濃厚，其中非常著名的是主體資源公平機制。然而，這類工作僅限于性能模型以及處理器與內存的比率，并不總能反映數據中心的情況。為提出適用于數據中心的博弈論模型，我們深入研究硬件架構的細節(jié)，從最小層次——晶體管開始。長期以來，晶體管功耗隨體積縮小而降低，部分原因在于工作電壓降低。然而，20世紀初，這種被稱為登納德縮放比例的定律被打破。其結果是，在固定功率預算內，處理器的速度不能再按照我們習慣的速度增長。臨時解決方案是在同一芯片內安置多個處理器內核，這樣仍可以經濟地冷卻大量的晶體管。然而，你很快發(fā)現，長時間全速開啟運行所有內核會熔化芯片。2012年，計算機架構師提出了一種叫作“計算沖刺”（computational sprinting）的變通方法。其概念是，處理器內核在較短的時間隔內安全地突破功率預算，稱為沖刺。一次沖刺之后，處理器必須在下一次沖刺之前冷卻下來；否則芯片就會損毀。如果處理得當，沖刺可使系統(tǒng)更快速地響應工作負載的變化。沖刺計算最初針對的是智能手機等移動設備的處理器，這些處理器必須限制功耗，節(jié)省電量，同時避免灼傷用戶。但沖刺很快便應用于數據中心，幫助處理瞬時激增的計算需求。

這便是問題所在。假設自私用戶啟用可實現沖刺的服務器，這些服務器在數據中心中共享一個電源。用戶可以通過沖刺來提高處理器的計算能力，但若眾多處理器同時沖刺，電源負荷將會激增，斷路器將跳閘。在系統(tǒng)恢復時，迫使不間斷電源（UPS）中的電池提供電力。電力應急狀況出現后，電池需要充電，在此期間連接此電源的所有服務器都必須按額定功率運行，不允許沖刺。

這種情形是典型“公地悲劇”的一個版本，英國經濟學家威廉?福斯特?羅伊德 （William Forster Lloyd）在1833年的一篇文章中首次提出這一概念。他描述了如下情況：假設牧民共享一片牧牛地。如果一位牧民的牧牛超過規(guī)定數量，他就可以獲得邊際收益。但如果許多牧民效仿，過度放牧就會破壞土地，無人能獨善其身。我們與當時杜克大學的博士生樊淞春（Songchun Fan，音）將沖刺策略作為公地悲劇來研究。我們構建了一個關注兩個主要物理約束的系統(tǒng)模型。首先，對于服務器處理器，在芯片散熱時，要求處理器等待，并限制下一次沖刺操作。其次，對于服務器集群，如果斷路器跳閘，在不間斷電源（UPS）電池充電期間，所有服務器處理器都必須等待。我們設計了一個沖刺博弈游戲，用戶在每一回合中可能處于活躍狀態(tài)、沖刺后的冷卻狀態(tài)或緊急斷電后的恢復狀態(tài)。在每個回合，或者每一輪游戲中，用戶唯一的決定是處理器處于活躍狀態(tài)時是否進行沖刺。用戶希望優(yōu)化沖刺的收益，比如提高吞吐量或減少執(zhí)行時間。注意，這些收益會隨著沖刺的時間而變化。例如，需求越高，沖刺收益越大。

舉一個簡單的例子。假如你正處于第5回合游戲，沖刺將為你帶來10個單位的收益。然而，你必須讓處理器冷卻幾輪才能再次沖刺。如果等到第6回合再沖刺，你可以獲得20個單位的收益?；蛘吣愦蛩悴辉诘?回合沖刺，而保留到未來某一回合，但所有其他用戶都決定在第5回合沖刺，于是出現了電力應急情況，導致你無法在后面數回合中沖刺。更糟糕的是，你的收益降低了。所有用戶的決策都必須基于他們的獲益和其他用戶的沖刺策略。當少數幾個用戶博弈時或許很有趣，但當競爭對手的數量增長到數據中心規(guī)模時，決策就變得非常棘手。幸好，我們發(fā)現了在大型系統(tǒng)中優(yōu)化每個用戶策略的方法，即所謂的平均場博弈分析。這一方法將用戶行為描述為一個整體，避免了審視每個競爭對手策略的復雜性。這種統(tǒng)計方法的關鍵是假設任何單個用戶的動作都不會明顯改變平均系統(tǒng)行為?；谶@一假設，我們可估計所有用戶對任意指定用戶造成的影響。這類似于千百萬個上班族試圖優(yōu)化日常出行的方法。比如有一個上班族名叫愛麗絲，她不可能對每個路人的出行方式進行推斷，但她可以將所有上班族作為一個群體來形成某種預測，比如某一天他們希望到達的時間，以及他們的出行計劃對交通擁堵的影響。平均場博弈分析能夠使我們找到沖刺游戲的“平均場平衡”。用戶優(yōu)化自己對群體的響應，在平衡狀態(tài)下，偏離用戶對群體的最佳響應不會給用戶帶來益處。在交通領域的類比中，愛麗絲據其對通勤群體平均行為的了解來優(yōu)化自己的通勤。如果優(yōu)化后的計劃未能達到預期交通模式，她會校正預測并重新考慮計劃。隨著每位上班族幾天優(yōu)化一次，交通趨于某種重復的模式，上班族的獨立行為便會產生一種整體的平衡。

根據平均場平衡，我們制定了沖刺博弈游戲的最優(yōu)策略，可歸結如下：當性能增益超過某個閾值（具體視用戶而定）時，用戶應沖刺?？梢酝ㄟ^數據中心的工作負載及其物理特性來計算這一閾值。在平均場平衡狀態(tài)下，每位用戶都以其最優(yōu)閾值運行，系統(tǒng)可獲得諸多收益。首先，數據中心的電源可以實現分布式管理，用戶無須向中央管理器請求沖刺許可，可自行實施策略。這種獨立使電源控制更加靈敏、節(jié)能。用戶可以在幾微秒的時間內調節(jié)處理器功耗，而如果他們必須等待幾十毫秒才能獲得許可并通過數據中心，那么這種效果將難以實現。其次，平衡可以完成更多計算工作，用戶可以根據自己的工作負載需求適時優(yōu)化沖刺策略。最后，用戶的策略變得簡單明了——當增益超過閾值時進行沖刺。這非常易于實現，且便于執(zhí)行。

我們在過去5年里開發(fā)了一系列數據中心管理系統(tǒng)，沖刺電源管理項目僅僅是其中之一。在每一個系統(tǒng)中，我們都使用硬件架構和系統(tǒng)的關鍵細節(jié)來規(guī)劃博弈。當參與者表現出自私的行為時，建成的實用管理機制也可保障系統(tǒng)能夠穩(wěn)定運行。我們相信，這種保障會鼓勵參與共享系統(tǒng)，并為節(jié)能和可擴展的數據中心奠定堅實基礎。

盡管我們已經設法解決服務器多處理器、服務器機架和服務器集群級別的資源分配問題，但是將它們用于大型數據中心仍將需要更多的工作。首先，必須能夠生成數據中心的性能配置文件。數據中心必須部署監(jiān)視硬件運行的必要設施、評估性能效果并推算資源參數。此類系統(tǒng)的多數博弈論解決方案都要離線分析階段。而更積極一點的方法，可以從一些先驗知識開始建造在線機制，然后在執(zhí)行過程中隨著特征變得更清晰，不斷更新其參數。甚至可能通過強化學習或其他形式的人工智能來在線改進機制的博弈規(guī)則。另外，在數據中心，用戶可能隨時到達和離開系統(tǒng)；任務可能會在不同階段進入和退出；服務器可能會發(fā)生故障并重新啟動。所有這些事件都需要重新分配資源，但是資源的重新分配可能會破壞整個系統(tǒng)的計算，要求數據分流，從而耗盡資源。在保持每個人公平博弈的同時，應對所有這些變化都需要進行更多的工作，但我們相信博弈論將發(fā)揮其應有的作用。