クラウドの技術的な特徴について

丸山先生のジェネラルセッション。内容的にはEric Brewerの資料（CAP Theorem/Eventually Consistent）をクラウドの立場から眺める、といったもの。

ScalabilityとAvailability
Scalabilityは、Scal-outによって達成できるが、Scale-outには技術的な裏打ちが必要であり、ノウハウの蓄積が必要。
Availabilityは、故障に対する適切な対処によって達成できるが、これには複製を作成する戦略（Replication）が基本になる。複製を作ってしまうと、同期の問題、すなわち一貫性に関する問題が発生する。

[メモ]
CAP定理で言うと、ScalabilityがおおよそPartitionに、AvailabilityがそのままAvailabilityに、一貫性がConsistencyにあたると考えてよいと思う。上記は、クラウドにおけるCAPの関係をわかりやすく説明してくれていると言える。

Partitionが必須となる背景
High-endコンピュータとCommodityコンピュータの価格性能比は、約1:33。経済的な選択をすると、必然的にPartitionを選択することになる。安いハードウェアはそれなりの能力しか持たないが、障害に強いソフトウェアが、安いハードウェアを役に立つものに変える。

[メモ]
ただし、よくよく考えると、Partitionと、Partition度合いを容易に増減できるかどうか（=Scalability）は、違った特性のようにも思える。セミナーでも、一口にクラウドといっても、リソースを動的に増減できるもの（Hot Scalable）とできないものとできないもの（静的にのみ可能、Scalable）がある、と言っている。

CAP定理とクラウド
これは、共有データを持つシステムにおいては、Consistency, Availability, Partitionの3つのうち、最大でも2つの特性しか持つことができない、というもの。
クラウドではPartitionは必須になるため、ConsistencyかAvailabilityのどちらかを選ばなければならない。…が、この選択はシステム全体に一律に適用しなければならないわけではない、というのが重要な点。単一のシステム内でも、カートに商品を入れる段階ではAvailabilityを優先し、注文の段階では一貫性を優先する、といったように、部分ごとに必要となる特性は変わる。

また、上記でAvailabilityを「優先する」と書いたように、AとCはどちらかを取ればもう一方が完全に失われる、というものではなく、AとCの配分には中間的な選択肢が数多く存在する。特に、Consistencyにはいくつかのレベルがあり、これには名前もつけられているようだ。以下、結城さんの翻訳サイトからの引用。

• 強い整合性(Strong consistency): 更新が完了したら, 続くアクセス(A, B, C いずれかによる) は更新された値を読み出す
• 弱い整合性(Weak consistency): システムは続くアクセスが更新された値を読みだすことを保証しない. 更新した値が返される前には様々な条件を満たす必要がある. 多くの場合, その条件は経過時間である. 更新された時刻から更新した値の読みだしを観測者に保証するまでの間隔を 不整合ウィンドウ(inconsistency window) と呼ぶ.
• 結果整合性(Eventual consistency): ストレージシステムは, オブジェクトに(不整合ウィンドウが閉じたあとも)最後まで変更が加えられなかったなら, 全てのアクセスが最後の更新値を読みだせると保証する. 結果整合性を実装する最もよく知られたシステムは DNS だ. 名前の更新は分散しており, 設定のパターンやキャッシュ制御の組合せで振舞いがかわる. クライアントは最終的に更新された値を見ることになる.

さらに結果整合性にも細かなバリエーションがあるらしい。

• 因果整合性(Causal consistency): プロセス A がプロセス B と通信を行い, その B がデータ要素を更新したとき, B が続けてアクセスをすると更新された値が戻る. また書込みはその前の書込みを上書することが保証される. プロセス A と因果関係をもたないプロセス C は通常の因果整合性に従う.
• Read-your-wrie consistency: このモデルは重要だ. プロセス A が書込みをしたとすると, そのあと A は常に更新された値にアクセスできる. 古い値は決して見えない. これは因果整合性の特別な場合だ.
• セッション整合性(Session consistency): 上のモデルの実用的なバージョン. プロセスはあるセッションの下でストレージシステムにアクセスする. セッションのある間, システムは Read-your-wrie consistency を保証する. 何らかの故障シナリオでセッションが破棄された場合は新たに作りなおす必要がある. また保証はセッションをまたがない.
• 単調読み出し整合性(Monotonic read consistency)： もしプロセスがオブジェクトからある値を読みだしたら, それ以降にはより古い値を読み出さない.
• 単調書き込み整合性(Monotonic write consistency): この場合はシステムが同じプロセスからの書込みが直列化されるよう保証する.このレベルの保証をもたないシステムでプログラムを書くのは難しいことで悪名高い.

クラウドの場合にConsistencyが問題になるのは、複数ノードへの書き込み（失敗）のケース。書き込み失敗時の対処としては、リトライや、失敗したノードの切り離しがあげられる。一定回数リトライし、それでもダメだった場合にはノードを削除することで、一定時間後にはシステム内は整合性が保たれた状態になる。これが、（クラウドにおいて）Eventually Consistentレベルの一貫性の実現方法の概要。

このような、リトライやノード削除の機能は、従来データベース製品が担っていたのだが、これらは本来OSが担っても良い部分。現段階でこの部分をOSが担っていないのは、単に歴史的な経緯によるものだと思われる。少なくともクラウドの分野では、OSとデータベースの統合がはじまっている。

このような、厳密にACIDを満たさないような新たなトランザクションモデルをBASE(Basically Available, Soft-state, Eventually-Consistent)と言う。ACIDはデータベース製品などが担当する比較的局地的なトランザクションモデルであるのに対し、BASEはもう少し広い、システムレベルのトランザクションモデルらしい。

Soft-State
分散システムにおいて、状態を完全に守りきるのは不可能。丸山先生の説明はよくわからなかったので、ネットで調べてみると、こんなのがでてきた。ステートと状態がかぶっているのが気になるが、丸山先生よりわかりやすかった。

ハード・ステート状態管理
　データ通信を管理する方法の一種。一般に、通信中のコンピュータが通信プログラムを終了する際に、「デー タ通信の終了」を通知しないと、それが正常に終了したのかどうか相手にわかりません。このため、通信プログラムの動作には高い信頼性がもてません。これに 対して、「データ通信の終了」を相手に通知してから終了するようなプログラムであれば、そのコンピュータの動作には高い信頼性が期待できます（終了通知な しに終了すれば事故だとわかる）。したがって、このようなプログラムに対しては、通信を始めるときにだけ状態を確認しておけば、以降の動作には信頼性がも てます。
　このように、通信の開始のときだけ相手プログラムの動作を確認するデータ通信管理手法を、ハード・ステート状態管理と言います。既存の 電話システムが、この例です。反対語は、通信中に絶えず相手の動作を確認するソフト・ステート状態管理で、インターネットがこれに当たります。

Eventually Consistency by Example
さて、ここで、2つのシステム要素（A, B）を持つ分散システム上で、システムAが自身の状態を更新し、その状態をもとにBの状態を更新するケースを考えてみる。
極端な例として、システム要素AとBが銀河をまたいで離れているようなケースを考えると、光速度の制約があるため、Aの状態変更とBの状態変更をACIDに行おうとすると、使い物にならなくなってしまう。この場合、まずはAの状態を（ACIDに）変更し、その後でBに状態変更を通知するのが現実的になるだろう。この際、Aが通知を送ってからBに届くまでの間、システムは不整合な状態となる。Bに通知が届いた後は整合性を回復したと考えることができ、Eventually Consistentとなる。逆にこうした動作を前提にすると、ACIDトランザクションをコーディネートするようなTransaction Managerは不要になる。

こうした状況を現実の分散システムにあてはめて考えてみると、ACIDトランザクションはBASE(Eventually Consistent)トランザクションの特殊な形態（Consistencyをほぼ完全に満たすことができるケース）とみなすことができる。

クラウドにおける排他戦略
悲観ロックより楽観ロックだよね、という話。Scalabilityのためには楽観ロック。ある意味当たり前？

クラウドと永続化
クラウドのようなシステムのノードは、落ちることなく動き続ける。であれば、メモリもPersistencyを担うことができるのではないか？という発想が出てくる。となると、DBのインデックスのようなものはハッシュテーブルとして実装されることになり、自然に分散ハッシュテーブル（Distributed Hash Table）への注力へとつながっていくことになる。

現実のEnterprise SystemへのEventually Consisitency概念の応用
システム全体を単一のトランザクションモデル（特にACID/Immediate Consistency）でカバーするのではなく、ケースに応じて一貫性レベルを選択することで、PartitionやAvailability、特にPartitionを増すことができる。こうした形で応用すると良いのではないか、みたいな話だった。
Eventually ConsistentやSoft Stateは、情報システムにおける物理的な限界点を示したものであり、基本原理となるため、考慮するのは必然、といった話もちらっと最後に出てきていた。

目次：
QCon Tokyo 2009に行ってきた