結果整合性
近年, データ複製の文脈で 結果整合性(eventual consistency) に関する議論が盛んだ. この記事では大規模データの複製における原則や抽象, 高可用性とデータ整合性のトレードオフに関する話題をいくつか集めてみたいと思う. 現在進行中の分野であり, 全ての定義が最初から明快であるとは思わないでほしい.
理想的な世界に整合性モデルは一つしかない: 更新があったら全ての観測者はその更新を知るというモデルだ. 70 年代後半のデータベースシステム分野で, このモデルの実現が難しくなりはじめた. この分野での <金字塔> は Bruce Lindsay らによる "Notes on Distributed Databases" (Research Report RJ2571(33471), IBM Research, July 1979) だろう. この記事ではデータベース複製の根本原則を示し, 整合性を実現する数々の技術が議論された. そうした技法の多くは分散透過を実現しようとしている: システムの利用者に対し, 連携して動くシステム群ではなく単一のシステムを見せようとしたのだ. こうしたシステムのとるアプローチの多くは, システムの故障より透過性の破れを気にしていた.
90年代の半ば, より巨大なインターネット・システムの登場により, こうした慣習は見直されだした. この時期からシステムの特性として可用性がより重要であるという考えが生まれた. 結果として人々はトレードオフがどうあるべきか模索することになる. Berkley のシステム部教授であり当時 Inktomi の親玉であった Eric Brewer は, 2000 年に開催された PODC カンファレンスのキーノートで 異なるトレードオフをまとめる考えを持ちこんだ. Eric は CAP 定理 を提唱した. この定理は共有データに関する三つの特性を記述する; データの整合性(consistency), システムの可用性(availability), ネットワークの分断(partition) だ. どんな時も, このうちの二つだけしか同時には達成することができない. Gilbert と Lincy の論文にはより形式的な証明がある.
ネットワーク分断への耐性を捨てたシステムなら, データの整合性と可用性を実現できる. これには普通トランザクション・プロトコルを使う. 実現のためにはクライアントとストレージ・システムが同じ環境にある必要がある. これだとシナリオによってはシステム全体が故障してしまうし, クライアントは分断を検知できない. 重要な洞察がある: 大規模な分散システムではネットワークの分断が所与のものであり, 従って整合性と可用性は両立しない. どちらか一方は捨てる必要がある. 整合性を妥協すればシステムは分断のある状況でも高可用性を実現できる. 整合性を優先すればシステムの使えない状況を生む.
いずれにせよクライアントの開発者はシステムがどちらを用意しているか意識する必要がある. システムが整合性をとるなら, 開発者はシステムが落ちていて書きこめないという状況に対処しなければならない. システムが落ちて書きこめなかったら, 書きこむはずだったデータをなんとかする必要がある. システムが可用性をとるなら, そのシステムはいつも書込みを受けつけるだろう. しかし場合によっては先に成功した書込み結果を読み込みが反映していないかもしれない. クライアントがいつも完全に最新のデータにアクセスする必要が あるか否か, 開発者は判断する必要がある. 世の中には少し古いデータでも使えるアプリケーションがそれなりにある. そうしたアプリケーションはこのモデルでうまく動く.
原則として, トランザクション・システムで ACID 特性 として 定義されている整合性特性はまた別のものだ. トランザクションが終わったときにデータベースのが整合性のある状態になる, ACID 整合性モデルはそんな保証をする. たとえばある口座から別の口座に金を移すとき, ふたつの口座の合計が変わってはいけない. ACID をもつシステムでこの種の整合性はトランザクションを書く開発者の責任だが, データベースは整合性制約を管理することでそれを助けてくれる.
クライアント側には四つのコンポーネントがある
クライアント側の整合性は, いつ, どうやって観測者 (ここではプロセス A, B, C) が ストレージシステム内のオブジェクトに起きた更新を知るかを定める. 以下の例では A がデータオブジェクトを更新したとする.
結果整合性モデルには考慮すべきバリエーションが多くある.
これらの特性は組み合わせて使える. たとえば単調読み出し整合性をセッション整合性と共に使うなど. 実用的な観点では単調読み出し整合性と単調書込み整合性の二つの組合せが 結果整合性として最も望ましい. しかし常にそうある必要はない.
異なるバリエーションを考えると, かなりのシナリオがありうるとわかる. その状況下でうまくいくかは, そこで作るアプリケーションが何なのかに依存する.
結果整合性は過激派分散システムの秘伝特性ではない. 今時の RDBMS の多くは プライマリ-バックアップ式に信頼性を提供しており, 複製更新の実装には同期と非同期のモードがある. 同期モードの複製更新はトランザクションの一部だ. 非同期モードの更新はバックアップが遅延して到着する. やってきたバックアップの値は古く, 非整合かもしれない. また読み出し性能をスケーラブルにするべく, RDBMS はバックアップからの読み込みができるようになりつつある. これは古典的な結果整合性保証の使い道で, 不整合ウィンドウの大きさはログの到着にかかる時間で決まる.
話を始めるまえに, いくつか定義をしておこう:
W+R > N なら, 読み込み集合と書き込み集合が重なるため強い整合性を保証できる. プライマリ-バックアップ式の RDBMS で N=2, W=2, R=1 の同期複製をする場合などがそうだ. クライアントがどの複製から読み出しをしても整合性のある結果が戻ってくる. 非同期の複製でバックアップから読み出す場合は N=2 W=1, R=1 となり, R+W=N なので整合性は保証できない.
こうした構成にともなう問題がある. これらは基本的な定足数(quorum, 多数決)プロトコルだ. システムの故障で W 個のノードに書き込むことができない場合がある. そうすると書込みは失敗し, システムの可用性が損なわれる. N=3 かつ W=3 のとき, ノードが 2 個しか動いていないと書込みは失敗する.
高性能かつ高可用性を担う分散ストレージシステムでは, 複製の数はふつう 2 より大きい. 対故障性だけを意図したシステムではよく N=3 を使う. (W=2, R=2 の構成.) 高負荷をさばきたいシステムでは対故障性に必要な数以上に複製を作ることが多い. N として数十, 数百のノードを用意し, R を 1 とする. 読み込みは一回ですぐ戻る. 整合性を気にするシステムでは W=N で更新をする. しかしこれは書き込みの成功率を下げるかもしれない. よくあるシステム構成として, 対故障性は気にするが一貫性はそうでもない場合は W=3 で更新の永続性を担保しつつ, 他の複製を更新するのに遅延(感染型, epidemic)技法を使う.
N, W, R の構成は, 一般的なケースや最適化したい性能パスがどこかに依存する. R=1 かつ N=W なら読み込みの場合に特化するし, W=1 かつ R=N なら書込みが極めて高速になる. もちろん後者の場合, 故障があった場合の永続性は保証されない. そしてもし W < (N+1)/2 なら書込み集合が重複しないせいで衝突のおこる可能性がでる.
弱い/結果整合性は W+R <= N の時にあらわれる. このとき読み込みと書込みの集合は重複しないことがある. この構成が意図的なもので, 故障の場合をふまえないなら, R を 1 以外にすることはほとんどない. こうするケースにはよく知られたものが二つある. 一つ目は読み出し側で大規模な複製を行う既に述べたようなケース. 二つ目はデータへのアクセスがより複雑なケースだ. キーと値の単純なモデルはバージョンを比べてどちらの値が最新かを判断するのが簡単だ. しかしオブジェクトの集合を返すようなシステムは 最新の値集合を正しく求めるのが難しい. こうしたシステムで書き込み集合が複製集合より小さいなら, 遅延方式を使って複製集合の残りのノードを更新することができる. 全ての複製を更新するまでにかかる時間が先に述べた不整合ウィンドウになる. W+R <= N だとシステムは値の更新を受け取る前のノードから値を読みだす危険がある.
read-your-write 整合性, セッション整合性, 単調整合性が 達成できるかどうかは, 一般にその分散プロトコルを実行するクライアントとサーバの "くっつき具合" に依存している. いつも同じサーバにアクセスするなら, read-your-write やセッション整合性は比較的簡単に実現できる. 負荷分散や耐故障性が少しやりにくくなるが, 単純な解ではある. "くっつく" セッションを使うと, クライアントに対して露出レベルを明示的に示すことができる.
read-your-write や単調読み出しはクライアント側で実装されることがある. 書き込みにバージョンをつけることで, 読みだした値のバージョンが過去につけておいたバージョンより前のものなら それを破棄することができる.
分断がおこると, システム内のあるノードから他のノードが見えなくなる. しかしクライアントからは全てのノードが見えてもいい. 古典的な多数決アプローチを使うなら, W 個の複製ノード集合を持つ分断部は他の分断部が見えなくても 更新を続けることができる. 同様のことが読み出しにも言える. 二つの分断部が重複した場合, 定義によって少数派が見えなくなる. 分断はそう頻繁におきない. しかしデータセンター内でもデータセンターをまたいでも起こることはある.
不整合を許しても二つの目的から割にあう. 並列性の高い動作環境での読み込み性能と書き込み性能の改善がひとつ. もう一つは分断した場合の動作だ. 分断時, 大半のモデルではノード自身が動いていても システムが部分的に動作できなくなってしまう.
クライアントが不整合を許容でるきるか否かはアプリケーションに依存する. 特によく知られたケースとして, ユーザに認知できる範囲で 整合性があればいいウェブサイトのシナリオがある; 不整合ウィンドウは顧客が次ページに移動する時間の期待値より小さければいい. これは時ページのロードまでにシステム内で更新を広めればよいことを意味する.
この記事では整合性と可用性のモデルに関する定義と原則をいくつか集めてみた. このリストは不完全だと思う. 間違っているかもしれないし, 厳密さは無いかもしれない. 有用で完全になるまで更新していきたい.