CNDBA社区
1 ACID & CAP
1.1 ACID 原则(内部一致性)
ACID 是指数据库管理系统在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：
- 原子性（atomicity）
- 一致性（consistency）
- 隔离性（isolation）
- 持久性（durability）
数据库 ACID 的一致性，又称之为内部一致性。事务开始前和结束后，数据库的完整性约束没有被破坏 。比如 A 向 B 转账，不可能 A 扣了钱，B 却没收到。
1.2 CAP 理论（外部一致性）
来自Berkerly的Eric Brewer教授提出了一个著名的CAP理论：一致性（Consistency），可用性（Availability）以及分区容忍性（Partition tolerance）三者不能同时满足。
- 一致性（Consistency）：对某个指定的客户端来说，读操作能返回最新的写操作。对于数据分布在不同节点上的数据上来说，如果在某个节点更新了数据，那么在其他节点如果都能读取到这个最新的数据，那么就称为强一致，如果有某个节点没有读取到，那就是分布式不一致；
- 可用性（Availability）：非故障的节点在合理的时间内返回合理的响应(不是错误和超时的响应)。可用性的两个关键一个是合理的时间，一个是合理的响应。合理的时间指的是请求不能无限被阻塞，应该在合理的时间给出返回。合理的响应指的是系统应该明确返回结果并且结果是正确的，这里的正确指的是比如应该返回50，而不是返回40。
- 分区容忍性（Partition tolerance）：当出现网络分区后，系统能够继续工作。打个比方，这里个集群有多台机器，有台机器网络出现了问题，但是这个集群仍然可以正常工作。
分布式 CAP 的一致性，也称之为外部一致性。在分布式系统中，写操作后再读，就必须返回写入的值。比如分布式数据库A、B、C，A 中写入数据 hello，写完马上读 B 和 C，就一定要读出 hello，读出来我们就称之为符合一致性。
两者区别，内部一致性注重于事务前后数据的完整性，而外部一致性则注重于读写数据值是否一致。
2 一致性
2.1 ACID事务一致性
2PC、3PC协议使基于分布式系统架构下的所有节点在进行事务提交时保持一致性而设计的算法。
ACID 一致性是指分布式事务的ACID中的C, 一致性，在事务开始之前和事务结束以后，数据库的完整性没有被破坏。这里的一致性是指逻辑上的一致性，即所有操作是符合现实当中的期望的， 比如丢失修改、不可重复读、脏读、幻读。
NewSQL 分布式数据库中的 协议（ 2PC / 3PC）和 选主算法（Paxos / Raft） 说明
https://www.cndba.cn/dave/article/4580
2.2 多副本的一致性
一致性协议大多使用了Quorum机制，但仅仅有Quorum(R+W>N)机制是保证不了一致性的。
Paxos、Raft 协议用于保证同一个数据分片的多个副本之间的数据一致性。当这些副本分布到不同的数据中心时，这个需求尤其强烈。通过Paxos算法，是可以解决外部的一致性。
3 Paxos和 Raft
3.1 Paxos算法
Paxos算法是莱斯利·兰伯特（英语：Leslie Lamport，LaTeX中的“La”）于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。
3.1.1 basic paxos
basic paxos的协议更复杂，且相对效率较低。所以现在所有的和paxos有关的协议，一定是基于multi-paxos来实现的。
basic paxos的角色分为 proposers，acceptors，和 learners（允许身兼数职）。
- proposers 提出提案，提案信息包括提案编号和提议的 value；
- acceptor 收到提案后可以接受（accept）提案，若提案获得多数派（majority）的 acceptors 的接受，则称该提案被批准（chosen）；
- learners 只能“学习”被批准的提案。
3.1.2 multi-paxos
Paxos的典型部署需要一组连续的被接受的值（value），作为应用到一个分布式状态机的一组命令。如果每个命令都通过一个Basic Paxos算法实例来达到一致，会产生大量开销。如果Leader是相对稳定不变的，第1阶段就变得不必要。 这样，系统可以在接下来的Paxos算法实例中，跳过的第1阶段，直接使用同样的Leader。
为了实现这一目的，在同一个Leader执行每轮Paxos算法时，提案编号 I 每次递增一个值，并与每个值一起发送。Multi-Paxos在没有故障发生时，将消息延迟(从propose阶段到learn阶段)从4次延迟降低为2次延迟。
使用同一个的提案编号计数器，因为执行实例使用的都是同一个的提案编号计数器，这样它承诺不再通过小于 n 的提案，应该可以应用在所有执行实例上，而不影响正确性。
prepare阶段，acceptor承诺不再回复小于n的提案。这是acceptor的职责。只要满足这个条件，paxos正确性就得到了保证。
3.2 Raft
由于Paxos难以理解，所以才有了Raft。Raft 以可理解性和易于实现为目标。
- Leader选举（Leader election）
- 日志同步（Log replication）
- 安全性（Safety）
- 日志压缩（Log compaction）
- 成员变更（Membership change）
4 Raft 对比 multi-paxos
4.1 两者相同之处
（1） 都是共识算法，引用场景以及所解决的问题是一致的。
（2） 两者都采用“多数派”决策的思想进行协商。
（3） 两者都能友好的支持容错。
4.2 两者不同之处
（1） Raft引入强Leader模型，规避了Basic Paxos的活锁的问题，Multi Paxos也仅仅降低了活锁的概率。
（2） 可用性，Raft引入强Leader，自然也导致了可用性的降低，在Leader选举期间，Raft将不可用。而Multi Paxos尽管也引入Leader，但是当Leader故障时，客户端访问另一个Leader即可，服务仍然是可用的。
（3） 协商性能，Basic Paxos加上提交操作（learn阶段或者comfirm请求）固定需要三个阶段（Prepare+Accept+Comfirm）才能提交一个提案，Multi Paxos在大多数情况下优化成两阶段（Accept+Confirm）提交，但是达到两阶段提交的条件仍然是需要进行Prepare阶段。而Raft抽象出选举阶段（类比Prepare阶段），并通过心跳机制替代了提交阶段（类比Confirm），实现了真正一阶段提交。
（4） 日志连续性，Paxos允许乱序提交，同样允许存在空洞日志。而Raft通过Leader严格规定了日志项的连续性。换句话说，Paxos只保证了每个提案（日志项）达成共识的安全性，而Raft还保证了日志项的连续性，这一特性隐含了两个成员之间，相同日志索引且term相同，那么该日志项之前所有日志项也必然相同。
（4） 非事务请求，Multi Paxos尽管可以让Leader为每个提案（日志项）记录Confirm日志，但是对于未记录这一Confirm日志的提案，必须重新走一遍Paxos流程，才能知道该提案是否已达成共识。而Raft在日志连续的特性上，也要求了日志项提交的顺序。因此，Raft只需要明确committedIndex，即可推测在此之前所有日志项都已达成共识。
（5） 日志压缩，Paxos没有明确这一细节，但是在Paxos的工程实现中往往也会采用类似Raft提到的快照方式，进行日志压缩。
（6） 日志存储，Paxos并不要求每个成员拥有完整的数据，而Raft要求成员加入集群时先和Leader完成数据对齐。
（7） 崩溃恢复，因为Paxos的灵活性，这一点在Paxos中并没有那么重要，由于每个成员的对等性，成员崩溃后重启即可。而Raft成员崩溃后，再加入集群时，需要以Leader的数据为基准恢复数据，然后才可加入集群。
综上所述，两者各存优劣。
- Paxos，更加灵活，可用性更好，但是协商效率更低（活锁、三阶段）
- Raft，可用性降低，协商效率更好，另外Raft算法更加完整，对非事务请求、日志压缩、崩溃恢复等模块都有明确的实现标准。
