深入浅出分布式系统(二) - 时间

发表于   |   分类于 技术   |   暂无评论

一、写在前面

第一节 介绍了分布式系统的定义、特性，以及CAP原理。 本节希望对分布式系统的时间特性有个更加深入的思考和探讨。本节也是《Time, Clocks, and the Ordering of Events in a Distributed System》的读后笔记，建议对比原文一起阅读。

上一节提到分布式系统对于时间的不确定性，主要体现在 多节点无法统一时间 以及 节点间传递信息的时间不能忽略。通常，我们判断两个事件a比b先发生，是指a发生的时间早于b发生的时间时间早，现在连时间都不靠谱了，导致我们无法通过直接通过物理时间来判断两个事件的先后顺序（因果关系）。

如果能找到一种不依赖物理时间的算法，通过定义出让所有节点都认同的时序，是否也意味着能够定义了所有事件的绝对顺序。

按相对论的解释，物理世界光速是恒定的，时间和空间都是相对的，所以我们根本无法设计一个绝对的物理时间。另一方面，我们追求绝对物理时间没有什么意义， 因为我们现实的世界就是相对的。

这里我们仍引入第一节中提到的XBox系统，系统的功能很简单，提供了一个变量的读写。支持两个指令：

  • GET ：获取值,无参数
  • SET X : 设置值，参数为需要设置的值

二 偏序（Partial Ordering）

2.1 定义偏序

首先定义符号 →，表示"因果关系"

因果：原文用的happen before

  • 如果a和b发生于同一个节点上，且a先发生，那么有 a → b ；
  • 如果a给b发送消息，那么也有 a → b；
  • 如果 a → b， b → c ，那么 a → c ;
  • 如果既不存在 a → b，也不存在 b → a，那么a和b是并发的；

请输入图片描述

上图是A、B、C三个节点的时序图，根据 → 的定义，可以得到以下的因果时序表，得出同一个节点的时序和不同节点有依赖关系的因果时序，我们把这事件的排序叫做偏序。

同一节点的因果时序 不同节点的因果时序 并发
a1 → a2 → a3 → a4
b1 → b2 → b3 → b4
c1 → c2		 a2 → b1 → b2 ....
a2 → c1 → c2...
b4 → a4
b4 → c2		 <a3,b1,c1>
<a3,b2,c1>
<a3,b3,c1>

但是从上表能看出来还有几个问题：

  • 每个节点有自己的时序编号，单节点时序编号是递增的，但是全局的时序编号不是递增的。
    如：a2 → b1 → b2 ，我们没法从全局直观的看出三个事件时序，我们更希望的应该是a2->b3->b4这种时序。

  • 并发是有先后顺序的，a3同时与b1、b2、b3并发，但是b1\b2\b3是有顺序的，违反我们的直觉。

2.2 逻辑时钟

刚才提到从整体看来时序编号不是递增的，我们更希望有一个全局递增的逻辑时钟。

强化一下时钟的定义：

  • 定义一个全局共享且递增逻辑全局时钟C
  • 每个节点定义一个属于自己的节点时钟，分别对应Ca 、 Cb 、Cc ..
  • 全局逻辑时钟的值等于时间发生事件时刻的节点时钟的值；C(a1)=Ca(a1)

C表示某节点的时钟，C(?)表示某事件对应的全局时钟编号，C(?)表示某事件对应的节点时钟编号
也可以知道C>=C<?>
根据因果的关系，可以定义逻辑时钟条件（Clock Condition）

根据 → 的定义和时钟条件的定义，可以看到要满足时钟条件，需要满足如下情况：

  • 如果a1和a2同属于节点A ， 且a1先发生，那么有 Ca(a1) < Ca(a2) 等同于 C(a1) < C(a2)
  • 如果a1属于A, b1属于B, 且a1发消息给b1，那么有Ca(a1)<Cb(b1)等同于C(a1)<C(b1)

很容易得到进程中的逻辑时钟的算法：

  • 相同节点连续的两个事件，需要增加 全局时钟 和节点时钟 的值。
  • 两节点有因果依赖时，发送消息时带上发送方的时间戳 Tm，接收方把自己的节点时钟调整为max(发送方时钟, 自己的节点时钟)+1
    如A节点向B节点发送消息，A节点的时钟当前为Ca， B节点的时钟为Cb， 最后全局时钟以及B节点的时钟为max(Ca, Cb)+1

请输入图片描述

综上我们成功定义了一个递增的全局时钟, 上图的红色字体表示全局时钟序号，我们也得到了一个新的因果时序表。这个时序表理的时序编号是递增的。

同一节点的因果时序 不同节点的因果时序 并发
A1->A2->A7->A8
B3->B4->B5->B6
C3->C7		 A2->B3->B4->B6...
A2->C3->C7
B6->A7
B6->C7		 <A3,B3,C3>
<A7,B7,C7>

三、 全序

通过逻辑时钟算法，我们对一个系统中的所有事件进行排序。但由于存在并发，任然无法让每个节点使用相同的时序，我们希望得到是单调递增的逻辑时钟。

于是我们在增加"逻辑因果"的定义，把原本没有因果的逻辑，强制加上先后顺序。

把扩展→ 到⇒ ，对于事件a、b，满足以下两个条件时才认为⇒

  • （i）Ca(a1) < Cb(b1)
  • （ii）Ca(a1) = Cb(b1) 且 P(i) ≺ P(j)

P(i) ≺ P(j) 的关系为人工定义的优先级，我可以定义A>B>C，也可以定义A<B<C，通过一个预设的顺序将并发变成有先后顺序的事件，这可能会与我们实际的时间看上去很不一致，但是逻辑上，是自洽的。

系统只关注有因果关系的顺序，没有因果关系的事件，我们给一个通用的顺序，看起来很随意。实际上解决了一个大问题，对于所有的节点而言，所有的事件都有了相同的顺序。

请输入图片描述

如上图红色处理的部分。把原来的A3=B3=C3变为了A3>B3>C3，我们的因果时序表也发生了变化。

整体时序
A1->A2->A3->B3->C3->B4->B5->B6->A7->B7->C7->A8->B8

注：A3的物理时间比B3大，但是A和B的逻辑时钟都是3，而且A节点优先级高于B，所以认为A3的逻辑时间更小。

四、XBox的时序

论文原文解决的是一个分布式锁的问题，这里我替换为更加简单的XBox系统。这里通过引入逻辑时钟解决了XBox的一致性问题。

约束条件

  • GET指令导致节点时钟、全局时钟加一
  • SET指令导致节点时钟、全局时钟加一
  • SET指令触发同步其他节点消息；将当前节点时钟与SET参数一起发送到其他节点，其他节点收到SET指令后，判断是否要执行SET指令，并将节点时钟，设置为max(消息节点时钟,当前节点时钟)+; 回复ACK并带上当前节点时钟；发送节点收到ACK后，将时钟设置为ACK时钟+1;
  • 判断是否执行SET规则：当前时钟<消息内发送方时钟

请输入图片描述

如上图，因为A SET 1指令由于网络原因比B的SET 2指令更晚到达，但是C节点知道SET 1是更早的请求，就会忽略SET 1指令。

五、遗留问题

通过逻辑时钟我们只能把系统内部事件排序，但是外部系统可能会改变系统内部的顺序，体现不到系统内部，如下图：外部系统导致B3 =>A3 。但是内部系统依然会任务A3=>B3 。

请输入图片描述

解决这个问题的办法是把外部系统也加入到系统中或者引入物理时钟。

六、总结

我们熟悉的raft、zab、paxos都有逻辑时钟的概念，不过换了一些名字，比如任期。

添加新评论