“混合逻辑时钟用物理来源分量和同值计数器组成二元标签,也只保留因果蕴含标签递增的单向保证。其并发事件d与f可以满足H(d)<H(f),因此二元字典序不能代替本页的逐分量偏序比较;固定数量字段与…”
形式陈述
一个标签包含两种进度
混合逻辑时钟HLC给事件分配二元标签H=(l,c),按字典序比较:先比较l,相等时再比较c。目标沿用逻辑时钟的单向时钟条件:事件a因果先于b,就有H(a)<H(b);同时让l来自已见物理读数的最大值,而不把每次逻辑递增都加到物理分量上。[1, §3.3, Figure5]
本页使用无崩溃、诚实进程的发送/接收/本地事件模型。每个进程初始(l,c)=(0,0),物理钟每次提供非负整数p,允许重复和倒退;c为非负无界整数。发送事件先更新,再把所得完整(l,c)随消息发出。每个进程的状态更新串行化,不能让两线程同时读取同一旧值再发布相同的新标签。
本地或发送事件:令l'=max(l,p)。若l'=l,取c'=c+1;否则c'=0。接收消息(l_m,c_m)时,先用三个旧输入计算l'=max(l,l_m,p),再按下表从上到下选择一个分支:
| 条件 | 新计数c' |
|---|---|
| l'=l=l_m | max(c,c_m)+1 |
| 否则,l'=l | c+1 |
| 否则,l'=l_m | c_m+1 |
| 否则,物理p严格超过两个旧l | 0 |
最后一次性保存(l',c'),并用它标记本事件。第一行不能省略:当两边物理分量相同,必须越过两边计数的最大者;只加本地计数可能没有超过消息时间。
直觉
物理分量不负责数所有事件
一台机器的物理读数停在100时,仍可以发生多个事件。若每次把标签的第一分量加一,会得到101、102、103,逐渐远离物理读数。HLC将它们写为(100,0)、(100,1)、(100,2):l仍记录已知最大物理读数,同值事件的因果进度放到c中。
当真实读到更大的物理值130且它也超过收到消息的l,标签变成(130,0)。计数虽然归零,整个二元标签却变大,因为先比较的第一分量已经严格增加。反过来,物理钟倒退到129时不能把l也退回129;应保持130并增加c。
收到较大的远端l也只改变HLC状态,不修改机器的物理钟。这个分离使应用可以继续读取原钟,同时用HLC保护事件标签的因果顺序。
例子与边界
九个事件覆盖四种接收分支
A、B、C初态全为(0,0)。消息m₀由B发给A,m₁由A发给B,m₂由B发给A,m₃由C发给A。m₀较早发送但很晚才交付,m₂最后又交付一个重传副本;接收事件本身都要标记。
| 事件 | 进程及动作 | 当前物理p | 消息标签 | 更新后H |
|---|---|---|---|---|
| a | A发送m₁ | 100 | 无 | (100,0) |
| b | B发送m₀ | 90 | 无 | (90,0) |
| c | B接收m₁ | 91 | (100,0) | (100,1) |
| d | B发送m₂ | 90 | 无 | (100,2) |
| e | A接收m₂ | 99 | (100,2) | (100,3) |
| f | C发送m₃ | 120 | 无 | (120,0) |
| g | A接收m₃ | 101 | (120,0) | (120,1) |
| h | A接收迟到m₀ | 130 | (90,0) | (130,0) |
| i | A接收m₂的副本 | 129 | (100,2) | (130,1) |
c和g是仅消息l最大;e是双方l同为100,取max(0,2)+1=3;h的物理130严格最大,计数归零;i只有本地l最大,计数加一。B的91退到90、A的100退到99及130退到129都没有使H倒退。
重传m₂并不制造一个新的发送时间戳,但产生新的接收事件i。HLC令d→i,不代表业务操作应重复执行;消息去重、事务提交和副作用仍由相应协议决定。
标签有序,事件仍可并发
在表中,C的事件f与B的事件d没有进程内或消息因果路径,记为d∥f(两事件并发),虽然(100,2)<(120,0)。按这两个标签排序,只是在一份与因果相容的总序中选定先后,不能反推d导致f。
另让两个完全不通信的进程都以p=100产生首事件,两者可同时取得(100,0)。若需要不同事件的唯一排序键,可以追加稳定且不复用的进程身份;同一进程的标签已严格递增,不会自行重复。附加身份只是破并列,不能把并发变成真正的因果。
向量时钟在其固定身份标准模型中能够由逐分量比较反推因果;HLC的二元字典序只能给出前述单向保证。少量字段节省元数据,同时也丢失了精确并发判定的信息。
推论与应用
对生成因果的两类边分别证明
每个本地更新都严格超过本进程旧标签:l增加则第一分量胜出,l不变则c严格增加。接收更新也严格超过消息标签:若新l大于l_m,已由第一分量胜出;若相等,双方相同分支或消息最大分支都会让新c>c_m。
因此每条进程内边和发送—接收边都指向更大的H。字典序严格小于的传递性把这项性质传到任意因果路径,得到a→b蕴含H(a)<H(b)。这个论证不依赖物理钟接近真实时间,所以物理读数回拨并不破坏该安全性质。[1, Theorem1]
接近物理时间需要另一份条件
l始终是当前事件及其因果过去中某次物理读数的最大值,再包括初始零。更新只取最大、不自行增加l,因而这个来源不变量可按事件归纳。要推出数值距离,还需明确物理钟的误差合同。
例如另假设真实时间非负,所有事件处的物理读数p满足距该事件真实时刻t不超过ε。对当前t,其所有因果过去的真实时刻都不大于t,所以历史读数都不大于t+ε;初始零也不超过它。于是
这里ε是“每台钟相对真实时间”的绝对误差界;原文使用的同步偏斜ε口径不同,不应把两个数字直接视为同一参数。[1, Theorem3与Corollary1] 若只知道最近一次四戳探测的区间,却没有覆盖全部事件的误差保证,就不能宣称已经满足这个前提。
若某钟任意跳到很远的未来再退回,HLC可以继续维持因果递增,但l会保留未来值,直到物理读数追上。此时刚才的距离界已经失去前提;不能为了把图画回当前时间而强行清零l。
两个整数不是固定宽度永不溢出
若物理读数无限重复且事件持续发生,c也可无限增长。本页不加入事件产生速率上界,因此不承诺某个固定位数一定够用。定宽实现应在下一次更新溢出时拒绝发布、等待可安全推进的物理值,或采用经过证明的扩展方案;直接对c取模会让同进程标签变小。
例如最大计数为3,在p=100下已有(100,3),再产生事件需要(100,4)。若错误回绕为(100,0),便破坏先后关系。附件的受限字段检查在更新提交之前报错,并保留旧状态;理论主实现则用Python整数。
进程重启清空(l,c)也可能重新发布较小标签。本页排除崩溃;若要跨重启维持同一因果合同,需要将相应状态和应用历史一并可靠恢复,不能只换一个pid便假装第一分量的倒退不存在。原论文的瞬态故障纠正与重新稳定讨论,是另一个带恢复阶段的保证,不等于任意重置后全部旧因果边仍然单调。[1, §4]
输出可复算的事件证书
每次更新只需常数次最大值、比较和加一;每进程保存两个整数、每消息附两个整数。在机器字模型下是O(1)核心工作;任意精度计数则另计位长,不把两个字段说成固定两个字节。保存E个事件的日志为O(E)条记录,核全部因果闭包是测试工作,不是每个事件的运行成本。
在时钟证书终结任务中,输出每个事件旧状态、物理读数、消息标签、选中分支和新状态;用独立消息图验证因果边,并保留并发但标签有序、物理回拨和拒绝溢出的反例。
参考资料
- Sandeep Kulkarni、Murat Demirbas、Deepak Madeppa、Bharadwaj Avva、Marcelo Leone,Logical Physical Clocks and Consistent Snapshots in Globally Distributed Databases,University at Buffalo技术报告2014-04,§3.3、物理第4–6页,Figure5、Theorems1–3与Corollary1;§4、物理第7页的故障恢复界。本页明确采用无界计数与自己的绝对误差2ε推导,不沿用带事件速率假设的有限计数上界。