Timestamp as a Service

Timestamp 論理時計 TaaS Logical_Clock

• VLDB 2024

• https://dl.acm.org/doi/10.14778/3641204.3641210

• https://www.vldb.org/pvldb/vol17/p994-li.pdf

• 評価実装

  • https://zenodo.org/records/10467612
  • https://github.com/liyishuai/taas-experiment/tree/v1.0

• Crash-fault torelantなTimestamp Server

  • Centralized timestamping
  • リーダーレスという特徴がある

背景

• 分散DBの分野では、Logical Clockが使われる。
  • Timestamp Oracleが使われているが、単一障害点になりがち
  • Lamport Clock、Vector Clockは使いづらいので、分散DBではあまり使われていない。
  • 既存のCFTなTimestamp Oracleは、PrimaryをRaftで選挙して…みたいなものだったが、選挙中ダウンタイムが長くなってしまって性能が悪化していた
• Linearizableで、Crash-fault torelantな論理時計のアルゴリズムを提案

満たしている性質 $Q_{\sigma }$: セッション$\sigma$のクエリ開始 $A_{\sigma }$: セッション$\sigma$の結果応答 $T_{\sigma }$: セッション$\sigma$のタイムスタンプ

• Timestamp Correctness: $\forall \sigma ,\forall \tau ,(A_{\sigma }\prec Q_{\tau }\Rightarrow T_{\sigma }<T_{\tau })$
  • Timestamp Completenessに近いかな(kekeho)
• Availability: 最小で$\lceil (n+1)/2\rceil$が生きていればOK アルゴリズム解説
• https://emptysqua.re/blog/review-timestamp-as-a-service/
  • 超わかりやすい(kekeho)
  • 論文は、この記事でも触れられている通り謎の記号を使っていて読みづらいンゴ…(kekeho)

メモ

• 全部のサーバーがUpしていれば、コンカレントにリクエスト出せるので、最も遠いサーバーへの1-RTTで時刻取得が完了する