一致性保证
本章主要包含了以下话题：
- 常用的强一致性模型：线性一致性，的优点和缺点。
- 分布式系统中的事件顺序，特别是因果关系和全局顺序的问题。
- 如何原子的提交分布式事务，也就是说如何解决共识问题。
线性一致性
哪些地方依赖于线性一致性呢 ？
- Locking 服务和 leader election，比如加锁出错了会导致两个人同时写同一个文件。
- 账户余额，产品库存信息，比如产品超卖。
如何实现一个线性一致性系统
在分布式系统里面，产生不一致的根本原因是因为数据有多个副本，而更新这些副本不是原子操作。
以下是几种多副本系统，能否实现线性一致性的比较：
- Single-leader replication (可能线性一致) 这里我猜作者说的是传统 MySQL 这样的主从复制技术。
- Consensus Algorithms (线性一致) 这里应该就是常说的 Panox 和 Raft 了。
- Multi-leader replication (非线性一致)
- Leaderless replication (也许不是线性一致的) Dynamo 风格 和 Cassandra 风格。
线性一致的代价
假设两个 datacenter 之间网络断了的情况下，
- 如果是 multi-leader 系统，那么每个 datacenter 仍然可以独立运行，datacenter 之间的数据是异步同步的，所以不会受到影响。
- 如果是 single-leader 系统，如果 client 连到了全是 follower 的 datacenter，那么所有 write 和 linerizable read 都受影响，如果 client 连到的是 leader 所在的 datacenter，则不受影响。
CAP Consistency, Availability, Partition Tolerance.
不单单是分布式系统有不一致的问题，在单机多核系统上也有，比如 CPU0 和 CPU1 同时写内存，实际上它们是先读写 L1 cache，然后 cache 异步写到 memory，因此才有了 “Memory Barrier” 这个概念。
CPU 或编译器在对内存进行操作的时候, 严格按照一定的顺序来执行, 也就是说在内存屏障之前的指令和之后的指令不会由于系统优化等原因而导致乱序。大多数现代计算机为了提高性能而采取乱序执行，这使得内存屏障成为必须。语义上，内存屏障之前的所有写操作都要写入内存；内存屏障之后的读操作都可以获得同步屏障之前的写操作的结果。因此，对于敏感的程序块，写操作之后、读操作之前可以插入内存屏障。
顺序保证
要保证顺序，最简单的方法就是给每个任务一个时间戳（或者叫序列号），做完 6.824 的同学应该不难理解这个概念，其实就是 term。
作者还提到了一个 Lamport 时间，类似分布式 ID 生成器那样，每个 server 用自己的 ID 加上 timestamp 作为任务的 ID 来保证顺序。
这样确实保证了每个任务有唯一ID，但是还是不够，比如创建账户的时候，不能两个用户有同一个用户名，所以每个 server 必须还要把自己的信息广播给其他 server。
分布式事务与共识
两阶段提交 2PC
主要分成 master 和 worker，第一阶段是准备阶段 prepare ，第二阶段是提交阶段 commit
准备阶段的主要目的在于打探集群中的各个参与者是否能够正常的执行事务，具体步骤如下：
- 协调者向所有的参与者发送事务执行请求，并等待参与者反馈事务执行结果；
- 事务参与者收到请求之后，执行事务但不提交，并记录事务日志；
- 参与者将自己事务执行情况反馈给协调者，同时阻塞等待协调者的后续指令。
上面的结果有 4 种可能性：
- 所有的参与者都回复能够正常执行事务。
- 一个或多个参与者回复事务执行失败。
- 协调者等待超时。
- 协调者 crash
提交阶段
针对第一种情况，协调者将向所有的参与者发出 commit 操作的通知，worker执行 commit 操作，并将结果返回给协调者。
实际中的情况远远比这个复杂，光是 master 和 worker 会在任何时候崩溃就有很多 corner case 需要考虑到，可能复习一遍 Raft 算法能更加加深理解。
两阶段锁 2PL
既然提到了两阶段提交，那么也复习下两阶段锁。
数据库中的每一个数据对象都有两种锁：(S)hared lock 和 e(X)clusive lock。正如字面意思，shared lock允许多个锁并存；exclusive lock具有排它性
操作和锁的对应关系很简单：如果一个transaction想要读取 x，那它必须获取 x 上的shared lock；如果一个transaction想要写入 x ，那它必须获取 x 上的exclusive lock
如果一个transaction释放了它所持有的任意一个锁，那它就再也不能获取任何锁。
明白了这一条规则我们也就明白two-phase locking名字的由来了，
在2PL协议下，每个transaction都会经过两个阶段：
- 在第一个阶段里，transaction根据需要不断地获取锁，叫做 growing phase (expanding phase)
- 在第二个阶段里，transaction开始释放其持有的锁，根据2PL的规则，这个transaction不能再获得新的锁，所以它所持有的锁逐渐减少，叫做 shrinking phase (contracting phase)。