文档章节

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

XDocker
 XDocker
发布于 2015/03/19 10:39
字数 2833
阅读 51
收藏 0
点赞 0
评论 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

[mongodb文档]分布式一致性

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

nileader ⋅ 2014/06/05 ⋅ 0

分布式key/value存储系统--BeansDB

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

匿名 ⋅ 2009/12/30 ⋅ 1

【PDF分享】BeansDB 设计与实现 V2

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

红薯 ⋅ 2010/12/30 ⋅ 0

Serverless加CRDT掀起的新浪潮

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

dev_csdn ⋅ 2017/11/28 ⋅ 0

NoSQL–Theory–CAP和BASE

一个成功的网络服务依赖于数据是正确、一致并且是可用的。对于一个简单的应用而言,它采用数据服务器加应用服务器构成。应用服务器相当于访问代理,并且处理应用的逻辑部分;数据服务器依靠数...

开源中国驻成都办事处 ⋅ 2013/06/13 ⋅ 0

谈谈分布式事务

> 最近几天都在研究分布式事务, 当然, 研究是官方语言, 其实也都是在学习前人的经验, 本文姑且做个整理. ### 什么是事务? [百度百科][1]的解释一般是指要做的或所做的事情。在计算机术语中是...

采蘑菇的大叔 ⋅ 2017/09/30 ⋅ 0

微服务架构下的数据一致性保证(一)

大家好,今天我给大家分享的题目是微服务架构下的数据一致性保证。 今天分享第一篇,主要内容包括: 1.传统使用本地事务和分布式事务保证一致性。 2.传统分布式事务不是微服务中一致性的最佳...

真爱2015 ⋅ 2016/09/29 ⋅ 0

聊聊分布式事务

原文出处:员海滨 投稿 分布式事务场景如何设计系统架构及解决数据一致性问题,个人理解最终方案把握以下原则就可以了,那就是:大事务=小事务(原子事务)+异步(消息通知),解决分布式事务...

员海滨 投稿 ⋅ 2017/04/07 ⋅ 0

架构设计:系统存储(23)——数据一致性与Paxos算法(上)

今年年初参加一家公司的面试,发生了一件有趣的事情。当我给面试官解释Ceph的运行原理时,提到了Ceph支持POSIX标准(Portable Operating System Interface),面试官突然问道:“那简述以下P...

yinwenjie ⋅ 2017/03/13 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Sqoop

1.Sqoop: 《=》 SQL to Hadoop 背景 1)场景:数据在RDBMS中,我们如何使用Hive或者Hadoop来进行数据分析呢? 1) RDBMS ==> Hadoop(广义) 2) Hadoop ==> RDBMS 2)原来可以通过MapReduce I...

GordonNemo ⋅ 47分钟前 ⋅ 0

全量构建和增量构建的区别

1.全量构建每次更新时都需要更新整个数据集,增量构建只对需要更新的时间范围进行更新,所以计算量会较小。 2.全量构建查询时不需要合并不同Segment,增量构建查询时需要合并不同Segment的结...

无精疯 ⋅ 58分钟前 ⋅ 0

如何将S/4HANA系统存储的图片文件用Java程序保存到本地

我在S/4HANA的事务码MM02里为Material维护图片文件作为附件: 通过如下简单的ABAP代码即可将图片文件的二进制内容读取出来: REPORT zgos_api.DATA ls_appl_object TYPE gos_s_obj.DA...

JerryWang_SAP ⋅ 今天 ⋅ 0

云计算的选择悖论如何对待?

导读 人们都希望在工作和生活中有所选择。但心理学家的调查研究表明,在多种选项中进行选择并不一定会使人们更快乐,甚至不会产生更好的决策。心理学家Barry Schwartz称之为“选择悖论”。云...

问题终结者 ⋅ 今天 ⋅ 0

637. Average of Levels in Binary Tree - LeetCode

Question 637. Average of Levels in Binary Tree Solution 思路:定义一个map,层数作为key,value保存每层的元素个数和所有元素的和,遍历这个树,把map里面填值,遍历结束后,再遍历这个map,把每...

yysue ⋅ 今天 ⋅ 0

IDEA配置和使用

版本控制 svn IDEA版本控制工具不能使用 VCS-->Enable Version Control Integration File-->Settings-->Plugins 搜索Subversion,勾选SVN和Git插件 删除.idea文件夹重新生成项目 安装SVN客户......

bithup ⋅ 今天 ⋅ 0

PE格式第三讲扩展,VA,RVA,FA的概念

作者:IBinary 出处:http://www.cnblogs.com/iBinary/ 版权所有,欢迎保留原文链接进行转载:) 一丶VA概念 VA (virtual Address) 虚拟地址的意思 ,比如随便打开一个PE,找下它的虚拟地址 这边...

simpower ⋅ 今天 ⋅ 0

180623-SpringBoot之logback配置文件

SpringBoot配置logback 项目的日志配置属于比较常见的case了,之前接触和使用的都是Spring结合xml的方式,引入几个依赖,然后写个 logback.xml 配置文件即可,那么在SpringBoot中可以怎么做?...

小灰灰Blog ⋅ 今天 ⋅ 0

冒泡排序

原理:比较两个相邻的元素,将值大的元素交换至右端。 思路:依次比较相邻的两个数,将小数放在前面,大数放在后面。即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。然后比较第...

人觉非常君 ⋅ 今天 ⋅ 0

Vagrant setup

安装软件 brew cask install virtualboxbrew cask install vagrant 创建project mkdir -p mst/vmcd mst/vmvagrant init hashicorp/precise64vagrant up hashicorp/precise64是一个box......

遥借东风 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部