Zookeeper与分布式理论

Part1 分布式一致性

通信故障、请求三态（成功、失败、超时）、节点故障等，这些问题会导致一系例数据不一致的问题，那么分布式一致性算法就是用来解决这个问题的。

理论是指导业界实现的纲领，也是提炼了多年研究的精华，在分布式一致性领域，最主要的指导理论是CAP和BASE两个。

CAP理论

CAP即Consistency 一致性、Availability 可用性、Partition-torlerance 分区容忍性。具体而言，CAP描述了分布式一致性的三个维度：

1. 一致性：每次读操作都能保证返回的是最新数据；在分布式系统中，如果能针对一个数据项的更新执行成功后，所有的请求都可以读到其最新的值，这样的系统就被认为具有严格的一致性。
2. 可用性：任何一个没有发生故障的节点，会在合理的时间内返回一个正常的结果，也就是对于每一个请求总能够在有限时间内返回结果。
3. 分区容忍性：当节点间出现网络分区，照样可以提供满足一致性和可用性的服务。

网络分区：

网络分区（Partition）是指在分布式系统中，由于网络通信故障或其他原因，系统被分割成两个或多个独立的部分，这些部分之间无法进行正常的通信。这种情况下，系统的一部分可能无法感知到另一部分的存在，从而无法进行数据同步和状态更新。

CAP指出，一个分布式系统只能满足三项中的两项而不可能满足全部三项。 既然CAP理论无法全部满足，为了指导工业实现，就需要降低标准，因此出现了BASE理论。

BASE理论

它的思想是：“即使无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方式来使系统达到最终一致性” 。

BASE理论有三项指标：

• 基本可用（Basically Available） ：是指分布式系统在出现不可预知故障的时候，允许损失部分可用性：比如响应时间、功能降级等；
• 软状态（ Soft State） ：也称为弱状态，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点之间进行数据同步的过程存在延时；
• 最终一致性（ Eventual Consistency） ：强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达成一致的状态。

BASE理论面向的是大型高可用、可扩展的分布式系统。BASE通过牺牲强一致性来获得可用性，并允许数据短时间内的不一致，但是最终达到一致状态。

​​

Part2 分布式算法

这些算法的目的就是为保证分布式一致性而提出的算法，基本上都是保证BASE理论。其实我们今天讨论的准确的说，应该是 状态机复制 的共识（consensus）算法。

从主从同步到PAXOS

那么我们很容易想到一个算法：

​​

两阶段提交

问题：一个节点失败，Master阻塞，导致整个集群不可用，保证了一致性，可用性却大大降低。并且如果出现OK消息丢失的问题，还会导致不同节点的状态不一致的问题。

​​

这通常特指分布式事务的一种实现，但也是一种通用的思想，为防止对副本的写入失败，在复制指令之前先去锁定状态机的应用，主节点发送一个预写命令，当其发送给所有的副本并接受到全部确认后，才会真正发送命令同步到副本，而副本节点在确认预写命令后将不再接受其他命令，直到此次命令同步结束。

这可以通过给每一个指令分配一个逻辑时序来实现，可以是一个单调递增的数值，用来区分指令序列，因为预写操作的锁定效果，如果副本节点写入后没有回复成功，可以不断重试，直到成功，进而实现最严格的最终一致性。

​​

多数派协议

问题：等待时间太长，并且极端情况下会陷入无限重试。

为了解决这个问题，引入了多数派协议，即鸽笼原理。按照客观事实，存在奇数N个抽屉，将N/2+1个信封放到N/2+1个抽屉中，那么再打开任意N/2+1个抽屉，都必然至少有一个存在信封。

同理，如果主节点发送命令被写入半数以上副本节点成功，那么读取时，只要获得任意半数以上节点的状态，从中选择时序最大的那个节点的数据即可。

两阶段提交+多数派协议

问题：并发情况下的原子性问题，如图：

​​

因此，提出最终方案两阶段提交+多数派协议

如果将两阶段提交预写阶段中所有副本都要回复确认改为只需要半数以上节点进行确认锁定，那么不会有另一个多数派副本集合同意其他的写入，这同样能达到锁定的效果，并且只在第二阶段中有任意的多数派集合写入成功，则数据就不会丢失，因为任意多数派集合都必然包含一个确认预写的副本，更进一步可以说，无论读写，任意的多数派集合总会包含写入的最新指令。

Basic Paxos

我们将上述描述的两阶段提交+多数派协议进行泛化，找到一种更加通用的描述方式：
首先来定义一下基本的概念范畴：

• 指令的提议者(Proposer)，上文提到的主节点，发起两阶段提交和多数派仲裁的角色。

• 指令的决策者(Acceptor)，上文提到的副本，根据自身的状态决策是否可以应用此指令到状态机。

• 法定人数(Quorum)，上文提到的构成多数派的节点集合。

• 回合(Round)，Basic-Paxos协议写入一个值到集群的过程，可以理解为是一个逻辑时序。

  整个Basic paxos一次完整的指令应用过程是：提案，决策，仲裁，修复/提交。

​​

具体操作：

​​

RAFT

RAFT最大的优化应该是确定了一个Leader，替代PAXOS的任意节点都可以发起请求的机制。这样一来，就不用经过PAXOS的提案阶段（加锁），就可以直接进行第二阶段。不过再加上确认机制要两次传递。

先来个图理解一下正常运行的全过程：

​​

Raft 中使用 日志 来记录所有操作，所有结点都有自己的日志列表来记录所有请求。算法将机器分成三种角色：Leader、Follower 和 Candidate。正常情况下只存在一个 Leader，其他均为 Follower，所有客户端都与 Leader 进行交互。

所有操作采用类似两阶段提交的方式，Leader 在收到来自客户端的请求后并不会执行，只是将其写入自己的日志列表中，然后将该操作发送给所有的 Follower。Follower 在收到请求后也只是写入自己的日志列表中然后回复 Leader，当有超过半数的结点写入后 Leader 才会提交该操作并返回给客户端，同时通知所有其他结点提交该操作。

在了解了算法的基本工作流程之后，就让我们开始解决其中会遇到的问题，首先就是 Leader 如何而来。

选取Leader

在算法刚开始时，所有结点都是 Follower，每个结点都会有一个定时器，每次收到来自 Leader 的信息就会更新该定时器。

如果定时器超时，说明一段时间内没有收到 Leader 的消息，那么就可以认为 Leader 已死或者不存在，那么该结点就会转变成 Candidate，意思为准备竞争成为 Leader。

成为 Candidate 后结点会向所有其他结点发送请求投票的请求（RequestVote），其他结点在收到请求后会判断是否可以投给他并返回结果。Candidate 如果收到了半数以上的投票就可以成为 Leader，成为之后会立即并在任期内定期发送一个心跳信息通知其他所有结点新的 Leader 信息，并用来重置定时器，避免其他结点再次成为 Candidate。

​​

而如果发生网络分区、Leader下线这类情况可能会触发Leader重选。特别说下网络分区的问题，因此只有拥有多数结点的分区可以正常工作。而对于少数结点的分区，即使仍存在 Leader，但由于写入日志的结点数量不可能超过半数因此不可能提交操作。

​​

任期

节点维护一个Term变量代表任期，当一个结点成为 Candidate 并向其他结点请求投票时，会将自己的 Term 加 1，表明新一轮的开始以及旧 Leader 的任期结束。

所有结点在收到比自己更新的 Term 之后就会更新自己的 Term 并转成 Follower，而收到过时的消息则拒绝该请求。

投票限制

投票成为新节点时，有一个问题，就是这个新节点必须是拥有完整日志的节点，这一步骤由投票来限制。

投票由一个称为 RequestVote 的 RPC 调用进行，请求中除了有 Candidate 自己的 term 和 id 之外，还要带有自己最后一个日志条目的 index 和 term。日志 Term 越大则越新，相同那么 index 较大的认为是更加新的日志。接收者只会投票给拥有相同或者更加新的日志的 Candidate。

由于只有日志在被多数结点复制之后才会被提交并返回，所以如果一个 Candidate 并不拥有最新的已被复制的日志，那么他不可能获得多数票，从而保证了 Leader 一定具有所有已被多数拥有的日志（Leader Completeness），在后续同步时会将其同步给所有结点。

日志提交限制

只要日志在多数结点上存在，那么 Leader 就可以提交该操作。但是 Raft 额外限制了 Leader 只对自己任期内的日志条目适用该规则，先前任期的条目只能由当前任期的提交而间接被提交。

这条是最抽象的。

​​

例如论文中图 8 这一 corner case。一开始如 (a) 所示，之后 S1 下线，(b) 中 S5 从 S3 和 S4 处获得了投票成为了 Leader 并收到了一条来自客户端的消息，之后 S5 下线。(c) 中 S1 恢复并成为了 Leader，并且将日志复制给了多数结点，之后进行了一个致命操作，将 index 为 2 的日志提交了，然后 S1 下线。(d) 中 S5 恢复，并从 S2、S3、S4 处获得了足够投票，然后将已提交的 index 为 2 的日志覆盖了。

为了解决这个问题，Raft 只允许提交自己任期内的日志，从而日志 2 只能像 (e) 中由于日志 3 同步而被间接提交，避免了 Follower 中由于缺少新任期的日志，使得 S5 能够继续成为 Leader。

总结大图

​​

Part3 Zookeeper

OK，以上是分布式一致性保证的协议和算法，那么在应用上或者说工程上的代表就是Zookeeper。

Zookeeper是什么？

一句话概括：具有分布式一致性保证的内存文件系统（或KV引擎）。它基于自己设计的ZAB协议，ZAB协议出现比Raft更早，因此Raft借鉴了很多ZAB的设计。实际上这个两个协议非常像，因此这里不再单独讨论ZAB。

不同点：别人的博客