谈谈CRDT

2014-09-08

Project FiFo 0.6.0的release note中有这样一条：全面采用CRDT作为底层数据结构。

为什么要采用CRDT，有啥好处? 其实是不太容易理解的。

在这里，我就试图用听的懂的语言来解释一下CRDT是什么，以及为什么采用它是一个巨大的进步。

CRDT是什么？

CRDT是Conflict-Free Replicated Data Types的缩写，直译的话即“无冲突可复制数据类型”。

翻译过来这还是不是人话啊！所以接下来还是保留其英文缩写称呼之。

先随便解释两句。

研究分布式系统，尤其是研究最终一致性分布式系统的过程中，一个最基本的问题就是，应该采用什么样的数据结构来保证最终一致性？ 这是一个关键的，难度超过一般人想象的问题。

CRDT即是理论界目前对于这个问题的答案（一篇集大成的论文在这里）。

当然理论界的思路现在不是所有人能跟上的，需要更加简单的解释。

一致性的难题

先回顾一下分布式系统。分布式系统即运行在多物理计算机上的系统。它的好处，不用说了，这是人类目前实际可行的构建超大规模系统的唯二办法之一（另一种就是构建超级计算机）。如果考虑上经济可行这个因素，那么分布式系统就是唯一可行之法。

构建分布式系统，抛开效率问题不谈，首先是如何保持其正确性？

简单的讲，构建一个分布式系统跑得飞快完全不难（例如写个存什么但是不保证取出来的系统:-)），只有构建一个运作起来正确性与单机程序完全无二的分布式系统，这才困难。

现实上，就算这个理想中的目标也不是很容易既可以达成的。这就要说到CAP定理。

CAP Theory

CAP定理告诉我们，在构建分布式系统的时候，Consistency（一致性），Availability（可用性），Partition tolerance（分区容错性），这三者只可以同时选择两样。

即，就算给我们再多的资源（比如人力，智力，机器，钱这些壕的东西），在目前的计算机体系结构下，三样同时选择，理论上无可能的。如果谁做到了？就是不科学。

不幸的是，分区容错性是实际运营的分布式系统所必需的。设想下，谁能保证系统的各节点永远保持网络联通？ 这是不给GFW面子。

所以接下来我们需要在一致性和可用性中二选其一。

选择一致性，构建的就是强一致性系统，比如符合ACID特性的数据库系统。选择可用性，构建的就是最终一致性系统。前者的特点是数据落地即是一致的，但是可用性不能时时保证，这意思就是，有时系统在忙着保证一致性，无法对外界服务。后者的特点是时时刻刻都保证可用性，用户随时都可以访问，但是各个节点之间会存在不一致的时刻。

需要注意的是最终一致性的系统不是不保证一致性，而是不在保证可用性和分区容错性的同时保证一致性。

最终我们还是要在最终一致性的各节点之间处理数据，使他们达到一致。

需要保存怎样的信息才可能达到最终一致？

因为最终一致性系统保证可用性与分区容错性，所以在构建去中心，无单点故障，总是可用的系统时，会是更自然的选择。

那么我们就一定需要在某个时刻处理这个一致性问题。

举个例子，我们设想一个最终一致的分布式系统，处理一个账户的支出收入问题。假设这个账户是T，初始化有100块钱，用户可以通过系统里面好几个节点，例如A, B, C，访问它。那么我们的最终一致的分布式系统，可以保证A B C三者在时时刻刻都可以对T进行操作。

假设某个时刻t1，A往T中存了10块钱，B则向T中取了10块钱，C则在接下来的一个时刻查询T有多少钱，他们是同时发生的。

显然，分布式系统会保证这三个操作都能完成，于是

  1. 在A系统看来，T有110块钱;
  2. 在B系统看来，T有90块钱;
  3. 在C系统看来，T有100块钱。

在这个时刻t1，这三者都是对的，即最终一致性系统中，存在不一致的时刻。那么经过一段时间之后，假设是t2吧，我们需要使得A B和C系统看来，T都有100块钱，即保证最终一致。

这中间肯定需要做一些操作，例如A B和C系统之间交换一些必要的信息数据。

问题是：这些需要被交换的数据至少需要是怎样的？

如果在各节点我们只是存了T的余额，例如用一个整数变量，这样显然是不行的：当A系统和B系统的数据传输到C系统时，C无法分辨A或者B系统的结果到底谁对。

简单的答案就是我们至少需要多存储一点信息。

在这个例子里面，我们或许可以这样设计：每个系统存储的不是一个最终数值，而是一系列包含了时刻与余额的记录。假设我们的系统是从t0时刻开始的，那么在我们的例子里面，t1时刻

  1. A系统存储的是： (t0, 100),(t1, 110)
  2. B系统存储的是： (t0, 100),(t1, 90)
  3. C系统存储的是： (t0, 100),(t1, 100)

这样的结构使得我们在传输了足够的信息之后，都能达成一致性。例如对于C系统，当然收到足够多的信息，即是除自己之外所有的节点信息（A和B）后，如下得出正确一致的数据

  1. A系统在t0至t1之间产生的变化是 +10
  2. B系统在t0至t1之间产生的变化是 -10
  3. C系统在t0至t1之间产生的变化是 +0
  4. A和B系统与C在t0时数据一致，在t1之后未至t2之前一致的数据应为 100 +10 -10 +0 = 100

类似的，在A和B上也可以这样的判断。

再谈CRDT

上面的例子足够简单，答案也足够的粗糙。想在实际系统中应用，我们必须要考虑更多的数据类型和应用场景。于是设计一个能够保持最终一致性的数据结构，就会变成一件很难的事情。甚至于这件事情本身会喧宾夺主，成为一个最终一致性系统中的最麻烦的问题。

有了这样的概念，现在我们可以回头看CRDT。

CRDT就是这样一些适应于不同场景的可以保持最终一致性的数据结构的统称。围绕着CRDT的理论，则涵盖了

  1. 它们应该具有怎样的基本表现形式，
  2. 满足一些什么样的基本条件才可以保持最终一致性（毕竟大家不想每次都穷举所有的情况），
  3. 以及在不断的寻找一些通用的，有大量应用场景的CRDT，并努力提高它们的空间和时间效率。

之前提到的那篇论文很好的总结了目前为止人们在CRDT这件事情上的认识程度。简要的总结，它

  1. 定义了CRDT
  2. 列举了CRDT的两种基本形式，即基于状态的CRDT与基于操作的CRDT。前者存储的是一个个的最终值，类似我们的例子，后者存储的是一个个的操作记录，类似于我们例子里面的推导过程
  3. 界定了CRDT能满足最终一致性的边界条件。简单说，设计一个CRDT，只需要验证它是否满足这些边界条件，即可知道它是否能保持最终一致
  4. 界定了两类CRDT在系统中应用时，需要的信息交换的边界条件。即回答怎样叫做“收集到足够多的信息”
  5. 枚举了当前人类所知的CRDT，包含了计数器(counter)，寄存器(register)，集合(set)和图(graph)等几类
  6. 在现实中应该如何应用CRDT，尤其是对于存储空间怎样进行回收的问题

简要的就是，这篇文章是一本字典，它包含了CRDT方面人类的知识结晶。

怎样在实际系统中应用

说了这么多，CRDT其实还是停留在纸上，或许对于系统构建者来说，更加关心怎么在自己的最终一致性系统中使用？以什么样的方式？

这样的问题或许太大，但是我们可以看看如何在RiakCore这样的最终一致性分布式框架中使用

  1. 抛弃自己所写的数据结构，实现CRDT，或者使用已经实现好的CRDT library
  2. 参照CRDT的一致性可判断条件（即"收集到足够多的信息"），在需要判断最终一致性时收集它们
  3. 抛弃自己所写的一致性判断算法，实现CRDT的一致性合并算法，或者使用已经实现好的存在于CRDT library中的方法

就是这样简单。

其实整个过程，与使用类似map/stack这样的数据结构并不不同的地方。

谁应该使用？谁在使用？

所有力求最终一致性的分布式系统，都应该使用CRDT。

如果一个最终一致的分布式系统至今还没有使用，那么要么是其所使用的数据结构已经实现了（很可能是粗糙的）CRDT的一种或者几种，要么是这个系统在最终一致性上的保证就存在问题。

至于谁在使用呢？应该说大部分的最终一致性系统都在自觉不自觉的向之迈进。Fifo已经全面的采用了; RiakKV也已经采用了，做为1.4版本的重要特性; 随着Riak_dt的开源，越来越多Erlang/OTP的程序也有希望尽快使用上CRDT。

最后的总结

CRDT带来了什么？从用户的层面，好象是什么也没有带来。但是从系统管理员/开发者的角度来看，CRDT给了我们从逻辑上既可以判断分布式系统能否保证最终一致性的能力。因此，在下一次选择系统的时候，我们就可以更加的理智，更加的清醒。