大规模分布式系统资源管理（一）

女主宣言

主要内容

概念 ：Server 端运行游戏，并将压缩的视频传给 Client；Client 只负责解压、显示视频

优点 : 将 load 从客户端转移到 Cloud端。显然用户就不用安装游戏，也不用很好的设备，普通的电脑就可以运行大型的游戏，从而实现

Gaming anywhere, anytime, on any device

完成高质量的游戏。比如，有的游戏玩家对游戏的反映时间和灵敏度有很高的要求，这一方面其实是很大的挑战。

延迟

双倍网络延迟 (Client - Server - Client)

有的游戏玩家对游戏的反映时间和灵敏度有很高的要求，使用时要把指令发送过去，再把指令传回来，同时还有视频压缩，这是一个很耗时的过程。

带宽

最低要求： 3~5 Mbps

传数值并不是一个小事情，如果传高质量的视频，最低要求是3-5Mbps的带宽。

成本

每台 server 同时只能运行几个游戏。

如果用户比较多的话，那么运营商就要提供很多的服务器。服务器的成本很高，包括它的运营成本维护成本等。云游戏收用户的钱可能还抵不过服务器的钱或者网络的钱。所以成本一直是云游戏里一个很大的挑战。

优化成本

所有 server 的总运行时间最短

一般来说是用越少的服务器越好，也可以理解为，我们使用服务器的总运行时间最短。服务器的数量可能有的时候不太合理，如果这个机房有一万台服务器，它们可能不需要同时运行.如果这台服务器是空闲的，我们可以把它关掉或者是转化到一种低能耗的模式。所以我们的优化目标并不是单单的使所用的服务器数量最少，而是在满足用户条件的情况下使得所有服务器的运行时间最短。

请求调度

这里有一个假设，假设所有的服务器都是重构的，如果其他条件都没有变化的情况下，运行时间基本上是由请求调度算法来决定的。

Example

假如现在有三个请求，r1，r2，r3。它们是同时到来的，横轴表示时间，假设在0时刻三个请求都到了，r1和r3的结束时间是10分钟，可以理解为玩游戏的时间停留在系统里的时间是10分钟。r2很快就离开了，它的停留时间是1分钟，假如每台服务器只能服务两个请求，那么希望有2种策略。

左边是一种，把r1和r2放在一台服务器上，r3另开一台服务器，那么如果要完成3个请求的话这2台服务器都要运行10分钟。总时间就是20分钟。

右边的策略是，把r1和r3放在一起，r2单独放在一台服务器上，那么r1和r3需要运行10分钟，而r2在1分钟之后就可以把它调为低能耗的模式或者关掉它。

所以这个例子可以说明，采用不同的调度策略，服务器总的运行时间，某种程度上可以理解为总的成本，是有很大差别的。

目标

如何调度游戏请求，使得总的 server 运行时间最少。

挑战

Online，请求到达后需马上做出决定

请求结束时间未知

运行中的游戏不能移动

有一个和上面所讲的云游戏的请求调度问题非常相似的问题，叫动态装箱问题。

普通装箱问题 ：我有一些请求，那么我希望用最少的箱子即最少的服务器，来装下这些请求。

动态装箱问题 ：请求是有来的时间和结束的时间的。目标是，要有一个策略，使得整个过程中所用的顺时的服务器的最大的数量最小。

区别 ：我们的问题是使所有服务器开着的时间总和最小。

比如，图上每个绿色的条代表一个服务器开着的时间段的话，我们的目标是使所有这些加起来最小。

可以说它是动态装箱问题的一个变形。我们就要研究经典的装箱问题的算法在这个问题上的表现如何。我们的研究工作主要集中在三个方面。

经典调度算法在云游戏请求调度上的表现

预测请求结束时间，优化请求调度算法

考虑游戏部署开销

下面简要介绍一下这三个部分

一、经典算法

Any Fit

只有当前正在运行的 server 都满负载时，才开一台新的。

First Fit

在所有有空闲的 server 中，选择最早开始运行的那台 server。

Best Fit

在所有有空闲的 server 中，选择空闲最少的那台 server。 目标是尽量使满的sever更满。

经典算法主要研究两个部分。

Worst Case Ratio 分析

主要研究最坏情况下这几种算法是最优解的多少倍。

对于1.3版本之前的Elasticsearch，fielddata cache大小是没有限制的。 从1.3版本开始，Elasticsearch添加了一个fielddata断路器，如果查询试图加载需要占用60％以上堆栈内存的fielddata，则会触发该断路器。

结论：通常情况下， Best Fit和First Fit的平均性能是差不多的。在最坏情况下，First Fit是有上界的，即First Fit在最坏情况下它不是很坏，但Best Fit在最坏情况下可以无限坏，没有上界。

Stochastic 分析

调度算法统计学上的平均性能。这里涉及到一些马尔可夫理论还有其他一些随机过程的理论。

二、新算法

游戏请求的 Daily Pattern

从早上七八点开始到12点左右请求一直是增加的。12点过后请求开始下降。

黄色的线是一个最优解，代表需要的使用服务器数量的下界。还有一条红色的线和灰色的线，它们俩是重合的，代表Best Fit和First Fit算法，说明它俩的表现是一样的，在下坡阶段即图中的0点-7点，比最优解还相差较多。可以得出结论：First Fit和Best Fit 在“下坡阶段”浪费大量服务器。

原因其实很简单。在上坡阶段，因为请求是不断地来的，不断开新的服务器，那么请求数量不断增加，每台服务器利用率就很高。在高峰比如11点，开了很多服务器，12点开始这些游戏请求就走了，进入了下坡阶段。这时每台服务器都都不是很满，这样浪费的服务器就比较多。如果游戏请求可以来回不断地发，那么这个问题就很好解决了。主要的问题是不满的这些服务器，这些请求是不能汇总到一台服务器上的。

请求结束时间预测

核心：游戏玩家的游戏时间是否可预测的。

如果是可预测的，请求到来时就能知道它大概什么时候走。如果不可预测那么整个算法就不可行。

我们对一些游戏进行了试验。其中后两个DotAlicious和WOT是组队式的。每一场游戏里面都有两队，每队里有几个队员。前面WoWAH是个人游戏。图纵坐标表示的是预测的错误率。