在谷歌的大尺度集群管理 Borg
概要
谷歌的Borg系统是一个集群管理者，它运行在十万台机器上，来自上千个不同的应用，穿越数个集群每个集群都有数万个机器。
结合准入控制，高效人任务打包、超量分配以及机器共享副以进程级别的性能隔离，来实现高录用率。它支持具有运行时特性的高可用性应用程序，这可以大大减少故障恢复时间，并且调度策略减少了相关故障的概率。Brog通过提供声明式的工作规范语言，名称服务，时时工作监控和分析与模拟行为的同居，简化了用户的操作。
我们提出了Borg系统架构的概要，和特性，重要的设计决策，对于一些决策的定量分析，并对从十年经验吸收的教训进行进行检查。
1 介绍
这个集群管理系统在我们内部被叫做Borg，负责接收、调度、启动、重启和监控谷歌运行的所有程序。本文将会进行解释。
Borg提供了三个主要的特性：1 隐藏了资源管理和错误处理的细节，因此应用可以聚焦于应用开发2 操作非常的可靠和可用并且支持同样的应用程序 3 我们运行的工作负载有效的穿过数万个机器。Borg不是第一个解决这个问题的系统，但是它是为数不多以这种规模运作的公司之一，并具有这种程度的弹性和完成性。 这个paper是围绕这个话题组织的，最后我们总结了我们在Borg上操作于生产环境中的一系列的定性观察。
2 用户视角
Borg的用户是谷歌开发者和系统管理员（可靠性工程或者SRE），它们运行谷歌应用和服务。用户以作业的形式提交他们的工作到Borg，每个作业包括了一个或多个任务在相同的程序员中（库）。每个工作运行在一个Borg调用中，作为一个整体来管理一组机器。这个章节剩余的部分描述了Borg用户视图中暴露出来的特征。
2.1 工作负载
Borg的单元允许由俩大部分组成的工作负载。第一个长期运行的服务必须永远不会下线，并且处理短期的延迟敏感的请求（几纳秒到几百毫秒）。这些服务被用作面向用户端的产品类似Gmail，Google Docs，和web搜索以及内部基础服务（如bigtable）。第二个是一批作业，它可能需要几秒钟或者几天才能完成；它们对于短期的性能波动铭感度来的更低。工作负载。工作单元的工作负载组合各不相同，这些应用程序根据主要租客（一些单元是批量密集的）运行不同的组合根据，并且会随着时间变化：一批工作的到来和离开，一些面向终端用户服务作业看到了每日使用模式。Borg需要同样出色的处理这些情况。
典型的工作负载可以在2011年5月一个长达一个月的跟踪中找到，它已经被充分的分析了。
在过去的几年里，一些应用框架已经构建在top之上，包括我们内部的Mapreduce系统，FlumeJava，Millwheel，Pregel。这些中的大部分有控制器，它提交一个主作业和多个工作作业；我们的分布式存储系统如GFS和它的继任者CFS， Bigtable和Megastore都运行在Borg中。
这篇文章我们将更高优先级的工作分类为生产（prod）的，其他为非生产的（non-prod）大部分的长期服务工作是prod；大部分的批量 作业是非生产的。在一个代表性的组成中，prod作业占用了70%的CPU资源，并且占用了大约60%的总CPU使用量；它分配了55%的内存总量，代表了大概85%的总内存。这个在分配和使用之间的差异我们会在5.5章证明是重要的。
2.2 集群和单元
单元中的机器在单个集群之下， 由它们连接的高性能的数据中心规模的网络结构定义。cluster位于单个数据中心内，并且建筑的集合构成了一个场地（site）。集群通常被一个大的单元托管，并且可能有一些小规模的测试或者特殊用途的单元。我们努力的避免任何的单点故障。
在排除测试单元后，我们的中位数单元大小大概为1万台机器；有的时候会更大，单元中的机器是在很多维度中有不同的种类：大小（CPU，内存，磁盘，网络），处理器类型，性能，以及外部IP地址或者闪存等功能。通过确定单元格中运行任务的位置，分配它的资源，安装应用程序和其他以来，监视他们的健康和在它们故障的时候进行重启，Borg将用户与大部分不同隔离。
2.3 作业和任务
Job(作业)：通常是指一个较大的计算任务或作业。它代表的是一个用户提交的整体工作请求，比如一个数据处理或分析任务。Job 是由多个 task 组成的，是整个计算过程的最高层级。
Task(任务)：是 job 的一个子单元，是 job 的具体执行部分。一个 job 会被拆分成多个 task，每个 task 执行 job 的一部分计算工作。
Borg的属性包括它的名称，所有者和它持有的任务数量。工作可以有约束以强制任务运行在特定属性的机器上，比如处理器架构，系统版本或者外部IP地址。约束可以是硬的也可以是软的；后者更像是偏好评而不是需求。工作的开始可以延期直到前一个任务完成。一个作业只运行在一个单元中。
每个工作映射到一组Linux进程，运行在机器上的容器中。绝大多数的Borg工作负载不在虚拟机内运行。因为我们不想要支付虚拟机的开销，此外，该系统是在我们对硬件中没有虚拟化支持的处理器进行大量投资的时候设计的。
任务也有资源，比如资源需求和任务在工作中的的索引。大部分的任务特性是在作业中的所有任务都是相同的，但是额可以被覆盖-例如，提供特定任务的命令行标志，每个资源维度（CPU 核心，RAM，磁盘空间，TCP端口等）是一细粒度独立指定的。我们不想强加固定大小的桶或槽（5.4章）。Borg程序是以静态连接的以减少允许时环境的依赖，并且被组织为二进制文件和数据文件的包，这些包由Borg协调。
通过发出远程过程调用（RPC）到Borg，用户在作业上进行操作，大部分通常来自命令行工具，其他Borg工作或者我们的监控系统（2.6章）。大部分工作的描述都是用声明性配置语言BCL编写的。这是一个GCL的变体，它生成protobuf文件，扩展了一些Borg特有的关键字。GCL提供了lambda函数以允许计算，通过应用条件他们的配置到环境来进行使用；上万个BCL文件长度超过1000多行，我们累计了数钱万行的BCL我们已经累计了千万行的BCL。Borg作业配置类似Aurora 配置文件。
如图2描述了工作和任务在生命周期中的状态。
作业和任务的状态图，用户可以发起提交，杀死，更新转换。
用户发布一个新的任务配置到Borg，可以修改一些资源或者所有在运行作业的任务，然后指定Borg将任务更新到新的规范。当它充当轻量级的非原子事务，可以在关闭之前很容易的撤销它（已提交）。通常以滚动方式运行，对更新导致的任务中断（重新安排或抢占）的数量进行限制；可能导致更多中断更新都会被跳过。
一些任务更新（例如，推送一个新的二进制文件）总是需要重新启动任务；有些（例如，增加资源需求或改变约束）可能会使任务不再适合机器，并使其停止并重新安排。还有一些（例如，改变优先级）可以总是在不重新启动或者移动的任务完成。
任务可以被在被SIGKILL抢占之前通过Unix SIGTERM信号得到通知，所以他们有时间进行清理，保存状态结束任何当前执行的请求，并且拒绝新的请求。如果抢占者设置了延迟限制，则设计通知可能会更少。事实上通知送达率约为80%。
2.4 分配（acclocs）
alloc 类似k8s中的pod，而这里的allocset有点类似deployment，cell是一组node。起到隔离调度和管理的作用
Borg alloc（allocation 的缩写 ）是机器上保留的一组资源，可以在其中运行一个或多个任务；资源仍然分配无论是否被使用。分配可以被用为未来的任务留出资源，在停止任务和重新启动任务之间保留资源，收集相同机器上的不同任务，即web服务结构和相关的日志保护任务，它复制从本地磁盘服务URL日志到分布式文件系统。分配资源的处理方式与机器资源处理的方式类似；在一个节点内运行多个任务共享其资源。如果一个分配必须被重新定位到另一台机器，它的任务将会被重新安排。
分类集合像一个作业：它是一个分配组，在多台机器上保留资源。一旦分配组已经被创建，可以提交一个或多个作业可以被提交在其中运行，简单起见，我们通常使用“task”来指代一个alloc或顶层任务（alloc之外的任务），而“job”来指代一个作业或alloc集。
2.5 优先级，配额，和准入控制
当更多的工作出现超过了配额会发生什么？我们的解决方案是隔离和配额。
每个作业都有优先级，小的正整数。高优先级的任务可以被牺牲低优先级的任务为代价获得资源，即便这可能要取代（杀死）后者。Brog定义了非重叠的优先级带为了不同的使用。Borg 为不同的用途定义了不重叠的优先级带，按优先级降序排列包括：监控、生产、批处理和尽力而为（也称为测试或空闲）。对于次文章，prod 作业指的是位于监控和生产带中的作业。
尽管被抢占的任务通常会在计算单元的其他地方重新调度，但是如果高优先级的任务挤掉了一个优先级稍低的任务，而这个任务挤掉了另一个优先级稍低的任务，就会发生抢占级联，以此类推。
k8s中也可以通过PriorityClass设置任务优先级。使用ResourceQuata设置配额。
简单来说一个带内的优先级不会相互干扰以免出现级联抢占。
尽管被抢占的任务通常会在计算单元的其他地方重新调度，但是如果高优先级的任务挤掉了一个优先级稍低的任务，而这个任务挤掉了另一个优先级稍低的任务，就会发生抢占级联，以此类推。为了消除大部分这样的情况，我们不允许生产生产优先带的任务相互抢占。细粒度的优先级在其他情况下依然有用-即Mapreduce任务中的master以稍高于他控制工作节点的优先级进行，以增强他的可靠性。
优先级表示了作业相对的重要性，它们在单元中运行或等待运行。配额用来决定哪些作业允许调度。配额在一段时间内以给定的优先级表示为资源量（CPU、RAM、磁盘等）的向量（通常是数月）。数量规定户作业一次可以请求的最大资源量。（例如现在起至七月底，xx单元将有限提供20TB内存）。配额是准入控制的一部分，不是调度：配额不充足的作业在提交时立刻被拒绝。
高优先级的配额代价超过低的配额。生产优先级被限制为单元中实际的可用资源数量，提交配额符合其于生产优先级作业的用户可以期望它运行，不考虑碎片和约束。尽管我们鼓励用户购买超过需求的配额，许多用户过渡购买，因为当应用增长时，这使他们避免受未来短缺的影响。我们对此的反映是低优先级的配额上超额销售配：每个用户在优先级为0时都有无限的资源，通常这很难实现因为资源被超额订阅了。低优先级的工作可能准许，但是仍然被挂起（事先未安排）因为不足够的资源。
配额分配由Borg外部处理，不并且与我们的物理容量计划密切相关，其反映在不同数据中心的配额价格和可用性上。只有当有足够的配额在所需的优先级上的时候作业才会被允许。配额的使用减少了对策略的需求比如Dominant Resource Fairness（优势资源公平DRF）。
Borg有一个能够赋予用户特权的系统。例如，允许管理员删除和修改任意的单元中的工作，或者允许用户访问受限制的核心特性或者Borg的行为，比如在它们的工作上禁用资源的估计。
2.6 命名和监控
这还不足以创建防止任务：服务的客户端和其他系统需要能够找到它们，即便是在重新定位到新的机器之后。为了实现这点，Borg创建了固定的 Borg name service（BNS）名称，每个任务其中包含了单元名称，作业名称和任务数量。Borg写入任务的主机名和端口到Chubby中的一致且高可用的文件中和此名称一致的、高可用的文件中，我们的RPC系统用来查找任务端点。BNS的名称也构成任务的DNS名称的基础，因此，用户ubar在单元格cc中拥有的作业jfoo中的第50个任务可以通过50.jfoo.ubar.cc.borg.google.com访问。Borg也写入作业大小和任务健康信息到Chubby无论它是否修改了，所以负载均衡器可以看到请求路由到哪了。
几乎每个在Borg下运行的任务都包含一个内置的HTTP服务，它发布关于任务健康和上千个性能指标的信息（如RPC延迟）。Borg监控健康检查URL和重启那些没有及时响应或者返回HTTP错误代码的任务。其他的数据由已屏蔽工具和服务等级目标（SLO）违规报警跟踪。
在这里Sigma有点类似于grafana
一个服务叫做Sigma提供了基于web的用户接口（UI）通过它，用户可以检查所有作业的状态，特定的单元，或者深入到单个作业和任务检查它们的行为，详细日志，执行历史，以及最终命运。我们的应用生成大量的日志；它是自动交替的，以避免运行耗尽磁盘空间，并在任务退出后保存一段时间以帮助debug。如果工作没有运行Borg提供了一个 为什么它挂起了的注释，以及如歌修改作业资源的请求以更好的使用单元的指导。我们发布了抑郁调度的符合资源形状的指导。
Borg记录所有的作业提交和任务事件，以及详细的每个任务资源使用信息在Infrastore中，其是一个可扩展的只读数据存储，通过Dremel具有交互式sql接口。这些数据被用于基础的使用情况的收费，debug任务和系统故障以及长期的容量计划。它还为谷歌集群工作负载跟踪提供了数据
所有的这些特性帮助了用户理解和debugVorg和它的工作底层，并且帮助我们的SRE管理每人数万台机器。
3 Borg 架构
Borg单元由一组机器构成，一个逻辑上的中心控制器叫做Borgmaster，以及一个名为Borglet的代理进程，它在单元中的每台机器上运行（如图1）。所有Borg的组件都是C++写的。
图1：高级别的Borg架构。只有工作节点的一小部分被展示了。
3.1 Borgmaster
Borglet类似于kubelet运行在每个node上
每个单元的Borgmaster包含俩个进程：主Borgmaster进程和单独的调度器（3.2章）。主Borgmaster进程处理客户端RPC，要么改变状态（即 创建工作）或者提供只读访问数句（即查看工作）。它也管理了系统中所有对象（机器，跳舞，分配）的状态机，与Borglet沟通并且提供WebUI作为Sigma的备份。
Borgmaster在逻辑上是单一的进程，但是实际上被复制了五次。每个副本在内存中维护一个单元的大部分状态的副本，并且这个状态也在高可用的分布式的基于paxos的存储记录在副本的本地磁盘中。每个单元选出master作为paxos的leader和状态增量，处理所有的修改cell状态的操作，比如提交作业或者中介机器上的任务。当单元被启动时，以及所选的主单元出现故障时，将选举主单元（使用paxos）。它获得Chubby锁所以其他系统可以找到它，选举master和故障转移到新的通常需要花费10s，但是在大的cell中需要一分钟，因为内存中的状态需要被创建。当副本从中断中恢复，它动态从最新一个副本重新同步它的状态。
Borgmaster的状态在某个时间点被称作检查点（checkpoint），并且定期快照加上保存更改的日志形式在paxos中进行存储。检查点会被多次使用，包括恢复Borg的状态以回到过去的任一点（例如，就在出发Borg软件缺陷请求之间调试它）；在极端的情况下手动修理，为了进一步的查询构建时间的持久日志；以及离线模拟。
这里可以做到完全模拟在生产环境故障片刻的调度情况以及请求情况，类似Kubernetes的流量重放。
一个叫做Fauxmaster的高保真的Borgmaster可以用来读取检查点文件，并且包括了完全的生产Borgmaster代码副本，同时对Borglet的接口做了桩替处理。它接受RPC以让状态机改变和执行操作，比如调度所有节点挂起服务，并且我们使用它来debug故障，通过与它交互，就好像是一个存活的Borgmaster，从检查点文件重放真实的交互。用户可以逐步执行并且观察在之前真实发生过的修改。Fauxmaster也被用来容量计划（有多少这种类型的新工作适合？），还有在单元配置更改之前进行完整性检查（这个修改将会流式任何的作业吗？）。
3.2 调度
未决队列：指在计算机科学中，等待处理的任务或事件的队列。
当工作被提交，Borgmaster持计划的将他记录在paxos存储中并且添加额外的作业的任务到未决队列中。这个扫描通过调度器进行同步，如果有足够的可用资源来满足作业的限制，那些任务分配给机器。（调度去主要操作任务，而不是作业。）来自高优先级或者低优先的扫描程序，在一个优先级内通过轮询机制进行调节，以确保跨用户的公平并且避免大人物下的对头阻塞。调度算法分为俩个部分：可行性检查，以找到可以运行的机器，以及打分，选择一个可行的机器。
在可行性检查中，调度器找到一组满足任务约束的机器，并且有足够可用的资源-它包括了可以被驱逐的低优先级任务的资源。在打分阶段，调度器程序确定每个可行机器的“好”。这个分数考虑了用户指定的偏好，但主要是由内置标准驱动的，比如最小化被抢占任务的数量和优先级，选择已经有任务副本的机器，划分任务分散到电源盒故障域，包装质量包括将高优先级和低优先级的任务混合到一台机器上以允许高优先级在负载高峰时扩展的。
优先级 (Priority)：算法会基于任务的重要性给每个任务设定优先级。高优先级的任务会优先获得资源，确保关键任务的及时完成。
价值度量 (Value Metrics)：除了优先级，E-PVM 还评估任务的价值。这些价值指标可以包括任务的执行时间、资源消耗、对系统性能的影响、完成任务的收益等。系统根据这些指标来衡量任务的“性价比”。
调度策略：E-PVM 结合优先级和价值度量，以一种平衡的方式为每个任务打分。打分后的任务会按得分排序，高分任务优先获得资源和处理。具体调度策略上，E-PVM 可以通过调整优先级和价值度量的权重，平衡系统的资源分配，以应对不同的场景需求。
避免资源占用不公平：E-PVM 通过动态权衡优先级和任务价值，避免资源被过高优先级任务长时间占用。此策略在保证关键任务的优先性时，也提高了整体的系统利用率和公平性。
Borg原生使用E-PVM算法的变种进行打分，它生成单个代价值，跨越多种资源并在防止任务时最小化修改的代价。在现实中，E-PVM最终切分负载穿过所有机器，为了负载峰值留下空间-但是代价为增加碎片化，尤其是需要大多数机器的大任务；我们有时叫这个最差适配。
与之相反的是最优适配，它会把机器劲量的填满。这使得一些机器没有用户作业（它们仍然运行存储服务），因此，防止大任务是直接的，但是紧凑的包装会惩罚用户或Borg对资源需求的任何错误估计。这将损害与突发负载的应用程序，并且尤其不适用于处理批作业，它指定低的CPU需，因为它可以轻松调度并适时的尝试运行在不用的资源：20%非生产任务请求需要小于0.1的CPU更新。
我们当前的模型混合了一个尝试减少搁浅的资源数量，即由于机器上的另一个资源已经被完全分配而无法使用的资源。它提供了3-5%的包装效率，而不是最合适我们的工作负载。
如果评分选择阶段的机器没有足够的新资源来适应新的任务，Borg从最低到最后优先级抢先杀死低优先级的任务，直到它完成。我们添加被抢占任务到调度这等待队列中而不是迁移或者休眠它们。
任务启动延迟（任务发起到任务运行的时间）是一个已经并且持续受到重大关注的领域。这是高度可变的，通常典型的是大约25S。软件安装占总时间越80%：一个已知的瓶颈是写入包对于本地磁盘的征用。为了减少任务启动时间，调度器执行分配任务到已经有必要的包（程序或者数据）被安装过的机器：大部分包都是不可变的，因此可以共享和缓存。（这是Borg调度器唯一支持的数据形式）。此外，Borg使用树形和种子式协议并行地将包分发到机器上。
树形广播和分布式哈希表广播
此外调度器使用几个基数词衣让他扩展到有数万台机器的单元。
3.3 Borglet
kubelet
Borg是一个本地代理在每个的单元的机器上。他启动和停止任务;如果他们失败了重启他们；我通过映射操作系统核心设置来管理本地资源；滚动调试日志并且上报机器的状态到Borgmaster和其他监控系统。
具体来说，当多个节点或服务同时崩溃并试图恢复时，系统会出现大量的资源请求，例如 I/O、网络带宽和 CPU。这种资源的集中消耗可能会对正常服务的运行造成冲击，进一步拖慢整个系统的恢复速度，有时甚至导致更多的服务不可用，形成恶性循环。这种现象就称为“recovery storm”。
Borg轮询每分钟每个Borglet以检索其当前状态并发送任何未完成的请求。这给了Borgmaster控制整个链接的频率，避免了对于显式流量控制机制的需要，并且避免了恢复风暴。
当选的master负责发送给borglet消息，并且和响应一起更新单元的状态。为了有效的扩展能力，每个Borgmaster副本运行无状态的链接碎片（link shard）已处理Borglet的通信；当Borg选举发生的时候重新计算分区。为了可恢复性，Borg总是上报全部状态，但是链接碎片通过是只上报差异信息来聚合与压缩状态机，以减少被选上的master的更新负载。
如果Borglet不回应几个投票信息它的机器就被标记为失败，它在运行的任何任务都被调度到其他机器上。如果链接修复了Borgmaster告诉Borglet杀死它的已经被重新调度的任务以避免多次复制。Borglet继续普通操作，即便它丢失了和主的租约，所以当前运行的任务和服务，因此即便所有的Borgmaster副本运行失败，当前运行的任务也会保证正常运行。
3.4 可扩展性
我们不确定Borg中心化架构的最终可扩展性限制来自哪里；因此，到目前为止每次接近极限时，我们都设法去消除它。单个Borgmaster可以管理数千个机器在一个单元中，并且几个单元的已经达到了高于每分钟10000个任务。忙碌的Borg使用10-14CPU核心和高达50GB的ram。我们使用几个技术来达到这个尺度。
Omega是谷歌的调度系统，提供乐观并发控制的（Optimistic concurrency control），传统的调度都是串行执行，每次调度请求都由单一调度器执行避免冲突。Omega允许多个调度器并发进行调度工作，并在最后阶段通过冲突检测来完成资源分配 。
Omega 的每个调度器都假设自己可以分配资源而不产生冲突。它们会在本地选择资源并生成调度决策，然后尝试提交到集群状态。只有在提交时，调度器才会检测到是否发生了资源冲突。如果多个调度器尝试同时分配相同的资源，这会触发冲突检测机制，被视为冲突的事务会自动回滚，重新调度。
当检测到资源冲突时，Omega 会让失败的调度器回退到冲突发生前的状态，再次尝试调度。这种设计让多个调度器能够“乐观地”去做决策，避免了锁机制可能带来的性能瓶颈，但也确保了资源分配的准确性和一致性。
Vorg的早期版本非常简单，同步循环接受请求，调度任务，并且和Borglet进行交流。以处理大的单元，我们将调度器拆分为单独的进程，因此它可以与其他的Borgmaster函数运行，这些复制被用于容错。调度器副本队单元状态缓存进行操作。这代表着：从选举出的master检索状态进行修改（包括已分配的和待完成的工作）；更新它本地副本； 通过调度器来分配任务；并且通知选出的master这些作业。除非这些作业不合适，不然master将接受并应用这些任务（即 基于数据集之外），这将会导致它们在调度程序的下一个阶段被重新考虑。这在精神上与Omega中使用的乐观并发控制非常相似，事实上我们最近添加了针对不同工作负载类型使用不同调度的功能。
为了提高响应时间，我们添加了单独的线程来与borglet通信，并且响应只读RPC。为了良好的性能，我们将这些函数分片（分区）到五个Borgmaster副本上 章节3.3 。这些接在一起保持了99%的UI响应时间能在1秒以下，百分之95的Borg轮询间隔小于10s。
一些让Borg调度器更加可扩展的事情：
分数缓存：评估机器的可行性和分数是昂贵的，所以Borg缓存了分数直到机器或者任务的机制改变-即，机器上的任务终止，分布已经被改变了或者任务需求改变了。忽略资源数量的微小变化可以减少缓存失效。
等价类：Borg作业中的TAsk通常有相同的需求和限制，所以不必为每个待处理的任务确定可行性，以及给所有的可行的任务打分，Borg只对相同类型的每个任务进行可行性和得分-一组有相同要求的任务。
Sparrow 是一个分布式调度系统，专为处理具有低延迟要求的任务而设计。其关键优化之一就是批量抽样（Batch Sampling），用来在分布式环境中快速、低成本地选择合适的服务器来执行任务。批量抽样是一种基于抽样的负载均衡方法，可以有效降低任务等待时间。
批量随机抽样：当一个任务到达调度器时，调度器不会查询整个集群中的每个服务器，而是从中随机挑选出一个较小的服务器子集，通常是 2 到 4 个。然后，调度器会从这个小批量的候选服务器中选出当前负载较低的服务器。
选择最优服务器：调度器会将任务分配给这个小批量服务器中负载最轻的服务器，即队列中任务最少的那一台。因为子集较小，查询操作会非常快，从而减少调度的延迟。
任务并发调度：Sparrow 还引入了一个称为“任务克隆”的策略，即当某些任务在队列中等待时间过长时，调度器会将这些任务的副本发送给其他候选服务器，以提高任务的启动概率。这种方式在负载较重的系统中尤其有效，能够减少极端情况下的任务等待时间。
放松的随机化：计算可行性是一种浪费，去计算所有的任务在大单元中的可行性和分数是一种浪费，所以调度器以随机顺序检查机器，直到找到足够多可惜的机器进行评分，然后在这个集合中选择最好的。这减少了所需的评分和缓存失效的数量，当任务进入或离开系统，并且加块了分配任务的速度。发送的随机化在某种程度上类似于Sparrow的批量抽样，同时也处理了资源，同时还处理优先级，抢占，异构和包装的成本。
在我们的实验中，从零开始调度单元的全部工作负载，通常需要花费几百秒，但在禁用上述技术后超过三天仍未完成。但是，通常情况下通过队列挂起的在线调度不到半秒的时间内完成。
4. 可用性
图3：生产和非生产的任务退出率和原因。数据来自2013年八月1日。
失败在在大尺度的分布式系统是常态。图3提供了逐出导致的崩溃在15个样本单元中。在Borg上运行的应用来接受处理这样的事件，使用类似的复制的技术，在分布式文件系统中存储持久化状态，并且（如果何时），偶尔设置检查点。即便如此，我们尝试去事件中的影响。例如，Borg
- 自动的重新调度被逐出的任务，如果需要的话在一个新的机器上。
- 通过将作业的任务分散到故障域（如机器、机架和电源域）来减少相关故障
- 限制作业中任务的中断和任务的数量，在操作系统维护等活动期间它可能会停机
- 使用声明性的期望状态表示和幂等的改变操作，因此失败的客户端可以无害的重新提交任何被忘记的请求
- 速率限制为无法到达的机器找到新的任务位置，因为它不能区分大规模的机器故障和网络分区
- 避免重复的任务：导致任务或者机器崩溃和
- 通过恢复写入本地磁盘的关键数据，恢复写入本地磁盘的中间数据，即便它所附加的分配终止或移动到另一台机器。用户可以设置系统的保持尝试的时间；一般是几天。
Borg中关键的设计特征是，已经运行的任务继续运行即便Borgmaster或者任务Borglet已经下线。但是保持master的在线仍然很重要，因为当它下线了，新的任务不能被提交或者已经存在的任务不能被修改，并且来自故障机器的任务不能重新调度。
Borgmaster使用技术的组合允许它达到99.99%的高可用在现实中：机器故障的复制；准入控制避免过载；并使用简单的低级别的工具来最小化多余的依赖。每个单元是和其他独立的，以最小化正确操作修改的错误和故障传播。这些目标不是可伸缩性的限制，是反对更大单元的主要原因。
5 使用
懒得翻译
6 隔离
我们机器的50%运行了9个或者更多的任务；我们的机器中有50%运行着9个或更多的任务；而一台90百分位的机器大约运行25个任务，并将运行约4500个线程。虽然在应用之间共享机器可以提高录用率，它也需要良好的机制来防止任务之间的相互干扰。这适用于安全和性能。
6.1 安全隔离
在 Linux 中，
chroot是一个用于更改进程根目录的工具和系统调用。它的名称源于 “change root”，意思是改变根目录。使用chroot后，一个进程及其子进程的文件系统根目录会被更改为指定的目录，从而在这个进程的上下文中形成一个受限的视图，就像一个独立的文件系统一样。（docker使用的是cgroups和namespace）KVM (Kernel-based Virtual Machine) 是一个 Linux 内核的虚拟化模块，它允许 Linux 系统作为虚拟化主机运行虚拟机。KVM 利用硬件虚拟化扩展（如 Intel VT-x 或 AMD-V）将物理主机的资源（CPU、内存、I/O 等）分配给虚拟机。
我们使用Linux Chroot 鉴于作为多个任务在一个机器上的主要的安全隔离机制。为了允许远程调试，我们使用了自动分发（和撤销）ssh key以给用户访问机器，只有它认为用户运行时。对于大部分的用户，这已经被borgssh命令所取代。它与blog合作以构建SSH连接到与任务运行在同一chroot和cgroup下的shell，从而更严格的封锁访问。
虚拟机和安全沙盒技术被用来运行外部的软件，通过Google AppEngine（GAE）Google Compute Engine (GCE)。我们在作为Borg任务运行的KVM进程中运行每个托管VM。
6.2 性能隔离
Borglet的早期版本相当的原始资源隔离强制：内存的事后推理检查，磁盘空间和CPU周期，结合终止使用磁盘或者内存任务，积极应用CPU优先级来控制任务使用过多的CPU。但是这对于在机器上影响其他性能的危险的任务还是过于简单了，所以一些用户抬高他们的资源请求，以减少BorgBorg可以和他们共同安排的任务数，从而降低录用率。资源回收可能会回收一些过剩，但是不是全部，因为设计到安全边际。在极端的情况下用户请求独占机器或者单元。
L3缓存污染（L3 cache pollution）指的是在多核处理器系统中，多个处理核心对共享的L3缓存进行不适当的或无效的缓存填充，导致缓存空间被低效占用，从而影响缓存的命中率和系统性能。
通常在发生在数据不相关性，多个任务同时竞争的情况下会发生。
现在Borg任务运行在Linux 基于cgroup的资源容器中，并且Borglet操作容器设置，由于操作系统内核处于循环中，因此提供了更号的控制。即便如此，偶尔的低级资源干扰仍然会发生（内存带宽或者L3缓存污染）。
为了防止过载和过度提交，Borg任务有任务类型或者appclass。最重要的区别是延迟敏感（LS）应用程序与其他应用程序之间的区别，在本文中我们称之为批处理（batch）。延迟敏感性应用多用于面向用户的应用程序，并且共享需要快速请求和响应的基础设施服务。高优先级的LS任务接受最好的对待，它们可以暂时饿死批处理任务几秒钟。
第二次切分是在可压缩（compressible）资源之间（即CPU周期，磁盘IO带宽），这是基于比率的并且可以通过降低它的服务质量而不杀死它从任务中回收。非压缩资源任务（内存，磁盘）它们通常不能在不杀死的情况下回收。如果一台机器用完了不可压缩的资源，Borg立即从低到高终结任务，直到保留的可以被满足。如果机器的运行超过了可压缩资源，Borg限制使用（偏好于LS任务）因此就可以在不杀死任何任务的情况下处理短暂的峰值。如果情况没改善，Borgmaster将会删除机器上的一个或者多个任务。
Borglet中用户空间控制的循环基于预测的未来使用情况（对于prod 任务）或者内存压力（non-prod任务）将内存分配给容器；处理来自内核的内存溢出（OOM）事件；并且当它尝试图分配的内存超出它的内存限制或者当他过度提交了实际上超过运行的内存就杀死这个任务。Linux的动态文件缓存使实现变的非常复杂，因为需要真实的内存计算。
为了提高性能隔离 ，LS任务可以保留整个物理CPU内核，这会组织其他LS任务来使用它们。批任务被允许运行在任何核心，但是相对于LS任务，它们被分配了很小的调度程序共享。Borglet动态调整贪心LS任务的资源上限以确保它们不会让批处理任务饿死好几分钟，在需要的时候有选择的使用CFS的带宽；因为我们有多个优先级所以份额不足。
在 Linux 系统中，cpusets 是一种用于限制和分配 CPU 和内存资源的机制。通过使用 cpusets，系统管理员或应用程序可以指定哪些 CPU 核心和内存节点（NUMA节点）可以用于特定的任务或进程，从而提高资源利用率，减少资源竞争，优化性能。
类似Leverich，我们发现标准的Linux CPU调度（CFS）需要大量的调整以支持低延迟和高录用率。为了减少调度延迟，我们CFS版本使用了扩展每组负载的历史，允许LS任务抢占批处理，当多个LS任务运行在同一个CPU上时减少了调度来给你。幸运的是，我们的一些应用使用了每个请求一个线程模型，这减轻了负载不平衡的影响。我们保守的使用cpuset来分配cpu内核给应用，特别是严格的低延迟要求。一些努力的结果如图13所示。这方面的工作仍在继续，增加了NUMA、超线程和功耗感知的线程放置和CPU管理，提高了Borglet控制的保真度。
图13：作为负载函数的调度延迟。一个线程需要等待超过1ms才能访问CPU的频率图，作为机器繁忙程度的函数。在每对柱状图中，延迟敏感任务在左边，批处理任务在右边。在只有百分之几的时间内，线程需要等待超过500ms才能访问CPU（白色条）。它们几乎不需要等待（深色的条）。来自数据来自2013年12月，错误柱展示了天到天的变化。
用户被允许在其限制范围内消耗资源。他们中的大部分允许超过CPU这样的可用资源。利用未使用的（限制）资源。只有5%的LS的任务禁用了这个，可能是为了获取更好的可预测性；只有不到1%的批处理任务是这样做的。没人情况下禁止使用闲置内存，因为它增加了任务被杀死的几率，但即便如此，10%的LS任务也重写了这点，并且79%的批任务默认会这样做，因为这是Mapreduce的默认设置。这补充了被回收的结果（5.5章）。批任务愿意适时的使用未使用的和再回收的内存：大部分情况下这是有效的，虽然偶尔批处理服务会被献祭，当LS匆忙需要资源的时候。