Spannerはなぜ原子時計が必要だったのか？ (1)

Cloud Spannerはなぜ原子時計 が必要だったのか？ あるいはSpanner Cloneはなぜ不要にできたのか？ 第三回 分散システム集会 on VRChat @bootjp / ぶーと

目次 ● ● ● ● ● ● ● ● ● ● ● 注意事項 自己紹介 Spannerとは 外部一貫性（External Consistency）？ TrueTimeとTrueTimeAPIってなんだ？ Spannerは高精度クロックでなにをしているのか？ Spanner Cloneとは CockroachDBの場合 TiDB(TiKV)の場合 Spanner Cloneが原子時計を不要にできた理由 まとめ

注意事項 発表には万全を期しておりますが、誤りが含まれる可能性があります。 もし、誤りを見つけた場合は ● VRChat会場の方 ○ ○ 進行をとめて質問をしていただく 質疑応答の時間にご指摘いただく ● 配信やアーカイブ、資料をご覧の方 ○ ○ @bootjp宛にメンション or DM いただく 分散システム集会Discordでご報告いただく よりよい集会運営へのご協力のほどよろしくお願いします

• https://twitter.com/bootjp.me
• https://discord.com/invite/xSuxsNxcde

自己紹介 HN: ぶーと 職業: 零細企業の代表 兼 社会人学部生(休学） 分散システム集会の主催の一人。 RaftやKVS、TiKVが好きです。 仕事でRaftベースの分散ストレージ作っていま す。 @bootjp @v_bootjp 今回の発表で出てくるいくつかの製品、社名と は関係ありません。 技術書典16で「Goで作って理解するRaftベー スRedis互換KVS」を頒布します。

最初はこのアカウントしかなかったんだけど 自己紹介 最初はこのアカウントしかなかったんだけど VRChatがらみのツイートたくさんしてたと VRChatがらみのツイートたくさんしてた時に、 き、 フォローしてくれてた研究者さんからフォロー フォローしてくれてた研究者さんからフォ HN: ぶーと 外されちゃって、 ロー外されちゃって悲しみにくれて生まれた 悲しみにくれて生まれたのが右のアカウント のが右のアカウント 職業: 零細企業の代表 兼 社会人学部生(休学） 分散システム集会の主催の一人。 RaftやKVS、TiKVが好きです。 仕事でRaftベースの分散ストレージ作っていま す。 @bootjp そうして生まれたのが 俺ってわけ @v_bootjp よかったらみてね！ 今回の発表で出てくるいくつかの製品、社名と は関係ありません。 技術書典16で「Goで作って理解するRaftベー スRedis互換KVS」を頒布します。

Spannerとは ● Googleが開発した大規模分散データベースシステム ○ ○ 2012年にOSDI論文で発表 Googleのグローバルなサービスのバックエンドとして活用 ● 高いスケーラビリティと強い整合性を両立 ○ ○ シャーディングによる水平スケーリング 外部一貫性（External Consistency）の保証 ● 高い可用性と耐障害性 ○ Paxosアルゴリズムによる複製管理 ● TrueTimeAPIと原子時計 ○ 高精度なタイムスタンプの生成

Spannerとは ● Googleが開発した大規模分散データベースシステム ○ ○ 2012年にOSDI論文で発表 Googleのグローバルなサービスのバックエンドとして活用 ● スケーラビリティと強い整合性を両立 ○ ○ シャーディングによる水平スケーリング 外部一貫性（External Consistency）の保証 ● 高い可用性と耐障害性 ○ Paxosアルゴリズムによる複製管理 ● TrueTimeAPIと原子時計 ○ 高精度なタイムスタンプの生成 ● Paxosによる一貫性 https://cloud.google.com/spanner?hl=ja

• https://cloud.google.com/spanner?hl=ja

Spannerとは ● Googleが開発した大規模分散データベースシステム ○ ○ 2012年にOSDI論文で発表 Googleのグローバルなサービスのバックエンドとして活用 ● スケーラビリティと強い整合性を両立 ○ ○ シャーディングによる水平スケーリング 外部一貫性（External Consistency）の保証 ● 高い可用性と耐障害性 ○ Paxosアルゴリズムによる複製管理 ● TrueTimeAPIと原子時計 ○ 高精度なタイムスタンプの生成 ● Paxosによる一貫性 https://cloud.google.com/spanner?hl=ja

• https://cloud.google.com/spanner?hl=ja

Spannerとは ● Googleが開発した大規模分散データベースシステム ○ ○ 2012年にOSDI論文で発表 Googleのグローバルなサービスのバックエンドとして活用 ● スケーラビリティと強い整合性を両立 ○ ○ シャーディングによる水平スケーリング 外部一貫性（External Consistency）の保証 ● 高い可用性と耐障害性 ○ Paxosアルゴリズムによる複製管理 ● TrueTimeAPIと原子時計 ○ 高精度なタイムスタンプの生成 ● Paxosによる一貫性

外部一貫性（External Consistency）? ● 一貫性モデルの一つ ● 全てのクライアントがトランザクションの結果を同じ順序で観測でき ることを保証する ● “あるトランザクションが終わった後にはじまったトランザクション は、より必ず大きいタイムスタンプを得る 引用元 Spanner #ポエム -" Qiita” ● 信頼できるタイムスタンプの中で ○ ○ ○ ● 「あるトランザクションが終わった後にはじまったトランザクションは、 より必ず大きいタイムスタンプを得る」 「自分よりタイムスタンプが小さいトランザクションの操作結果は読み取 ることができる」 「自分より大きなタイムスタンプのトランザクションは観測することがで きない」

• https://qiita.com/kumagi/items/7dbb0e2a76484f6c522b

引用元:https://jepsen.io/consistency 外部一貫性（External Consistency）? ● 一貫性モデルの一つ ● 全てのクライアントがトランザクションの結果を同じ順序で観測でき ることを保証する ● “あるトランザクションが終わった後にはじまったトランザクション は、より必ず大きいタイムスタンプを得る 引用元 Spanner #ポエム -" Qiita” ● 信頼できるタイムスタンプの中で ○ ○ ○ ● 「あるトランザクションが終わった後にはじまったトランザクションは、 より必ず大きいタイムスタンプを得る」 「自分よりタイムスタンプが小さいトランザクションの操作結果は読み取 ることができる」 「自分より大きなタイムスタンプのトランザクションは観測することがで きない」

• https://qiita.com/kumagi/items/7dbb0e2a76484f6c522b

外部一貫性（External Consistency）? ● 時刻は分散システムではとても難しい ● ある時間 t1 がノードAとノードBで同じ時間を指すとは限らない ○ これはコンピュータのクロックが正確ではないことに起因する ■ ■ ■ ○ ○ 時刻がドリフトしていく... クラッシュしたノードが復帰したり... 半分くらい壊れていて中途半端に動いていたり... NTPの場合で100~250msほどずれる（後述） じゃあ、時刻を合意取ればいいじゃん？ ■ ■ スループットがでない TiDBとかはTimeStamp Oracleで.....（後述）

Spannerとは ● Googleが開発した大規模分散データベースシステム ○ ○ 2012年にOSDI論文で発表 Googleのグローバルなサービスのバックエンドとして活用 ● スケーラビリティと強い整合性を両立 ○ ○ ○ シャーディングによる水平スケーリング 複数のデータセンターにまたがる同期レプリケーショ 外部一貫性（External Consistency）の保証 ● 高い可用性と耐障害性 ○ ○ Paxosアルゴリズムによる複製管理 自動フェイルオーバーとデータ復旧 ● TrueTimeAPIと原子時計 ○ 高精度なタイムスタンプの生成

TrueTimeとTrueTimeAPIってなんだ？ ● TrueTime ○ 原子時計とGPSをソースにしている ■ ○ ○ 二系統つかっている理由は故障対策 各データセンター二原子時計がある マスターマシンと各ノードにあるスレーブデーモンがある ● TrueTimeAPIが提供しているもの ○ ○ 規定値を超える時刻のズレがあるノードを排除 ノード間で時刻のオフセットの最小値と最大値がわかる ■ ○ ○ 通常は10ms トランザクション時に最も遅れているノードのオフセットがわかる 最大のオフセットがわかるということは、それだけそのトランザクション がの観測がおくれればよい！ これは「Commit Wait」 って言われているよ

• https://static.googleusercontent.com/media/research.google.com/ja//archive/spanner-osdi2012.pdf#page=2.66

TrueTimeとTrueTimeAPIってなんだ？ ●

Spannerは高精度クロックでなにをしているのか？ ● 原子時計を用いても時刻のずれは起きる ● ではなぜ高精度クロックを使っているのか？ ● 例えばノード間の最大のオフセットを1時間にしてみる ○ トランザクションの値が1時間後にならないと読めない ■ これでは現代のデータベースとして使い物にならない ● 高精度クロックはパフォーマンスのため ○ ○ トランザクション一つ一つのレイテンシー 並列トランザクションのスループット ● 理論上は高精度クロックは必須ではない ○ ○ ノード間の最大のオフセットがわかりその分を待機すること 規定値を超える時刻のずれのあるノードの排除する

Spanner Cloneとは ● 理論上は高精度クロックは必須ではない ○ ○ ノード間の最大のオフセットがわかりその分を待機すること 規定値を超える時刻のずれのあるノードの排除する そこで Spanner Cloneの登場

Spanner Cloneとは ● Spanner論文を元に実装されたソースコードが公開されたデータベース ○ ○ ○ CockroachDB TiDB(TiKV) YugaByteDB ● 原子時計を使わない時刻同期手法の採用 ○ ○ NTPを用いた時刻同期 現実的な時計精度での動作 ● 時計誤差を考慮したアルゴリズムの工夫 ○ ○ トランザクションのタイムスタンプ管理 最新の研究ではNTPでも1msほどの誤差にできるらしい

• https://www.usenix.org/system/files/conference/nsdi18/nsdi18-geng.pdf

Spanner Cloneとは ものによっては オープンソースソフトウェアライセンス ではないものもあるよ！ ● Spanner論文を元に実装されたソースコードが公開されたデータベース ○ ○ ○ CockroachDB TiDB(TiKV) YugaByteDB ● 原子時計を使わない時刻同期手法の採用 ○ ○ NTPを用いた時刻同期 現実的な時計精度での動作 ● 時計誤差を考慮したアルゴリズムの工夫 ○ ○ トランザクションのタイムスタンプ管理 最新の研究ではNTPでも1msほどの誤差にできるらしい 今度 読みま す

• https://www.usenix.org/system/files/conference/nsdi18/nsdi18-geng.pdf

CockroachDBの場合 ● Spannerとは違いNTPを用いる ○ ○ （より正確には NTPと論理クロックの混合） これはノード間の時刻の揺らぎが100~250msほどになる ● Spannerとは違いREAD時に待機することがある ○ ○ 複数ノードにまたがるトランザクション中競合するデータがあるとき commit timestamp + maximum clock offset ■ ○ “トランザクションが暫定コミット タイムスタンプよりも低いタイムス タンプの値を検出した場合、読み取り中にその値を監視し、書き込み中に 高い方のタイムスタンプの値を上書きします”引用元: ■ ■ ○ （bootjp注:どうやって競合を検知しているのかはまだわかっていない...） （トランザクション開始前にpre commit したTimestampをみてるのかな？） https://www.cockroachlabs.com/blog/living-without-atomic-clocks/ つまり最悪の場合で 250msが乗る

• https://www.cockroachlabs.com/glossary/distributed-db/hybrid-logical-clock-hlc-timestamps/
• https://www.cockroachlabs.com/blog/living-without-atomic-clocks/

TiDB(TiKV)の場合 ● Percolator論文をさらに最適化した Optimized Parcolator ● Placement Driver(PD)というコンポーネントがある ● Timestamp Oracle を用いた外部一貫性 ○ ○ ○ PDでetcd（のRaft）による合意された値 ■ 増加しか許さない一貫したtimestamp（後述） ● => 巻き戻ることが無い トランザクション時にPDに問い合わせをしTimestampを払い出してもらう この時刻をベースにイベントを順序付けをしている

• https://tikv.org/deep-dive/distributed-transaction/optimized-percolator/

TiDBの場合 ● TiDB ○ Percolator論文をさらに最適化したTimestamp Oracle ■ etcd（のRaft）による合意された値 https://docs.pingcap.com/tidb/stable/tso

• https://docs.pingcap.com/tidb/stable/tso

Spanner Cloneが原子時計を不要とできた理由 ● Spanner論文のTrueTimeの肝には原子時計は必須ではない a. b. c. もっとも時刻がおくれているノードのオフセットがわかること Commit Wait で(a)の分だけ待機すること 規定値以上時刻がおくれたノードを排除すること

Spanner Cloneが原子時計を不要とできた理由 ● Spanner論文のTrueTimeの肝には原子時計は必須ではない a. b. c. もっとも時刻がおくれているノードのオフセットがわかること Commit Wait で(a)の分だけ待機すること 規定値以上時刻がおくれたノードを排除すること 最もタイムスタンプが小 さいノードと大きいノー ドのオフセットを出す よ。 この区間はどこかで書き 込みをしても、不確実な 時間になるよ 最も遅いノードのオフセットに合わせ てあげることで、都度時刻を合意しな くても一貫性を維持するよ あまりにずれているノードがいると、 その分待機するため パフォーマンス上問題になるのでキッ クするよ

まとめ ● Spannerは最も遅いノードのオフセット分トランザクションが読めない ● CockroachDBは読み取り時に、競合を検知するとオフセット分待機する ことがある ● TiDBはPercolator論文を最適化したTimestamp Oracleを用いている

出典 ● Spanner: Google’s Globally-Distributed Database ○ ● Spanner #ポエム - Qiita ○ ● ● https://www.cockroachlabs.com/blog/living-without-atomic-clocks/ TiKV | Optimized Percolator ○ ● https://qiita.com/kumagi/items/7dbb0e2a76484f6c522b Living without atomic clocks: Where CockroachDB and Spanner diverge ○ ● https://static.googleusercontent.com/media/research.google.com/ja//arch ive/spanner-osdi2012.pdf https://tikv.org/deep-dive/distributed-transaction/optimized-percolator / TimeStamp Oracle (TSO) in TiDB ○ https://docs.pingcap.com/tidb/stable/tso Hybrid Logical Clock (HLC) Timestamp ○ https://www.cockroachlabs.com/glossary/distributed-db/hybrid-logical-cl ock-hlc-timestamps/

• https://static.googleusercontent.com/media/research.google.com/ja//archive/spanner-osdi2012.pdf
• https://qiita.com/kumagi/items/7dbb0e2a76484f6c522b
• https://www.cockroachlabs.com/blog/living-without-atomic-clocks/
• https://tikv.org/deep-dive/distributed-transaction/optimized-percolator/
• https://docs.pingcap.com/tidb/stable/tso
• https://www.cockroachlabs.com/glossary/distributed-db/hybrid-logical-clock-hlc-timestamps/

質疑応答