この記事は hacomono advent calendar 2024 の18日目の記事です
今年9月にhacomonoにJOINし、基盤本部というところで今後のhacomonoのアーキテクチャ設計をしている @bootjp と申します。分散システムが好きです。
hacomonoも昨今のWebサービスの例にもれず、分散システム化しています。
そしてより高い可用性と低い運用コストを目指して新たなアーキテクチャの検討をしています。
今回はその取り組みのなかで、分散システムに関わる難しさというテーマで一貫した時刻の取り扱いの話で記事を書きます。
はじめに
昨今のWebをはじめとしたサービスは一つのサーバーで完結することが少なくなりました。
一つのアプリケーションを複数のサーバーやコンテナで、そして異なるサービスのシステムを組み合わせて「分散システム」として構築されています。
それは可用性や負荷分散、スケールアウトあるいは組織の開発効率のために避けられない構成であることが多いです。
分散システムでは単一のサーバーを用いていたときと異なり、いくつかの難しさがあります。
例えば、クラッシュリカバリーの検知や可観測性、データの一貫性などがあります。
今回は時刻というテーマで分散システムにおける一貫した時刻の取り扱いの難しさと、Spanner、TiDB、CockroachDBがどのようにこの課題を克服したかを解説していきます。
今すぐに役立つような知識ではないものの、あなたがこれから分散システムを設計しなければならないときであったり、分散データベースの仕組みに興味があれば読んで損にはならないでしょう。
分散システムにおける「一貫した時刻」の取り扱いの難しさ
分散システムに限らず、なんらかのイベント発生時に時刻を付与し、あとから時刻でソートを行うというのはよくある手法です。
例えば、WebサイトのアクセスログやSaaSの監査ログ、ログETL、IoTデバイスからのセンサーデータなどではこのような仕組みを取ることが多くあります。
IoTデバイスからデータを受け取り時刻を付与するようなケースを考えてみましょう。
単一サーバーでは一貫して時刻を付与することが可能です。
---
title: シンプルな単一サーバー構成
---
graph LR
IoT1[IoTデバイス1]
IoT2[IoTデバイス2]
IoT3[IoTデバイス3]
Node[時刻を付与するサーバー]
IoT1 -->|イベント送信| Node
IoT2 -->|イベント送信| Node
IoT3 -->|イベント送信| Node
%% Node --> Queue
style IoT1 fill:#f9f,stroke:#333
style IoT2 fill:#f9f,stroke:#333
style IoT3 fill:#f9f,stroke:#333
style Node fill:#bbf,stroke:#333
%% style Queue fill:#bfb,stroke:#333
しかし、 時刻を付与するサーバー が単一であると可用性や負荷分散の点で懸念があります。
ロードバランサー(LB)を用いて冗長化を行いましょう。
---
title: ロードバランサー(LB)を用いて冗長化を行う
---
graph LR
IoT1[IoTデバイス1]
IoT2[IoTデバイス2]
IoT3[IoTデバイス3]
LB[LB]
Node1[時刻を付与するサーバーA]
Node2[時刻を付与するサーバーB]
Node3[時刻を付与するサーバーC]
%% Queue[Queue]
IoT1 -->|イベント送信| LB
IoT2 -->|イベント送信| LB
IoT3 -->|イベント送信| LB
LB --> Node1
LB --> Node2
LB --> Node3
%% Node1 --> Queue
%% Node2 --> Queue
%% Node3 --> Queue
style IoT1 fill:#f9f,stroke:#333
style IoT2 fill:#f9f,stroke:#333
style IoT3 fill:#f9f,stroke:#333
style LB fill:#ff9,stroke:#333
style Node1 fill:#bbf,stroke:#333
style Node2 fill:#bbf,stroke:#333
style Node3 fill:#bbf,stroke:#333
%% style Queue fill:#bfb,stroke:#333
イベントを処理するサーバーが複数台構成になりました。
冗長構成となり、さらなる負荷分散が必要になったときは簡単にオートスケールできそうです。
しかし、複数台構成になることで２つの観点について考慮が必要になります。
時刻を付与するサーバー[A-C]は全くの時刻のズレがなく同じ時刻を指しますか？- ノード間の時刻のズレが問題となる
- 全ノードの時刻が正しいとして、IoTデバイスから送られたデータは正しい順番通りに時刻が付与されますか？
- 通信の遅延や処理の遅延が問題となる
分散システムではノード間のクロックのズレと、通信や処理の遅延により時刻や順番を扱うことが非常に難しくなります。
ですが、GoogleのSpannerやTiDB、CockroachDBなどのデータベースは分散環境でも一貫性を失うことはなく、「先に書き込んだ値が必ず読み出せ、すでに書き換わった古いデータを読み出さない」ことを保証しています。
また、Amazon SQSのFIFOモードもFirst In First Outが保証されています。
この仕組みを実現する技術を本記事で掘り下げていきたいと思います。
💡Tips: イベント順序が重要ではないシステムの場合、ここまで考慮する必要はありません。
しかし、分散データベースでは分散環境であってもパフォーマンスを落とさずに一貫した時刻を元にイベント順序も適切に管理することができます。
この記事では分散データベースを例に、一貫した時刻を用いて厳密にイベント管理するためにはどのような方法があるのかを解説します。
💡Tips: 単調増加（インクリメントされていく）するIDがあればよいのでは？
単調増加する値を元にイベントを並び替えを行えば解決できるように思えるでしょう。
実際にそれに誤りはありません。しかし厳密な単調増加をする値は集中管理もしくは、都度合意を行う必要があります。
集中管理では分散データベース利点が失われ、都度の合意ではパフォーマンス上のボトルネックとなります。
順序関係が非常に大事だけど、そこまでのパフォーマンスが求められない用途では単調増加する値でよいでしょう。
Google SpannerとTrueTime APIを例とした「物理タイムスタンプ」の利用
Googleが開発したSpannerと呼ばれるグローバルに分散したデータベースがあります。
これは結果整合性のデータベースではなく、強整合性なデータベースです。
つまり、「先に書き込んだ値が必ず読み出せ、すでに書き換わった古いデータを読み出さない」ことが保証されています。
例えば、データベースのスケールアウトではMySQLやPostgreSQLを用いたレプリケーションを利用することがあると思います。
しかし、このようなレプリケーションではレプリカからデータを参照する際に、「すでに書き換わってしまった古いデータ」を読み出してしまうおそれがあります。
これは非同期でレプリケーションをしており、レプリケーションの反映が遅延していることに起因します。
💡Tips: 同期的にデータデータ書けば解決？
同期的なレプリケーションによって、すべての書き込みはコミット前に必要なレプリカへ適用され、これにより"すでに書き換わっているはずの値を古いまま読む"といった問題は軽減されます。しかし、これは必ずしも『時刻のズレ』によって生じる不整合を完全になくすわけではありません。
なぜなら、同期的なレプリケーションはあくまで『各レプリカ間の更新タイミングを揃える』ことで整合性を維持する手法であり、『各ノードで使われる時刻（タイムスタンプ）そのものの整合性』を保証するものではないからです。
各ノードが独立してローカルクロックを持ち、それぞれが異なる時刻を示していれば、MVCCなどのバージョニング手法が『いつの時点のデータを読むべきか』を判断する際に、時刻ズレによる誤認が起きる可能性は残ります。
Spannerでは同期的に他のノードにも書き込むことと、TrueTime（後述）とTrueTime API（後述）のグローバルに一貫した時刻を用いて、データベースのイベント順序を壊さないことを実現することで、強整合性を実現しています。
💡Tips: 分散合意にはPaxosが用いられています。
この記事では一貫した時刻を用いて順序付けを壊さない手法について解説していこうと思います。
Spannerでのノード間の時刻のズレへのアプローチ
Spannerと聞くと原子時計が思い浮かぶ方がいらっしゃるかもしれません。
Spannerに原子時計が使われているのは事実で、Googleもそのように記載しています。
TrueTime を機能させるには、Google のデータセンターに特別なハードウェア（原子時計）を組み込む必要がありました。これにより、他のプロトコル（NTP など）よりも非常に高い時間精度と正確性を実現しています。https://cloud.google.com/spanner/docs/whitepapers/life-of-reads-and-writes?hl=ja
原子時計と聞くとソフトウェア開発者が手が出せない領域での問題解決であるかのように見えると思います。
しかし、実際にはSpannerやTrueTime API（後述）の仕組みには原子時計は必須ではありません。
TrueTime
TrueTimeとは高精度な時刻ソースを用いた時刻データです。
Spannerでは原子時計+GPSによる冗長化がなされています。
TrueTime API
Spanner: Google’s Globally-Distributed Database page 5
https://static.googleusercontent.com/media/research.google.com/ja//archive/spanner-osdi2012.pdf
分散システムにおいて、一貫した時刻を提供することが困難であることはノード間の時刻にズレに起因します。
TrueTime APIとは高精度な時刻ソースを用いて、ノード間での時刻のズレを明らかにします。
言い換えると今存在しているノードの中で最も時刻が早いノードと、遅いノードの信頼できない時刻の区間が明らかにされています。
ノード間の時刻のズレの最大値がわかっていれば、書き込みを観測可能にするまでその分だけ待機することで時刻による不整合を防げます。Spannerではこの技術をCommit Waitと呼んでいます。
💡Tips: データベースにはMVCC（Multiversion Concurrency Control）という技術があります。
これはトランザクションの複数のデータバージョンを同時に保持し、更新中のトランザクションが他の読み取り処理をブロックしないようにする仕組みです。
これにより、読取は過去の安定した状態を参照でき、更新は独立して進行可能になります。
ここではデータベースはトランザクション開始時刻（またはコミット時刻）を元に最新の適用可能なデータを返すと考えてください。
---
title: TrueTimeAPIとCommit がないケース
---
sequenceDiagram
participant Client as Client
participant NodeA as Node A (1ms先行)
participant NodeB as Node B (1ms遅延)
opt RealClock: 13:00:000
Note over NodeB: NodeB Local: 12:59:999
Note over NodeA: NodeA Local: 13:00:001
Client -->> NodeA: Xに「val=100」と書き込み要求
Note right of NodeA: Node Aは13:00:001に書き込みが発生と認識
NodeA ->> NodeB: X = 100 (ts=13:00:001 by Node A's clock)
NodeA ->> Client: X は 13:00:001 以降のバージョンで読めるよ
end
opt RealClock: 13:00:001
Note over NodeB: NodeB Local: 13:00:000
Client -->> NodeB: 13:00:001 以降のXを読み込む要求
NodeB ->> Client: X = null だとレスポンス
end
---
title: TrueTimeとCommit Waitを用いるケース
---
sequenceDiagram
participant Client as Client
participant NodeA as Node A (+1ms先行)
participant NodeB as Node B (-1ms遅延)
opt RealClock: 13:00:000 (TrueTime: 13:00:000 ±1ms)
Note over NodeB: NodeB Local: 12:59:999
Note over NodeA: NodeA Local: 13:00:001
Client -->> NodeA: Xに「val=100」と書き込み要求
Note right of NodeA: Node AはTrueTimeAPIでTS取得
Note right of NodeA: TS = 13:00:000 ±1ms
NodeA ->> NodeA: Commit Wait開始 (2ms待機)
end
opt RealClock: 13:00:002
NodeA ->> NodeB: X = 100 (確定状態で反映)
Note over NodeA: Commit Wait終了この時点で全レプリカ間で書き込み確定が因果的に保証可能
NodeA ->> Client: X は 13:00:002 以降のバージョンで読めるよ
end
opt RealClock: 13:00:003
Note over NodeB: NodeB Local: 13:00:002
Client -->> NodeB: 「13:00:001以降のXを読みたい」
Note right of NodeB: NodeBはCommit Wait完了により<br>安全にX=100を返せる
NodeB ->> Client: X = 100
end
また、TrueTimeAPIの重要な役割として、時刻のズレが一定以上になったノードを排除する役割も担っています。
この時刻のズレが一定以上になったノードを排除するのは後ほどのなぜ原子時計が必要だったのかとも関わってくるため、少し覚えておいてください。
Spannerはなぜ原子時計+GPSなのか
ではSpannerはなぜ原子時計とGPSを利用しているのでしょうか。
これを考えるのにあたってキーとなるのは、先ほどの「ノード間の時刻のズレの最大値がわかっていれば、書き込みを観測可能にするまでその分だけ待機」という部分です。
例えば、最大1時間ずれたノードがあると仮定すると、書き込みは観測可能になるまでに1時間待機する必要があります。
言い換えると1つのトランザクションに1時間かかるということになり、そのようなパフォーマンスのデータベースは現代の高頻度に書き換えが起こるアプリケーションでは到底利用できないでしょう。
1時間という値は大げさですが、このゆらぎを小さくするために原子時計とGPSが用いられています。
また、先ほどTrueTimeAPIには一定以上の時刻のズレがあるノードを排除する仕組みがあると言いました。
この高精度クロックと一定以上のズレがあるノードを排除する仕組みでSpannerは一貫性と高パフォーマンスを実現しています。
ちなみにSpannerは原子時計とGPSを用いることで、このノード間の時刻のゆらぎを1~7msにすることができ、ほとんどの場合は4msの待機で済むようです。
In our production environ-ment, ε is typically a sawtooth function of time, varying from about 1 to 7 ms over each poll interval. ε is there- fore 4 ms most of the time
引用元: Spanner: Google’s Globally-Distributed Database page 5
https://static.googleusercontent.com/media/research.google.com/ja//archive/spanner-osdi2012.pdf
TiDBのTimestamp Oracle (TSO) とPercolator論文
Spannerの論文を元にしたNewSQLという種類に分類されるデータベースがあります。
TiDBではSpannerと違い、原子時計を必須としていません。
Spannerでは高いパフォーマンスのために原子時計を用いていたはずです。
しかしTiDBはどのようにして高いパフォーマンスを原子時計を用いずに実現したのでしょうか。
その秘密はTiDBを構成するコンポーネントである PlacementDriver(PD)が提供するTimestamp Oracleにあります。
💡Tips: TiDBのTimestamp OracleはGoogleによる論文「Large-scale Incremental Processing Using Distributed Transactions and Notifications 」に基づいています。
https://research.google/pubs/large-scale-incremental-processing-using-distributed-transactions-and-notifications/
https://www.usenix.org/legacy/event/osdi10/tech/full_papers/Peng.pdf
PlacementDriver（PD）
引用元: オープンソースの分散型NewSQLデータベースによるタイムサービス配信の仕組み
https://pingcap.co.jp/blog/how-an-open-source-distributed-newsql-database-delivers-time-services/
PlacementDriver（PD）はTiDBを構成する一つのコンポーネントです。
これはetcdを内部に組み込んでおり、Raftによるリーダー選出やデータレプリケーションを行います。
ここでは複数のサーバーで構成されたPDというものがあり、そのうちひとつのノードがリーダーを担っているというふうに理解していただければ大丈夫です。
💡Tips: Raft Consensus Algorithmについて
Raftについてはここでは詳しく触れませんが、これも分散システムにおける一貫性、分断耐性とクラッシュリカバリー時の安全性を担保するための仕組みです。
手前味噌となり恐縮ですが、Raftについても解説している資料がありますので、もし興味があればこちらの資料をご覧くださいhttps://speakerdeck.com/bootjp/what-is-raft-strengths-and-weaknesses-based-on-its-mechanism
Raftとは？ 仕組みから考える得意なこと苦手なこと/What is Raft? Strengths and Weaknesses Based on Its Mechanism
Timestamp Oracleとは？
Timestamp OracleはPlacementDriver(PD)により提供される時刻のデータです。
TiDBではこの時刻を用いることで命令の順序関係を管理しています。
Timestamp Oracleの内部は物理タイムスタンプと論理タイムスタンプをあわせたハイブリッドクロックとなっています。
物理タイムスタンプ部はUNIX タイムスタンプを想像してもらうと良いでしょう。
ハイブリッドクロックはインクリメントされていく数値を想像してもらうとわかりやすいです。
引用元: TiDB のタイムスタンプ Oracle (TSO)
https://docs.pingcap.com/ja/tidb/stable/tso
前半の物理タイムスタンプはPlacementDriverのリーダーの時刻から+3秒までをetcdにデータを保存し、全ノードで巻き戻ることのない時刻を扱います。
時刻の校正を終了した後、新しいPDリーダーはTSOサービスの配信を開始します。現PDリーダーがダウンした後、次に選出されたPDリーダーが時刻の校正が正常に行えるように、現PDリーダーは時間サービスを配信した後、毎回Tlastをetcdに格納する必要があります。しかし、PDリーダーが毎回そうしていたら、PDのパフォーマンスが大きく損なわれてしまいます。そこで、そのような問題を避けるために、PDリーダーは割り当て可能な時間枠Txをあらかじめ設定しておきます。その初期値は3秒です。
https://pingcap.co.jp/blog/how-an-open-source-distributed-newsql-database-delivers-time-services/
そして、後半のロジカルクロック部は現在のリーダーノードがメモリ上の操作でアトミックにインクリメントします。
このような構成を取ることで高いパフォーマンスで決して戻ることのない単調増加する時刻を実現しています。
Timestamp Oracleの欠点
PDを用いたTimestamp Oracleは非常にうまく原子時計を不要としています。
しかし、PDのリーダーノードがクラッシュした場合に新たなリーダーが選出されるまでの間時刻を発行することができません。
これはデータベースで言い換えると「新たなリーダーが選出されるまでの間トランザクションを行うことができない」といえます。
しかし、PDのリーダーノードがクラッシュすることは稀です。
また、計画的なメンテナンスの入れ替えであれば安全にリーダーを交代できるため、信頼性の高いパブリッククラウド上のインスタンスでは現実的に動作するアーキテクチャとなっています。
CockroachDBにおける「読む際の待機」戦略
CockroachDBもTiDBと同じくリアルクロックと論理タイムスタンプを用います。
ノード間の時刻の同期にはNTPを用いますが、この場合ノード間の時刻のゆらぎが100ms ~ 250msほどになると述べられています。
Synchronization hardware helps minimize the upper bound. In Spanner’s case, Google mentions an upper bound of 7ms. That’s pretty tight; by contrast, using NTP for clock synchronization is likely to give somewhere between 100ms and 250ms.
https://www.cockroachlabs.com/blog/living-without-atomic-clocks/
CockroachDBではSpannerが書き込み時に待機するのとは対称的に、読み込み時に待機する可能性があります。
考え方はSpannerと同じで、ノード間のゆらぎがある時間に書き込みが発生したことを検知したらゆらぎ分の時間読み出しを待機するという仕組みになっています。
CockroachDBの読み出し時待機の欠点
CockroachDBの読み出し時待機の最大の欠点は、NTPによる時刻同期の精度が低いため、最大250msもの待機が必要になる可能性があることです。
これは、Spannerの4msと比較すると非常に長い待機時間となり、読み取り性能に大きな影響を与える可能性があります。
各アプローチのトレードオフとまとめ
TrueTime API (Spanner)
- 現実の時刻でイベントの順序付けを行う
- ノード間の時刻のズレの最大値を算出し、その分の書き込みを待機する
- 原子時計とGPSを用いて高精度な時刻同期を実現することで、書き込み待機に時間を最小化する
- 通常は4msほどの書き込み待機がある
Timestamp Oracle (TiDB)
- リアル時刻と単調増加する論理タイムスタンプを用いてイベントの順序付けを行う
- 前半46ビットの物理タイムスタンプ
- 後半18ビットの論理タイムスタンプ
- リアル時刻の部分は過去のPDのリーダーが書き込んだ最大値になるため、正確な値ではない
- PDのリーダーノードがクラッシュした場合、次のリーダーが選出されるまで時刻が取得できない
TrueTimeAPI like な読み込み待機(CockroachDB)
- リアル時刻とロジカルクロックを組み合わせてイベントの順序付けを行う
- NTPによる時刻同期を用いるため、ノード間で100ms～250msのゆらぎが発生する
- 読み取り時に、読み取り対象のデータへの書き込みがあった場合、読み込み時に待機が必要となる
まとめ
分散システムにおいてナイーブに時刻を扱うと、ノード間の時刻のズレによって一貫性が壊れる可能性があります。これは分散システムにおける重要な課題の一つです。
この課題に対して、GoogleのSpannerはTrueTimeAPIによる信頼できない時間幅を明確にし、その分の観測を待機するという手法で解決しました。
TiDBはTimestamp Oracleによる中央集権的な時刻の発行と、ハイブリッドクロックにより単調増加する時刻とそのパフォーマンスの問題を解決しました。
CockroachDBは読み込み時の待機戦略を取り、非中央集権で一貫性を実現しました。
これらの事例から分かるように、適切な設計と実装を行うことで、分散システムでも順序付けられたイベントを安全に扱うことが可能です。
仲間を募集しています
株式会社hacomonoでは一緒に働く仲間を募集しています。
私たちは、技術の背景と仕組みを深く理解し、そのトレードオフを見極めながら、ビジネスニーズに合わせた適切な実装ができるエンジニアを探しています。
