FoundationDBの動作原理とその優れた設計選択について詳細に解説します。設計の核心部分、失敗時のリカバリー、驚くべき主張の真相を掘り下げます。
FoundationDBは非常に優れたデータベースです。その論文はSIGMOD’21のベスト産業論文賞を受賞しました。本記事では、FDBがどのように動作するのかを詳細に説明し、彼らが取った興味深い設計選択について考察します。論文には含まれていない多くの詳細や(ときには正しさの証明すら)必要に応じて補いました。
非シャーディング型、厳格な直列化可能性を持つ、障害耐性のあるキーバリューストアで、ポイント書き込み、読み取り、範囲リードに対応しています。SQLではなくキーバリューAPIを提供。非シャーディングのため、すべてのキー空間は一つの論理的シャードに存在します。厳格直列化可能な(必要に応じて緩和可能)KVストアがあれば、その上にSQLエンジンやセカンダリインデックス等を積み重ねて分散データベースを構築できます。これは優れた設計選択です。
論文は冒頭で、いくつか驚異的な主張をしています。
これらの主張については本文を通じて検証します。
FDBはマイクロサービス(論文ではデカップリング)設計を極限まで推し進めており、ほぼ全ての機能が独立したサービス(ステートフルまたはステートレス)で処理されます。
図中で最も重要なControl Planeのサービスは「Coordinator」です。全体設定の小規模メタデータ(例:エポック情報など)を管理します。ClusterControllerは各サーバのヘルス状態を監視します。
Data Planeは“トランザクションシステム”、“ログシステム”、“ストレージシステム”に分かれます。ログ/ストレージシステムは分散ログ、および分散シャーディングされたストレージ構成。最も興味深いのはトランザクションシステムで、なかでも「Sequencer」が重要です。
クライアントは常にProxyに接続。Proxyが内部サービスと通信。
ProxyはSequencerからHLC(ハイブリッド論理クロック)形式でリードバージョンを取得。Sequencerは唯一無二の物理プロセスで、すべてのイベントのシリアライズ順序(直列化順序)を提供します。
クライアントは取得したリードバージョンでストレージに読み取り要求(MVCCによる過去時点のデータ取得)。
再度Sequencerにコミットバージョンを要求。
書き込みセット&リードセットをResolverへ送信。Resolverはレンジごとにシャーディングされ、直近の書き込み履歴を短期間保持。ここで競合(リードセット対象データが[read-version, commit-version]間で変更された場合)を検出。
競合なしなら、コミットバージョンでLog Systemに書き込み。十分なACKを受信後、Proxyがクライアントに成功を返却。
これは楽観的並行制御(OCC)の非常にストレートな実装です。
Bhaskar Muppana氏の指摘に従い、一部文章を訂正しています。
Proxyが必要な理由は、ほとんどのRDBMSが提供する、「トランザクション中に未コミットの自身の書き込みを読める」機能を実現するためです。それはProxyサーバで未コミットの書き込みをローカルバッファに保持し、リード時にストレージのデータとマージして返すことで実現します。また、クライアントは未コミット書き込みをキャッシュし、同一トランザクション中の読込に対応します。
Proxyはクライアントとトランザクションシステムの仲介です。また、リクエストバッチ化(Sequencerに対するQPS軽減)などの役割も担います。
Resolverはレンジ単位でシャーディングされており、競合判定を並列化できます。Proxyはあらゆる関連Resolverからの応答を待つ必要があります。Resolverは最近の「書き込み試行」を記録し、それによって競合検出のみロック無しで実現。競合チェックは本当にロックフリーですが、Sequencerやシステム全体の順序付けには“どこかで”ロックや排他制御が必須です(OSカーネルやハードウェアのアトミック操作も広義のロック)。
SequencerやResolver故障時にも後ほど触れます。
一見シンプルなログ&ストレージ分離ですが、FDBは「シーケンス」と「ログ」を本質的に分離しています。Sequencerは唯一。それ以外のLogServerはただデータを蓄積するのみで順序制御をしません。この分離により高スループット・低レイテンシを実現します。各LogServerには全Key用メッセージがブロードキャストされますが、実データは該当ストレージシャードに関連するLogServerにのみ送信されます。
ここで2PCは不要です。Proxyが複数ログに"盲目的"に書き込む(失敗しても再試行可能)ため、完全な分散コミット合意は無くても構いません。
この設計により、ログコミットの本当の障害はログサーバの実障害時のみです(その際は後述のリカバリープロセスが走る)。
「Sequencer1個で複数ログ・複数ストレージを支える」設計になっている点に注意してください。
SequencerやResolver/LogServerがダウンした際の流れは以下です:
FDBのリカバリには「ダウンタイム」があります(P50で3.08秒)。この間、書き込みができません。ただしストレージノードからのスナップショットリードは可能であるため、FDBが読み中心のシーンに適している根拠とも言えます。
Proxyはステートレスなので再始動容易。Resolverは前エポック分を捨てて良い(エポックを跨いだトランザクション不可なため)。ログとSequencerのみが復旧の要。
m台のLogServerとレプリカ数kの場合:
DV
(Durable Version: 永続化済み最大LSN)とKCV
(Proxyが知りうる最新Commit version)を保持。max(KCVs)
までコミットされていたことが判明→新Sequencerは次バージョンから始動。論文で扱われているRV
(Recovery Version)はmin(DVs)
で、[PEV+1, RV]
のデータを新ログに複製し、以降を破棄します。詳細は省略しますが以下2点のための措置です:
max(KCVs)
までが完全コミット済とみなせる[PEV+1, RV]
は安全側に倒してコミット済扱いとする・以降破棄FDBは非常に優れたKVストアですが、論文冒頭のキャッチコピーはやや誇張・ミスリーディングな面があります。
FDBはおそらく、リージョナルなKVストアとして現存最良でしょう。シミュレーション基盤の堅牢性、優れた設計選択、密度の高い論文内容など、非常に高い評価に値します(一部仕様・細部・証明などが論文誌面の都合でカットされています)。FoundationDBチームに賛辞を送ります。