Bigtableと分散KVS・その2

ありがたいことに古橋さんに前回のエントリをご覧いただいたようで、大変ためになるつぶやきをされてたので、ここで引用させていただきます。

@frsyukiさん：

「分散KVS」という名前は何も考えていなくて、別に分散KVSにBigTableを含めても良くて、効率の話を問題にしていたけど、分かりにくかっただろうか…：http://bit.ly/IMFUs

それはそれとして、効率について。概念的には、データモデルがmultidimentionalであることで、BigTableはアプリケーションに依存した情報をより多く知ることができる。これによって最適化をしやすくなり、効率が上がる。

例えば、Every read or write of data under a single row key is atomic を効率的に保証する、reads of short row ranges are efficient にするなど。

これはパラメータをチューニングする程度の差ではなく、RDBとKVSの単体性能の差くらい大きく性能が変わってくるし、耐障害性やスケーラビリティにも影響する。分散トランザクションするのか、世界各国のデータセンターにクエリを飛ばすのかぃと。

で、これは multi dimentional だから効率化できる話で、multidiemntional であるという点は、他のDynamoなどのKVSと比べて、BigTableが本質的に勝っている特性だと言える。

本当に単純なkeyとvalueだけだと、同じrowに属した複数のcolumnはatomicに更新したいことがある、同時に取得したいことがあるといった情報を知ることができない。アプリケーションからストレージにこれらの情報を渡すインタフェースがない。

まとめると、データモデルがリッチであることで、データストアはよりアプリケーションに依存した情報を知ることができ、ときに圧倒的な効率化が可能になる。従ってデータモデルの違いはデータストアにとって本質的な問題である。

なるほどねぇ〜と思いました。まず私がここで学んだ点は、「multidimentional」とは「表形式」および「それより上の次元（時間軸とか）」を含む、ということです。Bigtable論文や古橋さんの元エントリでmultidimensionalという単語を見たとき、私はそれを後者の意味でのみ解釈してしまいました（表形式であることを当たり前に感じていたところは、まだ相当RDB脳なんですね）。そのため、前のエントリの真意は「（Bigtableが時間軸で履歴を残せる点は）本質的な特性ではない」という意味でした。

しかし純粋？なKVSは、キーと値しかありません（キー軸のみの1次元？）。つまりストレージ側ではそれらのデータが2次元の表形式として組織されてるのか、まったく無秩序なのかといった情報を知り得ないので、たとえ同じNoSQLであっても「表形式ストレージ」と「汎用のKVS」とでは最適化の可能性が大きく異なります。例えば、Bigtableのように、

・「行」や「テーブル」といった単位でひとつのサーバーにできるだけまとめたり（ローカリティ）
・複数カラムにまたがる行単位でACID保証したり

できます。つまり、「multidimensional map」＝表形式（＋履歴）に特化した分散KVSという点がBigtableの本質的な特性と言えます。

GAE経由で使えないから云々という話があった。row-columnsでないと（multi dimentionalでないと）１つのエンティティグループの中であってもトランザクションがまったく使えないことになるんじゃないかなぁ。

エンティティグループ（Bigtableの複数行）単位でのトランザクションは、BigtableではなくApp EngineのDatastore APIの付加機能ですが、これも「表形式」であることに大きく依存する点はおっしゃるとおりです。私が書いた「App EngineはBigtableのmultidimensionalな機能を提供していません」とは、履歴機能を提供していないという意味でした。

それともう1点、sortedについてですが、

@frsyukiさん：

途中ですっ飛ばしたけども、reads of short (←oneではない) row ranges are efficient にするためには、sortedである必要がある。Dynamoとかハッシュ関数かけるヤツはこのあたりがダメ。範囲検索ができるか否かは重大な問題。

sortedがタダのインデックスで良ければSkipGraphが要らなくなるしなぁ。

と古橋さんが指摘されてるとおり、Bigtable論文では、

Bigtable maintains data in lexicographic order by row key. The row range for a table is dynamically partitioned. Each row range is called a tablet, which is the unit of distribution and load balancing. As a result, reads of short row ranges are efficient and typically require communication with only a small number of machines.

・Bigtableではデータを行キーの辞書順で管理している
・テーブルを行範囲の単位で動的に分割している
・分割されたそれぞれのデータをタブレットと呼び、物理的および負荷的な分散の単位とする
・こうした仕組みによって、特定の行範囲の読み込みを少数のマシンとの通信で完了でき、効率的に実行可能である

と書いてあります。Bigtableでは特定のキー範囲のデータを「タブレット」と呼ばれる単位で分割し、複数台の「タブレットサーバー」に格納しています。そのため、例えば「キー0〜100番までのデータを取得する」なんてときに、ハッシュで世界中にばらまかれたデータを集めてくる…といった処理は不要で、多くの場合は1台のタブレットサーバーで「reads of short row ranges」をさくっと実行できる仕組みです。

ただし、タブレットサーバーと、実際にデータが保存されるGFSサーバーは論理的に分けられていて、多くの場合タブレットサーバーはローカルのGFSチャンクサーバーにデータを書き込むが、タブレットサーバーとGFSチャンクサーバーは物理的に異なるサーバーに別れることもあるとGoogleのJeff Deanさんは説明してます。つまりタブレットサーバーはGFSチャンクサーバー上のデータに対するインデックスとして機能しています。ということは、Skip Graphとは異なりますが、タブレットサーバーはレンジ単位で分割され分散化されたインデックスサーバーである。。と私は理解してます。

ですので、sortedとはいっても単純にキーと値のペアが辞書順でディスク上（もしくはファイル内に）にずらずら並んでいるというわけではなさそうです。

いずれにせよ、古橋さんのつぶやきから様々なことを学べて大変ありがたいです！ （古橋さんにBigtableを解説していただいている感じ）Bigtableについての理解がより深まった気がします。要するに、以前から分散KVSを研究されていた方からBigtableの内部構造について詳細に分析していただけるとものすごく嬉しいですね〜。