我們今天要講的，正是“數(shù)據(jù)中心”和“博弈游戲”的結(jié)合，但和在線游戲一點(diǎn)關(guān)系沒有。
今天的話題，是切實(shí)發(fā)生在數(shù)據(jù)中心的博弈——從共享的大量計(jì)算機(jī)和存儲系統(tǒng)中搶占資源。
即使是在算力最為充足的的公司——谷歌，員工們也常常進(jìn)行這樣的博弈。
當(dāng)要求提交任務(wù)的計(jì)算需求時(shí)，一些員工會夸大了他們對資源的請求，以減少與他人共享的數(shù)量。有趣的是，其他一些員工則會減少了他們的資源請求，假裝他們的任務(wù)可以輕松地在任何一臺計(jì)算機(jī)上完成。一旦他們在一臺機(jī)器上開始任務(wù)，相關(guān)的操作就會耗盡機(jī)器上所有可用的資源，并擠掉他們同事的任務(wù)。
這些伎倆看起來有點(diǎn)滑稽，但它直指一個(gè)真正的問題——效率低下。
2018年，全球數(shù)據(jù)中心耗電量為2050億千瓦時(shí)，幾乎和澳大利亞全境的用電量相當(dāng)，約占世界總量的1%。由于服務(wù)器未被充分利用，因此大量能源被浪費(fèi)掉了。一臺空閑服務(wù)器所浪費(fèi)的電力相當(dāng)于其峰值用電量的50%；而當(dāng)服務(wù)器開始工作時(shí)，其固定的電力成本就將分?jǐn)偟皆摴ぷ魃稀?/div>
由于運(yùn)行單個(gè)任務(wù)的用戶通常只占用服務(wù)器資源的20%到30%，因此多個(gè)用戶必須共享服務(wù)器以提高其利用率，從而提高其能源效率。共享還可以降低資本、運(yùn)營和基礎(chǔ)設(shè)施成本。畢竟，不是每個(gè)人都有足夠的錢來建立自己的數(shù)據(jù)中心。
為了分配共享資源，數(shù)據(jù)中心部署有資源管理系統(tǒng)，根據(jù)用戶需求和系統(tǒng)自身目標(biāo)，對可用的處理器內(nèi)核、內(nèi)存容量和網(wǎng)絡(luò)資源進(jìn)行劃分。乍一看，這個(gè)任務(wù)應(yīng)該很簡單，因?yàn)橛脩艚?jīng)常有補(bǔ)充需求。但事實(shí)并非如此。共享在用戶之間產(chǎn)生了競爭，正如我們看到的谷歌員工，很可能會扭曲資源的使用。
因此，我們可以使用博弈論（game theory），即描述理性決策者之間戰(zhàn)略交互的數(shù)學(xué)模型，進(jìn)行了一系列項(xiàng)目，以此來管理這些自私用戶之間的資源分配，同時(shí)最大化地提升數(shù)據(jù)中心的效率。在這種情況下，這種博弈還確實(shí)有利于解決資源分配問題。
貨幣兌換機(jī)制失效，博弈論登場
幫助一群理性和自私的用戶有效地共享資源并不僅僅是大數(shù)據(jù)時(shí)代的產(chǎn)物。經(jīng)濟(jì)學(xué)家們幾十年來一直在這樣做。
在經(jīng)濟(jì)學(xué)中，市場機(jī)制根據(jù)供求來決定資源的價(jià)格。實(shí)際上，目前不少公共數(shù)據(jù)中心就在這么做，比如Amazon EC2和Microsoft Azure。在那里，真實(shí)貨幣的轉(zhuǎn)移充當(dāng)了一種工具，將用戶的動機(jī)(績效)與提供商的目標(biāo)(效率)結(jié)合起來。
然而，在許多情況下，貨幣兌換機(jī)制是失效的。
讓我們考慮一個(gè)簡單的例子。
假設(shè)在你最好朋友的婚禮上，你得到了一張歌劇演出的門票，你決定把票給最喜歡該演出的人。所以你要進(jìn)行所謂的第二價(jià)拍賣：讓你的朋友們?yōu)檫@張票出價(jià)，規(guī)定贏家支付給你第二高的出價(jià)。數(shù)學(xué)上已經(jīng)證明，在這種拍賣中，你的朋友沒有動機(jī)去謊報(bào)他們對這張歌劇票的估價(jià)。
如果你不想要錢或不能讓你的朋友付你錢，你的選擇就會變得非常有限。如果你問你的朋友他們有多想去看歌劇，沒有什么能阻止他們夸大他們對門票的渴望。歌劇票只是一個(gè)簡單的例子，但在很多地方——比如谷歌的私人數(shù)據(jù)中心或?qū)W術(shù)計(jì)算機(jī)集群——金錢要不不能轉(zhuǎn)手，要不就是不該轉(zhuǎn)手，更不能以此來決定誰得到什么。
博弈論為這類問題提供了可行的解決方案——實(shí)際上它已被應(yīng)用于計(jì)算機(jī)網(wǎng)絡(luò)和計(jì)算機(jī)系統(tǒng)。我們從這兩個(gè)領(lǐng)域獲得了靈感，但我們也必須解決它們的局限性。在計(jì)算機(jī)網(wǎng)絡(luò)中，有很多工作通過設(shè)計(jì)機(jī)制來管理自利的和不協(xié)調(diào)的路由器以避免擁塞。但是這些模型只考慮對單個(gè)資源網(wǎng)絡(luò)帶寬的爭用。在數(shù)據(jù)中心計(jì)算機(jī)集群和服務(wù)器中，有各種各樣的資源需要爭奪。
在計(jì)算機(jī)系統(tǒng)中，人們對考慮多種資源的資源分配機(jī)制產(chǎn)生了濃厚的興趣，特別是一種稱為支配資源公平性的機(jī)制。然而，這類工作僅限于性能模型和處理器與內(nèi)存的比率，它們并不總是反映數(shù)據(jù)中心的真實(shí)場景。
“計(jì)算沖刺”引起“公地悲劇”
為了提出適用于數(shù)據(jù)中心的博弈論模型，我們深入研究了硬件架構(gòu)的細(xì)節(jié)，從最小的層次開始：晶體管。
長期以來，晶體管在縮小體積的同時(shí)耗散的功率越來越小，部分原因是降低了工作電壓。然而，到2005年左右，這種被稱為登納德縮放比例的定律已被打破。
結(jié)果就是，對于固定的電力預(yù)算，處理器不再以我們習(xí)慣的速度變快。一個(gè)臨時(shí)的解決方案是將多個(gè)處理器核心放在同一塊芯片上，這樣大量的晶體管仍然可以在經(jīng)濟(jì)上得到冷卻。然而，很明顯，你不可能同時(shí)全速運(yùn)轉(zhuǎn)所有的核心，否則芯片會熔化。
2012年，計(jì)算機(jī)架構(gòu)師提出了一種名為“計(jì)算沖刺”（computational sprinting）的變通方法。其概念是處理器核心可以在短時(shí)間間隔(稱為沖刺)內(nèi)安全地突破它們的能量預(yù)算。在一次沖刺之后，處理器必須在下一次沖刺之前冷卻下來；否則芯片就會被熔毀。如果處理正確，“沖刺”可以使系統(tǒng)對工作負(fù)載的變化做出更快速的響應(yīng)。“計(jì)算沖刺”最初是為智能手機(jī)等移動設(shè)備的處理器而提出的，因?yàn)檫@些處理器必須限制用電量，以節(jié)省電量，同時(shí)避免“燙傷”用戶。但“沖刺”很快就應(yīng)用于數(shù)據(jù)中心來處理計(jì)算需求的激增。
這就是問題所在。假設(shè)自私的用戶們擁有啟用了帶有“沖刺”的服務(wù)器，這些服務(wù)器在數(shù)據(jù)中心中共享一個(gè)電源供應(yīng)。用戶可以通過沖刺來提高處理器的計(jì)算能力，但如果大部分處理器同時(shí)沖刺，那么電力負(fù)荷將會激增。然后斷路器跳閘。這就迫使不間斷電源(UPS)中的電池在系統(tǒng)恢復(fù)時(shí)提供電力。在這樣的緊急情況之后，所有的服務(wù)器都必須在電池充電的時(shí)候以額定功率運(yùn)行——不允許沖刺。
這種情形是經(jīng)典的“公地悲劇”（tragedy of the commons）的一個(gè)版本，英國經(jīng)濟(jì)學(xué)家威廉·福斯特(43.900, 2.11, 5.05%)·勞埃德(William Forster Lloyd)在1833年的一篇文章中首次提出了這一觀點(diǎn)。他描述了如下的情況：假設(shè)牧牛人共享一塊土地來放牧他們的牛。如果一個(gè)牧民把超過分配數(shù)量的牛放到公共草地上，這個(gè)牧民可以獲得邊際收益；但如果許多牧民這樣做，過度放牧將破壞土地，傷害所有人。
我們與當(dāng)時(shí)杜克大學(xué)(Duke University)的博士生Songchun Fan一起，把“沖刺”戰(zhàn)略當(dāng)作公地悲劇來研究。我們建立了一個(gè)關(guān)注兩個(gè)主要物理約束的系統(tǒng)模型。首先，對于服務(wù)器處理器，沖刺要求處理器在芯片散熱時(shí)等待，從而限制了未來的操作。其次，對于一個(gè)服務(wù)器集群，如果斷路器跳閘，那么所有的服務(wù)器和處理器必須在UPS電池充電時(shí)處于等待狀態(tài)。
我們設(shè)計(jì)了一個(gè)博弈游戲。在每一輪比賽中，用戶可能處于三種狀態(tài)中的一種:活躍狀態(tài)、沖刺后的冷卻狀態(tài)、緊急斷電后的恢復(fù)狀態(tài)。在每一輪游戲中，用戶唯一能決定的就是當(dāng)他們的處理器處于活動狀態(tài)時(shí)是否進(jìn)行沖刺。用戶希望優(yōu)化他們的沖刺以獲得好處，比如提高吞吐量或減少執(zhí)行時(shí)間。但也要注意，這些好處會隨著沖刺的發(fā)生時(shí)間而變化。例如，沖刺在需求量大的時(shí)候更有益。
考慮一個(gè)簡單的例子。在第5輪，你知道如果此時(shí)沖刺將獲得10個(gè)單位的收益，然而處理器必須冷卻幾個(gè)回合才能再次沖刺。假設(shè)現(xiàn)在你沖刺了，那么在第6輪，你會發(fā)現(xiàn)沖刺可以獲得20個(gè)單位的收益。另一種情況是，你將沖刺權(quán)保存到了下一輪但所有其他用戶都決定在第5輪時(shí)沖刺，這導(dǎo)致電力緊急情況，使你無法在后續(xù)幾輪中沖刺。更糟的是，到那時(shí)你的收益就不會那么高了。
短跑游戲中的“平均場博弈分析”
玩家們使用一個(gè)數(shù)據(jù)中心來共享信息。如果其中一個(gè)玩家選擇在第5輪沖刺，他們將獲得一定的收益，但他們必須要等處理器冷卻一段時(shí)間才能再次加速。如果他們等到第6輪或者之后再沖刺，他們會獲得更多收益。
如果太多的玩家同時(shí)沖刺，電流大幅度增加會導(dǎo)致斷電。在計(jì)算機(jī)集群的不間斷電源電池充電之前，任何人都不能再沖刺，即使是沒有沖刺的玩家4也不行。
所有用戶都必須權(quán)衡他們獲得的效用的多少和其他用戶的沖刺策略，之后再做出相應(yīng)的決定。雖然少數(shù)用戶競爭的例子可能很有趣，但隨著競爭對手的數(shù)量增長到數(shù)據(jù)中心的規(guī)模，做出這些決定就變得非常棘手。
幸運(yùn)的是，我們找到了這種叫做“平均場博弈分析”的方法，可以在在大型系統(tǒng)中優(yōu)化每個(gè)用戶的策略。這種方法將所有用戶策略考慮為一個(gè)整體，避免了考慮每個(gè)競爭對手策略的復(fù)雜性。這種統(tǒng)計(jì)方法的關(guān)鍵在于假設(shè)任何單個(gè)用戶行為都不會顯著地改變系統(tǒng)的平均行為。正是由于這一假設(shè)，我們可以用單個(gè)平均效應(yīng)來近似所有其他用戶對任何給定用戶的影響。
這有點(diǎn)類似于數(shù)百萬上班族試圖優(yōu)化他們的日常出行。我們以文摘菌這樣一個(gè)上班族為例。雖然不能用她以一概全。但是，文摘菌的行為模式可以推斷出上班族這一總體在特定一天中希望到達(dá)的時(shí)間，以及他們的出行計(jì)劃會如何加劇道路擁堵等。
平均場分析允許我們找到?jīng)_刺游戲的“平均場平衡”。用戶會優(yōu)化他們對群體的響應(yīng)。這也意味著，在平衡狀態(tài)下，偏離他們對整體的最佳響應(yīng)將沒有任何好處。
在交通情況中，文摘菌會根據(jù)對通勤人群平均行為的理解來優(yōu)化通勤。如果優(yōu)化后的計(jì)劃沒有產(chǎn)生預(yù)期的交通模式，她就會修正自己的預(yù)期并重新考慮自己的計(jì)劃。隨著每一個(gè)通勤者在幾天內(nèi)的一次優(yōu)化，交通收斂到一些重復(fù)的模式，通勤者的獨(dú)立行動產(chǎn)生一個(gè)平衡。
通過平均場平衡，我們制定了沖刺游戲的最優(yōu)策略：當(dāng)性能收益超過某個(gè)閾值時(shí)，用戶應(yīng)該沖刺。
該閾值根據(jù)用戶的不同而不同。我們可以使用數(shù)據(jù)中心的工作負(fù)載及其物理特性來計(jì)算這個(gè)閾值。
當(dāng)每個(gè)人都在平均場平衡下以他們的最優(yōu)閾值運(yùn)行時(shí)，系統(tǒng)將會受益良多。首先，數(shù)據(jù)中心的電源管理可以是分布式的，因?yàn)橛脩艨梢詫?shí)現(xiàn)他們自己的策略，而不需要向中心管理員請求加速許可。這種獨(dú)立性使得功率控制更加靈敏、節(jié)能。用戶可以在微秒或更少的時(shí)間內(nèi)調(diào)節(jié)處理器的功耗。而如果他們必須等待幾十毫秒來獲得許可，才能通過數(shù)據(jù)中心，那么這種效果將難以實(shí)現(xiàn)。其次，用戶可以根據(jù)自己的工作負(fù)載需求來及時(shí)優(yōu)化加速策略，使得均衡條件下可以完成更多計(jì)算工作。最后，當(dāng)增益超過閾值時(shí)，用戶的策略就變成了簡單的沖刺。這是非常容易執(zhí)行的。
貪得無厭必自斃：在沖刺游戲中，與“貪心”策略相比，使用平均場均衡策略可以用更少的力完成更多的功。
博弈論必將發(fā)揮巨大作用
“沖刺管理項(xiàng)目”只是我們在過去五年中開發(fā)的一系列數(shù)據(jù)中心管理系統(tǒng)中的一個(gè)。在每一款游戲中，我們都使用了硬件架構(gòu)和系統(tǒng)的關(guān)鍵細(xì)節(jié)來設(shè)計(jì)游戲。而這樣利用這一管理機(jī)制使得，當(dāng)參與者行為表現(xiàn)得過于自私利己時(shí)，系統(tǒng)依舊可以穩(wěn)定運(yùn)行。我們有理由相信，這樣的保證只會鼓勵(lì)共享系統(tǒng)的參與，并為節(jié)能和可擴(kuò)展的數(shù)據(jù)中心奠定堅(jiān)實(shí)的基礎(chǔ)。
盡管我們已經(jīng)設(shè)法在服務(wù)器多處理器、服務(wù)器機(jī)柜和服務(wù)器集群級別解決了資源分配問題，但是將它們用于大型數(shù)據(jù)中心仍需要很多工作。一方面，你必須能夠生成數(shù)據(jù)中心的性能概要。因此，數(shù)據(jù)中心必須部署必要的基礎(chǔ)設(shè)施來監(jiān)視硬件活動、評估性能結(jié)果和推斷對資源的偏好。
這類系統(tǒng)的大多數(shù)博弈論解決方案都要求分析階段離線進(jìn)行。相反，構(gòu)建可以從一些先驗(yàn)知識開始，然后在執(zhí)行過程中隨著特征變得更清晰，而更新其參數(shù)的在線機(jī)制可能干擾更小。在線機(jī)制甚至可能通過強(qiáng)化學(xué)習(xí)或另一種形式的人工智能來改進(jìn)游戲。
還有一個(gè)現(xiàn)實(shí)問題就是：在數(shù)據(jù)中心，用戶可以隨時(shí)進(jìn)出系統(tǒng)，任務(wù)可以在計(jì)算過程中隨意穿插，服務(wù)器可能會失敗并重新啟動。所有這些事件都需要重新分配資源，但是這些重新分配可能會破壞整個(gè)系統(tǒng)的計(jì)算，并要求對數(shù)據(jù)進(jìn)行分流，從而耗盡資源。
在保持每個(gè)人公平競爭的同時(shí)，應(yīng)付所有這些變化肯定需要更多的工作，但我們堅(jiān)信博弈論必將發(fā)揮巨大作用。
京公網(wǎng)安備 11010502049343號