软件架构与思考

👉 所有文章
高性能 高性能设计模式
数据库 数据库分库分表指南 MySQL 建表参考 MySQL 初始化数据的一些方案 数据版本号
分布式 ID 分布式 ID 生成方案探讨
缓存 缓存 使用数据版本号保证缓存是最新数据 基于redis的二级缓存
微服务 如何实现远程调用 RPC 协议中的数据签名验签和加解密方案探讨 关于服务间调用循环依赖的一些思考 我所理解的负载均衡 一致性哈希 基于Redis的分布式会话管理系统 如何部署服务 灰度发布 如何区分上游和下游 日志级别
算法与协议 一个可扩展的 MQ 消息设计 Dynamo涉及的算法和协议 写时复制
任务分发 Gearman入门 如何使用redis构建异步任务处理程序
安全 关于对账的一些理解 一个简单可靠的 Dubbo 请求/响应数据签名方案
其他 使用卫语句减少 if else 嵌套

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 著 巨成 译


( 本文完 )

文章目录