Logical Physical Clocks

https://link.springer.com/chapter/10.1007/978-3-319-14472-6_2

• Hybrid Logical Clockの提案論文
• Lamport Clockと、Physical Timeのハイブリッド! かっこいい(kekeho)
• MongoDB, CockroachDBで使われているらしい

Introduction

• Brief History of Time
  • Logical Clock: Lamport Clock, Vector Clockなど。Lamport Clockは物理的な時間に紐づいていないし、バックチャンネルでの通信は反映できないので実用的でない
    • (とこの論文ではしている。まあケースバイケースでは)(kekeho)
  • [Physical Time]: 物理時間。NTP使っても完全に同期はできないので、Uncertainty intervalsが生じ、その期間が被っているイベントには順序付けができない。秒が飛んだり、巻き戻ったりということも発生する
  • TrueTime: Google Spannerで提案。特別なデバイスが必要である。また、同期がゆるいとイベントの遅延がかさむ。
    • TrueTimeちゃんと勉強してないけど、多分そうなんだろう(kekeho)
  • HybridTime: Vector ClockとPhysical Timeの組み合わせ

HLCのアルゴリズム

• HLC($l$)は以下の特性を提供する
  1. $e\mathsf{hb}f\Rightarrow l.e<l.f$
  2. $l.e$の空間計算量はO(1)
  3. $l.e$は有限のビット幅で表現される
     • 実際はint64(OSのNTPクロックと同じビット幅)
  4. $l.e$は$pt.e$と近い値を取る。$|l.e-pt.e|$が有界 Naive algorithm
• 任意のイベント$e$に対して、$l.e\ge pt.e$なタイムスタンプを与える
• 初期化
  • $l.j:=0$
• 送信イベント or ローカルイベント$f$
  • $l.j:=\max (l.j+1,pt.j)$
  • $l.j$をそのイベントのタイムスタンプとする(メッセージにはそれを付ける)
• 受信イベント of message $m$
  • $l.j:=\max (l.j+1,l.m+1,pt.j)$
  • $l.j$をそのイベントのタイムスタンプとする
• ほぼLamport Clockと一緒(kekeho)
• これで特性1, 2は満たすけど、4は満たされないし、3も満たさない
  • 3を満たさず、どんどんズレが蓄積していく例:
    • HLCアルゴリズム
• naive algorithmの$l.j$を、$l.j$と$c.j$に分割
  • $l.j$はこれまでに学習した$p.t$の最大値を把握するために使うレベル
  • $c.j$は、$l.j$の値が等しいときにのみ因果関係の更新を捉えるために使用される
• 送信・ローカルイベント
  • $l^{\prime }.j:=l.j$
  • $l.j:=max(l^{\prime }j,pt.j)$
  • $$\begin{gathered} \mathsf{If}(l.j=l^{\prime }j)\mathsf{then}c.j:=c.j+1 \\ \mathsf{Else}c.j:=0 \end{gathered}$$
  • イベントのタイムスタンプは$l.j,c.j$
• 受信イベント of message $m$
  • $l^{\prime }j:=l.j$
  • $l.j:=max(l^{\prime }j,l.m,pt.j)$
  • $$\begin{gathered} \mathsf{If}(l.j=l^{\prime }j=l.m)\mathsf{then}c.j:=max(c.j,c.m)+1 \\ \mathsf{Elseif}(l.j=l^{\prime }j)\mathsf{then}c.j:=c.j+1 \\ \mathsf{Elseif}(l.j=l.m)\mathsf{then}c.j:=c.m+1 \\ \mathsf{Else}c.j:=0 \end{gathered}$$
    • イベントのタイムスタンプは$l.j,c.j$
• happend-beforeを見たかったら、$l$を比べて、等しければ$c$を比べろということっぽい(kekeho)
• 要件4を満たすことの証明は論文に書いてある

参考

• https://martinfowler.com/articles/patterns-of-distributed-systems/hybrid-clock.html
• https://muratbuffalo.blogspot.com/2014/07/hybrid-logical-clocks.html