Google Borg论文

原文链接

一、简介 (Abstract)
    · Google Borg是一个集群管理器，运行着数千个应用程序的数以十万计的作业，跨多个由数万台机器组成的集群；

    · Borg可以通过超配、进程级别的资源隔离，实现高效的运行效率；
      同时支持高可用，最大限度的减少故障时间；
      并且可以通过调度策略降低相关故障的发生；

    · Borg还提供了声明性工作规范语言，名称服务集成，实时作业监控、分析、模拟系统行为的工具，简化用户操作；


二、Introduction    (入门)
    · Borg是一个集群管理系统，它全程管理、调度、启动、重启、以及监控所运行的程序；
        (个人理解，Borg本质上就是一个自动化运维程序)
    
    · Borg有三个好处：
        1. 向用户隐藏了资源管理和故障处理的细节，用户只需要专注于应用程序的开发；
        2. 高可靠性和高可用性的操作，同时还支持应用程序的相关特性；
        3. 有效在数以万计的机器上运行工作负载；


三、用户视角 (The user perspective)
    · Borg的面向用户是网站高可用工程师，也就是SRE，Borg集成自动化了传统运维的工作，
      SRE只需要以作业(JOB) 的方式向Borg提交工作，每个Job上由包含相同程序的一个或多个任务 (task)组成；
      每个Job运行在一个Borg Cell(一组机器集合管理单元)上；
    
    · 面向的工作模式 (The Workload)
        Borg包含两种workload：
            一种是那些长时间运行的服务，并且对请求延迟敏感，称之为"生产"(prod)类 一般是直接面向终端用户的产品，如 Gmail、Web、BigTable等
            一种是那些运行几秒甚至几天的批处理作业，这类服务对短期的性能波动不敏感，称之为"非生产"(non-prod)类，如mapreduce；
        一个典型的cell，一般分配给prod Job 70%的CPU资源，约占CPU使用率的60%；同时分配55%的内存资源，约占总内存使用率的85%；
    
    · 集群和单元 (Clusters and cells)
        · 一个cell的机器都归属一个cluster，通过高性能的书籍中心级的光纤网络连接；
          一个cluster部署在一个独立的数据中心建筑中，多个数据中心建筑构建为一个site；
          一个cluster通常包括一个大规模的cell和许多小规模的测试或者特殊项目的cell；
          尽量避免单点故障
        
        · 排除测试cells，一个中等规模的cell一般由10K个机器组成；
          一个cell中的机器规格是异构的，如 大小(CPU、RAM、磁盘、网络)、处理器类型、性能等；
          对于用户而言，用户不需要关心这些异构，
          Borg会在内部自动确定在哪个机器上运行任务，分配资源、安装相关依赖、并监控应用运行状态以及运行失败后的自动重启；
        
    · 作业和任务 (Jobs and tasks)
        · 一个BorgJob的属性包括name、从属的user以及tasks的数量；
          通过一个约束，可以指定Job运行在拥有指定属性的机器上；
          例如 指定处理器架构、OS版本、或者外部的IP地址；
          约束还可以分为硬限制和软限制，软限制表示优先部署在对应的机器，就像是一种偏好而不是要求；
          还可以指定Jobs的运行顺序，比如 一个Job在另一个Job运行之后再运行，一个Job只能运行在一个Cell上；

        · 每一个task会被映射为一组Linux进程运行在一台机器的容器中；
          大部分的Borg workload不会运行在虚拟机上，这样可以减少虚拟化导致的资源浪费；
          和Job一样，task也有属性，比如说它的资源需求和task在Job中的index；
          大多数task的属性通常在同一个Job，和所有task式一样的，但也是支持被覆盖的，
          例如 指定某个task执行某个命令行语句、以及每个资源维度(CPU、RAM、磁盘空间、TCP端口...)都是可以指定的；

        · 用户通过RPC来与Borg交互以操作Jobs，或者是通过其他的Job干预，又或者是监控系统；
          大部分的Job描述是用声明式配置文件BCL编写的，使用一些Borg的关键词

        · 一个Job和task的主要状态由Pending、Running、Dead组成；
          1. 当一个Job/Task被submit到Borg中，会进入Pending状态等待Borg的schedule，Pending状态的Jobs就像是被保存在一个队列中；
             Job被成功schedule到node上会进入Running状态，这时候一个Job才是真正的运行；
             Job执行finish后，会进入Dead状态，这时一个常规的流程就已经结束了；
          2. 因为Borg支持抢占schedule，所以在Running状态的Job可能会被evict，这时Job就会从新变为Pending状态，进入队列等待调度；
          3. 在Pending和Running状态的Job都可能会因为某些原因引起fail、kill、lost，从而进入Dead状态；
             所以在Borg中会自动监控到这些错误的情况，根据情况重新submit到Borg中，进而进入Pending状态等待schedule；
          4. Borg还支持在Pending和Running状态的Job进行update；
        
        · user可以修改Running中Job的tasks的属性并发送到Borg中，然后Borg会根据新的Job配置来更新对应的tasks；
          更新通常是以滚动的方式来完成，并且可以限制更新导致的task中断数量；
          一些task的update会需要重启task，如 push一个新的二进制文件；
          一些可能会使得task不适合继续在本机器部署，会需要重新调度，如 change资源的限制；
          还有一个可以在不重启不重新调度的情况下完成，如 改变优先级；

        · 在被SIGKILL抢占(被kill杀死进程)之前，task会事先通过SIGTERM得到通知，以便于清理和保存当前状态、处理正在执行的指令、以及拒绝新的指令；
          这样可以在后续恢复task的过程中，保证能够恢复到之前的状态，以及减少业务上的错误；
          如果设置了kill的延迟界限，实际的通知会少一点；在实际操作中，通知会在80%的情况下发出；
		
		· 资源分配 (Allocs) 
				· BorgAlloc是机器上一个或多个tasks可以运行的资源预留的集合；
				  无论其中的资源是否被使用，它们都会被分配	(先从OS总分配，再自行分配)；
					Allocs可以用于被未来的task所使用，在stop和restart tasks时会保留资源，在同一台机器上部署不同jobs的tasks；
					Alloc的资源处理方式和OS是类似的；
					多个tasks运行在alloc上是共享资源的；
					如果一个alloc被迁移到另一台机器上，alloc上的tasks也会随之迁移重新调度；
				
				· allocs类似于job，它是一组分配在多台机器上的预留资源；
					一旦创建了一组alloc集，就可以提交一个或多个jobs在其中运行；
					为了简洁起见，通常会使用task来refer一个alloc或者一个top-level task，
					而使用一个Job去refer一个Job或者一个alloc集；

		· 优先级、配额、权限控制	(Priority, quota, and admission control)
				· 优先级和配额设计是为了解决，工作量超出了能承受的范围；
				  给每一个Job都设置了一个Priority (优先级)，一个small positive integer；
					高优先级的task可以通过牺牲低优先级的task来获取资源，即 evict流程；
					Borg为不同用途定义不同的Priority(由高到低递减排序)：
						监控、生产(production) 、批处理(batch) 、best effort(又称testing或free)
					监控和production统称为prod任务；
				
				· 为了防止高优先级的任务evict掉一个低优先级任务后，低优先级任务继续evict掉一个更低优先级的任务；
				  也就是为了防止大部分的这种evict级联发生，我们不允许production的tasks相互抢占；
					优先级决定了task在cell中是处于running还是pending状态；

				· quota配额被用于控制那些jobs能被schedule；
				  quota表示了一段时间内给定优先级的资源量(CPU、RAM、磁盘...);
					这些值代表了Jobs在请求时间段内可以使用的最大资源使用量，
					检查quota是准入控制的一部分，如果quota不足以放下该Job，会在submit之后立即被拒绝；

				· 高优先级的配额成本比低优先级的高，在实际的使用中，程序的资源使用往往会随着工作负载增加而增加；
				  应对这种情况的发生，往往会给Jobs的quota分配会超出Jobs实际所使用的资源，也就是超卖；

				· quota分配是在Borg之外处理的，并且与我们的物理容量规划密切相关，其结果反映在不同数据中心配额的价格和可用性上；
				
				· Borg拥有一个capability系统，可以给予一个user特殊的权限；
				  例如：允许admin删除或者修改cell中的所有Jobs，访问受限的内核功能或者Borg操作，如 禁用Jobs的资源估计；
		
		· 命名和监控 (Naming and monitoring)
				· 只是提供创建和放置的tasks是不够的：我们还需要让client和其他系统能够找到这些tasks，即使它们被重新调度；
				  针对这个问题，Borg会给每一个task创建一个稳定的"Borg name service"(BNS)名称，其中包括CellName、JobName、和taskNumber;
					Borg将task部署在的机器的的hostname和port写入Chubby中一个一致的、高可用的文件中；该文件用于RPC系统查找task端；
					task 的DNS名也可以用BNS构成，如在名为cc的cell中ubar用户的名为jfoo的Job中的第50个task可以通过 50.jfoo.ubar.cc.borg.google.com 来访问；
					Borg还会当出现变化的时候将Job大小和task的状态写入到Chubby中，以便于负载均衡器可以获取到请求的路由；
				
				· 在Borg中运行的大部分task都会包含一个HTTP server，用于发布task的健康状态和数以千计的性能指标(比如 RPC延迟)
				  Borg监控健康检测的URL，并且在tasks无响应或者放回错误的HTTP码时重启该task；
					其他的数据会通过监视工具追踪展示在dashboards上，并且在发生服务级别目标(service level objective [SLO])违规警报时告警;

				· 用户可以通过Sigma提供的基于web的用户界面检查所有的Jobs、查看特定的cell，或者深入检查单个Job或task的资源行为、详细日志、执行历史最终的状态；
				  程序在running时会产生大量的log，会通过log的轮转自动覆盖掉old log，以节省磁盘的空间，并且不会在task结束后立刻删除，以协助后续的debug操作；
					如果一个Job没有在running，Borg会给出一个"why pending"的注释，以及应该如何修改Job的资源请求以更好地适配Cell的建议；

				· Brog记录所有Jobs提交和task的事务，以及每个task的资源使用的详细信息；
				  这些详细被存放在Infrastore (infra + store，元数据存储，Google的自造词hah)，
					Infrastore一个可伸缩的只读的数据存储，通过Dreme(google交互式数据分析系统) 提供类sql的交互式接口；
					这些数据用于基于使用的计费、task和系统故障的调试、以及长期容量规划；
					它还提供了google集群的工作负载跟踪数据；
					所有的这些功能都能有助于用户去理解和调试Borg的状态和其中的Jobs(利好SRE，hah)
	

四、基础架构 (Borg architecture)
		· 一个BorgCell由一组主机组成，采用的是经典的M/S(master/salve)架构；
		  逻辑集合控制器BorgMaster 和 代理进程Borglet；
			Borg的所有组件都是由C++编写的；
		
		· Borgmaster
				· 每个cell中的Borgmaster由两个进程组成：主Borgmaster进程 和 单独的scheduler调度器；
				
				· 主Brogmaster是直接对接Brog的其他组件的，
				  主要用于处理client的RPC请求，这些RPC可以改变状态(如 创建Jobs) 或者提供数据的只读访问(如 查找Jobs)，
					同时还管理着cell中所有对象(如 主机、tasks、allocs) 的状态机、与broglet通信，并提供一个web UI作为Sigma的备份；

				· Borgmaster在逻辑上是一个单一的进程，但是在实际上，它拥有五个副本(当然你也可以更多)；
				  每个副本都维护一部分cell的状态的内存副本，并且这个状态也以高可用、分布式的基于Paxos的存储在本机的磁盘中；
					每个cell都有以一个选举产生的master，它既是Paxos的leader，也是cell的mutator；
					master负责处理所有改变单元状态的操作，比如提交Jobs或者终止机器上的tasks；
					master的选举发生在cell启动或之前master失效时，master选举完成后，会获得一个Chubby锁，以便于其他节点能够找到master；
					选举master并故障转移到一个新的master一般需要十秒，并且这个时间会随着cell规模的变大而变长，因为必须要重建内存中的某些状态；
					当一个副本从中断中恢复，它会从其他最新的Paxos副本动态地重新同步它的状态；

				· Borgmaste会在某个时间点设置一个检查点，checkpoint中记录的当前时间点的状态，定期快照和保存在Paxos存储中的更改日志；
				  chickpoint用于将Borgmaster的状态恢复到过去的某个时间点(如 恢复到收到一个会触发Borg错误的请求前)、手动维护、为将来的查询建立一个持久化的事件日志和离线模拟；

				· chechpoint可以被一个名为Fauxmaster的高保真Borgmaster模拟器读取，并可以生产Borgmaster代码的完整副本，以及Borglets的存根接口；
				  它接受PRC请求来进行状态机变更和执行操作，如 "调度所有pending的tasks"，可以通过它来调试失败的情况，就像是在一个实时的Borgmaster进行交互；
					Fauxmaster还可以用于容量规划("这种类型的新Jobs多少合适？") 以及在变更cell配置前进行健全性检查("这次变更是否会驱逐其他重要的jobs？")

		· Scheduling
				· 当提交一个Job后，Borgmaster会将它永远的记录在Paxos存储中并将Jobs的tasks加入到panding队列中；
				  scheduler会异步的遍历pending的队列，如果有足够的资源满足job需求，则会分配tasks到主机；值得注意的一点：scheduler的工作对象是task，而不是Job；
					遍历顺序是优先遍历优先级高的task，通过在优先级内的轮询方案进行调度，以确保同一优先级的task的公平性，也避免了阻塞在一个大型的Job；

				· 该调度方法包括两个部分：可行性检查(找出任务可以在那些机器上运行) 和评分(从可行的机器中选择一个最适合部署的)；
				  在可行性检查中，scheduler会找到一组满足task约束条件的主机，并且拥有足够的"可用资源"(包括低优先级占用的资源，因为这些资源是可以被高优先级task抢占的)；
					在评分中，scheduler确保每个可行机器的好坏，scheduler会综合考虑用户设置的首选项，但主要有内置条件驱动，
					例如 最小化抢占tasks的数量和优先级、挑选已拥有task副本包的主机(主机上之前运行过)、在影响力和故障域层分离任务，以及packing质量(将高优先级和低优先级混合发布到一台机器，可以方便在高优先级任务在负载峰值时扩展)；
				
				· Borg最初是使用E-PVM的变体来进行评分，他在异构资源中抽象生成为单一的成本值，并在任务放置时最小化成本的变化；
				  在实践中，E-PVM最终会将负载分散到所有机器上，为负载峰值留下空间，但是代价是会增加碎片化的增加，特别是对于需要大部分机器的大型tasks；
					最终方法被称为"worst fit"(最糟糕的)
				
				· 与"worst fit"相对于的是"best fit"(最佳匹配)，它会试图将机器填满，使得部分机器上面没有Jobs运行(仍然会运行storage server) ，当大型的task需要分配时就还可以很容易找到对应的主机；
				  但是问题在于，严密的packing会惩罚用户对资源需求的误估，这在低CUP需求的批处理作业中尤其明显，20%的非prod的Job请求CPU小于0.1核，这让它们往往是作为填满机器的部分，那么当突发负载发生时，机器已经被彻底塞满，可能会导致大规模的迁移；

				· 当前的评分模型是一个混合模型，它试图减少搁浅资源(因为机器上的另一个资源被完全分配而无法使用的资源) 的数量；
					对于workload来说，这比"best fit"提供的packing效率高3~5%；

				· 如果评分阶段选择的主机没有足够可用的资源来适应新task，Borg会抢占(evict)低优先级的tasks；从低优先到高，直到可行；
				  如何将被抢占的tasks添加到scheduler中等待重新调度，而不是迁移或者休眠它们
				
				· task启动延迟(从Jobs提交到task running的时间) 的变数很大，中位数通常为25S；
				  其中安装依赖包的时间占到了80%，已知的瓶颈之一就是本地磁盘写入软件包的竞争；
					为了减少启动时间，scheduler会更倾向于把任务分配到已经安装过对于软件包的主机，因为大多数包是不可变的，因此可用共享和缓存(依赖包复用) ；
					此外Borg使用树状协议和类似torrent的协议并行发包到机器上；

		· Borglet
				· Borglet是cell中每个主机上运行的本地代理进程，它负责启动和停止tasks；如果失败了就负责重启它们；
				  通过OS内核设置来管理本地资源；滚的那调试日志；并向Borgmaster和其他监控系统报告机器的状态；

				· Borgmaster会每隔几秒就对每个Borglet轮询一次，以检索机器当前的状态，以及发送还未完成请求；
					通过master主动向node拉取信息的方式，使得Borgmaster可以控制通信速率，避免了对显式的流量控制机制的需求，防止过多的node同时对master发出请求导致master崩溃；

				· 选举出来的master负责准备发送信息给Borglets并且通过它们的响应来更新cell的状态；
					为了提高性能，每个Borgmaster副本会运行无状态的链接分片来处理与某些Borglet的通信，每次重新选举master都会重新计算分片；
					Borglet每次响应都会报告其完整的状态，但链接分片通过只报告的状态机的差异来绝活和压缩这些信息，以减少master的更新负载(增量更新，而不是全量更新)

				· 如果一个Borglet多次没有响应轮询消息，则将其主机标记为关闭，并重新调度对应主机上的tasks；
					如果通信恢复，Borgmaster告诉Borglet去kill那些已经被重新调度了的tasks，以task冗余；
				
				· 即使Borglet失去了与Borgmaster的联系，Borglet仍然会继续正常运行，一次即使所有的Borgmaster都失败了，当前正在运行的tasks和services也会保持正常运行；

		· Scalability (可扩展性)
				· 早期的Borgmaster有一个简单的同步循环，用于接收请求、安排task、与Borglet通信；
					为了处理更大规模的cell，将重要的scheduler拆解了出来，作为一个单独的进程存在，这样它就可以和其他Borgmaster功能并行运行；
					scheduler副本在cell状态的缓存副本进行运行；
					它重复地：从maste检索状态的变化(包括pending和running)、更新其本地副本、调度传递分配tasks、通知master这些任务；
					master收到这些任务的分配情况并接收它们，除非它们已经过期了，这会导致它们在调度程序的下一个pass从中重新考虑；

				· 为了提升响应时间，我们添加了单独的线程和Borglet通信并响应只读的RPC；
				  同时为了提高性能，我们通过Borgmaster的副本共享(分区)了这些功能；
					这些方法使得UI的99%响应时间低于了1S，Borglet轮询间隔的95%响应时间低于了10S；

				· 几个让scheduler更具扩展性的方法：
					1. Score cahing(评分缓存)：虽然评分是具有时效性的，但是评估可行性和主机评分成本是昂贵的，
										因此Borg会将评分缓存，直到机器的属性或者task发生了变化(机器上task终止、属性变化、或者任务的需求变化)，忽略资源数量上的小变化可以减少缓存失效；
					2. Equivalence classes(等价类)：一个Job中的tasks通常拥有相同的要求和约束，因此不是在每台机器上确定每个待处理任务的可行性，然后再给所有可行机器打分，而是在每个等价类(一组具有相同需求的任务)上做可行性分析和评分；
					3. Relaxed randomization(轻松随机化)：计算大型Cell所有机器的可行性和评分是一种很大的开销，因此scheduler并不需要分析所有机器的，可以用随机的方式在N个机器中找到一个比较合适的机器；
										这样减少了tasks加入和离开cell时所需要的评分和缓存失效量，并加快了将task分配给机器的速度；
										Relaxed randomization有点类似于Sparrow的批量抽样


五、高可用性 (Availability)
		· 在一个大的集群中，即使失败的概率再小也会常态化的发生；
			在实际的使用过程中，可以发现，大部分non-prod的tasks失败的原因是来自于被抢占，在prod task中大部分失败原因因为没有被抢占的可能所以来自于machine shutdown；
			为了减少失败的影响，运行在Borg的task会使用诸如副本、持久化保存在分布式文件系统以及在合适的情况下采用checkpoint等技术；
		
		· 即便如此，仍然需要尽可能的减轻这些事件的影响：
				1. 如果有必要，会在新的机器上重新调度被驱逐的tasks；	(即 不会在失败的机器上继续部署该task)
				2. 通过将任务分散到不同的故障域(如机器、机架、电源域)，减少相关故障；
				3. 限制在OS或机器升级等维护活动期间允许的tasks中断率和数量，即使用滚动更新的机制，而不是一次性全量更新；
				4. 使用声明式的期望状态表示以及幂等的操作(比如使用k-v结构和set的声明方式)描述Job，以便于失败的客户端可以无害地重新提交任何被遗忘的请求；
				5. 限制外网的对暴露接口的流量控制，来保证系统可靠性；
				6. 避免重复的 task-machine 配对导致的task或者machine崩溃；
				7. 通过反复re-running一个logsaver task来保存中间数据，即使Alloc被终止或者移动到其他机器；
					 这个周期可以设置，通常会设置成几天；

		· Borg的一个关键的设计特征是：即使Borgmaster或者运行task的Borglet出现了故障，已经运行的tasks仍然会继续运行；
			  尽管如此，保持master的运行仍然很重要，因为当master down时，无法提交新的Jobs，并且无法调度故障主机的tasks；

		· Borgmaster使用多种技术组合来保证高可用(4个9) ：
				机器故障复制、准入控制避免过载、使用简单、低级的工具部署实例(最小化外部依赖性)；
				每个cell独立于其他的cell，以减少相关错误和故障传播的可能，这些目标并不是可扩张性的约束，而是为了构建更大的cells的理论支持


六、资源利用率 (Utillzation)
		· Borg的主要目标之一时有效的利用google的主机，Borg的本质其实就是分布式的资源调度系统；
		
		· Evaluation methodology (资源利用率的评价方法)
				· Jobs有存放限制，需要处理罕见的工作负载峰值；机器是异构的，在从回收服务Jobs的资源中运行批处理Jobs；
					因此为了评估策略的选择，需要一个新的指标，一个比"平均利用率"更复杂的指标；
					经过实践，选择了cell压缩的方式来评估：
						即 给定一个工作负载，通过移除cell中机器的方式，直到不能满足工作负载为止，这样来确定它适合多小的cell；
						并反复从头重新re-packing工作负载，以确保不会在某个配置上挂起；
					这提供了干净的终止条件，并促进了自动比较，而没有合成工作负载生成和建模的缺陷；

				· 在正在运行的cell上进行这种实验是不可能的，但是可以使用Fauxmaster来获取高保真的模拟结构；
				  使用来自真实cell和workload的数据，包括它们的约束、实际限制、预留和使用数据
				
				· 也就是说cell压实的方法提供了一种公平、一致的方式来比较调度策略，它直接转化为成本/效益结果：
						更好的策略需要跟更少的机器来运行相同的工作负载；

		· Cell sharing (共享cell，还是按照Jobs类型等原因区分cell？)
				· 几乎所有的机器都在同时运行prod和non-prod Jobs：98%的机器在共享的Borg cell机器池中；

				· 在中型的cell中，分离prod和non-prod的Jobs需要额外20%-30%的机器才能运行我们的workload；
				  这是因为prod Jobs通常会预留资源来处理罕见的工作负载峰值，但是在大多数情况下，这些预留的资源并不会被使用；
					Borg回收未使用的资源来运行大部分的non-prod就能使用更少的机器；
					并且经过计算，如果按照用户的工作负载(比如 如果这些用户需要10TiB内存就分成一个新的cell)分成N个新cell，就需要16倍的cell数量，以及150%的总机器数量
					即使将这个阈值提升到100TiB，也至少需要2倍的cell和20%额外的机器；
					并且经过实验，将大的cell分成多个小cell，则需要更多的机器；
					因此，将资源汇集可以显著的降低机器成本；

				· 但是将不相关的用户和Jobs类型打包到相同的机器上会导致CPU的竞争，这会需要额外的机器吗？
					于是研究了具有相同时钟速度的相同机器类型下运行不同环境中的CPI(每条指令的周期) 如何变化，
					在这些条件中，CPI的值可以作为性能干扰度的一个表现，如果程序的运行时间翻倍，那么对于的CPI的值也会翻倍；
					在以上的基础上，得到几个观测点：
							1. CPI和同一时间间隔内的机器上的CPU使用率 和机器上tasks的数量 正相关：
								向机器中添加task会让CPI增加、CPU使用率越高CPI越高；
							2. 共享的cells和Jobs类型较少的cell相比，共享的cells的平均CPI要更高，通过对比Borglet的CPI效果更明显；
					这些观测点说明，共享并不会大幅度增加程序的运行成本。
				
				· 即使从两个角度观测得出的观点看起来是冲突的，但是共享仍然是最优的解法：
				  CPU性能的减速 被 减少的机器所抵消，共享带来的好处还减少了其他的资源，比如内存和磁盘；
		
		· Fine-grained resource request (细粒度的资源请求)
				· Brog会以milli-cores(微核) 为单位去请求CPU，以字节为单位请求内存和磁盘空间；
				  这样细粒度的资源请求方式可以最小化的明确资源的使用，减少资源的浪费；

				· 为什么不使用一组固定大小的桶来限制资源？
						经过实验，将请求资源的每个资源维度上四舍五入取最接近2的幂，从0.5core的CPU和1Gib的RAM开始，来桶分配资源；
						可以发现，这样做将需要额外30%~50%以上的资源
			
		· Resource reclamation (资源回收)
				· Jobs可以指定一个资源限制--每个tasks应该被授予的资源的上限；
				  这个限制被用于确定用户是否有足够的配额来接受Job，以及确定一台特定的机器是否有足够的空闲资源来安排task；
					正如有些用户会请求超过需求的配额一样，有些用户请求的资源比它们的tasks要多；
					因为Borg会杀死一个实际使用超出RAM和磁盘请求的任务，或者限制CPU使用率控制在请求的访问内；
					此外，一些tasks在偶尔需要使用它们所有的资源(比如 高峰时期)，但大多数情况下不需要；

				· 与其浪费之前已分配资源中没有使用的部分，不如尽量准确的估计将使用多少资源；
					并将剩余的资源回收给可容忍较低质量资源的工作，比如低优先级的批处理Jobs；
					这个过程就是资源回收，这个估计被称为tasks的预留，由Borgmaster每隔几秒使用Borglet捕获的细粒度使用(资源消耗)信息计算一次；
					大概的实现流程是：在tasks启动300S后，会慢慢衰减到实际使用量加上一个安全裕度，如果后续使用量超过了预定值，预定值会迅速上升	(是不是有点像拥塞控制？)

				· scheduler利用限制来计算prod tasks的可行性，因此它们依赖于回收出来的资源，也不会暴露于资源超额订阅；
				  对于non-prod的tasks，它使用现有任务的预留，因此可以将新的tasks调度到回收资源中；
				
				· 如果预留(预测) 错误，机器可能会在运行时耗尽资源(即使所有tasks的使用量都低于了限制) ；
				  如果发生了这种情况，会选择杀死non-prod tasks，而不会针对prod tasks；
				
				· 超出其内存限制的tasks将首先被抢占，而不管它的优先级如何，因此很少有tasks会超过其内存限制；
				  并且 CPU很容易被限制，因此在短期的峰值可以无害的将使用量推到预留以上；


七、隔离性 (Isolation)
		· 尽管之前通过实验证明了将多个程序混合部署在共享机器可以提高利用率，但是它还需要良好的机制来防止tasks之间相互干扰；
		  隔离性包括了安全隔离和性能隔离；
		
		·  Security isolation (安全隔离)
				· Brog使用了Linux的chroot jail作为同一台机器上的多个tasks之间的主要安全隔离机制；
				  为了允许远程调试，使用了自动分发(以及撤销) ssh密钥，以便于仅在机器为用户running task时才允许用户访问；
					对于大多数的用户来说，这个命令与Borglet合作构建了一个ssh连接，该shell连接在tasks相同的chroot和cgroup中运行，从而更紧密的锁定访问；
		
		· Performance isolation (性能隔离)
				· Borglet的早期版本具有原始的资源隔离：对内存、磁盘空间、CPU周期性的进行时候检查，同时终止使用过多内存或磁盘的task，并积极的应用Linux的CPU优先级来控制使用过多CPU的任务；
				  但是因为是事后检查所以，恶意的任务仍然很容易影响其他机器上其他任务的性能，所以一些用户会夸大资源请求，以减少Borg可以与它们共同调度的task数量，从而降低了资源利用率；
					虽然使用资源回收的策略可以弥补部分过剩，但不是全部；比如用户使用的是专用机器或cell (应该在前面说说过共享cell和专用cell吧！！！)
				
				· 所以Borg使用了Cgroup技术，所有的Brog tasks都运行在一个继续Linux Cgroup的资源容器中，并且Borglet操作容器设置，
					因为OS的内核是不断循环的，所以大大提高了控制能力；但是，偶然的低级资源干扰仍然会发生(比如 存储器带宽或L3高速污染)；
				
				· 为了帮助重载和超量使用资源，Borg tasks有一个或多个应用程序类；最重要的就是延迟敏感类(LS，对响应时间要求高) 和其他类(批处理)；
				  LS tasks用于需要快速响应请求的面向用户的应用程序和共享基础设施服务；
					高优先级的LS tasks会得到最好的处理，并且可以一次暂停几秒钟批处理tasks；

				· 第二次分割时在可压缩资源之间进行的，比如CPU周期、磁盘I/O带宽...
				  这些资源是基于速率的，可以通过降低tasks的服务质量而不是杀死它来回收；
					不可压缩资源(如 内存、磁盘空间)，这些资源通常不能在不终止tasks的情况下回收；
					如果一台机器耗尽了不可压缩资源，Borglet会立即终止task，从最低优先级到最高优先级，直到满足剩余的预留；
					如果机器耗尽的是可压缩资源，Borglet会限制使用，一百年在不终止任务的情况下处理短负载峰值，
					如果情况仍然没有改善，Borgmaster会从机器中删除一个或者多个tasks；

				· Borglet中的用户空间控制循环根据预测的未来使用量(对于prod tasks) 或内存压力(对于non-prod任务)将内存分配给容器；
				  从内核层面处理内存不足(OOM) 事件；当tasks试图分配超过其内存限制的内存时，或者当过度使用的机器耗尽内存时，将终止task；
					易于需要精确的内存统计，所以Linux eager file-caching(快速文件缓存)会使得实现变得非常复杂；
				
				· 为了提高性能隔离，LS tasks可以保留整个物理的CPU内核，从而组织其他LS task使用它们；
				  批处理task允许在任何核心上允许，但相对于LS task，批处理task只能获取少量的调度程序共享；
					Borglet动态调整贪婪LS任务的资源上限，以确保它们在多分钟内不会饿死批任务，并在需要时选择性的应用CFS带宽控制(控制一个任务组在给定周期时间内可消耗的CPU时间)；
					分配时不充分的，所以，我们需要多个优先级；

				· 标准的Linux CFS(Completely FairScheduler，完全公平调度器) 需要进行大量调整以支持低延迟和高利用率；
				  为了减少调度延迟，使用的CFS版本使用了扩展的每个cgroup负载历史，允许LS task抢占批处理task，并在一个CPU上运行多个LS task时减少调度量；
					值得一提的时，大多数的应用程序时 Thread-per-request 模型，即 每一个请求都会重新创建一个线程，这可以减轻持续负载不平衡的影响；
					谨慎的使用cpusets将CPU内核分配给对延迟要求严格的程序，以及增加线程布局和CPU管理(NUMA)、超线程和功耗感知；

				· 允许tasks消耗的资源达到限制，它们中的大多数被允许超出CPU等可压缩资源的范围，已利用未使用(slack) 的资源；
				  只有5%LS tasks会禁用这种功能，大概是为了获得更好的可预测性，只有1%的批处理task会这样做；
					默认情况下会禁止使用slack内存，因为它会增加tasks被kill的可能；
					但是10%LS tasks会这样做，79%的批处理tasks会这样做，因为这是MapReduce框架的默认设置；
					批处理task愿意机会地利用未使用的和回收的内存；


八、其他相关产品 (Related work)
		· Apache Mesos：
				使用offer-based机制，在一个中心资源管理器和多个"框架"(如 Haddop、Spark)之间拆分资源管理和放置功能；
				Borg采用的是一种基于请求的机制(request-based) 集中这些功能，这种机制更容易扩展；

		· YARN是一个以Hadoop为中心的集群管理器，每个程序都有一个与中央资源管理器协商获取所需资源的管理器；

		· Facebook的Tupperware是一个类似于Borg的系统，用于调度集群上的cgroup容器；

		· Microsoft的Apollo使用per-job调度器进行短期批处理Jobs，以便于在看起来与Borg Cells大小相当的集群上实现高吞吐量；
		  Apollp使用低优先级后台工作的机会性执行，以长时间的排队延迟为代价，将利用率提高到较高的水平；
			Apollo节点提供一个任务启动时间的预测矩阵，作为超双资源维度的函数，调度程序将其与启动成本和远程数据访问的估计相结合，通过随即延迟进行调制以减少冲突；
			Borg使用一个中央调度器来根据先前分配的状态进行布局决策，可以处理更多资源维度，并专注于高可用性、长期运行的应用程序的需求；
			Apllo会更可能处理更高的任务到达率；

		· Alibaba的Fuxi支持数据分析工作负载，和Borgmaster一样，Fuximaster从节点收集资源可用信息，接收来自应用的请求，并将其与另一个匹配；
			Fuxi增量调度策略是Borg等价类的反面，将新可用的资源与待处理工作进行匹配，为机器分配任务；
			Brog Equivalence classes是将相同约束的tasks视为一个等价类，给这一类分配机器
		
		...

		. 无论是什么思想引导的产品，管理大规模集群的另一个重要组成部分是"自动化"和"operator scaleout"；
		  描述了如何针对故障、多租户、运行状况检查、准入控制和可重新启动进行规划，以实现每个operator拥有大量机器；
			Borg的设计理念也是如此，是我们能够支持每个operator(SRE)能操作成千上万台机器；


九、经验总结 (关于Kubernetes)
		· Lessons learned：the bad
				· Job作为唯一的task分组机制，他是有限制的；
					· Borg没有使用更好的方式来将整个多任务(multi-job) 服务作为作为单体管理，或者去关联其他的服务；
						一方面，用户可用将其服务拓扑编码到Job名称中，然后构建更高级的管理工具去解析Job的名称；
						另一方面，不能应用Job的自己，这会导致滚动更新和Job调整大小的语义不灵活；
					 
					· Kubernetes没有使用Job的概念，而是使用tag来组织调度单元(pods)，用户可以将k-v对附加到系统中任一对象；
					  通过一组pods上添加job-jobname的tag，可用实现相当于Borg中Job的功能；
						同时还可以表示其他任何有用的分组，如 service、层、release-type(如 生产、阶段、测试)；
						Kubernetes中的操作可以通过选择操作tag来识别目标，如 select job=jobname；
						这种方法比Job的翻译固定分组提供了更大的灵活性；
				
				· 每台机器有一个IP地址会带来复杂性；
					· 在Brog中，主机上所有task都是用其主机的单个IP地址，从而共享主机的端口空间；
						这会导致很多麻烦：Borg必须将端口作为资源，tasks必须预先声明它们需要多少端口，并且声明在启动时使用哪些端口；
						Borglet必须强制执行端口隔离，以及命名和RPC系统必须处理端口和IP地址
					
					· 由于Linux namespaces、vm、IPv6和软件定义网络的出现，Kubernetes可以采用更友好的方法消除这些复杂性；
						每个pod和service都有自己的IP地址，允许开发人员选择端口(而不是要求他们的软件适应基础设施)，并消除了端口管理的基础架构复杂性；

				· Optimizing for power users at the expense of casual ones.(以牺牲普通用户为代价来优化高级用户)
					· Borg提供了大量针对"高级用户"的功能，这样它们就可以微调程序的运行方式(BCL中列出了230个参数)；
						过于细致的调配方式虽然对于Google来说可以很好地提高效率，但是对于普通的用户来说太复杂了，并且限制了它的发展；
						解决方案是构建在Borg之上运行的自动化工具和服务，并通过实验确定适当的设置；
		
		· Lessons learned：the good
				· Alloc的设计是非常有用的；
					· Borg Alloc抽象产生了广泛使用的logsaver模式和另一个流行的模式，简单的数据加载任务定期更新web服务器使用的数据；
					  Allocs和软件包允许由不同的团队开发这样的助手服务；

					· Kubernetes中与alloc等价的是pod，pod是一个或多个容器的资源封装，这些容器总是被调度到一个机器上，会共享资源；
						Kubernetes在同一个pod中使用helper容器，而不是像Alloc使用task，不过其中的思想是一样的，那就是通过其他的小服务来辅助一个大服务成功高效的执行；

				· 集群管理不仅仅是任务的管理；
					· 虽然Borg的主要作用是管理任务和机器的生命周期，但运行在Borg的应用程序受益于许多其他集群的服务，包括命名和负载均衡；

					· Kubernetes使用服务抽象来支持命名和负载均衡：服务有一个名称和一组由tag选择器定义的动态pods；
					  集群中的任何容器都可以使用service name连接到service，
						在这一层上，Kubernetes会自动和tag选择器匹配的pod之间的服务器连接进行负载均衡，并跟踪由于故障而重新调度的pod；
					
				· 自我检查是至关重要的；
					· 虽然Borg几乎总是"正常工作"，但当出现问题时，找到根因是很难的；
						Borg的一个重要的设计决策是向所有用户展示调试信息，而不是隐藏信息：Borg拥有成千上万的用户，所以"自助"(这里说的是用户自助haha) 是调试的第一步；
						虽然这样会更难弃用某些功能并改变用户依赖的内部决策，但是找不到其他的替代方案；
						为了处理巨大的数据量，我们提供了几个级别的UI和调试工具，这样用户就可以快速识别与其Job相关的异常事件，
						然后深入地查看应用程序和基础架构本身的详细数据和错误日志；

					· Kubernetes旨在复制Borg的许多自我检查技术；
						它附带了用于资源监控的cAdvisor工具(采集数据) ，以及基于Elasticsearch/Kibana和Fluentd的日志聚合工具；
						可以从主机查询其对象状态的快照；
						Kubernetes有一个统一的机制，所有的组件都可以用来记录事件(计划中的pod、容器故障)，以提供给用户；
					
				· master是分布式系统的核心；
					· Borgmaster最初设计的一个单一的系统，但是随着事件的推移，它更像是一个位于协同管理用户Jobs服务生态系统核心的内核；
						例如，将调度程序和主UI(Sigma) 拆分为单独的进程，并添加用于准入控制、垂直和水平自动伸缩、重新packing任务、周期性Job执行(cron)、工作流管理和离线查询的归档系统操作等服务；
						这些都使得我们能够在不牺牲性能或可维护性的情况下扩展workload和特征集；

					· Kubernetes架构更进一步：Kubernetes的核心是一个API server，只负责处理请求和操作底层的状态对象；
					  集群管理逻辑被构建为小型的、可组合的微服务，作为此API server的客户端，
						比如 replication controller，它会在发生故障时维护pod所需的副本的数量，
						以及 node controller，它管理着机器的生命周期；