DYNAMO平台的独门绝技： 利用NWR模型与vector clock解决锁问题

DYNAMO平台的独门绝技： 利用NWR模型与vector clock解决锁问题

我们知道当系统系统为多用户时，就必须使用文件锁的机制来保护数据的完整性和一致性。举例A用户向数据区D1写了数据1， 那么用户B和C都可以看到D1的数据为1，而当A，B同时在向数据区D1做加1的操作，就需要一个锁，让先发起的用户先操作，后发起的用户就需要在队列里面排队等待前面的用户完成操作，再继续进行。 如果只有几个，几十个用户，基本没有什么延时。但是 如果你有10000个用户，那排的队伍就比ICBC还要长咯。

         云存储用分布式的存储方式解决了大量的并发读的问题，但是针对并发写，也有很好的设计和算法。老蒋介绍一下AMAZON的dynamo的特殊设计，看如何能让你10000个用户快速的访问数据：

Quorum NRW

• N: 复制的节点数量
• R: 成功读操作的最小节点数
• W: 成功写操作的最小节点数

只需W + R > N，就可以保证强一致性。
Dynamo 的处理方式是把这个选择权交给用户，这就是它的N W R模型。N代表N个备份，W代表要写入至少W份才认为成功，R表示至少读取R个备份。配置的时候要求W+R > N。 因为W+R > N， 所以 R > N-W 这个是什么意思呢?就是读取的份数一定要比总备份数减去确保写成功的倍数的差值要大。

也就是说总是能读出一份最新的文档。呵呵，这就保证了读文件时版本不同的问题。

而写文件时最为复杂，Dynamo 的方法是保留所有时间版本，用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那四个版本。这个例子只举了一个客户的请求在被不同节点处理时候的情况

Dynamo 为了给出充分的弹性而被设计成完全的对等集群(peer to peer)，网络中的任何一个节点都不是特殊的。vector clock感觉是让存储设备存储了数据个各个版本信息，在用户要读取使用时，再让应用来进行合并处理，把原来分布锁中大量的处理给延后了。 而vector clock产生了大量非同步的数据必须使用N W R模型找出最新的数据。

建议继续学习：