結果整合性
Eventual Consistency ・ けっかせいごうせい
更新がすぐ全複製に届かなくても、書き込みが止まればいずれ全レプリカが同じ値に収束する整合性モデル。
✦ 30秒で試す — 航海数秒のずれを許すだけで、世界規模のサービスが止まらない「完了」の直後に友人が見るいいね数は？予想してみる概要
結果整合性（eventual consistency）は、「更新した瞬間に全員が最新の値を見られるわけではないが、新しい書き込みが止まれば、いずれすべての複製が同じ値に落ち着く」という整合性のモデルです。データを複数のノードに複製（レプリケーション）して運用するとき、書き込みを全レプリカに反映し終えるまで応答を待つのではなく、一部のレプリカに書けた時点で応答を返し、残りへは裏側で少し遅れて伝えます。この「遅れ」を許す代わりに、応答の速さと、一部のノードが落ちたりつながらなくなったりしても書き込みを受け付け続けられる可用性を手に入れます。
対になるのが強い整合性（strong consistency）で、代表は線形化可能性（linearizability）です。「書き込みが完了したあとに読めば、どのノードに読みに行っても必ずその値かそれより新しい値が返る。システム全体が1台であるかのように振る舞う」という保証です。分かりやすい代わりに、複製どうしが確かめ合うぶん遅く、ネットワークが分断されると応答を諦めなければならない場面が出ます。
結果整合性が選ばれるのは、SNS のタイムライン、いいね数、閲覧数、通知のように、「数百ミリ秒〜数秒の食い違いは実害が小さいが、遅延や停止は困る」という場面です。「いいねを押したのに、別の端末ではまだ数字が増えていない」という体験の裏には、たいていこのモデルがあります。「いずれ」がどのくらいの時間なのかをモデル自体は約束しない点も、最初に押さえておきたい性質です。
なぜ生まれたか
1台のデータベースにすべてを載せていた時代、整合性は悩む対象ですらありませんでした。真実は1か所にしかないので、書いた値をそのまま読めば必ず最新です。ところがアクセスが世界規模になり、データを地理的に離れた複数拠点へレプリケーションするようになると、事情が一変します。東京とロンドンのレプリカを常に完全に同期させようとすれば、書き込みのたびに地球の裏側との往復（100ミリ秒以上）を待つことになります。しかも両拠点をつなぐ回線が切れた瞬間、同期を待つ設計では書き込みそのものが止まってしまいます。
この限界を定理として示したのが CAP定理です。正確には「ネットワークの分断が起きたとき、線形化可能性（C）と、生きているノードは必ず応答すること（A）の、どちらかを諦めるしかない」という主張です。分断中も書き込みを受け付け続けたいシステムは、一時的な食い違いを受け入れるしかありません。さらに分断が起きていない平常時にも、「複製の確認を待つほど遅くなる」という遅延と整合性の取引があります（PACELC と呼ばれる整理です）。世界中に複製を持つシステムにとっては、まれな分断よりも、この毎回の待ち時間のほうが切実でした。
そこで「厳密な整合性を手放す代わりに、速さと可用性を取り、食い違いは後から必ず収束させる」という設計が現れます。1990年代にはすでに、モバイル端末どうしでデータを同期する研究（Xerox PARC の Bayou など）で、「自分の書いた値は自分には見える」といった弱い保証の組み合わせが整理されていました。2007年に Amazon が Dynamo の論文で、ショッピングカートを止めないためにこの考え方を大規模な実運用の設計として示し、翌年 Amazon の CTO ヴァーナー・ボーゲルスが「Eventually Consistent」という記事で用語を広めました。NoSQL の多くは、この系譜の上にあります。
詳細
更新が伝わって収束する様子
結果整合性の核心は、「書き込みの応答を返すタイミング」と「全レプリカがそろうタイミング」がずれていることです。あるレプリカに書き込むと、システムはその1台（あるいは一部）への反映だけで完了を返し、ほかのレプリカへの伝播は非同期で追いかけます。伝わり終わるまでのわずかな時間、レプリカによって古い値と新しい値が混在します。
図の「別の読み手」が古い 10 を受け取る一瞬が、結果整合性の代償です。その代わり書き手は同期の完了を待たずに済み、レプリカ B が一時的に落ちていても書き込みは通ります。伝播が届いて収束（convergence）したあとは、どのレプリカに読みに行っても同じ値が返ります。
収束を成り立たせる仕組み
「いずれ収束する」を本当に保証するには、二つのことが要ります。一つは、更新が漏れなく全レプリカに届くこと。もう一つは、届いた順番がレプリカごとに違っても、同じ結果にまとまることです。
届ける仕組みには、ノード同士がランダムに相手を選んで情報を交換し、噂話のように全体へ広める「ゴシッププロトコル」、読み取りのついでに複数レプリカの値を突き合わせて古いほうを直す「read repair」、落ちていたノードの代わりに書き込みを預かっておき、復帰したら渡す「hinted handoff」、レプリカ同士が定期的に中身の要約（Merkle 木というハッシュの木）を比べて差分だけを送る「アンチエントロピー」があります。
まとめる仕組みの代表は、各更新にタイムスタンプを付けて「新しいほうを残す」last-write-wins（LWW）です。単純ですが、同時に書かれた二つの値の片方を黙って捨てます。しかもノードの時計がずれていると、実際には後から書いた値のほうが捨てられることもあります。これを避けたいときは、更新の因果関係を記録するバージョンベクタで「どちらが後か」「同時だったか」を判定して、同時だった値は両方残してアプリケーションに解決させます。どんな順番でマージしても同じ結果になるよう数学的に設計されたデータ構造（CRDT。増えるだけのカウンタや、追加と削除を記録する集合など）を使えば、衝突そのものを起こさずに収束させられます。
クォーラム — 整合性の強さをダイヤルで選ぶ
Dynamo の系統のデータストア（Cassandra や Riak など）では、読み書きに関わるレプリカの数を調整して、整合性の強さを段階的に選べます。1つのデータを N 台に複製しておき、「書き込みは W 台から完了の返事が来たら成功」「読み取りは R 台に問い合わせて、返ってきた中でいちばん新しい版を採る」と決めます。このとき W + R > N にしておくと、書き込みが届いた W 台と、読みに行く R 台は、どう選んでも少なくとも1台で重なります。重なった1台が新しい版を持っているので、読み手は最新の書き込みに必ず触れられます。これがクォーラム（定足数）の考え方です。
W と R はダイヤルです。W=1・R=1 なら、1台でも生きていれば読み書きでき、待ち時間も最短ですが、古い値を読むことがあります。W=N なら読みは1台で済みますが、1台でも落ちると書けません。多くの現場では N=3・W=2・R=2 のように、過半数どうしを重ねて「1台落ちても読み書きでき、しかも読みは最新に触れる」点を選びます。ただし、ネットワークが分断されて片側に W 台が残らなくなれば、その側では書けなくなります。重なりを保証する代わりに、可用性を手放しているのです。
下の部品で確かめてください。レプリカの上下にかかった括弧の端をつかんで W と R を増減させ、書いてから読みます。読みは「いちばん遅れているレプリカに運悪く当たった」場合を試します。レプリカの間の隙間を押すと分断が立ち、箱を押すとそのレプリカが落ちます。
まず「書く」を押してください。書き込み（金の粒）は近いレプリカから順に届き、W 台から返事が来た時点で完了します。完了したらすぐ「読む」を押します。
W + R > N は強力な目安ですが、それだけで線形化可能性が手に入るわけではありません。落ちたノードの代わりに無関係なノードへ書き込みを預ける sloppy quorum（Dynamo の既定の動き）では、「W 台」がもともとの N 台の外に出てしまい、読みの集合と重ならないことがあります。二人の書き手が同時に書いたときや、書き込みが W 台に届く前に失敗して一部にだけ残ったときも、どちらが「最新」かはっきりしません。LWW で解決していれば、時計のずれによって新しい書き込みが古いものに負けることもあります。クォーラムは「最新に触れる確率を大きく上げる仕組み」であって、「最新だけを見せる約束」ではない、と考えておくのが安全です。
ACID の C、CAP の C、BASE
結果整合性は、RDBMS が重んじる ACID（原子性・一貫性・分離性・永続性）と対比して、BASE という言葉で語られることがあります。Basically Available（基本的に応答する）、Soft state（状態は揺らいでよい）、Eventually consistent（いずれ整合する）の頭字語で、1997年にブリュワーらが大規模なネットワークサービスの設計を論じた論文で、ACID と対になる語呂合わせとして使いました。
ここで混同しやすいのが、三つの「一貫性」の違いです。ACID の C（Consistency）は「制約（残高は0以上、など）を破ったデータを残さない」という、1つのデータベースの中の正しさの話です。CAP定理 の C は線形化可能性で、「複製が複数あっても、1台のように最新の値が見える」という、複製の間の見え方の話です。結果整合性が緩めているのは後者であって、前者ではありません。結果整合性のデータストアでも1件の書き込みの中で制約を守ることはできますし、逆に ACID のデータベースでもレプリカから読めば古い値が見えます。
どのデータに許すか — 使い分けと落とし穴
実務でいちばん大事なのは、「どのデータに結果整合性を許すか」の線引きです。口座の残高、在庫の引き当て、二重予約が許されない座席のように、一瞬の食い違いが金銭や信頼の損失に直結するデータには、強い整合性（あるいは合意アルゴリズムに基づく1か所での確定）を選びます。一方、いいね数、閲覧数、通知、キャッシュ、ソーシャルフィードのように、数秒ずれても誰も損をしないデータは、結果整合性で速さと可用性を優先します。同じサービスの中でも、データごとに選び分けるのが普通です。
典型的な落とし穴は、利用者から見た「おかしさ」です。投稿した直後に自分の画面で投稿が消えて見える（自分の書き込みが自分に見えない）、リロードするたびに数字が増えたり減ったりする（読むたびに別のレプリカに当たり、新しい値のあとに古い値を見る）、返信が元の投稿より先に表示される（因果の順序が崩れる）。どれも結果整合性の定義には違反していません。対策は、上の図の中段にある弱い保証を足すことです。書いた本人の読み取りだけはリーダーに向ける（read-your-writes）、同じ利用者は同じレプリカに張り付ける（単調読み取り）、依存関係のある更新は順序を保って届ける（因果整合性）。結果整合性は万能の緩和策ではなく、「どこまで緩めてよいか」をデータごとに設計する判断そのものです。
試問
5台のレプリカ（同じデータの複製を持つサーバ）に、書き手が書いて読み手が読む画面です。書き込みは全台に送り、上の括弧の W 台から返事が来たら完了。読みは下の括弧の R 台に問い合わせ、しかも生きている台のうち「いちばん遅れている R 台」に運悪く当たる場合を試します。括弧の端をドラッグして W と R を増減でき、レプリカの箱を押すとその台が落ちます（もう一度押すと戻る）。右の2台は遠く、書き込みが遅れて届きます。
まず「書く」を押してください。書き込み（金の粒）は近いレプリカから順に届き、W 台から返事が来た時点で完了します。完了したらすぐ「読む」を押します。