| title | date | categories | tags | permalink | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
分布式共识 |
2024-05-06 23:34:08 -0700 |
|
|
/pages/4ce1fe4e/ |
分布式系统最重要的抽象之一就是共识（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 是关于共识不可能性的重要理论结果，但现实中的分布式系统通常是可以达成共识的。
共识意味着就某一项提议，所有节点做出一致的决定，而且决定不可撤销。通过逐一分析，事实证明，多个广泛的问题最终都可以归结为共识，并且彼此等价（这就意味着，如果找到其中一个解决方案，就可以比较容易地将其转换为其他问题的解决方案）。这些等价的问题包括：
- 可线性化的比较－设置寄存器 - 寄存器需要根据当前值是否等于输入的参数， 来自动决定接下来是否应该设置新值。
- 原子事务提交 - 数据库需要决定是否提交或中止分布式事务。
- 全序广播 - 消息系统要决定以何种顺序发送消息。
- 锁与租约 - 当多个客户端争抢锁或租约时，要决定其中哪一个成功。
- 成员／协调服务 - 对于失败检测器（例如超时机制），系统要决定节点的存活状态（例如基于会i舌超时）。
- 唯一性约束 - 当多个事务在相同的主键上试图井发创建冲突资源时，约束条件要决定哪一个被允许，哪些违反约束因而必须失败。
如果系统只存在一个节点，或者愿意把所有决策功能都委托给某一个节点，那么事情就变得很简单。这和主从复制数据库的情形是一样的，即由主节点负责所有的决策事宜，正因如此，这样的数据库可以提供线性化操作、唯一性约束、完全有序的复制日志等。
然而，如果唯一的主节点发生故障，或者出现网络中断而导致主节点不可达，这样的系统就会陷入停顿状态。有以下三种基本思路来处理这种情况：
- 系统服务停止，井等待主节点恢复。许多XA I JTA 事务协调者采用了该方式。本质上，这种方怯并没有完全解决共识问题，因为它不满足终止性条件，试想如果主节点没法恢复，则系统就会永远处于停顿状态。
- 人为介入来选择新的主节点，并重新配置系统使之生效。许多关系数据库都采用这种方怯。本质上它引入了一种“上帝旨意” 的共识， 即在计算机系统之外由人 类来决定最终命运。故障切换的速度完全取决于人类的操作，通常比计算机慢。
- 采用算i法来自动选择新的主节点。这需要一个共识算法，我们建议采用那些经过验证的共识系统来确保正确处理各种网络异常。
共识算法选举主节点的过程如同投票选举领导者（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 - 论证了在一个异步系统中，即使只有一个进程出现了故障，也没有算法能保证达成共识。