分布式数据库与一致性 - 主从架构

一致性：（consistency）

一致性: 在多机备份（repliaction）的场景下，数据节点之间复制数据，数据系统（数据库）能够在一定的条件下读取相同的数据。

repliaction 的主要架构方式：

• 主从结构：有一个单一节点作为leader，写入请求发送给这个leader，leader 同步或异步地向其余节点发送更新消息，读取可以从各个节点读取。

  
  单leader节点.png

• 多主结构：

  有多个主节点，写入请求发送个其中任何一个leader，由各个leader 进行同步。这种结构多用于多数据中心的备份。

• 无主结构：

  没有具体的leader节点，每个节点都是平等的，写入请求可以发送到任何节点，读取请求也可以发送到任何节点。

由于篇幅有限这里我们主要介绍单主结构下的一致性问题。

可线性化的一致性(强一致性)：linearizability，即同一时间读任何个备份 总是能够获得同样的数据，就好像数据只有一份。

什么时候需要强一致性：
逻辑上的约束性，全局唯一性 因果关系 （这里需要举例说明）
多个消息通道导致的非一致性。（一致性是解决这些问题的一种方法，但是并不是唯一的一种方法）

强一致性的最简单实现：
点节点结构，发送消息给各个数据点，并且返回。

最终一致性：最终一致性是最低要求的一致性的保证，当我们停下对数据库的修改，经过一段时间之后能够在各个节点上读取到相同的数据结果。

但是最终一致性对于应用开发者是一个很困难处理的问题。加大了应用系统的复杂度。

一致性的强度变化

一致性强度.png

• 读自己写（能够读到自己写的东西）：
  简单实现方式：

  • 如果一份数据可能被用户修改过，就从leader 读取，否则从follower 读取
  • 通过最后修改时间判断，在最后修改“一分钟”之内的数据，从leader读取，否则从follower读取

• 单调读（在读到新的数据之后，就不会再读到老数据）：

  • 简单的实现方式：使用户一直从同一个备份节点读取

• 一致性前缀读 （因果读写）：

  如果一系列的写入操作有一个确定的写入顺序，则任何读取的人会发现同样的写入顺序（举例）

  • 任何具有因果关系的写入，需要写入同一个partition.
  • 单主情况下的数据请求都走主节点。

• 全序列广播：

  保证在主节点上的消息在所有的节点上都有，并且在各个节点顺序上保证一致。
  满足特定使用情况下能够达到 “可线性化”。

  将读取作为一个操作，写入到日志，等待日志更新提交成功的返回。（这个不好理解，可能需要讲完一致性协议再考虑）

total_order_boardcast.png

如何实现全局顺序广播：
使用节点间的共识
- 对于顺序达成一致
- 对于数据达成一致
- 对于是否可接收达成一致

共识（consensus）

共识是指多个节点能够对一些事情达成一致

consensus means getting several nodes to agree on something

常用的模式是指：一个或多个节点提出提议，一致性算法决定采纳哪个提议。

The consensus problem is normally formalized as follows: one or more nodes may propose values, and the consensus algorithm decides on one of those values.

如何达成共识：

使用一个节点作为唯一的裁决者，由裁决者节点决每个提议。

如何在任意一个节点可能存错误的情况下达成共识，这个节点可能失败后永远不会恢复过来。

以主从结构分布式系统为例：如果主节点发生失败，整个集群就不可用，虽然可以通过从节点变成主节点来实现，但是可能会发生脑裂，即集群中出现多个节点都认为自己是leader，依然可能破坏共识而造成不一致。这个逻辑链条就变成我希望达成一致性，需要一个裁决的节点，但是为了获取一个裁决节点我又需要一个共识算法。

面对任意节点可能会失败的情况，通过单一节点去达成一个集群的共识是不可能的。

使用多数裁决的方式是可以达到集群裁决的一致性。只要半数（指定个数）的节点能够工作，就能够达到一致性。

主从节点的结构裁决算法，为了解决脑裂的问题引入了一个叫做周期序列号的。其不追求永远的共识，但是最求保证在一个周期内的共识（下个周期这个共识可能就会改变）。

当选举一个新的leader 的时候，需要提一个新的周期序列号，通过全局投票的方式，决定在这个序列号所代表的周期内谁是主节点。这个序列号是单调递增的。每个节点达成主节点的前提是，其问讯集群中的所有成员只有多数达到了一致才能认为自己是主节点。

Raft 协议就是一个这样使用可容错的一致性算法达来达到全局广播一致性的算法。

raft 一致性协议的原理

• raft选主

在任意的时间，每一个服务器一定会处于以下三种状态中的一个：领导人、候选人、追随者。一个集群内只有一个领导者。追随者们是被动的：他们不会发送任何请求，只是响应来自领导人和候选人的请求。领导人来处理所有来自客户端的请求，满足一定提交下一个节点会成为候选人状态，可以参与竞选成为一个新的领导人的。（如下图）

raft选主.png

Raft 服务器间的通讯仅需要 2 种 RPC。RequestVote RPC 是候选人在选举过程中触发的，AppendEntries RPC 是领导人触发的，为的是复制日志条目并且提供一种心跳（heartbeat）机制。主节点正常的时候会向所有追随者周期性发送心跳（heartbeat，不带有任何日志条目的 AppendEntries RPC）来保证它们的领导人地位。如果一个追随者在一个周期内没有收到心跳信息，就叫做选举超时（election timeout）, 然后它就会假定没有可用的领导人并且开始一次选举来选出一个新的领导人（并发RequestVote给所有集群中节点）。收到大多数节点投票的候选人会成为新的领导人。一旦有一个候选人赢得了选举成为领导人，它会像其他服务器发送心跳信息来建立自己的领导地位并且组织新的选举。

因此时间被分为一个个的任期（term），每一个任期的开始都是领导人选举。在成功选举之后，一个领导人会在任期内管理整个集群直到下次新的选举。

周期性阶段

term 的使用原则
由于通讯延时或者异常的问题，有的节点认为自己处于term1，有的节点认为自己处于term2。

在服务器之间进行通信时，会互相交换当前任期号；如果一台服务器的当前任期号比其它服务器的小，则更新为较大的任期号。如果一个候选人或者领导人意识到它的任期号过时了，它会立刻转换为追随者状态。如果一台服务器收到的请求的任期号是过时的，那么它会拒绝此次请求。

• 2 日志复制

一旦选出了领导人，它就开始接收客户端的请求。每一个客户端请求都包含一条需要被复制的执行的命令。领导人把这条命令作为新的日志条目加入到它的日志中去，然后并行的向其他服务器发起 AppendEntries RPC ，要求其它服务器复制这个条目。当这个条目被安全的复制之后，领导人会将这个条目应用到它的状态机中并且会向客户端返回执行结果。如果追随者崩溃了或者运行缓慢或者是网络丢包了，领导人会无限的重试 AppendEntries RPC直到所有的追随者最终存储了所有的日志条目。

日志复制

日志由有序编号的日志条目组成。每个日志条目包含它被创建时的任期号（每个方块中的数字），并且包含用于状态机执行的命令。每个日志条目存储着一条被状态机执行的命令和当这条日志条目被领导人接收时的任期号，每个日志条目也包含一个整数索引来表示它在日志中的位置。

领导人决定什么时候将日志条目应用到状态机是安全的；这种条目被称为可被提交（commited）。Raft 保证可被提交（commited）的日志条目是持久化的并且最终会被所有可用的状态机执行。一旦被领导人创建的条目已经复制到了大多数的服务器上，这个条目就称为可被提交的领导人日志中之前的条目都是可被提交的（commited）。领导人跟踪记录它所知道的被提交条目的最大索引值，并且这个索引值会包含在之后的 AppendEntries RPC 中（包括心跳 heartbeat 中），为的是让其他服务器都知道这条条目已经提交。一旦一个追随者知道了一个日志条目已经被提交，它会将该条目应用至本地的状态机。

• 领导人的变更：

  但是当领导人崩溃（重新选举）会导致日志不一致，比如领导人还在复制日志的时候，发生奔溃造成日志复制的缺失或者是从节点之间日志不一致。

  为解决这个问题，新的领导者需要保证追随者的日志同自己的一致，即领导人需要找到追随者同它的日志一致的地方，然后删除追随者在该位置之后的条目，然后将自己在该位置之后的条目发送给追随者。

  日志可提交

同时为了保证已经被提交的日志的数据安全，raft算法还需要提供两个额外的选主限制来保证已提交的日志的安全性。

• Raft 使用投票的方式来阻止没有包含全部日志条目的服务器赢得选举。RequestVote RPC 提交的时候会包含候选人的日志信息，如果它自己的日志比候选人的日志要新，那么它会拒绝候选人的投票请求。Raft 通过比较日志中最后一个条目的索引和任期号来决定两个日志哪一个更新。如果两个日志的任期号不同，任期号大的更新；如果任期号相同，更长的日志更新

• Raft 从来不会通过计算复制的数目来提交之前人气的日志条目。领导人只会提交自己任期内的新增日志。但是领导人依然会复制前任的日志给各个从节点，但是不会直接提交，只是会在自己任期内有日志产生的时候才把前一个日志一起提交，所以之前任期内的日志条目是被间接的提交。

不能直接提交上个任期日志的原因可以看下图：

提交之前任期的日志条目

如图的时间序列说明了为什么领导人不能通过之前任期的日志条目判断它的提交状态。（a）中的 S1 是领导人并且部分复制了索引 2 上的日志条目。（b）中 S1 崩溃了；S5 通过 S3，S4 和自己的选票赢得了选举，并且在索引 2 上接收了另一条日志条目。（c）中 S5 崩溃了，S1 重启了，通过 S2，S3 和自己的选票赢得了选举，并且继续索引 2 处的复制，这时任期 2 的日志条目已经在大部分服务器上完成了复制，但是还并没有提交。如果在（d）时刻 S1 崩溃了，S5 会通过 S2，S3，S4 的选票成为领导人，然后用它自己在任期 3 的日志条目覆盖掉其他服务器的日志条目。然而，如果在崩溃之前，S1 在它的当前任期在大多数服务器上复制了一条日志条目，就像在（e）中那样，那么这条条目就会被提交（S5 就不会赢得选举）。在这时，之前的日志条目就会正常被提交。

实践中会有很多别的方法来实现上个任期日志的尽早提交，比如选举完成后领导者模拟一个空的日志条目提交的流程，以达到间接提交上个周期日志的的目的。或者是和集群内的大多数节点做一次rpc 通讯（其实就是为了证明当前自己还是集群最新的leader），如果成功就提交上一个任期内的日志。

集群成员变化

截止到目前，我们都假定集群的配置（加入到一致性算法的服务器集合）是固定的。在实际中，我们会经常更改配置，（添加/摘除额外的节点）

为了让配置修改机制能够安全，那么在转换的过程中在任何时间点两个领导人不能再同一个任期被同时选为领导人。不幸的是，服务器集群从旧的配置直接升级到新的配置的任何方法都是不安全的，一次性自动的转换所有服务器是不可能的，所以集群可以在转换的过程中划分成两个单独的组（如 图 -10 所示）。

复制状态

通过一致性算法统一更新配置

领导人首先在它的日志中创建 C(old,new)， C(old,new) 是指即包含new 的所有节点，又包含old 所有节点 配置条目并且将它提交到 C(old,new)。然后它创建 C(new) 配置条目并且将它提交到使用新配置的大部分机器上。如果在 C(old,new)的过程中主节点挂了，新选举出来的领导者必然是有 C(old,new) 这条日志的。

配置更新流程

raft 协议 （主从结构共识协议）的限制

所有的写入请求必须经过leader, 每次请求这个leader和至少半数的节点通讯，leader 就成为了这个系统的性能瓶颈。在单leader节点的边界，由于吞吐量的瓶颈，整个系统可能会频繁的选主，易造成雪崩效应。

广播顺序一致性如何变成强一致性

对于强一致性，要求当前读取任意一个节点就能获取当前集群最新的状态。类似raft这种日志广播分发的算法，直接读取从节点，只能保证日志顺序，并不能获取到整个集群最新的已提交的日志。一般的解决思路是从主节点读取，但是当读取主节点的时候，并不一定也是最新提交的日志，因为在读取的时候所谓的主节点可能已经不是集群当前的主节点了（可能恰巧这个时候发生了新的选主）。解决的办法是提交一个读取的请求，即将一个读请求变成一个写请求。当这个读请求变成commited 状态时则表示，当前系统的最新状态就是这个读commit所对应的状态。（即这个读请求在集群里面走了一圈，达成共识当前最新的数据状态是怎么样子的）这个也是满足cap原理的。

参考文档

raft paper 翻译
Designing Data-Intensive Applications