分布式一致性详解
什么是一致性
在分布式系统中，计算、存储分布在各个节点上，节点可能分布在各个区域甚至是国家。
一致性就是数据保持一致，在分布式系统中，可以理解为多个节点中数据的值是一致的。
CAP theorem
站内引用： {%post_link 工作/410_分布式/分布式一致性/CAP原理和BASE思想 CAP %}
分区容忍性：
举个简单的例子，一个服务共有5个节点分别部署在中国和美国，其中中国2个节点，美国3个节点。现在中美海底电缆断了，这两个分区无法互相访问，但是可以独立提供服务给外部。
此时保证一致性可以将某一个分区关闭服务，也可以保证可用性但此时数据可能会不一致，用户本来访问中国节点，出现分区之后只能访问美国节点，此时数据有可能不一致。
一致性模型
弱一致性
最终一致性
典型应用场景
- DNS(Domain Name System)
- Gossip(Cassandra的通信协议)
强一致性
-
同步
-
Paxos
-
Raft
-
ZAB
强一致性算法
首先，要明确问题
数据要保证是安全的容错的，就不能存在单点上。
分布式系统对fault tolorence的一般解决方案是state machine replication。
state machine 可以简单里理解为一个函数或者方程，本身有初始状态，比如0，有input或者log将这个值增加5，这个值最终状态就是5。分布式系统希望通过log的形式往节点上写操作日志，分布式系统的设计是把这一些log复制到其他各个节点上，保证这些log不存在单点上。类似mysql的undo/redo log。
其实本篇要讨论的准确的说，应该是state machine replication的共识(consensus)算法。
paxos其实是一个共识算法。系统的最终一致性，不仅需要达成共识，还会取决于client的行为。
主从同步
主从同步复制
- master接受写请求
- master复制日志到slave
- master等待，直到所有从库返回
问题：
一个节点失败，master阻塞，导致整个集群不可用，保证了一致性，可用性却大大降低。
多数派
基本想法：
多数派！
每次写都保证写入大于 N/2 个节点，每次读保证从大于 N/2 个节点中读。
问题：
在并发环境下，无法保证系统正确性，顺序非常重要
Paxos
Paxos算法是Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。
Paxos由Lamport于1998年在《The Part-Time Parliament》论文中首次公开，最初的描述使用希腊的一个小岛Paxos作为比喻，描述了Paxos小岛中通过决议的流程，并以此命名这个算法，但是这个描述理解起来比较有挑战性。后来在2001年，Lamport觉得同行不能理解他的幽默感，于是重新发表了朴实的算法描述版本《Paxos Made Simple》。
为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没有人愿意将自己的全部时间和精力放在这种事。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。
自Paxos问世以来就持续垄断了分布式一致性算法，Paxos这个名词几乎等同于分布式一致性。Google的很多大型分布式系统都采用了Paxos算法来解决分布式一致性问题，如Chubby、Megastore以及Spanner等。开源的ZooKeeper，以及MySQL 5.7推出的用来取代传统的主从复制的MySQL Group Replication等纷纷采用Paxos算法解决分布式一致性问题。
然而，Paxos的最大特点就是难，不仅难以理解，更难以实现。
分类：
- Basic Paxos
- Multi Paxos
- Fast Paxos
Basic Paxos
角色介绍
-
Client 客户端 产生议题者(群众)
系统外部角色，请求发起者，像民众。
-
Proposer 提案者
接受Client请求，向集群提出提议(propose)。并在冲突发生时，起到冲突调节的作用。像议员，替民众提出议案。
acceptor只是起到投票的作用，返回通过或者不通过，由proposer决定是否符合多数派，要不要进行到下一个阶段
谁改变了数据谁就是proposer，proposer可以理解成业务机器，acceptor是数据集群中的节点，代表分布式存储的独立存储节点
多数派用在两个场景，第一次是决定proposer，第二次是将日志写入learner后决定是否commit
-
Acceptor(Voter) 决策者
提议投票和接受者，只有在形成法定人数(Quorum，一般即为majority 多数派)时，提议才会最终被接受。像国会。
-
Learner 最终决策学习者（群众），和Client类似，不参与一致性的解决，只负责记录。
提议接受者，backup备份，对集群一致性没什么影响。像记录员。
在多副本状态机中，每个副本同时具有Proposer、Acceptor、Learner三种角色。
client 客户端
proposer 业务处理节点
acceptor 数据节点，参与投票，是达成共识最重要的数据节点
learner 也是数据备份节点，不参与投票，类似slave，提供读服务提高并发
各角色均是节点，每个节点也可能同时扮演多个角色
提案通过，proposer会将日志写入acceptor数据节点，acceptor再将日志写入learner数据备份节点，注意此时数据内容还没有被commit，只有当acceptor确认多数learner已经写入日志才会commit
基本流程
步骤、阶段(phases)：
-
Phase 1a: Prepare
proposer提出一个提案，编号为N，此N大于这个proposer之前提出的提案编号。请求acceptors的quorum接受。
-
Phase 1b: Promise
如果N大于此acceptor之前接受的任何提案编号则接受，否则拒绝。
-
Phase 2a: Accept
如果达到了多数派，proposer会发出accept请求，此请求包含提案编号N，以及提案内容。
-
Phase 2b: Accepted
如果此acceptor在此期间没有收到任何编号大于N的提案，则接受此提案内容，否则忽略。
两个阶段分别对应两次rpc调用，第一次是提案，第二次是提案内容
看来来理解
-
正常流程
跟现实中区别是，acceptor只关系提案是否冲突而不关心提案的内容。
-
部分节点失败，但达到了Quorum
-
Proposer失败
比如redis里的哨兵leader死了一个需要重新换一个
Basic潜在问题，活锁(liveness)或dueling
站内引用：{%post_link 工作/200_编程语言/java/并发编程/活锁 活锁 %}
Multi Paxos
Basic Paxos的问题：
- 难实现 角色很多
- 效率低 2轮RPC
- 活锁
Multi Paxos
新概念 Leader:唯一的proposer，所有请求都需经过此Leader，有点像主从架构，中心节点，zk里的master节点
第一轮RPC干的事就是决定使用哪个proposer的提案，现在不需要了（竞选总统阶段除外），而且避免了活锁
基本流程
只有这一个proposer也就是leader，不会有人跟他抢着去提案
Accept!(N, I, Vm) N任总统，提案编号I， 提案内容Vm
竞选完总统后接下来的请求就不用再竞选了，原来的两轮rpc现在只需要一轮rpc就可以完成了，关键点在于只有唯一一个proposer。
现在更像现实中的分布式系统了，主从节点，下面是一个Leader和两个Slavor
Raft
Raft是一个实现分布式一致性的协议
Paxos很难理解也很难实现，Raft应运而生。
raft可以简单理解成简化版本的Multi Paxos，也是为了解决多副本状态机复制的问题。它把状态机复制日志这个问题划分成了3个子问题，只要解决这3个子问题就能达成共识。
划分成三个子问题
- Leader Election 选主
- Log Replication 日志复制 log同步到其他节点上，两个阶段 写入日志 commit
- Safety 怎么保证所有的操作在集群中一直是一致的，leader失败了是怎样的，发生分区了是怎样的。
重定义角色
- Leader
- Follower
- Candidate 临时的橘色，只有在Leader宕机了，Follower要竞选Leader时才会起作用，这时某个Follower想要竞选，可以临时充当Candidate角色，期待成为下一个Leader
原理动画解释
split vote 选举时，两个follower的timeout同时到期，会再举行一轮选举，这两个节点采用随机的timeout
场景测试
注意：一致性并不一定代表完全正确性
三个可能结果：成功，失败，unknown
Raft 5 nodes example:
Client写请求，Leader向followers同步日志，此时集群中有3个节点失败，2个节点存活，结果是？
unkown，开始是两个节点的log处于未提交状态，当3个节点复活后，log会继续提交。
Client写请求，Leader向followers同步日志，此时集群中有2个节点失败，3个节点存活，结果是？
unkown，开始是两个节点的log处于未提交状态，3个节点提交，另两个节点复活后悔将未提交的抛弃，使用其他3个节点已同步的数据复制。
所以需要client决定如何处理。
ZAB
基本与raft相同，是zk的共识算法
在一些名词的叫法上有些区别：如ZAB将某一个leader的周期称为epoch，而raft则称之为term。
实现上也有些许不同：如raft保证日志连续性，心跳方向为leader至follower。ZAB则相反。
项目实践
在性能测试上etcd已经超过了ZK，最主要的应该是一致性算法的优势，zk基于从paxos改进而来的zab，而etcd基于raft，k8s现在都用etcd管理各种状态