Dynamo和Cassandra海量存储基础

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

先说共性：

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来进行冲突合并。其余的类似。