分布式体系结构之集中式结构

集中式结构就是由一台或多台机器组成中央服务器，所有数据存储于此，所有业务也先由其处理。多节点与中央服务器连接，并将自己信息汇报给中央服务器，由中央服务器同一进行资源和任务调度。特点是部署结构简单，中央节点无需考虑对任务的多节点部署，节点服务器间无需通信和协作，只要与中央服务器通信协作即可。

Google Borg

在Borg中，一个集群称为一个Cell，每个Cell中有一个Leader，称为BorgMaster，其他服务器称为 Borglet。BorgMaster由两个进程组成：

主进程：处理客户端RPC，管理系统中所有实体状态，与Borglet通信
scheduler进程：复制任务调度，通过任务对资源的需求和当前Borglet所在服务器的资源情况进行匹配，为任务找合适节点执行

每个节点机器的agent运行一个Borglet，负责任务的拉起、停止、重启等，并管理和搜集本服务资源，将信息上报给BorgMaster。BorgMaster周期性地轮询每个Borglet 获取服务状态和信息。

用户以Job形式向Borg提交工作，每个Job由运行一个或多个相同程序的Task组成。每个Job运行在一个Borg Cell中，并将一组机器当做一个单元进行管理。Borg的服务分为两类：

长服务：长时间不停止的服务，能够处理短暂、延迟敏感的请求。主要用于Gmail、web搜索等面向C端用户的服务，及内部基础设施
批处理服务：批处理Job，对短时间的性能波动不是很敏感

这些负载通常在Cell间混合发布，每个Cell随着主要租户及时间的不同会运行不同的应用：批处理型Job来了又走，长服务型Job长时间使用一个。

Kubernets

一个k8s集群主要由Master节点和Worker节点组成。

master运行在中心服务器上，由API Server、Scheduler、Cluster State Store、Control Manager Server 组成，负责对集群进行调度管理。

API Server：所有REST命令入口
Scheduler：根据需要资源及当前Worker节点所在节点的资源信息自动为容器选择合适的节点服务器
Cluster State Store：集群状态存储，默认用etcd
Control Manager Server：执行大部分集群层次功能，如执行生命周期功能和API业务逻辑

worker节点运行在从节点服务器，有2个组成部分：

kubelet：用于通用命令行与API Server交互，根据收到的请求对worker节点进行操作。
通过与API Server通信，接收master节点根据调度策略发出的请求或命令，在worker节点上管控容器（Pod），并管控其运行状态等。Pod是k8s的最小工作单元，每个Pod包含一个或多个容器
kube-proxy：负责为容器（Pod）创建网络代理/负载平衡服务，从API Server获取所有Server信息，并根据Server信息创建代理服务Service。

Kube DNS为整个集群提供DNS服务；CNI为 Container Network Interface 的一个标准通用接口，用于连接容器管理系统和网络插件。

自动化容器部署和复制
将容器组织为组，弹性伸缩
容器间负载均衡
易于版本滚动与滚动更新

Mesos

Borg的Master直接接收用户请求，Mesos只负责的车资源的管理和分配，不涉及存储、任务调度等功能，因此Mesos Master对接的是Spark、Hadoop、Marathon等框架，用户的任务要提交到他们之上。因此，Mesos的任务调度是双层架构的。

一个集群包含Mesos Master和多个Mesos Agent。

Master负责收集和管理所有Agent的资源和状态，对接Spark等框架，将集群中服务器资源信息告知这些框架，以便进行任务资源匹配和调度。通常采用一主两备的方式，方便故障处理和恢复
Agent负责任务的拉起、停止、重启等，并负责收集所在服务器的资源信息和状态，上报Master

Mesos本身只负责资源管理，不负责任务调度。可以使用Mesos+Marathon进行容器调度，支持Docker和cgroups

分布式体系结构之非集中式结构

非集中式中所有节点都一样，没有中央节点和从节点，解决了单点故障和单点瓶颈的问题。

Akka集群

基于Actor模型，提供了一个用于构建可扩展、弹性平台。Actor 是一个封装了状态和行为的对象，它接收消息并基于该消息执行计算。Actor 间互相隔离，不共享内存，他们都有自己的MailBox，能够相互间交换消息mail。发送的Mail消息先存在MailBox中，默认按照mail到达的顺序提取并处理。Actor模型是一个异步的、非阻塞的、高性能的事件驱动编程模块。

Akka集群负责Actor模型底层节点管理，包括故障检测、节点加入/退出等。Akka为Actor模型提供了一个去中心化的节点集群管理系统，用于保证Actor间的通信。集群中有Leader节点和非Leader节点之分，Leader节点只是增加了负责节点的加入和移除集群的功能，不会影响节点的平等关系。两个重点是数据传输和集群组建管理。Akka使用Gossip实现数据一致性，以时间戳最新的消息为准。在创建集群时，节点分为3类：

种子节点：使用静态配置文件或系统运行时指定，可以生成种子节点；其是普通节点加入集群的联系点，可自动接收新加入集群的节点的信息
首种子节点：首种子节点是配置文件中的第一个种子节点。集群第一次启动成功时，其启动成功集群才能创建，保证第一次创建只有一个集群
普通节点：可向种子节点或集群中任意节点发送Join消息，请求加入集群

Akka集群每个节点启动后，读取配置文件获取种子节点列表，然后开始组建集群：

首种子节点将自己加入集群列表，以自己为中心构建集群
种子节点向首种子节点请求加入，收到同意后可加入集群
普通节点可向任一种子节点请求加入，收到同意后可加入

加入成功后通过Gossip协议传播给所有节点，组建成功后不区分种子节点和普通节点。JVM中应用了Akka框架。

Redis 集群

数据分片存储在不同Redis节点上，多个节点可共享数据。Redis集群不存在中央节点，使用Gossip保证最终一致性。在设计时，要考虑数据可靠性和分片存储问题。集群中每个节点均存在主备，每台服务器上运行两个Redis服务器，分别为主备。引入哈希槽处理数据分片存储问题。

Cassandra 集群

与redis类似，Cassandra 集群的系统架构是基于一致性哈希的完全 P2P 结构，通过Gossip保证最终一致性。Redis 集群每个节点代表一部分哈希槽，一个哈希槽代表一个哈希值区间，而 Cassandra 集群中每个节点代表一个哈希值。

在 Cassandra 集群中，每次客户端随机选择集群中一个节点请求数据，节点将对应key在一致性哈希环上定位出节点，然后转发请求并将结果反馈给客户端。

分布式调度架构之单体调度

其拥有全局资源视图和全局任务，简单易维护

为用户任务寻找合适的服务器称为调度。分布式系统中单体调度是指一个集群中只有一个节点运行调度进程，该节点对其他节点有访问权限，可搜集信息、管理状态、指派任务。单体调度器拥有全局资源视图和全局任务，可以很容易地实现对任务的约束并实施全局性的调度策略。如Borg、Kubernets等。

Borg 调度设计

调度器在系统中以单实例存在，所有请求和调度都通过这个示例进行。其包含作业和任务两个概念。作业包括名称、拥有者、任务个数，也可以有一些约束指定执行的机器。一个作业只在一个集群中运行。一个任务对应一组Linux进程，运行在一个容器内或节点上。一个作业可包含多个任务，作业类似一个任务中要做的工作的总和，任务是一项项具体的工作。

Scheduler负责任务调度，当一个作业提交给BorgMaster后，作业保存到Paxos仓库中，并将这个作业的所有任务加入等待队列。调度器异步地扫描等待队列，将任务分配到满足作业约束且有足够资源的节点上。调度以任务为单位，而非作业。调度器将任务按优先级从高到低排列，同级别任务以轮询方式处理。

Borg 调度算法

核心思想是“筛选可行，评分取优”：

可行性检查，找到一组可运行任务的机器
查询是否满足内存、CPU等资源要求
评分，从可行机器中选择一个合适的机器
可根据最小化被抢占任务数、任务是否跨域部署、机器是否高低优先级任务混合部署等设计，类似操作系统调度算法
- 最差匹配：尽量选择资源最多的机器
- 最佳匹配：尽量选择满足要求的资源最少的机器

单体调度的特征

单体调度器可以很容易实现对作业的约束并实施全局性的调度策略，因此适合批处理任务和吞吐量较大、运行时间较长的任务。
单体调度系统的状态同步比较容易且稳定，这是因为资源使用和任务执行的状态被统一管理，降低了状态同步和并发控制的难度。
调度算法只能全部内置在核心调度器当中，因此调度框架的灵活性和策略的可扩展性不高。
单体调度存在单点故障的可能性。

分布式调度架构之两层调度

在单体调度架构中，中央服务器的单点瓶颈问题，会限制调度的效率和支持的任务类型。不同服务有不同特征，对调度框架和计算的要求都不同。两层调度就是资源和任务分开调度，也就是说一层调度器只负责资源管理和分配，另外一层调度器负责任务与资源的匹配。

两层调度结构对应两层调度器，中央调度器从整体上进行资源管理和分配，将资源分配到二层调度器；再由二层调度器将资源和具体任务匹配，二层可以有多个不同的调度器以支持不同任务类型。

Apache Mesos 和 Hadoop YARN 都使用了二层调度

两层调度设计

Mesos子负责底层资源管理分配，不涉及存储和任务调度。其实现了调度器的第一层调度，负责资源管理；第二层任务调度交给了框架。

Mesos资源管理集群，由一个Master节点和多个Slave节点组成的集中式系统。每个集群有且仅有一个Master节点负责Slave节点；Slave节点项Master汇报状态，并执行框架提交的任务
框架（Framework）：运行在Mesos上，负责应用管理和调度“组件”，如Hadoop、Spark、MPI等。框架主要由调度器和执行器组成，调度器可从Master获取集群节点信息，执行器在Slave上执行任务。

基本流程如下：

框架向 Mesos Master 注册
Mesos Slave 定期向 Master 上报节点空闲资源
Master 的 Scheduler 进程收集所有节点空虚资源并以 Resource Offer 的方式发给注册的框架
框架的Scheduler接收到Mesos发送的资源后，进行任务调度与匹配，将结果下发给Mesos Master，并由其转发给响应节点执行器执行任务

Resource Offer 机制衔接了第一层和第二层调度：Mesos Master 主动将节点空闲资源以Offer的方式发给每个框架，若需要则使用，否则则还回。

通过 Resource Offer 机制，第一层调度将资源主动告知第二层调度，然后第二层调度进行具体的任务匹配，从而实现了任务调度与资源管理的分离，Mesos Master 通过资源分配算法决定给各个 Framework 提供多少资源，而 Framework 则决定接受哪些资源，以及哪些任务使用这些资源运行。这样一来，一个两层调度架构就实现了。

第二层调度器的调度策略可参考Hadoop、Spark等

资源分配算法

此处讨论第一层，需要决定当前可用资源分配给哪些框架及分配多少。接下来讨论最大最小公平算法（Max-min Fairness，MMF）和主导资源公平算法（Dominant Resource Fairness，DRF）

最大最小公平算法

3个主要准则：

按照用户对资源需求量递增的顺序进行空闲资源分配；
不存在用户得到的资源超过自己需求的情况；
对于分配的资源不满足需求的用户，所获得的资源是相等的。

采用了绝对公平的方式，导致大量资源浪费

主导资源公平算法

在考虑用户公平性的前提下还考虑了用户对不同资源类型的需求。在Mesos中，首先计算已分配给用户的每一种资源的占用率，比如已分配的CPU占用量和已分配的内存占用总资源量。所有资源占有率中的最大值称为该用户的主导资源占用率，对应的资源就是用户的主导资源。

计算资源分配量
A占用<2 cpu, 8 GB> B占用 <6cpu, 2GB>，分配的总资源为 <(2x+6y)cpu, (8x+2y)GB>
确定主导资源
对于A，每个任务占总CPU资源的2/18，总内存的8/36，所以A的主导资源为内存；
对于B，每个任务占总CPU资源的6/18，总内存的2/36，所以B的主导资源为CPU
DRF算法核心是平衡所有用户的主导资源占用率，尽可能试图最大化所有用户中最小的主导资源占用率。满足公式条件下最大化x和y
```
2x+6y≤18
8x+2y≤36
8x/36=6y/18
```

最大最小公平算法适用于单一类型的资源分配场景，而主导资源公平算法适用于多种类型资源混合的场景。并且，最大最小公平算法从公平的角度出发，为每个用户分配不多于需求量的资源；而主导资源公平算法从任务出发，目的在于尽量充分利用资源使得能够执行的任务越多越好。

分布式调度架构之共享状态调度

集群中管理对象主要有两种：

资源的分配和使用
任务的调度和执行

单体调度中两种对象都由单体调度器管理，可保证全局状态一致性，可拓展性差，存在单点瓶颈。两层调度中第二次的Framework只能看到部分资源，不能保证全局状态一致性，不易实现全局最优调度。

共享状态调度器将单体调度器分解为多个调度器，每个调度器都有全局资源状态信息，再支持多种任务类型的同时还拥有全局信息，从而实现最优任务调度、提供了更好可拓展性。

State Storage模块：资源维护模块，负责存储和维护资源及任务状态，方便scheduler查询和调度
Resource Pool：多个节点集群，接收scheduler调度的任务
Scheduler：只包含任务调度

共享状态调度类似两层调度架构，但主要有两个不同：

存在多个调度器，每个都有集群全局的资源状态信息，可根据其进行调度
共享状态调度是乐观并发调度，执行任务匹配算法后，Scheduler将调度结果提交给State Storage，由其决定是否本次调度，从而解决竞争同一种资源引起的冲突问题，实现全局最优解。两层调度是悲观并发调度，执行任务前避免冲突，无法实现全局最优

乐观并发调度：事后检测，在事务提交时检测是否冲突，冲突则回滚并重新执行。在执行任务匹配调度算法后，等计算出结果后再进行冲突检测
悲观并发调度：事先预防，事务执行时检查是否存在冲突，存在则等待或回滚。再执行调度任务前，通过给不同Framework发送不同资源以避免冲突

代表有Google的Omega、微软的Apollo、Hashicorp的Nomad容器调度器。Omega作为谷歌的第二代集群管理系统，对Borg做了改进。

Omega 调度器

概念“Cell”管理部分物理集群，一个集群有多个Cell。Cell可理解为集群的子集群。

State Storage 模块维护资源和任务状态，里面的Cell State文件记录着全局共享的集群状态。每个调度器有一个Cell State副本，也就是集群资源状态信息的副本，进而达到了共享集群资源状态信息。

其中没有中央资源分配器，所有资源分配决策在调度器中根据私有的Cell State副本进行决策。调度器根据本地全局状态副本申请可用资源，做出决策后在原子提交中更新本地Cell State的资源副本。多个调度器申请发生冲突，State Storage模块可根据任务优先级进行调度。

Omega系统中每个调度器都有对整个集群资源的访问权限，允许自由地竞争空闲资源，并用乐观并发控制资源冲突。

Omega 共享调度工作原理

Omega使用事务管理思想，将资源使用和任务调度当作数据库中事务一样管理。

如图，应用执行中，调度器会将一个Job中所有Task与Resource进行多对多匹配，期间会设置多个Checkpoint检测Resource是否被占用，只有这个Job的所有Task可匹配到资源时，这个Job才可被调度。
这里一个Job类似一个事务，所有Task匹配成功后，这个事务会被成功Commit；存在Task匹配不成功，这个事务就要回滚，Job调度失败。

事务执行后，无论是否成功都会从主本那更新本地Cell State的资源状态副本。调度器对Job的调度是原子性的，一个Job的所有Task是一起调度的，即使部分Task失败，调度器再次调度时也必须再次调度整个Job。多个调度器可并行调度，存在冲突时，高优先级的获得资源。Omega涉及了Job并发调度，采用了传统数据库中的乐观锁MVCC，每个应用都发放了所有可用资源，在更新集群状态时用乐观并发控制来解决资源冲突问题，提高Omega并发度。

不同Omega调度器可实现不同策略，但某些调度规则所有调度器需一致，如那些资源可分配、如何评估作用优先级。Omega 调度器将两层调度器中的集中式资源调度模块简化成了一些持久化的共享数据（状态）和针对这些数据的验证代码。共享数据就是集群的实时资源状态信息，验证代码就是解决冲突的调度规则。