本章讨论构建分布式系统的相关算法和协议，类似于事务，构建分布式容错系统也需要建立一套通用的抽象机制和与之对应的技术保证。
共识：所有节点对某项提议达成一致，解决共识问题可以解决许多应用需求，例如主节点的选取。
一致性保证
最终一致性：如果停止更新并等待一定长度（未知长度）的时间，所有读请求会返回相同的内容，意味着所有副本最终收敛于相同的值。最终一致性是非常弱的保证，未保证合适会收敛。
本章将探索比最终一致性更强的一致性模型，首先讨论线性化，之后讨论顺序关系，最后讨论如何自动提交分布式事务，解决共识问题。
可线性化
可线性化：让一个系统看起来只有一个数据副本，保证读取到最近最新的值
如上图所示，由于不同副本复制完成的时间不同，Alice和Bob先后读取不同的副本，但是后读取的Bob却读取到了更旧的数据。
如何达到可线性化？
多个客户端读取数据库的同一条数据，如果不加限制，只要读操作与写操作存在一定的重叠，那么读取结果可能是写入前结果，也可能是写入后结果。
为了实现线性化，可以添加约束：一旦某个读操作读到新值后，之后所有的读操作都需要返回新值。
上图中引入了原子比较-设置操作（Compare and Set, CAS），而客户端B的最后一个读操作因为与客户端C的最后一个CAS操作有时间上的重叠，导致返回值不满足可线性化。上图中可以看到，请求顺序、数据库处理顺序、响应顺序互相之间呈弱相关，这是由网络延迟导致的，另外可线性化模型没有假定事务之间是具有隔离的。
线性化的依赖条件
线性化在某些场景下，对于保障系统正常工作至关重要
加锁和主节点选取
集群中选取主节点必须严格保证只有一个主节点，否则会产生脑裂，选举主节点可以视为每个节点都尝试获得锁，但只有一个可以成功。etcd、zookeeper可以用来实现分布式锁和主节点选举。
约束与唯一性保证
某些约束需要严格的线性化，例如不应当有相同的用户ID，银行账户余额不应当为负值。
跨通道的时间依赖
上图所示为图片调整服务架构，理想的运行状态为图片上传后由数据库存储，再将处理任务消息发送至队列，最终由调整模块收到消息后读取图片进行最终的调整。但是由于网络原因，可能导致保存过慢，处理模块收到消息时图片仍为保存完成。
实现线性化系统
不同复制方案是否满足可线性化：
主从复制（部分满足可线性化）
共识算法（可线性化）
多主复制（不可线性化）
无主复制（可能不线性化）
线性化与quorum
如上图所示，quorum并不能保证一致性，这是因为不同节点复制完成的时间不一致。
线性化的代价
如图所示为两个互相复制的数据中心，如果网络发生中断，则会面临可用性和可线性化的抉择。
CAP理论
可线性化、可用性、分区容错性的三选二，不过CAP理论只考虑了一种一致性模型即线性化模型和一种错误模型即网络分区。
可线性化与网络延迟
虽然线性化是个很有用的保证，但是很少有系统真正满足线性化，甚至因为指令重排等原因单机上的内存都未必满足可线性化。当今的数据库倾向于牺牲一致性来提高系统的容错性。
顺序保证
可线性化意味着操作按照某种顺序执行，顺序、可线性化、共识之间存在深刻的联系。
顺序与因果关系
保证顺序的一大意义在于，保证一系列操作的因果关系。如果系统服从因果关系规定的顺序，则称之为因果一致性。
因果顺序并非全序
全序/偏序：集合内元素支持/不支持比较。对于可线性化系统中，各个操作总能指出先后顺序；如果两个事件为并发，则无法比较两者的因果关系，并发意味着时间线的分支与合并，不同分支上的操作无法直接比较。
可线性化强于因果一致性
可线性化是因果一致性的充分条件，但线性化并不是保证因果一致性的唯一方式。
捕获因果依赖关系
对于事件之间的因果关系进行逻辑分析。
序列号排序
相比于检测因果关系，使用序列号或者时间戳对于事件进行排序是更好的方法，对于主从复制数据库，主节点可以简单的递增计数器，为每个复制日志分配一个单调递增的序列号，从节点按照主节点日志的顺序进行同步操作，从而结果一定满足因果一致性。
非因果序列发生器
如果主节点不唯一，产生单调递增的序列号就不那么容易了，有一些序列号产生方法，但是这些方法并不能满足产生单调递增递增的序列号，例如：每个节点特定产生奇数或偶数的序列号，利用墙上时钟作为序列号，预先给不同节点分配序列号范围，但是以上方法都不能严格保证因果关系。
Lamport时间戳
Lamport时间戳要求每个节点保存自己已经处理的请求总数与ID信息，每个客户端和节点都跟踪迄今为止所见过的最大计数器数值，从而确保了全序关系。
时间戳排序依然不够
仅仅依赖Lamport时间戳，无法解决唯一性约束的问题。
全序关系广播
全序关系广播通常指节点间交换消息的某种协议，满足两个基本的安全属性：
可靠发送：如果消息发送到了某个节点，则一定要发送到所有节点
严格有序：消息总是以相同顺序发送
即使网络或节点发生故障，全序关系广播算法的实现也必须保证以上两条
使用全序关系广播
ZooKeeper，etcd等实现了全序关系广播，全序关系广播和共识之间存在密切的联系。全序关系广播可以用来实现可串行化事务，提供fencing锁服务。
采用全序关系广播实现线性化存储
采用线性化存储实现全序关系广播
分布式事务与共识
许多场景需要集群节点达成某种一致：
主节点选取：错误的共识将导致脑裂
原子事务提交：为了维护分布式事务的原子性，需要对事务的结果达成一致
原子提交与两阶段提交
原子性防止失败的事务破坏系统。
从单节点到分布式的原子提交
单个节点事务的原子性依赖于严格的执行顺序，多个节点的事务和单个节点的事务具有显著区别。
两阶段提交
2PC引入了协调者，并将提交/中止过程分成两个阶段，在任何阶段来自于任何节点的否定回答都会中止事务。
系统的承诺
在2PC中存在两个“不归路”：
阶段1中参与者的做出肯定提交的承诺
阶段2中协调者做出提交决定
如果这两个承诺发生，那么即便出现故障也会不断重试而不会中止。
协调者发生故障
协调者的崩溃导致参与者只能一直等待协调者的消息，除非协调者恢复。
三阶段提交
2PC也被称为阻塞式原子提交协议，3PC作为2PC的替代方案假定有限的
