错误地活着，还是正确地挂掉？
——Jay Kreps，关于Kafka和Jepsen的若干注解
分布式系统最重要的抽象之一就是共识：所有的节点就某一项提议达成一致。
可线性化
数据库对应用提供只有单个副本的假象，让每个客户端都拥有相同的数据视图，而不必担心复制滞后，这就是可线性化（也称为原子一致性，强一致性等）的思想。其基本的想法是让一个系统看起来好像只有一个数据副本，且所有操作都是原子的。有了这个保证，应用程序就不需要关心系统内部的多个副本。
在有些场景下，线性化对于保证系统正确工作至关重要：
- 加锁与主节点选举
- 约束与唯一性保证
- 跨通道的时间依赖
实现线性化系统
最简单的方案即单副本，但无法容错，因此一般采用复制机制。
- 主从复制（部分支持可线性化），如果从主节点或同步更新的从节点上读取，可以满足线性化。
- 共识算法（可线性化），通常内置一些措施来防止脑裂和过期的副本，可以安全地实现线性化存储，这些系统包括ZooKeeper和etcd等。
- 多主复制（不可线性化），多个主节点可能会产生冲突的写入。
- 无主复制（可能不可线性化）
顺序保证
顺序与因果关系
如果系统服从因果关系所规定的顺序，我们称之为因果一致性。
全序和偏序的差异体现在不同的数据库一致性模型中：可线性化系统存在全序操作关系；因果关系至少可以定义为偏序，而非全序。因果一致性可以认为是不会由于网络延迟而显著影响性能，又能对网络故障提供容错的最强的一致性模型。
序列号排序
版本向量技术可以推广为捕获请求的因果依赖关系的一种通用解决方案。为了确定因果关系，数据库需要知道应用程序读取的是哪个版本的数据，但很明显，显式跟踪所有已读数据意味着巨大的运行开销。另外我们可以考虑使用序列号或时间戳来排序事件，时间戳可以是个逻辑时钟，通常是递增的计数器。
兰伯特时间戳（Lamport timestamp）是一个产出因果关系一致的序列号的生成算法。Lamport时间戳是一个值对（计数器，节点ID），每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个请求中附带该最大计数器值。当节点发现请求内嵌的最大计数器值大于节点自身的计数器值，则它立即把自己的计数器修改为该最大值。
版本向量和Lamport时间戳区别：版本向量用于区分两个操作是并发还是因果依赖，而Lamport时间戳则主要用于确保全序关系。即使Lamport时间戳与因果序一致，但根据其全序关系却无法区分两个操作属于并发还是因果依赖关系。Lamport时间戳更加紧凑和高效。
全序关系广播
全序关系广播通常指节点之间交换消息的某种协议，它要满足两个基本安全属性：
- 可靠发送：没有消息丢失，如果消息发送到了某一个节点，则它一定要发送到所有节点。
- 严格有序：消息总是以相同的顺序发送给每个节点。
像ZooKeeper和etcd这样的共识服务就实现了全序关系广播。全序关系广播正是数据库复制需要的：如果每条消息代表数据库写请求，并且每个副本按相同的顺序处理这些写请求，那么所有副本可以保持一致（可能有滞后）。该原则也称为状态机复制。
可以通过使用全序关系广播以追加日志的方式来实现线性化的原子比较-设置操作。
我们也可以反过来，在线性化的存储之上构建全序关系广播：对于每个要通过全序关系广播的消息，原子递增并读取该线性化的计数，然后将其作为序列号附加到消息中。接下来，将消息广播到所有节点，而接收者也严格按照序列化来发送回复消息。
分布式事务与共识
共识问题是分布式计算中最重要也是最基本的问题之一。有很多重要的场景都需要集群节点达成某种一致，例如：
- 主节点选举，对于主从复制数据库，所有节点需要就谁来充当主节点达成一致。
- 原子事务提交，所有节点必须对事务的结果达成一致，要么全部成功提交，要么中止/回滚。
原子提交与两阶段提交
两阶段提交（two-phase commit，2PC）是一种在多节点之间实现事务原子提交的算法。2PC引入了新组件：协调者（也叫事务管理器）。协调者通常实现为共享库，运行在请求事务相同的进程中，但也可以是单独的进程或服务。两阶段提交也被称为阻塞式原子提交协议，因为2PC可能在等待协调者恢复时卡住。
作为2PC的替代方案，目前也有三阶段提交算法。3PC假定一个有界的网络延迟和节点在规定时间内响应。
目前有两种不同的分布式事务概念：
- 数据库内部的分布式事务
- 异构分布式事务
X/Open XA（eXtended Architecture，XA）是异构环境下实施两阶段提交的一个工业标准。
支持容错的共识
共识通常形式化描述如下：一个或多个节点可以提议某些值，由共识算法来决定最终值。共识算法必须满足以下性质：
- 协商一致性（Uniform agreement），所有的节点都接受相同的决议
- 诚实性（Integrity），所有节点不能反悔，即对一项提议不能有两次决定。
- 合法性（Validity），如果决定了值v，则v一定是某个节点所提议的。
- 可终止性（Termination），节点如果不崩溃则最终一定可以达成决议。
协商一致性和诚实性定义了共识的核心思想：决定一致的结果，一旦决定，就不能改变。合法性主要是为了排除无意义的方案。可终止性则引入了容错的思想，即使某些节点出现了故障，其它节点也必须最终作出决定，可终止性属于活性，而其它三种属于安全性。
最著名的容错式共识算法包括VSR、Paxos、Raft、Zab。他们决定了一系列值，然后采用全序关系广播算法。全序关系广播相当于持续的多轮共识（每一轮共识的决定对应于一条消息）：
- 由于协商一致性，所有节点决定以相同的顺序发送相同的消息。
- 由于诚实性，消息不能重复。
- 由于合法性，消息不会被破坏，也不是凭空捏造的。
- 由于可终止性，消息不会丢失。
成员与协调服务
ZooKeeper或etcd这样的项目通常称为”分布式键值存储”或”协调与配置服务”。它们通常采用容错的全序关系广播算法在所有节点上复制数据从而实现高可靠。同时ZooKeeper还提供了其它很多特性：
- 线性化的原子操作
- 操作全序
- 故障检测，客户端与ZooKeeper节点维护一个长期会话，客户端会周期性地与ZooKeeper服务节点互相交换心跳信息。
- 更改通知，客户端可以监视其它客户端创建的键值变化。通过订阅通知机制，客户端不需要进行轮询即可知道感兴趣的对象的变化情况。
ZooKeeper可以非常方便地使应用程序达到故障自动恢复，适用于数据库的复制、分区等场景进行协调。它提供了一种将跨节点协调服务专业外包的方式。
另外ZooKeeper、etcd等还经常用于服务发现。ZooKeeper等还可以看作是成员服务范畴的一部分。成员服务用来确定当前哪些节点处于活动状态并属于集群的有效成员。
参考文献：
[1] (美)Martin Kleppmann. 数据密集型应用系统设计（赵军平，吕云松，耿煜，李三平 译）[M]. 北京：中国电力出版社，2018.