An introduction to state-based CRDTs

原文链接: https://www.bartoszsypytkowski.com/the-state-of-a-state-based-crdts/
作者: Bartosz Sypytkowski

（翻译）基于状态的CRDT简介

这是一个在以往的一些分享中已经谈论过的主题，但却从未写过。 这里我想写一点关于CRDT（冲突无关复制数据类型）的内容： 它要解决什么样的问题，并通过一些基本的代码实现（F#）来帮助你理解怎样去使用CRDT。

动机

CRDT是解决一个常见的分布式环境下数据同步问题的答案。 尽管人们熟知分布式领域中的此类问题，在过去已经进行了许多尝试来解决， 通常是去中心化的两阶段提交事物的变种。 但他们无一例外有以下的问题：

• 我们的一个假设是，所有的参与者总是在事务发生期间是可用的，而经常这个假设恰恰是不成立的（比如在边缘计算和移动应用的场景中）
• 多阶段提交和使用议会制的方案需要在参与者之间进行多次往返通信。这附带带来延迟和吞吐量的开销。而且，当机器增多或者通信距离增加时，这种方式有降低可扩展性的趋势。多数场景中，一旦跨越单个数据中心机房，使用分布式事务都是行不通的
• 这些方案通常确定一个单一的主节点来进行排他写操作，或者作为单一的数据源。在某些情况下，比如上面提到的场景中，都是不可接受的。

这并非是说先有的解决方案不好。 我们期望在一个更广阔的可能的解决方案的范围中， 找到解决特定条件下的问题的更佳方式。 这其中我期望呈现的一个问题是：

试想你需要建造一个全球范围的视频流服务。 每当用户上传一个视频文件的时候， 都需要复制到位于其他大陆的数据中心中，以便维持良好的延迟和吞吐量， 从而得到更好的用户体验。 不仅如此， 我们还希望把视频的播放次数展示给用户。

视频上传是一个主-从复制的很好的例子。 但是仅仅当添加一个播放数量的小小功能时，事情却变得复杂起来。 在整个地球许多并发用户、又是写操作多的特点下，使用诸如计数器的方式恐怕不是一个好主意， 因为对于热点视频可能会导致阻塞。 这个问题的本质允许我们降低强一致性来换取更高的可用性，因此并不需要事务。 但是如先前所述， 先有方案大多数在复制资源的写操作上又是采取排他的方式实现的。 正因如此，CRDT和多主场景有了发挥的空间。

使用场景和实现

除开这些简单的例子外，有许多我们在现在的工业应用中遇到的例子：

• 亚马逊使用CRDT来保持购物车的同步。他们也发布了名为Dynamo的数据库来允许他们的受众来使用CRDT
• Riak是这个领域最著名的解决方案。他们一个最知名的客户是Riot游戏公司（英雄联盟背后的公司），使用Riak来实现游戏中的聊天
• Rovio（愤怒的小鸟背后的公司）在他们的广告平台中使用冲突无关的计数器来确保展示量在离线的场景下也能正确工作
• SoundClound有他们自己的使用Go和Redis的最后写成功集合（Last-Write-Wins Set）实现，叫做

Roshi，他们用它来做观察者管理

• TomTom使用CRDT来管理导航数据
• CREAustralia使用CRDT来做点击流分析

除此之外，还有一些其他的解决方案：

• AntdoteDB是另一个具有创意的最终一致性数据库。它有一些独特的功能，其中之一是其事务支持最终一致性环境
• Akka.DistributedData是一个Akka（以及Akka.NET)编程模型的插件，在Akka集群上暴露了多个CRDT类型
• Redislabs提供了CRDB作为他们企业化Redis解决方案的一部分
• Cassandra 和 ScyllaDB支持最终一致性的计数器

冲突无关意味着什么

冲突无关是一个比较模糊的描述，但它表达了一个简单的态度： 我们是操作在一个无需拍他写入，可以检测并发更新并执行确定的、自动的冲突解决的数据结构之上。 这并不意味着冲突永远不会发生， 而是我们总是能根据这个数据结构维护的元数据本身来得到一个确定的输出。 这里的核心数据结构包括计数器、寄存器和集合， 从他们我们又可以组合出更多复杂的类型，例如字典（map）、图甚至JSON。

CRDT的类型

我们可以将CRDT分为两大类：基于状态的（convergent——聚合型）和基于操作的（commutative——交换型）。 不论谈到哪种类型， 均包含两个重要的部分：数据复制协议和状态转换算法。

在实践上，两种类型在实现上存在巨大差异， 他们的重心也关注在不同的地方。 由于我们需要一些额外的元数据来产生自动化的冲突解决方法， 基于状态的CRDT将其作为数据结构的一部分， 而基于操作的CRDT倾向于将其更多放到复制协议本身。 这里，我们将介绍其中一种简单的基于状态的方案。

聚合复制数据类型

基于状态的CRDT中，最最重要的操作是Merge（合并）方法。 它所做的仅仅是拿到相关逻辑实体的两个副本， 将更新后的状态作为输出。 如果发生了任何冲突， 需要由merge操作来解决。

除此之外，merge操作必须满足下面三个条件，才能使我们使用时得心应手：

• 交换律[math]\displaystyle{ x \cdot y = y \cdot x }[/math]和结合律[math]\displaystyle{ (x \cdot y) \cdotz = x \cdot (y \cdot z) }[/math]