NOSQL Patterns、和訳

http://horicky.blogspot.com/2009/11/nosql-patterns.html

11/30時点で、一通り翻訳のうち、正直ベースのざっくり感覚（業界用語）で75%完了です。
本人も理解が怪しいながら訳しているので、随所に間違いを仕込んでいます。ご指摘頂ければ幸いです。

NOSQL Patterns

ここ数年、大規模データを扱うデータストレージ機構が発展している。これらの機構は従来のRDBMSモデルとは異なっており、NOSQLとも呼ばれている。キープレイヤーとしては：

  • GoogleBigTable, HBase, Hypertable
  • AmazonDynano, Voldemort, Cassendra, Riak
  • Redis
  • CouchDB, MongoDB

これらは、次の共通点を持っている。

  • Key-Valueストア
  • 多数台の一般的なPCで運用可能
  • 複数サーバに分割・複製されてデータを保持
  • 緩い一貫性(consistency)を保証（CAP定理によると、一貫性、可用性、分割性は同時に満たすことはできない）

このブログでは、NOSQLに共通する原理的な技術について明らかにし、アプリケーションを設計方法についてより深く理解することを狙いとしている。それぞれにある違いや将来性などについては、特に論じない。

API Model

原理的なデータモデルは、巨大なハッシュテーブル(Key/Valueストア)である。

基本となるAPIアクセスは：

  • get(key) ... keyに対応するvalueを取り出す
  • put(key, value) ... keyに対応するvalueを生成または更新する
  • delete(key) ... keyと、対応するvalueを削除する

サーバ環境によっては、拡張APIが用意されていることもある。

  • execute(key, operation, parameters) ... keyに対応する(List, Set, Mapなどの)特定のデータ構造に対してoperationを実行する
  • mapreduce(keyList, mapFunc, reduceFunk) ... keyListに対して、map/reduce関数を実行する

Machines layout

数百〜数千の低性能で低信頼な普及型のマシンをネットワーク接続した形が、基本的なインフラである。それぞれのマシンを「PN (physical node、物理ノード)」と呼ぶことにする。各PNは同じソフトウェア・設定がされていれば、CPUやメモリ、ディスク容量などは異なっていてもよい。各物理ノードには、容量が許す限りの複数の「VN (virtual node、仮想ノード)」を持っていてもよい。

Data partitioning (Consistent Hashing)

ハッシュテーブル全体は複数の仮想ノードに分割されるため、各keyを仮想ノードに対応させる方法が必要となる。

一つの方法としては：

partition = key mod (total_VNs)

この方法の欠点は、仮想ノードの数を変更する場合、既存のキー管理が劇的に変わるため、データの再分配が必要となることである。多くの大規模ストアでは「consistent hashing(一貫性のあるハッシュ生成)」技術を使い、キー管理の変更を抑えている。

一貫性のあるハッシュ生成する方法では、キー空間を有限かつリング上に配置する。仮想ノードのidも同様にリング上のノードとして割り当てられる。全てのキーは、時計回りにはじめに出会う仮想ノードを主ノードとして扱う。主ノードがクラッシュした場合、そのノードが所有していたキーは、時計回りで隣のノードが主ノードとなる。従って、クラッシュしたノードの隣のノードのみでキーの再配置が起こり、その他のノードは元のまま保たれることになる。

Data replication

個別には信頼性の低いリソースを使って高い信頼性を確保するために、レプリカによるデータの分割が必要となる。

レプリカはデータの信頼性を向上させるほか、作業負荷分散によりパフォーマンス向上にも役立つ。

読み出しリクエストはどのレプリカに割り当ててもよいが、更新リクエストでは、レプリカも注意深く連携させながら更新する必要があるため、すこしやりがいのある仕事になる。

Membership Changes

仮想ノードはいつでも追加・削除でき、リング上の操作に影響を与えない。

新しいノードが追加されたとき
  1. ノードが追加されたことが、ネットワーク全体に通知される。
  2. 左右両隣のノードが所有するキーとレプリカとして持つキーが調整される。これは通常、同期的に実行する。
  3. 追加したノードは並行非同期に、両隣のノードからデータを大量にコピーする。
  4. 所有権が変更されたことを、他のノードに非同期に通知する。

このとき、他のノードが持つ所有キー表は更新されていないこともあり、その場合は古い所有ノードにリクエストを転送してしまうことになる。が、古い所有ノード（追加したノードの隣にあるはず）が持つ所有キー表はステップ2で既に更新されており、追加したノードにリクエストを転送することができるため、問題にはならない。

既存のノードが削除されたとき（例えばクラッシュなど）
  1. クラッシュしたノードはメッセージに反応しなくなるので、両端のノードはクラッシュしたことを知る。
  2. 隣のノードは所有キー表を更新し、非同期にデータをコピーする。

仮想ノードがどのように物理ノード上に割り当てられるのかについて説明しよう。仮想ノードが管理するレプリカは同じ物理ノードに置くべきではない、というのが多くの方式が目指すゴールとなる。シンプルな例として、ランダムに割り当てるが、同じ物理ノードにキーレンジが重複する仮想ノードがないかチェックする方式がある。

マシンのクラッシュは物理ノードレベルで起こり、稼働している多数の仮想ノードを巻き込んでクラッシュする。そのため、物理ノードがクラッシュしたとき、（その複数ある仮想ノードの）作業負荷が多くの物理ノードにまき散らされる。故に、物理ノードのクラッシュに伴う作業負荷の増加は全体に均等にかかることになる。

Client Consistency - クライアントから見た一貫性

ある一つのデータを複数コピーした場合、クライアントからデータを参照したとき一貫性についてどう同期を取るか、心配しなきゃならない。

クライアント一貫性モデルは幾つかある。

  1. Strict Consistency (厳密一貫性) : データは一つしか存在しない状態と同じように動作する。すべての更新は即座に反映する。
  2. Read your write consistency (read-your-write一貫性) : そのクライアント自身が更新した情報はすぐに参照できる（クライアントはリクエストするサーバを切り替えることもできる）が、他のクライアントが更新した情報はすぐには参照できない。
  3. Session consistency (セッション一貫性) : 同一セッションに限りread-your-write一貫性を実現する（セッションが共有されていない限り、サーバを切り替えた場合には保証されない）。
  4. Monotonic Read Consistency (単調読込み一貫性) : 単純に時間を掛けて、クライアントは最新のデータを参照できるよう保証する。
  5. Eventual Consistency (終局一貫性) : 単調読込み一貫性の弱い形式である。更新が実行中の場合、クライアントは一貫していないデータを参照する。同一データへのアクセスがほとんど起こらず、最新データを参照したいときはクライアントが少し待ってもよい場合に、このモデルが利用できる。

どのモデルを採用するかによって、2つのメカニズムが用意される：

  • クライアントのリクエストを、どうレプリカに対応させるか
  • どのようにレプリカを増殖させるか、更新を反映させるか

この2つの要素を実現する様々なモデルがあり、それぞれにトレードオフが存在する。

Master Slave (or Single Master) Model

データの各分割は単一のマスタと複数のスレイブを持つモデルをいう。このモデルでは、キー「AB」のマスタはノードBであり、ノードCとノードDはスレイブである。全ての更新リクエストはマスタに送られ、実行し、非同期にスレイブへ増殖させる。スレイブに増殖させる前にマスタがクラッシュした場合データが失われることになるので、更新時に1つ以上のスレイブと同期して更新を実行するシステムもある。

読込みリクエストはどのレプリカに送ってもよいが、ある程度の古いデータが送られてくることを我慢する必要はある。読込み負荷は多数のレプリカで分散される。クライアントが最新のデータを要求する場合は、リクエストはマスタに送られる。

ある特定の物理ノードがマスタの役割を持つわけではない。キー所有の粒度は、仮想ノードレベルで決定される。各物理ノード上に複数の仮想ノードがあり、その仮想ノードが特定のキー範囲についてのマスタとなり、別のキー範囲についてのスレイブとなる。すなわち、レプリカを分割管理しているというのはあるけれども、書き込み負荷は物理ノードレベルでは分散されることになる。

物理ノードのクラッシュが起こった場合、特定の範囲のマスタが失われることになる。通常は、最後に更新されたスレイブが新しいマスタとなる。

マスタ-スレイブモデルは一般的に、高い頻度で読込み/書込みが起こるアプリケーションに向いている。また、広いキー範囲に対して頻繁に更新が起こるようなものにも向いている。その意味で、データ複製モデルとして最重要なモデルである。

スレイブに対してレプリカを作るには、2つの方法がある；State transfer（状態移送）モデルとOperation trancfer（処理移送）モデルだ。状態移送モデルでは、マスタは最新状態をスレイブに渡し、スレイブは最新状態に置き換える。処理移送モデルでは、マスタは処理（の流れ）をスレイブに送り、各スレイブは処理を個別に実行して、自身が管理するデータを更新する。

状態移送モデルは、最後のメッセージさえ受け取れば最新状態に更新できるため、メッセージの喪失に対して安定して動作することができる。

状態移送モードでは、オブジェクトの一部分だけしか更新していないのに、毎回オブジェクト全体を送りたくはない。更新しない部分を送るとネットワーク帯域を浪費してしまうため、更新があった差分のみを送るメカニズムが必要となる。よくあるアプローチとしては、チャンク（塊）単位にオブジェクトを解体し、ハッシュ木を生成する方法がある。レプリカのハッシュ木を比較し、更新されたチャンクを特定し、そのチャンクのみを送付させるようにする。

処理移送モデルでは、ネットワークで送る更新データが少なくて済む。しかし、メッセージ授受の信頼性を担保する必要がある。

Multi-Master (or No Master) Model

特定のキー範囲にデータが集中し、かつ集中的に書込みリクエストが起こるような場合、マスタ-スレイブモデルは負荷分散が難しくなる。マルチマスタモデルとは、どのレプリカに対して更新が許されるモデルである（個人的には"No Master"モデルという方が正確だと思っている）。

任意のクライアントが任意の更新を任意のサーバに送る場合、状態の同期をどのようにとれば、クライアントから見た一貫性を保ち、また、全てのレプリカを同じ状態にさせることができるのだろうか？

続くトピックでは、幾つかのアプローチを示す。

Quorum Based 2PC - 2相コミットベースのクォーラム*1 / QB2PC

伝統的な2相コミット方式は、全てのレプリカに毎回同じ状態を送る方式で厳密一貫性を提供する。あるデータのレプリカがN個あるとする。データが更新されるとき、「prepare」フェイズ（相）として、コーディネータはすべてのレプリカに対して、更新の準備ができるかを問い合わせる。各レプリカはデータをログファイルへ書込み、成功すれば、コーディネータに返信する。

すべてのレプリカから「成功」の返信が届いたら、コーディネータは次のフェイズ「commit」を起動し、すべてのレプリカにコミットを指示し、各レプリカは更新を別のログファイルに登録する。ただし、この方式はスケーラビリティの問題がある。同期処理が必要であり、ネットワークからディスクI/Oに至るすべてに起因する待ち時間が生じるためである。

一方で、レプリカの一つがクラッシュした場合、更新は失敗する。レプリカが増えるに従い、そのうちの一つがクラッシュする確率は上がる。従って、レプリカの作成は、安定性に寄与するどころか、障害となってしまう。これが伝統的な2相コミット方式が、高スループットが要求される環境で使われなかった原因である。

これを解決するのが、QB2PC方式である。このモデルでは、コーディネータはW (< N) 個のレプリカのみを同期の対象とする。コーディネータはN個全てのレプリカに書き込むが、N個のうちW個だけ、正常更新を確認する。これで、確率論の観点から効果が期待できる。

この時点では、すべてのレプリカが更新されている保証がないため、読込みの際に注意が必要となる。読み込んだデータが最新であることを確認するために、複数のレプリカを読込み、その中で最新のデータが正しいデータとして扱う。R個のレプリカを参照し、タイムスタンプが最も新しいものをクライアントに返す。

「厳密一貫性」を保証するためには、書き込むノード集合と読み込むノード集合が重なっていることが条件となる。すなわち、W + R > Nが必要条件である。

既に気付いているかもしれないが、QB2PCは、より一般的な2相コミット方式と考えることができる。伝統的な2相コミットはQB2PCの特殊なケース、W = NかつR = 1である場合と同等である。一般的なクォーラムモデルでは、WとRは書込み負荷と読込み負荷のトレードオフで、状況に応じて判断することになる。

仮にWとRを十分に確保できなかったとしたら、すなわちW + R ≤ Nの場合、クライアントはより弱く、緩い一貫性が提供されることになる。

より緩い一貫性で十分であれば、2相コミットやクォーラム方式を使う必要はない。「Gossip(ゴシップ)モデル」について、後の章で紹介する。ゴシップモデルでは、ゴシップメッセージの交換により更新情報を非同期に繁殖させ、自動エントロピ方式によりすべてのレプリカが最終的には最新状態になるよう更新を適用する。

Vector Clock - ベクタークロック/クロックベクトル

（Vector Clockについては、ベクタークロック : kei@sodanもどうぞ。ベクタークロックで比較不能となった場合の扱いは記述されてないけど、どうするんだろう？）

ベクタークロックとは、更新の因果関係の判断にタイムスタンプを用いる方式である。まず、各レプリカはクロックベクトルを保持している。レプリカiのクロックベクトルをViとする。Viの要素であるVi[k]は、以下の条件に従って更新される論理的なクロック（現実の時刻とは関連性はない、タイムスタンプの一種）である。

  • レプリカiで内部の処理が起これば、必ず、クロックVi[i]を進める。
  • レプリカiがレプリカjにメッセージを送るときは、必ず、まずクロックVi[i]を進め、メッセージにViを添付する。
  • レプリカjがレプリカiからメッセージを受け取ったときは、必ず、クロックVj[j]を進め、自身のクロックベクトルVjと受け取ったクロックベクトルViをマージする。すなわち、Vj[k] = max(Vj[k], Vi[k])とする。*2

このとき、「任意のk対してVi[k] ≥ Vj[k] ⇒ Vi > Vj」という部分的順序関係が定義できる。この部分的順序は、更新間の因果関係を抽出するために使うことが出来る。その理由を以下に示す。

  • あるノードでの内部処理の結果は、そのノードは、すぐに知ることができる。
  • あるノードがメッセージを受け取れば、そのノードは、送信元ノードの状況を知ることができる。同時に、送信元ノードの状況は他のノードにも送られているため、他のノードがその状況を知っていることを知ることができる。
  • つまり…
    • Vi[i]は、ノードiにおいて、最新の内部処理が起こったクロックを反映している。
    • Vi[k] = 6は、ノードiにおいて、レプリカkのクロック"6"の状況までは知っているということを反映している。

「状況」という単語は、ここでは抽象的な意味で使っている。メッセージで渡される情報によっては、「状況」は異なることもある。これは、クロックベクトルがどのように進むかに左右される。以下で、「状態移送モデル」と「処理移送モデル」について説明する。どちらも、メッセージで渡される情報や、クロックベクトルの進め方が異なる。

その理由は、レプリカからクライアントに送られる状態は常に流動的であるが退行することはないため、また、クライアントはクロックベクトル上では扱われないためである。クロックベクトルは、一つのレプリカに対して一つの情報しか持たない。しかし、クライアントは情報が最新であることを確認するために、ベクトルクロックを保持する必要がある。このことは、既に説明したクライアント一貫性モデルを実現するために重要である。例えば、単調読込み一貫性では送るデータに関して、レプリカはクライアントが提出したクロックベクトルよりも大きい（つまり新しい）ことを保証する必要がある。

Gossip (State Transfer Model)

状態移送モデルに従い、レプリカ管理にはベクタクロックを用いてデータ状態の履歴管理を行う方式である。ベクタクロックで、データ状態の大小関係を判定する。つまり、更新の衝突も含め、状態の履歴を管理する。

...

Gossip (Operation Transfer Model)

処理移送モデルでは、実行すべき処理の流れはとても重要となる。最低限、処理の順番を管理しなければならない。

...

Map Reduce Execution

分散型データ管理アーキテクチャは、分散処理に向いている。例として、キーのリストに対するMap/Reduce処理がある。

...

Handling Deletes

マルチマスタ複製システムでは、ベクタクロックのタイムスタンプを用いて順序関係を決めているが、「delete（削除）」操作については注意が必要だ。削除したオブジェクトのタイムスタンプを残しておかなければ、削除操作の順序が管理できなくなってしまう。

従って、一般的に、削除は特別な更新として扱い、オブジェクトを「削除済」状態に更新し、メタデータやタイムスタンプを残す方法をとる。十分に時間が経過し、すべてのレプリカで削除済状態となったことが確認できれば、ガベージコレクトを実行して記録スペースを再生する。

Storage Implementation

一つの戦略として、プラガブルにストレージを実装する戦略がある。例えば、ローカルなMySQL、Berkeleyなどのデータベースやファイルシステム、インメモリのハッシュテーブルは、それぞれストレージとして使うことができる。

もう一つの戦略としては、スケーラビリティを重視する方向もある。CouchDBやGoogleBigTableが採用している戦略だ。

...

*1:クォーラムとは、ある一定数の確認をもって結論を導きだすという意味。らしい。

*2:元記事では、Vj[k] = max(Vj[k], Vm[k])と記述してあるけど、VmじゃなくViと書いた方がわかりやすいと思います。