分布式共识
分布式共识
什么是分布式共识
共识 (distributed consensus) 是分布式系统中最基本的问题，用来保证一个分布式系统的可靠性以及容错能力。简单来说，分布式共识性是指多个服务器的保持状态一致。
共识问题通常形式化如下：一个或多个节点可以提议（propose） 某些值，而集群中的所有有效节点根据共识算法进行协商，最终决议（decides） 采纳某个节点的提议。
而共识算法必须满足以下性质：
- 达成一致（Uniform agreement） - 没有两个节点的决定不同。
- 完整性（Integrity） - 每个节点最多决议一次。
- 有效性（Validity） - 如果一个节点决定了值
v，则v由某个节点所提议。 - 终止（Termination） - 由所有未崩溃的节点来最终决议。
达成一致和完整性定义了共识算法的核心思想：所有人同意了相同的结果，且一旦决定了，就不能改变主意。有效性 主要是为了排除无效的提案。如果不关心容错，那么满足前三个属性很容易：你可以将一个节点做为 “独裁者”，并让该节点做出所有的决定。但如果该节点失效，那么系统就无法再做出任何决定。事实上，2PC 就存在这种问题：如果协调者失效，那么存疑的参与者就无法决定提交还是中止。
终止 意味着：即使部分节点出现故障，其他节点也必须达成共识。当然，算法可以容忍的失效节点数是有限的：需要超过半数以上的服务器达成一致。假设有 N 台服务器， 大于等于 N/2 + 1 台服务器就算是半数以上了 。
共识（Consensus）与一致性（Consistency）的区别：一致性是指数据不同副本之间的差异；而共识是指达成一致性的方法与过程。很多中文资料把 Consensus 翻译为一致性，但其实是不准确的。
为什么需要分布式共识
在分布式系统中，主节点负责对其他节点进行协调和管理，也就是说，其他节点都必须听从主节点的安排。主节点的存在，就可以保证其他节点的有序运行，以及数据库集群中的写入数据在每个节点上的一致性。这里的一致性是指，数据在每个集群节点中都是一样的，不存在不同的情况。
如果主节点故障了，集群就会天下大乱，就好比一个国家的皇帝驾崩了，国家大乱一样。比如，数据库集群中主节点故障后，可能导致每个节点上的数据会不一致。这，就应了那句话“国不可一日无君”，对应到分布式系统中就是“集群不可一刻无主”。
主节点如此重要，那么如何选举主节点呢？答案就是：分布式共识。
集群中的有效节点需要通过选举决议出哪个节点是主节点。如果部分节点由于网络故障而无法与其他节点通信，则可能会对主节点的归属引起争议。在这种情况下，共识对于避免错误的故障切换非常重要。错误的故障切换会导致两个节点都认为自己是主节点，即脑裂。这种情况下，它们都会接受写入操作，从而导致数据不一致或数据丢失。
分布式共识能否达成
Fischer、Lynch 和 Paterson （FLP）在 Impossibility of Distributed Consensus with One Faulty Process 论文中论证了：在一个异步系统中，即使只有一个进程出现了故障，也没有算法能保证达成共识。
简单来说，在一个异步系统中，由于进程可以随时发出响应，所以没有办法分辨一个进程是速度很慢还是已经崩溃，这不满足终止性（Termination）。
共识的不可能性
FLP 是一种限制性很强的模型，它假定共识性算法不能使用任何时钟或超时。如果允许算法使用 超时 或其他方法来识别可疑的崩溃节点（即使怀疑有时是错误的），则共识变为一个可解的问题。因此，虽然 FLP 是关于共识不可能性的重要理论结果，但现实中的分布式系统通常是可以达成共识的。
分布式共识算法
共识算法选举主节点的过程如同投票选举领导者（Leader），参选者（Candidate）需要说服大多数投票者（Follower）投票给他。一旦选举出领导者，就由领导者发号施令，所有追随者必须服从命令。
常见的分布式共识算法有：
这些算法之间有不少相似之处，但并不相同。下面，将大致介绍一下它们的共同思想。
全序广播
全序广播要求将消息按照相同的顺序，恰好传递一次，准确传送到所有节点。这相当于进行了几轮共识：在每一轮中，节点提议下一条要发送的消息，然后决定在全序中下一条要发送的消息。
所以，全序广播相当于重复进行多轮共识（每次共识决定与一次消息传递相对应）：
- 由于 一致同意 属性，所有节点决定以相同的顺序传递相同的消息。
- 由于 完整性 属性，消息不会重复。
- 由于 有效性 属性，消息不会被损坏，也不能凭空编造。
- 由于 终止 属性，消息不会丢失。
Raft 和 Zab 直接实现了全序广播，因为这样做比重复**一次一值（one value a time）**的共识更高效。在 Paxos 的情况下，这种优化被称为 Multi-Paxos。
主从复制和共识
主从复制将所有的写入操作都交给领导者，并以相同的顺序将状态变化广播同步到追随者，从而保持一致性。这实际上不就是一个全序广播吗？为什么不需要担心共识问题呢？
因为，这种场景下实际是一种独裁型的共识模型：只有一个节点被允许接收写入（即决定写入复制日志的顺序），如果该节点发生故障，则系统将无法写入，直到选出新的领导者。
纪元和法定人数
为了保证领导者是独一无二的，共识算法通常会定义一个逻辑时钟，用于表示选举领导者的投票轮次（纪元），而共识算法要保证每界选举得出的领导者是惟一的。不同算法中，对代表逻辑时钟的值定义不同，但作用是共通的：在 Paxos 中称其为选票（ballot）；在 Raft 中称其为任期（term）；在 Zab 中称其为纪元（epoch）。
每当现任领导者被认为宕机时，节点间就会发起一场投票，选举出新的领导者。这次选举被赋予一个全序且单调递增的纪元编号。如果出现两个不同时代的领导者，则以更高纪元编号的领导为主。
在每轮选举中，参选者如果要赢得选举，当选领导者，必须获得法定人数**（quorum）** 的选票。通常，会约定法定人数为超过半数以上，举例来说：假设总共有 N 张投票， 大于等于 N/2 + 1 张投票就算是半数以上了 。
共识的局限性
共识对于集群节点数的限制
多数派共识算法的核心是少数服从多数，获得投票多的节点胜出。这对于集群节点数有以下限制：
- 集群中最多可以容忍半数以下的节点出现故障。因为，一旦故障节点数达到半数，则无法在选举中获得半数以上投票。举例来说：如果集群有 3 个节点，最多允许 1 个节点出现故障；如果集群中有 5 个节点，最多允许 2 个节点出现故障。
- 集群的节点数一般要求是奇数。如果集群节点数为偶数，就很有可能在选主时出现某两个节点均获得半数以上投票的情况，这种情况下就必须重新投票选举。
选举会影响性能
共识系统通常依靠超时来检测失效的节点。在网络延迟高度变化的环境中，特别是在地理上散布的系统中，经常发生一个节点由于暂时的网络问题，错误地认为领导者已经失效。虽然这种错误不会损害安全属性，但频繁的领导者选举会导致糟糕的性能表现，因系统最后可能花在权力倾扎上的时间要比花在建设性工作的多得多。
参考资料
- 《数据密集型应用系统设计》 - 这可能是目前最好的分布式存储书籍，强力推荐【进阶】
- Impossibility of Distributed Consensus with One Faulty Process - 论证了在一个异步系统中，即使只有一个进程出现了故障，也没有算法能保证达成共识。