什么是一致性
CAP Theorem
对于一个分布式系统，不能同时满足一下三点：
一致性（Consistency）
可用性（Availability）
-
分区容错性（Partition Tolerance）
image.png
弱一致性
最终一致性
DNS(Domain Name System)
Gossip(Cassandra的通信协议)
强一致性
同步
Paxos
Raft(multi-paxos)
ZAB(multi-poxos)
明确问题
数据不能存在单点上
分布式系统对fault tolorence的一般解决方案是state machine replication
paxos其实是一个共识算法。系统的最终一致性，不仅需要达到共识，还会取决于client的行为。
强一致性算法--主从同步
主从同步复制
1.Master接受写请求
2.Master复制日志至slave
3.Master等待，直到所有从库返回
问题
一个节点失败，Master阻塞，导致整个集群不可用，保证了一致性，可用性却大大降低。
强一致性算法--多数派
** 基本思想**
每次写都保证写入大于N/2个节点，每次读保证从大于N/2个节点中读
问题：
在并发环境下，无法保证系统正确性，顺序非常重要
强一致性算法--Paxos
Lesile Lamport，Latex的发明人为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没人愿意将自己的全部时间和精力放在这种事上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。
- Paxos
- Basic Paxos
- Multi Paxos
- Fast Paxos
角色介绍：
<u>Client</u>: 系统外部角色，请求发起者。像民众。
<u>Proposer</u>: 接受Client请求，向集群提出提议（propose）。并在冲突发生时，起到冲突调节的作用。像议员，替民众提出议案。
<u>Acceptor(Voter)</u>: 提议投票和接收者，只有在形成法定人数（Quorum,一般即为majority多数派）时，提议才会最终被接受。像国会。
<u>Learner</u>：提议接受者，backup，备份，对集群一致性没什么影响。像记录员。
步骤、阶段（phases）:
1.Phase 1a:Prepare proposer提供一个提案，编号为N，此N大于这个proposer之前提出提案编号，请求acceptors的quorum接受。
2.Phase 1b:Promise 如果N大于此acceptor之前接受的任何提案编号则接受，否则拒绝。
3.Phase 2a:Accept 如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N，以及提案内容。
4.Phase 2b:Accepted 如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。
基本流程
部分节点失败，但达到了Quoroms
Proposer失败
潜在问题:
活锁（liveness）或dueling
Basic Paxos的问题难实现、效率低（2轮RPC）、活锁
Multi Paxos：新概念，Leader：唯一的proposer，所有请求都需经过此Leader。
Multi Paxos
基本流程
**减少角色**，进一步简化
强一致性算法--Raft
<u>划分成三个子问题</u>：
Leader Election
Log Replication
Safety
<u>重定义角色</u>：
- Leader
- Follower
- Candidate
原理动画：http://thesecretlivesofdata.com/raft/
一致性并不代表完全正确性！三个可能结果：成功，失败，unknown
强一致性算法--ZAB
基本与raft相同。在一些名词的叫法上有些区别：如ZAB将某一个leader的周期称为epoch，而raft则称为term。实现上也有些许不同：如raft保证日志连续性，心跳方向为leader至follower，ZAB则相反。
