Dynamo涉及的算法和协议

2014-6-16

Dynamo是Amazon的一个分布式的键值系统,P2P架构,没有主从的概念,数据一致性做到了最终一致。Apache Cassandra参考了它的实现方法。

一致性哈希

关于一致性哈希的具体内容,可以参考一致性哈希

容错

由于一致性哈希的使用,Dynamo集群中的节点在逻辑上可以认为是一个圆环。假设有M个节点,我们从某个节点开始顺时针地依次为每个节点标号为1、2、3、…、M。出于容错的需要,假设一份数据存3份。如果某份数据通过一致性哈希被存储到了节点2中,那么这份数据的另外两个副本存储在节点3和节点4中。如果节点3临时性的宕机了,那么在节点3恢复之前,会把增量数据存入节点5中;待节点3恢复后,节点5通过Gossip协议发现节点3恢复了,节点5会将那些暂存的数据“数据回传”给节点5。判断节点3的宕机是临时性的还是永久性的方法比较简单,就是看它宕(dang)机的时间长短。如果节点3永久性宕机了,那么需要使用有效的方式将这份数据的完整版本同步到节点5中。

Gossip协议

Gossip协议,也就是闲话协议。主要用来让每个节点知道集群的最新状态。这个协议其实就是:

with a given frequency, each machine picks another machine at random and shares any hot rumors.

节点之间以固定的时间频率交换信息。在交换信息时,一节点随机选取集群中的其他某个节点交换各自对集群的掌握情况,并据此更新到最新(或者较新)的集群状态信息。

NWR

N表示一份数据的副本数量。W代表写操作成功所至少需要的副本数,即在一次写入操作中至少W个副本写成功了,这次写操作才算成功。R代表读操作成功所至少需要的副本数。Dynamo认为只要R+W>N,可以保证集群的可用性。N、W、R的值是可以设定的。如果注重读的效率,可以把R的值设置小些;如果注重写的效率,可以把W的值设置小些。NWR并不能保证数据一致。如果R=N且W=N,那么可以保证一致性。

向量时钟

对于小型的或者要求不高的分布式系统而言,可以使用时间戳的方式保证副本之间数据的一致性,在时间戳方式下,多使用NTP协议同步时钟,节点之间的时钟有较小的误差。不过在大型分布式系统中,还是换种方式比较好。

向量时钟(Vector Clock),Amazon Dynamo使用的解决数据一致性问题的方法。这是一个逻辑上的时钟。假设一份数据三个副本,这三个副本分别命名为n1n2n3,每个副本都会记录所有副本的时钟(包括自身的),一个副本一个向量,三个副本则共有三个向量。所谓时钟,其实就是所存储数据的版本号,一般从0递增即可。更新时钟的规则如下:

  • 初始化所有时钟,即全部置0。
  • 某副本有数据更新时,将其自身的向量中自身的时钟的值加一个步长,一般步长设置为1。
  • 当一副本向其他副本发送消息时(一般是为了同步数据),这个副本会把自身的向量一起发送给其他副本。
  • 若一副本接收到消息,将其自身的向量中自身的时钟的值加一个步长,并 比较自身的向量和发送来的向量,如果发送来的消息是希望同步数据,那么需要判断是否更新数据。对每个向量的元素比较并取最大值,以此更新自身的向量。那么,如何更新数据? 该副本自身存储的向量的每一个值都小于发送来的向量的每一个值,说明发送来的数据比较新,那么更新数据。如果都大于,则不需要更新数据。当然,第三种情况是既有大于的关系,也有小于的关系;还有一种情况是向量相同,但是数据不同。这种情况下,需要进行冲突的解决,比如再比较时间戳。

举个例子。

假设,n1n2n3要存储的用户id为1的用户的昵称。
最开始,三个副本的向量时钟以及数据如下表示:

n1: { vector: {n1:0, n2:0, n3:0}, data: null }
n2: { vector: {n1:0, n2:0, n3:0}, data: null }
n3: { vector: {n1:0, n2:0, n3:0}, data: null }

时刻1,n1将用户昵称更新为john,向量时钟以及数据更新后如下:

n1: { vector: {n1:1, n2:0, n3:0}, data: 'jian' }
n2: { vector: {n1:0, n2:0, n3:0}, data: null }
n3: { vector: {n1:0, n2:0, n3:0}, data: null }

此时对系统进行读操作,结果应是’jian’。n1给n2、n3发送了消息,更新后如下:

n1: { vector: {n1:1, n2:0, n3:0}, data: 'jian' }
n2: { vector: {n1:1, n2:0, n3:0}, data: 'jian' }
n3: { vector: {n1:1, n2:0, n3:0}, data: 'jian' }

此时对系统进行读操作,结果应是’jian’。

时刻2,n3将用户昵称改为’fan’,更新后如下:

n1: { vector: {n1:1, n2:0, n3:0}, data: 'jian' }
n2: { vector: {n1:1, n2:0, n3:0}, data: 'jian' }
n3: { vector: {n1:1, n2:0, n3:1}, data: 'fan' }

此时对系统进行读操作,结果应是’fan’。n3先给n2发送了消息,更新后如下:

n1: { vector: {n1:1, n2:0, n3:0}, data: 'jian' }
n2: { vector: {n1:1, n2:0, n3:1}, data: 'fan' }
n3: { vector: {n1:1, n2:0, n3:1}, data: 'fan' }

当n3要给n1发消息之前,n1却对数据进行了修改,例如将用户昵称改为’ ruan’,更新后如下:

n1: { vector: {n1:2, n2:0, n3:0}, data: 'ruan' }
n2: { vector: {n1:1, n2:0, n3:1}, data: 'fan' }
n3: { vector: {n1:1, n2:0, n3:1}, data: 'fan' }

此后,可能会出现下面两种冲突:

  • 对系统进行读操作,发现n2、n3与n1的向量没有偏序关系(即不小于也不大于),而且存的数据的值是不同的。此时需要解决冲突。
  • n1收到了n3发送来的消息,比较了两者的向量,发现了冲突,于是想办法解决。

资料

Vector clock

Gossip protocol

2.4.5 向量时钟(1)

《大规模分布式存储系统——原理解析与架构实践》第五章 杨传辉 著
《深入NoSQL》 Shashank Tiwari 著 巨成 译

( 完 )