原題：BASE: An Acid Alternative 著者：Dan Pritchett, eBay 原文: BASE: AN ACID ALTERNATIVE - ACM Queue (PDF Version)
This article is translated by @ono_matope. Please contact me if any problem.
この10年でWebアプリケーションの人気は上昇しました。あなたが構築しているものがエンドユーザー向けのアプリケーションであれアプリケーション開発者向けのもの(つまり、サービス)であれ、あなたの希望はおそらくアプリケーションが普及することで、そして普及はトランザクション量の増加を伴うことでしょう。もしあなたのアプリケーションが永続性に頼っているなら、データストレージはおそらくボトルネックになるでしょう。
アプリケーションをスケールするには二種類の戦略があります。一つ目の、そしてかなり簡単なものは、垂直スケーリングです。これはアプリケーションを大きなコンピューターに移動するというものです。垂直スケーリングはかなりうまくいきますが、いくつかの制約があります。最も明らかな制約は、利用可能なシステムの最大容量を超過してしまうことです。垂直スケーリングはまた、トランザクション能力を追加するには通常さらに大きなシステムを購入する必要があるため、高価でもあります。垂直スケーリングはしばしばコストの追加以上にベンダーロックインも作り出してしまうこともあります。
水平スケーリングはより高い柔軟性を提供しますが、同時にかなり複雑でもあります。水平データスケーリングは2つの方向性にそって実施されます。機能的スケーリングはデータの機能によるグループ化と、その機能グループのデータベース間の分配を伴います。機能分野内部でデータを複数のデータベースまたはシャーディング(※1)分割することは、水平スケーリングに次の次元を追加します。figure 1の図は水平データスケーリング戦略を説明したものです。
Figure1が図解するように、水平スケーリングへの二つの手法は同時に適用することができます。ユーザー、製品、トランザクションはデータベース分割できます。さらに、それぞれの機能分野はトランザクション能力のために複数データベースにわたって分割することができます。図のように、機能分野はお互いに独立してスケール可能です
機能パーティショニングは高度なスケーラビリティを得るために重要です。よいデータベースアーキテクチャはみなスキーマを機能でまとめたテーブルに分解しています。ユーザ、製品、トランザクション、そしてコミュニケーションは機能分野の例です。外部キーのようなデータベースの概念の利用は、機能分野にまたがって一貫性を保つために一般的な手法です。
機能グループにまたがる一貫性の確保をデータベース制約に頼ると、スキーマとデータベースデプロイ戦略との結合を生み出してしまいます。制約を適用するには、それらのテーブルは単一のデータベースサーバーに所属していなければならず、これはトランザクション量の成長にともなう水平スケーリングを阻害します。
非常に高いトランザクションボリュームにスケール可能なスキーマは、機能的に異なるデータを異なるデータベースサーバーに配置するでしょう。これはデータの制約をデータベースからアプリケーション側に移すことを必要とします。これは、この記事の後半で示すいくつかの挑戦を導入することにもなります。
カリフォルニア大学バークレイ校教授ででありInktomiのチーフサイエンティストかつ共同設立者のEric Brewerは、Webサービスは次の３属性全てを同時に満たすことはできないという(CAP定理として知られる)予想を立てました。(※2)
Consistency(一貫性)。クライアントには、命令セット全てが一度に起こったように知覚される
Availability(可用性)。全てのオペレーションは意図されたとおりのレスポンスを返却しなければならない
Partition tolerance(分割耐性)。オペレーションはたとえそれぞれのコンポーネントが利用不可能になっていようと完了するであろう
特に、Webアプリケーションはどのようなデータベース設計であろうと、これら3属性のうち2つまでしかサポートできません。どのような水平スケーリング戦略も明らかにデータ分割に基づいているので、設計者は一貫性と可用性のどちらか一つを選択することを強いられています。
ACIDデータベーストランザクションはアプリケーション開発者の仕事を非常に簡単にしました。頭文字ACIDとして知られるトランザクションは次の保証を提供します。
Atomicity(原子性)。トランザクション中の全てのオペレーションは完全に完了するか、まったく実行されないかのどちらか
Consistency(一貫性)。データベースはトランザクションの開始時と終了時に矛盾のない状態を保つ
Isolation(孤立性)。トランザクションはそのデータベース上で実行された単一のオペレーションであるかのように振る舞う
Durability(永続性)。トランザクションが完了したら、オペレーションは取り消されない
データベースベンダーは以前からデータベース分割の必要性を認め、複数データベースインスタンス間でACIDを保証するために2PC(二相コミット)として知られる技術を導入してきました。そのプロトコルは2フェーズに分解されます。
- まず、トランザクションコーディネーターが関連するそれぞれのデータベースにオペレーションのprecommitを依頼し、commitが可能かどうかを示します。もし全てのデータベースがcommitの続行に同意したら、フェーズ2が開始されます。
- トランザクションコーディネーターは各データベースにデータのコミットを依頼します。
もしデータベースのいずれかがcommitを拒否したら、全てのデータベースはトランザクション部分をロールバックするよう依頼されます。なにが問題なのでしょうか？我々はパーティションをまたがって一貫性を手に入れました。もしBrewerが正しいのなら、我々は可用性を犠牲にしているはずです、しかしそれはどのように起こっているのでしょう？
どのようなシステムでも可用性とは、オペレーションに必要なコンポーネントの可用性の積です。この文の最後の部分がもっとも重要です。システムによって使われうるが必須ではないコンポーネントはシステム可用性を下げません。2PCコミットで二つのデータベースをまたいだトランザクションの可用性は、各データベースの可用性の積になるでしょう。例えば、各データベースの可用性をが99.9と想定するとき、トランザクションの可用性は99.8%となり、月間に43分のダウンタイムが追加されます。
もしACIDが分散データベースにおいて一貫性の選択を提供するなら、代わりに可用性を達成するにはどうしたらいいでしょう？ひとつの回答はBASE(basically available, soft state, eventually consistent)です。
BASEはACIDとは正反対です。ACIDの立場は悲観的で全てのオペレーションの終わりに一貫性を強制しますが、BASEは楽観的で、データベース一貫性が流動的な状態になることを受け入れます。これではうまく処理するのは不可能に思えますが、実際にはまったく対処可能であり、ACIDでは得られなかったスケーラビリティのレベルに導くのです。
BASEの可用性はシステム全体の障害を含まない部分的な障害をサポートすることで得られます。ここに簡単な例を示します：もしユーザーが5つのデータベースサーバーに分割されていたら、BASEの設計は、ユーザーデータベースの障害がユーザーの当該ホストに乗っている20%にしか影響がでないようにオペレーションを作りこむことを推奨します。ここには特に魔法はありませんが、これはシステムの見た目の可用性を高めるものです。
さて、今やあなたはデータを機能的なグループに分解し、最も忙しいグループを複数のデータベースに分割しましたが、どのようにBASEをあなたのアプリケーションに組み込めばいいでしょうか？BASEは、典型的なACIDを適用するよりも深い論理トランザクションに関するオペレーションの分析を必要とします。何を探せばいいのでしょう？次の章ではいくつかの方向性を示します。
Brewerの予測に従うなら、もしBASEが分割されたデータベースにおいて可用性を許可するなら、反対に一貫性を緩和することが定められています。これはまた、ビジネス経営者と開発者の両者とも、アプリケーションの成功には一貫性が最も重要であると主張する傾向にあるため困難です。一時的な非一貫性はエンドユーザーから隠せないので、エンジニアリングもプロダクトオーナーも一貫性を緩和する機会の選択に巻き込まれます。
Figure 2はBASEの一貫性の考え方を示す単純なスキーマです。userテーブルは売却と購入の総量を含むユーザー情報を保持します。これらは累計数です。transacionテーブルは売り手と買い手、それと取り引きの量を示す各取り引き情報を持ちます。これらは現実のテーブルのひどく簡略化したものですが、一貫性の幾つかの側面を示すのに必要な要素を備えています。
一般的に、機能的なグループをまたいだ一貫性は機能的グループ内よりも緩和しやすいです。例に挙げたスキーマはusersとtransactionsのふたつの機能的グループをもちます。アイテムが売れるたび、transactionテーブルに1行追加され、売り手と買い手のカウンターが更新されます。ACIDスタイルのトランザクションを使うと、SQLはfigure 3のようになります。
userテーブルの購入総数及び売却総数のカラムはtransactionテーブルのキャッシュと考えることができます。それはシステムの効率性を持続します。このことを考慮に入れると、一貫性制約を緩和することができます。売り手と買い手の期待は設定可能なので、彼らの総残高はトランザクションの結果を即座に反映している必要はありません。これは特殊なことではなく、実際みなさんはこのトランザクションと累計の間の遅延に日常的に直面しています(例えば、ATMの引き出しや携帯電話の呼び出しなど)。
一貫性を緩和するためにSQLステートメントがどのように修正されるかは、総残高がどのように定義されているかに依存します。もしそれらが単に概算であれば、いくらかのトランザクションを消失しても良いことになり、変更はFigure 4に示すように、至って単純になります。
これでuserテーブルとtransactionテーブルの更新が分離しました。テーブル間の一貫性は保証されません。実際には、一つ目と二つ目のトランザクションの間での障害は永続的な非一貫性を引き起こしますが、もし総残高が概算であると契約が規定していれば、かろうじて許せるかもしれません。
それでは概算が許容できなければ？それでもまだユーザーと取り引きの更新を分離できるでしょうか？永続的メッセージキューの導入がこの問題を解決します。永続メッセージを実装するにはいくつかの選択が伴います。しかし、キューの実装について最も重大な要素はその永続化バックエンドが確実にデータベースと同一リソース上になくてはならないということです。これはキューが2PCを伴わずにトランザクショナルにコミットされるために必要です。これで、SQLオペレーションは少し変わってFigure 5のようにになります。
この例は、コンセプトを伝えるために文法をいくらか勝手に書き換えており、ロジックは簡略化し過ぎています。Insertと同じトランザクション内で永続的メッセージをキューイングすることで、ユーザーの総残高を更新するために必要な情報は獲得されています。トランザクションは単一のデータベースインスタンスに収納されるので、システムの可用性に影響を与えません。
独立したメッセージ処理コンポーネントは各メッセージをデキューしてユーザーテーブルへの情報を適用するでしょう。例はすべての関心事を解決するように見えますが、問題があります。メッセージ永続性はキューイング期間中の2PCを避けるためにtransactionホスト上にあります。もしuserホストに関わるトランザクションの内部でメッセージがデキューされたら、私たちは依然として2PCな状況に陥ります。
メッセージ処理コンポーネントにおける2PCの解決策の一つは、なにもしないことです。更新を別々のバックエンドコンポーネントに分割することで、顧客に面したコンポーネントの可用性は保護されます。メッセージプロセッサの低い可用性はビジネス要件的に許容出来るかもしれません。
しかしながら、2PCが単純にあなたのシステムで許容できないと想定しましょう。この問題をどう解決しましょうか。最初に、冪等性(idempotence)という概念を理解してもらう必要があります。そのオペレーションが一度適用されても複数回適用されても同じ結果になるのなら、冪等であると考えられます。冪等性オペレーションは、適用の繰り返しがシステムの最終的な状態を変えないので、部分的障害を許容する場合に便利です。
選んだ例は冪等性を見出すには問題があります。更新オペレーションが冪等であることは稀です。例は残高カラムをその場で(in-placeに)増分します。このオペレーションの一回以上の適用は明らかに正しくない残高になります。単純に値をセットする更新オペレーションでさえ、しかしオペレーションの順序に関しては冪等ではありません。もし更新が受信した順序で適用されることをシステムが保証できないなら、最終的な状態は不正になるでしょう。詳しくはあとで述べます。
残高更新の場合、どの更新が成功裏に適用され、どれがまだ未決済かを追跡する方法が必要です。ひとつのやり方は、適用済みのトランザクション識別子を記録するテーブルを使うことです。
Figure 6で示すテーブルは残高が更新されたトランザクションIDと残高が適用されたuser IDをトラッキングします。私たちのサンプル擬似コードはfigure 7のようになります。
この例は、キュー内のメッセージを盗み見して、処理が成功したらそれを除去できることに依存しています。これは、必要であれば二つの独立したトランザクションで実行できます：ひとつはメッセージキュー上の、もうひとつはユーザーデータベース上のものです。キューオペレーションはデータベースオペレーションのコミットが成功しないとコミットされません。これでアルゴリズムは部分障害をサポートし、2PCの助けなしに依然としてトランザクション保証を提供します。
関心事が順序だけであれば、冪等更新を保証するもっとシンプルな技術があります。問題と解決を示すため、サンプルスキーマを少しだけ変更しましょう(Figure 8参照)。あなたがユーザーの売却と購入の最終日もトラックしたいとしましょう。あなたはメッセージによる日付更新に似た手法を使えますが、そこにはひとつ問題があります。
短い時間ウィンドウの中で二つの更新の発生を仮定すると、私たちのメッセージシステムはオペレーションの順序を保証しません。私たちはいま、どの順番でメッセージが処理されるかによってlast_purchaseの値が不正になる状況にあります。幸運なことに、この種類の更新はfigure 9のようなSQLの小さな変更で対処できます。
単純に、last_purchase時刻の巻き戻りを許さないことで、更新オペレーションを順序独立にすることができます。この手法を、順序の狂った(異常な？)更新からどんな更新であれ保護するために使うことでもできます。時間を使う以外に、単調(monotonically)増加するtransaction IDを使ってみることもできます。
関連する順序付きメッセージデリバリーについての注釈。メッセージシステムはメッセージが受信した順序で配送されることを保証する能力を提供します。これは高価でしばしば不要かもしれず、実際、時としてセキュリティの錯誤になります。
ここで示した例は、メッセージ順序を緩和しつつまたデータベースの結果的な(eventually)コンシステントビューを提供する方法を示します。順序の緩和に必要なオーバーヘッドはほんのわずかばかりで、殆どの場合メッセージシステム内で順序を強制するよりも大幅に少なくて済みます。
また、Webアプリケーションとは意味論的にはインタラクションの形式を問わずイベントドリブンシステムです。クライアントのリクエストはシステムに任意の順序で到達します。リクエストごとの処理時間はさまざまです。システムコンポーネント全体を通じたリクエストスケジューリングは非決定性であり、結果的にメッセージのキューイングも非決定性となります。順序保護の要求は、セキュリティの観点での錯誤ともなります。シンプルな現実は、非決定性の入力は非決定性の出力を導くというものです。
ここまで、一貫性を引き換えに可用性を得る話にフォーカスしてきました。見方を変えれば、これはsoft stateとeventual consistencyがアプリケーション設計へ与える影響を理解することです。
ソフトウェアエンジニアとして、私たちは私たちのシステムを、閉回路として考える傾向があります。予測可能な入力が予測可能な出力を生むという観点でシステム動作の予測可能性を考えます。これは正しいソフトウェアシステムを作る上で必要です。多くのケースでの良い知らせは、BASEの使用は閉回路としてのシステムの予測可能性を変更しません。ただし、その振る舞いを全体として見る必要があります。
シンプルな例でそのポイントの説明を助けることができます。ユーザーが資産を他のユーザーに移すことができるシステムを考えましょう。資産の種類は問題ではありませんーお金かもしれませんし、ゲーム内のオブジェクトかもしれません。この例では、あるユーザーから資産を引き出し、他のユーザーに与える２つのオペレーションを、メッセージキューを使って分離されていることを想定します。
すぐに、このシステムは非決定的で問題をはらむように感じるでしょう。資産がユーザーから去っていながら、もう一方に到着していない時間的な期間が存在します。このタイムウィンドウのサイズはメッセージングシステムの設計で決定できます。それでも、開始状態と終了状態の間に、どちらのユーザーも資産を持っていない遅延があります。
ユーザー視点からこれを考慮するなら、しかしながらこのラグは関係ないか、または知りもしません。送信ユーザーも受信ユーザーもいつ資産が届いたか知ることはないでしょう。もし送信と受信の遅延が数秒しかないなら、それは資産転送のやり取りをしているユーザーにとって不可視であるか、確実に我慢できるものでしょう。この状況では、soft stateとeventual consistencyに依存しているとしても、システムの動作は一貫的でユーザーに受け入れられるものと考えられます。
もしあなたが、いつ状態がconsistentになったか知る必要があったらどうでしょう？あなたにはその状態に適用される必要があるものの、それは入力リクエストに関係のある状態が一貫性に達したときのみであるようなアルゴリズムがあるかもしれません。単純なアプローチは、状態がconsistentになったときに生成されるイベントに頼ることです。
前の例で話を続けると、資産が到着したことをユーザーに通知する必要が有る場合はどうでしょう？受信ユーザーへの資産をコミットしたトランザクション中でイベントを作成することは、一度状態が到達したことでさらに処理を実行できるメカニズムを提供します。EDA(event-driven architecture)はスケーラビリティの劇的な改善とアーキテクチャの分離をもたらします。EDAのアプリケーションに関するさらなる議論はこの記事のスコープではありません。
劇的なトランザクションレートのためのシステムのスケーリングはリソース管理をめぐる新しい方法を要求します。伝統的なトランザクショナルモデルは負荷を多数のコンポーネントに分散する必要が出た時に問題を抱えています。オペレーションを分離してそれらを順番に実行するのは、一貫性を犠牲にして可用性とスケールを改善します。BASEはこの分離を考えるためのモデルを提供します。
##REFERENCES
- http://highscalability.com/unorthodox-approach-database-design-coming-shard
- http://citeseer.ist.psu.edu/544596.html
DAN PRITCHETT is a Technical Fellow at eBay where he has been a member of the architecture team for the past four years. In this role, he interfaces with the strategy, business, product, and technology teams across eBay marketplaces, PayPal, and Skype. With more than 20 years of experience at technology companies such as Sun Microsystems, Hewlett-Packard, and Silicon Graphics, Pritchett has a depth of technical experience, ranging from network-level protocols and operating systems to systems design and software patterns. He has a B.S. in computer science from the University of Missouri, Rolla.