1. 顺序与因果关系
违背因果关系的例子：
- 不可重复读：
- 现象：读到了某个时间点之后的内容
- 解决：从一致性快照读，快照创建时刻之前的数据可见，之后的不可见，满足因果一致
- 幻读：
- 现象：写时读到了某个时间点之后的内容（即之前的读无效）
- 解决：可序列化的快照隔离，追踪因果依赖关系，以满足因果一致
若系统服从因果关系规定的顺序（发出消息一定在收到消息之前），则它支持因果一致性。
可线性化：操作存在全序关系，所有操作都有先后顺序。（系统好像只有一个副本且操作原子）
因果关系：若两个事件确定有因果关系，则它们可被排序，否则它们是并发操作，不能被排序
易知，可线性化一定保证因果关系，反过来不行。
可线性化并非实现保证因果关系的唯一方法，还有其它的实现，其能提供比可线性化更好的性能。
2. 序列号排序
由于追踪所有的因果关系不现实，因此可通过序列号/时间戳排序事件。
时间戳通常是递增的逻辑时钟（例如通过算法产生的一个递增的序列号）。这样序列化保证了全序关系，也因此保证了因果关系。
也可以按照因果关系创建序列号，即若A在B前，则A的序列号一定比B小，而并发操作的序列可以是任意的。
2.1. 非因果序列号生成器
- 节点独立产生序列号，但序列号不相同。（不同节点的序列号顺序无法比较）
- 请求捎带墙上（物理）时间戳。（时钟偏移、漂移导致无法正确比较）
- 不同节点预分配序列号范围，在范围内分配，若不够再开辟新的。（一定保证先出现的在小范围，后出现的在大的范围内，否则无法比较）
多主/无主/本身分区系统下，上述的生成器不能保证因果一致。
2.2. 全序逻辑的Lamport时间戳
数据结构：由进程标识和进程单独维护的递增时间戳构成的数对$(P_{i}, t_{i})$
比较规则：给定$L_1 = (P_1, t_1)$和$L_2 = (P_2, t_2)$，下面比较规则是全序的
- 若$t_1 < t_2$，则$L_1 < L_2$
- 若$t_1 = t_2$，则若$P_1 < P_2$，则$L_1 < L_2$
与因果顺序保持一致（维持偏序关系）：
-
客户端和服务端都维护自己所见的时间戳最大值$L_i = (P_i, t_i)$
-
每次请求捎带计数器值$t_i$
-
收到请求若$t_{recv} > t_i$，则更新$t_i = t_{recv}$
书中服务端在更新时间戳前，取最大值后还自增了一次。
实际上，给每个
send&recv事件打上时间戳时都要自增，不过书上的操作结果也满足维护因果关系的要求。
全序逻辑的Lamport时间戳构建了全序关系，这个全序关系与因果关系保持了一致（即维持了因果关系这个偏序），但无法通过Lamport时间戳判断2个事件是因果关系还是并发关系，即：
- $e_1 \rightarrow e_2 \Rightarrow L_1 < L_2$
- $L_1 < L_2 \not\Rightarrow e_1 \rightarrow e_2$
第二条要推断出来，需要向量时间戳（向量时间戳也满足第一条）。维护顺序的方式类似，参考这里。
因果一致：如果A通知B它已经更新了数据，那么B后续读取会读取到A写入的最新值（通知动作展示了因果顺序关系，B要和A看到的因果顺序是一样的）。
3. 全序关系广播
全序关系必须在所有操作都收集完毕后，才能被确定。知道什么时候全序关系已被确定，需要全序关系广播/原子广播。
全序关系广播即节点之间交换消息的某种协议，必须满足以下2点，即使节点和网络发生故障：
- 可靠发送（没有消息丢失或篡改）
- 严格有序（消息以相同顺序发给所有节点）
在上述条件上，使用该机制：通过单Leader多Follower机制，在Leader节点上对所有操作进行排序，从而决定了整个操作顺序，并将操作顺序进行广播。（与主从复制十分类似）
共识算法提供了全序关系广播，以容错的方式实现了线性化的原子操作。
可线性化与全序关系广播不完全相同：
- 前者强调实时性，读必须看到最新的写；
- 后者可基于异步模型，这代表可能出现滞后性。
3.1. 采用全序关系广播实现线性化存储
可采用追加日志的方式，并广播。
线性化原子写/CAS：
- 在日志中追加一条消息，指明想要的值；
- 将日志广播到其它所有节点，等待回复；
- 检查是否有其它节点是否已占用这个值，如果有则中止操作。
线性化读：
- 追加读请求日志，广播，然后各节点获取日志，开始读取（读请求的时间由日志的位置确定）
- 以线性化的方式获取最新日志的位置，查询位置，获得该位置前的所有内容，然后再读取
- 写时同步更新副本，从同步的副本中读取，确保读到的是最新值
顺序一致(Sequential Consistency)：
不同进程执行的所有操作最后得到的结果，与它们其中一种串行序列的执行结果相同（同一进程操作顺序保证，不同进程的操作顺序可以调换，串行序列不唯一）。
如$P_1$:
write(x,4),read(y,2); $P_2$：write(y,2),read(x,0)，则满足顺序一致，因为执行的结果和下列串行执行的结果一样：
write(y,2)->read(x,0)->write(x,4)->read(y,2)而如$P_1$:
write(x,4),read(y,0); $P_2$：write(y,2),read(x,0)，则不满足顺序一致，因为找不到一条串行序列符合上面的执行结果，如下面的，会有冲突：
write(x,4)->read(y,0)->write(y,2)->read(x,0)（第一步与第四步冲突）。
此外，Linearizability（线性化） can be defined as sequential consistency with the real-time constraint.
etcd: 读写均线性一致
zookeeper: 写线性一致；读若不调用
sync()则为顺序一致
3.2. 采用线性化存储实现全序关系广播
思路：
- 对于每个要通过全序广播发送的消息，首先对线性一致寄存器执行CAS-
incrementAndGet操作 - 然后将从寄存器获得的值作为序列号附加到消息中
- 然后将消息发送到所有节点（消息丢失则重试），而接收者严格将按序列号连续回复消息
4. 一致性：整理
本书目前提及的一致性包括：
- Linearizability/Atomic consistency/Strong consistency
- Sequential consistency
- Casual consistency
- Read-after-write/Read-your-write
- Monotonic read/Monotonic write
- Consistent prefix read
- Eventual consistency
可在本文，以及数据复制一文看到详细整理。
