Borg
Large-scale cluster management at Google with Borg
an opportunity cost approach for job assignment in scalable computing cluster
Multi-agent Cluster Scheduling for Scalability and Flexibility
在各种分布式存储、批处理、流计算中都假设要占用一组独立的服务器。采购服务器后会根据峰值流量确定服务器数，高峰和低谷时资源消耗率大不相同。且对于数据中心，硬件成本只是一小部分，电力成本是大头。所以，少用点服务器就很重要了，需要“削峰填谷”。如流计算和批处理使用同一批服务器，在流计算的低谷期进行批处理，保证服务器资源的最大化利用。需要让各种大数据和业务系统混合编排在同一批服务器上。
CGroups-Linux 隔离资源解决方案
一台服务器上不同程序会竞争资源，如一台机器上流量高峰时Kafka传输流量占据整个网络带框后其他程序无法提供服务。这时需要讲服务器资源拆分开，讲一组程序隔离开，只允许使用一部分资源。这就是Linux的CGroups功能（Linux Control Group），可限制一组Linux进程使用的资源：
- 资源限制，如限制一组进程总共可用内存
- 优先级，如限制这组进程能拿到的CPU和IO吞吐量
- 结算，统计这组进程实际使用多少资源
- 控制，冻结一组进程的允许，或恢复它们的运行
系统进程被封装进一个个LXC容器，可以通过一个集群管理系统讲LXC分配到不同机器运行
Borg
一个Borg集群被称为一个Cell，部署在一个数据中心，一般约10000台机器。底层机器可能是不同版本和性能，且能够动态扩缩容，同时向上层隐藏所有资源管理细节。Borg中部署的不是一个个裸CGroup，而是一个个Tasks。用户向Borg提交一个个Job。这些Job包括长期驻留服务，也包括一次性运行批处理任务。一个Job就是一个二进制程序，被部署到一台或多台机器，每个运行的实例就是Tasks。
当遇到资源不够用时，Borg采用配额和优先级的机制。Job的优先级从高到低分为：监控（Monitoring），生产（Production），批处理（Batch），尽最大努力（Best Effort）。同一优先级根据priority参数区分。Job部署到机器上变为Task，这些Task也就继承了Job上的优先级。
生产类Tasks可抢占批处理类Tasks的资源，但生产类Tasks不可互相抢占资源。但有些批处理服务要在规定时间内完成，如每天都要使用MapReduce生产报表，可MapReduce的资源若是被生产类Task抢占则无法保证任务的按时完成。为此Borg提供了alloc的机制。alloc是一组预留的、不会被其他生产类Job抢占的资源，无论这个服务器资源是否被用到。
Borg 是典型的 Master-Slave 系统，组成部分：
- 用户界面
- Master 集群
通过Paxos协议维护多个同步复制的副本以保障高可用。通过Checkpoint建立快照，通过日志记录所有操作。整个Master集群里再选出一个master，通过Chubby的锁确保唯一性。Master集群负责管理所有元数据和处理外部RPC请求，并和Borglets通信了解集群状态。 - Scheduler 服务器
负责将Task分配给具体的服务器。一个Job提交给Master后，Master将其变为待调度的Tasks加入队列，Scheduler异步遍历队列，当有足够资源满足Job时，将Task分配到Slave服务器。 - Slave 服务器
负责运行Task的服务器。每个Slave服务器上有一个Borglet进程，负责与Master通信。Blorglet还会负责启动和停止Task，若Task失败则重启。一个集群中机器数量太多，所以由Borglet主动上报任务运行信息，Master定期轮询Borglet获得Slave服务器信息
因为节点数多达1万，Borg会将所有Slave分片，让每个master副本负责一部分Borglet通信。然后副本将Borglet上报的最新信息和Master已知信息的差（Diff）交给Master里的master，以减少其负载。
万级别规模
1万台数量本身就是一个很大挑战。Master集群通过Paxos选出master，但除了master其他副本也要与Borglet通信，且不仅仅时一个同步数据的副本。真正的挑战还在于对一个个Task的调度：
- Job发给Master集群时，该把Tasks调度到哪台机器？
- Job声明消耗的资源和Task实际消耗资源差异很大怎么办？
- 不同Task竞争CPU资源，虽然CPU利用率很高，但会不会资源都用在上下文切换而非Task的运算？
“贪心”的开发者
Borg为程序分配的资源不会超过用户声明的，这样用户倾向于多申请资源，这不利于提高机器的使用率。Borg解决方式：
- 对资源“超卖”
如64GB内存的机器允许声明了80GB的任务在Borg运行，但不会对生产类型任务进行超卖以保证正常运行。对离线任务超卖是没问题的，当资源不足时可以将其挂起或调度到其他机器 - 对资源进行动态“回收”
生产类Task使用的资源也不会达到声明的规模，所以Borg不会为其始终预留这么多。在Task开始时分配其申请的所有资源，之后逐渐减少资源，之后只留下一点Buffer。Task对资源的利用是动态的，当出现大幅上涨时，Borg迅速将Task分配的资源增加到申请的的规模
限制资源（Resource Limit）开发者申请的资源
保留资源（Resource Reservation）实际Borg动态分配的资源
回收资源（Resource Reclamation）二者差值，可以利用但只分配给非生产型任务，因为随时可能动态抢回，而Borg不允许生产线Task相互抢占
对于生产类和非生产类Task，Borg都会动态挑战分配的资源
Task 分配到服务器
调度器异步从Master写入的队列中扫描Task再分配，期间会先调度优先级高的，同一优先级Borg采用轮询方式。调度过程：
- 可行性检查（feasible checking）寻找能满足Task资源需求的机器
- 通过打分选择服务器，资源不足时高优先权Task抢占正在运行的低优先级Task
打分策略有什么用？
如果采用“平均分配”会使每台机器负载差不多，导致需要整台机器资源的大型任务找不到满足要求的机器（类似操作系统中内存分配的最坏分配）。
如果尽量使运行中服务器负载尽可能高（内存分配的最优分配），就存在很多满足大型任务的空闲服务器。但此时若某个任务需要资源忽然变多，会抢占同台机器中其他非生产型Task的资源。且出现故障时会影响更多的Task。
Google最终采用混合模型打分，也就是采取尽量减少被“搁浅（stranded）”的资源数量。“搁浅”是指某任务100%占用自己声明的资源后这个机器上不能被使用的资源。打分时要考虑的不止资源：
- 尽量挑无需重新下载Task容器镜像的机器
- 尽量不抢占正在运行的Task资源，或抢占尽量少的Task。因为有些任务失败后可能要重来
- 分布式任务的多个Task尽可能分不到不同物理位置，避免网络和硬件引起单点故障
- 尽量让不同优先级的任务混合部署，在负载高峰时高优先级可抢占低优先级的任务
k8s中可自定义调度规则
Omega & Kubernetes
- 为什么从Borg的中央式调度系统，变成Omega这种支持同时运行多个调度系统的设计？
- 除了资源的调度和隔离，编排系统还要考虑哪些问题？
负载过大的调度系统
- Borg将在线服务和批处理任务看成同样的Job，并放一起调度。没有拆为Service和Job，分别用两种调度器（Scheduler）调度
- Borg是个单Master系统，可使其只分配某个业务集群的资源，业务集群内部再进行资源分配。Borg的Master只要和少数集群的调度器交互即可
单一Master成为Borg的一个瓶颈。如果一个只要5秒的SQL Job和一个Nginx job同时提交，Borg中要等Nginx启动成功后才能执行SQl job，这使得前端的分析师体验很差。可行的方法是使用多个调度器。但面临新问题：不能让两个Job被调度到同一份资源。
静态资源分配违背了Borg的初衷，所以采用动态分区。再集群进行功能层面的划分，每个集群分配的资源会动态调整。 服务空闲时会匀出一些给批处理任务，Mesos就采用这种方案。
Mesos中第一次分配采用 Resource Offer 机制，也就是资源并不是下层调度器申请的，而是Master主动提供的，调度器只能选择接受不接受但不能抢占。这种两层调度类似数据库的悲观锁。下游调度器只能先“锁”住资源才能执行任务。但Borg中会锁住大量资源很长时间
将Master调度器变成数据库
可将悲观锁换成乐观锁
多个不同调度器看到全局资源并竞争，失败了重试。每次调度在线服务要花很多时间计算，岂不是很容易竞争失败？Borg的在线服务可抢占批处理任务资源，相同优先级在线服务使用同一个调度器，互相间不会产生并发和竞争。
这种模式，第一层更像一个调度器，除了基本调度信息读写外还要确保Borg里一系列的调度分配规则限制始终有效。