Skip to content

算法Algorithm

混合逻辑时钟

Hybrid logical clock · HLC

用物理分量和同值计数器生成因果递增标签,逐分支验证接收合并,区分墙钟接近条件、并发排序、倒退与计数溢出。

形式陈述 ​

一个标签包含两种进度 ​

混合逻辑时钟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+ε;初始零也不超过它。于是

p≤l≤t+ε,0≤l−p≤2ε.

这里ε是“每台钟相对真实时间”的绝对误差界;原文使用的同步偏斜ε口径不同,不应把两个数字直接视为同一参数。[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)条记录,核全部因果闭包是测试工作,不是每个事件的运行成本。

在时钟证书终结任务中,输出每个事件旧状态、物理读数、消息标签、选中分支和新状态;用独立消息图验证因果边,并保留并发但标签有序、物理回拨和拒绝溢出的反例。

参考资料
  1. 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ε推导,不沿用带事件速率假设的有限计数上界。
关系图谱6 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系

并列辨析