BigtableについてはBigtable: A Distributed Storage System for Structured Dataを参照した。

Refinements(改良)

実装については前回紹介したが、高いパフォーマンスを実現することや、可用性、信頼性など改良点がいくつかあったがユーザーにとっては必要だ。今回はその詳細な実装について。

Locality groups

クライアントは複数のカラムファミリーをローカルグループとして含む事が出来る。分割されたSSTableはそれぞれのタブレットのローカルグループの為に生成される。分離したカラムファミリーは通常一緒にアクセスされることはないので、別のローカルグループに分割することで効率的になる。例えば、Webtableのページメタデータでは、一つのローカルグループにして、ページのコンテンツは違うグループにすることができる。アプリケーションは全部にわたるページコンテンツの読み込みは必要なく、メタデータを読みたいからである。
さらに、ローカルグループ毎に指定できる便利なパラメータがある。例えば、ローカルグループをインメモリに宣言できる。
インメモリのローカルグループのSSTablesはタブレットサーバーのメモリに遅延ロードされる。一度呼び出されると、カラムファミリーはローカルグループに所属し、ディスクにアクセスせずに、読み書きができる。この機能は頻繁にアクセスするちいさなデータなどに有用であり、内部的にはMETADATAテーブルのローカルカラムファミリーに使っている。

Compression

クライアントはSSTableがローカルグループの圧縮であるかどうか制御でき、かつ、どのフォーマットを使っているか制御できる。ユーザーが指定した圧縮形式をそれぞれのSSTableのブロックに指定できる。たとえ、分離して圧縮した一部のスペースを失った場合でも、SSTableの恩恵を受けて、読み込むのに全てを解凍する必要はない。多くのクライアントはtwo-pass custom compression schemeを使う。最初にBentleyとMcllroy's Schemeを使う。これはData Compression Using Long Commmon Stringsというものである。二つ目は16KBのデータを繰り返し探す早い圧縮アルゴリズムである。
これらはとても早くて、100〜200MB/sでエンコードする。
全体に渡ってスピードよりも格納容量の削減と強調しているが、意外にもこのtwo-pass圧縮は性能がいい。
例えば、Webtableでは、Webページコンテンツを格納する為にこの圧縮スキームを使用している。
一つの実験では、大きないくつかのドキュメントをローカルグループに圧縮した。実験の目的のために、我々は代わりに我々にに利用できるすべてのバージョンを格納する各文書の1バージョンに自分自身を制限したが、そのスキームで10から1のアーカイブ容量の削減にせいこうした。これはWebtableの行が同じホストのページは近くレイアウトしてあるので、Gzip圧縮よりも3から1か4から1削減されている。
これはBently-Mcllroyアルゴリズムが同ホストの大きな容量のページ内のボイラープレートを共有できるからである。
多くのアプリケーションでは、Webtableだけでなく、類似のデータをそろえてクラスタ化できるように行名を決めると、
いい圧縮比率を得られる。圧縮比率は同じあたいの複数のバージョンを持つデータをBigtableに格納したときも得られる。

Caching for read performance

読み込み性能を向上させる為にタブレットサーバーは2段階のキャッシングを行う。スキャンキャッシュは高レベルのキャッシュで、SSTableから返却されるタブレットサーバーへのKey-Valueペアのキャッシュである。ブロックキャッシュは、低レベルのキャッシュで、GFSから読み込まれる、SSTableのブロックである。
スキャンキャッシュはアプリケーションにとってもっとも便利で、同じデータを繰り替し読み込むのに有用である。ブロックキャッシュは最近読み込んだデータなどに有用である。(順序で読み込んだり、Hot Rowの同じローカルグループの違うカラムをランダムに読み込むなど）

Bloom Filters

Tablet Servingで記載した通り、読み込みのオペレーションはタブレットの状態を構成する全てのSSTableから読み込む。SSTableがインメモリでない場合は、多くのディスクへのアクセスで構成していただろう。クライアントが指定できるBloom Filterは特にローカルグループのSSTableに作成した方が良い。これによっていくつかのアクセスが削減される。
Bloom Filterは、SSTableが指定された行/列のペアごとに、任意のデータが含まれている可能性があるかどうかを尋ねることができる。特定のアプリケーションでは、BloomFiltersの格納のために使うタブレットサーバーの少量のメモリが、大幅に読み取り操作に必要なディスクのシーク数を減らすことができる。Bloom Filtersはディスクに触れる事無く、存在しないカラムや、行を見つけ出す事に使用する事もできる。

Commit-logの実装

もしそれぞれのタブレットのコミットログをGFS上に保持し、分割してかつ並列にたくさんのファイルに書き込みしたい場合。
それは、基礎となるそれぞれのGFSサーバーに実装されているファイルシステムに依存し、多数の物理ファイルに書き込むみや読み込みを発生する原因となる。さらに、分割されたファイルをタブレット毎に保持することもグループコミットの恩恵を削減してしまう。これらの問題を解決する為に、それぞれのタブレットサーバーに、物理ファイルが同じ違うタブレットにco-mingling mutationという可変のシングルコミットを付加した。
一つのログを提供するのであれば、正常時パフォーマンスは良くなるが、リカバリーには難がある。
それぞれのタブレットサーバーは普通は少量のタブレットをロードするが、タブレットサーバーが死んだ際に、タブレットは多量の他のタブレットサーバーへ移動する。タブレットの状態を復元する為に、オリジナルのタブレットサーバーによって書かれたコミットログから、新しいタブレットサーバーに可変の再適用が必要になる。
しかし、それらのタブレットの可変は同じ物理ログファイルにco-mingled mutationsが適用されている。
一つのアプローチは、このフルコミット·ログ·ファイルを読み取り、それを復旧するのに必要なタブレットに必要なエントリだけを適用するためにそれぞれの新しいタブレットサーバーになること。しかし、そのようなスキームがあっても、もし、100台のマシンが故障したタブレットサーバーから１つのタブレットを割り当てると、100回ログファイルが読み込まれることになる。
重複したログを読み込むのを防ぐ為にキーでコミットログを並び変える(テーブル、行名、ログ番号)
ソート済みの出力ファイルの中では、特定のタブレットへの全ての可変操作は隣接するタブレットへ行われるので、順序読み込みが続いて、１つのディスクへの探索が読み込み効率がいい。並行ソートの為に、ログファイルを64MBのセグメントで分割し、それぞれのセグメントを異なるタブレットサーバーでソートする。このソート処理は、マスターとコミットログファイルから可変復元が必要とされる初期化されたタブレットサーバーにより構成される。コミットログの書き込みは時々様々な理由によりつまずくことがある。可変をGFSのレイテンシから守る為に、それぞれのタブレットサーバーは実際には２つのログ書き込みスレッドを持っている。それぞれ自分自身のログファイルに書き込む。１つのスレッドはその時点で書き込んでいるスレッド、二つ目のスレッドは、１つ目のスレッドでの書き込みが遅い場合に、切り替えられ、コミットログのキューはこの新しいログ書き込みスレッドにより可変される。
ログエントリーは順序番号をもっていてこのログスイッチ処理で重複処理されないようにしている。

タブレット復元の高速化

マスターはタブレットを他のタブレットサーバーに移動する場合に、元のタブレットサーバーはまず、小圧縮をそのタブレットに対して行う。この圧縮は、タブレットサーバーのコミットログで未圧縮な量と復元時間を縮小する。この圧縮が完了すると、そのタブレットの供給を停止する。このタブレットを実際にアンロードする前には、タブレットサーバーは未圧縮のタブレットサーバーのログを取り除く為の他の小圧縮を行っている。この２回の小圧縮が完了したら、タブレットは他のタブレットサーバーからリカバリーログ無しでロードできる。

Exploiting immutability(不変の悪用)

SSTableキャッシュに加えて、Bigtableのシステムの様々な他の部分は我々が生成するSSTablesのすべてが不変であるという事実によって簡素化された。
例えば、SSTableから読み込むときは同期処理は必要ない。結果として行を超えての並行操作がとても効率的にできた。
memtableだけが唯一読み書き可能となっている。読み込み中の係争（競合？）を削減する為に、それぞれのmemtableの行をcopy on write と 読み書きを並列に行う。SStableが不変であることから、永遠に削除されたデータがGCされることがなくなっている。それぞれのタブレットのSSTableはMETADATAテーブルに登録されている。マスターはMETADATAに含まれているSSTableのセットをmark-and-sweep GCで廃れたSSTableを削除している。最後に不変のSSTableはタブレットの分割を素早く行う事を可能にしている。子のタブレットへ新しいセットのSSTableを生成する代わりに、子のタブレットは親のタブレットのSSTableを共有しよう。

３回に渡ってBigtableについて、Bigtable: A Distributed Storage System for Structured Dataを読んだメモを書いていったが、Datastoreとの関連性などはこの先実践していくなかで、結び付けていけたらと思っている。