Skip to content

Latest commit

 

History

History
153 lines (94 loc) · 12.5 KB

线性一致性.md

File metadata and controls

153 lines (94 loc) · 12.5 KB
Raw

什么是线性一致性

分布式系统的 CAP 理论

CAP 理论主张基于网络的数据共享系统，都最多只能拥有以下三条中的两条：

  • Consistency：在分布式存储系统中，通常以多副本冗余的方式实现数据的可靠存储。同一份数据的多个副本必须保证一致，而数据的多个副本又存储在不同的节点中，这里的分布式一致性问题就是存储在不同节点中的数据副本（或称为变量）的取值必须一致。不仅如此，因为变量是可变的，变量会有多次取值，变量的多次取值构成一个序列，分布式一致性还要求多个节点对该变量的取值序列必须一致。
  • Available：对数据更新具备高可用性
  • Partitions tolerance：指容忍网络分区

实际上 CAP 并不是完全对立的，非此即彼的关系，CAP 三个概念都有一定的度，比如说一致性有线性一致性、最终一致性等说法。

一致性

一致性模型确定了编写系统的程序员与系统之间的某种协议，如果程序员遵守了这种协议，那么这个系统就能提供某种一致性。常见的一致性模型有：

  • Strict Consistency
  • Linearizability (Atomic Consistency)
  • Sequential Consistency
  • Casual Consistency
  • Serializability
  • ……

需要注意的是这里的系统指并发系统，分布式系统只是其中的一类。

顺序一致性（Sequential Consistency）

Lamport 在论文《How-to-Make-a-Multiprocessor-Computer-That-Correctly-Executes-Multiprocess-Programs》中对其这样定义:

"A multiprocessor system is sequentially consistent if the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program."

简单来说，顺序一致性保证了两点：

  1. 每个 Processer 按照程序指定的顺序（program order）执行操作。（单个 Processer 视角）
  2. Processor 并行交错的情况下，程序执行顺序可以任意，==但所有 Processer 看到的执行顺序必须一致==，即所谓的顺序一致性。（多 Processer 构成的程序全局视角）

举个例子（注意下图中的顺序不是时间序）：

img

  • 图 (a) 中所示共 4 个 Processer，P1、P2 分别对 x 写了 a 和 b，P3 和 P4 分别都读 x 的值，都按顺序先读出 x=b 再读出 x=a，满足顺序一致性。
  • 图 (b) 中 P3 按顺序先读到了 x=b，然后读到了 x=a，P4 则相反，所以不满足顺序一致性，因为 P3 和 P4 看到的顺序不一样。

Tips:

  • 图 a 中的执行顺序可以是：P2 W(x)b -> P3 R(x)b -> P4 R(x)b -> P1 W(x)a -> P4 R(x)a -> P3 R(x)a
  • 图中没有画出单个 Processer 执行多个操作，如果有，这多个操作在所有 Processer 看来也应该是有序的。(即如果 P1 有两个操作，先 W(x)a 再 W(x)c，那么所有 Processer 都必须看到的是这个顺序)

线性一致性（Linearizable Consistency）

Sequential Consistency 仅定义了每个 Processor 看到的程序执行顺序必须是一致的，==并没有限制在多 Processor 并行交叉执行的情况下，某个 Processor 上某一操作必须在另外一 Processor 的某个操作之前或之后==，意即 ==Sequential Consistency 并不关心时间顺序==。==Linearizability 则关心时间顺序==，它在 Sequential Consistency 模型基础上，为每个操作增加了时间戳，并定义：如果操作 1 的时间戳小于（意即早于）操作 2 的时间戳，那么操作 1 应该在操作 2 之前完成。因此 Linearizable Consistency 一致性要求强于 Sequential Consistency。

图中 (a) 满足 Sequential Consistency 但不满足 Linearizability，因为 write(x=a) 操作先于 write(x=b)，而 read 操作却先读到 x=b 的值。

背景知识 要了解线性一致性，我们需要一种表示方法描述分布式系统的行为。分布式系统可以抽象成几个部分:

  • Client
  • Server
  • Events
    • Invocation
    • Response
  • Operations
    • Read
    • Write

一个分布式系统通常有两种角色，Client 和 Server。Client 通过发起请求来获取 Server 的服务。一次完整请求由两个事件组成，Invocation（以下简称 Inv）和 Response（以下简称 Resp）。一个请求中包含一个 Operation，有两种类型 Read 和 Write，最终会在 Server 上执行。

论文《Linearizability: A Correctness Condition for Concurrent Objects》中，使用一个 FIFO 队列来解释 Linearizability。即使多个进程在同一队列上进行操作，也必须满足队列 FIFO 特性。E(x) A 表示进程 A 执行元素 x 的入队列操作，D(x) B 表示进程 B 执行出队列操作，得到元素 x。

图中每一个线段的起始和结束分别表示 Inv 和 Resp，实际上真正的读写操作可以发生在这段时间内的任意时间点。

img

  • (a) (c) 满足线性一致性；
  • (b) 不满足线性一致性，因为 E(y) B 一定发生在 E(x) A之后，即 E(x) A happen before E(x) B，而 D(y) A 却先读到了 y，而不是 x；
  • (d) 不满足线性一致性，因为 y 出队了两次。

上面有提到过，==实际上真正的读写操作可以发生在 Inv 和 Resp 这段时间内的任意时间点==，看下面这个例子

img

Client A B C 满足线性一致性很好理解，Client D 的读跨越了很长时间，它的起始时间比 Client B 开始写 2 的时间要早，比 Client B 结束写 2 的时间要晚，最后读到的数据是 1，因为读可以发生在任何时间点，所有也是满足线性一致性的。同理，A 读到的值也可以是 2。C 就不太一样了，C 只有读到了 2 才能满足线性一致。因为 “x R() C” 发生在 “x Ok() B” 之后（happen before)，可以推出 R 发生在 W 之后，那么 R 一定得读到 W 完成之后的结果 2。

Summary

《Distributed Computing，Principles, Algorithms, and Systems》一书中有如下例子：

image-20220708010544932

image-20220708010617294

分布式系统中的线性一致性读

什么是线性一致读？所谓线性一致读，一个简单的例子就是在 t1 的时刻我们写入了一个值，那么在 t1 之后，我们一定能读到这个值，不可能读到 t1 之前的旧值 （想想 Java 中的 volatile 关键字，说白了线性一致读就是在分布式系统中实现 Java volatile 语义）。

==即每次读都要读到”最新“的数据，对于最新的定义，实际上是要求能读到 happen before 读请求开始（即 Inv）之前的数据，而在 Inv 和 Resp 之间的更改，可以读到也可以读不到，即上面的 Client D 的情况==。

下面以 Raft 的实现为例，说明线性一致性读的实现，首先有以下两个思路：

  1. 既然 Raft 是强主的，是否可以直接读 Leader 呢？结论是不行，因为当前认为自己是 Leader 的节点不一定真的是当前的 Leader，也就不一定有最新的数据。
  2. 那既然不能确认当前 Leader 就是 Leader，那就读请求也走一遍 Raft 复制协议，这样如果能读到，肯定是在 Leader 上读的。这确实是可行的方案，但是因为走 Raft 协议的网络开销和日志开销，性能肯定不会好。

基于上面的两个方案都不可行，业界主要有以下两个实现：

ReadIndex Read

  1. Leader 将自己当前 Log 的 commitIndex 记录到一个 Local 变量 ReadIndex 里面；
  2. 接着向 Followers 发起一轮 heartbeat，如果半数以上节点返回了对应的 heartbeat response，那么 Leader 就能够确定现在自己仍然是 Leader；
  3. Leader 等待自己的状态机执行，直到 applyIndex 超过了 ReadIndex，这样就能够安全的提供 Linearizable Read 了，也不必管读的时刻是否 Leader 已飘走；
  4. Leader 执行 read 请求，将结果返回给 Client。

其中有两个关键点需要注意：

  • 记录 ReadIndex，并等到 applyIndex 超过了 ReadIndex
  • 通过心跳确认当前节点是 Leader；

需要注意的是通过心跳的方式也只能确定在其他节点收到心跳包的时刻当前节点仍然是 Leader，并不表示心跳包返回以后也就是真正读数据的时候当前节点还是Leader，那又是如何保证读到最新的数据的呢？我们上面说过，线性一致性读只要求一定能读到 happen before Inv 之前的数据，而 Inv 和 Resp 之间的数据，能不能读到都满足线性一致性的。

在这里，Inv 就相当于收到读请求的时刻，即记录 ReadIndex 的时刻，Resp 就相当于返回数据给 Client 的时刻，既然如此，等到日志 applyIndex 超过了 ReadIndex 之后，就一定能读到”最新“的数据了（不是一定要等到 applyIndex == ReadIndex）。另外，读的时刻并不要求当前节点还是 Leader，因为 Raft 的commitIndex 之前的数据一定是持久化了的，不会再被修改的，所以即使当前节点不是 Leader 也没有关系。

上面的 ReadIndex 都是在 Leader 上的，实际上在 Follower 也一样，只需要请求 Leader 把当前的 commitIndex 发送给自己就行了，同样 Leader 也要通过心跳确认自己是 Leader，详细流程请查看参考资料[5]。

Lease Read

  • Lease Read 与 ReadIndex 类似，但更进一步，不仅省去了 Log，还省去了网络交互，它可以大幅提升读的吞吐也能显著降低延时。
  • 基本的思路是 Leader 取一个比 election timeout 小的租期（最好小一个数量级），==在租约期内不会发生选举，这就确保了 Leader 不会变，所以可以跳过 ReadIndex 的第 3 步==，也就降低了延时。可以看到 Lease Read 的正确性和时间是挂钩的，因此时间的实现至关重要，如果时钟漂移严重，这套机制就会有问题。

Wait Free

到此为止 Lease 省去了 ReadIndex 的第 2 步，实际能再进一步，省去第 3 步。这样的 LeaseRead 在收到请求后会立刻进行读请求，不取 commit index 也不等状态机。由于 Raft 的强 Leader 特性，在租期内的 Client 收到的 Resp 由 Leader 的状态机产生，所以只要状态机满足线性一致，那么在 Lease 内，不管何时发生读都能满足线性一致性。有一点需要注意，只有在 Leader 的状态机应用了当前 term 的第一个 Log 后才能进行 LeaseRead。因为新选举产生的 Leader，它虽然有全部 committed Log，但它的状态机可能落后于之前的 Leader，状态机应用到当前 term 的 Log 就保证了新 Leader 的状态机一定新于旧 Leader，之后肯定不会出现 stale read。

TIPS:

为什么不用等 commit index apply？因为只要读写都发生在 Leader 上，对于写请求，Leader apply 完之后才回复给客户端完成，这样读实际上是和写在时间上有交集的，不需要读到也能保证线性一致性。

Links

  1. https://www.jianshu.com/p/2ca07befc9a1
  2. https://www.jianshu.com/p/3697fd5797cc
  3. https://pingcap.com/blog-cn/linearizability/
  4. https://mp.weixin.qq.com/s/iOe1VjG1CrHalr_I1PKdKw
  5. https://mp.weixin.qq.com/s/pmbI_FyOJJyvg008amPutA
  6. https://cn.pingcap.com/blog/linearizability-and-raft
  7. https://zhuanlan.zhihu.com/p/47117804
  8. Herlihy, Maurice P., and Jeannette M. Wing. "Linearizability: A correctness condition for concurrent objects." _ACM Transactions on Programming Languages and Systems (TOPLAS)_12.3 (1990): 463-492.
  9. Lamport, Leslie. "How to make a multiprocessor computer that correctly executes multiprocess progranm." IEEE transactions on computers 9 (1979): 690-691.
  10. Whang, Kyu-Young, Brad T. Vander-Zanden, and Howard M. Taylor. "A linear-time probabilistic counting algorithm for database applications." _ACM Transactions on Database Systems (TODS)_15.2 (1990): 208-229.