文档章节

谈谈CRDT---应该采用什么样的数据结构来保证最终一致性

XDocker
 XDocker
发布于 2015/03/19 10:39
字数 2833
阅读 58
收藏 0

http://www.project-fifo.net 0.6.0的 release note 中有这样一条:全面采用CRDT作为底层数据结构。

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

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

CRDT是什么?

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

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

用稍微通俗一点的话说:研究分布式系统,尤其是研究最终一致性分布式系统的过程中,一个最基本的问题就是,应该采用什么样的数据结构来保证最终一致性?CRDT即是理论界目前对于这个问题的答案(一篇集大成的论文在 这里 )。

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

一致性的难题

先看一下分布式系统。分布式系统的好处,不用说了,这是人类目前唯一实际可行的构建超大规模系统的唯二办法之一(另一种就是超级计算机)。如果考虑上经济可行这个因素,那么分布式系统就是唯一可行之法。

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

简单的讲,构建一个分布式系统跑得飞快完全不难,只有构建一个运作起来正确性与单机程序完全无二的分布式系统,这才困难。

现实上,就算这个理想中的目标也不是很容易既可以达成的。这就要说到 CAP定理 。CAP定理告诉我们,在构建分布式系统的时候,Consistency(一致性),Availability(可用性),Partition tolerance(分区容错性),这三者只可以同时选择两样。

CAP Theory

即,就算给我们再多的钱,在目前的计算机体系结构下,三样同时选择,理论上无可能的。如果谁做到了?就是不科学。

可惜的是,分区容错性是实际运行的分布式系统所必需的。设想下,谁能保证系统的各节点永远保持网络联通?(这是不给GFW面子)。

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

选择一致性,构建的就是强一致性系统。选择可用性,构建的就是最终一致性系统。前者的特点是数据落地即是一致的,但是可用性可能会有下降,实际中就是,有时系统在忙着保证一致性,无法对外界服务。后者的特点是时时刻刻都保证可用性,用户随时都可以访问,但是各个节点之间会存在不一致的时刻。

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

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

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

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

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

举个例子,我们设想一个最终一致的分布式系统,处理一个账户的支出收入问题。假设这个账户是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的理论,则涵盖了它们应该具有怎样的基本表现形式,满足一些什么样的基本条件才可以保持最终一致性(毕竟大家不想每次都穷举所有的情况),以及在不断的寻找一些通用的,有大量应用场景的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给了我们从逻辑上既可以判断分布式系统能否保证最终一致性的能力。因此,在下一次选择系统的时候,我们就可以更加的理智,更加的清醒。

本文转载自:http://liyu1981.github.io/what-is-CRDT/

共有 人打赏支持
XDocker
粉丝 0
博文 8
码字总数 1285
作品 0
昌平
架构师
分布式系统的弱一致性模型协议和Dynamo DB的设计思想

对于容许数据副本不一致的协议, 我们很难用一个单一的维度来定义或者归类这些协议,对于这些协议来说,更关键的问题在于他们提供的一致性保证,抽象和API是不是对用户有用,尽管这些协议允许...

三川_8f54
2017/11/21
0
0
[mongodb文档]分布式一致性

[mongodb文档]分布式一致性(一)[1] 一致性模型对于一个分布式数据库来说是至关重要的。这里我们将专门一个专题的形式来讲解一些主题:例如:针对一些具体的应用场景应该使用什么样的模型。...

nileader
2014/06/05
0
0
Serverless加CRDT掀起的新浪潮

原文:Birth Of The NearCloud: Serverless + CRDTs @ Edge Is The New Next Thing 翻译:Vincent 译者注:无服务器是这几年新提出的一种概念,作者在本文介绍了一下无服务器架构是如何在C...

dev_csdn
2017/11/28
0
0
分布式key/value存储系统--BeansDB

BeansDB 是一个主要针对大数据量、高可用性的分布式KeyValue存储系统,采用HashTree和简化的版本号来快速同步保证最终一致性(弱),一个简化版的 Dynamo。 它采用类似memcached的去中心化结...

匿名
2009/12/30
9.6K
1
【PDF分享】BeansDB 设计与实现 V2

BeansDB 是一个主要针对大数据量、高可用性的分布式KeyValue存储系统,采用HashTree和简化的版本号来快速同步保证最终一致性(弱),一个简化版的 Dynamo。 它采用类似memcached的去中心化结...

红薯
2010/12/30
825
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

git +STS使用问题解决一

1. 2.点以一个pull就是更新代码 3.synchronize workSpace 同步代码,同SVN一致

森火
8分钟前
0
0
powerBi odbc 连接impala 实现自助分析

配置Impala以使用ODBC 可以将第三方产品设计为使用ODBC与Impala集成。为获得最佳体验,请确保支持您打算使用的任何第三方产品。验证支持包括检查Impala,ODBC,操作系统和第三方产品的版本是...

hblt-j
13分钟前
0
0
Purism FAQ

<font size="37" color="#006248" face="幼圆"> <p align="center"> Purism FAQ </p> </font> 原文:https://puri.sm/faq/ 原作者:Purism Team 翻译者:冰焰火灵X 1079092922@qq.com 文章许......

ICE冰焰火灵X
29分钟前
0
0
nginx+webdav

1、配置Nginx以支持WebDav: Webdav是nginx一个组件,默认编译nginx时是没有安装这个组件的。 如果跟应用公用一个nginx,需要重新编译安装nginx,重新安装前需要备份好原来的nginx.conf。 1....

yaukie
34分钟前
0
0
spring 事件

ContextRefreshedEvent Event raised when an {@code ApplicationContext} gets initialized or refreshed. ContextClosedEvent Event raised when an {@code ApplicationContext} gets clos......

Canaan_
46分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部