実装

Bigtableはクライアントのライブラリー群、１つのマスターサーバー、多数のタブレットサーバーの３つの主要コンポーネントから構成されている。タブレットサーバーのクラスタ構成は追加や削除を動的に行える。マスターはタブレットサーバーの割当、サーバーの追加や満了を検知したり、ロードバランス、GFSのガベージコレクションなどの請け負っている。さらに、テーブルのようにスキーマの変更やカラムファミリーの作成を処理する。
タブレットサーバーはタブレットのセットを管理する（通常10から1000のタブレット）。タブレットサーバーはタブレットが大きくなったら分割したり、ロードされたら読み書きのリクエストを処理する。
多くのシングルマスターの分散システム同様に、クライアントのデータはマスターを介して移動しない。クライアントはタブレットサーバーと直接通信して読み書きを行う。Bigtableのクライアントはタブレットの場所の情報をマスターに頼っていないからで、ほとんどのクライアントはマスターと通信することはない。結果としてマスターのロードは軽くなる。
Bigtableクラスタは行の範囲に関連づいているタブレットのセットのテーブルを格納している。最初はテーブルは一つのタブレットからなるが、テーブルが大きくなれば自動的に分割される。デフォルトでは100から200MBくらいで分割される。

Tablet Location

タブレットの場所をB-treeに類似した3階層で格納する。

1つ目の階層は、ルートタブレットの場所を含むChubbyファイルで格納している。ルートタブレットは全てのタブレットの場所を格納している特別なメタデータテーブルを含んでいる。それぞれのメタデータテーブルはユーザータブレットの場所のセットを含んでいる。ルートタブレットはメタデータテーブルのなかで最初のタブレットだが、特別扱いされる。これはタブレットの場所の階層は３階層以上は持たないので分割されない。メタデータテーブルにタブレットのテーブルの識別子や行端をエンコードした行キーの下(もと)に格納される。それぞれのメタデータは大体1KBくらいである。128MBというメタデータのサイズは3階層のロケーションスキームには十分である。
クライアントライブラリーはタブレットの場所をキャッシュしている。もしクライアント側がタブレットの場所が分からない、または、タブレットの場所が間違えているなどの場合は、再帰的に情報を置き換える。
もしクライアント側のキャッシュが空の場合は、Chubbyから読み込むのだが、3往復の通信が必要になる。
また、もしキャッシュが古い場合、それが見つかるのはミスが起きたとき(メタデータタブレットは滅多に動かない）なので、
6往復必要になる。しかし、タブレットの場所はタブレットの場所はメモリ上にキャッシュされていて、GFSへのアクセスはしなくて済むさらにクライアント側でライブラリで事前読み込みが行われるとさらに節約になる。
それはメタデータテーブルを読むたびに、それは複数のタブレットのためのメタデータを読み込む。

Tabletの割当て

1回に1つのタブレットサーバーにそれぞれのタブレットは割り当てられる。
マスターは、タブレットサーバーのセットと、最近タブレットサーバーに割り当てられたタブレットと、割り当てられていないタブレットも含み監視している。未割当のタブレットがあり、タブレットサーバーに空きがあればタブレットサーバーにロードリクエストを送る事で、割当できる。
BigtableはChubbyをタブレットサーバーの開始を継続する為に用いられている。タブレットサーバーを開始すると、指定したChubbyディレクトリの一意のファイル名のロックを獲得する。マスターはタブレットサーバーを発見するため、このディレクトリを監視する。

ネットワークが断絶されるかChubbyセッションが途切れたなどで、獲得したロックが解除されると、タブレットサーバーはタブレットの供給を停止する。(Chubbyはネットワーク遅延が発生しているノードでロックが獲得され続けていないか監視する効率的な機構を提供している）
ファイルが存在している間はタブレットサーバーは再びロックを獲得する。もしファイルが存在しなくなった場合は、タブレットサーバーは供給を自分自身で停止する。タブレットの割当を早く行う為にタブレットサーバーが終了するたびにロックの解放を試みる。
マスターはタブレットが長い間停止している事を検知し、新しいタブレットの割当をなるべく早く行う責任がある。タブレットサーバーの停止を検知する為に、定期的にロック状態を聞いている。タブレットサーバーは、そのロックを失ったことを報告した場合またはマスターはその時にサーバに到達できなかった場合、マスターはサーバーのファイルに排他的ロックをかける。
マスターがロックを獲得できたら、Chubbyは生きているので、タブレットサーバーが死んでいるか、トラブルが起きているのかはChubbyから取得できるので、そのサーバーのファイルを削除して、供給を停止するようにする。
一度サーバーのファイルが削除されると未割当として割り当てられたサーバーを移動することができる。Chubbyとマスター間で通信脆弱にならないように、Chubbyのセッションが期限切れになったらマスターは自分自身でそれを殺す。
しかし、マスターが失敗するとTabletサーバーは切り替わらない。
マスターがクラスタ管理システムにより開始した際、変更される前に最近のタブレッット割当を見つける必要がある。
マスターは開始時に以下のことを行う。

Chubbyのユニークなマスターロックをつかみ、並行にインスタンス化されるのを防ぐ
Chubbyのサーバーディレクトリをスキャンし生きてるサーバーを見つける
それぞれのサーバーに割り当てられているタブレットを通信を行い探す
マスターはテーブルのセットを把握するため、METADATAをスキャンする。

タブレットを適切に割り当てる為に、まだ割り当てられていないタブレットを見つける度、マスターは未割当タブレットセットに追加する。
一つ問題なのが、METADATAタブレットが割り当てられるまで、METADATAのスキャンができない。
従って、ステップ3の間にルートタブレットが見つからなかった場合は、ステップ4のスキャンが行われる前に、未割当タブレットリストにルートタブレットを追加する。これは、ルートタブレットが割り当てられるようにしている。
ルートタブレットは全てのMETADATAタブレットの名前を持っていて、マスターはルートタブレットをスキャンした後にそれらを知る。
既存のタブレットのセットは、作成や削除、マージされたり、分割された時にしか変わらない。マスターは最後を除いて、全ての初期を行うのでそのように追跡することができる。
分割されたタブレットはタブレットサーバーに初期化されて以来特別扱いされる。METADATAテーブルに新しい分割されたタブレットの情報の書き込みを行う。分割がコミットされた際はマスターに通知がいく。分割通知が失われた場合(タブレットサーバーが死んだり、マスターが死んだとき)マスターは分割されたタブレットがタブレットサーバーにロードされる時に検出する。タブレットサーバーはMETADATAテーブルがそのタブレットをロードする時に見つける一部分となるので、マスターへ分割通知する。

Tablet Serving

下記の図のように、タブレットの状態はGFSに保存される。更新情報はコミットログに格納される。

いくつか更新すると、最近コミットした情報はmemtableという順序を持つバッファーに格納される。古い更新はSSTableに格納される。
タブレットサーバーはタブレットをリカバリーするときにメタデータをMETADATAテーブルから読み込む。このメタデータはRedoポイントのセットとタブレットを含むSSTableのリストから成り、それらは、全てのタブレットへのコミットログのポインターが含まれている。
サーバーはメモリへSSTableの索引を読み込みを行いREDOポイントからの更新を適用し、MemTableを再構築する。
書き込み処理がタブレットサーバーへ到達した際、サーバーはデータが有効か、また送信者は変更の権限を持っているかを確認する。認証はChubbyファイルから読み込みと書き込みを許可されたリストをもらう(ほとんどはChubbyクライアントのキャッシュから取得できる)有効な変更はコミットログに書き込まれる。小さな変更のコミットであれば、グループコミットを使うとスループットが向上する。書き込みが終わると、memtableへ挿入される。
読み込み処理がタブレットサーバーへ到達すると、書き込みと同様にデータの有効性と権限を確認する。有効な読み込みは、SSTableの順序のマージされたビューとmemtableから読み込まれる。SSTableとmemtableが辞書順序で並べてある間は、マージされたビューは効率的に構成できる。

圧縮

書き込み処理が行われたりするとmemtableのサイズは大きくなる。memtableの容量がしきい値に達すると凍結され、新しいmemtableが作成される。凍結したmemtableはSSTableに変換されてGFSに格納される。この小圧縮はタブレットサーバーのメモリ使用率を下げることと、サーバーが死んだときに読み込む量を減らす目的がある。圧縮処理中であっても読み込み書き込みは行える。
小圧縮では毎回SSTableが作成される。このまま続けて小圧縮が続けられると、読み込むときにマージが必要になってしまう。なので、数を指定してマージ処理が行われるようにしている。マージ圧縮はいくつかのSSTableとmemtableからコンテンツを読み込んで、新しいSSTableを書き出す。圧縮が終わると入力されたSSTableとmemtableは圧縮処理が完了すると、削除される。マージ圧縮は全てのSSTableを一つのSSTableに再書き込みすることから大圧縮と呼ばれる。
SSTableが大圧縮で作られたものであれば、生きているSSTableの削除を抑えるため、特別な削除用のデータを含むことができる。大圧縮は一方で、削除データと削除情報のないSSTableを作成する。Bigtableは全タブレットを通過し、定期的に大圧縮を行っている。それらの大圧縮は削除データにより使われていたリソースをとりもどし、適時にそれらのデータを消すようにすることもできる。

次回はRefinements(改良)編から。