关于我们:
梧桐数据库团队本次为大家带来知识分享系列的第一期:
分布式一致性算法 1. Paxos算法
什么是分布式一致性
分布式一致性是分布式系统中的一个核心概念，它涉及到在多个计算机节点之间保持数据的一致性。在分布式系统中，数据可能会被复制到多个节点上，以提高系统的可用性和性能。然而，这也带来了数据一致性的问题，因为对一个节点上的数据进行更新后，需要确保其他节点上的数据也得到相应的更新，以保持数据的一致性。
Paxos算法
Paxos算法是Lamport提出的一种基于消息传递的分布式一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一，现在绝大多数一致性算法都是基于Paxos算法思想为基础改进和适配各自的业务场景。
算法描述
三个角色:
Proposer 提案者/ 请求发起 (类似立法的法官 提出一个议题提案)
提案者负责提出提案 (Proposal)，Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。所谓提案的value，在实际项目中可以是任何操作，比如“将A的值从0改为1”，Paxos 协议中统一将这些操作抽象为value。Proposer可以有多个，不同的Proposer可以提出不同的甚至矛盾的value，比如提案者A提议“将变量X设置为0”，另一个提案者B提议“将变量X设置为2”，但对同一轮Paxose而言，最多只有一个value可以被批准。
Acceptor 接受者/请求响应处理 (类似议员，对提案表决)
接受者可以对提议者提出的提议进行投票表决，接受者之间是完全独立的。提议有超过半数的接受者投票批准即被选中，接受提案后提案里面的value就选定了。
Learner 学习者 (类似书记员, 记录最终的表决结果)
Learner 不参与选举，而是学习被批准的 value，在Paxos中，Learner主要参与相关的状态机同步流程。如果某个value需要获得超过半数的Acceptor 批准，Learner需要至少读取 N/2+1个Accpetor，最多读取 N个Acceptor的结果后，才能学习到一个通过的value。
Paxos 两阶段决议机制
两个阶段:
一. Prepare 准备阶段 ： proposer向Acceptor发送请求检查服务状态。
Proposer生成全局唯一且递增的提案编号N，向所有Acceptor发送Prepare请求，这里无需携带提案内容，只携带提案编号即可。
Acceptor收到Prepare请求后，有两种情况：
- 如果Acceptor首次接收Prepare请求, 设置MaxN=N， 同时响应ok
- 如果Acceptor不是首次接收Prepare请求，则：若请求过来的提案编号N小于等于上次持久化的提案编号ResN，则不响应或者响应error。若请求过来的提案编号N大于上次持久化的提案编号MaxN, 则更新MaxN=N，同时给出响应。响应的结果也有两种: 如果这个Acceptor此前没有接受过提案，只返回ok，并承诺不再回复小于N的提案; 如果这个Acceptor此前接收过提案，则返回ok和上次接受的提案编号AcceptN, 接收的提案AcceptV。
二. Acceptor处理阶段 ： proposer向Acceptor发送真正的请求, Acceptor根据请求返回内容，proposer收到的返回可能有多个结果，最终敲定为多数的那个结果，同时Learner对返回值进行学习记录。
为了方便描述，我们把 Phase 2 选举阶段继续拆分为 P2a、P2b 和 P2c：
P2a Proposer接收Accept消息，发送Accept，经过一段时间后，Proposer 收集到一些Prepare阶段的回复，有下列几种情况：
- 若回复数量 > 一半的 Acceptor 数量，且所有回复的 value 都为空时，则 Porposer 发出 accept 请求，并带上自己指定的提案value。
- 若回复数量 > 一半的 Acceptor 数量，且有的回复 value 不为空时，则 Porposer 发出 accept 请求，并挑选出回复中提案号最大的提案，取出提案的value作为自己的提案内容。
- 若回复数量 <= 一半的 Acceptor 数量时，则重新尝试更新生成更大的提案号N，再转到准备阶段执行。
P2b Acceptor 应答 Accept，Accpetor 收到 Accpet 请求后，判断：
- 若收到的提案号N >= MaxN（一般情况下是等于），则回复提交成功，并持久化N和value，接受提案；
- 若收到的 N < MaxN，则不回复或者回复提交失败，不接受提案。
P2c Proposer 统计投票
经过一段时间后，Proposer 会收集到一些 Accept 回复提交成功的情况，比如：
- 当回复数量 > 一半的 Acceptor 数量时，则表示提交 value 成功，此时可以发一个广播给所有的 Proposer、Learner，通知它们已提交的 value；
- 当回复数量 <= 一半的 Acceptor 数量时，则尝试更新生成更大的提案号，转到准备阶段执行。
- 当收到一条提交失败的回复时，则尝试更新生成更大的提案号，也会转到准备阶段执行。
学习阶段
Proposer收到多数Acceptor的Accept后，决议形成，将形成的决议发送给所有Learner，Learner进行学习。至此对"提议"达成了一致
存在的问题:
效率比较低，每个提案都要经过两阶段，对消息频繁的场景，比如消息队列，很不友好。这个问题就引出了一些改进的思路，比如， 在一次请求中 带有多个提案，Acceptor同时对这些提案进行返回； 或者可以在Accept阶段同时完成Prepare的服务可用性验证。
下一篇文章我们将介绍，paxos的一种改进且广泛使用的分布式一致性算法: raft算法
本文参考资料:
