文档教程【免费下载链接】ddia《Designing Data-Intensive Application》DDIA 第一版 / 第二版 中文翻译项目地址https://gitcode.com/gh_mirrors/dd/ddia点击查看免费下载本篇技术指南以《Designing Data-Intensive Applications》DDIA第二版第 10 章一致性与共识为骨架结合本仓库的 英文原文 与 中文译本 深度展开。你将系统掌握三大核心能力理解强一致性的精确定义——线性一致性linearizability掌握分布式 ID 生成器与逻辑时钟Lamport 时钟、混合逻辑时钟的设计取舍并理解共识consensus算法如何让分布式系统在线性一致性与容错之间取得平衡。无论你是后端工程师、数据库开发者还是分布式系统架构师本章的理论框架都是设计可靠数据系统的必修课。从容错说起复制带来的不一致难题分布式系统里可能出错的事情很多第 9 章 已详述要让服务在这些故障发生时仍能正确运行就必须设法容忍故障。复制replication是实现容错最有力的工具之一。但把同一份数据复制到多个副本也带来了不一致的风险读请求可能由尚未追上进度的副本处理、返回陈旧结果如果多个副本都能接受写入还必须解决并发写入产生的值冲突。处理这类问题有两种彼此竞争的思路最终一致性eventual consistency把系统采用复制这一事实暴露给应用由应用开发者处理随之而来的不一致与冲突。采用多主复制multi-leader replication和无主复制leaderless replication的系统常常使用这种方式。强一致性strong consistency应用不应操心复制的内部细节系统应当表现得仿佛只有一个节点。代价是更强的一致性会损害性能而且有些在最终一致系统中尚可容忍的故障会令强一致系统停摆。哪种方式更好取决于具体应用如果应用允许用户离线修改数据最终一致性不可避免如果各副本位于通信快速而可靠的数据中心强一致性的成本通常可以接受因而往往更合适。本章深入讨论强一致性重点考察三个方面线性一致性强一致性这个说法相当含糊需要给出更精确的目标。ID 和时间戳的生成看似与一致性无关实际上关系密切。共识算法分布式系统如何既实现线性一致性又保持容错能力。在此过程中会看到分布式系统中什么可以做到、什么无法做到受到一些根本限制。本章内容素以难以正确实现而著称——一个系统在没有故障时运行良好并不难难的是它可能在某种设计者未曾考虑的不利故障组合下彻底崩溃。线性一致性让分布式系统表现得像单机要让复制数据库尽可能简单易用最好让它表现得仿佛根本没有复制。这就是线性一致性linearizability1——也称为原子一致性atomic consistency、强一致性、即时一致性immediate consistency或外部一致性external consistency2——背后的思想让系统看起来仿佛只有一份数据所有操作都原子地作用于这份数据。在线性一致的系统中只要一个客户端成功完成写入此后所有客户端读取时都必须能看到刚写入的值。维持只有一份数据的假象就必须保证读到的是最近写入的最新值而不是来自陈旧缓存或副本的旧值。换句话说线性一致性是一种新鲜度保证recency guarantee。以 图 10-1 的体育网站为例Aaliyah 和 Bryce 坐在同一房间用手机关注比赛终场比分刚公布Aaliyah 刷新页面看到了获胜方并告诉 BryceBryce 随后刷新请求却被路由到落后的副本页面仍显示比赛进行中。若两人同时刷新得到不同结果倒不意外但 Bryce 明确知道自己是听到 Aaliyah 报出比分之后才发起查询的因此有理由期待结果至少不比 Aaliyah 看到的更旧。返回陈旧数据就违反了线性一致性。什么使系统具有线性一致性在分布式系统理论中被读写对象称为寄存器register实际系统里它可以是键值存储中的一个键、关系数据库中的一行或文档数据库中的一个文档。寄存器上有两类基本操作read(x) ⇒v客户端请求读取寄存器x数据库返回值v。write(x,v) ⇒r客户端请求把寄存器x设为v数据库返回响应rok或error。考虑一个寄存器x初始值为 0客户端 C 写 1同时客户端 A、B 不断轮询读值的场景A 在写入开始前完成的读取必然返回旧值 0A 在写入完成后开始的读取在线性一致数据库中必然返回新值 1与写操作时间上重叠的读取可能返回 0 或 1——这些操作与写入是并发的。但这还不够。如果并发读可以任意返回新旧值读者可能看到值在新旧之间来回跳变这不符合只有一份数据的预期。因此还需一条额外约束在线性一致的系统中可以设想写操作起止之间存在某个时刻x的值在那一点原子地从 0 变为 1。一旦某个客户端读到新值 1此后所有读取也必须返回 1即使写操作本身尚未结束——这就是线性化点的思想每个操作在某个时刻原子生效。更复杂的情形图 10-4还加入了第三种操作cas(x,vold,vnew) ⇒r原子比较并设置compare-and-set操作若寄存器x当前值等于vold 则原子地改为vnew否则保持不变并返回错误。把每个操作视为在某个时刻原子生效再将各操作标记按序连接得到的必须是寄存器的一条合法读写序列——每次读取都返回最近一次写入所设置的值。线性一致性要求这些标记连线只能沿时间向前移动从左向右绝不能倒退。几个容易误解的细节请求发出顺序可以不同于数据库处理顺序并发请求处理顺序任意只要合法一个客户端可能在写客户端收到ok确认之前就读到新值响应在网络中延迟所致模型不作事务隔离假设其他客户端随时可能改值。实践中可以用工具记录所有请求与响应的时序再检查它们能否排成一条合法的顺序序列来检验线性一致性——只是这种检验的计算成本很高。线性一致性与可串行化必须区分的两种保证线性一致性很容易与可串行化混淆但二者是完全不同的保证特性可串行化Serializability线性一致性Linearizability作用对象事务的隔离属性可读写多个对象行、文档、记录寄存器单个对象的读写保证核心保证事务行为等同于按某种串行顺序执行顺序可与实际运行顺序不同新鲜度保证若一个操作在另一个操作开始前完成后者必须观察到至少同样新的状态防止的问题防止事务交错导致的异常不防止涉及多对象的写入偏斜write skew等问题对陈旧读的态度允许陈旧读不允许数据库可以同时提供二者这种组合称为严格可串行化strict serializability或强一拷贝可串行化strong-1SR。单节点数据库通常既是可串行化又是线性一致的采用可串行化快照隔离SSI这类乐观方法的分布式数据库则更复杂——例如 CockroachDB 提供可串行化以及部分读取新鲜度保证但不提供严格可串行化因为那需要事务间昂贵的协调。此外一致性模型与隔离级别在很大程度上可以彼此独立选择。依赖线性一致性的场景锁与主节点选举采用单主复制single-leader replication的系统必须确保只有一个主节点防止 split brain。一种选主方式是租约lease每个启动的节点尝试获取租约成功者成为主节点无论机制如何实现它必须满足线性一致性——不能让两个节点同时获取租约。Apache ZooKeeper 和 etcd 等协调服务常用来实现分布式租约与选主它们用共识算法以容错方式实现线性化操作。严格来说 ZooKeeper 只保证写操作线性一致读可能陈旧etcd 自 3.x 起默认提供线性化读。Oracle Real Application ClustersRAC则按磁盘页加锁多节点共享同一磁盘存储由于这些线性化锁处于事务执行关键路径上RAC 部署通常配备专用集群互联网络。约束与唯一性保证用户名、邮箱必须唯一标识一个用户文件存储服务中不能存在同名同路径文件。若要在写入时强制执行这类约束两个用户并发注册同一用户名一个成功一个报错就需要线性一致性。这实际上类似锁用户注册相当于在所选用户名上获取锁操作也类似原子 CAS——前提是用户名尚未被占用就把它设为认领用户的 ID。银行账户余额不为负、库存不超卖、机票或剧院座位不重复预订也都要求所有节点对单一最新值余额、库存、座位占用状态达成一致。宽松约束如超卖后可改签并补偿可以不依赖线性一致性但关系数据库中典型的硬唯一性约束需要它外键等约束则可以不借助线性一致性实现。跨通道时序依赖这是最容易忽视的场景。设想一个视频上传网站Web 服务器把视频写入文件存储服务写完后通过消息队列通知后台转码器处理。图 10-5 展示了这一数据流。若文件存储服务不是线性一致的就可能出现竞态消息队列的投递比存储服务内部复制更快转码器取回的是旧版本视频甚至什么都没有——原始视频与转码结果永久不一致。问题的根源在于 Web 服务器与转码器之间存在两个通信通道文件存储与消息队列没有新鲜度保证就可能出现竞态。移动应用的推送通知场景同样如此通知很快到达但随后拉取数据的请求可能打到落后副本看不到通知所描述的数据。线性一致性不是避免竞态的唯一方法若你控制额外通道可用读自己写入等替代方案但它是最容易理解的一种。实现线性一致的系统各复制方法的可行性对比线性一致性本质上意味着表现得像只有一份数据最朴素的想法就是真的只用一份数据——但那无法容忍故障持有该副本的节点一旦宕机数据就丢失或不可访问。回到第 6 章 的复制方法逐一评估单主复制可能线性一致只要所有读写都走主节点通常就是线性一致的。但前提是你确切知道谁是主节点——节点可能误以为自己是主节点分布式锁与租约 中讨论过妄想型主节点继续服务请求就会违反线性一致性。异步复制下故障切换甚至可能丢失已提交写入同时违反持久性与线性一致性。按分片各设主节点的做法不影响线性一致性它是单对象保证跨分片事务则是另一回事。共识算法很可能线性一致一些共识算法本质上是带自动选主与自动故障切换的单主复制被精心设计为防止 split brain因而能安全实现线性化存储。例如 ZooKeeper 使用 Zabetcd 使用 Raft。但使用共识并不自动保证所有操作线性一致若允许节点不确认自己仍是主节点就提供读服务新主刚选出时读到的结果可能陈旧。多主复制不线性一致多个节点并发处理写入并异步复制会产生需要解决的冲突写入因此一般不满足线性一致性。无主复制大概不线性一致Dynamo 风格的无主复制常被声称通过仲裁读写wrn获得强一致性但严格来说并不成立。仲裁为何不足以保证线性一致图 10-6 展示了竞态场景。初始x 0写客户端向全部三个副本写 1n 3,w 3客户端 A 从一个双节点仲裁r 2读到新值 1客户端 B 从另一个双节点仲裁读到旧值 0。仲裁条件wrn虽然满足但执行并不线性一致B 的请求在 A 完成后才开始却读到更旧的值。要让 Dynamo 风格仲裁线性一致代价是降低性能读者必须在返回结果前同步执行读修复写者必须在写前读取仲裁节点的最新状态确保新写入的时间戳更大。即便如此Riak 因性能代价不执行同步读修复Cassandra 在仲裁读上等待读修复完成却因使用墙上时钟做时间戳而失去线性一致性。更重要的是只有线性化的读写操作能这样实现线性化的 CAS 不行——它需要共识算法。总结最稳妥的假设是Dynamo 风格无主系统即使使用仲裁读写也不提供线性一致性。线性一致性的代价CAP 定理与网络延迟考虑两个区域之间的网络中断网络分区多主数据库中每个区域可继续独立运作写入排队待网络恢复后交换单主数据库中跟随者区域的客户端无法联系主节点既不能写也不能线性化读仍可做可能陈旧的普通读应用在无法触达主节点的区域整体不可用。这个问题不限于单主/多主任何线性化数据库都有此问题若应用要求线性一致性分区期间部分副本无法处理请求——要么等待网络修复要么返回错误即CP分区时保持一致性。若不要求线性一致性可让每个副本独立处理请求如多主分区期间仍可用AP分区时保持可用。这一洞察即著名的CAP 定理2000 年由 Eric Brewer 命名虽然 1970 年代分布式数据库设计者就已知道这一权衡。CAP 最初只是作为启发式规则提出旨在开启数据库权衡的讨论客观地说它推动了 NoSQL 运动——这值得肯定。但 CAP 也常被误导性地表述为一致性、可用性、分区容错性三选二。这种表述有误导性网络分区是一种故障你无从选择它是否发生。更准确的说法是网络正常时系统可同时提供一致性与可用性网络故障时必须在二者间选择。此外CP/AP 分类还有若干缺陷CAP 的一致性被形式化为线性一致性对弱一致性模型无话可说其对可用性的形式化也与通常含义不符还有些系统两者都不提供、既非 CP 也非 AP。从正式定义看CAP 定理范围很窄只考虑一种一致性模型线性一致性和一种故障网络分区——据 Google 数据分区只占不到 8% 的事故不涉及网络延迟、宕机节点或其他权衡。CAP 虽有历史影响力但对设计系统的实际价值有限最好避免使用。作为推广PACELC 原则指出网络分区时P需要在可用性A与一致性C间选择否则E时可在低延迟L与一致性C间选择。实践中很少有系统真正线性一致多核 CPU 的 RAM 都不线性一致缓存与存储缓冲异步回写主存因为放弃线性一致性是为了性能而非容错。Attiya 与 Welch 证明若要线性一致性读写响应时间至少与网络延迟的不确定性成正比在高延迟变动的网络中线性化读写响应时间必然很高不存在更快的线性化算法。弱一致性模型则可以快得多——这个权衡对延迟敏感系统至关重要。ID 生成器与逻辑时钟很多应用需要为数据库记录分配唯一 ID 作为主键。单节点数据库常用自增整数只占 64 位若确定记录数不会超过 40 亿也可用 32 位但这很冒险且 ID 顺序即创建顺序——例如聊天应用可据自增 ID 排序消息Aaliyah 的提问 ID 为 1Bryce 的回答 ID 更大图 10-8。这个单节点 ID 生成器本身就是一个线性化系统每次取 ID 都是一次原子递增并返回旧值的操作fetch-and-add线性一致性保证先完成的消息获得更小 ID。内存中的实现很容易用 CPU 原子递增指令即可难点在于持久化节点崩溃重启不能重置计数器导致重复 ID以及三个现实问题单点故障、跨地域取 ID 需绕地球半圈的网络往返、高写入吞吐下成为瓶颈。分布式 ID 生成方案对比方案优点缺点分片 ID 分配多个节点并行分配ID 仍紧凑丢失排序属性ID 16 与 17 无法判断谁先发出不同节点可能进度不同预分配 ID 块节点从块内独立发号块将耗尽时再向中心申请排序同样不保证后分配的消息可能拿到更小的 ID随机 UUIDv4本地生成无需通信碰撞概率极低占用 128 位顺序随机无法比较新旧墙上时钟 唯一性填充高位为时间戳可粗略排序实现如 Version 7 UUID、Twitter Snowflake、ULID、Hazelcast Flake、MongoDB ObjectID依赖 NTP 时钟同步时钟跳变或偏斜时排序可能与真实事件顺序不一致难以线性一致这些方案都能生成足够唯一的 ID但排序保证远弱于单节点自增。基于墙上时钟的 ID 生成器还受制于时钟偏斜稍快的时钟先写的事件可能拿到更晚的时间戳。利用原子钟或 GPS 接收机做高精度同步可缓解但能否不依赖特殊硬件就生成唯一且有序的 ID这就要说到逻辑时钟。逻辑时钟Lamport 时间戳与混合逻辑时钟物理时钟墙上时钟、单调时钟测量流逝的秒数逻辑时钟logical clock则是统计已发生事件的算法。逻辑时钟的时间戳不告诉你现在几点但可以比较两个时间戳的先后。典型要求时间戳紧凑几个字节且唯一任意两个时间戳可比较全序顺序与因果一致——若操作 A 发生在 B 之前则 A 的时间戳小于 B 的。Lamport 时间戳1978 年 Leslie Lamport 提出每个节点有唯一标识实践中可用随机 UUID并维护一个计数器时间戳即二元组counter,node ID。每次生成时间戳节点递增本地计数并使用新值每次看到来自其他节点的时间戳若其计数大于本地计数就把本地计数提升到该值。比较时先比较计数计数相同则按节点 ID 字典序比较。例如 图 10-9 中 Aaliyah 和 Caleb 各自从 0 递增到 1 发消息Bryce 收到后把计数提升到 1回复时再递增到 2。时间戳顺序为 (1, Aaliyah) (1, Caleb) (2, Bryce)。Lamport 时钟的局限与物理时间无直接关系无法按日期检索事件互不通信的节点计数可能差距悬殊。混合逻辑时钟HLC结合物理时钟的读数能力与 Lamport 时钟的排序保证像物理时钟一样计数秒或微秒看到更大的其他节点时间戳时把自己的本地值前移每次生成时间戳再递增——保证单调前进即使底层物理时钟如 NTP 调整回跳。HLC 时间戳几乎可以当作常规墙上时钟时间使用又附加了与 happened-before 关系一致的排序不依赖特殊硬件只需大致同步的时钟。CockroachDB 即使用 HLC。与向量时钟的取舍Lamport/HLC 适合生成快照隔离的事务 ID保证快照与因果一致。但当多个时间戳并发生成时算法会任意排序它们一般无法从两个时间戳判断是否并发。若要能判断记录是否并发创建需要向量时钟——代价是时间戳大得多可能为每个节点存一个整数。线性化 ID 生成器从逻辑时钟到共识的缺口图 10-10 展示了非线性化 ID 生成器引发的问题用户 A 先在笔记本上把公开账号改为私密再用手机上传私密照片。账号权限与照片存储在两个数据库或同一数据库的不同分片各自用 Lamport/HLC 分配时间戳。照片库没读过账号库本地计数落后照片上传被分配了比账号设置更新更小的时间戳。查看者用 MVCC 快照读时快照时间戳大于照片上传却小于账号更新于是系统判定账号当时仍公开展示了不该看到的私密照片。最简单的修复是用线性化 ID 生成器确保照片上传获得更大 ID。实现方式单节点原子递增计数器 持久化防重启重复 单主复制容错。TiDB/TiKV 称之为时间戳预言机timestamp oracle灵感来自 Google Percolator。优化不必每次请求都做磁盘写入与复制可批量分配——持久化复制一条描述一批 ID 的记录后节点按序发放节点崩溃或切换到跟随者时会跳过部分 ID但不会重复或乱序。该生成器不能轻易分片多个分片发号无法保证全序线性化也难以跨地域分布好在其职责极简单节点可支撑高吞吐。替代方案是 Google Spanner 的做法第 9 章同步时钟用于全局快照物理时钟返回的不是单一时间戳而是一个表示不确定性的区间然后等待该不确定区间过去再返回。若区间估计正确真实物理时间总在区间内即使跨地域请求也能在无通信的情况下正确排序前提是硬件与软件对时钟同步和不确定性区间计算提供支持。为什么逻辑时钟不足以实现锁与唯一性约束用逻辑时钟给争抢同一锁/用户名的请求排序、取最小时间戳者为胜看似可行但难题在于节点如何知道自己的时间戳就是最小它必须听到每一个可能生成时间戳的节点的回应——若有节点故障或网络不通系统就会停滞因为我们无法确定那个节点是否持最小时间戳。这不符合容错要求。要实现容错的锁、租约等构造需要比逻辑时钟或 ID 生成器更强的东西——共识。共识分布式系统的基石本章已经看到许多单节点容易、容错后极难的问题单主复制如何安全故障切换而避免 split brain线性化 ID 生成器崩溃后怎么办CAS 操作决定谁获得锁/租约、保证文件或用户名唯一性如何做到容错。所有这些问题都是同一个根本问题的实例共识consensus——分布式计算中最重要、最基础、也最臭名昭著难以做对的问题。最著名的共识算法包括 Viewstamped Replication、Paxos、Raft 和 Zab彼此相似但不相同。它们工作在非拜占庭系统模型下网络消息可任意延迟或丢弃节点可崩溃、重启、断连但假定节点会正确遵守协议、不恶意行为。另有能容忍部分拜占庭节点的 BFT 算法常见假设是少于三分之一的节点为拜占庭故障用于区块链——但超出本书范围。FLP 不可能性共识真的无解吗以 Fischer、Lynch、Paterson 命名的FLP 结果证明在节点可能崩溃的系统中不存在总能达成共识的算法。但 FLP 只说明不能保证总是终止且其证明基于异步系统模型中的确定性算法不能使用时钟或超时。只要允许使用超时来怀疑节点崩溃哪怕有时猜错共识就变得可解甚至仅允许算法使用随机数也能绕过不可能性。因此虽然 FLP 在理论上极其重要分布式系统在实践中通常可以达成共识。共识的多种面孔等价问题家族共识可以表述为多种形式它们彼此等价——有了其中一个的解法就能转换成其他任何一个的解法单值共识多个节点对一个值达成一致类似原子 CAS可实现锁、租约、唯一性约束。共识算法必须满足四条性质统一同意Uniform agreement没有两个节点做出不同决定完整性Integrity节点一旦决定某值不能改判另一个值有效性Validity节点决定的值v必须曾被某个节点提出过排除总是决定 null这类平凡解终止性Termination不崩溃的节点最终都做出决定——这是活性liveness属性前三者是安全性safety属性。不关心容错时前三条性质很容易满足硬编码一个独裁者节点做决定即可但独裁者失败系统就停摆。共识算法要求至少多数节点正常运转才能保证终止好在安全属性同意、完整、有效即使在多数节点故障或严重网络问题时也始终成立——大规模故障只会让系统无法处理请求不会造成不一致的决定。CAS 即共识有了容错线性化的 CAS容易解决共识——对象初始化为 null节点用 CAS期望 null新值为自己的提议竞争最终对象的值即决定值反之有了共识也能实现 CAS用共识协议决定 CAS 的新值落选者返回错误。但线性化读写寄存器不足以解决共识——这正是从 FLP 与仲裁实现寄存器的事实推出的结论。共享日志 / 全序广播即共识日志存储有序条目序列所有读者看到相同顺序。共享日志shared log形式化为全序广播、原子广播的性质最终追加请求者最终读到自己的值、可靠投递不丢条目、仅追加条目不可变、同意读同一条目 e 之前必须读到完全相同的前缀序列、有效性。有了共享日志即得共识每个提议者请求把值追加到日志日志中第一个出现的值即决定值反之为每个未来日志槽位运行一次共识实例被选中的值依次追加成条目。单主复制不满足活性要求——主节点崩溃就停止投递挑战在于安全而自动地故障切换。fetch-and-add 与共识数线性化 ID 生成器fetch-and-add几乎就是共识但差一步。所有节点执行 fetch-and-add 后读到 0 的节点是赢家——但其他节点不知道赢家是谁若赢家在广播结果前崩溃共识无法终止。例外是确定最多两个节点提议时两节点互发提议再各自 fetch-and-add 即可解决因此 fetch-and-add 的共识数consensus number为 2而 CAS 与共享日志对任意数量节点可解共识数为 ∞。原子提交即共识分布式事务的原子提交如两阶段提交与共识表面相似但有重要区别共识可以决定任意被提出的值而原子提交只要任一参与者投票中止就必须中止。原子提交的性质统一同意、完整性、有效性若决定提交则所有节点必须此前都投了提交票任一节点投了中止则必须中止、非平凡性全部节点都投票提交且无通信超时则必须提交、终止性。有了共识可解原子提交每节点把投票提交/中止提议给共识算法得知决定后相应提交或中止有了容错原子提交也可解共识——两者等价。实践中的共识从共享日志到自动化选主理论等价性很有价值但实践中最有用的形式是什么答案是共享日志全序广播Raft、Viewstamped Replication、Zab 直接提供共享日志Paxos 提供单值共识实践中多数系统使用其扩展 Multi-Paxos 也提供共享日志。共享日志的用途每个日志条目代表一次数据库写入所有副本用确定性逻辑按相同顺序处理相同写入最终状态一致——即状态机复制state machine replication也是事件溯源第 3 章背后的原理共享日志还可用于流处理第 12 章。每个日志条目代表一个确定性存储过程事务、各节点按相同顺序执行即可实现可串行化事务实际串行执行。强一致模型的分片数据库通常每分片维护独立日志这提升可扩展性但限制跨分片保证一致快照、外键引用跨分片可串行化事务需要额外协调。共享日志还能衍生出其他共识形式决定日志中第一个出现的值即单值共识把座位号写入条目即可为每个座位做一次决定把计数增量写入条目、当前计数值即历史条目之和——日志上的简单计数器可用于生成 fencing tokenZooKeeper 中叫zxid。从单主复制到共识传统单主数据库把主节点故障切换留给人工 DBA 操作这带来大量停机时间也不满足共识的终止性。矛盾在于选主需要共识解共识又需要主节点——如何打破循环答案是共识算法并不要求任何时刻只有一个主节点而是定义纪元号epoch numberPaxos 称ballot numberViewstamped Replication 称view numberRaft 称term number保证每个纪元内主节点唯一。节点超时未听到主节点消息时可发起更高纪元号的新选举两个纪元的冲突以更高纪元的主节点为准。主节点追加下一条日志前必须先通过收集法定人数节点的投票确认不存在更高纪元的主节点。于是有两轮投票选主一次为主节点追加日志的提议投票一次——两次投票的仲裁必须相交从而保证赢得提议投票时没有更高纪元的主节点被选出。这与两阶段提交表面相似但本质不同共识算法中任何节点可发起选举、只需仲裁响应2PC 只有协调者可请求投票、提交前需要所有参与者投是。共识的微妙之处所有 Raft/Multi-Paxos/Zab/VR 共享这一基本结构仲裁投票选出主节点主节点追加的每条日志再经一次仲裁投票每条新条目在向客户端确认前同步复制到仲裁——确保主节点故障时不丢条目。细节差异在于旧主故障后Raft 只允许日志至少与多数跟随者一样新的节点当选Paxos 允许任意节点当选但要求其先补全日志再追加新条目。若允许陈旧节点当选它可能覆盖旧主已写入的条目违反仅追加属性——严格保证共识属性要求新主在服务写入/线性化读前补齐所有已确认条目。有些系统会为更快恢复而放宽这一要求例如 Kafka 的unclean leader election允许任何副本当选异步复制的数据库也无法保证故障切换时任一跟随者是最新的。放宽后性能与可用性可能改善但共识理论不再适用故障时极易造成大量数据丢失或损坏。此外线性化读也需要像写一样经过仲裁投票确认自认主节点确实仍是最新的etcd 的线性化读即如此多数共识算法假定固定的节点集合实践中需要重配置reconfiguration功能支持增删节点例如跨地域扩展或迁移。共识的优缺点共识本质上是做得对的单主复制——自动故障切换、不丢已提交数据、杜绝 split brain这是巨大突破。但代价不菲始终需要严格多数容忍 1 个故障至少 3 节点容忍 2 个至少 5 节点每次操作都要与仲裁通信加节点只会让算法更慢吞吐不增反降分区时只有多数侧能推进。共识依赖超时检测故障延迟波动大尤其跨地域时超时调优困难太大则故障恢复慢太小则频繁无谓选举、系统把时间花在选主上。Raft 还被证明存在不愉快边界情况当整个网络正常、仅某一条链路持续不可靠时领导权可能在两个节点间反复横跳系统实际无法推进。想要高可用又不接受共识成本唯一现实替代是弱一致性模型无主或多主复制——它们通常不提供线性一致性但对不需要它的应用正合适。协调服务共识的忠实用户协调服务ZooKeeper、etcd、Consul是共识算法最突出的用户。它们外表像键值存储但并非为通用数据存储设计而是用于协调另一个分布式系统的节点Kubernetes 依赖 etcdSpark 与 Flink 的高可用模式依赖 ZooKeeper。协调服务的数据量小到可全部放入内存仍写磁盘保证持久性由容错共识算法复制。这类服务以 Google 的 Chubby 锁服务为模型把共识算法与几项对构建分布式系统特别有用的特性结合锁与租约利用共识实现的容错原子 CAS——多个节点并发争抢同一租约时只有一个成功。fencing 支持给每个日志条目单调递增 IDZooKeeper 的zxid、cversionetcd 的 revision 号用于生成 fencing token 防止进程暂停或大延迟时客户端相互干扰。故障检测客户端维持长会话、周期心跳心跳超时则服务端认定客户端死亡并释放租约ZooKeeper 称临时节点ephemeral nodes。连接暂时中断或服务器故障时租约保持有效。变更通知客户端可订阅键变化通知从而发现其他客户端加入集群或失败会话超时、临时节点消失免去频繁轮询。故障检测与变更通知本身不需要共识但配合依赖共识的原子操作与 fencing 支持构成了分布式协调的完整工具箱。协调服务也常用来存储配置超时、线程池大小等键值对进程启动时加载最新配置并订阅变更通知配置变化后立即生效或重启加载。配置管理本身不需要共识但既然已在运行协调服务顺便利用其通知能力很方便。工作分配协调服务适合从多个进程实例中选主/主节点、失败后接管也适合为分片资源数据库、消息流、文件存储、分布式 actor 系统决定分片归属、在节点加入/退出时再平衡。正确组合原子操作、临时节点与通知应用就能自动从故障中恢复——虽不简单Apache Curator 等库提供了 ZooKeeper 客户端之上的高级配方但远比自己实现共识算法可靠。专用协调服务的另一优势无论被协调系统有多少节点协调服务自身通常只需固定三五个节点——给上千个分片跑共识算法极其低效把共识外包给少量节点要划算得多。注意协调服务适合变化缓慢的数据IP 10.1.1.23 的节点是分片 7 的主节点分钟或小时级变化每秒变化数千次的数据应使用常规数据库或用 Apache BookKeeper 复制服务内部快速变化的状态。服务发现ZooKeeper、etcd、Consul 也常用于服务发现——云端虚拟机来来去去服务启动时在网络端点注册表注册自身供其他服务查找。既然已经用协调服务做租约、锁或选主顺便用它做服务发现很自然。但对服务发现而言共识往往大材小用这个用例通常不需要线性一致性更需要高可用与低延迟。因此更常见的做法是缓存服务发现信息、容忍轻微陈旧——DNS 式服务发现就用多层缓存换取性能与可用性。为此 ZooKeeper 支持observer观察者接收日志并维护数据副本但不参与投票的副本——observer 读不线性化可能陈旧但网络中断时仍可用并通过缓存提升系统可支撑的读吞吐。总结本章深入考察了容错系统中的强一致性是什么以及如何实现。线性一致性是强一致性的流行形式化复制数据表现得仿佛只有一份拷贝所有操作原子地作用于它。需要读到最新数据、或需要解决竞态如多节点并发创建同名文件时线性一致性非常有用。它容易理解让数据库表现得像单线程程序中的变量但代价是慢——尤其在网络延迟大的环境中。许多复制算法表面上可能像提供了强一致性实际并不保证线性一致性。ID 生成器单节点自增计数器是线性一致的但不容错许多分布式 ID 生成方案不保证 ID 顺序与事件真实发生顺序一致。Lamport 时钟、混合逻辑时钟等逻辑时钟提供与因果一致的排序但不提供线性一致性。共识意味着以所有节点同意、且不可改判的方式做出决定。大量问题都可归结为共识且彼此等价线性化 CAS、锁与租约、唯一性约束、共享日志全序广播、原子事务提交、线性化 fetch-and-add此例只对两个节点可解。这些在单节点上都很简单或可以交给单一决策节点单主数据库的实质但主节点故障或不可达时系统停滞直到人工故障切换。Raft、Paxos 等共识算法本质上是内置自动选主与故障切换的单主复制——精心设计确保故障切换不丢已提交写入、不进入多节点同时接受写入的 split brain 状态。这要求每次写入和每次线性化读都被仲裁通常为多数确认跨地域尤其昂贵但这是强一致性与容错兼得的必要条件。协调服务ZooKeeper、etcd基于共识算法构建提供锁、租约、故障检测与变更通知用于管理分布式应用状态。若你想做某件可归结为共识的事且要求容错使用协调服务是明智之选——它不保证你一定做对但很可能帮到你。共识并不总是对的工具有些系统不需要强一致性弱一致性加高可用与更好性能更合适可用无主或多主复制本章的逻辑时钟在那类场景中很有帮助。共识算法复杂而微妙但有 1980 年代以来发展出的丰富理论支撑使构建能容忍第 9 章 所述各种故障、同时保证数据不被破坏的系统成为可能——这是了不起的成就。本章参考文献列出了该领域的重要工作可作为深入学习的起点。仓库资源索引本篇基于 英文原文含完整参考文献列表与 中文译文 撰写繁体版本见 content/tw/ch10.md全部插图位于 static/fig/本文引用的 图 10-1、图 10-6、图 10-9 等时序示意图本仓库为 Hugo 站点构建配置见 hugo.yaml启用了 footnote、table 等 Markdown 扩展可通过 Makefile 中的make dev、make build、make epub等目标本地构建与导出。Maurice P. Herlihy and Jeannette M. Wing, Linearizability: A Correctness Condition for Concurrent Objects, TOPLAS 12(3), 1990.↩David K. Gifford, Information Storage in a Decentralized Computer System, Xerox PARC, CSL-81-8, 1981.↩赞分享文档教程【免费下载链接】ddia《Designing Data-Intensive Application》DDIA 第一版 / 第二版 中文翻译项目地址https://gitcode.com/gh_mirrors/dd/ddia点击查看免费下载相关推荐深入解读 DDIA 第 10 章从线性一致性、逻辑时钟到分布式共识的完整图谱深入解读 DDIA 第 10 章从线性一致性、逻辑时钟到分布式共识的完整图谱 本文以《Designing Data Intensive Application文档教程DDIA 一致性与共识精读从线性一致性、全序广播到容错共识的完整技术地图DDIA 一致性与共识精读从线性一致性、全序广播到容错共识的完整技术地图 本篇技术指南以《Designing Data Intensive Applicati文档教程TenWizards巫师网络最短路Dijkstra算法在airbnb题库的巧妙应用TenWizards巫师网络最短路Dijkstra算法在airbnb题库的巧妙应用 Airbnb 面试题库airbnb中的 Ten Wizards十巫师上一篇Flutter-Notebook深度链接App Links与Universal Links配置下一篇2025企业AI成本革命T-pro-it-2.0-GGUF如何让本地化部署成本直降60%创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考