博弈論應(yīng)有的作用

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

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

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

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

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

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

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

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

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

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