SpannerやCockroachDBが内部で使うTSOを、Rust製の単一バイナリで動かせる「tsoracle」

Strictly monotonic timestamps and gapless sequences in Rust

tsoracleは、分散システム全体でイベントの順序を決める厳密に単調増加なタイムスタンプを発行するtimestamp oracle(TSO)をRustで実装したもの。SpannerやCockroachDB、FoundationDBが内部で使う仕組みを、openraftやOmniPaxosによる合意形成、fsync済みのウィンドウ割り当て、gRPCクライアント付きで単体バイナリとして提供する。さらにget_seq()では、飛びなく連続するgaplessシーケンスも同じ経路で発行できる。

gaplessな前進は消費を取り消せないため、この呼び出しは非冪等であり、曖昧な失敗は黙って再試行されることなくSeqUncertainとして表面化する。
  1. lmz

    「ギャップレスシーケンス」を実際にギャップレスにするには、クライアント/呼び出し元からの非常に強い保証が必要だろう。呼び出し元がシーケンスを進めた後に自身の障害を起こす可能性があるからだ。これは実際に2相コミットを行っているわけではないと思うが?

    編集:シーケンスが不確かな場合は調整すべきだと書いてあるが、クライアント側でそれを行う方法が見当たらないのは私が愚かなだけだろうか?

  2. pnathan

    直感的には、これは高速では不可能だ。これらの特性は障害時には両立しない。

    一方で、直感は時折間違っている。TLA+の証明はあるのか?

  3. hansvm

    何か怪しい。何を見落としているんだ?

    > 引き裂かれた状態がない

    バッチから割り当てを行い、その割り当てを実行したことをfsyncし、アプリケーションがそのカウンタで何もできずに失敗し、それによって構築しようとしている「ギャップレス」シーケンスにギャップが生じる、という障害モードは存在しないのか?ここで公開されているプリミティブ自体はギャップレスにできるかもしれないが、APIは、あなたが強制しようとしているギャップレス特性を持つアプリケーションをうまく構成できるようには見えない。

    アプリケーション状態とtsoracle状態の間のこの非同期は、タイムスタンプのバッチ要求(記載されたパフォーマンス数値を達成するために必要)のような他の機能を考慮すると、より起こりやすく思える。

    > ギャップレス、高スループット、単調

    何だって?どの実装でもこれら3つを同時に得ることはできない。この実装を見ると、(予想通り)ここでも得られていない。基本的にはパーティション分割された割り当て戦略を使用している——各ノードにウィンドウを割り当て、各ノードはそのウィンドウから割り当てる(一見すると、その戦略のかなり良い実装のように思える。けなしているわけではない、少なくともこれ以上読むまでは)。しかし、それはギャップレスかつ単調ではない。ノード間のウィンドウ内同期を強制するものは何もない。ノードが最終的に常にアイドル状態にならなければ、(最終的には)ギャップレス性は得られるが、それは大きな数を割り当てる前に明示的に穴を残し、時にはその穴を小さな数で埋めるからにすぎない[…]

この日のほかの記事

2026-11-15