一致性问题总结

标签：分布式系统首次发布：2023-11-28最近修改：2023-11-28

一致性模型

1. 严格一致性

严格一致性也称强一致性，原子一致性或者是线性一致性，是要求最高的一致性模型，CAP 中的 C 一般就指它。严格一致性的要求具体如下。

  1. 任何一次读都能读到某个数据的最近一次写的数据。
  2. 系统中的所有进程，看到的操作顺序，都与全局时钟下的顺序一致。

对于严格一致性的存储器，要求写操作在任一时刻对所有的进程都是可见的，同时还要维护一个绝对全局时间顺序。一旦存储器中的值发生改变，那么不管读写之间的事件间隔有多小，不管是哪个进程执行了读操作，也不管进程在何处，以后读出的都是新更改的值。同样，如果执行了读操作，那么不管后面的写操作有多迅速，该读操作仍应读出原来的值。

传统意义上，单处理机遵守严格一致性。但是在分布式计算机系统中为每个操作都分配一个准确的全局时间戳是不可能实现的。因此，严格一致性，只是存在于理论中的一致性模型。

按照定义来看，强一致模型是可组合的，也就是说如果一个操作由两个满足强一致的子操作组成，那么父操作也是强一致的。强一致提供了一系列很好的特性，也非常易于理解，但问题在于它基本很难得到高效的实现。因此，研究人员放松了要求，从而得到了在单机多线程环境下实际上普遍存在的顺序一致性模型。

2. 顺序一致性

顺序一致性比严格一致性要求弱一点，但也是能够实现的最高级别的一致性模型。因为全局时钟导致严格一致性很难实现，因此顺序一致性放弃了全局时钟的约束，改为分布式逻辑时钟实现。顺序一致性是指所有的进程都以相同的顺序看到所有的修改。读操作未必能够及时得到此前其他进程对同一数据的写更新，但是每个进程读到的该数据不同值的顺序却是一致的。

可见，顺序一致性在顺序要求上并没有那么严格，它只要求系统中的所有进程达成自己认为的一致就可以了，即“错的话一起错，对的话一起对”，只要不违反程序的顺序即可，并不需要整个全局顺序保持一致。

下面是严格一致性和顺序一致性的对比：

image-20231127213619096

在严格一致性中，因为每个读操作都读到了该变量最新写的结果，同时两个进程看到的操作顺序与全局时钟的顺序一样，都是 Write(y，2)→Read(x，4)→Write(x，4)→Read(y，2)。

image-20231127212845940

在顺序一致性中，因为两个进程 P1、P2 的一致性并没有冲突。从这两个进程的角度来看，顺序应该是这样的（这里假设所有的读写操作都是原子性的不可再分割）：Write(y，2)→Read(x，0)→Write(x，4)→Read(y，2)，每个进程内部的读写顺序都是合理的（P2 先执行，因此看不到任何 P1 做的修改；P1 执行时 P2 已经执行完毕，因此 P2 做的修改 P1 是可以看到的），但是显然这个顺序与全局时钟下看到的顺序并不一样。

3. 因果一致性

因果一致性模型通常用于分布式系统中来确保写操作和读操作都遵守因果关系，简单地说，因果关系可以描述成如下情况。

  • 本地顺序：本进程中，事件执行的顺序即为本地因果顺序。
  • 异地顺序：如果读操作返回的是写操作的值，那么该写操作在顺序上一定在读操作之前。
  • 闭包传递：与时钟向量里面定义的一样，如果 a→b 且 b→c，那么肯定也有 a→c。

否则，操作之间的关系为并发关系。对于具有潜在因果关系的写操作，所有进程看到的执行顺序应相同。并发写操作（没有因果关系）在不同主机上被看到的顺序可以不同。

text
P1   W(x)aP2           R(x)a W(x)bP3                       W(x)cP4                             R(x)a R(x)b R(x)cP5                             R(x)a R(x)c R(x)bP6                             R(x)c R(x)a R(x)b

在上面的结果中，P4、P5 和 P6 返回的结果都是满足因果一致性的。下面是我的分析：

  1. P1 进程执行了一个写操作 Write(x,a)。
  2. P2 进程由于读取到 x 的值为 a，说明 P2 进程的读操作和 P1 进程的写操作是有因果关系的，即 P2 进程的读操作一定在 P1 进程的写操作之后发生。
  3. 在 P2 进程内部对 x 数据的读写操作也有因果关系（属于上面提到的本地顺序）。也就是在 P2 内部，对 x 的写操作 Write(x,b)一定发生在读操作 Read(x,a)之后。
  4. 又根据因果关系具有传递性，所以对 x 数据的写操作一定是先将 x 写为 a 再将 x 写为 b 这一顺序。
  5. 那么对 x 数据的读操作要满足因果一致性也必需先读到 x 数据为 a，再读 x 数据为 b。
  6. P3 进程将 x 的值改为 c，尽管在时间线上，此时 x 的值已经为 c，但是由于数据同步具有延时性，当在分布式系统中数据还没有完全同步完成时，所以其他进程依然可能会读取到 x 的值为 a 或 b（即使此时 x 的值为 c）。
  7. 所以，对于写操作 Write(x,c)和写操作 Write(x,b)之间是并发关系，并且写操作 Write(x,c)和写操作 Write(x,a)之间也是并发关系；而写操作 Write(x,a)和写操作 Write(x,b)之间是因果关系。
  8. 因此，其他进程在读取 x 的值的时候，只要是先读取到 a 再读取到 b 那么就满足因果一致性，至于 c 的顺序无所谓。
  9. 从 P4、P5 和 P6 的结果上来看，P4 的读取结果最符合实际情况，但是 P5 和 P6 的读取结果也符合因果一致性模型。

4. FIFO 一致性

如果说操作的历史等同于以某种单一原子顺序发生的历史，但对调用和完成时间没有说明，那么就可以获得称为 FIFO 的一致性模型。这个模型很有意思，一致性要么比你想象的强得多，要么弱得多。

  • FIFO 一致性可以很弱，由于它没有按时间或顺序排列界限，因此这就好像消息可以任意发送到过去或未来。例如，有如下所示的这样一个程序：

    text
    x = 1x = x + 1print(x)

    在这里，我们假设每行代表一个操作，并且所有的操作都成功。因为这些操作可以以任何顺序进行，所以可能打印出 nil、1 或 2。因此，一致性显得很弱。

  • FIFO 一致性可以很强，因为它需要一个线性顺序。例如，下面的这个程序：

    text
    if x = 3;print(x)if x = nil;x = 1if x = 1;x = 2if x = 2;x = 3

    它可能不会严格地以我们编写的顺序发生，但它能够可靠地将 x 从 nil→1→2，更改为 3，最后打印出 3，具有很强的一致性。

5. 最终一致性

理念：不保证在任意时刻任意节点上的同一份数据都是相同的，但是随着时间的迁移，不同节点上的同一份数据总是在向趋同的方向变化。

简单说，就是在一段时间后，节点间的数据会最终达到一致状态。不过最终一致性的要求非常低，比如我记录操作日志，然后在副本故障了 100 天之后手动在副本上执行日志以达成一致，也算是符合最终一致性的定义。所以有人说最终一致性就是没有一致性，因为没人可以知道什么时候算是最终。

最终一致性的分支很多，下面都是它的变种：

  • Causal consistency（因果一致性）
  • Read-your-writes consistency （读己所写一致性）
  • Session consistency （会话一致性）
  • Monotonic read consistency （单调读一致性）
  • Monotonic write consistency （单调写一致性）

除此之外，BASE 理论中的 E 就是最终一致性的意思。

复制状态机

基本思想：一个分布式的复制状态机系统由多个复制单元组成，每个复制单元均是一个状态机，它的状态保存在一组状态变量中。状态机的状态能够并且只能通过外部命令来改变。

上面提到的“一组状态变量”通常是基于操作日志来实现的。每一个复制单元存储一个包含一系列指令的日志，并且严格按照顺序逐条执行日志上的指令。因为每个状态机都是确定的，所以每个外部命令都将产生相同的操作序列（日志）。又因为每一个日志都是按照相同的顺序包含相同的指令，所以每一个服务器都将执行相同的指令序列，并且最终到达相同的状态。

综上所述，在复制状态机模型下，一致性模型的主要工作就变成了如何保证操作日志的一致性。只要操作日志一致了，那么每个副本中的数据也就一致了。

复制状态机是通过使用一致性模型保证日志的一致性从而保证数据的一致性，那为什么不直接使用一致性模型保证数据的一致性？

在分布式系统中，通过复制日志来同步状态是实现高可用性和容错的一种常见方法。日志是一种记录状态变化的顺序列表，状态机通过复制和应用这个日志来保持一致性。日志的使用并不是多此一举，而是有以下几个原因：

  1. 顺序保证：分布式系统中的不同副本可能会以不同的顺序收到更新请求。日志提供了一个全局的操作顺序，确保所有副本以相同的顺序应用这些更新，这是保持状态一致性的关键。
  2. 容错能力：一致性协议如 Raft 通过日志复制来处理节点故障。即便某些节点宕机，只要多数节点上的日志是一致的，系统就可以从这些节点的日志中恢复到一个一致的状态。
  3. 复制延迟：在现实世界中，网络延迟和分区是常有的事。日志允许各个副本在不同的时间应用更新，但最终仍能达到一致的状态。
  4. 易于理解和实现：基于日志的复制模型提供了一个清晰的框架，开发人员可以围绕它设计和实现一致性保证机制。
  5. 状态和操作的分离：日志中记录的是状态变更的操作，而不是状态本身。这意味着即使状态机本身非常复杂，日志中的操作依然可以是简单的，这样可以简化状态同步的过程。
  6. 历史记录：日志提供了状态变化的完整历史，这对于故障恢复、系统审核以及调试等都是非常有用的。
  7. 性能优化：在某些实现中，通过日志复制可以实现读写分离，读操作可以在任何副本上执行，而写操作则通过日志复制来保证一致性。这可以在不牺牲一致性的情况下提高系统的性能。

因此，虽然在第一眼看来直接保证数据的一致性似乎更直接，但是在分布式系统中，日志的使用是为了保证系统的顺序一致性、容错性和可扩展性，这对于构建可靠的分布式系统来说是至关重要的。

复制状态机的运行示意图如下所示：

image-20231128171510815

具体过程如下：

  1. 客户端发起请求：客户端发起一个状态变更的请求到服务器，这个请求可以是一个命令，要求修改状态机中某个变量的值。
  2. 日志复制：服务器上的一致性模块负责接收外部命令，然后追加到自己的操作日志中。它与其他服务器上的一致性模块进行通信以保证每一个服务器上的操作日志最终都以相同的顺序包含相同的指令。这通常通过一个一致性算法来实现，如 Paxos 或 Raft。一旦请求的顺序达成共识，服务器会将命令写入到本地日志中，步骤(2)下方的“Log”部分显示了已经记录的状态变更操作，例如“x→3”表示将变量 x 的值设为 3。
  3. 状态机执行操作：接下来服务器中的状态机执行日志中记录的操作，这导致状态机的状态被更新，如图中的 State Machine 部分所示。所有复制的状态机都会执行相同的日志操作序列，因此它们的状态会保持一致。
  4. 响应客户端：最后作为响应，执行操作的结果被发送回客户端。

需要注意的是，指令在状态机上的执行顺序并不一定等同于指令的发出顺序或接收顺序，即一个服务器可能先收到了"指令 B"，而另一个服务器可能先收到了"指令 A"。这造成了同一组指令在不同服务器上有不同的初始接收顺序，而共识算法的作用就是达成一致的指令执行顺序。