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

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

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

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

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

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

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

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

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

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

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