この記事の初出はComputer誌であり、InfoQとIEEEコンピュータソサエティによって転載します。
CAP定理は、共通のデータを扱うネットワークで繋がったシステムは3つの望ましい性質のうち、2つしか満たせないことを示します。しかし、明示的に分割に対処することで、設計者は一貫性と可用性を最適化し、3つの性質すべての釣り合いを取ることができます。
CAP定理が紹介されてから10年、設計者や研究者はCAP定理を新しい分散システムを探すための指針として利用(あるいは乱用)しました。NoSQLも従来のデータベースに対する論拠としてCAP定理を利用しています。
CAP定理は、共通のデータを扱うネットワークで繋がったシステムが3つの望ましい性質のうち、2つしか満たせないことを示します。
- 一貫性(C)、つまり単一の最新データを持っていること
- そのデータの更新に対する高可用性(A)
- そして、ネットワーク分割に対する耐性(P)
CAP定理のこの表現は目的を果たしました。目的とは設計者がシステム対する幅広い視点を持ちトレードオフを意識するようになることです。実際、この10年でさまざまな新しいシステムが現れ、一貫性と可用性の相対的なメリットについても多くの議論がされました。ただし、"3のうち2つ"という公式はミスリーディングでした。というのは、この公式は3つの属性の緊張関係を過度に単純化してしまうからです。過度の単純化は問題です。CAPが不可能だとしているのはほんの一部の設計です。つまり、分割が発生している状態で完璧な可用性と一貫性を備えたシステムの設計です。しかし現実には、そのような設計はめったにありません。
設計者は分割が発生したとき一貫性と可用性のどちらかを選ぶ必要がありますが、分割の扱い方と分割の復旧には柔軟な対処方法があります。現在のCAPの目的は特定のアプリケーションが必要とする一貫性と可用性を最適化することでしょう。このような方法には分割発生中の計画や分割の復旧計画が組み込まれています。したがって、設計者はこのような方法を採用することで、従来受け取られてきたCAPの限界を超えてCAPについて考えることができます。
なぜ"3つのうち2つ"がミスリーディングなのか
CAPを理解する最も簡単な方法は分割の両側にひとつずつノードがある場合を考えることです。片方のノードだけ状態を更新できるようにすると、2つのノードに一貫性がなくなります。つまり、Cが失われます。一貫性を維持しようとすれば、一方のノードは利用できない状態であるかのように動作しなければなりません。この場合、Aが失われます。一貫性と可用性が維持できるのは、ふたつのノードが通信できる場合だけです。この場合、Pが失われます。一般的には、広域システムの場合、設計者はPを失えませんので、CとAの間で難しい選択を強いられます。ある意味ではNoSQLの勃興は可用性を第一優先に、一貫性を二の次にする選択肢を生み出していると言えます。ACID属性に従うデータベース(原子性、一貫性、独立性、耐久性)はこの反対です。"ACID、BASE、CAP"のセクションでこの違いを詳述します。
実のところ、この違いについての検討がCAP定理を生み出しました。1990年代中頃、私は同僚と共にさまざまなクラスタベースの広域システム(クラウドコンピューティングの先駆け)を構築していました。検索エンジンやプロキシキャッシュ、コンテンツ配信システムなどです1。収益目標と契約仕様のため、システムの可用性が第一優先になり、私たちはキャッシュを採用したり、後からのデータ復旧に使うために更新を記録したりして、可用性を最適化しました。しかし、このような方法で可用性は向上さしましたが、一貫性が犠牲になりました。
一貫性対可用性の議論の最初のバージョンはACID対BASEというかたちで現れました2。しかし、この議論は当時あまり受け入れられませんでした。皆、ACID属性を好んでおり、ACIDを諦められなかったからです。CAP定理の目的はより広く設計について探索する必要があることを示すことでした。そして、"3つのうち2つ"という公式がうまれました。CAP定理は1998年の秋に生まれ、1999年に発表され、2000年のSymposium on Principles of Distributed Computing4の基調講演での発表がきっかけで証明されました。
"CAPの混乱"セクションで説明する通り、"3つのうち2つ"はいくつかの場面でミスリーディングです。まず、分割は滅多に起きないので、分割のない状態ではCやAは失われません。次に、同じシステムの中でとても細かい粒度で何度もCとAのどちらかを選択する場合があります。サブシステムによって異なる選択をすることもできますし、操作やデータや関係するユーザによって選択を変えることもできます。最後に、3つの属性は満たす/満たせないのふたつの選択肢しかないのではなく、度合いがあります。可用性は明らかに0%から100%まで度合いがありますが、一貫性にも多様なレベルがあります。分割耐性にも同様です。システムに分割があるかどうかについての意見の相違も含んだ度合いがあります。
このような度合いを調べ、3つの属性の最適化を図る場合、分割への従来の対処法をより推し進める必要がありますが、これには根本的な困難が伴います。分割は滅多に起きないので、ほとんどの場合、完璧なCとAを実現できますが、分割が発生した場合のために、分割を検知し明示的に対処する仕組みを整えておく必要があります。この仕組みは3つのステップに分かれます。まずは分割を検知するステップ、そして、動作が制限される分割モードに明示的に移行するステップ、最後に復旧処理を起動し一貫性を復元し、分割中に発生した動作不良を補償するステップです。
ACID、BASE、CAP
ACIDとBASEは一貫性と可用性の領域の両端にある設計思想です。ACID属性は一貫性に重点を置いたデータベースの伝統的な属性です。90年代後半、私は同僚と共に、当時出現し始めていた高可用性を維持するための設計手法を捉え、一貫性と可用性の領域とその中での選択肢を明示するためにBASEを作成しました。クラウドを含む大規模広域システムは2つの方法論を混ぜ合わせて使っています。
ACIDもBASEも単語としては覚えやすいですが、BASEという頭字語は少しわかりにくいです。BASEは次の単語の頭文字を合わせています。Basically Available(基本的に利用可能)、Soft state(柔らかい状態)、Eventually consistent(最終的な一貫性)。柔らかい状態と最終的な一貫性は分割が発生した場合の対処法で、可用性を担保します。
CAPとACIDの関係は複雑で間違えやすいです。というのは、ACIDのAとCはCAPのAとCと違う概念を表しているからです。また、可用性に重点を置いてもACIDが保証する属性の一部にしか影響を与えないからです。ACIDの4つの属性とは、
原子性 (A) すべてのシステムは不可分な処理の恩恵を受ける。可用性の観点から考える場合、分割の両端のノードが不可分な処理を行う必要がある。高いレベルでの不可分な処理は復旧が容易である。
一貫性 (C) ACIDのCはトランザクションが一意キーのようなデータベースのルールを守るという意味。他方、CAPのCはデータのひとつのコピーの一貫性についてだけ言及している。つまり、ACIDの一貫性のほんの一部分なのだ。また、ACIDの一貫性は分割をまたがって維持されない。ACIDのCは分割の復旧で復元されなければならない。一般的には、分割発生中に不変式を維持するのは不可能なので、分割発生中にどの処理を行わないようにするのか、分割の復旧でどのようにして不変式を復元するのか、注意深く考えておく必要がある。
独立性 (I) 独立性はCAP定理の中核にある。ACIDの独立性を要求するシステムは、分割が発生している間、片方だけで動作することができる。しかし、直列化可能性を担保できない。通信が必要だからだ。この場合、トラザクションの正確性は分割からの復旧処理を前提として定義される。
耐久性 (D) 開発者は耐久性の維持は大変なので、柔らかい状態(BASEの)を使うことで耐久性が必要のないシステムを作ろうとするかもしれないが、原子性と同様、耐久性も失いようがない。分割からの復旧では、知らないうちに不変式を侵してしまった永続性のある処理を取り消すことができる。しかし、復旧時には分割の両側の永続性のある処理の履歴があるので、そのような処理は検知し修正できる。一般的には、分割の両側でACIDなトランザクションが実行されていれば、復旧は容易であり、分割の復旧で利用される補償トランザクションの仕組みも活用できる。
CAPと通信の遅延
通常の解釈では、CAP定理は遅延を無視しています。しかし実際には、遅延と分割には深い関連があります。CAPの本質はタイムアウトが発生した時に現れます。つまり、プログラムが分割が発生した場合の判断をしなければならない時です。すなわち、
-
処理を中断して可用性を犠牲にする。あるいは
-
処理を進めて一貫性を犠牲にする。
例えばPaxosや2フェーズコミットを使って一貫性を保証するために通信のリトライをするのは、この決定を遅らせているだけです。プログラムはどこかの時点で判断を下さなければなりません。無限にリトライを続けるのは、AよりもCを優先するということです。
実際には分割は通信上のある一定の時間幅として現れます。その一定の時間内に一貫性を保証することに失敗したということが分割の発生を示し、その処理についてCかAのどちらかを選択することになります。このような考えは遅延に関する設計上の本質的な課題を捉えます。つまり、分割の両側は通信しないで、それぞれ独立して処理を進めるかどうかということです。
この実践的な視点から考えるといくつかの重要な結論が導けます。第一に全体に適用できる分割の概念は存在しないということです。というのは、あるノードは分割を検知するかもしれませんが、別のノードは検知しないかもしれないからです。第二にノードは分割を検知すると分割モード、つまりCとAの最適化を目指すモードになるということです。
最後に、設計者は通信相手の応答時間を踏まえて意図的に時間幅を設定できるということです。この時間幅が狭いシステムはネットワークが遅いだけで、実際には分割が発生していない場合でも分割モードになってしまうかもしれません。
広域にまたがって一貫性を維持するために発生する遅延を避けるために厳密なCを諦めた方がよい場合もあります。YahooのPNUTSはリモートのコピーを非同期でメンテナンスするため、一貫性が崩れます5。しかし、マスタコピーがローカルにあるので、遅延は発生しにくいです。実際、この方法は上手く動作します。ユーザのデータが、そのユーザのいる場所によって自然に分かれているからです。各ユーザのデータマスタがそのユーザの近くにあるのは理想的です。
Facebookは反対の方法を採用しています6。マスタコピーをひとつの場所に置き、ユーザは、自分のいる場所に近いが最新でない可能性のあるコピーを利用します。しかし、ユーザがページの更新を行うと、少しの間、遅延が発生しつつも、更新も読み込みもマスタコピーに対して行われます。20秒経つと、近くにあるコピーを参照するようになります。つまり、更新が近くのコピーに反映されるまではマスタコピーを参照するのです。
CAPの混乱
CAP定理は誤解されがちです。特に可用性と一貫性の範囲については誤解が多いです。この誤解が原因で望ましくない結果になる場合があります。ユーザがサービスを全く利用できなければ、CもAも選択できません。この場合、ユーザのクライアント環境でサービスの一部を動かすしかありません。この例外処理は非接続処理やオフラインモードとして知られていますが7、次第に重要になっています。クライアント永続化ストレージのようなHTML5の機能のいくつかは、この非接続処理を容易にします。このような機能はCよりもAを優先するものであり、長時間の分割が発生した場合は復旧を行わなければなりません。
一貫性とは、ある範囲内では状態の一貫性が維持されるが、その範囲外は全く考慮されない、ということです。例えば、最優先される範囲の内部では一貫性と可用性を完全に保証できるものの、その範囲の外ではサービスが利用できない、ということです。Paxosや原子的同報通信システムはこのシナリオで利用できます8。Googleでは普通、最優先される範囲はひとつのデータセンター内で完結しています。しかし、Chubby9で使われているPaxosはグローバルなコンセンサスを確保するために広域で使われます。Megastore10の高可用永続化ストレージも同様です。
独立していて、一貫性のある部分は分割が発生しても処理を進められますが、グローバルな不変式を侵している可能性があります。例えば、シャーディングをする場合です。設計者が各ノードにデータを分けた場合、各シャードは分割が発生したときに処理を進めても問題なさそうです。反対に関連する状態が分割を横断している場合や、グローバルな不変式が必要な場合は、最高でもひとつのノードだけ処理を進めることしかできません。最悪の場合は全く処理を進められません。
"3つのうちの2つ"として一貫性と可用性(CA)を選ぶのは合理的でしょうか。一部の研究者が正しく指摘しているように、Pを失うということが正確に何を意味するのか明確ではありません11,12。設計者は分割が起こらないことを選択できるのでしょうか。CAを選び、分割が発生した場合、CかAの選択に逆戻りします。これは確率論的に考えるのが良いでしょう。CAを選ぶということは分割発生の確率を、災害や複数の問題の同時発生による障害など他の障害の発生確率よりもはるかに小さく見積もるということを意味します。
このように考えるのは意味があります。現実のシステムはある種の障害の発生が重なるとCとAを両方とも失います。つまり、3つの属性はすべて程度の問題なのです。実際にはほとんどの場合、ひとつのデータセンター内では分割は発生しないと仮定し、CAを保証する設計がされています。従来のデータベースもこのような設計になっていますが、CAPが登場するまでは既定の設計でした。しかし、ひとつのデータセンター内で分割が発生することは少ないとはいえ、可能性はあるので、CAを保証する設計は問題を孕みます。広域で遅延が発生することを前提として、より良い性能を求めるため完全な一貫性をあきらめるのが相対的に一般的な設計です。
CAPの混乱の要因は他にもあります。それは一貫性を失う場合の隠れたコストです。すなわちシステムの不変式を明らかにしなければならないということです。一貫性のある小さなシステムの美点は、設計者が意識しなくても不変式が維持できることです。反対に、設計者がAを選んだ場合、分割が発生した時に不変式を復元できるようにしておく必要があります。したがって、すべての不変式を把握しておく必要がありますが、これは難しく問題が発生しやすいです。この問題は本質的には、マルチスレッドによる並列更新を難しくしている問題と同じです。
分割に対処する
設計者にとって困難なのは、一貫性と可用性に対する分割の影響を緩和することです。その際、重要なのは分割を明示的に扱うことです。検知だけでなく、回復処理や分割によって侵された可能性のあるすべての不変式のに対する計画も明確に処理します。分割の対処法には3つのステップがあります。
(クリックして拡大)
/filters:no_upscale()/articles/cap-twelve-years-later-how-the-rules-have-changed/ja/resources/fig1large.jpg){kind=link}
- 分割の発生を検知する
- 明示的に機能制限がある分割モードになる
- 通信が復旧したら回復処理を起動する
最後のステップの目的は、一貫性を復元し、分割発生中のプログラムの失敗を補償することです。
図1は分割の進捗を表します。通常、処理は原子的でひとつずつ順に実行されます。したがって、分割は常に処理の間に発生します。タイムアウトすると、システムは分割を検知し、分割を検知した側は分割モードになります。実際に分割が発生していたら、もう一方の側も分割モードになりますが、片方だけ分割モードになることも可能です。このような場合、もう一方は必要に応じて通信をしますが、分割を検知した方は正常に応答するか、通信を要求しないかどちらかです。どちらでも一貫性は保たれます。しかし、分割を検知した方は一貫性を無視した処理が行われる可能性があるので、分割モードにならなければなりません。クォーラムを使ったシステムはこの片側分割モードのひとつの例です。片側がクォーラムを持ち、処理を続け、他は処理を続けないという方法です。非接続処理は明らかに分割モードの概念を持っています。原子的同報システムやJavaのJGroupも同様です。
システムが分割モードに突入した場合、ふたつの動作があり得ます。ひとつは処理を制限する動作で、これは可用性を下げます。もうひとつは、分割からの復旧に役に立つ処理の情報を記録する動作です。また、通信を試み続けると、システムはいつ分割が終わったのかを判断できます。
どの処理を進めるべきか
どの処理を制限するかはそのシステムが守らなければならない不変式に依存します。設計者はどの不変式を維持し、どの不変式を維持しないのか、あるいは意図的に不変式を侵害して復旧時に回復するようにするのか、決めなければなりません。例えば、あるテーブルのキーは一意であるという不変式があったとします。設計者は普通、分割モード時にはあえてこの不変式に違反し、重複キーを許します。というのは重複キーは発見するのが容易で、簡単に復旧できるからです。
しかし、設計者は分割発生中に維持しなければならない不変式を侵害する可能性のある処理は禁止したり変更をしたりする必要があります(一般的には、どの処理が不変式を侵害するのかはわかりません。分割を横断する状態がどうなっているかわからないからです)。クレジットカードの支払い処理はこのような処理制限がかけられます。この場合、処理を記録しておき分割から復旧した後で実行します。このようなトランザクションはより大きな処理の流れの一部であり、明確な発注処理状態を持ちます。また、分割が終わるまで処理が滞っても大きな問題は起きません。設計者はある意味ではAを失いますが、ユーザには見えていません。ユーザが知っているのは自分が発注をしたこととその処理が後に行われるということだけです。
一般的に、分割モードはユーザインターフェイスに難問を突きつけます。タスクは実行中だがまだ終わっていないということを示す必要があるからです。研究者は非接続処理の問題としてこの難問を探求してきました。非接続処理とは長期間の分割なのです。例えば、Bayouのカレンダーアプリケーションは矛盾している可能性の予定を異なる色で表示します13。このような表示の仕方はワークフローアプリケーションやGoogle Docsのようなオフラインモードがあるクラウドサービスで見られます。
単なる読み書きではなく、明確な原子的処理に注目するのは、その方が処理の不変式に対する影響を簡単に把握できるからです。本来、設計者はその製品のすべての処理とすべての不変式の交差表を作り、どの処理がどの不変式を侵害する可能性があるかを把握しておく必要があります。そして、分割発生時にその処理を禁止するか、遅延させるか、変更するかを決めます。実際には、この決定は既知の状態やパラメータに依存します。
分割の両側の処理の履歴を追跡するのに最適な方法はバージョンベクタを使う方法です。バージョンベクタは処理間の因果関係を捉えます。ベクタは一組(ノードと論理時間)を持ち、ひとつのエントリはあるオブジェクトをアップデートしたすべてのノードと更新時の論理時間の組を持ちます。例えば、2つのオベブジェクトAとBがあり、すべてのノードのベクタでAがBよりも新しい場合、すべてのベクタのAの論理時間はBと等しいかBよりも大きい、少なくともひとつのベクタのAの論理時間はBよりも大きいことがわかります。
ベクタを順に並べられない場合、更新は並列で行われ、一貫性が崩れている可能性があります。分割の両側のバージョンベクタの履歴を使うことで、どの処理が既定の順で処理され、どの処理が並列実行されたか簡単に把握できます。最近の研究では14、設計者が可用性を最優先にする場合、このような因果関係の一貫性を保証することが最良の結果であることを証明しています。
分割の復旧
どこかの時点で通信は再開し、分割は終わります。分割の間、分割の両側は動作しており処理を続けていましたが、いくつかの処理は遅延し、いくつかの不変式は成立しなくなっています。このとき、システムは両側の状態と履歴を知っています。分割発生中の詳細なログを保持しているからです。状態より履歴の方が役に立ちます。システムは履歴からどの処理が不変式を侵害し、何が起きたのか推測できます。ユーザへの返答内容なども確認できます。復旧時には設計者はふたつの難問を解決しなければなりません。
- 分割の両側を一貫性を保持した状態にすること
- 分割モード時の処理失敗を補償すること
一般的には、分割発生時の状態から、一貫性を維持できる一定の順で処理を再実行することで、現在の状態を正しくするのが簡単な方法です。Bayouはデータベースをある時間までロールバックして確定的な順ですべての処理を再実行することで、すべてのノードが同じ状態に到達するようにします15。Concurrent Versioning System (CVS)のようなソースコード管理システムも同様に、一貫性がある時点からロールフォワードして更新を再実行しブランチをマージします。
ほとんどのシステムは常に競合を解決できるわけではありません。例えば、CVSではユーザが手動でマージを行わなければならない競合があります。オフラインモードがあるウィキシステムも手動で編集しなければならない競合が発生します16。
反対に、分割発生中の処理を選択することで常に自動的に競合をマージできるシステムもあります。例えば、Google Docs17のテキスト編集は分割発生時は、スタイルの適用とテキストの追加と削除しかできません。このような方法は競合の一般的な問題を解決しませんが、実際には分割時の処理を制限することでシステムは自動的に状態をマージすることができます。危険な処理を遅延させるのはこのような方法の比較的簡単な実装です。
自動的に状態を修復する汎用的な方法に最も近いのは交換可能な処理を使う方法です。システムは処理の履歴を連結し、一定の順に並び替えて実行します。処理が交換可能であるということは、処理を望ましい順に並び替えられるということです。残念ながら交換可能な処理は実現するのが難しいです。例えば、追加処理は交換可能ですが、境界値チェックを伴う追加処理は交換可能ではありません。
INRIAのMarc Shapiro氏らの最近の研究は18,19状態復旧のための交換可能な処理の利用を大きく改善しました。研究チームは可換複製データ型(commutative replicated data types、CRDT)を開発しました。このデータ型は分割後に収斂し、このデータ型を使って下記を実現する方法を記述します。
- 分割時のすべての処理の交換可能性を保証する。または、
- 束(lattice)上に値を表現して、分割発生中のすべての処理でその束の値が単純に増加することを保証する
２番目の方法は分割の両側の値を最大まで動かすことで状態を復旧する方法です。これはAmazonが買い物かごで実現している方法を定式化し改善したものです20。分割が終わった後、2つの買い物かごはある一定の処理の組み合わせを適用することで復旧状態になります。この方法の場合、削除した商品が復活してしまうかもしれません。
しかし、CRDTは、分割耐性があり商品の追加と削除ができる集合を実装できます。この方法の重要な点はふたつの集合を扱うということです。それぞれの集合は収束します。ふたつの集合の差も同様です。システムはどこかの時点で両方の集合から削除された商品を取り除きます。しかし、分割が発生していないときでないとこの処理はできません。言い換えれば、分割発生中は禁止するか延期しなければならない処理があるものの、それは可用性を毀損しないということです。このようにCRDTを使って状態を実装することで、設計者はAを担保しながら自動的に状態を復元することができます。
処理失敗を補償する
分割後の状態の復旧に加え、分割モードの間の処理失敗を補償するという難しい問題があります。分割モード時の処理の追跡と処理の制限のおかげで、どの不変式が侵されているかがわかるので、設計者は不変式の復旧方法を作成できます。普通、システムは分割復旧時に侵害された不変式を見つけ、そのときに修正をしてしまいます。
不変式侵害の修正にはさまざまな方法があります。"最後の書き込み勝ち"(いくつかの更新が無視される)というようなありふれた方法や、マージ処理よりも賢い方法、人間に通知して解決する方法などさまざまです。人間に通知する方法の例としては、飛行機のオーバーブッキングがあります。オーバーブッキングが発生している飛行機への搭乗はある意味では分割の復旧です。この復旧は飛行機の座席の数と乗客の数が一致していなければならないという不変式を伴います。もし乗客が座席の数より多い場合、誰かの座席がありません。この場合はカスタマーサービスが座席がない乗客に何らかの補償を行います。
この飛行機の例は外部化された処理失敗の例でもあります。もし、航空会社が乗客に座席があると伝えていなければ、修正はもっと簡単でしょう。危険な処理を遅延される理由はここにもあります。つまり、復旧時には、真実がわかっているのです。補償の概念はこのような処理失敗で最も重要です。設計者は不変式を復旧し、外部化された失敗を補償する処理を作成する必要があります。
技術的にはCRDTはローカルで検証できる不変式のみ許容します。この制限は補償の不必要にしますが、同時にこの技術の力を多少弱めます。CRDTを使った状態復元方法はグローバルな不変式を一時的に侵害する可能性があるものの、分割が終わった後に状態の復元を行い、必要な補償処理を実行します。
外部化された処理失敗の復旧は外部への出力の履歴が必要です。例えば、泥酔して電話してしまった場合を考えましょう。ある人は前の晩、泥酔している間にいろいろな人に電話をかけてしまいましたが覚えていません。翌日の彼の状態は問題ないかもしれませんが、電話の発信履歴は残っています。この中のどれかの発信が何らかの問題を引き起こしたかもしれません。この発信は彼の状態(泥酔)の外部効果です。彼は覚えていないので、何かの問題が起こったとしても補償するのは難しいでしょう。
コンピューターは分割発生中に同じ処理を2度実行する可能性があります。システムが意図的に2回処理している場合と、処理が重複してしまっている場合を区別できれば、重複した処理をキャンセルできます。失敗が外部化されてしまったら、顧客にメールを自動送信し、システムトラブルが原因で処理を2回してしまったがこの処理ミスは既に修正していることを説明し、次の買い物で使える割引クーポンを送付すればいいでしょう。しかし、適切な処理履歴がなければ、処理ミスの不都合は顧客に転嫁されてしまいます。
長時間のトランザクションを扱うために補償トランザクションを研究している研究者もいます21,22。長時間のトランザクションの場合、分割時の意思決定も変わります。一貫性を保証するためにロックを保持し続けた方がいいのか、それとも早くロックを解放して他のトランザクションがコミットされていないデータをわかるようにして、並列処理を許した方がいいのか。一般的なのは、ひとつのトランザクションですべてのレコードを更新しようとする方法です。トランザクションを一般的な方法で直列化すればすべてのレコードをロックし、並列処理を避けることができます。補償トランザクションはこの方法とは違います。補償トランザクションを使う場合、大きなトランザクションは複数のサブトランザクションに分割し、それぞれが途中でコミットします。大きなトランザクションをアボードするには、システムは新しいトランザクションを発行してすでにコミットされているサブトランザクションを取り消さなければなりません。この時の新しいトランザクションが補償トランザクションです。
この方法の場合、不正にコミットされたデータを使っている他のトランザクションがアボードされないようにします。この方法の正確さは直列性や独立性ではなく、一連のトランザクションの、状態や出力への影響に依存します。つまり、補償が完了した後のデータベースの状態がサブトランザクションに分割しないで大きなトランザクションを実施した場合の状態と同じかどうかが重要なのです。外部に対する処理も同じになっている必要があります。例えば、重複した購入処理を払い戻すことは、そもそも重複して請求しないことと同一の処理ではありませんが、外部からは同じに見えます。分割の復旧も同じように考えられます。サービスや製品の提供側は常にミスを直接修正できるとは限りません。しかし、ミスを認め補償することはできます。この考えの分割復旧への最も優れた応用方法は未だに見つかっていません。"現金自動預け払い機の補償問題"というセクションで、ひとつのアプリケーションを題材にこの問題について説明します。
システムの設計者は分割発生時に何も考えずに一貫性や可用性を犠牲にしてはなりません。上述した方法を使い、不変式を丁寧に管理することで、両方の属性を最適化できます。バージョンベクタやCRDTのような新しい技術が簡単に使えるフレームワークに組み込まれるにしたがって、このような最適化はより一般的になるでしょう。しかし、ACIDとは違い、この方法は過去の方法と比べてより注意深く適用する必要があります。そして、最良の解決策はそのサービスの不変式と処理の詳細に依存します。
現金自動預け払い機の補償問題
現金自動預け払い機(ATM)の設計では、厳密な一貫性が選択されているように思えますが、実際にはCよりもAに重点が置かれています。理由ははっきりしています。可用性が高ければ、利益も上がるからです。いずれにしろ、ATMの設計は分割時の不変式侵害の補償に伴う難題を説明するのにちょうどいい題材です。
ATMの主な処理は入金、引き出し、残高照会です。重要な不変式は残高が0以上であることです。この不変式を侵害するのは引き出し処理だけなので、引き出し処理には特別な配慮が必要ですが、他の2つの処理は常に実行できます。
ATMの設計者は分割発生中は引き出し処理を出来ないようにすることもできます。分割発生中は本当の残高がわからないからです。しかし、この方法は可用性を毀損する可能性があります。代わりに現在のATMはスタンドインモード(分割モード)を使って、引き出し金額に上限を設定します。例えば引き出し金額の上限総額200ドルにします。分割発生中はこの上限以下の金額を引き出すことができます。上限に達すれば、システムは引き出し処理を拒否します。ATMはこのような方法で可用性を制限してリスクを限定的にしつつ、引き出し処理自体は許すことができます。
分割が終わった時、一貫性を復元する方法と分割中の処理失敗を補償する方法が必要です。状態を復元するのは簡単です。処理が交換可能だからです。しかし、補償にはいくつかの方法があります。最終的な残高が0を下回ることは不変式侵害です。通常、この不変式侵害が外部に発覚するのはATMがお金を分配するときです。銀行は、手数料と返済を請求することで補償をします。この場合、リスクは限られているので問題は深刻になりません。しかし、分割発生中のある時点で残高が0を下回り、その後、振り込みによって0以上になった場合は厄介です。この場合、銀行は過去にさかのぼって貸し越し金額を請求するかもしれません。また、顧客がすでに必要な支払いを済ませている場合は不変式の侵害を無視するかもしれません。
一般的には、通信を遅延させるため、銀行システムは正確さのための一貫性に依存しません。むしろ、監査と補償に依存します。例えば、"入金当て込み小切手振り出し"の場合、顧客は複数の支店からお金を引き出し、支店同士が通信する前に逃げてしまいます。この場合、貸し越しは後になって発覚し、何らかの法的な補償がなされるでしょう。
謝辞
Mike Dahlin氏、Hank Korth氏、Marc Shapiro氏、Justin Sheehy氏、Amin Vahdat氏、Ben Zhao氏、そしてIEEEコンピュータソサエティの皆さんの親切なフィードバックに感謝します。
著者紹介
Eric Brewer氏はカリフォルニア大学バークレー校のコンピュータサイエンスの教授であり、Googleのインフラストラクチャ部門のバイスプレジデント。クラウドコンピューティングやスケーラブルサーバー、センサーネットワーク、開発地域の技術などを研究している。また、連邦政府の公式ポータルUSA.govの作成も支援した。MITから電子工学とコンピューターサイエンスの分野でPhDを授与されている。全米技術アカデミーのメンバー。連絡先はbrewer@cs.berkeley.edu
ComputerはIEEEコンピュータソサエティの旗艦誌。ハードウエアからソフトウエアまで、現在の研究から最新の応用例まで、専門家が書き、専門家が査読したコンピュータ技術に関するあらゆる領域の記事が掲載される。業界誌よりも専門的で、研究誌よりも実践的な内容を掲載している。Computerは日々の仕事に適用できる有用な情報を提供している。
参考
1. E. Brewer, "Lessons from Giant-Scale Services," IEEE Internet Computing, July/Aug. 2001, pp. 46-55.
2. A. Fox et al., "Cluster-Based Scalable Network Services," Proc. 16th ACM Symp. Operating Systems Principles (SOSP 97), ACM, 1997, pp. 78-91.
3. A. Fox and E.A. Brewer, "Harvest, Yield and Scalable Tolerant Systems," Proc. 7th Workshop Hot Topics in Operating Systems (HotOS 99), IEEE CS, 1999, pp. 174-178.
4. E. Brewer, "Towards Robust Distributed Systems," Proc. 19th Ann. ACM Symp.Principles of Distributed Computing (PODC 00), ACM, 2000, pp. 7-10; on-line resource.
5. B. Cooper et al., "PNUTS: Yahoo!’s Hosted Data Serving Platform," Proc. VLDB Endowment (VLDB 08), ACM, 2008, pp. 1277-1288.
6. J. Sobel, "Scaling Out," Facebook Engineering Notes, 20 Aug. 2008; on-line resource.
7. J. Kistler and M. Satyanarayanan, "Disconnected Operation in the Coda File System" ACM Trans. Computer Systems, Feb. 1992, pp. 3-25.
8. K. Birman, Q. Huang, and D. Freedman, "Overcoming the ‘D’ in CAP: Using Isis2 to Build Locally Responsive Cloud Services," Computer, Feb. 2011, pp. 50-58.
9. M. Burrows, "The Chubby Lock Service for Loosely-Coupled Distributed Systems," Proc. Symp. Operating Systems Design and Implementation (OSDI 06), Usenix, 2006, pp. 335-350.
10. J. Baker et al., "Megastore: Providing Scalable, Highly Available Storage for Interactive Services," Proc. 5th Biennial Conf. Innovative Data Systems Research (CIDR 11), ACM, 2011, pp. 223-234.
11. D. Abadi, "Problems with CAP, and Yahoo’s Little Known NoSQL System," DBMS Musings, blog, 23 Apr. 2010; on-line resource.
12. C. Hale, "You Can’t Sacrifice Partition Tolerance," 7 Oct. 2010; on-line resource.
13. W. K. Edwards et al., "Designing and Implementing Asynchronous Collaborative Applications with Bayou," Proc. 10th Ann. ACM Symp. User Interface Software and Technology (UIST 97), ACM, 1999, pp. 119-128.
14. P. Mahajan, L. Alvisi, and M. Dahlin, Consistency, Availability, and Convergence, tech. report UTCS TR-11-22, Univ. of Texas at Austin, 2011.
15. D.B. Terry et al., "Managing Update Conflicts in Bayou, a Weakly Connected Replicated Storage System," Proc. 15th ACM Symp. Operating Systems Principles (SOSP 95), ACM, 1995, pp. 172-182.
16. B. Du and E.A. Brewer, "DTWiki: A Disconnection and Intermittency Tolerant Wiki," Proc. 17th Int’l Conf. World Wide Web (WWW 08), ACM, 2008, pp. 945-952.
17. "What’s Different about the New Google Docs: Conflict Resolution" blog.
18. M. Shapiro et al., "Conflict-Free Replicated Data Types," Proc. 13th Int’l Conf. Stabilization, Safety, and Security of Distributed Systems (SSS 11), ACM, 2011, pp. 386-400.
19. M. Shapiro et al., "Convergent and Commutative Replicated Data Types," Bulletin of the EATCS, no. 104, June 2011, pp. 67-88.
20. G. DeCandia et al., "Dynamo: Amazon’s Highly Available Key-Value Store," Proc. 21st ACM SIGOPS Symp. Operating Systems Principles (SOSP 07), ACM, 2007, pp. 205-220.
21. H. Garcia-Molina and K. Salem, "SAGAS," Proc. ACM SIGMOD Int’l Conf. Management of Data (SIGMOD 87), ACM, 1987, pp. 249-259.
22. H. Korth, E. Levy, and A. Silberschatz, "A Formal Approach to Recovery by Compensating Transactions," Proc. VLDB Endowment (VLDB 90), ACM, 1990, pp. 95-106