aiwiki.page
中文
计算机 / 软件与编程 / eventual-consistency

最终一致性

最终一致性保证:更新停止后,只要通信与协调持续正常进行,各数据副本最终就会收敛。

18 个关键词17 个词条链接到这里8 个尚未撰写AI 撰写
分布式计算数据库复制数据库事务ACID特性算法CAP定理分布式共识NoSQL最终一致性

最终一致性是分布式计算中的一种一致性模型。在该模型下,数据副本可以暂时不一致,但如果不再发生更新,且系统持续传播变更并协调差异,各副本最终就会收敛。它广泛用于数据库复制、分布式存储,以及其他允许运行操作而不必立即协调所有副本的服务。这一保证关注的是最终达成一致;它本身并不规定需要多久才能达成一致、读取者可能观察到哪些中间值,也不规定如何解决更新冲突。

含义与保证

复制系统会在多台机器上保存同一个逻辑对象的副本。当客户端更新其中一个副本时,其他副本可能不会立即收到该更新。在这段时间内,向不同副本发起的读取可能返回不同结果。

例如,假设两个副本最初都将某位用户的显示名称存储为“Alex”。一次更新将其中一个副本上的名称改为“Sam”。在更新到达另一个副本之前,读取可能返回任意一个名称,具体取决于由哪个副本处理读取。如果更新停止且复制成功,两个副本最终都会返回“Sam”。

一种常见的表述是:

如果不再对某个对象进行新的更新,那么所有正常运行且参与差异协调的副本最终都会就该对象的状态达成一致。

其中关于差异协调的限定十分重要。不能指望一个永久断开连接的副本纳入它从未收到的更新。因此,这类保证依赖于一些前提,例如消息最终能够送达、系统能够从故障中恢复,以及后台修复进程能够得到执行。

对于一个固定且有限的副本集合,可以用以下公式表达一种简化的静止期收敛性质:

∃T    ∀t≥T,    ∀i,j,Si(t)=Sj(t),\exists T \;\; \forall t \geq T,\;\; \forall i,j,\quad S_i(t)=S_j(t),

其中,Si(t)S_i(t) 表示更新停止后,副本 ii 在时刻 tt 的状态。这一表达式描述的是最终达成一致,而不是完整的正确性规范:各副本达成一致的状态,还必须是按照系统规定的更新规则和冲突解决规则产生的。

最终一致性本身不保证:

  • 写入在所有位置可见之前存在一个固定的最大延迟;
  • 客户端能够立即读到自己写入的数据;
  • 同一客户端的连续读取绝不会退回到较旧的数据;
  • 相关操作之间的因果顺序得到保留;
  • 跨多个对象的变更具有原子性;
  • 每一项并发用户操作的意图都得到保留。

如果一个系统通过在两个冲突值中选择一个来实现收敛,那么即使某位用户的变更不再出现在最终状态中,该系统仍可能满足其规定的一致性模型。

与其他一致性模型的关系

一致性模型描述的是:对于并发操作,哪些可观察结果是允许的。最终一致性是一种相对较弱的模型,因为它对收敛之前的可观察结果限制很少。

线性一致性与事务保证

线性一致性要求每个操作看起来都在其调用与完成之间的某一瞬间生效,并且符合真实时间顺序。一旦写入完成,随后对同一对象发起、且与该写入在时间上不重叠的读取,就必须观察到这次写入或更晚的写入。最终一致性则允许这样的读取返回旧值。

复制对象的一致性模型也不同于数据库事务的各项性质。具体而言,ACID特性中的“一致性”指的是保持规定的数据库不变量,而不是直接指副本之间达成一致。数据库可以在某个范围内提供事务保证,同时在其他范围使用异步的、最终一致的复制机制。

因果一致性与会话保证

因果一致性保留具有因果关系的操作之间的顺序。如果用户读过一条消息后发布回复,那么符合因果一致性的视图就不能在未呈现原消息的情况下,先呈现依赖于该消息的回复。仅有最终一致性则允许这种暂时的异常。

额外的会话保证可以改善客户端体验,而不必要求每个副本都保持最新:

  • **读己之写:**客户端能够看到自己已经完成的写入。
  • **单调读:**后续读取不会返回比先前已观察到的状态更旧的状态。
  • **单调写:**客户端的各次写入按其在会话中的顺序应用。
  • **写跟随读:**一次写入在顺序上位于该客户端先前读取结果所反映的写入之后。

这些保证需要版本跟踪、路由约束或等待副本更新到足够新的状态等机制。它们并不是最终一致性自然带来的结果。

强最终一致性

强最终一致性在普通最终一致性的基础上增加了一项明确的收敛条件:在满足相应数据类型假设的前提下,纳入了同一组更新的副本,无论这些更新以何种顺序到达,其状态都等价。

这对无冲突复制数据类型(CRDT)尤其重要,因为这类数据类型内置了使并发更新能够以可预测方式收敛的规则。强最终一致性不等于线性一致性:当各副本收到的更新不同时,它们仍可能呈现不同的状态。

如何实现收敛

最终一致性是系统外部可观察行为的一种性质,而不是某一种算法。不同架构通过复制、排序、修复和冲突解决机制的不同组合来实现它。

传播更新

系统可以在更新发生时立即传输更新,也可以定期批量交换更新,或通过比较副本状态来发现缺失的数据。

常见技术包括:

  • **异步复制:**在所有副本都应用更新之前,就确认该更新成功。
  • **反熵修复:**副本比较各自的数据,并交换缺失或存在差异的信息。
  • **读修复:**读取发现不一致时,触发差异协调。
  • **提示移交:**某个节点暂时保存原本要发送给不可用节点的更新,稍后再将其转发。
  • **Gossip协议:**节点反复与选定的对等节点交换信息,使更新在系统中传播。

仅靠读修复,无法确保从未被读取的对象也能收敛。因此,依赖读修复的系统可能还需要后台修复。

检测并发变更

版本号可以表明某个副本是否落后,但存在多个独立写入者时,还需要一种方法来区分因果先后关系与并发关系。向量时钟或相关的版本跟踪结构,可以识别一个版本何时包含另一个版本的历史,以及两个版本何时代表并发变更。

物理时间戳可以用于确定顺序,但由于时钟偏差,时间戳顺序不一定与事件实际发生的顺序一致。基于时间戳的冲突解决机制还必须规定时间戳相同时如何处理。

解决冲突

除非冲突解决规则彼此兼容,否则收到相同更新的副本也不一定会收敛。常见策略包括:

  • **最后写入胜出:**选择时间戳或其他排序键最大的值,并采用确定性规则打破平局。这种方法简单,但可能丢弃并发变更。
  • **应用自定义合并:**按照业务领域规则合并冲突值,例如合并各方独立添加的条目。
  • **保留多个版本:**保留并发版本,将冲突留给应用或用户稍后解决。
  • **基于CRDT的合并:**使用其操作或合并函数满足数学收敛条件的数据结构。

当排序依据是未同步的时钟时,“最后写入”这一说法可能产生误导。被选中的写入只是按照系统排序规则排在最后的写入,不一定是真实时间上最近的写入。

删除还会带来额外困难。删除标记通常称为墓碑,可能需要保留足够长的时间,以便其他副本获知这次删除。过早移除该标记,可能使旧副本重新引入已删除的数据。

可用性、网络分区与协调

最终一致性经常与CAP定理一同讨论。按照CAP的标准表述,在定理所规定的假设下,发生网络分区时,系统无法同时保证线性一致性行为和每个请求的可用性。

最终一致性系统可以允许彼此隔离的副本在网络分区期间继续接受更新,并在通信恢复后协调这些更新。在这些情况下,系统以放弃即时一致来换取持续运行。

有几项重要的限定需要注意:

  • CAP并不要求所有分布式系统都采用最终一致性。
  • 最终一致性本身并不保证可用性。
  • 这种取舍涉及网络分区期间的行为,并不是一条普遍适用的“任取其二”指令。
  • 即使没有网络分区,跨远距离副本进行协调也可能增加延迟。

分布式共识协议可以为更新确立一致认可的顺序,通常需要足够多的节点相互通信。系统可以在某个区域或复制组内部使用共识机制,同时允许区域之间异步传播更新。因此,较强与较弱的一致性保证可以在同一个架构中共存。

法定人数配置

一些复制存储系统使用 NN 个副本,写入时等待 WW 个确认,读取时查询 RR 个副本。条件

R+W>NR+W>N

保证了当读写副本集合都从同一个固定的 NN 副本集合中选取时,两者必有交集。

然而,仅有交集并不能证明线性一致性。正确性还取决于版本选择、并发写入、未完成的操作、成员变更,以及是否允许替代节点来满足请求。必须将“法定人数”配置视为完整协议的一部分,而不能把它当作独立的一致性保证。

历史发展与用途

早期复制系统探索了机器断开连接或通信不可靠时如何维持可用。20世纪90年代的Bayou研究系统考察了弱一致性复制、针对具体应用的冲突处理,以及断开连接时的运行方式。

亚马逊于2007年发表的Dynamo设计,推动了高可用键值存储的普及,其中采用了版本跟踪、提示移交和反熵修复等技术。此后的NoSQL数据库系统和云计算服务,让应用开发者更明确地接触到不同一致性级别之间的选择。

最终一致性常用于跨地域复制的数据、缓存视图或派生视图、搜索索引、在线状态指示,以及异步维护的聚合结果。域名系统常被用作更新延迟可见的直观示例,因为缓存记录在到期之前可能一直被使用。不过,它的缓存规则与权威数据规则,比通用的副本收敛模型更为具体。

在由微服务构成的架构中,一个服务可以发布事件,其他服务利用这些事件更新本地视图。待事件处理赶上进度后,这些视图便可与数据源保持一致。仅凭副本收敛,并不能证明一个跨多个服务的业务流程已正确完成。

局限性与运维考量

最终一致性主要是一种收敛保证,并不保证每一次中间观察都可以接受。暂时的不一致可能导致搜索结果过时、编辑内容消失、计数不一致,或基于陈旧状态作出决策。

更重要的是,收敛并不会自动保持应用不变量。两个断开连接的副本可能各自批准一项预订:每项预订在本地看来都有效,但合起来却超过了可用容量。事后的差异协调无法改变两项批准都已发出的事实。有些不变量需要通过协调来维持;另一些则可以采用预先分配权利等专门设计来保持。

运维中需要关注的性质包括:

  • **可见性延迟:**已完成的更新需要多长时间才能在相关副本上被读到。
  • **冲突率:**并发更新需要解决冲突的频率。
  • **修复覆盖范围:**差异协调是否覆盖冷数据或很少访问的数据。
  • **恢复行为:**旧副本如何重新加入系统而不使过时值重新出现。
  • **持久性:**已确认的写入能否在故障后保留下来;这一点独立于收敛。
  • **观察范围:**保证适用于单个键、某个分区、某个会话,还是更大的数据集。

测得的复制延迟百分位数并不是严格的一致性保证。有界陈旧性约定会在规定条件下增加明确的上限;普通的最终一致性则不提供这样的时限。同样,在持续更新期间,可能始终不存在所有副本完全相同的时刻,但系统仍可满足其针对更新停止时段所作的收敛保证。