FoundationDBの仕組みと、その理由

jaCreated: 2025/4/29Updated: 2025/6/22

FoundationDBの動作原理とその優れた設計選択について詳細に解説します。設計の核心部分、失敗時のリカバリー、驚くべき主張の真相を掘り下げます。

FoundationDBの仕組みと、その理由

FoundationDBは非常に優れたデータベースです。その論文はSIGMOD’21のベスト産業論文賞を受賞しました。本記事では、FDBがどのように動作するのかを詳細に説明し、彼らが取った興味深い設計選択について考察します。論文には含まれていない多くの詳細や(ときには正しさの証明すら)必要に応じて補いました。

FoundationDBとは?

非シャーディング型、厳格な直列化可能性を持つ、障害耐性のあるキーバリューストアで、ポイント書き込み、読み取り、範囲リードに対応しています。SQLではなくキーバリューAPIを提供。非シャーディングのため、すべてのキー空間は一つの論理的シャードに存在します。厳格直列化可能な(必要に応じて緩和可能)KVストアがあれば、その上にSQLエンジンやセカンダリインデックス等を積み重ねて分散データベースを構築できます。これは優れた設計選択です。

驚くべき主張

論文は冒頭で、いくつか驚異的な主張をしています。

  • FDBは strict serializable でロックフリー。どうやって?
  • グローバル展開でxリージョン書き込み遅延を回避できる。
  • f個の障害に対して f+1 レプリカのみで耐性がある。

これらの主張については本文を通じて検証します。

アーキテクチャ

Image 1: fdb1

FDBはマイクロサービス(論文ではデカップリング)設計を極限まで推し進めており、ほぼ全ての機能が独立したサービス(ステートフルまたはステートレス)で処理されます。

コントロールプレーン

図中で最も重要なControl Planeのサービスは「Coordinator」です。全体設定の小規模メタデータ(例:エポック情報など)を管理します。ClusterControllerは各サーバのヘルス状態を監視します。

データプレーン

Data Planeは“トランザクションシステム”、“ログシステム”、“ストレージシステム”に分かれます。ログ/ストレージシステムは分散ログ、および分散シャーディングされたストレージ構成。最も興味深いのはトランザクションシステムで、なかでも「Sequencer」が重要です。

トランザクション管理

  1. クライアントは常にProxyに接続。Proxyが内部サービスと通信。

  2. ProxyはSequencerからHLC(ハイブリッド論理クロック)形式でリードバージョンを取得。Sequencerは唯一無二の物理プロセスで、すべてのイベントのシリアライズ順序(直列化順序)を提供します。

    Image 2: fdb2

  3. クライアントは取得したリードバージョンでストレージに読み取り要求(MVCCによる過去時点のデータ取得)。

  4. 再度Sequencerにコミットバージョンを要求。

  5. 書き込みセット&リードセットをResolverへ送信。Resolverはレンジごとにシャーディングされ、直近の書き込み履歴を短期間保持。ここで競合(リードセット対象データが[read-version, commit-version]間で変更された場合)を検出。

  6. 競合なしなら、コミットバージョンでLog Systemに書き込み。十分なACKを受信後、Proxyがクライアントに成功を返却。

これは楽観的並行制御(OCC)の非常にストレートな実装です。

Bhaskar Muppana氏の指摘に従い、一部文章を訂正しています。

Proxyが必要な理由は、ほとんどのRDBMSが提供する、「トランザクション中に未コミットの自身の書き込みを読める」機能を実現するためです。それはProxyサーバで未コミットの書き込みをローカルバッファに保持し、リード時にストレージのデータとマージして返すことで実現します。また、クライアントは未コミット書き込みをキャッシュし、同一トランザクション中の読込に対応します。

Proxyはクライアントとトランザクションシステムの仲介です。また、リクエストバッチ化(Sequencerに対するQPS軽減)などの役割も担います。

Resolverはレンジ単位でシャーディングされており、競合判定を並列化できます。Proxyはあらゆる関連Resolverからの応答を待つ必要があります。Resolverは最近の「書き込み試行」を記録し、それによって競合検出のみロック無しで実現。競合チェックは本当にロックフリーですが、Sequencerやシステム全体の順序付けには“どこかで”ロックや排他制御が必須です(OSカーネルやハードウェアのアトミック操作も広義のロック)。

SequencerやResolver故障時にも後ほど触れます。

ログプロトコル

Image 3: fbd3

一見シンプルなログ&ストレージ分離ですが、FDBは「シーケンス」と「ログ」を本質的に分離しています。Sequencerは唯一。それ以外のLogServerはただデータを蓄積するのみで順序制御をしません。この分離により高スループット・低レイテンシを実現します。各LogServerには全Key用メッセージがブロードキャストされますが、実データは該当ストレージシャードに関連するLogServerにのみ送信されます。

ここで2PCは不要です。Proxyが複数ログに"盲目的"に書き込む(失敗しても再試行可能)ため、完全な分散コミット合意は無くても構いません。

この設計により、ログコミットの本当の障害はログサーバの実障害時のみです(その際は後述のリカバリープロセスが走る)。

「Sequencer1個で複数ログ・複数ストレージを支える」設計になっている点に注意してください。

リカバリープロセス

SequencerやResolver/LogServerがダウンした際の流れは以下です:

  1. ClusterControllerが障害検知→リカバリーを明示的に開始。
  2. SequencerはCoordinatorから以前の状態をロックして読み出す(新しいSequencerによるリカバリーで同時変更を防止)。CoordinatorがPaxos動作中なので、多重ロック問題はPaxosで解決可能。
  3. 古いLogServer群を停止し、古いSequencer等から受け入れ以後をブロック。これによりデータ損失や競合Sequencer発生を防止。
  4. 新たにProxy/Resolver/LogServer群を配置。
  5. 新システム状態を書き戻し、ロック解除。
  6. 新Sequencer稼働—新規トランザクション受け入れ開始。

FDBのリカバリには「ダウンタイム」があります(P50で3.08秒)。この間、書き込みができません。ただしストレージノードからのスナップショットリードは可能であるため、FDBが読み中心のシーンに適している根拠とも言えます。

Image 4: fbd4

Proxyはステートレスなので再始動容易。Resolverは前エポック分を捨てて良い(エポックを跨いだトランザクション不可なため)。ログとSequencerのみが復旧の要。

ログリカバリー詳細

Image 5: fbd5

m台のLogServerとレプリカ数kの場合:

  • それぞれのログはDV(Durable Version: 永続化済み最大LSN)とKCV(Proxyが知りうる最新Commit version)を保持。
  • Sequencerは全旧ログ停止を試み、m-k+1台から返事を得た時点で、以前のエポックがmax(KCVs)までコミットされていたことが判明→新Sequencerは次バージョンから始動。

論文で扱われているRV(Recovery Version)はmin(DVs)で、[PEV+1, RV]のデータを新ログに複製し、以降を破棄します。詳細は省略しますが以下2点のための措置です:

  1. ログコミットの部分的失敗時のアトミック性確保
  2. コミット済みデータのレプリケーション修復

正しさの証明(概要)

  • あらゆるログメッセージは競合判定済&耐障害性考慮済のため、max(KCVs)までが完全コミット済とみなせる
  • [PEV+1, RV]は安全側に倒してコミット済扱いとする・以降破棄
  • 詳細な証明は本文省略

Image 6: fbd6

レプリケーションまとめ

  • Coordinator: Paxosで 2f+1 台中 f 台まで障害耐性
  • LogServer: f+1 レプリカでf台耐性(台数依存しない)。ストレージも類似
  • 多様な分離により柔軟な冗長化を実現

冒頭の主張について

FDBは非常に優れたKVストアですが、論文冒頭のキャッチコピーはやや誇張・ミスリーディングな面があります。

  • 「strict serializability かつ lock-free」→ 厳密には競合検出がlock-free、だがSequencer自体はそうではない。
  • 「グローバル展開でもxリージョン遅延を回避」→ ローカルリージョン・特定障害ドメイン等の前提条件が必須
  • 「f+1レプリカでf障害耐性」→ あくまでログやストレージであり、Coordinatorの単純多数故障時はダウン

まとめ

FDBはおそらく、リージョナルなKVストアとして現存最良でしょう。シミュレーション基盤の堅牢性、優れた設計選択、密度の高い論文内容など、非常に高い評価に値します(一部仕様・細部・証明などが論文誌面の都合でカットされています)。FoundationDBチームに賛辞を送ります。


  1. FDBシングルトン(主にSequencer)のスケーラビリティ制約には依存します。 ↩︎