CRDT

CRDT 是一种无冲突复制数据类型,它支持强最终一致性(SEC, Strong Eventual Consistency)。这种数据类型常用于需要多用户协作编辑的文档,或者那些要求快速响应但不需要很高实时性保证的场景,比如强调(AP, Availability and Partition Tolerance)的应用。

CRDT 适用于异步传播(gossip)场景。无论网络状态如何,总能保证数据的最终一致性。它具有以下特点:

  • 将请求以任意顺序合并
  • 同样的请求有幂等性
  • 即使请求延迟、乱序、重复,都没关系

其数据结构形成了一个半格(semi-lattice)。CRDT 通过维护一个偏序关系构成的有向图,在这张有向图中能保证最终所有的节点会收敛到一个最小公共祖先节点,即在 semi-lattice diagram 中找到 upper bound。

CRDT 节点,需要维护:

  • 本地对请求的排序
  • merge 函数,可以将其他节点的请求合并到自己身上
  • update 函数,可以更新自己的数据(需要合并的更新中最小公共祖先节点)

IPFS Cluster 所采用的 CRDT 是专为 Merkle DAG 设计的。在 IPFS Cluster 中,多个节点可以通过 CRDT 维护达成对集群 Merkle DAG 状态的共识,可以将 Merkle DAG node 看做是 Merkle-Clock,作为一个分布式系统的 event,一旦创建便无法改变。

updatedupdated2024-04-122024-04-12