CRDT

2021-12-28

技术

文章目录

介绍

无冲突复制数据类型(CRDT: conflict-free replicated data type) 是一种简化分布式数据存储系统和多用户应用程序的数据结构。

在许多系统中，某些数据的副本需要存储在多台计算机上。此类系统的示例包括：

在本地设备上存储数据，并且需要将该数据同步到属于同一用户的其他设备（同一用户多端设备同步，例如日历、笔记、联系人或提醒）的移动应用程序；
分布式数据库，维护数据的多个副本（在同一数据中心或不同位置,一般是不同数据中心的多活场景），以便在某些副本离线时系统继续正常工作；
协作软件，例如 Google Docs、Trello、Figma 或许多其他软件，其中多个用户可以同时更改同一文件或数据；
边缘计算场景，比如多个手机/车载app 在无信号的森林中，产生的本地离线协同数据，多个设备同步到云上处理;
大规模数据存储和处理系统，复制数据以实现全球可扩展性。

所有此类系统都需要处理数据可能在不同副本上同时修改的事实。从广义上讲，有两种可能的方法来处理此类数据修改：

强一致性复制：

在这个模型中，副本相互协调以决定何时以及如何应用修改。这种方法支持强一致性模型，例如可序列化事务和可线性化。然而，等待这种协调会降低这些系统的性能；此外，CAP 定理告诉我们，当副本与系统的其余部分断开连接时（例如，由于网络分区，或者因为它是具有间歇性连接的移动设备），不可能对副本进行任何数据更改。
乐观复制：

在此模型中，用户可以独立于任何其他副本修改任何副本上的数据，即使该副本离线或与其他副本断开连接。这种方法可实现最大的性能和可用性，但当多个客户端或用户同时修改同一条数据时，它可能会导致冲突。当副本相互通信时，需要解决这些冲突。

无冲突复制数据类型 (CRDT) 用于具有乐观复制的系统，它们负责解决冲突。CRDT 确保，无论在不同的副本上进行什么数据修改，数据始终可以合并到一致的状态。此合并由 CRDT 自动执行，无需任何特殊的冲突解决代码或用户干预。

原理

实现

automerge

Yjs

redis (CRDB)

references

文章作者 weedge

上次更新 2021-12-28

许可协议 CC BY-NC-ND 4.0

显示 Disqus 评论