Dynamo和Cassandra海量存储基础

标签: 分布式存储 架构设计 算法数据结构 Cassandra Dynamo | 发表时间:2014-05-24 14:37 | 作者:童燕群
出处:http://shentar.me

提到这两个系统,他们在核心思路上是非常类似的,但有一些细节性的东西又有所偏重,在分布式系统中也算是独树一帜了,很有代表性的一个系列,这些不一致的地方,最明显的地方就在于一致性上。可见,哪怕是从追求简单为上的工程化实现来说,各种不同的方式实现一致性也都有很大的不同,不过他们也有一些共性和一些独树一帜的概念,下面来做一下分别解说。

先说共性:

W+R>N

相信这个大家都耳熟能详了吧?呵呵,我从其他角度来说明这件事吧。

N表示这个复制集群的总数【很多地方解释的不是很准确造成了不少误解】。
W表示写入份数
R表示一次一致性读所需要的份数(这里要注意,是随机从N中选择的机器数量哦)

这个公式表示为:

如果满足W+R>N(W,R,N 属于不为负数的整数且R,W<N),那么集群的读写是强一致的。如果不满足,那么这个复制集群的读写是非强一致的。这里我强调一下,这里的“集群”,是指数据完全相同的多份拷贝。不涉及数据切分哦:)

这个公式的最常用的用法是求R,也就是说公式应该写成N-W<R(W,R,N 属于不为负数的整数且R,W<N)。我们举几个常见的例子:

1。 简单的主备强一致复制。
因为是强一致,所以数据一定是写够两份的,W=2。
这个集群的节点数呢?只有两台,所以N=2。
那么R>(N-W = 2 – 2 = 0)。
R> 0 所以R可以取 1, 2。 不能取三,因为机器数只有2。。取不来3 :)。

2。 假定有三台机器,使用quorum的方式强一致的写入数据。
因为有三台机器,所以N=3。
因为是进行quorum写入,只要写两台就算成功了,所以W=2
这时候R>(N-W=3-2=1)
所以R的取值只可能是2,3
R的取值意味着什么?意味着你必须从N=3台机器中,最少随机选择两台进行读取,才有可能读取到数据的最新值。

3。 假定有三台机器,写一台就算成功。
因为有三台机器,所以N=3。
因为是进行quorum写入,只要写一台就算成功,所以W=1。
这时候R>(N-W=3-1=2)
R的取值只可能是3。
这意味着什么?意味着如果你只写一台机器就算做成功,那么你在读取的时候需要读取3台机器,才能取得数据的最新值。
具体证明我就不列了,感兴趣自己去看一下:) 。 枚举一下很容易可以得出结论的。

gossip协议

gossip协议是这两套存储的基础之一,说复杂也复杂,说不复杂也不复杂。。其实gossip就是p2p协议。他主要要做的事情是,去中心化。
怎么做到的呢?我只希望在这篇文章里给大家留下几个印象:gossip是干什么的?怎么做到的?优势劣势是什么?即可。对协议的细节感兴趣的,可以自己去深入研究。

gossip的核心目标就是去中心。做到的方式:

根据种子文件,按照某种规则连接到一些机器,与他们建立联系,不追求全局一致性,只是将对方机器中自己没有的数据同步过来。这里就设计到如何能够快速的知道自己的数据和其他人的数据在哪些部分不一致呢?这时候就要用到Merkle tree了,它能够快速感知自己所持有的数据中哪里发生了变更。

优势:

去中心化,看看伟大的tor,只要能连到一个seed,有一个口子能出长城,那么你最终就能跳出长城。。

劣势:

一致性比较难以维持, (这里我们介绍很简单,因为我也没有实际的写过。。。如果谁有这方面经验欢迎补充)

不同选择:

Dynamo : vector clock vs. Cassandratimestamp。
这两个协议的目标都是解决一致性的。也是我们要说的重点。
我们先来说说Vector clock:

提到vector clock ,不能不提Lamport的另一篇论文Time Clocks and the Ordering of Events in a Distributed System(中文翻译 http://t.cn/zlEwziN

这篇文章核心讲的是多进程之间的互斥和排队问题。不过这不是我们主要的要吸收的,在这篇文章中,更多的能够让你意识到一个问题:原来你跑到了一个相对论的世界里。也即,在进程之间没有消息相互通知的时候,他们就是各自为政的,遵循着自己的时钟的。只有在当他们之间有了相互之间的消息传递的时候,才有可能创造一个全局时间序出来。

vector clock 给我的感觉,就正是沿着这条路子思考下去得出来的一种方式。如果要我一定有一个现实生活的类比的话,我想说,vector clock给我的感觉更像git 。
让我们从他与paxos的比较上面开始吧。
在paxos里面,我们使用quorum和类三阶段提交的方式来保证数据提议是顺序的,一次只会有一个提议被接受。
这样在一个场景下效率不是最高的:如果我们假定,大部分场景更新的数据都不重复,那么效率就不会高了。

比如,如果我们不断地往一个kv里面进行以下操作:
{查看A够不够100块?如果够,减少100块}
{查看A够不够100块?如果够,减少100块}
{查看A够不够100块?如果够,减少100块}
。。。

如果不断地塞入这种数据,那么实际上每次的写入都依托了上一次数据的值。这种操作是必须排队才会高效的,否则会出现超减的情况的。但如果我们的操作只是我们不断地往一个kv里面进行以下操作:

A登陆了
B登陆了
C登陆了
D登陆了
E登陆了
F登陆了

那么可以认为,所有的数据之间都是“相互没有关系的”, 这时候,再让这些写入全部排队一次,代价明显就高了。

我理解的Dynamo和Cassandra,他们的场景主要是适合后面的这种方式,也即数据之间冲突很小的情况。在这种情况下,维持一个全局有序的队列的效率太低了,不如这种分散式的方式。但冲突的概率小,并不意味着没有冲突,所以,还是需要有一套机制,能够帮你感知哪些数据出现了冲突,允许你进行冲突处理的。而在这个问题上dynamo和Cassandra选择了不同的道路。

dynamo选择了vector clock 。
他的主要方式是:在数据传递的信息中,额外带上这数据是从哪里来的版本是多少。
我们来看看,用这种方式,如何能够知道什么时候发生了冲突:
我们假定有A,B,C三台机器。
初始的时候,A,B,C三台机器的数据sequence都是100。
这时候,我随机挑了一台机器,B写了一行记录[key=Whisper , Val=0]
这时候B生成的数据是议案[101 from B->[key=Whisper , Val=0]]。
然后,又有另外一个人选择C写了另外一条记录,比如[key=Whisper , Val=10000]
这时候C生成的数据议案是[101 from C->[key=Whisper , Val=10000]]
这时候,B的数据传递给C。 因为C也有个101的议案,所以【他会保持两份议案】(请注意,这是和paxos不一致的地方哦)

所以C接受的议案是:

[101号议案 
         {fromB [key=Whisper , Val=0]} 
         {fromC [key=Whisper , Val=10000]}
]

然后怎么办?然后..然后你在get("Whisper")这个数据的时候,vector clock会把这两条记录都反馈给你,告诉你,冲突,你自己选择一条吧:)

那么,这样我们有几种选择,对于{count ++ 类}操作,应该将所有决议合并加到一起。而对于其他数据,则应该按照时间戳,取时间戳最大的数据,这是最新的。这就是vector clock的工作流程,在合并这段,让我很容易就想到svn或git中的冲突解决。。

怎么样?是否觉得思路更开阔了?欢迎大家基于paxos和vector clock再进行其他思考,一致性的研究远远没有结束。就我个人嘛。。我更喜欢能保证顺序的一致性模型,不喜欢这种各自为政按需合并的模型。

好,说完了vector clock 我们来说说Cassandra 的Timestamp。

其实,TimeStamp模型是vector clock的劣化和简化版本。在vector clock里面,冲突是由用户处理的,系统只是帮你检查冲突,但Cassandra做的更粗暴和简单一些。他不检测冲突,所有数据只保留时间戳最大的那个。这种模型可以应对80%场景了,模型得到了极大简化,不过我估计应该是不能做count++操作了吧?我没实际使用过。

好,回顾一下,我们在刚才讲了三个新概念: W+R>N 。用来决定一致性级别。gossip协议和Merkle tree,用来进行去中心化的节点间数据同步。vector clock或timestamp。

现在是拼装时间。
dynamo : 数据同步使用了gossip+Merkletree, 使用vector clock来标记冲突数据,冲突数据会交给用户做出处理。允许通过配置,指定一组小集群有几个相同数据的Equalty Group(N)。以及你要写入并保证同时成功的份数(W),以及你要读的份数(R)。
Cassanra :与dynamo类似(因为同源), 在选择上,放弃了vectorclock,使用Timestamp来进行冲突合并。其余的类似。

相关 [dynamo cassandra 基础] 推荐:

Dynamo和Cassandra海量存储基础

- - 忘我的追寻
提到这两个系统,他们在核心思路上是非常类似的,但有一些细节性的东西又有所偏重,在分布式系统中也算是独树一帜了,很有代表性的一个系列,这些不一致的地方,最明显的地方就在于一致性上. 可见,哪怕是从追求简单为上的工程化实现来说,各种不同的方式实现一致性也都有很大的不同,不过他们也有一些共性和一些独树一帜的概念,下面来做一下分别解说.

Amazon Dynamo – 纠结的设计

- Lianhui Wang - NOSQL Notes
从09年第一次阅读Dynamo论文,到最近阅读Amazon S3的一篇专利,一路过来对论文的理解可以简单归结为两个字 – 纠结. 第一次看到Amazon Dynamo论文,有一种眼前一亮的感觉,Dynamo通过巧妙地组合一些P2P技术在Amazon构建了一个工程上可行的系统,CAP,NWR, Vector Clock一时成为流行词,更为神奇的是,Dynamo号称能够让用户设置不同的NWR策略从而在CAP三者之间获得一个很好的权衡,鱼和熊掌亦可兼得.

Cassandra代替Redis?

- - Tim[后端技术]
最近用Cassandra的又逐渐多了,除了之前的360案例,在月初的QCon Shanghai 2013 篱笆网也介绍了其使用案例. 而这篇 百万用户时尚分享网站feed系统扩展实践文章则提到了Fashiolista和Instagram从Redis迁移到Cassandra的案例. 考虑到到目前仍然有不少网友在讨论Redis的用法问题,Redis是一个数据库、内存、还是Key value store?以及Redis和memcache在实际场景的抉择问题,因此简单谈下相关区别.

Cassandra on DC/OS

- - 灰狐博客
Apache Cassandra 是一个强大的开源分布式NoSQL数据库,高度的可伸展性. 基于DC/OS构建其分布式集群是个非常值得采纳的方法,其基本思路是:. 把Cassandra放到Docker里,然后由DC/OS调度Cassandra容器集群运行、管理. Mesos 的 persistence primitives 是一个新的强大的工具,它使得更多的有状态应用可以运行在 Mesos 上.

Cassandra 1.1的缓存策略

- - NoSQLFan
从0.5和0.6版本开始, Cassandra就提供了主键 缓存和行缓存. 在1.1 版本中,Cassandra的核心开发团队重新对缓存策略进行了设计和实现,以提供配置更简单但同时又更高效的缓存效果. 为什么要将缓存集成到数据库内部. 实际上,缓存既可以储存到数据库内部,也可以是外部的独立缓存层.

MariaDB的Cassandra存储引擎

- - InfoQ cn
MariaDB已经宣布了Cassandra存储引擎的一个预览版本. 该插件允许MariaDB通过标准SQL语法使用Cassandra集群. MariaDB并不是第一款为Cassandra提供SQL支持的产品. 例如,Simba提供了一个 Cassandra ODBC驱动,可用于大多数的ODBC兼容工具.

Dynamo的实现技术和去中心化

- - 四火的唠叨
Amazon Dynamo是分布式的key-value系统,最近阅读了Dynamo最初的论文 《Dynamo: Amazon's Highly Available Key-value Store》,本文想聊一聊它的去中心化(decentralization). 既有阅读相关材料后对其实现的理解,也有自己的思考,其中如有不正确言论欢迎指出.

Cassandra新特性:分层压缩

- gnawux - NoSQLFan
目前的压缩机制:Tiered Compaction. 在讲分层压缩之前,我们先来看一下Cassandra目前的数据存储模型和数据压缩机制. 像我们上面说的一样,Cassandra在内存数据达到一定大小时,会将数据排序写入磁盘生成一个sstable文件块,当第一级的sstable数目达到四个时,由于这四个sstable相当于是按时间划分的一段时间的数据快照,所以这四个块中会有一些相同的数据.

[转][转]Cassandra、MongoDB、CouchDB、Redis、Riak、HBase比较

- - heiyeluren的blog(黑夜路人的开源世界)
来源: http://blog.nosqlfan.com/html/1845.html. 在NoSQL如日中天的今天,各种NoSQL产品可谓百花齐放,但每一个产品都有自己的特点,有长处也有不适合的场景. 本文对 Cassandra,  Mongodb,  CouchDB,  Redis,  Riak 以及  HBase 进行了多方面的特点分析,希望看完此文的您能够对这些NoSQL产品的特性有所了解.

Cassandra HBase和MongoDb性能比较

- - 数据库 - ITeye博客
这是一篇基于亚马逊云平台上对三个主流的. NoSQL数据库性能比较,在读写两个操作不同的组合情况下性能表现不同. 横坐标是吞吐量,纵坐标是延迟,这是一对矛盾,吞吐量越大,延迟越低,代表越好. 纯粹插入,Cassandra领先,见下图:. 2.WorkloadA: 读修改操作各占一半情况下的修改性能:MongoDB明显延迟增加,落败:.