Skip to content

Last-Writer-Wins Register CRDT

Last-Writer-Wins Register · LWW-Register · LWW 寄存器

为每次写入附全序 marker,并通过选取确定最大 marker 在所有副本保留同一单值的寄存器 CRDT。

条目类型
模型

形式陈述

State-based LWW-Register 的状态为

X=(m,v),

其中 v 是值,marker m 取自带全序 M 的集合。写入 v 必须生成一个严格大于本副本当前已观察 marker、且对不同写事件全局唯一的新 marker m;merge 选择 marker 较大的状态:

XX={X,mMm,X,m<Mm.

若两次不同写入可能获得同一主时间值,marker 必须带稳定的确定 tie-break,例如

m=(logical time,replica ID,local sequence)

并按字典序比较。唯一性保证合法状态中 m=Mm 只会表示同一写事件,因而也有 X=X,等号分支正好处理状态重传。若实现仍可能让不同值获得完全相同的 marker,就必须把值的规范编码纳入最终全序;否则合并无法同时成为确定、交换的 join。

取最大值满足结合、交换和幂等,且写入提升 marker,所以该构造是状态型 CRDT。名称中的“last”只表示 marker 全序中的最大者;除非时钟模型另有证明,它不等于真实世界最后完成的写入。为使因果后继写确实覆盖前驱,生成器至少要令新 marker 大于本地已观察最大 marker;单纯读取可能回拨的墙钟不满足此条件。

直觉

两个副本并发覆盖同一格子时,LWW 不保留冲突,而是预先约定一把所有人都能独立使用的尺。只要尺是全序且比较稳定,副本无需协调便会挑中同一赢家。代价是另一写入的意图被确定丢弃。

物理时间戳看似自然,却把语义交给时钟同步。快钟副本的一次旧业务写入可能压过慢钟副本稍后发生的写入;NTP 回拨还会让同一副本的新写 marker 变小。Hybrid logical clock 或“至少大于本地已见最大值”的生成规则能保持因果推进,但仍不把 marker 变成可信全球实时。Marker 是冲突解决数据,必须随值一起原子持久化;只落盘 payload 会在恢复时失去赢家依据。

这与Multi-Value Register形成实质对比:LWW 以任意确定全序删除并发 loser,MV-Register 保留因果上无法比较的所有最大版本,让应用或后续写显式化解。

例子与边界

A、B 都从值 old、marker (4,Z,0) 开始。二者并发写入:

A: ((5,A,1),red),B: ((5,B,1),blue).

约定 replica ID 中 A<B,所以字典序有 (5,A,1)<M(5,B,1)。A 先收到自己的状态再收到 B,B 以相反顺序合并,二者都选择 blue;重复收到 red 也不会改变结果。这个例子中的“B 胜”来自 tie-break,不是因为 B 在物理时间更晚。

若 marker 只有整数 5,两个不同值都标 5,A 的 merge 实现“相等保留左值”、B 的实现同样保留左值,则 A 可能保留 red、B 保留 blue;操作看似确定,交换性却失败。稳定的 replica ID 不能由启动时随机且可碰撞的短字符串替代。

再设 A 的墙钟误快一天,写入 marker 1000 后离线;B 在真实一天后写 marker 900。合并仍选 A。CRDT 收敛完全正确,但“用户最后写入”语义错误。LWW 不能修复时钟偏斜,只能让偏斜后果在各副本一致。

推论与应用

LWW 适合可接受确定丢弃并发写的缓存、偏好项和派生值。审计或财务记录通常不能只保留赢家;应保存不可变事件、MV 版本或业务级合并结果。Conditional write 也不由 LWW 自动原子化:两个副本都看到 old 后各自“仅当 old 才写”,仍可能都成功并在合并时丢掉一个结果。本地读只返回当前赢家。

Marker 还必须跨崩溃持久化。副本重启后从较小逻辑时钟开始,它的新写会被旧 marker 永久盖住。成员 ID 重用同样可能造成 tie-break 冲突;安全 incarnation 应进入 marker 或由协调 epoch 管理。

参考资料
  • Marc Shapiro et al., “A Comprehensive Study of Convergent and Commutative Replicated Data Types,” INRIA RR-7506, 2011, Specifications 8–9.
  • Leslie Lamport, “Time, Clocks, and the Ordering of Events in a Distributed System,” Communications of the ACM 21(7), 1978, pp. 558–565.
  • Martin Kleppmann and Alastair R. Beresford, “A Conflict-Free Replicated JSON Datatype,” IEEE Transactions on Parallel and Distributed Systems 28(10), 2017, pp. 2733–2746.
关系图谱2 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:分类

分类位置

上位 / 更一般

下位 / 直接特例

暂未标注直接特例。

类型化关系