京公网安备11010502063487号分布式系统里“谁先谁后”靠什么判断?物理时钟有偏差,会让接收早于发送。Lamport 时钟、向量时钟、混合逻辑时钟各保证什么、各付出什么?拿它们做最后写入者胜会怎样?这篇用 3 个真实进程互发消息、注入时钟偏差,把它们的行为数出来。
时钟偏差 | 收到的消息数 | 接收时间戳 < 发送时间戳的消息数 | 最大倒退量 -------------------+--------+-------------------+------- 三个节点时钟完全一致(偏差 0) | 276 | 0 | 0 ms 偏差 [0, 50, -80] ms | 276 | 140 | 130 ms 偏差为 0 时(本机同一个时钟)没有一条消息倒退;偏差 [0, +50, -80] 时,从“快”的节点发给“慢”的节点的消息,在接收方看来是“来自未来”——这里注入的偏差只是模拟机器之间的时钟不同步
节点之间的时钟偏差让因果上在后的事件时间戳更小。
共 713 个事件;Lamport 条件 “发送的 L < 接收的 L” 被违反的消息数:0 抽样 19964 对:有因果关系的 19727 对,真正并发的 237 对 并发的 237 对里,Lamport 给出了先后(L 不相等)的有 207 对(87.3%):单看 Lamport 值分不清“有因果”还是“碰巧数字大小不同” 有因果关系的 19727 对里,按物理时间戳反而是“后发生的更小或相等”的有 196 对(1.0%) 向量时钟对全部 19964 对的判定(a 先于 b / b 先于 a / 并发)和真值一致的有 19964 对(100.0%)
保证因果在前则数字更小,但数字大小不能反推因果,并发事件也被排出了先后。
节点数 N | Lamport(1 个整数) | HLC(l, c) | 向量时钟(N 个整数) ------+----------------+-----------+------------ 3 | 5 字节 | 19 字节 | 21 字节 10 | 5 字节 | 19 字节 | 70 字节 50 | 5 字节 | 19 字节 | 350 字节 200 | 5 字节 | 19 字节 | 1400 字节 Lamport 和 HLC 的大小不随节点数增长,向量时钟线性增长;换来的是向量时钟能精确判定并发
能精确区分先于、后于、并发,代价是每条消息带 N 个计数器。
“发送的 HLC < 接收的 HLC” 被违反的消息数 0;抽样的有因果关系的 9690 对里,HLC 顺序和因果相反的 0 对(同一批 9690 对里,物理时间戳顺序和因果相反或相等的有 80 对) l 与事件发生时本节点物理时钟的差(l - pt):最小 -1 ms,最大 130 ms(注入的偏差之差最大是 130 ms);c 的最大值 10,c > 0 的事件占 55.4% HLC 把“因果”交给逻辑部分、把“离真实时间不远”交给物理部分:时间戳还能当成大致的墙上时间用,偏差也有上界(取决于节点间时钟偏差)
l 追物理时间、c 补序号:因果不违反,时间戳离真实时间的差有上界,消息头不随节点数增长。
LWW 用的时间戳 | 写入对数 | 因果上在后的 v2 被压掉的次数 | 比例 ------------+------+------------------+------ 物理时钟时间戳 | 1000 | 447 | 44.7% HLC 时间戳 | 1000 | 0 | 0.0% Lamport 时间戳 | 1000 | 0 | 0.0% 用物理时钟做 LWW,两个节点时钟差 130 ms:相隔不到 130 ms 的因果写入,后面的会输给前面的(这里相隔 0 到 300 ms 均匀分布,理论上约 130/300 = 43%);HLC 和 Lamport 保证因果在后的时间戳更大
物理时钟做 LWW 会丢掉因果在后的写入;HLC 或 Lamport 不会。