文章目錄

1. 1. Borg论文翻译及理解
   1. 1.1. 引言
   2. 1.2. 一些不错的infoq资料
   3. 1.3. 其他需要理解的几个东西
   4. 1.4. Abstract
   5. 1.5. Introduction
   6. 1.6. 用户眼中的Borg
      1. 1.6.1. Work Load
      2. 1.6.2. Clusters and Cells
      3. 1.6.3. 作业概述
         1. 1.6.3.1. 作业的Alloc
         2. 1.6.3.2. 作业的Priority, quota, and admission control
         3. 1.6.3.3. Naming and monitoring
   7. 1.7. Borg Arc
      1. 1.7.1. Borg Master
      2. 1.7.2. Scheduling
      3. 1.7.3. BorgLet
      4. 1.7.4. Scalability
         1. 1.7.4.1. 调度实现问题
         2. 1.7.4.2. 响应时间问题
         3. 1.7.4.3. 调度优化
   8. 1.8. 可靠性

Borg论文翻译及理解

引言

随着docker使用的日渐普遍，资源调度从新成为一个火热的方向。不过这一次从之前的调度算法的研究晋升到实现。

所以G也赶紧把珍藏多年的大杀器Borg拿出来显摆一下。

一些不错的infoq资料

http://www.infoq.com/cn/news/2015/05/Kubernetes-Borg-Eurosys

http://www.infoq.com/cn/articles/docker-container-cluster-management-part-01

http://www.infoq.com/cn/articles/docker-container-cluster-management-part-02

其他需要理解的几个东西

Sparrow[65] Sparrow: distributed, low latency scheduling.

Omega[69] Omega: flexible, scalable schedulers for large compute clusters

Abstract

Google的borg使用大量机器支持着数千个应用的10W个作业，其中部分单个集群规模超过万台机器。

其通过

1. Adminition control
2. Task-packing
3. Over-commitment
4. Machine sharing with process level isolation

提供

• Declarative job specification lauguage
• Naming service integration
• Real time job monitoring
• Tools to analyze and simulate system behavior

Introduction

Borg 主要得益于三点：

1. 他隐藏了Resource Management以及Failure Handling的细节，所以保证他的用户可以focus在应用开发本身。
2. 其本身就具有高可用性以及高可靠性，与此同时，也保证运行其上的应用具有同样的特性。
3. 很好的保证我们可以在数万台机器上运行应用。

Borg当然不是第一个提出这些问题的软件，但是的确是第一个在如此规模运行的软件。

用户眼中的Borg

在Google开发工程师眼中，他们将作业提交到Borg，Borg将他们的作业运行在Borg Cell中。每个Borg Cell可能有多达上万台机器构成。本节主要介绍在开发者眼中的borg。

Work Load

Borg支持异质的workload，其主要包括两种：

• 一种是never goes down Service 如 Gmail/Google Doc，这些服务是latency-sensitive的（ms level）
• 另外一种是Batch Job 如Mapreduce作业。这些任务可能运行几天后完成，这些相比之前的服务对延时并没有那么敏感。

在此文当中，我们将高priority任务称之为Prod（production），其他的则称为non-prod。大部分第一种任务是prod任务，而batch任务大部分则为none-prod任务。

在一个典型的Cell中，prod类型任务占有70%的CPU资源，并利用了其中的60%，同时占用了55%的内存，并使用了其中的85%。

Clusters and Cells

一个Cluster往往用于描述处在同一个机房中的一部分机器，一个Cluster往往具有个Cell，部分Cluster还具有Test Cell以及其他具有其他功能的Cell。

一般一个中等规模的Cell具有1w个左右的机器，而且其中的机器并非同构架机器，可能different in cpu mem dist network。但Borg屏蔽了这些特异性，对于developer而言，一切都是一样的，包括故障处理，监控以及依赖等等。

作业概述

每个Job在一个Cell中进行执行，与此同时，可以为每个job分配名字，以及该job希望其所属的task执行的环境（包括CPU类型，IP，System arc等等）。

每个job在执行过程会会映射到多个机器的多个进程上。值得注意的是，大部分作业并没有映射到一个虚拟机上，因为我们不希望因为虚拟机的原因付出更多的资源，另一个原因是Borg产生在一个虚拟化还不那么流行的年代-。-！

对于每个task而言，每个task同样可以指定希望执行的环境，当然，其中但部分内容还是继承自job，但允许被overriden。在每个机器上，我们并不使用类似slot的方式约定每个机器上可执行的task数量。Borg程序在运行环境被静态链接了以减少执行依赖，且这些borg程序会以package或者binary file的形式由Borg系统进行传递。

对于每个borg程序，Borg具有监控工具以及commandline供需以支持用户对自己的job进行操作以及监控。大部分作业描述是以BCL的方式进行描述的，该方式类似GCL，同时BCL也支持lambda函数。图2展示了job的生命周期

对于一个运行中的Job而言，用户可以通过向Borg推送一个新的配置文件来对Job的（配置、属性、甚至执行文件）进行更改，而后命令Borg针对新的配置文件update。这种update是一种轻量级的非原子性的操作，因此在完成之前很容易被撤销。其中一些更新可能需要task重启，而一些更新使得job不再适配原来所在的机器，因此这些job会被停止并reschedule，而其他一些任务则可以直接继续执行。

这些task会首先通过Unix的 SIGTERM进行通知，而后进行SIGKILL。所以他们有时间进行 clean up，save status，完成请求响应以及拒绝新的请求。

作业的Alloc

对Borg而言，Borg Alloc是机器上被预留出的一批资源，从而保证真正的task可以运行在其中。因此alloc可以用于预留出一部分资源给未来的task，或者在task重启的过程中为其一直保持资源，还或者把运行在不同机器上的task移动到一起。

对于Alloc中的资源的使用，如同一台机器一样，如果有多个任务在一个alloc中，则他们会共享其中的资源。

因此Alloc set更像是一个job，一大堆alloc在不同的机器上都预留了资源。当alloc set被建立之后，一个或者多个任务就可以在alloc set中进行执行。

为了简洁起见，我们用task来表示单个的alloc或者alloc其中运行的任务，而使用job来表示一个alloc set 或者大型的运行其中的任务。

所以说Alloc事实上是在task之上一层对资源隔离的实现。

作业的Priority, quota, and admission control

我们通过Quota以及Priority综合对作业进行控制。

• Priority用于描述作业重要程度，用于在同一个Cell中作业之间竞争资源时进行判定。

对每个任务而言，我们都使用一个整数来表示其优先级。相比较而言，高等级的任务更容易获得资源，甚至不惜以杀掉低等级的任务为代价。在Borg中，我们使用非重叠的优先级策略（从高到低）：Monitoring，Production，batch，以及best effort（即test 或者free）。在本文中我们所指的prod类型程序即为monitoring或者production级别。

同时，严格的等级问题以及允许kill可能会带来优势震荡（preemption cascades），即：在一个机器上，Monitoring级的task为了资源，试图kill一个prodcution级的任务，而后者为了资源继续kill一个batch类型task，从而导致对资源的大量浪费。

为了处理此类问题，我们禁止了production level 及之上级别的任务的kill掉同级任务的情况。同样，很好的权限设置也可以用于其他地方，比如MR在每个机器上的任务分配进程的优先级就会比MR worker稍微高一点。

• Quota(配额)则主要是对作业提交者的一种限定。

在使用priority时就存在这样一个问题，如果高priority的job可以kill低priority的job，会不会所有user都申请尽可能高priority的job呢？

所以必须对作业提交者进行限制，以保证作业之间具有不同的优先级。其基本策略就是每个用户都在不同的优先级下具有不同的配额。

配额的概念更像是硬性要求（Admission Control）而非调度算法。Quota的表示形式是使用一个Vector的资源限定（CPU，内存硬盘），例如“20TiB of RAM at prod priority from now until the end of July in cell xx”。无法满足该需求的job会在提交的时候就被拒绝。

高权限的quota cost more than 低权限quota。而且会对高权限的quota资源有限（例如production权限的计算资源只占整个Cell的20%，而更低权限的计算资源Quota可能更多）。我们鼓励用户在申请资源的时候仅仅足够运行的资源，而非申请额外富裕的资源。但还是会有很多用户overbuy资源，因为这样可以杜绝在未来因为用户的增长而增长的资源使用。

对于最低权限的作业，其具有无限的quota。然并卵，很多时候底level的作业可能虽然通过了quota审核，但是却因为没有实际资源而无法被调度上cell。

对于Quota如何分配的问题，是在Borg之外进行的。而且这与机器，以及我们对机器的预期密切相关。更多请去看参考文献[29, 35, 36, 66]

Naming and monitoring

Borg name Service（BNS）用于查看提交之后作业状态，在提交一个job的时候，BNS把job的每个task具体信息写入Chubby，因此在查找job每个task状态时可轻易找到。例如，在chubby路径里大概是这么个样子。

jobid：jfoo
user：ubar
taskid：50
Cell： cc

Final ID：50.jfoo.ubar.cc.borg.google.com

Borg同样把job size以及task health 写入 chubby，所以load balancer可以很轻松的从chubby里获取状态，进行操作。

与此同时，每个在Borg中运行的的task都具有一个内建的http server，用于向外推送信息。Borg monitor 可以方便的通过http server对task的监控以及被动参数进行获取。

其他的还有很多很人性化的地方，比如有个UI可以再Cell，task或者深入到job去查看运行状态，看日志。而且当job结束时，日志并不会立刻随着job的结束删除，而是会保留一段时间。

与此同时，所有的Job提交信息以及运行事件以及占用的资源信息等，全部存储在Dremel中。用于charging，debugging failure以及long-term capacity planning。

Borg Arc

Borg里有Borg Master 管理很多borg cell。C++ written。

Borg Master

BorgMaster系统启动两个进程。进程2负责进行调度。进程1负责：

• 处理RPC call in order to handle 状态变化（例如 create job）。
• 数据读取，例如：查找job
• 处理所有其他系统的状态机（例如：machine，task，allocs等等）与Borglet通信以及提供界面。

虽然BorgMaster看上去是一个单点，但其实他有五个冗余副本。这5个冗余副本里都有一份内存镜像拷贝。与此同时，他们还吧状态考入一个paxos-based 存储中。
在工作时，5副本中的一份被同时选为存储的master以及工作的master。因此它这时候及负责状态变更（提交任务，停止任务），也负责paxos-leader。

Leader会在chubby上挂一把锁，因此leader挂掉时候就会从新做一次leader eleciton。一般从master 挂掉到选出新的master一般只需要10s，但实际上切换过程可能要持续一分钟，因为如果在一个大一点的cell中，一些in memory state change 会被reconstruct。一个副本挂掉的时候，他会从其他节点同步信息并从新进入备份状态。

Leader状态维护是通过checkpoint+stagelog的形式实现的。

G家为了debug BorgMaster 专门做了一个fake FauxMaster。该Master可以读取checkpoint file+stagelog还原真正的borg。这样可以方便步进borgMaster以调试Master的性能状态。

Scheduling

当提交一个任务时，borgmaster先存到paxos store中，然后扔到pending
queue中。Scheduler会使用round-robin在考虑优先级的条件下，以async的方式扫描pending queue，任何task一旦有适合的资源就扔上去提交。之所以用round-robin的方式扫所有而不是严格等待是担心有大作业堵塞队列。具体来说，具体的调度分为两部分：可能性检测（feasibility check）以及打分（scoring）。feasibility check负责找到能够支持task run的机器，而scoring在所有支持的机器中选出合适的机器。

• Feasibility Check

feasibility check 选择符合作业描述的constraint并且还有空闲资源的机器（注意，这里所谓的具有空闲资源包括哪些运行着比当前作业优先级低的作业，因为在最坏的情况下，有可能要杀掉这些作业才能有足够的资源）。

• Scoring

Scoring就是给这些机器打分挑选出『好』机器，核心显然是定义什么是『好』。
Scoring考虑了用户preference，但主要还是参考一些内部criteria，包括

1. 尽可能减少允许执行的task 数量以及优先级（ minimizing the number and priority of preempted tasks没懂？？）
2. 使用哪些已经有task安装包的机器
3. Spreading tasks across power and failure domains
4. Packing quality including putting a mix of high and low prioritytasks onto a single machine to allow the high-priority ones to expand in a load spike

Borg在打分上之前是使用E-PVM。该系统针对不同的系统产生一个单一的分数，用以减少提交一个新作业的时候更改数量。在实践过程中，E-PVM以使用大量机器分散负载而告终，这样有利于在每个机器上空出空闲资源以应对高峰负载。当然这也是有代价的：该方法已产生大量碎片为代价，尤其是针对需要很多机器的大型作业时（有可能出现永远也匹配不上的情况）。因此我们也称之为『worst fit』。

而与之对应的就是『Best Fit』，该方法尽可能的填满每一台当前正在使用的机器。这样就空闲出来一部分机器给新来的作业（当然，每天机器上市肯定要跑存储的啦）。在该方式下，放置大作业就会相对轻松。
当然其问题也很突出，在这种模式下，严重压缩了task，所以会伤害对那些对borg资源申请不足或者有突发峰值的任务。尤其是对于那些non-prod的batch任务，他们常常会向borg申请极少的CPU以试图利用系统中空闲的CPU资源。 例如：有20%的non-prod任务会申请0.1个CPU。

当前打分算法是个比『Best Fit』更狠的算法，比其打包效率还高3~5%。该方法是个混合模型：Our current scoring model is a hybrid one that tries to reduce the amount of stranded resources – ones that cannot be used because another resource on the machine is fully allocated。

当然，如果socring选出来的机器资源不足，Borg是允许杀掉（preempt）优先级低一些的task的。被杀掉的任务会被重新扔到pending queue中而非让其进入冬眠状态。

任务启动时间需要被严格关心，其启动中位数大概为25s，其中package installation时间占到80%。其中一个众所周知的bottleneck是contention for the local disk where packages are written to。因此为了减少startup时间，scheduler倾向于使用那些已经安装好包的机器，此外G家还说我们做了个p2p的包下载。

BorgLet

BorgLet就是borg的agent，分布在每个机器上。作为一个borg的小弟，他做了如下事情：

• starts and stops tasks
• restarts them if they fail
• manages local resources by manipulating OS kernel settings
• rolls over debug logs
• reports the state of the machine to the Borgmaster and other monitoring systems.

BorgMaster是定时找borglet拉取信息，这就给了brogmaster足够的能力控制二者之间的通信带宽。防止出现recovery storm之类的网络风暴。

BorgMaster应该负责采集每个borglet的状态并负责更新这些状态。为了performance scalability 每个borgmaster replica运行一个stateless link shard对一部分borglet进行通信；并且这种分区会在每次borgmaster被重新选举的时候重新分配。为了可弹性（resiliency），borg小弟每次都返回自己全部的状态，但link shard会根据其期之前的状态进行压缩以及合并，向state machine 上传变化的部分，以减少通信开销。

在轮询的过程中，如果borglet没有回复消息，说明挂了。并将borglet的计算任务重新部署到其他节点上进行计算。如果通信恢复了，老大让小弟再杀掉任务以避免出现重复计算的问题。其实这一点也另外隐含着一个主题，就是当小弟与大哥失去通信的事后，小弟会继续执行任务。

Scalability

G家先装了一个B：我们不知道我们系统可扩展性的上限是多少，因为我们遇到的任何上限都被我们消除了。目前我们一个borg Master大概可以管理一个Cell中成千上万个机器。其中部分Cell中达到task 1W/minute。忙碌情况下的Borg Master大概使用10~14个core以及50GB的mem。

调度实现问题

早期实现的Borg Masters通过一个Loop全部搞定：接受request，调度task，comunicate with borglet。为了handle更大规模的问题，我们将scheduler分成了多个进程，用以保证它可以喝其他borgmaster的函数并行执行。
一个scheduler replica针对一个cell state的copy执行如下操作：

• 从选出来的master拿到job的状态，包括pending的以及assigned
• 更新其本地copy
• 进行一次scheduling并assign task
• 把结果通知elected master
• master会接受并回应这次 assignment 除非其不合理的（例如 based on out of date state）。这时replica们会考虑重新再来一次scheduling。

This is quite similar in spirit to the optimistic concurrency control used in Omega [69], and indeed we recently added the ability for Borg to use different schedulers for different workload types.

响应时间问题

为了更好采集系统状态，

• 我们将状态采集从scheduling中分离出来作为单独的线程进行实现。
• 让所有的replica都负责一部分数据的的采集。

这样使得99%的UIrequest小于1s， 95%的borglet polling 小于5s。

调度优化

• 打分缓存:

Scoring算一次是很昂贵的，所以打分依赖项不变的话，是可以对一个打分进行缓存的。

• Equivalence classes

部分borg job有一些额外的需求，这些额外需求可能部分机器才能满足（外网IP之类）。预期选出所有隐含的机器，然后对所有机器打分，不如机器提前执行constraints，选机器的时候就只选符合constraints的。

• Relaxed randomization

对cell中所有的点计算一遍feasibility以及score还是一个很慢的过程，所以scheduler可以random的选一部机器直到他觉得『够了』，并从中选出最合适的。这样当作业加入以及了离开cell的时候，使用这种方式可以减少scoring次数以及scoring cache miss的次数。 Relaxed randomization在一定程度上与sparrow的 batch sampling。

可靠性

Failure在large scale system中是非常常见的。Borg中的程序应该是有一定容错能力的，例如使用replication，state storing in distributed storage，check point。但是borg依然做了一些事情。

• 被驱逐或者踢掉的任务会被重新调度
• reduces correlated failures by spreading tasks of a job across failure domains such as machines, racks, and power domains;
• limits the allowed rate of task disruptions and the number of tasks from a job that can be simultaneously down during maintenance activities such as OS or machine
  upgrades;
• uses declarative desired-state representations and idem-
  potent mutating operations, so that a failed client can
  harmlessly resubmit any forgotten requests;
• rate-limits finding new places for tasks from machines that become unreachable, because it cannot distinguish between large-scale machine failure and a network partition;
• 记录挂掉的task-machine组合并拒绝再次执行
• recovers critical intermediate data written to local disk by
  repeatedly re-running a logsaver task (§2.4), even if the alloc it was attached to is terminated or moved to another machine. Users can set how long the system keeps trying; a few days is common.

A key design feature in Borg is that already-running tasks continue to run even if the Borgmaster or a task’s Borglet goes down. But keeping the master up is still important because when it is down new jobs cannot be submitted or existing ones updated, and tasks from failed machines cannot be rescheduled.
Borgmaster uses a combination of techniques that enable it to achieve 99.99% availability in practice: replication for machine failures; admission control to avoid overload; and deploying instances using simple, low-level tools to mini- mize external dependencies. Each cell is independent of the others to minimize the chance of correlated operator errors and failure propagation. These goals, not scalability limita- tions, are the primary argument against larger cells.