20.1.1. Paxos
Paxos算法解决的问题是一个分布式系统如何就某个值（决议）达成一致。一个典型的场景是， 在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么 他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执 行一个"一致性算法"以保证每个节点看到的指令一致。zookeeper使用的zab算法是该算法的 一个实现。在Paxos算法中，有三种角色：Proposer，Acceptor，Learners
Paxos 三种角色：Proposer, Acceptor, Learners
Proposer：
只要Proposer发的提案被半数以上Acceptor接受，Proposer就认为该提案里的value被选定 了。
Acceptor：
只要Acceptor接受了某个提案，Acceptor就认为该提案里的value被选定了。
Learner：
Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定
Paxos算法分为两个阶段。具体如下：
阶段一（准leader确定）:
（a）Proposer选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求。
（b）如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的 所有Prepare请求的编号，那么它就会将它已经接受过的编号最大的提案（如果有的话）作为响 应反馈给Proposer，同时该Acceptor承诺不再接受任何编号小于N的提案。
阶段二deader确认）：
（a）如果Proposer收到半数以上Acceptor对其发出的编号为N的Prepare请求的响应，那么它 就会发送一个针对［N,V］提案的Accept请求给半数以上的Acceptor。注意：V就是收到的响应中 编号最大的提案的value，如果响应中不包含任何提案，那么V就由Proposer自己决定。
（b）如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号 大于N的Prepare请求做出过响应，它就接受该提案。
20.1.2. Zab
ZAB（ ZooKeeper Atomic Broadcast , ZooKeeper原子消息广播协议）协议包括两种基本的模 式：崩溃恢复和消息广播
1. 当整个服务框架在启动过程中，或是当Leader服务器出现网络中断崩溃退出与重启等异常情 况时，ZAB就会进入恢复模式并选举产生新的Leader服务器。
2. 当选举产生了新的Leader月艮务器，同时集群中已经有过半的机器与该Leader服务器完成了 状态同步之后，ZAB协议就会退出崩溃恢复模式，进入消息广播模式。
3. 当有新的服务器加入到集群中去，如果此时集群中已经存在一个Leader月艮务器在负责进行消 息广播，那么新加入的月艮务器会自动进入数据恢复模式，找到Leader服务器，并与其进行数 据同步，然后一起参与到消息广播流程中去。
以上其实大致经历了三个步骤：
1. 崩溃恢复:主要就是Leader选举过程
2. 数据同步:Leader服务器与其他服务器进行数据同步
3. 消息广播:Leader服务器将数据发送给其他服务器
说明：zookeeper章节对该协议有详细描述。
20.1.3. Raft
与Paxos不同Raft强调的是易懂（Understandability），Raft和Paxos 一样只要保证n/2+1节 点正常就能够提供服务；raft把算法流程分为三个子问题：选举（Leader election）、日志复制 （Log replication）.安全性（Safety）三个子问题。
20.1.3.1. 角色
Raft把集群中的节点分为三种状态：Leader、Follower x Candidate，理所当然每种状态负 责的任务也是不一样的，Raft运行时提供服务的时候只存在Leader与Follower两种状态
Leader （领导者-日志管理）
负责日志的同步管理，处理来自客户端的请求，与Follower保持这heartBeat的联系；
Follower （追随者日志同步）
刚启动时所有节点为Follower状态，响应Leader的日志同步请求，响应Candidate的请求， 把请求到Follower的事务转发给Leader；
Candidate （候选者负责选票）
负责选举投票，Raft刚启动时由一个节点从Follower转为Candidate发起选举，选举出 Leader后从 Candidate 转为 Leader状态；
20.1.3.2. Term （任期）
在Raft中使用了一个可以理解为周期（第几届、任期）的概念，用Term作为一个周期，每 个Term都是一个连续递增的编号，每一轮选举都是一个Term周期，在一个Term中只能产生一 个Leader；当某节点收到的请求中Term比当前Term小时则拒绝该请求。
20.1.3.3. 选举（Election）
选举定时器
Raft的选举由定时器来触发，每个节点的选举定时器时间都是不一样的，开始时状态都为 Follower某个节点定时器触发选举后Term递增，状态由Follower转为Candidate，向其他节点 发起RequestVote RPC请求，这时候有三种可能的情况发生：
1:该RequestVote请求接收到n/2+1 （过半数）个节点的投票，从Candidate转为Leader， 向其他节点发送heartBeat以保持Leader的正常运转。
2：在此期间如果收到其他节点发送过来的AppendEntries RPC请求，如该节点的Term大 则当前节点转为Follower，否则保持Candidate拒绝该请求。
3： Election timeout发生则Term递增，重新发起选举
在一个Term期间每个节点只能投票一次，所以当有多个Candidate存在时就会出现每个 Candidate发起的选举都存在接收到的投票数都不过半的问题，这时每个Candidate都将Term 递增、重启定时器并重新发起选举，由于每个节点中定时器的时间都是随机的，所以就不会多次 存在有多个Candidate同时发起投票的问题。
在Raft中当接收到客户端的日志（事务请求）后先把该日志追加到本地的Log中，然后通过 heartbeat把该Entry同步给其他Follower，Follower接收到日志后记录日志然后向Leader发送 ACK，当Leader收到大多数（n/2+1）Follower的ACK信息后将该日志设置为已提交并追加到 本地磁盘中，通知客户端并在下个heartbeat中Leader将通知所有的Follower将该日志存储在 自己的本地磁盘中。
20.1.3.4. 安全性（Safety）
安全性是用于保证每个节点都执行相同序列的安全机制如当某个Follower在当前Leader commit Log时变得不可用了，稍后可能该Follower又会倍选举为Leader，这时新Leader可能会用新的 Log覆盖先前已committed的Log，这就是导致节点执行不同序列；Safety就是用于保证选举出 来的Leader —定包含先前commited Log的机制；
选举安全性（Election Safety）:每个Term只能选举出一个Leader
Leader完整性（Leader Completeness）:这里所说的完整性是指Leader日志的完整性 Raft在选举阶段就使用Term的判断用于保证完整性：当请求投票的该Candidate的Term较大 或Term相同Index更大则投票，该节点将容易变成leader。
20.1.3.5. raft协议和zab协议区别
相同点
- 采用quorum来确定整个系统的一致性，这个quorum 一般实现是集群中半数以上的服务器， , zookeeper里还提供了带权重的quorum实现.
,都由leader来发起写操作.
- 都采用心跳检测存活性
, leader election都采用先到先得的投票方式
不同点
，zab用的是epoch和count的组合来唯一表示一个值，而raft用的是term和index
，zab的follower在投票给一个leader之前必须和leader的日志达成一致，而raft的follower 贝帽单地说是谁的term高就投票给谁
，raft协议的心跳是从leader到follower,而zab协议则相反
，raft协议数据只有单向地从leader到follower(成为leader的条件之一就是拥有最新的log), 而zab协议在discovery阶段，一个prospective leader需要将自己的log更新为quorum里面 最新的log,然后才好在synchronization阶段将quorum里的其他机器的log都同步到一致.
20.1.4. NWR
N：在分布式存储系统中,有多少份备份数据
W：代表一次成功的更新操作要求至少有w份数据写入成功
R：代表一次成功的读数据操作要求至少有R份数据成功读取
NWR值的不同组合会产生不同的一致性效果，当W+R>N的时候，整个系统对于客户端来讲能保 证强一致性。而如果R+W<=N,则无法保证数据的强一致性。以常见的N=3、W=2、R=2为例:
N=3，表示，任何一个对象都必须有三个副本(Replica)，W=2表示，对数据的修改操作 (Write)只需要在3个Replica中的2个上面完成就返回，R=2表示，从三个对象中要读取到2 个数据对象，才能返回。
20.1.5. Gossip
Gossip算法又被称为反熵(Anti-Entropy),熵是物理学上的一个概念，代表杂乱无章，而反熵 就是在杂乱无章中寻求一致，这充分说明了 Gossip的特点：在一个有界网络中，每个节点都随机
地与其他节点通信，经过一番杂乱无章的通信，最终所有节点的状态都会达成一致。每个节点可 能知道所有其他节点，也可能仅知道几个邻居节点，只要这些节可以通过网络连通，最终他们的 状态都是一致的，当然这也是疫情传播的特点。
20.1.6. 一致性 Hash
—致性哈希算法(Consistent Hashing Algorithm)是一种分布式算法，常用于负载均衡。 Memcached client也选择这种算法，解决将key-value均匀分配到众多Memcached server上 的问题。它可以取代传统的取模操作，解决了取模操作无法应对增删Memcached Server的问题 (增删server会导致同一个key,在get操作时分配不到数据真正存储的server，命中率会急剧下 降)。
20.1.6.1. 一致性 Hash 特性
- 平衡性(Balance):平衡性是指哈希的结果能够尽可能分布到所有的缓冲中去，这样可以使得 所有的缓冲空间都得到利用。
- 单调性(Monotonicity):单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中， 又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓 冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。容易看到，上面的简单求余算法 hash(object)%N难以满足单调性要求。
- 平滑性(Smoothness):平滑性是指缓存服务器的数目平滑改变和缓存对象的平滑改变是一致 的。
20.1.6.2. 一致性 Hash 原理
1.建构环形hash空间:
1. 考虑通常的hash算法都是将value映射到一个32为的key值，也即是0~2A32-1次方的 数值空间；我们可以将这个空间想象成一个首(0 )尾(2人32-1 )相接的圆环
2. 把需要缓存的内容(对象)映射到hash空间
2. 接下来考虑4个对象objectl ~object4，通过hash函数计算出的hash值key在环上的分 布
3. 把服务器(节点)映射到hash空间
3. Consistent hashing的基本思想就是将对象和cache都映射到同一个hash数值空间中，并 且使用相同的hash算法。一般的方法可以使用服务器(节点)机器的IP地址或者机器名作为 hash输入。
4. 把对象映射到服务节点
4.现在月艮务节点和对象都已经通过同一个hash算法映射到hash数值空间中了，首先确定对象 hash值在环上的位置，从此位置沿环顺时针"行走”，第一台遇到的服务器就是其应该定位 到的月服务器。
考察 cache 的变动
5. 通过 hash 然后求余的方法带来的最大问题就在于不能满足单调性，当 cache 有所变动时，
cache 会失效。
5.1 移除 cache：考虑假设 cache B 挂掉了，根据上面讲到的映射方法，这时受影响的将仅是
那些沿 cache B 逆时针遍历直到下一个 cache （
cache C ）之间的对象。
5.2 添加 cache：再考虑添加一台新的 cache D 的情况，这时受影响的将仅是那些沿 cache
D 逆时针遍历直到下一个 cache 之间的对象，将这些对象重新映射到 cache D 上即可。
虚拟节点
hash 算法并不是保证绝对的平衡，如果 cache 较少的话，对象并不能被均匀的映射到 cache 上，
为了解决这种情况， consistent hashing 引入了“虚拟节点”的概念，它可以如下定义：
虚拟节点（
virtual node ）是实际节点在 hash 空间的复制品（
replica ），一实际个节点对应了
若干个“虚拟节点”，这个对应个数也成为“复制个数”，“虚拟节点”在 hash 空间中以 hash
值排列。
仍以仅部署 cache A 和 cache C 的情况为例。现在我们引入虚拟节点，并设置“复制个数”为 2 ，
这就意味着一共会存在 4 个“虚拟节点”， cache A1, cache A2 代表了 cache A； cache C1,
cache C2 代表了 cache C 。此时，对象到“虚拟节点”的映射关系为：
objec1->cache A2 ； objec2->cache A1 ； objec3->cache C1 ； objec4->cache C2 ；
因此对象 object1 和 object2 都被映射到了 cache A 上，而 object3 和 object4 映射到了 cache
C 上；平衡性有了很大提高。
引入“虚拟节点”后，映射关系就从 { 对象 -> 节点 } 转换到了 { 对象 -> 虚拟节点 } 。查询物体所
在 cache 时的映射关系如下图 所示。
