解决数据版本问题
这里我们需要讨论一下数据版本问题，这个问题不仅仅存在于分布式系统，只是分布式系统的一些要求使得这个问题更复杂。先看个简单的例子，用户x对key1做了一次写入操作，我们设值是数字3。然后用户y读取了key1，这个时候用户y知道的值是3。然后用户x对值做了一个+1操作，将新值写入，现在key1的值是4了。而用户y也做了一次+1操作，然后写入，因为用户y读到的值是3，y不知道这个值现在已经变化了，结果按照语义本应该是5的值，现在还是4。
解决这个问题常用的方法是设置一个版本值。用户x第一次写入key1 值3的时候，产生一个版本设为v1。用户y读取的信息中包括版本编号v1。当x做了加1把值4写入的时候，告诉server自己拿到的是版本v1，要在v1的基础上把值改成4。server发现自己保存的版本的确是v1所以就同意这个写入，并且把版本改成v2。这个时候y也要写入4，并且宣称自己是在版本v1上做的修改。
但是因为server发现自己手里已经是版本v2了，所以server就拒绝y的写入请求，告诉y，版本错误。这个算法在版本冲突的时候经常被使用。但是刚才我们描述的分布式系统不能简单采用这个方式来实现。
假设我们设置了N=3 W=1。现在x写入key1 值3，这个请求被节点A处理，生成了v1版本的数据。然后x用户又在版本v1上进行了一次key1值4的写操作，这个请求这次是节点C处理的。但是节点C还没有收到上一个A接收的版本(数据备份是异步进行的)如果按照上面的算法，他应该拒绝这个请求，因为他不了解版本v1的信息。但是实际上是不可以拒绝的，因为如果C拒绝了写请求，实际上W=1这个配置，这个服务器向客户做出的承诺将被打破，从而使得系统的行为退化成W=N的形式。那么C接收了这个请求，就可能产生前面提到的不一致性。如何解决这个问题呢?
Dynamo 的方法是保留所有这些版本，用vector clock记录版本信息。当读取操作发生的时候返回多个版本，由客户端的业务层来解决这个冲突合并各个版本。当然客户端也可以选择最简单的策略，就是最近一次的写覆盖以前的写。
vector clock算法保证版本信息
这里又引入了一个vector clock算法，这里简单介绍一下。可以把这个vector clock想象成每个节点都记录自己的版本信息，而一个数据，包含所有这些版本信息。来看一个例子：假设一个写请求，第一次被节点A处理了。节点A会增加一个版本信息(A，1)。我们把这个时候的数据记做D1(A，1)。 然后另外一个对同样key(这一段讨论都是针对同样的key的)的请求还是被A处理了于是有D2(A，2)。
这个时候，D2是可以覆盖D1的，不会有冲突产生。现在我们假设D2传播到了所有节点(B和C)，B和C收到的数据不是从客户产生的，而是别人复制给他们的，所以他们不产生新的版本信息，所以现在B和C都持有数据D2(A，2)。好，继续，又一个请求，被B处理了，生成数据D3(A，2;B，1)，因为这是一个新版本的数据，被B处理，所以要增加B的版本信息。
假设D3没有传播到C的时候又一个请求被C处理记做D4(A，2;C，1)。假设在这些版本没有传播开来以前，有一个读取操作，我们要记得，我们的W=1 那么R=N=3，所以R会从所有三个节点上读，在这个例子中将读到三个版本。A上的D2(A，2);B上的D3(A，2;B，1);C上的D4(A，2;C，1)这个时候可以判断出，D2已经是旧版本，可以舍弃，但是D3和D4都是新版本，需要应用自己去合并。
如果需要高可写性，就要处理这种合并问题。好假设应用完成了冲入解决，这里就是合并D3和D4版本，然后重新做了写入，假设是B处理这个请求，于是有D5(A，2;B，2;C，1);这个版本将可以覆盖掉D1-D4那四个版本。这个例子只举了一个客户的请求在被不同节点处理时候的情况， 而且每次写更新都是可接受的，大家可以自己更深入的演算一下几个并发客户的情况，以及用一个旧版本做更新的情况。
上面问题看似好像可以通过在三个节点里选择一个主节点来解决，所有的读取和写入都从主节点来进行。但是这样就违背了W=1这个约定，实际上还是退化到W=N的情况了。所以如果系统不需要很大的弹性，W=N为所有应用都接受，那么系统的设计上可以得到很大的简化。Dynamo 为了给出充分的弹性而被设计成完全的对等集群(peer to peer)，网络中的任何一个节点都不是特殊的。
解决单点故障问题
最后还有一个单点故障的问题，这个问题的解决要求系统构建的时候是完全分布式，不存在一个核心的。例如传统的存储系统里面往往存在一个中心节点，这个单点的存在使得系统在这一点上变得很脆弱。解决方法就是让系统的每个节点都可以承担起所有需要的功能。这个问题的解决涉及到事情比较多，以亚马逊平台的Dynamo分布式存储引擎来说，有Seed节点的概念，不过本文我们暂时不做过多剖析。
Vector Clock是Amazon’s Dynamo用来捕捉同一不同版本的对象的因果关系的一种算法。根据Dyanmo paper的描述，矢量时钟实际上是一个(node,counter)对列表(即(节点，计数器)列表)。矢量时钟是与每个对象的每个版本相关联。通过审查其向量时钟，我们可以判断一个对象的两个版本是平行分枝或有因果顺序。如果第一个时钟对象上的计数器在第二个时钟对象上小于或等于其他所有节点的计数器，那么第一个是第二个的祖先，可以被人忽略。否则，这两个变化被认为是冲突，并要求协调。
是不是有点晕？为了理解，自己举了个例子：
现在有个手机商城，里面卖的iphone价格是瞬息万变的，有全国各地好几个编辑不停地更新自己那边iphone的价格。当然同时也不断有用户询问当前iphone的价格。
假设该商城有A、B、C三个node，则我们的N是3。
我们准备只写一份W=1,那么根据W+R>N有R=3。那么就有如下场景：
- 首先A收到了iphone价格是4000的请求。我们有了4000[A:1];
- 在数据被复制到B，C之前，有人告诉A，价格上调，变成了4500.那么A上就有了4500[A:2],它覆盖了之前的[A:1]
- 随后这个价格被复制到了B，C。那么B，C上也有了4500[A:2].
- 此时，有人告诉B说iphone又涨了，变成了5000块，那么B上就有了5000[A:2,B:1]
- 在B上这个价格被复制到A，C之前，又有个请求到C说iphone降价了，变成了3000块！
经过上面这么一番折腾，C上有了3000[A:2,C:1],此时A上是4500[A:2]， B上则是5000[A:2,B:1]。
三个node上数据全不一致！！！有点儿乱啊~
根据墨菲定律——最不想发生的事情发生了——这时有人询问iphone的价格。
看看vector clock这时能起到什么作用？
由于我们的R=3, 所以这三个几点上的数据都会被读到，那么4500、5000和3000哪个被返回呢？显而易见，A上的版本最低，应被舍弃，那么B和C呢？
客户端拿到3000[A:2,C:1]和5000[A:2,B:1]确实有点手足无措，但我们可以让它有个判断依据——比如时间戳——现在客户端看到B上的数据是最新的，那么结论就是5000.
既 然已经有了结论，那就不能让之后的客户端再这么纠结，接下来就是要统一各个节点，合并vector clock。这时候要做的事情就是通知A节点，现在iphone价格是5000以及得到5000这个值所基于的vector clock.这样A上的数据就变成了5000[A:3,C:1, B:1]. 这样，再有读请求的话，我们可以毫不犹豫的选择A上的数据。
我们看看如果W=2,R=2的情况：
- A收到4000，但是只有这个数据也到达B，才算成功。所以我们有了A上的4000[A:1]和B上的4000[A:1]
- 在被复制到C之前，有人告诉A，价格上调，变成了4500.同上A和B上都会有4500[A:2]
- 数据被复制到C，C上也有了4500[A:2]
- 此时，有人告诉B说iphone又涨了，变成了5000块，那么B上就有了5000[A:2,B:1] 同1理，C上有了5000[A:2,B:1]
- 又 有个请求到C说iphone降价了，变成了3000块！那么C上应该有3000[A:2,B:1,C:1] .同1理，新数据的写也会到达A,A上的4500[A:2]看到3000[A:2,B:1,C:1]后，无条件接受被覆盖，因此也变成了 3000[A:2,B:1,C:1]。
经过上面这么一番折腾，C上有了3000[A:2,B:1,C:1],此时A上是3000[A:2,B:1,C:1]， B上则是5000[A:2,B:1]。
这时读请求过来我们还纠结吗？虽然R=2，但无论我们读哪两个，都将得到5000这个价格，因为显然[A:2,B:1,C:1]要比[A:2,B:1]的更新鲜。上面这番折腾在W=2的情况下不需要协调。
由此我们也可以看出提高W可以降低冲突，提高一致性。但代价也是显然的：写两份显然比写一份要慢，并且同时能写成功的概率也变低了——也就是Availability降低。这跟CAP理论也是吻合的。
关于向量时钟一个可能的问题是，如果许多服务器协调对一个对象的写，向量时钟的大小可能会增长。实际上，这是不太可能的，因为写入通常是由首选列表中的前 N个节点中的一个节点处理。在网络分裂或多个服务器故障时，写请求可能会被不是首选列表中的前N个节点中的一个处理的，因此会导致矢量时钟的大小增长。在 这种情况下，值得限制向量时钟的大小。为此，Dynamo采用了以下时钟截断方案：伴随着每个(节点，计数器)对，Dynamo存储一个时间戳表示最后一 次更新的时间。当向量时钟中(节点，计数器)对的数目达到一个阈值(如10)，最早的一对将从时钟中删除。显然，这个截断方案会导至在协调时效率低下，因为后代关系不能准确得到。不过，这个问题还没有出现在生产环境，因此这个问题没有得到彻底研究。
觉得不错的文章
why vector clocks are easy:
http://blog.basho.co
why vector clocks are hard
http://blog.basho.co
vector clocks again:
http://pl.atyp.us/wo
三篇文章比较详细的介绍了vector clock，希望对大家有所帮助
