Google App Engine Datastoreの詳細について、理解する為の、自分なりに反芻したメモ。今回はBigtableについて。Bigtable: A Distributed Storage System for Structured Dataを読んでみた。
DatastoreはBigtable（分散型の大規模なキー値ストア）上に構築されている。

概要

Bigtableは構造データを扱う分散型のストレージシステムで、それらは大規模なサイズでスケーリングするよう設計されている。
多くのプロジェクトがBigtableを使っていて、例えば、Webページのインデックス,Google Earth, Google Finance,これらのアプリケーションにおいてデータサイズや、レイテンシへの要求などで違えど、Bigtableはフレキシブルに要求を果たしている。

Data Model

分散型多次元疎マップであり、マップはタイムスタンプ、カラムキー、行キーでインデックスされていて、その値はバイト配列である。

上記はBigtableに格納されたWebページの例である。行名はURLで、contentsと称するカラムにはページのHTMLが格納されていてanchorと称するカラムにはアンカーのテキストが入っている。CNNのホームページは、スポーツ解説とmy.lookホームページから参照されている。行にはanchor:cnnsi.comとanchor.my.look.caを含んでおり、それぞれのアンカーセルは一つのバージョンを持っている。contentsカラムはタイムスタンプの３つバージョンを持っている。Webtable(Webページのコレクション)ではURLを行のキーとして使って、カラム名として様々なWebPageを設定し、contentsカラムにはコンテンツとフェッチした時間をタイムスタンプとして持っている。

行

行キーは任意の文字列で設定する。１行に対する読み込みと書き込みはその数などに関わらず、アトミック（成功するか失敗するかどっちか）に行われる。この設計は同じ行に対する並列での更新を簡単にするためである。
Bigtableの行は辞書順序でソートされる。行の長さはパーティションされる為に動的に変化し、それぞれの行は分散と負荷分散される。その単位をタブレットと呼ぶ。
行の長さを少なくすることが効率化につながるのとマシン間の通信を少なくできる。
クライアントはローカルでデータを扱えるようにする為にこれを操作できる。例えば、map.google.com/index.htmlはcom.google.maps/index.htmlとすることで同じドメインは近くの格納されるので、効率的に解析ができる。

カラムファミリー

カラムのキーはグループ化されたセットで、カラムファミリーと呼ばれる。これらはアクセス制御の単位を形式している。全てのデータはカラムファミリーに格納される。
データを格納する前にカラムファミリーを作成する必要がある。いずれかの列のキーの下に、そのファミリーの中で、ファミリー内の任意の列のキーを使用することができる。それは意図するところであって、その個別の列の番号テーブル内のファミリーが（せいぜい数百で）小さくなるとそのファミリーはめったに処理中には変化しない。対照的に、表の列(ファミリー内の列）の数は無制限がある可能性がある。
カラムキーはfamily:qualifierのように表現される。カラムファミリーの名前は任意の文字列。例えば、ウェブページの内容の言語をカラムファミリーとして格納する場合に、一つのカラムキーを使いそのファミリーにそれぞれのウェブページのlanguageIDを格納する。他にanchorカラムの為にカラムファミリーを便利に使うことができる。このファミリーのキーはそれぞれのanchorを表している。図で表されているように参照しているサイトのアンカー文字列がセルのタイトルとなっている。
また、アクセスコントロールやディスクとメモリ容量の換算はカラムファミリーレベルで扱われる。Webtableの例ではこれらの操作でそれぞれに違うタイプの適用を行っている。それは、新しいデータを追加したり、データを読み込んだり、派生のカラムファミリーを作ったり、既存のデータの読み込みだけを許可したり。ということができる。

タイムスタンプ

Bigtableはそれぞれのセルにタイムスタンプでインデックスされたバージョンを持つことができる。タイムスタンプは64bitのInteger型で格納される。これは明示的にアプリケーションで指定するか、自動的にミリ秒単位で設定される。アプリケーションは重複したタイムスタンプを設定しないようにする必要がある。異なったセルは最新のセルから読み込む為にタイムスタンプを降順にして並べる。
煩わしさをなくす為にそれぞれのカラムファミリー毎にガベージコレクションをサポートしている。クライアントは新しいバージョンのみかnバージョンまでは保持するという形で指定ができる。Webtableの例では、contentsカラムにバージョンを持たせていて、３つのバージョンを保持するようにしてしてある。

API

Bigtable APIでテーブルやカラムファミリーの作成や削除ができる。また、クラスタの変更、テーブル、カラムファミリー、メタデータ、アクセス制御の変更が出来る。またクライアントはテーブルのデータを読み込み、更新もできる。下記にC++のコードを記載するが、これはRowMutationをつかって一連の更新を行っている。

// Open the table
Table *T = OpenOrDie("/bigtable/web/webtable");
// Write a new anchor and delete an old anchor
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);

Applyを呼び出す事によって、Webtableへアトミックに変更を行っている。これはanchorのwww.cnn.comを追加して別のanchorを削除している。

下記のコードはScannerをつかってanchorをイテレートしている。
クライアントはスキャンする際に、行を制限することができる。

Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
  printf("%s %s %lld %s\n",
  scanner.RowName(),
  stream->ColumnName(),
  stream->MicroTimestamp(),
  stream->Value());
}

Bigtableはいくつか他の機能もサポートしていてそれを複合してデータを操作できる。
一つ目に読み込みと書き込みでアトミックな振る舞いをするsingle-row トランザクションがある。
バッチ処理では、クライアントで行·キー全体の書き込みに対してインターフェースを提供するが、Bigtableは現在、行キー全体にわたって一般的なトランザクションをサポートしていない。
二つ目にセルを整数カウンターとして使用できる。
最後に、Bigtableはサーバのアドレス空間内のクライアントが提供するスクリプトの実行をサポートしている。
そのスクリプトはSawzallと呼ばれるデータ操作の為の開発言語で記述されている。
また、MapReduceを使う事も出来る。入力データとしても出力先としてもBigtableを使う事ができる。

Building Blocks

BigtableはGoogleの他のいくつかのインフラで構成されている。
Bigtableは分散ファイルシステムでGoogle File Systemをログの格納やデータの格納で使っている。
Bigtableクラスターは様々は分散アプリケーションの共有マシンの中で動作している。また、ときどき他のアプリケーションのプロセスで同じマシンを共有して処理をおこなう。Bigtableはスケジューリングや共有リソースの管理やマシンの故障などのモニタリングしている管理システムに依存している。
また、BigtableのデータにはSStableファイルを内部でつかっている。SSTableは永続を提供し、キーからキーと値の両方を任意のバイト列である値に不変な順序でマッピングしている(※翻訳間違ってるかも）。
指定したキーに関連する値を見つけ出すのと、キーの範囲で指定したキーバリューペアをイテレートしたり動作を提供している。内部的には、それぞれのSSTableは連続したブロックを含んでいる。(典型的には64KBのブロックだが、変更できる）
ブロックのインデックスは(ブロックの最後に格納されている）ブロックの場所を示している。インデックスはSSTableをOpenした時にメモリー内でロードされる。検索は一つのディスクを使用して行われる。まず、バイナリサーチで適切なブロックを見つけ出し、ディスクから読み込む。必要に応じて、SSTableは完全にディスクに触れることなく、検索およびスキャンを実行することができ、メモリにマッピングすることができる。
BigtableはChubbyと呼ばれる分散型ロックサービスもつかっている。Chubbyは５つのレプリカから構成されていて、一つはマスターとしてとして選出され、リクエストをさばく。過半数のレプリカが生きていれば動作する仕組みになっている。
ChubbyはPaxosアルゴリズムを使用していて、可用性をキープする。
Chubbyはディレクトリと小さなファイルから構成されている名前空間を提供している。それぞれのディレクトリはアトミックに読み書きできるのと、ロック機構として使用できる。Chubbyのクライアントライブラリは可用性のあるChubbyファイルキャッシュを提供している。それぞれのChubbyクライアントはセッションの管理でChubbyサービスを使っている。それはリース満了時間内にそのセッションのリースを更新することができない場合、クライアントのセッションの有効期限が切れるように使っている。ChubbyクライアントはChubbyファイルやディレクトリが変更された時の通知を受ける為のコールバックを登録できる。Bigtableは様々な箇所で利用しているが、マスターをいつでも一つは確保するのと、Bigtableのブートストラップの場所を格納しているのと、タブレットサーバーを見つけ出すのと死んだサーバーのファイナライズ、スキーマ情報、アクセス制御リストの格納に使われている。Chubbyが長期間利用できなくなるとBigtableが使えなくなる。14Bigtableクラスタスパニングと11Chubbyインスタンスで測定をしてみたが、平均0.0047%でChubbyが使えない為にBigtableに書き込みが出来なくなった。最もChubbyが使えない状態の影響を受けた単一のクラスタ0.0326%であった。

次は実装について、続きは次回。