データベースのルネッサンスは2008年頃のNoSQLの動向に端を発しています。コンシューマ向けインターネット企業(Twitter、Facebook、Google、Amazon)の新たな波による技術的要求に、従来のRDBMSの能力が応じられなくなったのです。それに加えて、OracleなどRDBMSベンダの価格構成は、このような企業の持つ極めて小さな単位のエコノミクス、特に広告収入を中心としたものには相応しくありませんでした。では、どうするのか？
企業が最初に向かったのは、従来のデータベース、特にMySQLとInnoDBをストレージエンジンとして使用する、独自の分散型共有サービスでした。Memcacheや､後にはRedisなどの分散キャッシュが、当然のものとして使用されるようになりました。しかし、これらのシステムは自立的ではありません。障害からの復旧には、依然としてDBAの関与が必要でした。セルフシャーディングやセルフヒーリングではなかったのです。
私は当時、Twitterでソフトウェアインフラストラクチャチームを指揮していましたが、規模と柔軟性を透過的に提供可能なシステムの構築は可能である、という確信を持っていました。そこで、業界他社と同じように、オープンソースによるシステム構築に着手し、当初はApache CassandraやHadoop、その他のストレージプラットフォームに多大な投資をしていました。ビジネスが規模を求めるのならば、それを妨げるものはすべて捨て去らねばなりません。
これらのシステムの営利的なベンダたちは、自分たちが提供できない従来的なRDBMSの機能については、誰も望まないし、必要としていない、と言って説得してきました。これは明らかに真実ではありません。今はすべてのビジネスがスケールを必要とする時代です。しかしながら、NoSQLでそれを実現する上で、私たちは何を諦めてきたのでしょう？それを取り戻すことはできるのでしょうか？
結果整合性の実務的効果
CAP定理とは、簡単に言えば、“ネットワークが分断された時にどうなるか？”ということです。システムの一貫性(正確性)を維持するために一時停止するのか、それとも、可用性を維持するための動作継続に最大限の努力を払うのか？しかし現実的には、一貫性と可用性は潜在的なトレードオフの範囲で選択するものであって、実際のストーリはもっと微妙なものです。
第1世代のNoSQLシステムは結果整合的でした。分断が発生した後、可変かつ有限な期間中にコンフリクトを調整し、データがどうあるべきかを確率的に投票する、という主張でした。しかし現実の結果整合性システムでは、実際にこのように高度なものはごく一部で、大部分はローカルシステム時刻に基づいた、単純な“後勝ち書き込み”の方法を用いていたのです。これはこれで賢いのですが、アプリケーションを構築する上で有用な保証にはなりません。ホスト全体を対象としたコンフリクト解決策を、システム設計者が、アプリケーション層に導入する必要があったのです。
例
トランザクションが明らかに失敗するパターンとして、次のようなものがあります。
- BobがATMで200ドル預金する。
- データベースのひとつのシャード(shard)が、“結果一貫的に”Bobの預金を受け入れる。彼の新しい預金残高である200ドルは待ち行列に入れられる。
- Bobがモバイルアプリで100ドル預金する。この更新が最初のシャードとは別のシャードへ行き、クラスタの他の部分にレプリケーションされるが、最初のシャードへはレプリケーションされなかった。
- 後にネットワークが回復し、レプリケーションが続行される。
- 物理的に後の時間に発生しているので、他のシャードにおけるBobの預金残高は、ステップ3に従って100ドルに更新される。
Bobは200ドル損することになりました。結果整合性は可用性を保証します。お金をいつでも預けられるのです！ですが、正確性は保証しません。
CRDTとブロックチェーン
この問題を解決するために、これまで、さまざまなスキーマが提案されてきました。中でもCRDT(conflict-free replicated data types)は、すべての中間状態を実質的に成立させることにより、最終値を正確に構築できるようにします。この方法では、 Bobのトランザクションは最終的な残高ではなく、借方と貸方として記録されます。最終的な残高の計算は、データベース内あるいはアプリケーション層で実行されるのです。それを転化したものがブロックチェーンで、すべてのトランザクションを常時、クラスタの全ノードに記録します。
しかし現実には、これですべての問題が解決するわけではありません。データベースはクローズドシステムだからです。すべてのデータの読み込み点と書き込み点は、外部的な操作の結果として得られるものです。もしBobがATMから現金を引き出せば、お金は持ち出されてしまいます。CRDTが後になって預金額が不足していたことを明らかにしても、もはや手遅れです。
これは決して机上の空論ではありません。ATMにおける意図的な引き出しの競合は、数多く報告されている詐欺行為です。ですから、データベースには“外部一貫性(external consistency)“、俗にいうACIDが必要なのです。
従来の解決策
これまでのデータベース(特に集中型のRDBMS)はこの問題を、非分散型であることで解決していました。究極的には、ひとつのディスクを持った1台のマシン – 実装面では、ディスク更新のための単一のmutex – は、真実の源になります。状態の更新は直列的、すなわち、決定論的な順序でひとつずつ発生し、外部的一貫性が保たれます。物理的な時刻による発生順に処理されるのです。スケーラビリティは唯一、その単一マシンの垂直的スケールアップによってのみ実現されます。
このモデルは実装が容易ではありますが、多くの重要な保証、具体的には可用性に関する保証を満足することができません。
そのために、プライマリ/フォロワ形式のレプリケーションシステムが登場しました。プライマリノードの状態を非同期的に複製したフォロワノードを使って、DBAが手作業でプライマリノードを置き換えることが可能なシステムです。これは素晴らしいとは言えませんが、結果整合性を持つ分散システムとは違って、不一致の範囲が分かっています – フォロワに複製された最後のトランザクションから、外部から確認できたプライマリの障害までの間です。
消費者向けのインターネット・シャーディングシステムは、事実上、このような運用をしています。すなわち、
- トランザクションはひとつのシャード(単一マシン)内で実行可能である
- 手動ないし半手動でバックアップシャードにフェールオーバ可能である
- 同時に複数のシャードにまたがったトランザクションはできない
TwitterやFacebookにとってこれは許容範囲でしたが、望ましいものではありませんでした。例えば、Webサイトでまだ読むことのできないメッセージを電話で通知されるというのは、困惑することではあっても、大問題にはなりません。プロダクト上にはトランザクション性を必要な機能 – 例えばユーザ名の割り当て – もありますが、従来のRDBMSでも十分に処理可能な規模でした。
しかし、プロダクトが複雑になるにつれて、外部一貫性の欠如によるマイナス面がますます深刻度を増してきたのです。
Google Spanner
Spannerは、これらの問題に対するGoogleのソリューションです。当初はGoogleの社内インフラストラクチャでのみ使用されていましたが、現在はGoogle Cloudのマネージドプロダクトとして利用可能になりました。
Spannerは2つのことを実行します。
- マルチシャードのトランザクションが、2フェーズのprepare/commitアルゴリズムによって実装されています – 1980年代のトランザクション監視プロトコルであるTuxedoと、これは本質的に同じです。
- HAやメインフレームクラスのハードウェアに可用性を頼るのではなく、一般的なハードウェア上でのシャードのフェールオーバが、Paxosによって自動化されます。
このアプローチは、ある程度は機能します。直列性の保証、すなわち、個々のシャードに対する更新は、リアルタイム順に発生することが保証されるのですが、外部一貫性、あるいはシャードを越えたリアルタイム整合性については保証されません。この最後の問題を解決するため、Spannerはもうひとつのことをします。
-
物理的な原子時計ハードウェアによって、すべてのシャードのシステム時間を、極めて低い誤差範囲で同期化する。
これによって、トランザクションコーディネータは、次のように言うことができます – “おいシャード、私は実時間Tでトランザクションを実行しているのだが、我々の共有時間のエラー範囲内に別の更新が来なければ、このトランザクションは競合しない、ということだ”。このようにするのは、すべてのシャードがクロックのアンビギュイティ(ambiguity、曖昧性)ウィンドウを待たねばならないため、外部一貫性のある読み込みや書き込みそれぞれにわずかな遅延が発生するからです。
レイテンシの影響を除けば、このソリューションはGoogleにとって素晴らしいものです。同社には、独自の原子時計ハードウェアと、遅延保証のあるネットワークを構築し、維持するためのリソースがあるからです。一方で、これと同じようなプロトコルをコストを要する原子時計を使わずに実装した、新しいデータベースシステムもたくさんあります。
NTPを使用したSpanner
NTPクロック同期に依存するデータベースは、もっと長い、数百ミリ秒のアンビギュイティウィンドウを持っています。現実には、これらのシステムでは、それだけの時間を待つのではなく、外部一貫性のない単一レコードの線形化可能性の保証にフォールバックしています。これは結果として、前の例と同じような、行を跨いだ２重振り出し(double-debit)効果を発生させる可能性があります。
これらのシステムは高速な外部逐次読み出し(serializable read)を提供しませんが、最後に判明しているPaxosリーダからの読み出しがしばしば行われます。これもまた、直列化可能性を棄損する原因となり得ます。自身がリーダでなくなっていることを知らず、一般的に数秒のオーダである選出期間中に、すでに無効になったデータを提供する可能性があるからです。このウィンドウを阻止するためには、一時停止を行う必要があります。
さらに、クロックの同期が失われた場合 – クラウド内でこれが発生すると、VMのストールなど、クロック自体とは無関係なあらゆる種類の事象が発生する可能性があるため、Googleが最も回避に努力している状況です – には、書き込みの直列化可能性も失われることになります。
Google Percolator
別のクラスである、単一の物理時計(Google Percolatorの論文の説明では“clock oracle”)を照会する方式のデータベースでは、その共有クロックに対するインターネット上のラウンドトリップに等価なアンビギュイティウィンドウが存在するだけでなく、それが明らかな単一障害点(single point of failure)になるという問題もあります。
このモデルは、システムバスがネットワークに代わったことを除けば、マルチプロセッサのRDBMS – 単一のマシンなので、同じくひとつの物理的クロックを共有します – と同じです。実際には、このようなシステムではマルチリージョンのスケールには耐えられず、単一のデータセンタ内に限定されることになります。
物理的なクロック同期がなければ、分散システムでの外部一貫性が不可能なのは明らかです ... あるいは、何か方法があるのでしょうか？
Calvinで物理的クロックを排除する
すべてのトランザクションに対して論理的なclock oracleを構築可能で、それが物理的に1台のマシンに依存せず、クラウドに分散していたとしたらどうでしょう？Calvinが行うのはまさにこれです。Calvinは、Yale大学のDaniel Abadi氏の研究室で開発されました。
John Calvinはフランスのプロテスタント改革者で、すべての魂の最終的な運命は – 天国か地獄か – は、世界の初めに神によって定められている、と考えていました。
Calvinの動作もこれと同じです。トランザクションの順番は事前に決定されています – ノードのサブセットが分割されたoracleとして機能し、一連のパイプライン化されたバッチ内のすべての着信トランザクションに対して、外部一貫性を持った順序を割り当てるのです。その後バッチは、PaxosあるいはRaftで実装された分散型の先行書き込みログに対して、10マイクロ秒単位でコミットされます。
この事前処理には多くのメリットがあります。
- 分散ログへのコミットを、単一のネットワークラウンドトリップで完了することができます – レプリカへの2フェーズコミットは必要ありません。
- この運用トポロジはレプリカのトポロジとは異なり、ロングテールレイテンシを削減することが可能です。
- 直列化可能な読み取りでの調停は不要で、アンビギュイティウィンドウを待つ必要もありません。しかも、結果一貫性システムと同じように、グローバルにスケールアップします。
ただし、いくつかのトレードオフも必要です。
- トランザクションはバッチでコミットされるため、書き込みレイテンシは次のコミットの待ち時間を下回ることはできず、平均で5ミリ秒、場合によっては10ミリ秒に達します。
このモデルの実装でさまざまなパフォーマンス改善を実現したFaunaDBはNewSQLシステムではなく、リレーショナルNoSQLシステムなのですが、ただし、FaunaDBが最終的にSQLインターフェースを実装する可能性を排除する理由は何もありません。
CAPでは
完全に無作為なネットワーク分断の発生に対して、CPシステムが動作を維持できないのは事実です。しかし実際には、クラウド上のSpannerやFaunaDBなどのシステムの現実的な可用性は、APシステムの可用性と遜色ありません。99.9パーセントを越える可用性における障害は、実装上の問題よりもハードウェアやネットワークに起因する場合が多く、CPシステムのフォーマルな整合性モデルは、APシステムよりも障害下での検証が容易なのです。
例えば、5つのデータセンタを持つFaunaDBクラスタは、その有用性を失うことなく、2つのデータセンタ全体の損失を許容します。また、FaunaDBのようなCPシステムは一般的に、ネットワーク分断の発生下においても、(スナップショットアイソレーションのような)低いレイテンシレベルで読み取り可用性を維持します。これはAPシステムが提供可能な一貫性レベルよりも、常に同等かそれ以上です。
理論的には、書き込み可用性を99.999パーセントから99.9999パーセントに向上する(年間で数分の違い)意義はありません。停止中に受け入れた書き込みに、恒久的なデータの不整合というコストがあるならばなおさらです。
結論
分散トランザクションはコンピュータサイエンスにおける最も難しい問題のひとつです。このようなシステムがオフ・ザ・シェルフで利用可能な世界に生きている私たちは幸せです。どのような制限のある一貫性でも、結果一貫性よりは優れています – 堅牢性など従来のNoSQLが抱える他のすべての問題や、運用上のオーバーヘッドなど従来のRDBMSの持つ問題を差し引いても、それは変わりません。
それでもなお、物理的なクロックのない分散型の外部一貫性という聖杯は、私たちを惑わせます – Clavinを除けば。FaunaDBはClavin形式のトランザクションプロトコルの、実用レベルに達した唯一の実装です。使用中のデータベースが提供する一貫性保証に一度目を向けてみましょう。そしてぜひ、FaunaDBを試してみてください。
著者について
Evan Weaver氏はTwitterのインフラストラクチャを担当していた元ディレクタで、Twitterのバックエンドのスケールアップを実践していました。コンピュータサイエンスの修士号を持つ氏は、これまでCNETやSAPで開発を行っていました。FaunaDBの開発者のひとりでもあります。