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