Category: storage

1. 特指 linearizability Consistency
2. CAP根本没有提到延迟(latency),满足CAP可用性的系统可以花任意长的时间来回复一个请求.
3. CAP系统的模型是一个只能读写单个数据的寄存器,事务(transaction)不在这个定理的范围之内
4. 在设计分布式系统的时候，你需要考虑到更多得多的问题。如果太关注CAP就容易导致忽略了其他重要的问题

(more…)

[TOC]

整体结构

寻找一种易于理解的一致性算法（扩展版）

基于Raft分布式一致性协议实现的局限及其对数据库的风险

主要分为以下几部分,相对于 Paxos，Raft 减少了非确定性的程度和服务器互相不一致的方式

1. 领导选取（leader selection）
2. 日志复制（log replication）
3. 安全性（safety））
4. 减少状态（state space reduction）

新特征

比一些已有算法有几个新特征

• 强领导者（Strong Leader）：Raft 使用一种比其他算法更强的领导形式。例如，日志条目只从领导者发送向其他服务器。这样就简化了对日志复制的管理，使得 Raft 更易于理解。
• 领导选取（Leader Selection）：Raft 使用随机定时器来选取领导者。这种方式仅仅是在所有算法都需要实现的心跳机制上增加了一点变化，它使得在解决冲突时更简单和快速。
• 成员变化（Membership Change）：Raft 为了调整集群中成员关系使用了新的联合一致性（joint consensus）的方法，这种方法中大多数不同配置的机器在转换关系的时候会交叠（overlap）。这使得在配置改变的时候，集群能够继续操作。

复制状态机

replication state machine

一致性算法是在复制状态机的背景下提出来的。在这个方法中，在一组服务器的状态机产生同样的状态的副本因此即使有一些服务器崩溃了这组服务器也还能继续执行。复制状态机在分布式系统中被用于解决许多有关容错的问题。

复制状态机是通过复制日志来实现的。每一台服务器保存着一份日志，日志中包含一系列的命令，状态机会按顺序执行这些命令。因为每一台计算机的状态机都是确定的，所以每个状态机的状态都是相同的，执行的命令是相同的，最后的执行结果也就是一样的了。

一致性

如何保证复制日志一致就是一致性算法的工作了。在一台服务器上，一致性模块接受客户端的命令并且把命令加入到它的日志中。它和其他服务器上的一致性模块进行通信来确保每一个日志最终包含相同序列的请求，即使有一些服务器宕机了。一旦这些命令被正确的复制了，每一个服务器的状态机都会按同样的顺序去执行它们，然后将结果返回给客户端。最终，这些服务器看起来就像一台可靠的状态机。

一致性特征

应用于实际系统的一致性算法一般有以下特性：

• 确保安全性（从来不会返回一个错误的结果），即使在所有的非拜占庭（Non-Byzantine）情况下，包括网络延迟、分区、丢包、冗余和乱序的情况下。
• 高可用性，只要集群中的大部分机器都能运行，可以互相通信并且可以和客户端通信，这个集群就可用。因此，一般来说，一个拥有 5 台机器的集群可以容忍其中的 2 台的失败（fail）。服务器停止工作了我们就认为它失败（fail）了，没准一会当它们存储稳定时就能从中恢复过来，重新加入到集群中。
• 不依赖时序保证一致性，时钟错误和极端情况下的消息延迟在最坏的情况下才会引起可用性问题。
• 通常情况下，一条命令能够尽可能快的在大多数节点对一轮远程调用作出相应时完成，一少部分慢的机器不会影响系统的整体性能

Paxos 算法的不足

Paxos 首先定义了一个能够达成单一决策一致的协议，例如一个单一复制日志条目（single replicated log entry）。我们把这个子集叫做单一决策 Paxos（single-decree Paxos）。

之后 Paxos 通过组合多个这种协议来完成一系列的决策，例如一个日志（multi-Paxos）。

Paxos 确保安全性和活跃性（liveness），并且它支持集群成员的变更。它的正确性已经被证明，通常情况下也很高效。

Paxos 有两个致命的缺点。

第一个

Paxos 太难以理解。它的完整的解释晦涩难懂；很少有人能完全理解，只有少数人成功的读懂了它。并且大家做了许多努力来用一些简单的术语来描述它。尽管这些解释都关注于单一决策子集问题，但仍具有挑战性。

第二个

它难以在实际环境中实现。

• 其中一个原因是，对于多决策 Paxos （multi-Paxos） ，大家还没有一个一致同意的算法。
• 另外，Paxos 的结构也是不容易在一个实际系统中进行实现的，这是单决策问题分解带来的又一个问题。例如，从许多日志条目中选出条目然后把它们融合到一个序列化的日志中并没有带来什么好处，它仅仅增加了复杂性。(围绕着日志来设计一个系统是更简单、更高效的：新日志按照严格的顺序添加到日志中去。)
• 另一个问题是，Paxos 使用对等的点对点的实现作为它的核心（尽管它最终提出了一种弱领导者的形式来优化性能）。这种方法在只有一个决策被制定的情况下才显得有效，但是很少有现实中的系统使用它。如果要做许多的决策，选择一个领导人，由领带人来协调是更简单有效的方法。

因此，在实际的系统应用中和 Paxos 算法都相差很大。所有开始于 Paxos 的实现都会遇到很多问题，然后由此衍生出了许多与 Paxos 有很大不同的架构。这是既费时又容易出错的，并且理解 Paxos 的难度又非常大。Paxos 算法在它正确性的理论证明上是很好的，但是在实现上的价值就远远不足了。来自 Chubby 的实现的一条评论就能够说明：

Paxos 算法的描述与实际实现之间存在巨大的鸿沟…最终的系统往往建立在一个没有被证明的算法之上。

Raft易于理解的设计

设计 Raft 的目标有如下几个：

• 它必须提供一个完整的、实际的基础来进行系统构建，为的是减少开发者的工作；
• 它必须在所有情况下都能保证安全可用；
• 它对于常规操作必须高效；
• 最重要的目标是：易于理解，它必须使得大多数人能够很容易的理解；
  另外，它必须能让开发者有一个直观的认识，这样才能使系统构建者们去对它进行扩展。

使用了两种适用的方式。

• 第一种是众所周知的问题分解：我们尽可能将问题分解成为若干个可解决的、可被理解的小问题。例如，在 Raft 中，我们把问题分解成为了领导选取（leader election）、日志复制（log replication）、安全（safety）和成员变化（membership changes）
• 第二个方法是通过减少需要考虑的状态的数量将状态空间简化，这能够使得整个系统更加一致并且尽可能消除不确定性。特别地，日志之间不允许出现空洞，并且 Raft 限制了日志不一致的可能性。尽管在大多数情况下，我们都在试图消除不确定性，但是有时候有些情况下，不确定性使得算法更易理解。(使用随机化来简化了 Raft 中的领导选取算法。随机化方法会使得不确定性增加，但是它能简化状态空间。)

Raft 一致性算法

Raft 是一种用来管理复制日志的算法

STATE

1. 所有服务器上的持久性状态 (在响应RPC请求之前 已经持久化到存储设备)

currentTerm	服务器已知最新的任期（在服务器首次启动的时候初始化为0，单调递增）
votedFor	当前任期内收到选票的候选者id 如果没有投给任何候选者 则为空
log[]	日志条目;每个条目包含了用于状态机的命令，以及领导者接收到该条目时的任期（第一个索引为1）

2. 所有服务器上的不稳定状态

commitIndex	已知已提交的最高的日志条目的索引（初始值为0，单调递增）
lastApplied	已经被应用到状态机的最高的日志条目的索引（初始值为0，单调递增）

3. 领导者（服务器）上的不稳定状态 (选举后已经重新初始化)

nextIndex[]	对于每一台服务器，发送到该服务器的下一个日志条目的索引（初始值为领导者最后的日志条目的索引+1）
matchIndex[]	对于每一台服务器，已知的已经复制到该服务器的最高日志条目的索引（初始值为0，单调递增）

Append Entries RPC

被领导者调用,用于日志条目的复制 同时也被当做心跳使用

参数	含义
term	领导者的任期
leaderId	领导者ID 因此跟随者可以对客户端进行重定向（译者注：跟随者根据领导者id把客户端的请求重定向到领导者，比如有时客户端把请求发给了跟随者而不是领导者）| |prevLogIndex|紧邻新日志条目之前的那个日志条目的索引
prevLogTerm	紧邻新日志条目之前的那个日志条目的任期
entries[]	需要被保存的日志条目（被当做心跳使用是 则日志条目内容为空；为了提高效率可能一次性发送多个）
leaderCommit	领导者的已知已提交的最高的日志条目的索引

结果	含义
term	当前任期,对于领导者而言 它会更新自己的任期
success	结果为真 如果跟随者所含有的条目和preLogIndex以及preLogTerm匹配上了

接收者的实现：

1. 返回假.如果领导者的任期 小于 接收者的当前任期（译者注：这里的接收者是指跟随者或者候选者）（5.1 节）
2. 返回假.如果接收者日志中没有包含这样一个条目 即该条目的任期在preLogIndex上能和prevLogTerm匹配上 （译者注：在接收者日志中 如果能找到一个和preLogIndex以及prevLogTerm一样的索引和任期的日志条目 则返回真 否则返回假）（5.3 节）
3. 如果一个已经存在的条目和新条目（译者注：即刚刚接收到的日志条目）发生了冲突（因为索引相同，任期不同），那么就删除这个已经存在的条目以及它之后的所有条目 （5.3 节）
4. 追加日志中尚未存在的任何新条目
5. 如果领导者的已知已经提交的最高的日志条目的索引 大于 接收者的已知已经提交的最高的日志条目的索引, 则把 接收者的已知已经提交的最高的日志条目的索引 重置为 领导者的已知已经提交的最高的日志条目的索引 或者是 上一个新条目的索引 取两者的最小值

请求投票 RPC

由候选人负责调用用来征集选票（5.2 节）

参数	解释
term	候选人的任期号
candidateId	请求选票的候选人的 Id
lastLogIndex	候选人的最后日志条目的索引值
lastLogTerm	候选人最后日志条目的任期号

返回值	解释
term	当前任期号，以便于候选人去更新自己的任期号
voteGranted	候选人赢得了此张选票时为真

接收者实现：

1. if term < currentTerm, return false （5.2 节）
2. 如果 votedFor 为空或者为 candidateId，并且候选人的日志至少和自己一样新，那么就投票给他（5.2 节，5.4 节）

服务器规则

1. 所有服务器需遵守的规则：

• if commitIndex > lastApplied， lastApplied +=1，并把log[lastApplied]应用到状态机中（5.3 节）
• 如果接收到的 RPC 请求或响应中，任期号T > currentTerm，那么就令 currentTerm 等于 T，并切换状态为跟随者（5.1 节）

2. 跟随者（5.2 节）

• 响应来自候选人和领导者的请求
• 如果在选举超时时间之前没有收到当前领导人（即该领导人的任期需与这个跟随者的当前任期相同）的心跳/附加日志，或者是给某个候选人投了票，那么自己变成候选人

3. 候选人（5.2 节）：

• 在转变成候选人后就立即开始选举过程
• 自增当前的任期号（currentTerm）
• 给自己投票
• 重置选举超时计时器
• 发送请求投票的 RPC 给其他所有服务器
• 如果接收到大多数服务器的选票，那么就变成领导人
• 如果接收到来自新的领导人的附加日志 RPC，转变成跟随者
• 如果选举过程超时，再次发起一轮选举

4. 领导人：

• 一旦成为领导人：发送空的附加日志 RPC（心跳）给其他所有的服务器；在一定的空余时间之后不停的重复发送，以阻止跟随者超时（5.2 节）
• 如果接收到来自客户端的请求：附加条目到本地日志中，在条目被应用到状态机后响应客户端（5.3 节）
• 如果对于一个跟随者，最后日志条目的索引值大于等于 nextIndex，那么：发送从 nextIndex 开始的所有日志条目：
• 如果成功：更新相应跟随者的 nextIndex 和 matchIndex
• 如果因为日志不一致而失败，减少 nextIndex 重试
• 如果存在一个满足N > commitIndex的 N，并且大多数的matchIndex[i] ≥ N成立，并且log[N].term currentTerm成立，那么令 commitIndex 等于这个 N （5.3 和 5.4 节）

RAFT 一致性特征

特性	解释
选举安全特性	对于一个给定的任期号，最多只会有一个领导人被选举出来（5.2 节）
领导人只附加原则	领导人绝对不会删除或者覆盖自己的日志，只会增加（5.3 节）
日志匹配原则	如果两个日志在相同的索引位置的日志条目的任期号相同，那么我们就认为这个日志从头到这个索引位置之间全部完全相同（5.3 节）
领导人完全特性	如果某个日志条目在某个任期号中已经被提交，那么这个条目必然出现在更大任期号的所有领导人中（5.4 节）
状态机安全特性	如果一个领导人已经将给定的索引值位置的日志条目应用到状态机中，那么其他任何的服务器在这个索引位置不会应用一个不同的日志（5.4.3 节）

RAFT 基本流程

一个 Raft 集群包含若干个服务器节点；通常是 5 个，这允许整个系统容忍 2 个节点的失效。在任何时刻，每一个服务器节点都处于这三个状态之一：

• 领导人
• 跟随者
• 候选人

在通常情况下，系统中只有一个领导人并且其他的节点全部都是跟随者。跟随者都是被动的：他们不会发送任何请求，只是简单的响应来自领导者或者候选人的请求。领导人处理所有的客户端请求（如果一个客户端和跟随者联系，那么跟随者会把请求重定向给领导人）。第三种状态，候选人，是用来在 5.2 节描述的选举新领导人时使用。下图展示了这些状态和他们之间的转换关系；这些转换关系会在接下来进行讨论。

• 跟随者只响应来自其他服务器的请求。

• 如果跟随者接收不到消息，那么他就会变成候选人并发起一次选举。

• 获得集群中大多数选票的候选人将成为领导者。

• 在一个任期内，领导人一直都会是领导人直到自己宕机了

• 时间被划分成一个个的任期，每个任期开始都是一次选举。

• 在选举成功后，领导人会管理整个集群直到任期结束。

• 有时候选举会失败，那么这个任期就会没有领导人而结束。

• 任期之间的切换可以在不同的时间,不同的服务器上观察到。

Raft 把时间分割成任意长度的任期，如图 5。

任期用连续的整数标记。

每一段任期从一次选举开始，就像章节 5.2 描述的一样，一个或者多个候选人尝试成为领导者。

如果一个候选人赢得选举，然后他就在接下来的任期内充当领导人的职责。

在某些情况下，一次选举过程会造成选票的瓜分。在这种情况下，这一任期会以没有领导人结束；一个新的任期（和一次新的选举）会很快重新开始。

Raft 保证了在一个给定的任期内，最多只有一个领导者。

不同的服务器节点可能多次观察到任期之间的转换，但在某些情况下，一个节点也可能观察不到任何一次选举或者整个任期全程。

任期在 Raft 算法中充当逻辑时钟的作用，这会允许服务器节点查明一些过期的信息比如陈旧的领导者。

每一个节点存储一个当前任期号，这一编号在整个时期内单调的增长。

当服务器之间通信的时候会交换当前任期号；

如果一个服务器的当前任期号比其他人小，那么他会更新自己的编号到较大的编号值。

如果一个候选人或者领导者发现自己的任期号过期了，那么他会立即恢复成跟随者状态。

如果一个节点接收到一个包含过期的任期号的请求，那么他会直接拒绝这个请求。

Raft 算法中服务器节点之间通信使用远程过程调用（RPCs），并且基本的一致性算法只需要两种类型的 RPCs。请求投票（RequestVote） RPCs 由候选人在选举期间发起（章节 5.2），然后附加条目（AppendEntries）RPCs 由领导人发起，用来复制日志和提供一种心跳机制（章节 5.3）。第 7 节为了在服务器之间传输快照增加了第三种 RPC。当服务器没有及时的收到 RPC 的响应时，会进行重试， 并且他们能够并行的发起 RPCs 来获得最佳的性能。