論文メモ Bigtable: A Distributed Storage System for Structured Data

November 30, 2020

Bigtableは、数千のコモディティサーバ上でペタバイト級のデータをホスティングできる分散ストレージであり、行、列、タイムスタンプをキーとして値の文字列を保存する。 論文の発表された2005年時点で、検索エンジンのインデックス, Google Earth, Google Financeなどの多様なアプリケーションの実装に使用されている。

行にあたるキーは最大64KBの任意の文字列で、単一の行キーで指定した読み込み、書き込みはアトミックに処理できる。 データは行キーの辞書順でtabletと呼ばれるパーティションを区切られて管理されている。 Tabletの概念は、半リレーショナルデータモデルの大域分散データベースSpannerに継承されている。

列キーの構文は\(\texttt{family:qualifier}\)であり、ファミリーと呼ばれる単位でグループ化される。 BigTableは、このColumn family単位にデータへのアクセスを制御する。 また、キーのタイムスタンプは64-bitの整数値であり、タイムスタンプの異なるデータをもつことで、データの版を管理している。

ログやデータはGoogle File Sytem(GFS)上に保存される。 ファイル形式は、Google SSTableという順序つきのイミュータブルなマップである。 SSTableは、デフォルトで64KBの複数の連続したブロックを含む。 ファイルを開いたらブロックのインデックスをメモリに読み込み、二分探索で目的のブロックへのインデックスを探す。 目的のインデックスを見つけたら、一度のシークでブロックを読み込むことができる。

Bigtableは、アクセスするクライント、1台のマスターサーバ、多数のタブレットサーバからなる。 タブレットサーバはtabletを管理するためのサーバであり、マスターサーバがtabletをタブレットサーバに配布する。 ほかにもマスターサーバは、タブレットサーバへの負荷分散や、クラスタを構成するタブレットサーバの増加や消失の検知、GFSのガベージコレクション、スキーマの変更を担う。

クラスタに参加するサーバを管理する実装には高可用性の分散ロックサービスChubbyが使われている。 Chubbyは、5つのレプリカからなり、そのうちの1つがマスターの役割をはたし、リクエストを処理する。 レプリカの整合性の保証はPaxosによって実装されている。 Chubbyは、ロックに使えるディレクトリと小さいファイルを提供する。 また、ファイルへの読み書きはアトミックに処理できる。 Bigtableは、マスターが高々1台しか存在しないことの保証やタブレットサーバの追加、消失の検知にChubbyを使用している。