跳至主要內容

逻辑时钟

钝悟...大约 9 分钟分布式分布式综合分布式物理时钟逻辑时钟向量时钟全序偏序

逻辑时钟

什么是逻辑时钟

1978 年,Lamport 在 Time, Clocks, and the Ordering of Events in a Distributed Systemopen in new window 中提出了逻辑时钟的概念,来解决分布式系统中区分事件发生的时序问题。

逻辑时钟指的是分布式系统中用于区分事件的发生顺序的时间机制

为什么需要逻辑时钟

对于程序来说,时间维度非常重要,很多业务逻辑都依赖于时间。常见的场景有:

  • 某个请求是否超时了?
  • 某项服务 P99 的响应时间是多少?
  • 在过去五分钟,服务平均每秒处理多少个查询?
  • 用户在我们的网站上浏览花了多段时间?
  • 这篇文章什么时候发表?
  • 在什么时间发送提醒邮件?
  • 这个缓存条目何时过期?
  • 日志文件中错误消息的时间戳是多少?

分布式系统,意味着整个系统中有多个节点。为了让多节点的系统时间保持同步,需要有一个对表机制,来保证各节点的时间一致。一种常见方法是使用 NTPopen in new window,它的工作机制是使用专门的高精度时间服务器来作为基准,调整服务器的本地时间。即使使用了 NTP,也难免存在微小的误差,在有些场景中(如金融)是不能接受的。

在分布式系统中,由于跨节点通信不可能即时完成,因此在多节点上难以确定事件的先后顺序。而逻辑时钟就是一种定义时序先后顺序的方案。

全序和偏序

全序和偏序是集合论中的概念,用于描述集合中元素之间的关系。

什么是偏序

偏序是指集合中的元素之间存在一种关系,使得任意两个元素之间可能存在比较,但不一定所有元素都可以相互比较。这种关系不一定是传递的或者反对称的。例如,集合中的子集关系就是一个偏序关系,因为不是所有的子集都可以相互比较。

设 R 是集合 A 上的一个二元关系,若 R 满足:

(1)自反性:对任意 x∈A,有 xRx

(2)反对称性(即反对称关系open in new window):对任意 x,y∈A,若 xRy,且 yRx,则 x=y

(3)传递性:对任意 x,y,z∈A,若 xRy,且 yRz,则 xRz

则称 R 为 A 上的偏序关系。

什么是全序

全序是指集合中的元素之间存在一种关系,使得任意两个元素都可以进行比较,且这种比较关系是传递的,反对称的。换句话说,任意两个元素都可以比较大小,并且不会出现无法比较的情况。例如,实数集合上的小于等于关系就是一个全序关系。

设集合 X 上有一全序关系,如果我们把这种关系用 ≤ 表述,则下列陈述对于 X 中的所有 a, b 和 c 成立:

如果 a ≤ b 且 b ≤ a 则 a = b(反对称性open in new window

如果 a ≤ b 且 b ≤ c 则 a ≤ c(传递性open in new window

a ≤ b 或 b ≤ a (完全性)

注意

完全性本身也包括了自反性open in new window。 所以,全序关系必是偏序关系open in new window

时序的关键

**两个事件可以建立因果(时序)关系的前提是:两个事件之间是否发生过信息传递。**在分布式系统中,进程间通信的手段(共享内存、消息发送等)都属于信息传递,如果两个进程间没有任何交互,实际上他们之间内部事件的时序也无关紧要。但是有交互的情况下,特别是多个节点的要保持同一副本的情况下,事件的时序非常重要。

逻辑时钟

分布式系统中按是否存在节点交互可分为三类事件,一类发生于节点内部,二是发送事件,三是接收事件。Lamport 时间戳原理如下:

Lamport timestamps space time (图片来源: wikipedia)_
Lamport timestamps space time (图片来源: wikipedia)_
  1. 每个事件对应一个 Lamport 时间戳,初始值为 0
  2. 如果事件在节点内发生,时间戳加 1
  3. 如果事件属于发送事件,时间戳加 1 并在消息中带上该时间戳
  4. 如果事件属于接收事件,时间戳 = Max(本地时间戳,消息中的时间戳) + 1

假设有事件 a、b,C(a)、C(b)分别表示事件 a、b 对应的 Lamport 时间戳,如果 a->b,则 C(a) < C(b),a 发生在 b 之前(happened before),例如图 1 中有 C1 -> B1。通过该定义,事件集中 Lamport 时间戳不等的事件可进行比较,我们获得事件的偏序关系open in new window(partial order)。

如果 C(a) = C(b),那 a、b 事件的顺序又是怎样的?假设 a、b 分别在节点 P、Q 上发生,Pi、Qj 分别表示我们给 P、Q 的编号,如果 C(a) = C(b) 并且 Pi < Qj,同样定义为 a 发生在 b 之前,记作 a => b。假如我们对图 1 的 A、B、C 分别编号 Ai = 1、Bj = 2、Ck = 3,因 C(B4) = C(C3) 并且 Bj < Ck,则 B4 => C3。

通过以上定义,我们可以对所有事件排序、获得事件的全序关系open in new window(total order)。上图例子,我们可以从 C1 到 A4 进行排序。

向量时钟

Lamport 时间戳帮助我们得到事件顺序关系,但还有一种顺序关系不能用 Lamport 时间戳很好地表示出来,那就是同时发生关系(concurrent)(4)。例如图 1 中事件 B4 和事件 C3 没有因果关系,属于同时发生事件,但 Lamport 时间戳定义两者有先后顺序。

Vector clock 是在 Lamport 时间戳基础上演进的另一种逻辑时钟方法,它通过 vector 结构不但记录本节点的 Lamport 时间戳,同时也记录了其他节点的 Lamport 时间戳(5)(6)。Vector clock 的原理与 Lamport 时间戳类似,使用图例如下:

Vector clock space time (图片来源: wikipedia)
Vector clock space time (图片来源: wikipedia)

假设有事件 a、b 分别在节点 P、Q 上发生,Vector clock 分别为 Ta、Tb,如果 Tb[Q] > Ta[Q] 并且 Tb[P] >= Ta[P],则 a 发生于 b 之前,记作 a -> b。到目前为止还和 Lamport 时间戳差别不大,那 Vector clock 怎么判别同时发生关系呢?

如果 Tb[Q] > Ta[Q] 并且 Tb[P] < Ta[P],则认为 a、b 同时发生,记作 a <-> b。例如图 2 中节点 B 上的第 4 个事件 (A:2,B:4,C:1) 与节点 C 上的第 2 个事件 (B:3,C:2) 没有因果关系、属于同时发生事件。

版本向量时钟

基于 Vector clock 我们可以获得任意两个事件的顺序关系,结果或为先后顺序或为同时发生,识别事件顺序在工程实践中有很重要的引申应用,最常见的应用是发现数据冲突(detect conflict)。

分布式系统中数据一般存在多个副本(replication),多个副本可能被同时更新,这会引起副本间数据不一致,Version vector 的实现与 Vector clock 非常类似,目的用于发现数据冲突。下面通过一个例子说明 Version vector 的用法:

Version Vector Clock
Version Vector Clock
  • client 端写入数据,该请求被 Sx 处理并创建相应的 vector ([Sx, 1]),记为数据 D1
  • 第 2 次请求也被 Sx 处理,数据修改为 D2,vector 修改为([Sx, 2])
  • 第 3、第 4 次请求分别被 Sy、Sz 处理,client 端先读取到 D2,然后 D3、D4 被写入 Sy、Sz
  • 第 5 次更新时 client 端读取到 D2、D3 和 D4 3 个数据版本,通过类似 Vector clock 判断同时发生关系的方法可判断 D3、D4 存在数据冲突,最终通过一定方法解决数据冲突并写入 D5

Vector clock 只用于发现数据冲突,不能解决数据冲突。如何解决数据冲突因场景而异,具体方法有以最后更新为准(last write win),或将冲突的数据交给 client 由 client 端决定如何处理,或通过 quorum 决议事先避免数据冲突的情况发生(11)。

由于记录了所有数据在所有节点上的逻辑时钟信息,Vector clock 和 Version vector 在实际应用中可能面临的一个问题是 vector 过大,用于数据管理的元数据(meta data)甚至大于数据本(12)。

解决该问题的方法是使用 server id 取代 client id 创建 vector (因为 server 的数量相对 client 稳定),或设定最大的 size、如果超过该 size 值则淘汰最旧的 vector 信息(10)(13)。

参考资料

评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.15.7