Bigtableと分散KVS

首藤さんがUNIX managineに「key-valueストアという名前には、キーと値のペア（key-value pair）を格納するデータ格納ソフトウェアというくらいの意味しかない」と書かれていたように、KVSにはRDBのようなベースとなるデータモデルとか定義があるわけじゃありません。むしろRDBへのアンチテーゼとして登場している様々な非リレーショナルなデータストアを象徴するキーワードとして使われるケースが多いと思います（そういった意味でNoSQLっていう表現は的を射てますね）。

なので「Bigtableが分散KVSなのかどうか」という問いは、KVSの定義が曖昧な以上あまり意味のある問いではありませんが、しかし様々なKVS実装とBigtableは何が違うのかを知るきっかけとして気になりました。

古橋さんの分散KVSの使い方より：

ここで言うところの分散KVSには、BigTableやCassandraなどの、いわゆるMulti dimensional sorted storeは含めていない。
これらの分散データストアはkey-valueよりも高級なデータモデルを持ち、単純なKVSの効率上の問題を解決しようとしている。

分散KVSを研究・実装されてきた方から見ると、Bigtableは「高級なデータモデル」を持つために、（DHT等で実装された多くの）の分散KVSとは区別しておこうという趣旨と思います。

一方、Bigtable: A Distributed Storage System for Structured Dataでは、
p1

2 Data Model

A Bigtable is a sparse, distributed, persistent multidimensional sorted map. The map is indexed by a row key, column key, and a timestamp; each value in the map is an uninterpreted array of bytes.

(row:string, column:string, time:int64) → string

つまり、Bigtableは「(row:string, column:string, time:int64)」をキーとして値を保持するmapであると説明しています。mapですから、素直に考えるとキーで値を保存するKVSであり、分散化されているので分散KVSと言えると思います。

ただ、一般的な分散KVSと異なる点は、古橋さんが指摘されているように「multidimensional」であり「sorted」であるという点です。

multidimensional？

直訳すると「多次元」ですが、これは単純に、2次元テーブルの個々のセル（値）について履歴を残せるという意味です。もともとBigtableはGoogle検索のために開発されたデータストアであり、Webコンテンツの過去の履歴を残すためにmultidimensionalである特性が生かされてきました。しかし上述のとおり、この多次元を構成するためのタイムスタンプもキーに含まれており、最終的には単純な文字列キーと値のペアとしてデータストアに格納されています。

また、Google App EngineではBigtableのmultidimensionalな機能を提供していません。またそれによって特に本質的な機能の欠落もありません（すごく不便とか、皆が欲しがっているとか）。よって、multidimensionalであるという特性は、Bigtableの本質的な特性とは言えないと私は思います。

sorted？

sortedとは言っても、もちろんBigtableでもデータを物理的にソートした順番で格納しているわけではなく、sparseに格納されたデータに対して、行／列／時間でソート済みのデータとしてアクセスするためのインデックスを別途備えているという意味です。

これはBigtableの非常に特徴的な機能であり、これのおかげで「範囲検索（レンジスキャン）ができる分散KVS」となっています。もしBigtableでレンジスキャンができなかったら、App EngineでGQLとかJDOQLによるクエリを実行することもできなかったかもしれません。

こうした「リッチ」さはBigtable論文でも明記されており、

p12

In terms of the distributed data storage model that one might provide to application developers, we believe the key-value pair model provided by distributed B-trees or distributed hash tables is too limiting. Key-value pairs are a useful building block, but they should not be the only building block one provides to developers. The model we chose is richer than simple key-value pairs, and supports sparse semi-structured data. Nonetheless, it is still simple enough that it lends itself to a very efficient flat-file representation, and it is transparent enough (via locality groups) to allow our users to tune important behaviors of the system.

要点をまとめると、

• 分散B-treeã‚„DHTによるkey-value pairモデルのみではアプリ開発者にとって制限が大きすぎる
• key-value pairは便利な構成要素だが、それだけでは足りない
• そこでBigtableではsparseな半構造データ（＝スキーマレスな構造化データ）を扱える、よりリッチなモデルを提供する
• かつ、非常に効率的なフラットファイル構造に保存したり、（ローカリティグループにより）システムの重要な振る舞いをユーザーが調整することが可能

Bigtable＝分散KVSベースのレンジスキャン可能な表形式データストア

つまり、KVSをベースに、より高級なデータモデル（＝レンジスキャン可能なソート済みのテーブル）を提供することがBigtableのミソ、というわけです。また、ローカリティグループ（すなわちApp Engineで言うところのキーの親子関係）をプログラマーが調整することで、DHTのようにデータを完全にばらばらに分散させるのではなく1か所に集めてローカリティを実現する（パフォーマンスやトランザクションが目的？）ことが可能になっています。

というわけで、Bigtableは「分散KVSベースのレンジスキャン可能な表形式データストア」という私の印象です。

めんどくさいので全部NoSQLと呼びましょう！w

追記

ところでGoogleさん、BigtableなのかBigTableなのかハッキリしてください！
SmalltalkとSmallTalk、JavaとJAVAとか、そういうところすごく気になるんですよ。。w

11/19追記

「multidimensional」の解釈については、考えが変わりました: http://d.hatena.ne.jp/kazunori_279/20091119/1258593439

12/14追記

Google自身はBigtableのことを分散KVSと捉えているようです：

How Entities and Indexes are Stored

Background

App Engine's datastore is built on top of Bigtable, a large, distributed key-value store that is built to scale.