参考: https://www.bilibili.com/video/av21667358

什么是分布式系统？

由多台设备组成的一个系统叫做分布式系统。

什么是一致性？

CAP理论

对于一个分布式系统，不能同时满足以下三点：

• 一致性(Consistency)
• 可用性(Availability)
• 分区容错性(Partition Tolerance)

一致性模型

• 弱一致性
  • 最终一致性
    • DNS(Domain Name System)
    • Gossip(Cassandra的通信协议)
• 强一致性
  • 同步
  • Paxos
  • Raft(multi-paxos)
  • ZAB(multi-paxos)

最终一致性

例如：

映射域名test.yangzhang.edu到11.11.11.11，这个操作是对这个分布式系统中一台设备的操作，不会立即被整个分布式系统同步，所以当你想立即访问你的域名时，可能会出现访问不到的情况，但过了一段时间之后，一定可以访问到那个域名，这种情况被称为最终一致性。

首先——明确问题

数据不能存在单点上。
分布式系统对 fault tolorance 的一般解决方案是 state machine replication。
其实强一致性算法的本质就是 state machine replication 的共识算法。
(系统的最终一致性，不仅需要达成共识，还会取决于 client 的行为)
state machine replication: 通过存/读 log 的方式来完成一致性

强一致性算法——主从同步

1. Master接受写请求
2. Master复制日志到slave
3. Master等待，直到所有slave返回
   

问题：
一个节点失败，导致Master阻塞，整个集群不可用，保证了一致性，但可用性缺大大降低。

强一致性算法——多数派

基本思想：
每次写都保证写入大于 N/2 个节点，每次读都保证从大于 N/2 个节点中读。
问题：
在高并发的场景下，例如某台设备input Inc5(增加5)，另一台设备input Set0，会导致某些设备上的 log 顺序不一致。

强一致性算法——Paxos

发明者：Lesile Lamport
为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没有人愿意将自己的全部时间和精力放在这种事。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。

• Paxos
  • Basic Paxos
  • Multi Paxos
  • Fast Paxos

强一致性算法——Basic Paxos

• 角色介绍：
  • Client：系统外部角色，请求发起者。比作民众。
  • Proposer：接受Client请求，向集群提出提议(propose)。并在冲突发生时，起到冲突调节的作用。比作议员，替民众提出议案。(在Basic中是多个，在Multi中是单个)
  • Accpetor(Voter)：提议投票和接收者，只有在形成法定人数(Qunrum = (n+1)/2，一般即为majority多数派)时，提议才会最终被接受。比作国会。
  • Learner：提议接受者，backup，备份，对集群一致性没什么影响。比作记录员。

基本流程：

1. Client民众 对 Proposer议员 发出一个写请求
2. Proposer议员 对 Acceptor1、2、3 发出请求：请求采用方案1(1是编号，此时只对Acceptor发送编号，不发生方案的实际内容)
3. Acceptor1、2、3 响应 Proposer 表示同意(一共有3个 Acceptor，其中有3个 Acceptor表示同意，同意的数量大于等于 Qunrum(大多数))
4. Proposer议员 对 Acceptor1、2、3 发送方案1的实际内容
5. Acceptor1、2、3 相应 Proposer 表示同意，并告诉 Learner记录员 记下这个方案(此时才正式写入log)
6. Learner 将 response 返回给 client
   

部分节点失败，但达到了Quorum：

失败的方案1：

在方案1没有完成记录之前，方案2到来，Acceptor将直接放弃方案1，只相应编号最大的方案。

潜在问题：活锁

每个方案在被记录之前，都有新的方案提出，导致没有任何方案记录，没有response，产生活锁。

Basic Paxos 总结：

1. 难实现
2. 效率低(2轮RPC)
3. 活锁

强一致性算法——Multi Paxos

引入新的概念：Leader，唯一的Proposer，所有写请求都需要经过此Leader。

基本流程：

1. Proposer 请求 Acceptor 成为 Leader
2. 达到Quorum数量的 Acceptor 响应(同意)，此Proposer成为Leader
3. Client发出request给Leader
4. 第N号Leader(Proposer)，发出编号I的方案和方案内容给Acceptor
5. Acceptor响应Leader，并通知Learner 写入log
6. Client发出request给Leader
7. 第N号Leader(Proposer)，发出编号I+1的方案和方案内容给Acceptor
8. Acceptor响应Leader，并通知Learner 写入log
   ......
   

Multi Paxos总结：

1. 解决活锁：只有一个Leader，由Leader来决定方案顺序
2. 提高效率

强一致性算法——Raft

• Raft
  • 划分成三个子问题：
    • Leader Election
    • Log Replication
    • Safety
  • 重定义角色：
    • Leader
    • Follower
    • Candidate(只存在一段时间)
  • 原理动画解释：http://thesecretlivesofdata.com/raft/
  • 场景测试：https://raft.github.io/