活捉那只抢算力的谷歌员工！挤占计算资源？博弈论或可破解数据中心“囚徒困境”

原标题：活捉那只抢算力的谷歌员工！挤占计算资源？博弈论或可破解数据中心“囚徒困境” 来源：IEEE

大数据文摘出品来源：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也不行。

所有用户都必须权衡他们获得的效用的多少和其他用户的冲刺策略，之后再做出相应的决定。虽然少数用户竞争的例子可能很有趣，但随着竞争对手的数量增长到数据中心的规模，做出这些决定就变得非常棘手。

幸运的是，我们找到了这种叫做“平均场博弈分析”的方法，可以在在大型系统中优化每个用户的策略。这种方法将所有用户策略考虑为一个整体，避免了考虑每个竞争对手策略的复杂性。这种统计方法的关键在于假设任何单个用户行为都不会显著地改变系统的平均行为。正是由于这一假设，我们可以用单个平均效应来近似所有其他用户对任何给定用户的影响。

这有点类似于数百万上班族试图优化他们的日常出行。我们以文摘菌这样一个上班族为例。虽然不能用她以一概全。但是，文摘菌的行为模式可以推断出上班族这一总体在特定一天中希望到达的时间，以及他们的出行计划会如何加剧道路拥堵等。

平均场分析允许我们找到冲刺游戏的“平均场平衡”。用户会优化他们对群体的响应。这也意味着，在平衡状态下，偏离他们对整体的最佳响应将没有任何好处。

在交通情况中，文摘菌会根据对通勤人群平均行为的理解来优化通勤。如果优化后的计划没有产生预期的交通模式，她就会修正自己的预期并重新考虑自己的计划。随着每一个通勤者在几天内的一次优化，交通收敛到一些重复的模式，通勤者的独立行动产生一个平衡。

通过平均场平衡，我们制定了冲刺游戏的最优策略：当性能收益超过某个阈值时，用户应该冲刺。

该阈值根据用户的不同而不同。我们可以使用数据中心的工作负载及其物理特性来计算这个阈值。

当每个人都在平均场平衡下以他们的最优阈值运行时，系统将会受益良多。首先，数据中心的电源管理可以是分布式的，因为用户可以实现他们自己的策略，而不需要向中心管理员请求加速许可。这种独立性使得功率控制更加灵敏、节能。用户可以在微秒或更少的时间内调节处理器的功耗。而如果他们必须等待几十毫秒来获得许可，才能通过数据中心，那么这种效果将难以实现。其次，用户可以根据自己的工作负载需求来及时优化加速策略，使得均衡条件下可以完成更多计算工作。最后，当增益超过阈值时，用户的策略就变成了简单的冲刺。这是非常容易执行的。

贪得无厌必自毙：在冲刺游戏中，与“贪心”策略相比，使用平均场均衡策略可以用更少的力完成更多的功。

博弈论必将发挥巨大作用

“冲刺管理项目”只是我们在过去五年中开发的一系列数据中心管理系统中的一个。在每一款游戏中，我们都使用了硬件架构和系统的关键细节来设计游戏。而这样利用这一管理机制使得，当参与者行为表现得过于自私利己时，系统依旧可以稳定运行。我们有理由相信，这样的保证只会鼓励共享系统的参与，并为节能和可扩展的数据中心奠定坚实的基础。

尽管我们已经设法在服务器多处理器、服务器机柜和服务器集群级别解决了资源分配问题，但是将它们用于大型数据中心仍需要很多工作。一方面，你必须能够生成数据中心的性能概要。因此，数据中心必须部署必要的基础设施来监视硬件活动、评估性能结果和推断对资源的偏好。

这类系统的大多数博弈论解决方案都要求分析阶段离线进行。相反，构建可以从一些先验知识开始，然后在执行过程中随着特征变得更清晰，而更新其参数的在线机制可能干扰更小。在线机制甚至可能通过强化学习或另一种形式的人工智能来改进游戏。

还有一个现实问题就是：在数据中心，用户可以随时进出系统，任务可以在计算过程中随意穿插，服务器可能会失败并重新启动。所有这些事件都需要重新分配资源，但是这些重新分配可能会破坏整个系统的计算，并要求对数据进行分流，从而耗尽资源。

在保持每个人公平竞争的同时，应付所有这些变化肯定需要更多的工作，但我们坚信博弈论必将发挥巨大作用。