经典论文 | Google使用Borg进行大规模集群的管理(第三章、第四章)


【编者的话】这两章介绍了Borg的架构和可用性,从前面的用户视角跳到了系统设计者的视角。

3. Borg架构

一个Borg的Cell包括一堆机器,一个逻辑的中心控制服务叫做Borgmaster,和在每台机器上跑的Borglet的agent进程(见图1)。所有Borg的组件都是用C++写的。
5ffc769b277374efb48c89a1b55acd5a.jpg

3.1 Borgmaster

Cell的Borgmaster由2个进程组成,主的Borgmaster进程和一个单独的scheduler($3.2)。主的Borgmaster处理所有客户端的RPC请求,例如修改状态(创建job),提供数据读取服务(查找job)。它同时管理系统中所有组件(机器、task、allocs等等)的状态机,和Borglet通信,并且提供一个Sigma的备份Web UI。

Borgmaster在逻辑上是一个单进程,但实际上开了5个副本。每个副本维护了一个内存级别的cell状态拷贝,这些状态同时被记录在一个高可用、分布式、Paxos-based存储[55]放在这些副本的本地硬盘上。在一个cell里面,一个单独的被选举出来的master同时用于Paxos leader和状态修改器,用来处理所有改变cell状态的请求,例如提交一个job或者在一个机器上终止一个task。当cell启动或前一个master挂了时,Paxos算法会选举出一个master;这需要一个Chubby锁然后其他系统可以找到master。选举一个master或者换一个新的需要的典型事件是10s,但需要大概1分钟才能让一个大的cell内生效,因为一些内存状态要重构。当一个副本从网络隔离中恢复时,需要动态的从其他Paxos副本中重新同步自己的状态。

某个时刻的Borgmaster的状态被称为checkpoint,会被以快照形式+change log形式保存在Paxos存储里面。checkpoints有很多用途,包括把Borgmaster的状态恢复到以前的任意时刻(例如在处理一个请求之前,用来解决软件缺陷);极端情况下手动修改checkpoints,形成一个持续的事件日志供今后用;或用于线下的在线仿真。

一个高仿真的Borgmaster叫Fauxmaster,可以用来读取checkpoint文件,包括一份完整的Borgmaster的代码,和Borglet的存根接口。它接受RPC来改变状态机和执行操作,例如调度所有阻塞的tasks,我们用它来debug错误,和它交互就和Borgmaster交互是一样的,同样我们也有一个仿真的Borglet可以用checkpoint重放真实的交互。用户可以单步调试看到系统中的所有过去的改变。Fauxmaster在这种情况下也很有用:多个这个类型的job比较合适?以及在改变cell配置前做一个安全检查(这个操作会把任何关键jobs给踢掉吗?)

3.2 调度 schedule

当一个job被提交的时候,Borgmaster会把它持久化的存储在Paxos存储上,然后把这个job的task放到等待(pending)的队列里面去。这个队列会被scheduler异步的扫描,然后分发task到有充足资源的机器上。scheduler主要是处理task的,不是job。扫描从高优先级到低优先级,在同个优先级上用round-robin的方式处理,以保证用户之间的公平性和避免头上的大job阻塞住。调度算法有2个部分:可行性检查(feasibility checking),找到一台能跑task的机器,和打分(scoring),找个一个最合适的机器。

在可行性检查这个阶段,scheduler会找到一组机器,都满足task的约束而且有足够可用的资源 —— 包括了一些已经分配给低优先级任务的可以被腾出来的资源。在打分阶段,scheduler会找到其中“最好”的机器。这个分数包括了用户的偏好,但主要是被内置的标准:例如最小化的倒腾其他task,找到已经有这个task安装包的,在电力和出错的可用域之间尽可能分散的,在单台机器上混合高低优先级的task以保证高峰期扩容的。

Borg原来用E-PVM[4]的变种算法来打分,在异构的资源上生成一个单一的分数,在调度一个task时最小化系统的改变。但在实践中,E-PVM最后把负载平均分配到所有机器,把扩展空间留给高峰期 —— 但这么做的代价是增加了碎片,尤其是对于大的task需要大部分机器的时候;我们有时候给这种分配取绰号叫“最差匹配”。

分配策略光谱的另一端是“最佳匹配”,把机器塞任务塞的越紧越好。这样就能留下一些空的机器给用户jobs(他们也跑存储服务),所以处理大task就比较直接了,不过,紧分配会惩罚那些对自己所需资源预估不足的用户。这种策略会伤害爆发负载的应用,而且对需要低CPU的批处理任务特别不友好,这些任务可以被轻易调度到不用的资源上:20%的non-prod task需要小于0.1核的CPU。

我们目前的打分模型是一个混合的,试图减少搁浅的资源 —— 一些因为这台机器上资源没被全部用掉而剩下的。比起“最佳匹配”,这个模型提供了3%-5%的打包效率提升(在[78]里面定义的)。

如果一台机器在打分后没有足够的资源运行新的task,Borg会驱逐(preempts)低优先级的任务,从最低优先级往上踢,直到资源够用。我们把被踢掉的task放到scheduler的等待(pending)队列里面去,而不是迁移或冬眠这些task。

task启动延迟(从job提交到task运行之间的时间段)是被我们持续关注的。这个时间差别很大,一般来说是25s。包安装耗费了这里面80%的时间:一个已知的瓶颈就是对本地硬盘的争抢。为了减少task启动时间,scheduler希望机器上已经有足够的包(程序和数据):大部分包是只读的所以可以被分享和缓存。这是唯一一种Borg scheduler支持的数据本地化方式。顺便说一下,Borg分发包到机器的办法是树形的和BT类型的协议。

另外,scheduler用了某些技术来扩散到几万台机器的cell里面。($3.4)

3.3 Borglet

Borglet是部署在cell的每台机器上的本地Borg代理程序。它启动停止task;如果task失败就重启;通过修改OS内核设置来管理本地资源;滚动debug日志;把本机的状态上报给Borgmaster和其他监控系统。

Borgmaster每过几秒就会轮询所有的Borglet来获取机器当前的状态还有发送任何请求。这让Borgmaster能控制交流频率,避免一个显式的流控机制,而且防止了恢复风暴[9].

选举出来的master负责发送消息给Borglet并且根据响应更新cell的状态。为了性能可扩展,每个Borgmaster副本会运行一个无状态的连接分配(link shard)来处理和特定几个Borglet的交流;这个分配会在Borgmaster选举的时候重新计算。为了保证弹性,Borglet把所有状态都报上来,但是link shard会聚合和压缩这些信息到状态机,来减少选举出来的master的负载。

如果Borglet几次没有响应轮询请求,将会被标记为挂了(down),然后上面跑的task会被重新分配到其他机器。如果通讯恢复,Borgmaster会让这个Borglet杀掉已经被分配出去的task,来避免重复。Borglet会继续常规的操作即使和Borgmaster恢复联系,所以目前跑的task和service保持运行以防所有的Borgmaster挂了。

3.4 可扩展性

我们还不知道Borg的可扩展性极限在哪里,每次我们碰到一个极限,我们就越过去。一个单独的Borgmaster可以管理一个cell里面几千台机器,若干个cell可以处理10000个任务每分钟。一个繁忙的Borgmaster使用10-14个CPU核以及50GB内存。我们用了几项技术来获得这种扩展性。

早期的Borgmaster有一个简单的,同步的循环来处理请求、调度tasks,和Borglet通信。为了处理大的cell,我们把scheduler分出来作为一个单独的进程,然后就可以和别的Borgmaster功能并行的跑,别的Borgmaster可以开副本来容错。一个scheduler副本操作一份cell的状态拷贝。它重复地:从选举出来的master获取状态改变(包括所有的分配的和pending的工作);更新自己的本地拷贝,做调度工作来分配task;告诉选举出来的master这些分配。master会接受这些信息然后应用之,除非这些信息不适合(例如,过时了),这些会在scheduler的下一个循环里面处理。这一切都符合Omega[69]的乐观并行策略精神,而且我们最近真的给Borg添加这种功能,对不同的工作负载用不同的scheduler来调度。

为了改进响应时间,我们增加了一些独立线程和Borglet通信、响应只读RPC。为了更高的性能,我们分享(分区)这些请求给5个Borgmaster副本$3.3。最后,这让99%的UI响应在1s以内,而95%的Borglet轮询在10s以内。

一些让Borg scheduler更加可扩展的东西:

分数缓存:评估一台机器的可用性和分数是比较昂贵的,所以Borg会一直缓存分数直到这个机器或者task变化了——例如,这台机器上的task结束了,一些属性修改了,或者task的需求改变了。忽略小的资源变化让缓存保质期变长。

同级别均化处理:同一个Borg job的task一般来说有相同的需求和资源,所以不用一个个等待的task每次都去找可用机器,这会把所有可用的机器打n次分。Borg会对相同级别的task找一遍可用机器打一次分。

适度随机:把一个大的Cell里面的所有机器都去衡量一遍可用性和打分是比较浪费的。所以scheduler会随机的检查机器,找到足够多的可用机器去打分,然后挑出最好的一个。这会减少task进入和离开系统时的打分次数和缓存失效。适度随机有点像Sparrow [65]的批处理采样技术,同样要面对优先级、驱逐、非同构系统和包安装的耗费。

在我们的实验中($5),调度整个cell的工作负载要花几百秒,但不用上面几项技术的话会花3天以上的时间。一般来说,一个在线的调度从等待队列里面花半秒就能搞定。

4. 可用性

图3.jpg

在大型分布式系统里面故障是很常见的[10,11,12]。图3展示了在15个cell里面task驱逐的原因。在Borg上跑的应用需要能处理这种事件,应用要支持开副本、存储数据到分布式存储这些技术,并能定期的做快照。即使这样,我们也尽可能的缓和这些事件造成的影响。例如,Borg:
  • 自动的重新调度被驱逐的task,如果需要放到新机器上运行
  • 通过把一个job分散到不同的可用域里面去,例如机器、机架、供电域
  • 在机器、OS升级这些维护性工作时,降低在同一时刻的一个job中的task的关闭率
  • 使用声明式的目标状态表示和幂等的状态改变做操作,这样故障的客户端可以无损的重新启动或安全的遗忘请求
  • 对于失联的机器上的task,限制一定的比率去重新调度,因为很难去区分大规模的机器故障和网络分区
  • 避免特定的会造成崩溃的task:机器的匹配
  • critical级别的中间数据写到本地硬盘的日志保存task很重要,就算这个task所属的alloc被终止或调度到其他机器上,也要恢复出来做。用户可以设置系统保持重复尝试多久:若干天是比较合理的做法。


一个关键的Borg设计特性是:就算Borgmaster或者Borglet挂了,task也会继续运行下去。不过,保持master运行也很重要,因为在它挂的时候新的jobs不能提交,或者结束的无法更新状态,故障的机器上的task也不能重新调度。

Borgmaster使用组合的技术在实践中保证99.99%的可用性:副本技术应对机器故障;管理控制应对超载;部署实例时用简单、底层的工具去减少外部依赖(译者:我猜测是rsync或者scp这种工具)。每个cell和其他cell都是独立的,这样减少了误操作关联和故障传染。为了达到这个目的,所以我们不搞大cell。

原文链接:Large-scale cluster management at Google with Borg(翻译:难易

1 个评论

用BT协议来分发task真的是个非常cool的设计!

要回复文章请先登录注册