分布式一致算法 clock

作者 chauncy 日期 2016-12-30
分布式一致算法 clock

aws 的 Dynamo 在数据一致性上面使用的算法为 vector clock (也叫做Data Version) 感觉挺不错,然后就去看了看paper

主要是使用的是一种 vector clock 和 logic clock
要解释这一个东西,就不得不说一个神一样的纯在的lamport大神写的“Time Clocks and the Ordering of Events in a Distributed System”可以认为是Vector Clock的理论基础,有兴趣同学可以看看

先来说说 logic clock
logic clock 说简单一点就是定义了一种happen before原则,过多的理论就不说了,直接搬出算法,主要遵守这几个规则
1.在一个进程中,每次处理一个时间的时候,他的计算器要增加1
2.当以进程发送一个消息到另外个进程的时候,应该将计算器的值联通消息一起发送过去
3.当接收进程收到一个消息的时候,他的计数器应该去两则之间的最大
sending 端:
time = time+1;
time_stamp = time;
send(message, time_stamp);
receiving 端:
(message, time_stamp) = receive();
time = max(time_stamp, time)+1;

vector clock
1.初始化所有的时钟为0
2.每一次处理内完内部事件,将自己的logic clock 加1
3.每一次发送一个消息的时候,需要将自己的向量时钟和消息一起发送
4.每一次接收到一个消息的时候,需要将自己的 logic clock +1,同时更新每一个逻辑时钟,更新的规则是取出收到 向量时钟和自己的取最大值

向量时钟

假设分布式系统有A、B和C这3个进程,根据上述规则其各自对应的逻辑时钟 随着时间演化情况如图所示,其数值变化规则遵循上述规则,时间线之间的边代表 进程间发送的消息。标为cause的阴影部分代表导致[A:2,B:4,C:1] 事件的原因,标为effect的阴影部分则代表[ A:2,B:4,C:1]事件影响到的后续事件, 而无阴影部分覆盖的事件则是和[ A:2, B:4, C:1]事件无逻辑上因果关系的事件,事件,比如事件[ A:1,B:2,C:1]以及[ A:4,B:5,C5],通过和[A:2, B:4,C:1]对应位置比较可知其因果关系为:, B: 2, C: 1] 为[ A: 2, B: 4, C: 1]之 因,[ A: 4, B: 5, C5] 为[ A: 2, B: 4, C: 1] 之 果。而Dynamo数据就是通过向量时钟和RWN协议完成数据一致性维护的。