大规模分布式系统资源管理(一)

2019-09-10 15:59:16 采集侠

如今大火的机器学习和人工智能等技术如何应用在资源管理方面?我们请到了南开大学的王刚和李雨森教授前来360,分享他们以及所在课题组在大规模分布式系统资源管理方面的研究工作,内容包括云游戏系统中的请求调度、资源分配,以及搜索引擎数据中心的负载均衡、配额管理等。

主要内容

(1)云游戏中的资源管理

(2)搜索引擎中的资源管理

(3)AI 在资源管理中的应用

1.云游戏中的资源管理 云游戏

云游戏

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

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

Gaming anywhere, anytime, on any device

挑战

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

延迟

双倍网络延迟 (Client – Server – Client) 有的游戏玩家对游戏的反映时间和灵敏度有很高的要求,使用时要把指令发送过去,再把指令传回来,同时还有视频压缩,这是一个很耗时的过程。带宽最低要求: 3~5 Mbps

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

成本

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

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

研究目标

优化成本

所有 server 的总运行时间最短

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

请求调度

 server

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

Example

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,请求到达后需马上做出决定

请求结束时间未知

运行中的游戏不能移动

相似问题 有一个和上面所讲的云游戏的请求调度问题非常相似的问题,叫动态装箱问题。 普通装箱问题:我有一些请求,那么我希望用最少的箱子即最少的服务器,来装下这些请求。动态装箱问题:请求是有来的时间和结束的时间的。目标是,要有一个策略,使得整个过程中所用的顺时的服务器的最大的数量最小。

大规模分布式系统资源管理(一)

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

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

研究工作

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

一、经典算法

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

 二、新算法

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

 三、问题延伸

考虑游戏部署开销

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

(1)经典算法

Any Fit

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

First Fit

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

Best Fit

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

 server

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

Worst Case Ratio 分析

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