叨絮
前面大致的熟悉了下zk,今天我们来看看看看分布式的一致性理论吧！
什么是分布式系统
我们前面说到 zookeeper是一个分布式协调服务，就是用来调节各种分布式系统中节点的作用，那么我们大部分使用zk的话 也是在分布式系统开发。所以我们来说说分布式系统开发
拿一个最简单的例子，就比如说我们的图书管理系统。之前的系统包含了所有的功能，比如用户注册登录、管理员功能、图书借阅管理等。这叫做集中式系统。也就是一个人干了好几件事。 后来随着功能的增多，用户量也越来越大。集中式系统维护太麻烦，拓展性也不好。于是就考虑着把这些功能分开。通俗的理解就是原本需要一个人干的事，现在分给n个人干，各自干各自的，最终取得和一个人干的效果一样。 稍微正规一点的定义就是：一个业务分拆多个子业务，部署在不同的服务器上。 然后通过一定的通信协议，能够让这些子业务之间相互通信。 既然分给了n个人，那就涉及到这些人的沟通交流协作问题。想要去解决这些问题，就需要先聊聊分布式系统中的CAP理论。
CAP理论
CAP原理指的是一个分布式系统最多只能同时满足一致性（Consistency）、可用性（Availability）和分区容错性（Partition tolerance）这三项中的两项。
这张图不知道你之前看到过没，如果你看过书或者是视频，这张图应该被列举了好几遍了。下面我不准备直接上来就对每一个特性进行概述。我们先从案例出发逐步过渡。
例子
首先我们看一张图。
现在网络中有两个节点N1和N2，他们之间网络可以连通，N1中有一个应用程序A，和一个数据库V，N2也有一个应用程序B2和一个数据库V。现在，A和B是分布式系统的两个部分，V是分布式系统的两个子数据库。
现在问题来了。突然有两个用户小明和小华分别同时访问了N1和N2。我们理想中的操作是下面这样的。
- 小明访问N1节点，小华访问N2节点。同时访问的。
- 小明把N1节点的数据V0变成了V1。
- N1节点一看自己的数据有变化，立马执行M操作，告诉了N2节点。
- 小华读取到的就是最新的数据。也是正确的数据。
上面这是一种最理想的情景。它满足了CAP理论的三个特性。现在我们看看如何来理解满足的这三个特性。
Consistency 一致性
一致性指的是所有节点在同一时间的数据完全一致。 对于一致性，也可以分为从客户端和服务端两个不同的视角来理解。
- 客户端
从客户端来看，一致性主要指的是多并发访问时更新过的数据如何获取的问题。也就是小明和小华同时访问，如何获取更新的最新的数据。
- 服务端
从服务端来看，则是更新如何分布到整个系统，以保证数据最终一致。也就是N1节点和N2节点如何通信保持数据的一致。对于一致性，一致的程度不同大体可以分为强、弱、最终一致性三类。
- 强一致性
对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。比如小明更新V0到V1，那么小华读取的时候也应该是V1。
- 弱一致性
如果能容忍后续的部分或者全部访问不到，则是弱一致性。比如小明更新VO到V1，可以容忍那么小华读取的时候是V0。
可用性
可用性指服务一直可用，而且是正常响应时间。就好比刚刚的N1和N2节点，不管什么时候访问，都可以正常的获取数据值。而不会出现问题。好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。 对于可用性来说就比较好理解了。
分区容错性
分区容错性指在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。就好比是N1节点和N2节点出现故障，但是依然可以很好地对外提供服务。 这个分区容错性也是很好理解。 在经过上面的分析中，在理想情况下，没有出现任何错误的时候，这三条应该都是满足的。但是天有不测风云。系统总是会出现各种各样的问题。下面来分析一下为什么说CAP理论只能满足两条。
验证CAP理论
既然系统总是会有错误，那我们就来看看可能会出现什么错误。
N1节点更新了V0到V1，想在也想把这个消息通过M操作告诉N1节点，却发生了网络故障。这时候小明和小华都要同时访问这个数据，怎么办呢？现在我们依然想要我们的系统具有CAP三个特性，我们分析一下会发生什么。
- 系统网络发生了故障，但是系统依然可以访问，因此具有容错性。
- 小明在访问节点N1的时候更改了V0到V1，想要小华访问节点N2的V数据库的时候是V1，因此需要等网络故障恢复，将N2节点的数据库进行更新才可以。
- 在网络故障恢复的这段时间内，想要系统满足可用性，是不可能的。因为可用性要求随时随地访问系统都是正确有效的。这就出现了矛盾。
正是这个矛盾所以CAP三个特性肯定不能同时满足。既然不能满足，那我们就进行取舍。
有两种选择：
- 牺牲数据一致性，也就是小明看到的衣服数量是10，买了一件应该是9了。但是小华看到的依然是10。
- 牺牲可用性，也就是小明看到的衣服数量是10，买了一件应该是9了。但是小华想要获取的最新的数据的话，那就一直等待阻塞，一直到网络故障恢复。
现在你可以看到了CAP三个特性肯定是不能同时满足的，但是可以满足其中两个。
一致性算法
想了想一致性算法好像蛮多的，下面列举一下
- 两阶段提交
- 三阶段提交
- paxos
- raft
- zab
一致性概述
当前工业实际应用中的一致性模型分类
- 弱一致性（最终一致性）
mq等
- 强一致性
也可分为2种
主从同步
基本思想： 主从同步复制：
- Master接受写请求
- Master复制日志至slave
- Master等待，直到所有从库返回
多数派
基本思想： 每次写都保证写入大于N/2个节点，每次读保证从大于N/2个节点中读。
相关算法：
- Paxos
- Raft（multi-paxos）
- ZAB（multi-paxos）
Basic Paxos
角色介绍
- Client： 系统外部角色，请求发起者。像民众
- Proposer： 接受Client请求，向集群提出提议（propose），并在冲突发生时，起到冲突调解的作用。像议员，替民众提出议案
- Acceptor：提议投票和接受者，只有在形成法定人数（Quorum，一般即为majority-多数派）时，提议才会最终被接受。像国会
- Learner：提议接受者，backup-备份，对集群一致性没什么影响。像记录员
步骤、阶段
- 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的提案，则接受此提案内容，否则忽略。
ZAB 协议
ZAB 协议 ( Zookeeper Atomic Broadcast) 原子广播协议：保证了发给各副本的消息顺序相同 定义：原子广播协议 ZAB 是一致性协议，Zookeeper 把其作为数据一致性的算法。ZAB 是在 Paxos 算法基础上进行扩展而来的。Zookeeper 使用单一主进程 Leader用于处理客户端所有事务请求，采用 ZAB 协议将服务器状态以事务形式广播到所有 Follower 上，由于事务间可能存在着依赖关系，ZAB协议保证 Leader 广播的变更序列被顺序的处理，一个状态被处理那么它所依赖的状态也已经提前被处理 核心思想：保证任意时刻只有一个节点是Leader，所有更新事务由Leader发起去更新所有副本 Follower，更新时用的是 两段提交协议，只要多数节点 prepare 成功，就通知他们commit。各个follower 要按当初 leader 让他们 prepare 的顺序来 apply 事务协议状态
zab的具体过程就不说了
Raft 算法
Raft 算法也是一种少数服从多数的算法，在任何时候一个服务器可以扮演以下角色之一： Leader：负责 Client 交互 和 log 复制，同一时刻系统中最多存在一个 Follower：被动响应请求 RPC，从不主动发起请求 RPC Candidate : 由Follower 向Leader转换的中间状态 在选举Leader的过程中，是有时间限制的，raft 将时间分为一个个 Term，可以认为是“逻辑时间”： 每个 Term中至多存在1个 Leader 某些 Term由于不止一个得到的票数一样，就会选举失败，不存在Leader。则会出现 Split Vote ，再由候选者发出邀票 每个 Server 本地维护 currentTerm
选举过程： 获得超过半数的Server的投票，转换为 Leader，广播 HeatBeat 接收到 合法 Leader 的 AppendEnties RPC，转换为Follower 选举超时，没有 Server选举成功，自增 currentTerm ,重新选举 自增 CurrentTerm，由Follower 转换为 Candidate，设置 votedFor 为自身，并行发起 RequestVote RPC,不断重试，直至满足下列条件之一为止： 当Candidate 在等待投票结果的过程中，可能会接收到来自其他Leader的 AppendEntries RPC ,如果该 Leader 的 Term 不小于本地的 Current Term，则认可该Leader身份的合法性，主动降级为Follower，反之，则维持 candida 身份继续等待投票结果 Candidate 既没有选举成功，也没有收到其他 Leader 的 RPC (多个节点同时发起选举，最终每个 Candidate都将超时)，为了减少冲突，采取随机退让策略，每个 Candidate 重启选举定时器
- 日志更新问题：
如果在日志复制过程中，发生了网络分区或者网络通信故障，使得Leader不能访问大多数Follwers了，那么Leader只能正常更新它能访问的那些Follower服务器，而大多数的服务器Follower因为没有了Leader，他们重新选举一个候选者作为Leader，然后这个Leader作为代表于外界打交道，如果外界要求其添加新的日志，这个新的Leader就按上述步骤通知大多数Followers，如果这时网络故障修复了，那么原先的Leader就变成Follower，在失联阶段这个老Leader的任何更新都不能算commit，都回滚，接受新的Leader的新的更新。
- 流程：
解决办法：Client 赋予每个 Command唯一标识，Leader在接收 command 之前首先检查本地log Client 发送command 命令给 Leader Leader追加日志项，等待 commit 更新本地状态机，最终响应 Client 若 Client超时，则不断重试，直到收到响应为止（重发 command，可能被执行多次，在被执行但是由于网络通信问题未收到响应）
paxos 算法与 raft 算法的差异
相同点
得到大多数的赞成，这个 entries 就会定下来，最终所有节点都会赞成
不同点
raft强调是唯一leader的协议，此leader至高无上raft：新选举出来的leader拥有全部提交的日志，而 paxos 需要额外的流程从其他节点获取已经被提交的日志，它允许日志有空洞
区块链的分布式一致性
其实很多人觉得区块链 比特币特别的牛，确实也很牛，但是他的本质其实还很简单，当然是表象的本质，具体的小六六也不清楚，其实他就是一个异地多活的数据中心，只要你加入到这个数据中心，成为节点，你就可以获得他所有的数据记录，所以说他是去中心化的。
目前 区块链的一致性算法 大致有已下几个
- PoW
- Pos
- DPoS
PoW
矿工通过把网络尚未记录的现有交易打包到一个区块，然后不断遍历尝试来寻找一个随机数，使的新区块加上随机数的哈希值满足一定难度的条件，找到满足条件的随机数就相当于确定了区块链最新的一个区块，也相当于获得了区块链的本轮记账权。矿工吧满足条件的区块在网络中广播出去，全网其他节点在验证该区块满足挖矿难度条件，同时区块里的交易数据符合协议规范后，将各自把该区块链接到自己版本的区块链上从而在全网行程对当前网络状态的共识。
- 优点：完全去中心化，节点自由进出，避免了建立和维护中心化信用机构的成本，只要网络破坏者的算力不超过全网50%，网络的交易状态就能达成一致
- 缺点：挖矿造成大量的资源浪费，同时挖矿的奖励机制也造成矿池算力的高度集中，背离了当初去中心化设计的初衷，更大的问题是PoW机制达成共识的周期比较长，每秒钟最多只能做七笔交易，不适合商业应用
Pos
要求节点提供拥有一定数量的代币证明来获取竞争区块链记账权的一种分布式共识机制，如果单纯依靠代币余额来决定记账者必然使得富有者胜出，导致记账权的中心化，降低共识的公正性，因此不同的PoS机制在权益证明的基础上，采用不同方式来增加记账权的随机性来避免中心化，例如点点币（PeerCoin）PoS机制中拥有最多链龄长的比特币获得记账权的几率就越大，NXT和Blackcoin则采用一个公式来预测下一个记账的节点，拥有多的代币被选为记账节点的概率就越大；
- 优点：在一定 程度上缩短了共识达成的时间，降低了资源浪费
- 缺点：破坏者对网络攻击的成本低，网络安全性有待验证，另外拥有代币数量大的节点获得记账权的几率更大，会使得网络的共识受少数富裕账户支配从而失去公正性。
DPoS
类似于董事会投票，比特股（bitshares）采用的PoS机制是持股者投票选出一定数量的见证人，每个见证人按顺序有两秒钟的权限时间生成区块，若见证人在指定的时间片不能生成区块，区块生成权限交给下一个时间片对应的见证人。持股人可以随时通过投票更换这些见证人，DPoS的这种设计使得区块的生成更快捷更节能。
- 优点：大幅度缩小参与验证和记账节点的数量，可以达到秒级共识验证
- 缺点：选举固定数量的见证人作为记账候选人有可能不适合完全去中心化的场景，另外在网络节点数量少的场景，选举的见证人代表性也不强。
结尾
主要介绍的是分布式的一些理论，下篇我们就来zookeeper的实战拉。
