Timestamp Oracle

• Logical Clockの一種。Centralizedなタイムスタンプサービス
• インクリメンタルなタイムスタンプ(クロック値)を提供するサーバー
• 単一のサーバーの場合もあれば、レプリケーションされている場合もある
  • 何らかのConsensus algorithmでクロック値をレプリケーションする方法が主流
    • TiDBではTimestamp Oracle をRaftでレプリケーションしている
    • PolarDB-Xでは、Paxosを使ってレプリケーションしている
  • Timestamp as a Serviceではコンセンサスプロトコルを使わない。リーダーレスなアプローチが提案されている。
• Percolator Transaction Modelでよく使われる

Correctness

• TSOは以下のCorrectnessを提供する (セッション$\sigma$は、時刻$Q_{\sigma }$に開始し、$A_{\sigma }$に終了する) $\forall \sigma ,\tau \in \text{Sessions}:A_{\sigma }\prec Q_{\tau }⟹T(\sigma )<T(\tau )$

うれしさ

• 一般的な論理クロックでは、プロセス間でメッセージを伝播することで因果関係を伝えていかないといけないが…TSOであれば、クロックサーバーと通信するだけで一貫したクロック値を得られる。例えばプロセス数が数百個とか数千個だと、ありがたそう
• Real-time Orderがあると言えそう
  • 参考?

参考

• https://tikv.org/deep-dive/distributed-transaction/timestamp-oracle/