Notes on Consistency: Raft & ZooKeeper and Potpourri
Notes on Consistency: Raft & ZooKeeper
Raft 协议按照论文实现的话，是能保证 Linearizable 的，这是最强的一致性模型，在整个系统中，operation 有序并原子的完成，每个操作都像瞬间发生一样，在这个时间点之后看到这个对象都是写入的值，在这个点之前看到的都是前一个值。
以上只是一个我自己理解的很模糊的说法，实际内容可以参考：
实际上，在了解 Wing&Gong 算法之类的判别法之前，我们可以尝试看看上面的 history4:
- Wx0 在 Rx1 Rx2 之前发生，这意味着如果系统是 Linearizable 的，读取之前就发生了 Wx1 和 Wx2
- C2 Rx1 之后 Rx2, 没有重叠的情况下，2 应该在 1之后被写入
你可能会在两种地方看到 Linearizable ：
- 你在单机的多核处理器中实现了一个 Queue, 需要判断在多核处理器下访问它的语义是否是 Linearizable 的
- 你实现了一个 Raft, 要来判断他是否满足 Linearizable
Linearizable 实现的代价很高，当你实现一个基础的 kv raft 的时候，你得保证：
- Raft 把你写消息广播到了大部分机器上
- 在你读取的时候，Raft Leader 仍然是大部分集群的 Leader
- …
在系统中，我们可能需要 Linearizable 的协调单点，来完成这样的语义。
Sequential Consistency
… 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.
以上是 Sequential Consistency 的定义，它保证了操作是 total order 的，并且在你读到一个值之后，你就再也不会读到它之前的值了。
但是，有一点需要注意的是，有的时候你并没有“同时”这个保证：Linearizable 系统中，A写入了，B同时一定就能读到（假设没有其他的 Writer）。但是 Sequential Consistency 的系统中，你可以保证 Total Order，但不能保证这一点。
你如果了解过 memory order 的话，可能会比较熟悉 acquire release acq_rel seq_cst, 在 stackoverflow 有后两个的讨论，或许能帮你更加了解：
ZooKeeper 提供一种类似 Sequential Consistency 的定义，它称为 Linearizable-Write
- 写会被有序全局广播
- 读会读 local-cache
- 通过 watch 来看等待通知
可以参见我之前翻译的 Paper
验证
Jepsen 根据调用的图提供了验证方式，etcd 等都用 Jepsen 来做一些一致性验证和混沌情况下的一致性验证，可以看看 Jepsen 对应的文档：
多个变量
当你要处理多个变量的“一致性” 的时候，你可能需要的是数据库的一致性。
Generalized Isolation Level Definitions 这篇论文介绍了包括 SI 下它的详细定义，PostgreSQL 的 SSI 也是在这基础上实现的。
之前做过一个相关的 slide: https://docs.google.com/presentation/d/1FrW41bGt6iSjxQwbYu0YulYR-SoV2iiqyKpDV4SPxxc/edit?usp=sharing
实际上，Jepsen 的 elle 也对这种情况进行了实验：