什么是分布式系统中的CRDT？

我是分布式系统的新手,我正在尝试深入了解CRDT的概念.我意识到它有三个符号:

Conflict-free Replicated Data Type
Convergent Replicated Data Type
Commutative Replicated Data Type

任何人都可以举例说明我们在分布式系统中使用CRDT吗？非常感谢提前.

CRDT的灵感来自Marc Shapiro的作品.在分布式计算中,无冲突复制数据类型(缩写为CRDT)是一种专门设计的数据结构,用于实现强烈的最终一致性(SEC)和单调性(没有回滚).确保SEC有两种替代途径:基于操作的CRDT和基于状态的CRDT.

不同副本上的CRD可以彼此分开,但最后它们可以安全地合并,提供最终一致的值.换句话说,CRDT具有幂等,可交换和关联的合并方法.

这两种选择是等效的,因为可以模仿另一种,但基于操作的CRDT需要来自通信中间件的额外保证.CRDT用于在网络中的多台计算机之间复制数据,无需远程同步即可执行更新.这将导致使用传统最终一致性技术的系统中的合并冲突,但CRDT的设计使得冲突在数学上是不可能的.在CAP定理的约束下,它们为可用/分区容忍(AP)设置提供了最强的一致性保证.

一些使用它们的例子

Riak是CRDT最受欢迎的开源库,被Bet365和League of Legends使用.以下是一些支持Riak的有用链接.

1- Bet365(使用Erlang和Riak) http://www.erlang-factory.com/static/upload/media/1434558446558020erlanguserconference2015bet365michaelowen.pdf

2- League of Legends使用Riak CRDT实现其游戏内聊天系统(每秒处理750万并发用户和11,000条消息)

由SoundCloud实现的3- Roshi支持LWW时间戳集:-Blog帖子:https://developers.soundcloud.com/blog/roshi-a-crdt-system-for-timestamped-events

CRDT使用Math在分布式集群中强制实现一致性,而不必担心共识和相关的延迟/不可用性.

CRDT可以随时采用的值集属于半格(具体为半连格)的类别,其是具有最小上限函数(LUB)的POSET(部分有序集).

简单来说,POSET是一个项目集合,其中并非所有项目都具有可比性.例如,在一对数组中:{(2,4), (4, 5), (2, 1), (6, 3)},(2,4)是< (4,5),但不能与之比较(6,3)(因为一个元素较大而另一个元素较小).现在,半格是POSET,其中给出2对,即使你不能比较两者,你也可以找到一个大于两者的元素(LUB).

另一个条件是,更新此数据类型需要在增加,CRDTs已经单调递增的状态,其中客户从来没有遵守国家回滚.

这篇优秀的文章使用我上面使用的数组作为例子.对于维护这些值的CRDT,如果2个副本试图在(4,5)和之间达成共识(6,3),则可以选择LUB = (6,5)作为共识并将两个副本分配给它.由于价值在增加,这是一个很好的价值.

CRDT有两种方式可以在副本之间保持同步,它们可以定期传输状态(会聚复制数据类型),或者它们可以在获取更新(增量)时传输更新(增量)(可交换复制数据类型).前者占用更多带宽.

SoundCloud的Roshi就是一个很好的例子(虽然它似乎不再在开发中),它们存储与时间戳相关的数据,时间戳显然在增加.以时间戳小于或等于存储的时间戳进入的任何更新都将被丢弃,这确保了幂等性(重复写入正常)和可交换性(无序写入是正确的.交换性a=b means b=a,在这种情况下意味着update1后跟update2是相同的作为update2后跟update1)

写入被发送到所有集群,并且如果某些节点由于诸如缓慢或分区之类的问题而未能响应,则它们预期稍后通过a赶上read-repair,这确保了值收敛.如上所述,可以通过2个协议实现收敛,传播状态或更新到其他副本.我相信Roshi是前者.作为read-repair复制品交换状态的一部分,并且因为数据遵循半格子属性,它们会聚.

PS.使用CRDT的系统最终是一致的,即它们在CAP定理中采用AP(高可用性和分区容忍性).

另一篇关于这个主题的精彩读物