分布式

分布式应用到很多领域中，例如存储、缓存、文件系统、锁、事务、调度任务、调度计算、中间件消息、数据采集等等。本篇主要学习分布式的概念和理论基础。

术语概念

进程与线程

进程是系统进行资源分配和调度的一个独立单位，是具有一定独立功能的程序关于某个数据集上的一次运行活动；

线程是进程的一个实体，能独立运行的基本单位，是 CPU 调度和分配的基本单位，线程基本拥有很少系统资源（程序计数器、寄存器和栈），可以与其他线程共享进程所拥有的资源。

并行和并发

系统拥有多 CPU，当一个 CPU 执行一个线程时，另一个 CPU 可以执行另一个线程，两个线程可以同时执行互不影响，叫做并行。

运行时间或者系统资源有限，CPU 将其划分为若干个时间段去执行，当一个线程正在执行时，其他线程处于挂起状态，当再次获取资源时继续执行，这种方式称为并发。

锁

保护临界区的一种机制，再多线程场景中应用比较广泛。减少或者规避锁争用的集中策略：分拆锁、分离锁、避免共享变量缓存、使用并发容器（Amino）、使用 Immutable 数据和 ThreadLocal 中的数据。如果一个锁守护多个相互独立的状态量，通过分拆锁是每一个锁守护不同的状态量，改进可伸缩性降低每个锁被访问的频率。分拆锁对于中等竞争强度的锁能够有效的将其转换为非竞争锁，提高性能和扩展性。分拆锁被扩展为若干加锁快的集合归属于相互独立的对象，这种叫做分离锁。JDK 8 中的 ConcurrentHashMap 的实现就是使用多个锁的数组，每个锁守护自己的一部分数据，将原锁的请求分摊，以支持更好的并发性。

集群

一组相互独立、通过高速网络互连的计算机，构成一个组以单一系统的模式加以管理。集群对外的表现应当和独立的服务器相同。集群的搭建也是为了提供系统的可用性和扩展性。根据担任的角色不同，集群有几种类型：

  • 节点：系统中按照协议完成工作的一个逻辑实体，可以是执行某些工作的进程或者机器
  • 网络：系统的数据传输通道，用来彼此通信，通信具有方向性
  • 存储：系统中持久化数据的数据库或者文件存储服务器

搭建集群涉及到的技术：

  • 网络层，网络互联结构、通信协议和信号技术
  • 节点机及操作系统层高性能客户机、分层或基于微内核的操作系统
  • 集群系统管理层：资源管理、资源调度、负载均衡、并行 IPO、安全等
  • 应用层：并行程序开发环境、串行应用、并行应用等

无状态

服务无状态，不保存存储状态，可以随意重启和替代便于做扩展。

系统重发与幂等性

在做微服务设计或者 httpClient 的设计中，当一次请求出现网络或者其他失败时，有时会涉及自动重发（重试）机制。由于第一次的请求服务提供者没有明确返回业务成功与否的结果，所以当调用者有重试机制的时候，服务方应该支持幂等性设计。客户端配置重试机制时也应当充分了解服务提供者是否支持幂等性。

硬件异常

服务器宕机：服务器停电、内存异常错误等，宕机时不能提供服务的节点称为不可用，服务器宕机时将丢失内部信息，所以要考虑存储系统的持久化，以便系统重启时恢复数据。

网络异常：消息丢失、网络数据包错误等

磁盘故障：区分为软件故障和硬件故障。硬件故障例如：主板 IDE 接口松动、硬件设备不兼容、电源不稳；坏道、分区表损坏病毒等。

机房级异常：当一个机房整体断点，此时对于业务可能就是毁灭性的。需要做到同城或者异地机房的灾备。

分布式理论

CAP 理论提出了一致性、可用性、分区容错性的取舍问题；Paxos、Raft、2PC、3PC 给出了一致性的解决方案；Lease 主要针对网络拥堵或者瞬断情况给出双主的解决方案；Quorum NWR 和 MVCC 主要解决分布式存储领域的一致性问题；Gossip 是一种去中心化、容错而又最终一致性的算法。

CAP 理论

一致性（C）：在分布式系统中的所有数据备份，在同一时刻是否有同样的值，所有数据节点都是同一份最新的数据副本。一致性被称为原子对象，任何读写都应该看起来是原子操作或串行，后面的读一定能读到前面写的内容，所有的读写请求看起来像全局有序。

可用性（A）：在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求，对数据更新具备高可用性。对任何非失败的节点都应该在有限的时间内给出请求的响应，请求可终止性。

分区容忍性（P）：分区相当于对于通信时限的要求，在一定时间内系统不能达到数据一致性，就意味着发生了分区，此时需要在 C 和 A 之间做出选择。允许节点之间丢失任意多的消息，当发生网络分区时有可能完全丢失消息。

CA without P

如果不允许 P 的情况出现，则 C 和 A 是可以保证的，但是分区情况的出现是不可控的，始终会存在。分布式系统强调的是分区出现后各子系统依然可以保持 CA。关系数据库、LDAP就是放弃了分区容忍性

CP without A

不要求可用性，各个节点之间强一致，但是分区可能导致节点之间的同步时间无限延长，如此来保证 CP，传统的数据库分布式事务、分布式锁属于这种情况。

AP without C

分区发生时保证高可用就需要放弃一致性，分区发生时，一些节点可能失去联系，为了高可用每个节点使用本地数据提供服务这样可能导致全局的数据不一致。或者某些节点的数据延迟或者损失，造成对外服务的数据不一致。有些微服务的注册中心就采用这种方式实现。

Paxos 协议

基于消息传递一致性算法，主要解决分布式系统中在多个节点之间就某个值（提案）达成一致（决议）的通信协议。能够处理在少数节点离线的情况下剩余的多数节点仍然能够达成一致。对于协议的学习可以参考：Paxos 算法详解 或者《从Paxos到zookeeper分布式一致性原理与实践》- 倪超 一书。

2 PC 协议

2 阶段提交协议， 是一种原子提交协议。有第三者协调器来处理分布式原子服务参与者是提交或者回滚事务的分布式算法。该协议的两个阶段：提交请求阶段（投票阶段）和提交阶段。

投票阶段

确定各个参与者对于各自事务处理是否准备就绪，参与者发送 YES 表示可以提交，NO 表示失败。如果所有参与者都返回 YES，则进入提交阶段；如果有参与者发送 No，则协调器通知所有参与者事务中断。

提交阶段

如果参与者都表示 YES 已经准备可以提交事务，此时协调者给所有参与者发送提交事务的消息，参与者接收提交事务后并发送反馈信息（ACK）；如果有参与者事务提交失败或者超时，则协调者通知所有参与者回滚，参与者完整回滚并发送确认消息（ACK）。

缺点
  • 同步阻塞性协议，所有参与者（节点）事务阻塞，当参与者占有共有资源时，其他事务也将处于阻塞
  • 由于协调者的重要性，当协调者故障时会导致参与者的事务处于悬挂状态

3 PC 协议

由于 2 PC 协议中，当协调者故障后整个分布式事务可能就会瘫痪阻塞掉，所以在 3 PC 协议中增加了一个预提交的过程。

第一阶段，协调器询问确认参与者是否都可以提交事务，全部 YES 之后进入到预提交阶段；如果有 NO 则事务中断，协调者向参与者发消息事务中断

第二阶段，协调者向参与者发送预提交请求，各个参与者执行预提交请求并返回 ACK 响应，都成功后进入第三阶段；如果有参与者发送了 NO 或者超时，协调者向所有参与者发送 abort 中断请求，参与者执行事务中断

第三阶段，参与者在预提交全部 YES 之后，协调者通知参与者真正提交事务，参与者提交成功之后想协调者发送 ACK 响应；如果协调者没有收到参与者发送的 ACK 消息或者超时，则协调者发送 abort 请求中断事务；

如果协调者故障导致参与者等待超时或者网络原因部分参与者没有收到 doCommit 请求，由于之前已经全部执行过 preCommit 所以参与者会倾向于自己提交事务，但这也有可能造成数据不一致。

3 PC 协议在协调者和参与者都增加了超时机制，不会让事务一直处于阻塞状态，解决了单点故障导致的阻塞问题，但是也有可能造成数据不一致。

Raft 算法

Raft 和 Paxos 算法都是一致性算法，在实现上稍微不同，Raft 分解为几个关键模块：领导人选举、日志复制、安全性。在 Raft 算法中任何一个服务器可以扮演三种角色之一：

  • 领导者（Leader）：处理所有客户端交互、日志复制等动作，一般只有一个领导者
  • 选民（Follower）：负责响应来自 Leader 或者 Candidate 的数据，被动参与选举的投票
  • 候选人（Candidate）：Leader 的候选者，选举成功后成为 Leader

选举过程：

  • 任何一个服务器都可以成为候选者，向其他服务器发出要求选取自己的请求，其他服务器都同意回复 OK，则该服务器成为 Leader；成为 Leader 后可以做日志复制等操作，并在每一段时间内向所有 Follower 发送 Hearbeat 保持所有节点的状态，Follower 收到 Hearbeat 后重设自己的 Timeout 时间
  • 如果有一个选民 Follower 宕机或者失联，则只要超过半数选民同意回复 OK 即可
  • 如果 Leader 故障，其他选民正常进行选举；如果故障 Leader 恢复，由于选举是有届数记录，旧的 Leader 自动降级为 Follower
  • 假如出现一种竞争状态，总共四个服务器，有两个 Follower 同时发出选举请求，各获得两票支持（分别有一台回复 OK和自己的一票），要超过半数才能成为 Leader，此时共有两个 Candidate 和两个 Follower，两类节点的倒计时器还在运行，达到 Timeout 的节点重新发起选举

参考：Raft 算法

Lease 机制

维护分布式系统的数据一致性，由授权者授予分布式环境一段时间内数据一致性的承诺。颁发者发出 Lease 后，不管是否被接收，只要Lease不过期，颁发者都会按照协议遵守承诺，在过期时间内不修改数据。Lease 的持有者只能在有效期内使用，一旦 Lease 过期持有者需要放弃执行重新申请 Lease。主要解决缓存和服务器之间的数据一致性问题。

  • 已经过期的 Lease 导致读不到的问题，节点数据已经过期，但是服务器还未发布新的 Lease，此时读不到数据影响业务；解决方案：此时有服务器直接返回数据，下次再读时可能已经发布 Lease
  • 服务器通过其他方式修改了数据要发布新的 Lease，但是各节点的 Lease 还没有到过期时间；解决方法：服务器主动通知所有节点放弃当前 Lease，接收新的 Lease
  • 如果一次更新操作的数据对象分布在不同的节点上，对于数据 A，只要对应的节点 Lease 过期即可，对于数据 B 不影响。

脑裂问题

主备模式是实现高可用（HA）系统的一种方式，但是两个节点断开联系时，一个整体分裂为两个独立节点，节点之间争抢共享资源，导致系统紊乱数据错误等。

心跳检测是判断主备服务器是否还建立链接的一个重要方式，但是心跳检测的不确定性也是导致脑裂的一个重要原因。例如：master 服务器暂时失联，slave 服务器上位开始接手工作，但是此时 master 又活过来了还在继续工作，这个就会导致两个服务器发生分裂对主备判断逻辑带来不确定因素。

此时需要引入第三方检测服务器（Monitor），当 salve 要接管 master 时，由 Monitor 再 ping 一下 master，如果确实失联在切换。此时就需要 Monitor 的高可用保障。

Quorum NWR

分布式存储系统中控制一致性级别的策略。

  • N：同一份数据的拷贝份数
  • W：更新一个数据对象时确保成功更新的份数
  • R：读取一个对象时需要读取的拷贝份数

具体的策略是：
$$
W > N / 2
\
W + R > N
$$
写操作要确保成功的份数应高于同一份数据拷贝总份数的一半；

写操作加上读操作的总份数也要高于同一份数据拷贝总份数

N W R 说明
1 单点问题，无法满足高可用
2 在一个节点故障后，退化为单点
3 2，3 1，2，3 读越大，写性能越差；写越大，读性能越差
4 或者更多 服务器节点成本高

MVCC

多版本并发控制，一般把基于锁（行级锁）的并发控制称为悲观锁机制，MVCC 机制称为乐观锁机制。MVCC 是一种宽松的机制，读写互不阻塞。

Gossip

分布式系统状态分布在集群中的各个节点上，集群的状态同步存在两个问题：

  • 每一个节点如何较快的得知集群状态全集的某些特征
  • 如何避免多个节点就某个状态发生分歧，是的集群的状态实时或者最终一致

Gossip 是一个去中心化思路的分布式协议，通过信息的部分传递，达到全集群的状态信息传播，传播时间收敛在 $O(log(N))$ N 是节点数量。解决状态在集群中的传播和状态一致性的保证两个问题。

状态的传播

这种状态消息的传播类似于留言的传播，节点接收到消息后在传播给其他节点。每个节点起初可能只掌握整个集群的部分状态信息，通过传播达到全集状态的获取。

状态一致性

同一状态信息，不同的节点掌握的值可能不同，通过基于 Gossip 构建的协议包版本进行解决。