分散データベース — CAP・レプリケーション・合意

データベースを2台に増やした瞬間、「どちらが正しいのか」という新しい問いが生まれます。レプリケーション・クォーラム・CAP定理・2相コミット・Raft・結果整合性を、前提知識ゼロから、PostgreSQLやCassandraで実際に触るパラメータ名まで降ろして解説します。

In Search of an Understandable Consensus Algorithm (Raft) — Diego Ongaro

比喩: 3つの支店に置いた同じ台帳

東京・大阪・シンガポールの3支店に、まったく同じ台帳を置いた会社を考えます。どこでも残高が引けて、どこでも書ける。1つの建物が焼けても帳簿は残ります。

問題は支店をつなぐ回線が切れたときです。東京の窓口に客が来て「10万円下ろしたい」と言う。東京の台帳では残高は足りている。けれど同じ客が同時に大阪でも引き出していたら？ 回線が切れている以上、東京から確かめる術はありません。

残された道は2つです。「確認できないので、いまは扱えません」と断るか、「たぶん大丈夫」として払い、後で辻褄を合わせるか。前者は営業を止め、後者は残高がマイナスになりうることを飲みます。

分散データベースの理論は、突き詰めればこの二択の言い換えです。1台の中で何が起きているかはデータベース内部構造とトランザクションとACIDで扱っているので、ここでは台数が増えたときに何が新しく壊れるかだけを追います。

なぜ1台で済ませないのか

増やす動機は3つです。壊れるから——ディスクは壊れ、電源は落ち、データセンターは水没します。1台構成の可用性は、その1台の可用性でしかありません。入りきらないから——1台のディスクとメモリには上限がある。遠いから——東京のサーバーに東京から聞けば数ミリ秒ですが、地球の裏側からでは光の速度だけで往復100ミリ秒近くかかります。回線に金を払っても物理法則は値切れません。

答えは2種類あります。壊れる問題にはレプリケーション（同じデータを複数台に持つ）、入りきらない問題にはシャーディング（データを分割して別の台へ置く）。現場では両方を重ねます——データを100個の断片に分け、各断片を3台ずつ複製する、という具合に。この記事が扱うのは前者、同じデータの写しが複数ある状態で、どれを正しいと見なすかという問題です。

レプリケーション — 誰が書き、誰が写すか

写しの持ち方は3通りあります。

単一リーダーは、書き込みを受ける台を1つに決め、残りは写しに徹する方式です。PostgreSQL・MySQL・MongoDBの標準構成がこれで、「誰が正しいか」が定義上つねに決まっているので考えることが少ない。代わりにリーダーが落ちると、次が決まるまで書き込みが止まります。

複数リーダーは書ける台を複数持ちます。地域ごとに書き込み先を置けるので近くて速い。代わりに2箇所で同じ行が同時に書かれ、衝突をどう解くかという宿題が必ず付いてきます。

リーダーレスは、クライアントが複数台へ直接書き、複数台から直接読む方式です。Amazonが2007年に発表したDynamo論文が出発点で、Cassandraなどが採用しています。単一障害点がない代わりに、「何台から返事が来たら成功と見なすか」を自分で決めることになります。

3つのうち2つがわざわざ「リーダー」を立てているのには理由があります。台数を $n$ とすると、リーダーが全員に配る通信は $n$ に比例して増えるだけですが、全員が全員に確認を取る形は $n^2$ で伸びる。丈夫にするつもりで増やした台数が、そのまま遅さに化けるかどうかの分かれ目です。

待つか、待たないか

リーダーが自分のディスクに書いたあと、写しが届いたのを確認してから成功を返すか、確認せずに返すか。ここが最初の分岐点です。

確認しない（非同期）なら速い。ただしリーダーが直後に壊れると、まだ誰にも伝わっていない書き込みが消えます。「成功しました」と答えたのに消えるのがこの構成の性質です。確認する（同期）なら消えませんが、写し先が1台詰まるだけで書き込み全体がその遅さに引きずられます。

PostgreSQLではこの深さを synchronous_commit で選びます（local は自分のディスクまで、remote_apply は待機系が反映してレプリカから読める状態になるまで）。落とし穴はその先です。準同期の実装はたいていタイムアウトを持っていて、待機系が応答しなくなると自動的に非同期へ落ちる。可用性は保たれますが、そのとき「同期のつもりの系」は黙って非同期になっています。切り替わりを監視していなければ、次の障害でデータが消えて初めて気づきます。