3.数据的一致性与一致性算法（CAP原则、Paxos算法、Raft算法、ZAB协议）_一致性算法 信息交互 更新

数据的一致性与一致性算法（CAP原则、Paxos算法、Raft算法、ZAB协议）

一、数据的一致性

1.定义

• 一些分布式系统通过复制数据来提高系统的可靠性和容错性，并且将数据的不同的副本存放在不同的机器
• 在数据有多分副本的情况下，如果网络、服务器或者软件出现故障，会导致部分副本写入成功，部分副本写入失败。这就造成各个副本之间的数据不一致，数据内容冲突。

2.模型

• 强一致性
  • 要求无论更新操作实在哪一个副本执行，之后所有的读操作都要能获得最新的数据。
• 弱一致性
  • 用户读到某一操作对系统特定数据的更新需要一段时间，我们称这段时间为“不一致性窗口”。
• 最终一致性
  • 是弱一致性的一种特例，保证用户最终能够读取到某操作对系统特定数据的更新。
  • 从客户端来看，有可能暂时获取的不是最新的数据，但是最终还是能访问到最新的
  • 从服务端来看，数据存储并复制到分布到整个系统超过半数的节点，以保证数据最终一致。

3.最终一致性

• 因果一致性（Casual Consistency）

  • 如果进程A通知进程B它已更新了一个数据项，那么进程B的后续访问将返回更新后的值，且一次写入将保证取代前一次写入。
  • 与进程A无因果关系的进程C的访问，遵守一般的最终一致性规则。
  • 查询微博和评论
  • 

• 读己之所写一致性（read-your-writes）

  • 当进程A自己更新一个数据项之后，它总是访问到更新过的值，绝不会看到旧值。这是因果一致性模型的一个特例。
  • 读自己的数据都从主服务器去读取，读其他人的数据再从从服务器去读取
  • 发表微博与修改微博

• 会话（Session）一致性

  • 这是上一个模型的实用版本，它把访问存储系统的进程放到会话的上下文中。只要会话还存
  • 在，系统就保证“读己之所写”一致性。如果由于某些失败情形令会话终止，就要建立新的会话，而且系统的保证不会延续到新的会话。
  • 确保会话内访问的都是最新的

• 单调（Monotonic）读一致性

  • 如果进程已经看到过数据对象的某个最新值，那么任何后续访问都不会返回在那个值之前的值。
  • 不会读取最旧的数据

• 单调写一致性

  • 系统保证来自同一个进程的写操作顺序执行。要是系统不能保证这种程度的一致性，就非常难以编程了。

  • 按照顺序完成数据的书写

  • 

  • 

二、CAP原则

1.定义

• CAP定理是2000年，由 Eric Brewer 提出来的。Brewer认为在分布式的环境下设计和部署系统时，有3个核心的需求，以一种特殊的关系存在。
• 这3个核心的需求是：Consistency，Availability和Partition Tolerance
• CAP定理认为：一个提供数据服务的存储系统无法同时满足数据一致性、数据可用性、分区容忍性

2.概念

• Consistency：
  • 一致性，这个和数据库ACID的一致性类似，但这里关注的所有数据节点上的数据一致性和正确性，而数据库的ACID关注的是在在一个事务内，对数据的一些约束。
  • 系统在执行过某项操作后仍然处于一致的状态。在分布式系统中，更新操作执行成功后所有的用户都应该读取到最新值。
• Availability：
  • 可用性，每一个操作总是能够在一定时间内返回结果。需要注意“一定时间”和“返回结果”。
  • “一定时间”是指系统结果必须在给定时间内返回。
  • “返回结果”是指系统返回操作成功或失败的结果。
• Partition Tolerance：
  • 分区容忍性，是否可以对数据进行分区。这是考虑到性能和可伸缩性。

3.推导

• 如果要求对数据进行分区了，就说明了必须节点之间必须进行通信，涉及到通信，就无法确保在有限的时间内完成指定的任务
• 如果要求两个操作之间要完整的进行，因为涉及到通信，肯定存在某一个时刻只完成一部分的业务操作，在通信完成的这一段时间内，数据就是不一致性的。
• 如果要求保证一致性，那么就必须在通信完成这一段时间内保护数据，使得任何访问这些数据的操作不可用。

4.结论

• 在大型网站应用中，数据规模总是快速扩张的，因此可伸缩性即分区容忍性必不可少，规模变大以后，机器数量也会变得庞大，这是网络和服务器故障会频繁出现，要想保证应用可用，就必须保证分布式处理系统的高可用性。
• 在大型网站中，通常会选择强化分布式存储系统的可用性和伸缩性，在某种程度上放弃一致性。

三、Paxos算法

1.简介

• Paxos算法是Leslie Lamport宗师提出的一种基于消息传递的分布式一致性算法，使其获得2013年图灵奖。
• Paxos在1990年提出，被广泛应用于分布式计算中，Google的Chubby，Apache的Zookeeper都是基于它的理论来实现的
• Paxos算法解决的问题是分布式一致性问题，即一个分布式系统中的各个进程如何就某个值（决议）达成一致。
• 传统节点间通信存在着两种通讯模型：共享内存（Shared memory）、消息传递（Messagespassing），Paxos是一个基于消息传递的一致性算法。

2.算法描述

Paxos描述了这样一个场景，有一个叫做Paxos的小岛(Island)上面住了一批居民，岛上面所有的事情 由一些特殊的人决定，他们叫做议员(Senator)。议员的总数(Senator Count)是确定的，不能更 改。岛上每次环境事务的变更都需要通过一个提议(Proposal)，每个提议都有一个编号(PID)，这个编 号是一直增长的，不能倒退。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生 效。每个议员只会同意大于当前编号的提议，包括已生效的和未生效的。如果议员收到小于等于当前编号 的提议，他会拒绝，并告知对方：你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上 面记录的编号，他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会 有一个目标：保证所有的议员对于提议都能达成一致的看法。
现在议会开始运作，所有议员一开始记事本上面记录的编号都是0。有一个议员发了一个提议：将电费设 定为1元/度。他首先看了一下记事本，嗯，当前提议编号是0，那么我的这个提议的编号就是1，于是他 给所有议员发消息：1号提议，设定电费1元/度。其他议员收到消息以后查了一下记事本，哦，当前提议 编号是0，这个提议可接受，于是他记录下这个提议并回复：我接受你的1号提议，同时他在记事本上记 录：当前提议编号为1。发起提议的议员收到了超过半数的回复，立即给所有人发通知：1号提议生效！收 到的议员会修改他的记事本，将1好提议由记录改成正式的法令，当有人问他电费为多少时，他会查看法 令并告诉对方：1元/度。
现在看冲突的解决：假设总共有三个议员S1-S3，S1和S2同时发起了一个提议:1号提议，设定电费。S1 想设为1元/度, S2想设为2元/度。结果S3先收到了S1的提议，于是他做了和前面同样的操作。紧接着他 又收到了S2的提议，结果他一查记事本，咦，这个提议的编号小于等于我的当前编号1，于是他拒绝了这 个提议：对不起，这个提议先前提过了。于是S2的提议被拒绝，S1正式发布了提议: 1号提议生效。S2 向S1或者S3打听并更新了1号法令的内容，然后他可以选择继续发起2号提议。
1
2
3

3.Paxos推断

• 小岛(Island) 服务器集群
• 议员(Senator) 单台服务器
• 议员的总数(Senator Count)是确定的
• 提议(Proposal) 每一次对集群中的数据进行修改
• 每个提议都有一个编号(PID)，这个编号是一直增长的
• 每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效
• 每个议员只会同意大于当前编号的提议
• 每个议员在自己记事本上面记录的编号，他不断更新这个编号
• 整个议会不能保证所有议员记事本上的编号总是相同的
• 议会有一个目标：保证所有的议员对于提议都能达成一致的看法。
• 前期投票(>1/2)，后期广播(all)
• Paxos算法
  • 数据的全量备份
  • 弱一致性 ——》最终一致性

4.算法模型延伸

如果Paxos岛上的议员人人平等，在某种情况下会由于提议的冲突而产生一个“活锁”（所谓活锁我的理解是大 家都没有死，都在动，但是一直解决不了冲突问题）。Paxos的作者在所有议员中设立一个总统，只有总统有 权发出提议，如果议员有自己的提议，必须发给总统并由总统来提出。
情况一：屁民甲(Client)到某个议员(ZK Server)那里询问(Get)某条法令的情况(ZNode的数据)，议员毫 不犹豫的拿出他的记事本(local storage)，查阅法令并告诉他结果，同时声明：我的数据不一定是最新 的。你想要最新的数据？没问题，等着，等我找总统Sync一下再告诉你。
情况二：屁民乙(Client)到某个议员(ZK Server)那里要求政府归还欠他的一万元钱，议员让他在办公室等 着，自己将问题反映给了总统，总统询问所有议员的意见，多数议员表示欠屁民的钱一定要还，于是总统发表 声明，从国库中拿出一万元还债，国库总资产由100万变成99万。屁民乙拿到钱回去了(Client函数返回)。 情况三：总统突然挂了，议员接二连三的发现联系不上总统，于是各自发表声明，推选新的总统，总统大选期 间政府停业，拒绝屁民的请求。
1
2
3

• 无主集群模型
  • 人人都会发送指令,投票
    • 投票人数有可能导致分区(分不同阵营)，
      • 6个节点 33对立
      • 类似于以前党争
  • 事务编号混乱，每个节点都有可能有自己的提议
    • 提议的编号不能重复和小于
• 有主集群模型
  • 只能有一个主发送指令，发送提议
  • 单主会单点故障，肯定有备用的方案
    • 重新选举
    • 切换到备用节点
  • 如果存在多个主就会脑裂
• 主要集群中节点数目高于1/2+1，集群就可以正常运行
• 

四、Raft算法

1.简介

• Raft 适用于一个管理日志一致性的协议，相比于 Paxos 协议 Raft 更易于理解和去实现它。
• Raft 将一致性算法分为了几个部分，包括领导选取（leader selection）、日志复制（logreplication）、安全（safety）
• http://thesecretlivesofdata.com/raft/

2.问题

• 分布式存储系统通过维护多个副本来提高系统的availability，难点在于分布式存储系统的核心问题：

  • 维护多个副本的一致性

• Raft协议基于复制状态机（replicated state machine）

  • 一组server从相同的初始状态起，按相同的顺序执行相同的命令，最终会达到一致的状态

  • 一组server记录相同的操作日志，并以相同的顺序应用到状态机。

• Raft有一个明确的场景，就是管理复制日志的一致性

  • 每台机器保存一份日志，日志来自于客户端的请求，包含一系列的命令，状态机会按顺序执行这些命令。

3.角色分配

• Raft算法将Server划分为3种状态，或者也可以称作角色：
  • Leader
    • 负责Client交互和log复制，同一时刻系统中最多存在1个。
  • Follower
    • 被动响应请求RPC，从不主动发起请求RPC。
  • Candidate
    • 一种临时的角色，只存在于leader的选举阶段，某个节点想要变成leader，那么就发起
    • 投票请求，同时自己变成candidate
    • 

4.算法流程

• Term

  • Term的概念类比中国历史上的朝代更替，Raft 算法将时间划分成为任意不同长度的任期（term）。
  • 任期用连续的数字进行表示。每一个任期的开始都是一次选举（election），一个或多个候选人会试图成为领导人。如果一个候选人赢得了选举，它就会在该任期的剩余时间担任领导人。在某些情况下，选票会被瓜分，有可能没有选出领导人，那么，将会开始另一个任期，并且立刻开始下一次选举。Raft 算法保证在给定的一个任期最多只有一个领导人。

• RPC

  • Raft 算法中服务器节点之间通信使用远程过程调用（RPCs）

  • 基本的一致性算法只需要两种类型的 RPCs，为了在服务器之间传输快照增加了第三种 RPC。

    • RequestVote RPC：候选人在选举期间发起

    • AppendEntries RPC：领导人发起的一种心跳机制，复制日志也在该命令中完成

    • InstallSnapshot RPC: 领导者使用该RPC来发送快照给太落后的追随者

• 日志复制（Log Replication）

  • 主要用于保证节点的一致性，这阶段所做的操作也是为了保证一致性与高可用性。

  • 当Leader选举出来后便开始负责客户端的请求，所有事务（更新操作）请求都必须先经过Leader处理

  • 日志复制（Log Replication）就是为了保证执行相同的操作序列所做的工作。

  • 在Raft中当接收到客户端的日志（事务请求）后先把该日志追加到本地的Log中

  • 然后通过heartbeat把该Entry同步给其他Follower，Follower接收到日志后记录日志然后向Leader发送ACK

  • 当Leader收到大多数（n/2+1）Follower的ACK信息后将该日志设置为已提交并追加到本地磁盘中

  • 通知客户端并在下个heartbeat中Leader将通知所有的Follower将该日志存储在自己的本地磁盘中。

五、ZAB协议

1.简介

• ZAB（Zookeeper Atomic Broadcast） 协议是为分布式协调服务zookeeper专门设计的一种支持崩溃恢复的原子广播协议。
• ZAB是ZooKeeper实现分布式数据一致性的核心算法，ZAB借鉴Paxos算法
• 在zookeeper中，主要依赖ZAB协议来实现分布式数据一致性，基于该协议，zookeeper实现了一种主备模式的系统架构来保持集群中各个副本之间的数据一致性。

2.ZAB协议的三个阶段

• 发现：即要求zookeeper集群必须选择出一个leader进程，同时leader会维护一个follower可用列表。将来客户端可以这follower中的节点进行通信。
• 同步：leader要负责将本身的数据与follower完成同步，做到多副本存储。这样也是体现了CAP中CP。follower将队列中未处理完的请求消费完成后，写入本地事物日志中。
• 广播：leader可以接受客户端新的proposal请求，将新的proposal请求广播给所有的follower。

3.协议核心

• ZAB协议的核心是定义了对于那些会改变ZooKeeper服务器数据状态的事务请求处理方式，即：
  • 所有事务请求必须由一个全局唯一的服务器来协调处理，这样的服务器被称为Leader服务器，而余下的其他服务器称为Follower服务器。Leader服务器负责将一个客户端事务请求转换成一个事务Proposal(提议)，并将该Proposal分发给集群中所有的Follower服务器。之后Leader服务器需要等待所有的Follower服务器的反馈，一旦超过半数的Follower服务器进行了正确的反馈后，那么Leader就会再次向所有的Follower服务器分发Commit消息，要求其将前一个Proposal进提交。

4.两种基本模式

• 1》崩溃恢复之数据恢复
  • 当整个集群正在启动时，或者当leader节点出现网络中断、崩溃等情况时，ZAB协议就会进入恢复模式并选举产生新的leader，当leader服务器选举出来后，并且集群中有过半的机器和该leader节点完成数据同步后（同步指的是数据同步，用来保证集群中过半的机器能够和leader服务器的数据状态保持一致），ZAB协议就会退出恢复模式。
• 2》消息广播之原子广播
  oposal进提交。

4.两种基本模式

• 1》崩溃恢复之数据恢复
  • 当整个集群正在启动时，或者当leader节点出现网络中断、崩溃等情况时，ZAB协议就会进入恢复模式并选举产生新的leader，当leader服务器选举出来后，并且集群中有过半的机器和该leader节点完成数据同步后（同步指的是数据同步，用来保证集群中过半的机器能够和leader服务器的数据状态保持一致），ZAB协议就会退出恢复模式。
• 2》消息广播之原子广播
  • 当集群中已经有过半的Follower节点完成了和Leader状态同步以后，那么整个集群就进入了消息广播模式。这个时候，在Leader节点正常工作时，启动一台新的服务器加入到集群，那这个服务器会直接进入数据恢复模式，和leader节点进行数据同步。同步完成后即可正常对外提供非事务请求的处理。