CRDT(Conflict-free Replicated Data Type,无冲突复制数据类型)是构建分布式协同应用的核心数据结构。近日,前 Recurse Center 工程师 Jake Lazaroff 撰写了 一篇交互式入门教程,以图灵机为比喻,帮助开发者直观理解 CRDT 的工作原理。
CRDT 是什么
CRDT 是一种可以在不同计算机(对等节点)上存储的数据结构。其核心特性是:每个节点可以即时更新本地状态,无需网络请求,最终保证所有节点收敛到一致状态。
用作者的话来说:"CRDT 的概念并不复杂,只是名字很长。"其关键在于 merge 函数必须满足三个数学性质:交换律、结合律、幂等性。这意味着无论合并顺序如何、重复合并多少次,最终状态都保持一致。
以图灵机理解 CRDT
Lazaroff 提出了一个独特的理解方式:将 CRDT 看作一台图灵机——它只有一个状态,但可以通过 merge 操作与另一台图灵机的"纸带"合并。
CRDT 的接口可以这样定义:value 是当前值,state 是内部状态,merge则将另一个状态合并到当前状态。
两种 CRDT:状态型与操作型
教程主要聚焦状态型 CRDT(LWW-Register 和 LWW-Map)。LWW(Last-Write-Wins)基于时间戳,后写入的数据胜出。LWW-Map 由多个 LWW Register 组成,支持添加、更新和删除。
值得注意的是删除的处理方式:不是真正移除键,而是将寄存器值设为 null。这种"墓碑"机制可以区分"该键已删除"和"该键从未存在"两种状态。
应用场景与局限
CRDT 被广泛应用于协作工具(如 Figma、Google Docs)、消息系统和分布式数据库。其关键限制是:CRDT 是单调递增的数据结构,只能添加信息不能删除,因此会产生存储开销。
参考来源:An Interactive Intro to CRDTs - Jake Lazaroff(https://jakelazaroff.com/words/an-interactive-intro-to-crdts/)