“出海切勿带两只航海钟，要么带一只，要么带三只”
复制 replication 是实现容错最有力的工具之一，把同一份数据复制到多个副本，也带来了不一致的风险。读请求可能由尚未追上进度的副本处理，返回陈旧结果；如果多个副本都能接受写入，还必须解决不同副本上并发写入的值之间的冲突。总体上，处理这类问题有两种彼此竞争的思路：
最终一致性 eventual consistency:
这种思路把系统采用复制这一事实暴露给应用，由应用开发者处理随之而来的不一致与冲突。采用“多主复制”和“无主复制”的系统常常使用这种方式。
强一致性 strong consistency:
这种思路认为，应用不应操心复制的内部细节，系统应当表现得仿佛只有一个节点。它让应用开发者的工作简单得多，代价则是更强的一致性会损害性能，而且有些故障在最终一致系统中尚可容忍，却会令强一致系统停摆。
哪种方式更好取决于具体应用。如果应用允许用户离线修改数据，最终一致性不可避免。应用要正确处理最终一致性也很困难。如果各副本位于通信快速而可靠的数据中心，强一致性的成本通常可以接受，因而往往更合适。
要让复制数据库尽可能简单易用，最好让它表现得仿佛根本没有复制。这样用户不必操心复制延迟、冲突和其他不一致的问题。既能获得容错的好处，又不必承担思考多个副本所带来的复杂性。
这就是 线性一致性（linearizability）（也称为 原子一致性，atomic consistency ，强一致性，strong consistency，即时一致性，immediate consistency，或 外部一致性，external consistency ）背后的思想。
其基本思想，是让系统看起来仿佛只有一份数据，所有操作都原子地作用于这份数据。有了这种保证，即使实际上存在多个副本，应用也无需关心它们。
在线性一致的系统中，只要一个客户端成功完成写入，此后所有客户端从数据库读取时，都必须能看到刚写入的值。要维持“只有一份数据”的假象，就必须保证读到的是最近写入的最新值，而不是来自陈旧缓存或副本的旧值。换句话说，线性一致性是一种 新鲜度保证（recency guarantee） 。下面用一个不满足线性一致性的系统来说明这一点。
例如 Aaliyah 和 Bryce 在同一个房间，Bryce 听 Aaliyah 他获得的数据更新了，Bryce 尝试 却得到的是陈旧的值，这就违反了线性一致性。
展示了三个客户端如何并发读写线性一致数据库中同一个对象x。在分布式系统理论中，x 称为 寄存器 register； 在实际系统里，它可以是键值存储中的一个键、关键数据库中的一行，或文档数据库中的一个文档。
这不足以完整描述线性一致性，如果与写入并发的读取可以任意返回旧值或新值，那么在写入期间，读者可能看到值在新旧之间来回跳变。这不符合对“只有一份数据”的系统的预期。
要使系统满足线性一致性，还需要增加一条约束：
在线性一致的系统中，可以设想在写操作起止之间存在某个时刻，x 的值在那一刻原子地从 0 变为 1。因此，只要某个客户端已经读到新值 1，此后所有读取也都必须返回 1，即使写操作本身尚未结束。
图中的箭头标出了时序依赖，客户端 A 最先读到新值 1；A 的读取刚一返回，B 就开始了新的读取。由于 B 的读取严格晚于 A 的读取，它也必须返回 1，哪怕 C 的写入仍在进行。
线性一致性要求，连接这些操作标记的线只能沿时间向前移动（从左向右），绝不能倒退。这项要求保证了前面所说的新鲜度：一旦新值已经被写入或读到，此后的读取就都必须看到这个值，直至它再次被覆盖。
线性一致性很容易与可串行化混淆，因为两个名称看起来都像是在说 可以排成某种顺序，但二者是完全不同的保证，必须加以区分：
可串行化:
可串行化是事务的一项隔离属性；每个事务可以读写 多个对象（行、文档或记录）。它保证事务的行为等同于按 某种 串行顺序执行：先完整执行一个事务，再完整执行下一个事务，彼此不交错。这个串行顺序可以不同于事务实际运行的顺序。
线性一致性:
线性一致性是对寄存器（即 单个对象）读写的保证。它不会把操作组合成事务，因此无法防止“写偏差与幻读”这类涉及多个对象的问题。但线性一致性是一项 新鲜度 保证：如果一个操作在另一个操作开始前已经结束，那么后一个操作必须观察到至少与前一个操作同样新的状态。可串行化没有这项要求，例如它允许陈旧读取。
数据库可以同时提供可串行化与线性一致性，这种组合称为 严格可串行化（strict serializability）或 强单副本可串行化（strong one-copy serializability，strong-1SR）。单节点数据库通常满足线性一致性。对于采用“可串行化快照隔离（SSI）”等乐观方法的分布式数据库，情况要复杂一些。例如，CockroachDB 提供可串行化以及一定的读取新鲜度保证，却不提供严格可串行化，因为后者要求事务之间进行代价高昂的协调。
线性一致性在什么情况下有用？查看体育比赛的终场比分也许只是个无关紧要的例子：结果陈旧几秒，通常不会造成实际损失。然而在少数领域，线性一致性却是系统正确工作的必要条件。
采用单主复制的系统必须确保领导者确实只有一个，而不是同时出现多个领导者（脑裂）。一种选举办法是使用租约：每个启动的节点都尝试获取租约，成功者成为领导者。无论底层机制如何实现，都必须满足线性一致性，绝不能让两个不同节点同时获得同一份租约。
Apache ZooKeeper、etcd 等协调服务经常用于实现分布式租约和领导者选举。它们借助共识算法，以容错方式提供线性一致的操作。严格来说，ZooKeeper 的写入满足线性一致性，但读取可能陈旧，因为它不保证读请求一定由当前领导者处理。从版本 3 开始，etcd 默认提供线性一致的读取。
一些分布式数据库还会在细得多的粒度上使用分布式锁，例如 Oracle Real Application Clusters（RAC）。RAC 为每个磁盘页设置一把锁，多个节点共享同一套磁盘存储。由于这些线性一致的锁位于事务执行的关键路径上，RAC 部署通常会使用专用的集群互连网络，让数据库节点彼此通信。
唯一性约束在数据库中十分常见，例如，用户名或电子邮件地址必须唯一标识一位用户；文件存储服务也不能同时存在路径和文件名完全相同的两个文件。如果要在写入时强制执行这种约束——也就是说，两个人并发创建同名用户或文件时，必须让其中一人收到错误——就需要线性一致性。
这种情形其实与锁很相似：用户注册服务时，可以看作在获取所选用户名的“锁”。这个操作也很像原子的比较并设置：只要用户名尚未被占用，就把它设为认领该名称的用户 ID。
类似的问题还有很多：确保银行账户余额永不为负，商品销量不超过仓库库存，或不让两个人同时订到同一航班、同一剧场的同一个座位。这些约束都要求存在一个由所有节点共同认可的最新值，例如账户余额、库存数量或座位占用状态。
实际应用有时可以宽松处理此类约束。例如航班超售后，可以把旅客转到另一趟航班，并为造成的不便提供补偿。在这种情况下，线性一致性未必必要；
不过，关系数据库里常见的硬性唯一约束确实需要线性一致性。外键约束、属性约束等其他约束则可以不依赖线性一致性来实现。
假设某网站允许用户上传视频，后台进程会把视频转码为画质较低的版本，以便通过慢速网络流式播放。视频转码器必须收到明确指令才会执行转码作业，这条指令由 Web 服务器通过消息队列发送。Web 服务器不会把整段视频塞进队列，因为大多数消息代理是为短消息设计的，而视频可能有数十兆字节甚至更大。它会先把视频写入文件存储服务，确认写入完成后，再将转码指令放入队列。
如果文件存储服务满足线性一致性，这套系统就能正常工作；否则便可能出现竞态条件：消息队列也许比存储服务内部的复制传播得更快。这样一来，转码器获取原始视频时，可能读到文件的旧版本，甚至什么也读不到。如果它转码了旧版本，文件存储中的原始视频与转码版本就会永久不一致。
问题的根源在于，Web 服务器与转码器之间存在两条不同的通信通道：文件存储和消息队列。没有线性一致性提供的新鲜度保证，两条通道之间就可能发生竞态。
能接收推送通知的移动应用也可能遇到类似竞态：应用收到通知后会向服务器获取相关数据；如果读请求可能落到滞后的副本上，推送通知也许很快就到了，紧随其后的数据读取却看不到通知所指的更新。
线性一致性不是避免这类竞态的唯一办法，却是最容易理解的一种。
思考如何实现一个提供线性一致语义的系统：
线性一致性本质上要求系统“表现得仿佛只有一份数据，而且所有操作都原子地作用于它”，因此最简单的实现就是真的只保存一份数据。可惜这种方式无法容错：保存这份数据的节点一旦失效，数据就会丢失，至少也会在节点恢复前无法访问。
在单主复制系统中，领导者保存用于写入的主副本，其他节点上的追随者则维护备份。只要所有读写都由领导者处理，通常就有可能满足线性一致性。但这依赖一个前提：你必须确切知道谁是领导者。节点完全可能误以为自己仍是领导者；如果这个自以为是的领导者继续处理请求，就很可能破坏线性一致性。采用异步复制时，故障切换甚至可能丢失已经提交的写入，同时违反持久性与线性一致性。
对单主数据库进行分片、让每个分片拥有各自的领导者，不会影响线性一致性，因为它只保证单个对象。跨分片事务则是另一个问题（分布式事务）。
有些共识算法本质上是增加了自动领导者选举和故障切换的单主复制。它们经过精心设计以避免脑裂，因而能够安全实现线性一致的存储。
例如，ZooKeeper 使用 Zab 共识算法，etcd 使用 Raft。不过，系统采用了共识，并不等于它的所有操作都满足线性一致性：如果某个节点处理读取前没有确认自己仍是领导者，那么在刚刚选出新领导者时，它就可能返回陈旧结果。
多主复制系统通常不满足线性一致性，因为多个节点会并发处理写入，再把结果异步复制到其他节点。因此，它们可能产生需要“处理写入冲突”的并发写入。
对于采用无主复制的系统（Dynamo
风格，参见“无主复制”），有人声称，只要要求仲裁读写满足
w + r > n，就能得到“强一致性”。这取决于具体算法以及“强一致性”的定义，但通常并不准确。
Cassandra 和 ScyllaDB 等系统采用基于日历时钟的“最后写入者胜”来解决冲突，这几乎肯定不满足线性一致性，因为时钟偏差使时间戳无法保证与事件的实际顺序一致。即使采用仲裁读写，仍然可能出现违反线性一致性的行为。
直觉上，Dynamo 风格模型中的仲裁读写似乎应当满足线性一致性。但当网络延迟变化不定时，仍然可能出现竞态
可以让 Dynamo 风格的法定人数读写满足线性一致性，但要牺牲性能：读取方必须先同步完成“追赶错过的写入”所述的读修复，再把结果返回应用；写入方则必须在写入前先读取达到法定人数的节点的最新状态，取得此前所有写入中的最大时间戳，并确保新写入使用更大的时间戳。这种方式只能实现线性一致的读写；无法实现线性一致的比较并设置，因为后者需要共识算法。
总之，最稳妥的假设是：采用 Dynamo 风格复制的无主系统即使使用仲裁读写，也不提供线性一致性。
既然有些复制方式能够提供线性一致性，有些不能，有必要仔细考察它的利弊：
例如，对多地区复制而言，多主复制往往是不错的选择
考虑两个地区之间网络中断时会发生什么。假设各地区内部的网络仍然正常，客户端也能访问本地区域， 但两个地区彼此无法通信。这种情况称为 网络分区 network partition。
在多主数据库中，每个地区都可以继续正常工作：一地的写入原本就异步复制到另一地，因此网络中断期间只需暂存排队，连接恢复后再相互交换。
若采用单主复制，领导者必然位于其中一个地区。所有写入和线性一致读取都必须发给领导者；因此，连接到追随者所在地区的客户端，必须跨地区同步地把读写请求发送到领导者所在地区。
单主配置下，一旦地区间网络中断，追随者所在地区的客户端便无法联系领导者，因而既不能写入数据库，也不能执行线性一致读取。它们仍可从追随者读取，但结果可能陈旧，不满足线性一致性。如果应用要求线性一致的读写，那么所有无法联系领导者的地区都会在网络中断期间变得不可用。
能直接连接领导者所在地区的客户端不受影响，应用在那里仍可正常工作；但只能访问追随者所在地区的客户端会一直停摆，直到网络链路修复。
这个问题并非单主复制与多主复制特有：任何线性一致的数据库，无论怎样实现，都会面对同样的困境。它也不限于多地区部署；任何不可靠的网络都可能发生这种情况，即使是在同一地区内。具体权衡如下：
因此，不要求线性一致性的应用可以更好地容忍网络问题。这一认识通常称为 CAP 定理，由 Eric Brewer 2000年命名。
CAP 最初只是一个没有精确定义的经验法则，目的是引发对数据库权衡的讨论。当时许多分布式数据库都专注于在共享存储的机器集群上提供线性一致语义；CAP 则鼓励数据库工程师探索更广阔的分布式无共享系统设计空间，而后者更适合承载大规模 Web 服务。CAP 推动了这种观念转变，也帮助催生了 NoSQL 运动以及 21 世纪头十年中期涌现的大批新型数据库技术。
CAP 有时被概括成 一致性、可用性、分区容错性，三者择二。这种说法会误导人：网络分区是一类故障，并不是可以自由取舍的选项，不管你愿不愿意，它都会发生。
网络正常时，系统完全可以同时提供一致性（线性一致性）与全面可用性；发生网络故障时，才必须在线性一致性和全面可用性之间取舍。因此，更准确的说法是：发生分区时，要么一致，要么可用。网络越可靠，面临这种选择的次数就越少，但它终究无法彻底避免。
线性一致性虽然很有用，实际满足它的系统却少得出人意料。甚至现代多核CPU上的RAM也不满足线性一致性。一个 CPU 核上的线程写入某个内存地址后，另一个核上的线程稍晚读取同一地址，也不保证能看见前一个线程写入的值，除非使用 内存屏障 或 栅栏。
原因在于，每个 CPU 核都有自己的缓存和存储缓冲区。默认情况下，内存访问会先经过缓存，修改再异步写回主存。访问缓存远快于访问主存，因此这种机制对现代 CPU 的性能不可或缺。但系统里也因此出现了多份数据，主存中一份，各级缓存里可能还有几份，而且它们异步更新，于是失去了线性一致性。
为什么要作这种取舍？用 CAP 定理解释多核处理器的内存一致性模型毫无意义：在同一台计算机内，我们通常假定通信可靠，也不指望某个 CPU 核与计算机其他部分断开后还能正常工作。这里牺牲线性一致性是为了 性能，而不是容错。
许多不提供线性一致性保证的分布式数据库也是如此：主要目的是提高性能，而非增强容错。线性一致性很慢，而且始终如此，并非只在网络故障时才慢。
许多应用在创建数据库记录时，都要为其分配某种唯一ID，作为以后引用该记录的主键。单节点数据库通常使用自增整数， 它的优点是只需 64 位即可存储；如果能确定记录数永远不会超过 40 亿，甚至可以只用 32 位，不过这样做颇有风险。
自增 ID 还有一个好处：ID 顺序可以反映记录的创建顺序。聊天应用会在消息发出时为其分配自增 ID。按 ID 递增顺序展示消息，对话就能保持合理的先后关系：
这种单节点 ID 生成器也是一个线性一致系统。每次取 ID 都会原子地递增计数器并返回递增前的值，这称为 获取并增加（fetch-and-add）操作。
内存中的单节点 ID 生成器很容易实现：直接使用 CPU 提供的原子递增指令，就能让多个线程安全地更新同一个计数器。要把计数器做成持久的稍微麻烦一些，否则节点崩溃重启后计数器会复位，产生重复 ID。但更棘手的问题是：
ID 生成器还有几种替代方案：
分片 ID 分配:
可以让多个节点分别分配 ID，例如一个只生成偶数，另一个只生成奇数。更一般地，可以在 ID 中预留若干位来保存分片编号。这种 ID 仍然紧凑，却失去了顺序含义：看到 ID 为 16 和 17 的两条聊天消息，并不能断定消息 16 先发出，因为两个 ID 来自不同节点，而其中一个节点的进度可能领先于另一个。
预分配ID块:
单节点生成器不必逐个发放 ID，也可以一次分配一整块。例如，节点 A 取得 1 到 1,000，节点 B 取得 1,001 到 2,000；此后各节点可在自己的区间内独立发号，快用完时再申请下一块。但这种方案同样无法保证正确顺序：一条消息可能先从 1,001 到 2,000 的区间取得 ID，而稍后另一节点发出的消息却从 1 到 1,000 的区间取得了更小的 ID。
随机UUID:
可以采用 通用唯一标识符（UUID），也称 全局唯一标识符（GUID）。它最大的好处是，任意节点都能在本地生成，无需通信；代价是占用更多空间（128 位）。UUID 有多个版本，最简单的第 4 版本质上是一个足够长的随机数，两个节点碰巧选中同一值的概率微乎其微。可惜这类 ID 的顺序也是随机的，比较两个 ID 无法判断哪个更新。
为日历时钟时间戳补充唯一性信息:
如果各节点通过 NTP 让日历时钟大致准确，可以把时间戳放在 ID 的高位，再用额外信息填充其余位，保证即使时间戳相同，完整 ID 仍然唯一。例如，可以加入分片编号和分片内自增序列号，或一段足够长的随机值。第 7 版 UUID、Twitter Snowflake、ULID、Hazelcast Flake ID 生成器、MongoDB ObjectID 等许多方案都采用这种思路。这类 ID 生成器既可以在应用代码中实现，也可以放在数据库内部。
日历时钟时间戳至多只能给出近似顺序：如果较早的写入读取了略快的时钟，较晚的写入读取了略慢的时钟，时间戳顺序就可能与事件实际顺序相反。非单调时钟还可能突然跳变，甚至让同一节点生成的时间戳顺序出错。因此，基于日历时钟的 ID 生成器通常不满足线性一致性。
使用原子钟或 GPS 接收器进行高精度时钟同步，可以减少这种顺序错乱。但如果无需特殊硬件，也能生成唯一且顺序正确的 ID，当然更好。这正是 逻辑时钟（logical clock）要解决的问题。
日历时钟和单调时钟，二者都属于 物理时钟，度量的是经过了多少秒（毫秒、微妙等）。
分布式系统还经常使用另一类时钟，称为 逻辑时钟（logical clock）。物理时钟是计算流逝秒数的硬件设备；逻辑时钟则是一种计算已发生事件数量的算法。因此，逻辑时间戳不能告诉你现在是几点，却 可以 相互比较，判断哪个较早、哪个较晚。
逻辑时钟的要求通常是：
单节点ID生成器满足这些要求，而前面几种分布式ID生成器不满足因果顺序要求。
有一种简单方法可以生成与因果关系 一致 的逻辑时间戳，并将其用作分布式 ID。这就是 Leslie Lamport 于 1978 年提出的 Lamport 时钟；介绍它的论文如今已成为分布式系统领域引用次数最多的论文之一。
每个节点都有唯一标识符；每个节点维护一个计数器，记录自己处理过多少次操作。Lamport 时间戳就是一个二元组（计数器，节点 ID）。不同节点的计数器值有时相同，但加入节点 ID 后，每个时间戳仍然唯一。
节点每生成一次时间戳，都会先递增本地计数器并使用新值。节点每次看到其他节点生成的时间戳时，如果其中的计数器大于自己的本地值，就把本地计数器向前推进到同一个值。
比较两个 Lamport
时间戳时，先比较计数器值。例如，(2, “Bryce”) 大于
(1, “Aaliyah”)，也大于
(1, “Caleb”)。若计数器相同，再按通常的字符串字典序比较节点
ID。因此，本例中的时间戳顺序为
(1, “Aaliyah”) < (1, “Caleb”) < (2, “Bryce”) 。
Lamport 时间戳很适合表示事件发生顺序，但也有一些局限。
混合逻辑时钟（hybrid logical clock，HLC）兼具物理日历时钟的优点与 Lamport 时钟的顺序保证。它像物理时钟一样以秒或微秒计数；又像 Lamport 时钟一样，在看到其他节点更大的时间戳时，把自己的本地值向前推进到对方的时间戳。因此，如果某个节点的时钟偏快，其他节点与它通信后也会相应地把时钟向前推进。
混合逻辑时钟每次生成时间戳时也会递增，从而保证始终单调向前，即使底层物理时钟因 NTP 校正而向后跳变也不例外。因此，混合逻辑时钟可能略微领先于底层物理时钟；算法会尽量把这项误差控制在最小范围内。
因此，混合逻辑时间戳几乎可以像普通日历时间戳一样使用，同时还多了一项性质：其顺序与先发生关系一致。它不依赖特殊硬件，只要求各时钟大致同步。CockroachDB 就使用了混合逻辑时钟。
快照隔离的一种常见实现：为每个事务分配事务 ID，让它看见 ID 较小的事务所做的写入，同时隐藏 ID 较大的事务所做的写入。Lamport 时钟和混合逻辑时钟很适合生成这些事务 ID，因为它们可以保证快照与因果关系一致。
多个时间戳并发生成时，这些算法会任意规定它们之间的顺序。因此，只看两个时间戳，通常无法判断二者是并发生成，还是一个先于另一个发生。具有相同计数器值，可以断定它们彼此并发；但计数器值不同时，就无法作出这种判断。
如果需要判断记录是否并发创建，就得采用另一种算法，例如 向量时钟（vector clock）。它的缺点是时间戳大得多，可能需要为系统中的每个节点保存一个整数。
Lamport 时钟与混合逻辑时钟虽然提供了实用的顺序保证，却仍弱于前面那种线性一致的单节点 ID 生成器。回想一下，线性一致性要求：只要请求 A 在请求 B 开始前已经完成，B 的 ID 就必须更大，即使二者从未彼此通信。Lamport 时钟只能保证节点新生成的时间戳大于它此前 见过 的所有时间戳，对未曾见过的时间戳则无法作出任何保证。
假设某个社交网站的用户 A 想把一张难为情的照片只分享给朋友。A 的账户原本公开；A 先在笔记本电脑上把账户设为私密，随后又用手机上传照片。这些操作由 A 依次完成，因此 A 有理由认为，上传的照片会受新的私密账户权限保护。
账户权限与照片保存在两个独立数据库中（也可能是同一数据库的不同分片），并假设二者都用 Lamport 时钟或混合逻辑时钟为写入分配时间戳。照片数据库没有读取账户数据库，因此它的本地计数器可能稍微落后，导致照片上传得到的时间戳反而小于账户设置更新的时间戳。
接着，假设一位并非 A 好友的访客正在浏览 A 的个人资料，而这次读取由实现快照隔离的 MVCC 处理。访客读取的时间戳可能大于照片上传，却小于账户权限更新。系统于是认定，在这个快照中账户仍是公开的，并把本不该让访客看到的照片显示出来。
这个问题有几种可能的修复方式。也许照片数据库应在写入前读取用户账户状态，但开发者很容易漏掉这项检查。如果 A 的所有操作都来自同一台设备，设备上的应用或许能跟踪该用户最近一次写入的时间戳；可本例中用户同时使用笔记本电脑和手机，事情就没那么简单。
这里最简单的解决方案，是使用线性一致的 ID 生成器，保证照片上传取得的 ID 一定大于账户权限变更的 ID。
确保 ID 分配满足线性一致性的最简单办法，确实是使用单个节点。这个节点只需在收到请求时原子递增计数器并返回结果，同时持久化计数器值，以免崩溃重启后产生重复 ID，再用单主复制实现容错。
可以通过批量预留来避免每次请求都写盘和复制。ID 生成器先写入一条记录，声明某一批 ID；这条记录持久化并完成复制后，节点便可按顺序把其中的 ID 发给客户端。在这一批快要用完前，再提前持久化并复制下一批。这样，节点崩溃重启或故障切换到追随者时，可能会跳过一些 ID，却绝不会发出重复或顺序错误的 ID。
ID 生成器很难分片：多个分片独立发号后，就无法再保证整体顺序满足线性一致性。它也很难分布到多个地区，因此地理分布式数据库中的所有 ID 请求，都得发往某个固定地区的节点。好在 ID 生成器的工作十分简单，单个节点就能承担很高的请求吞吐量。
如果不想采用单节点 ID 生成器，还有 Google Spanner 的做法，参见“用于全局快照的同步时钟”。它依赖一种物理时钟：返回的不是单个时间戳，而是一个时间戳区间，表示时钟读数的不确定性；系统会等待这个不确定区间完全过去之后再返回结果。
只要不确定区间确实可靠，真实物理时间始终落在区间内，这个过程同样能保证：若一个请求在另一个请求开始前完成，后一个请求就取得更大的时间戳。它无需节点间通信就能实现线性一致的 ID 分配；即使请求来自不同地区，也能正确排序，不必等待跨地区往返。代价是必须有相应的软硬件支持，既要让时钟高度同步，又要计算必要的不确定区间。
线性一致的比较并设置可以用来实现分布式锁、唯一性约束等构造。于是自然会问：逻辑时钟或线性一致的 ID 生成器，是否也足以实现这些功能？
答案是：还不够。若多个节点都在争抢同一把锁或注册同一个用户名，可以用逻辑时钟为请求分配时间戳，并选出时间戳最小者。如果时钟满足线性一致性，那么此后所有请求生成的时间戳都更大，也就不可能再出现比当前胜者更小的时间戳。
可惜问题还有一半没有解决：节点怎样知道自己的时间戳就是最小的？要做到确定无疑，它必须收到 每一个 可能生成时间戳的其他节点的消息。只要其中一个节点失效，或因网络问题无法联系，整个系统就会停滞，因为谁也无法排除那个节点拥有更小时间戳的可能。这显然不是我们想要的容错系统。
要以容错方式实现锁、租约等构造，需要比逻辑时钟或 ID 生成器更强的工具：我们需要共识。
只用单个节点时，事情十分简单；一旦还要求容错，就会困难很多。
这些都是同一个分布式系统基本问题的不同实例：共识 consensus。共识是分布式计算中最重要、最基本的问题之一； 同时，它也是出了名地难以正确实现。
最著名的共识算法包括 视图戳 Viewstamped Replication VSR，Paxos、Raft、Zab。这些算法有不少相似之处， 它们采用非拜占庭系统模型，网络通信可以被任意延迟或丢弃，节点可以崩溃、重启或断开连接；但除此之外。算法假定节点都会正确遵守协议，不会采取恶意行为。
共识可以用几种不同的方式表达：
共识的标准表述涉及让多个节点就单个值达成一致。例如：
更一般地说，一个或多个节点可以 提议 某个值，而共识算法从中 决定 一个值。在上述例子中，每个节点都可以提议自己的 ID，算法则决定哪个节点 ID 应当成为新的领导者、租约持有者或机票 戏票的购买者。在这种形式化定义下，共识算法必须满足以下属性：
如果需要决定多个值，可以为每个值分别运行一个共识算法实例。例如，可以为剧院中每个可预订的座位分别运行一次共识，从而为每个座位作出一项决定（确定一位买家）。
一致同意与完整性定义了共识的核心思想：所有节点都决定相同的结果，而且一旦作出决定，就不能再改变主意 。
如果不关心容错，满足前三个属性很容易：只需把一个节点硬编码为“独裁者”，由它作出所有决定即可。但这个节点一旦失效，系统便再也无法作出任何决定，这与没有故障切换的单主复制如出一辙。所有困难都源于容错这一要求。
终止属性形式化了容错的含义。它实质上要求共识算法不能永远无所作为，换句话说，算法必须取得进展。即使一部分节点失效，其余节点仍须作出决定。
如果崩溃的节点还有可能恢复，当然可以等它回来。然而，共识必须保证，即使某个节点突然消失而且永远不再回来，系统仍能作出决定。
当然，如果 所有 节点都已崩溃，无一仍在运行，那么任何算法都不可能决定任何事情。算法能容忍的故障数量存在上限：事实上，可以证明，任何共识算法都要求至少多数节点正常运行，才能保证终止。这组多数节点可以安全地构成法定人数。
终止属性以少于一半节点崩溃或不可达为前提。不过，即使多数节点失效，或网络出现严重问题，大多数共识算法仍能保证安全属性，一致同意、完整性与有效性——始终成立。所以，大规模中断可能令系统无法处理请求，却不能迫使共识系统作出彼此矛盾的决定，从而破坏其正确性。
比较并设置 CAS 操作会检查某个对象的当前值是否等于预期。如果相等，它就以原子方式把对象更新为新值；否则保持对象不变并返回错误。
有了容错且线性一致的CAS操作，就很容易解决共识问题；先把对象设为空值；每个想提议某个值的节点都调用CAS，把预期值设为空，把新值设为自己要提议的值（假设该值非空）。对象最终被设成什么值，共识决定的就是什么值。
反过来，有了共识的解法，也可以实现 CAS：每当一个或多个节点想以相同的预期值执行 CAS 时，就通过共识协议提议各次 CAS 调用中的新值，再把对象设为共识所决定的值。新值未获选中的 CAS 调用返回错误。预期值不同的 CAS 调用，则分别运行共识协议。
CAS 与共识彼此等价。两者在单个节点上都很简单，难点都在于如何实现容错。以前了解过，对象存储的条件写入操作只有在当前客户端上次读取之后，同名对象没有被其他客户端创建或修改时，才允许写入发生。
已经见过多种日志，例如复制日志、事务日志和预写日志。日志存储一系列 日志条目（log entry），任何读取者都会以相同顺序看到相同的条目。有时，只有一个写入者有权向日志追加新条目；而在 共享日志（shared log）中，多个节点都可以请求追加条目。单主复制就是一个例子：任何客户端都可以请求领导者执行写入，领导者把写入追加到复制日志，随后所有追随者都按照与领导者相同的顺序应用这些写入。
更形式化地说，共享日志支持两种操作：请求把一个值加入日志，以及读取日志条目。它必须满足以下属性：
共享日志在形式上称为 全序广播（total order broadcast）、原子广播（atomic broadcast）或 全序组播（total order multicast）协议。这些术语只是用不同说法描述同一件事：请求把一个值加入日志称为“广播”这个值，读取日志条目则称为“交付”这条日志。
有了共享日志的实现，就很容易解决共识问题：每个想提议某个值的节点都请求把它加入日志，而第一条日志条目中读出的值就是决定值。由于所有节点都按相同顺序读取日志条目，它们必然会就哪个值最先交付达成一致。
反过来，有了共识的解法，也可以实现共享日志。具体细节稍显复杂，但基本思路如下：
这说明，共识等价于全序广播，也等价于共享日志。没有故障切换的单主复制不满足活性要求，因为领导者一旦崩溃，系统就会停止交付消息。一如既往，真正的挑战在于如何安全、自动地完成故障切换。
有了 CAS 操作，实现获取并增加很容易：先读取计数器的值，再执行一次 CAS，把预期值设为刚才读到的值，把新值设为旧值加一。如果 CAS 失败，就从头重试，直到成功为止。存在争用时，这种实现不如原生的获取并增加操作高效，但两者在功能上等价。既然共识可以实现 CAS，自然也可以实现获取并增加。
反过来，如果有了容错的获取并增加操作，能否解决共识？假设计数器初值为零，每个想提议某个值的节点都调用获取并增加来递增计数器。由于这项操作具有原子性，其中一个节点会读到初始值零，其他节点读到的值则都至少已经递增过一次。
现在规定，读到零的节点胜出，其提议值成为决定值。这对读到零的节点当然没问题，其他节点却陷入了困境：它们知道自己没有胜出，却不知道其他节点中究竟谁赢了。胜者可以发消息告知其他节点，但如果它还没来得及发送消息就崩溃了呢？其余节点将一直悬而未决，无法决定任何值，共识也就不能终止。它们也不能改选另一个节点，因为读到零的节点日后仍可能恢复，并有充分理由决定自己提议的值。
有一个例外：我们能够确定提议值的节点不超过两个。此时，两个节点可以先互相发送各自的提议值，再分别执行获取并增加。读到零的节点决定自己的值，读到一的节点则决定另一个节点的值。这样就解决了两个节点之间的共识问题，因此我们说获取并增加的 共识数（consensus number）为二。相比之下，CAS 和共享日志可以在任意数量的节点提议值时解决共识，所以它们的共识数为 ∞（无穷大）。
原子提交（atomic commitment）问题：参与分布式事务的所有数据库或分片，要么全都提交事务，要么全都中止。我们还见过 两阶段提交（two-phase commit，2PC）算法，它依赖一个构成单点故障的协调者。
共识与原子提交是什么关系？乍一看，两者十分相似，都要求节点达成某种一致。不过，它们存在一项重要区别：共识可以决定任意一个被提议的值；原子提交则要求，只要 任何 参与者投票中止，算法就 必须 中止。更准确地说，原子提交必须满足以下属性：
有效性确保事务只有在所有节点都同意时才能提交；非平凡性则确保算法不能简单地一律中止（但只要节点间发生任何通信超时，它就允许中止）。另外三项属性与共识基本相同。
有了共识的解法，可以用多种方式解决原子提交。其中一种做法如下：准备提交事务时，每个节点把自己的提交或中止票发送给其他所有节点。某个节点如果收到自己以及所有其他节点的提交票，就通过共识算法提议“提交”；如果收到中止票或遇到超时，就通过共识算法提议“中止”。节点得知共识算法的决定后，再据此提交或中止事务。
在这种算法中，只有所有节点都投票提交，才可能有人提议“提交”。只要有任何节点投票中止，共识算法收到的所有提议都会是“中止”。如果所有节点都投票提交，但部分通信发生超时，就可能有些节点提议“中止”，另一些节点提议“提交”；这时最终提交还是中止并不重要，只要所有节点采取相同的决定即可。
反过来，有了容错的原子提交协议，也可以解决共识。每个想提议某个值的节点都在一组法定人数节点上发起事务，并在每个节点上执行一次单节点 CAS：如果寄存器尚未被另一个事务设值，就将其设为本节点的提议值。CAS 成功时节点投票提交，否则投票中止。如果原子提交协议决定提交这个事务，其值就成为共识的决定值；如果原子提交中止，提议节点就用一个新事务重试。
由此可见，原子提交与共识也彼此等价。
大多数共识系统都提供共享日志，也就是全序广播。Raft、视图戳复制和 Zab 直接提供共享日志；Paxos 提供的是单值共识，但实践中，采用 Paxos 的系统大多使用名为 Multi-Paxos 的扩展，它同样提供共享日志。
共享日志与数据库复制十分契合，如果每条日志条目都代表一次数据库写入，而每个副本都以相同、 使用确定性逻辑处理相同的写入，那么所有副本最终都会处于一致状态。这个思想称为 状态机复制（state machine replication）。
类似地，共享日志还可以实现可串行化事务。如果每条日志条目都代表一个将以存储过程形式执行的确定性事务，而且每个节点都以相同顺序执行这些事务，那么事务就是可串行化的。
共享日志的另一个强大之处在于，它很容易改造成其他形式的共识：
前面已经看到，如果由一个“独裁者”节点作出决定，单值共识就很容易；类似地，如果只有一个领导者有权向共享日志追加条目，共享日志也很容易实现。问题在于：这个节点失效时，怎样才能实现容错？
传统的单主复制数据库并没有解决这个问题，而是把领导者故障切换留给管理员手工操作。人类的反应速度终究有限，这种方式难免造成相当长的停机时间，也不满足共识的终止属性。共识要求算法能够自动选出新的领导者。（并非所有共识算法都有领导者，但常用算法通常都有。）
所有节点必须就谁是领导者达成一致，否则两个不同节点可能都自认为是领导者，进而作出彼此矛盾的决定。如此看来，选举领导者需要共识，解决共识又需要领导者。怎样才能跳出这个先有鸡还是先有蛋的困局？
事实上，共识算法并不要求任何时刻都只有一个领导者，它们提供的是稍弱一些的保证；协议定义一个 纪元编号 （epoch number；Paxos 称为 投票编号，ballot number，视图戳复制称为 视图编号，view number，Raft 称为 任期编号，term number），并保证每个纪元内的领导者是唯一的。
如果一个节点在指定的超时时间内始终没有收到现任领导者的消息，因而认为它已经失效，这个节点就可能发起投票，选举新的领导者。这次选举会取得一个大于以往所有纪元的新纪元编号。如果两个不同纪元的领导者发生冲突，也许前任领导者其实并未失效，纪元编号较高的领导者说了算。
领导者要向共享日志追加下一条记录，必须先确认不存在纪元编号更高的其他领导者，否则后者可能会追加不同的条目。它可以向一组法定人数节点收集选票，这组节点通常是多数，但并非总是如此。只有在不知道任何更高纪元领导者的情况下，节点才会投赞成票。
因此，这里需要两轮投票：第一轮选举领导者；第二轮对领导者提议追加的下一条日志条目进行表决。两轮投票的法定人数必须相互重叠：如果某项提议表决通过，投赞成票的节点中，至少要有一个参加过最近一次成功的领导者选举。所以，如果提议表决通过，而且投票过程没有发现编号更高的纪元，现任领导者便可以断定，没有纪元编号更高的领导者当选，因而可以安全地把提议条目追加到日志。
这两轮投票表面上很像两阶段提交，实际上却是两种截然不同的协议。在共识算法中，任何节点都可以发起选举，而且只需一组法定人数节点响应；在 2PC 中，只有协调者能请求投票，并且必须从 每个 参与者那里得到“同意”票，事务才能提交。
Raft、Multi-Paxos、Zab 和视图戳复制都采用这一基本结构：先由一组法定人数节点投票选举领导者；此后，领导者想追加的每一条日志条目，还要经过另一组法定人数节点投票。每条新日志条目都要同步复制到一组法定人数节点，才会向发起写入的客户端确认成功。这样即使现任领导者失效，日志条目也不会丢失。
不过，魔鬼藏在细节里，而这些算法的差异也恰恰体现在细节中。例如，旧领导者失效并选出新领导者后，算法必须保证，新领导者会保留旧领导者在失效前已经追加的所有日志条目。Raft 的做法是：只有日志至少与多数追随者一样新鲜的节点，才有资格成为新领导者。Paxos 则允许任何节点成为新领导者，但要求它先从其他节点补齐日志，才能开始追加自己的新条目。
另一个微妙之处是，旧领导者在失效前已经提议了某条日志条目，但追加该条目的投票尚未结束，算法应该如何处理。
对于用共识算法做复制的数据库，不仅写入要转成日志条目并复制到一组法定人数节点。如果还要保证线性一致读取，读取也必须像写入一样经过法定人数投票，以确认那个自认为是领导者的节点确实仍掌握最新数据。etcd 的线性一致读取就是这样实现的。
大多数共识算法的标准形式都假定节点集合固定不变：节点可以下线后重新上线，但哪些节点有权投票，在集群创建时便已确定。实践中，却经常需要在系统配置中添加新节点或移除旧节点。共识算法因此扩展出了 重新配置 功能。向系统增加新地区，或把系统从一个位置迁往另一个位置时，这项功能尤其有用：可以先加入新节点，再移除旧节点。
如果希望共识算法严格保证 “共享日志作为共识” 中列出的属性，那么新领导者在处理任何写入或线性一致读取之前，必须掌握所有已经确认的日志条目。这是保证上述属性的必要条件。如果一个数据陈旧的节点成为新领导者，它可能会改写旧领导者已经写入的日志条目，从而违反共享日志的仅追加属性。
有些系统会选择削弱共识属性，以便更快地从领导者失效中恢复。例如，Kafka 可以启用 非同步副本选举（unclean leader election），允许任何副本成为领导者，即使它没有追上最新进度。另外，在采用异步复制的数据库中，领导者失效时，根本无法保证任何追随者已经赶上最新进度。
放弃“新领导者必须掌握最新数据”这一要求，或许能提高性能与可用性，却也如同在薄冰上行走，因为共识理论已经不再适用。没有故障时，系统固然可以正常工作；但一旦遇到 种种问题，就很容易造成大量数据丢失或损坏。
共识算法虽然复杂而微妙，却是分布式系统领域的一项重大突破，共识本质上就是“正确实现的单主复制”：领导者失效时自动进行故障切换；也能保证已提交的数据不会丢失，系统绝不会发生脑裂。
既然带自动故障切换的单主复制本质上就是共识的一种定义，那么，任何提供自动故障切换、却没有采用经过验证的共识算法的系统，都很可能不安全。当然，采用经过验证的共识算法，并不能保证整个系统一定正确，错误仍可能潜伏在许多其他角落，但至少是一个良好的开端。
尽管如此，共识并未无处不在，因为它的好处也有代价。共识系统总要有严格多数节点才能运行：要容忍一个节点故障，至少需要三个节点；要容忍两个节点故障，至少需要五个。每项操作都必须与一组法定人数节点通信，因此不能靠增加节点来提高吞吐量（实际上，每增加一个节点，算法反而会变慢）。如果网络分区把一部分节点同其余节点隔开，只有多数派所在的一侧能够取得进展，另一侧则会阻塞。
共识系统通常依靠超时来检测失效节点。在网络延迟变化很大的环境中，尤其是跨多个地理区域部署的系统，超时时间很难调好：设得太长，故障恢复会耗时很久；设得太短，又会触发大量不必要的领导者选举，导致性能极差，系统花在选举领导者上的时间，可能比花在有用工作上的还多。
有些共识算法对网络问题格外敏感。例如，Raft 已被发现存在一些棘手的边界情况：即使整个网络都运行正常，只要有一条特定链路始终不可靠，领导权就可能在两个节点之间来回跳转，或者现任领导者不断被迫辞职，导致系统实际上永远无法取得进展。怎样设计对不可靠网络更稳健的算法，至今仍是一个开放的研究问题。
如果系统既希望高可用，又不愿承担共识的成本，真正可行的选择只有改用较弱的一致性模型，例如 无主复制或多主复制。这些方法通常不提供线性一致性；不过，对于并不需要线性一致性的应用，这已经足够。
任何想提供线性一致操作的分布式数据库，都能从共识算法中受益；许多现代分布式数据库确实也用共识算法做复制。不过，有一类系统尤其倚重共识：ZooKeeper、etcd、Consul 等 协调服务（coordination service）。它们表面上与普通键值存储相似，却不像大多数数据库那样以通用数据存储为目标。
协调服务的用途，是协调另一个分布式系统中的多个节点。例如，Kubernetes 依赖 etcd；Spark 和 Flink 在高可用模式下，则依赖后台运行的 ZooKeeper。协调服务只保存少量足以全部放入内存的数据（同时仍会写入磁盘以保证持久性），再用容错共识算法把这些数据复制到多个节点。
协调服务以 Google 的 Chubby 锁服务为蓝本，把共识算法与几项对构建分布式系统格外有用的功能结合在一起：
故障检测与变更通知本身并不需要共识；但把它们同确实需要共识的原子操作、栅栏机制组合起来，对分布式协调就格外有用。
应用与基础设施通常都有超时时间、线程池大小等配置参数。有时，人们会把这类配置数据以键值对形式存入协调服务。进程启动时加载最新配置，并订阅此后的变更通知。配置变化后，进程可以立即采用新设置，也可以通过重启来加载最新设置。
配置管理本身并不需要协调服务的共识能力；不过，如果系统本来就在运行协调服务，顺便利用它的通知功能会很方便。另一种办法是让进程定期从文件或 URL 轮询配置更新，从而不必依赖专门的协调服务。
如果某个进程或服务有多个实例，需要从中选出一个领导者或主实例，协调服务就很有用。领导者失效时，应当由其他某个节点接管。这对单主数据库必不可少，也适用于作业调度器等有状态系统。
另一种场景是分配分片资源（数据库、消息流、文件存储、分布式 Actor 系统等）：系统需要决定每个分片交给哪个节点。新节点加入集群时，需要把一部分分片从现有节点移到新节点，以重新平衡负载；节点被移除或失效时，则要由其他节点接手它的工作。
审慎组合协调服务中的原子操作、临时节点与通知机制，就可以完成这类任务。实现得当时，应用能在无需人工干预的情况下自动从故障中恢复。即使已经有 Apache Curator 之类基于 ZooKeeper 客户端 API 提供高层工具的库，这仍然不是一件容易的事；但无论如何，都远胜于从头实现所需的共识算法，后者极易埋下错误。
专用协调服务还有一个优点：无论依赖它协调的分布式系统有多少节点，协调服务本身都可以只运行在一组固定节点上，通常是三个或五个。例如，一个存储系统拥有数千个分片；若让数千个节点共同运行共识算法，效率会低得惊人。把共识“外包”给少量运行协调服务的节点，要合理得多。
协调服务管理的数据通常变化缓慢，例如“IP 地址为 10.1.1.23 的节点是分片 7 的领导者”这类分配关系，往往几分钟或几小时才会变一次。协调服务并非用来存储每秒可能变化数千次的数据；这类数据更适合交给常规数据库。或者，也可以用 Apache BookKeeper 之类的工具，复制服务内部快速变化的状态。
ZooKeeper、etcd 和 Consul 也经常用于 服务发现（service discovery），即找出应当连接哪个 IP 地址才能访问特定服务。
云环境中的虚拟机不断创建和销毁，通常无法预先知道服务的 IP 地址。常见做法是让服务在启动时把自己的网络端点注册到服务注册表，供其他服务查找。
用协调服务做服务发现很方便：故障检测与变更通知功能，让客户端很容易跟踪服务实例的增减。如果系统已经用协调服务管理租约、锁或领导者选举，继续用它做服务发现也顺理成章，因为它本来就知道哪个节点应当接收服务请求。
不过，服务发现使用共识往往有些杀鸡用牛刀。这个场景通常不要求线性一致性；高可用与低延迟反而更加重要，因为一旦服务发现不可用，整个系统都会停摆。因此，更常见的做法是缓存服务发现信息，并接受结果可能略有陈旧。例如，基于 DNS 的服务发现就通过多层缓存获得良好的性能与可用性。
为支持这类用途，ZooKeeper 提供了 观察者（observer）节点。这些副本会接收日志、维护一份 ZooKeeper 数据副本，却不参与共识算法的投票。观察者上的读取可能陈旧，因而不具备线性一致性；但即使网络中断，读取仍可继续，而且缓存还能提高系统所能支持的读取吞吐量。