Question

分布式系统常见问题

1、「拜占庭将军问题」：1982 年 Lamport 提出拜占庭将军问题。多个拜占庭将军要如何在可能有叛徒、信使可能被策反或者暗杀的情况下达成是否要进攻的一致性决定？

2、「拜占庭将军问题简化」：假设将军中没有叛军，信使的信息可靠但有可能被暗杀的情况下，将军们如何达成一致性决定？ 解决方案：Paxos、Raft

应用场景：领导人选举、关键状态共享、分布式锁

应用案例：ZooKeeper、区块链

一致性常用算法 ：Paxos/2PC(1990)、DHT（1997）、Quorum 拜占庭协议、Zab（2010）、Raft（2014）、

表格 9 分布式系统算法列表

算法	简介	实现原理	应用案例
Paxos	最早的解决拜占庭将军问题简化的方案。1990 年 Lamport 提出。	基于消息传递的一致性算法。一致性状态机(state machine replication)。
DHT	1997 年麻省理工学院提出的一种分布式哈希（DHT）实现算法。解决因特网中的热点(Hot spot) 问题。		P2P
Quorum 拜占庭协议
拜占庭容错 PBFT	1999 年 Castro 和 Liskov 提出实用拜占庭容错算法 PBFT（Practical Byzantine Fault Tolerance），首次将此类算法的复杂度从指数级降到了多项式级。	如果系统内作恶节点数目不超过总节点数目的 1/3，PBFT 算法就能生效。
Raft	2014 年哈佛提出的算法。
Zab	为 ZooKeeper 设计的一种支持崩溃恢复的原子广播协议。	为分布式主备系统设计。	ZooKeeper

备注：ZooKeeper 是业界第一个有行业影响力的开源共识系统。

4.1 分布式共识 Paxos/2PC (1990)

Paxos 算法是莱斯利·兰伯特（Leslie Lamport，就是 LaTeX 中的"La"，此人现在在微软研究院）于 1990 年提出的一种基于消息传递的一致性算法。这个算法被 认为 是类似算法中最有效的。

Paxos 是用于解决分布式系统中一致性问题的共识算法（Consensus Algorithm），其最基本的功能是为了在多个进程之间对某个值达成一致。通过这个最基本功能，就可以在多个进程之间进行数据库、状态机、账本（区块链）等对象的同步。

Paxos 不追求值的正确性、权威性、及时性，只追求一致性。

可能问题：拜占庭式（进程由于 BUG 或者恶意发送的不正确消息）、非拜占庭式、角斗士

概念术语

表格 10 Paxos 的概念表

ID	相互不冲突的提案编号，用于区分不同轮次的提案。
Value	提案的值，即最后试图达成共识的候选结果。
Proposer	提案发起者，用于提出议案，提案的内容为：令 x=value，对同一轮提案，最多提议一个 value 。Proposer 角度看，提案分为两个阶段：Prepare 阶段、Propose 阶段。一轮提案的 value 不一定非要是 Proposer 自己提议的 value。
Acceptor	提案投票者，有 N 个。Proposer 提出的 x=value 提案必须获得超过半数(N/2+1) 的 Acceptor 接受后才能被 chosen。Acceptor 之间完全对等，在独立的时间轴执行提案投票。从 Acceptor 角度看，投票分两阶段进行：Promise 阶段、Accept 阶段。
Learner	提案学习者。一个提案超过半数 accpetor 通过即可被 chosen，其他未确定的 Acceptor 可以通过 learner 来同步结果。

说明：Paxos 中有三类角色 Proposer、Acceptor 及 Learner，主要交互过程在 Proposer 和 Acceptor 之间。

Paxos 交互有二个阶段 Phase： Prepare(Phase 1) 和 Propose(Phase 2)。

图 3 Paxos 算法图解

Prepare 阶段

A：Proposer 选择一个提案编号 n，向所有的 Acceptor 广播 Prepare（n）请求。

B：Acceptor 收到 Prepare（n）请求，若提案编号 n 比之前接收的 Prepare 请求都要大，则承诺（Promise，将 n 记录下来） 将不会接收提案编号比 n 小的提议，并且带上之前 Accept 的提议中编号小于 n 的最大的提案 value。如果 n 比之前接受的提案编号小，则不予理会。

Propose 阶段

A：Proposer 收到 Acceptor 的 Promise

如果未超过半数的 accpetor 回复承诺（Promise），本次提案失败；

如果超过半数的 Acceptor 回复承诺，又分为不同情况：

如果（回复承诺的）所有 Acceptor 都未接收过 value（都为 null），那么向所有的 Acceptor 发起（Propose）自己的 value 和提案编号 n。

如果有部分 Acceptor 接收过 value，那么从接受过的 value 中选择提案编号最大的 value 作为本次提案的 value，提议编号仍然为 n（即：此时 Proposer 不能提议自己的 value，只能信任 Acceptor 通过的 value，以达成收敛的效果。）

B：Acceptor 接收到提议后，如果该提案编号不等于自身当前承诺的编号（第一阶段记录的），不接受该请求，相等则将提案的 value 写入本地。

4.2 一致性哈希 DHT (1997)

一致性哈希算法在 1997 年由麻省理工学院提出的一种分布式哈希（DHT）实现算法，设计目标是为了解决因特网中的热点(Hot spot) 问题，初衷和 CARP 十分类似。一致性哈希修正了 CARP 使用的简单哈希算法带来的问题，使得分布式哈希（DHT）可以在 P2P 环境中真正得到 应用。

一致性 hash 算法提出了在动态变化的 Cache 环境中，判定哈希算法好坏的四个定义：

1、 平衡性 (Balance)：平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得所有的缓冲空间都得到利用。很多哈希算法都能够满足这一条件。

2、 单调性 (Monotonicity)：单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到原有的或者新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。

3、 分散性 (Spread)：在分布式环境中，终端有可能看不到所有的缓冲，而是只能看到其中的一部分。当终端 希望通过哈希过程将内容映射到缓冲上时，由于不同终端所见的缓冲范围有可能不同，从而导致哈希的结果不一致，最终的结果是相同的内容被不同的终端映射到不 同的缓冲区中。这种情况显然是应该避免的，因为它导致相同内容被存储到不同缓冲中去，降低了系统存储的效率。分散性的定义就是上述情况发生的严重程度。好 的哈希算法应能够尽量避免不一致的情况发生，也就是尽量降低分散性。

4、 负载 (Load)：负载问题实际上是从另一个角度看待分散性问题。既然不同的终端可能将相同的内容映射到不 同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同 的内容。与分散性一样，这种情况也是应当避免的，因此好的哈希算法应能够尽量降低缓冲的负荷。

在分布式集群中，对机器的添加删除，或者机器故障后自动脱离集群这些操作是分布式集群管理最基本的功能。如果采用常用的 hash(object)%N 算法，那么在有机器添加或者删除后，很多原有的数据就无法找到了，这样严重的违反了单调性原则。

4.3 拜占庭容错 PBFT Quorum

图 4 PBFT（拜占庭容错）算法

其中 C 为发送请求端，0123 为服务端，3 为宕机的服务端，具体步骤如下：

1. Request：请求端 C 发送请求到任意一节点，这里是 0
2. Pre-Prepare：服务端 0 收到 C 的请求后进行广播，扩散至 123
3. Prepare：123,收到后记录并再次广播，1->023，2->013，3 因为宕机无法广播
4. Commit：0123 节点在 Prepare 阶段，若收到超过一定数量的相同请求，则进入 Commit 阶段，广播 Commit 请求
5. Reply：0123 节点在 Commit 阶段，若收到超过一定数量的相同请求，则对 C 进行反馈

根据上述流程，在 N ≥ 3F + 1 的情況下一致性是可能解決，N 为总计算机数，F 为有问题的计算机总数。

备注：拜占庭容错能够容纳将近 1/3 的错误节点误差，IBM 创建的 Hyperledger 就是使用了该算法作为共识算法。

4.4 Raft (2014)

Raft 是一种管理复制日志的一致性算法。

它的首要设计目的就是易于理解，所以在选主的冲突处理等方式上它都选择了非常简单明了的解决方案。

在 Raft 中，问题分解为：Leader 领导选取、日志复制、安全和成员变化。

复制状态机通过复制日志来实现：

• 日志：每台机器保存一份日志，日志来自于客户端的请求，包含一系列的命令
• 状态机：状态机会按顺序执行这些命令
• 一致性模型：分布式环境下，保证多机的日志是一致的，这样回放到状态机中的状态是一致的。

RAFT 核心思想很容易理解，如果数个数据库，初始状态一致，只要之后的进行的操作一致，就能保证之后的数据一致。由此 RAFT 使用的是 Log 进行同步，并且将服务器分为三中角色：Leader，Follower，Candidate，相互可以互相转换。

RAFT 从大的角度看，分为两个过程：

1. 选举 Leader
2. Leader 生成 Log，并与 Follower 进行 Headbeats 同步

4.5 ZAB

Zab 协议 的全称是 Zookeeper Atomic Broadcast （Zookeeper 原子广播），是为 ZooKeeper 设计的一种支持崩溃恢复的原子广播协议。

ZAB 的具体实现

• ZooKeeper 由 client、server 两部分构成
• client 可以在任何一个 server 节点上进行读操作
• client 可以在任何一个 server 节点上发起写请求，非 leader 节点会把此次写请求转发到 leader 节点上。由 leader 节点执行
• ZooKeeper 使用改编的两阶段提交协议来保证 server 节点的事务一致性

ZKID：ZooKeeper 会为每一个事务生成一个唯一且递增长度为 64 位的 ZXID,ZXID 由两部分组成：低 32 位表示计数器(counter) 和高 32 位的纪元号(epoch)。

Zookeeper 是通过 Zab 协议来保证分布式事务的最终一致性。

• Zab 协议是为分布式协调服务 Zookeeper 专门设计的一种 支持崩溃恢复 的 原子广播协议 ，是 Zookeeper 保证数据一致性的核心算法。Zab 借鉴了 Paxos 算法，但又不像 Paxos 那样，是一种通用的分布式一致性算法。它是特别为 Zookeeper 设计的支持崩溃恢复的原子广播协议。
• 在 Zookeeper 中主要依赖 Zab 协议来实现数据一致性，基于该协议，zk 实现了一种主备模型（即 Leader 和 Follower 模型）的系统架构来保证集群中各个副本之间数据的一致性。

Zab 协议的特性 ：

1. Zab 协议需要确保那些 已经在 Leader 服务器上提交（Commit）的事务最终被所有的服务器提交 。
2. Zab 协议需要确保 丢弃那些只在 Leader 上被提出而没有被提交的事务 。

图 5 ZAB 协议

Zab 协议原理

Zab 协议要求每个 Leader 都要经历三个阶段：发现，同步，广播。

• 发现：要求 zookeeper 集群必须选举出一个 Leader 进程，同时 Leader 会维护一个 Follower 可用客户端列表。将来客户端可以和这些 Follower 节点进行通信。
• 同步：Leader 要负责将本身的数据与 Follower 完成同步，做到多副本存储。这样也是提现了 CAP 中的高可用和分区容错。Follower 将队列中未处理完的请求消费完成后，写入本地事务日志中。
• 广播：Leader 可以接受客户端新的事务 Proposal 请求，将新的 Proposal 请求广播给所有的 Follower。

本章参考

[1]. paxos 图解, http://coderxy.com/archives/121
[2]. Paxos 算法详解, http://coderxy.com/archives/136
[3]. Paxos 算法 wiki, http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95#.E5.AE.9E.E4.BE.8B
[4]. 晦涩的 Paxos https://www.jianshu.com/p/ddf0db5d5f52
[5]. 区块链共识算法 PBFT（拜占庭容错）、PAXOS、RAFT 简述 https://blog.csdn.net/jerry81333/article/details/74303194
[6]. Raft 《 In search of an Understandable Consensus Algorithm (Extended Version) 》(寻找一种易于理解的一致性算法)
[7]. Raft 一致性算法论文译文 https://www.infoq.cn/article/raft-paper/
[8]. 聊聊 zookeeper 的 ZAB 算法 https://www.jianshu.com/p/400a44edee88
[9]. Zookeeper——一致性协议:Zab 协议 https://www.jianshu.com/p/2bceacd60b8a
[10]. Zab vs. Paxos
[11] . Architecture of ZAB – ZooKeeper Atomic Broadcast protocol
[12]. 从分布式一致性算法到区块链共识机制 https://blog.csdn.net/weixin_43970890/article/details/90173996