Bigtable：疎な多次元マップという分散ストレージ

この論文が解いた問題

横にスクロール

2000年代前半のGoogleは、Web検索インデックス、Google Earth、Google Financeなど、性質のまったく異なるサービスを同じ基盤の上で動かそうとしていた。これらが扱うのは「構造化」されたデータだ。URLごとの本文やリンク、地図タイルの座標とメタデータといった、行と列で表せる情報である。しかしその規模はペタバイト級におよび、数千台のコモディティサーバーに分散させなければ到底さばけなかった。

リレーショナルデータベースの一式をそのまま持ち込む道もあった。だが当時のRDBMSは、この規模での水平スケールを前提に作られていない。結合や複雑なトランザクションといった豊かな機能の多くは、Googleのこれらの用途では必ずしも要らない。むしろ必要だったのは、次の四つを同時に満たす土台だった。

• ペタバイト級・数千台まで素直にスケールすること
• 低レイテンシのランダムな読み書きと、大規模なバッチ処理の両方をこなすこと
• 列を後から自由に足せる、スキーマの柔軟さ
• 故障が日常であるコモディティサーバー群の上で、壊れることを前提に動き続けること

土台の一部はすでにあった。分散ファイルシステムのGFS（GFSの論文を参照）は、巨大なファイルを数千台に分けて確実に保存できる。しかしGFSが得意なのは大きなファイルへの追記であって、「あるURLの、ある列だけを、いま書き換える」といった行単位のランダムな更新ではない。構造化データへ細かくアクセスする層が、GFSの上にもう一枚必要だった。

Bigtable（Changら、2006年）が示したのは、リレーショナルモデルとは別の、単純だが驚くほど応用の効くデータモデルと、それを数千台で動かすための仕組みである。

核心アイデア

データモデル：疎で、ソート済みの多次元マップ

Bigtableのデータモデルは、論文の一文にほぼ言い尽くされている。すなわち「疎で、ソート済みで、永続的な多次元のマップ」である。このマップのキーは (行キー, 列キー, タイムスタンプ) という三つ組で、対応する値はただのバイト列だ。数値でも文字列でも構造でもなく、その解釈はアプリケーション側に委ねられる。

言葉だけでは掴みにくいので、論文が例に挙げるWebページの表（Webtable）で図示する。行キーにURLを、列にページ本文やリンク元（アンカー）を置く。

キー = (行キー, 列キー, タイムスタンプ)     値 = バイト列

("com.cnn.www", "contents:",          t6) → …ページ本文 v6…
("com.cnn.www", "contents:",          t3) → …ページ本文 v3…   ← 同じセルの旧バージョン
("com.cnn.www", "anchor:cnnsi.com",   t9) → CNN
("com.cnn.www", "anchor:my.look.ca",  t8) → CNN.com

行キー com.cnn.www は、ドメイン名 www.cnn.com を逆順にしたものだ。こうすると同じドメインの下のページが辞書順で隣り合い、まとめて読みやすくなる。後述するとおり、この「行キーの設計」がBigtable運用の勘所になる。

三つ組のそれぞれの役割を整理すると次のようになる。

「疎」であることは重要だ。ある行にどの列が存在するかは行ごとにばらばらでよく、値のない列は一切場所を取らない。何百万もの列を定義しておいて各行では数個しか使わない、という設計が破綻なく成り立つ。これがスキーマの柔軟さの正体である。

行キーでソートし、タブレットで分ける

行キーは辞書順にソートして保持される。そしてテーブル全体を行キーの範囲でいくつもの区間に切り分け、その一区間を「タブレット（tablet）」と呼ぶ。タブレットこそが分散と負荷分散の単位だ。データが増えればタブレットは自動的に分割され、多数のタブレットサーバーへ割り当てられていく。

行キーが辞書順に並ぶという性質は、範囲スキャンを効率化する。隣り合うキーは同じタブレットに載りやすいので、「あるドメイン配下のページをまとめて読む」といった操作が、あちこちのサーバーに散らばらずに済む。

列ファミリと複数バージョン

列キーは単独の名前ではなく、「列ファミリ:修飾子」という二段構えになっている。先の例の anchor がファミリ、cnnsi.com が修飾子だ。列ファミリはあらかじめ作っておく数少ない単位で、アクセス制御やディスク上の圧縮はこのファミリごとに設定する。一方で修飾子は事実上いくらでも動的に増やせる。

各セルは、タイムスタンプの異なる複数バージョンを保持できる。先ほどの contents セルが v6 と v3 を同時に持つように、同じ場所の履歴を時間軸に沿って残せるわけだ。増えすぎを防ぐため、「最新のN個だけ残す」「一定期間より古いものは消す」といったガベージコレクションのポリシーを、列ファミリ単位で指定できる。

SSTable、GFS、Chubby

物理的な保存形式がSSTable（Sorted String Table）である。SSTableはキーでソートされた、一度書いたら変更しない不変のファイルだ。書き込みはまずコミットログに追記され、メモリ上の表（memtable）に反映される。memtableが膨らむと、その内容がまとめて新しいSSTableとしてディスクへ書き出される。読み出しのときは、memtableと複数のSSTableをマージして最新の値を組み立てる。増え続けるSSTableは、定期的なコンパクションで併合・整理される。

この「追記して溜め、後でまとめて整える」構造こそ、のちにLSM-Tree（Log-Structured Merge-Tree）として広く知られる書き込み最適化の考え方そのものだ。SSTableの実体は、先に触れた分散ファイルシステムGFSの上に置かれる。個々のサーバーが壊れても、データはGFSの複製に守られる。

最後の要がChubbyという分散ロックサービスだ。Chubbyは、どのタブレットがどのサーバーにあるかという位置情報の起点、スキーマやアクセス制御の情報、そして生きているマスターの選出などを一手に引き受ける。タブレットの位置は、Chubbyが指すルートタブレットを起点に三段階の階層をたどって解決される。全体の構成は1台のマスターと多数のタブレットサーバーからなるが、実際の読み書きはクライアントとタブレットサーバーの間で直接行われ、マスターを経由しない。だからマスターが一瞬止まってもデータへのアクセスは続く。そして読み書きは、一つの行キーの範囲でアトミックに行われることが保証される。

その後の影響

Bigtableの論文は、実装そのものを公開したわけではない。それでも設計思想が克明に描かれていて、外部の開発者がこれを手がかりに再実装できるほどだった。実際、Apache HBaseはBigtableをほぼ忠実になぞったオープンソース実装だ。GFSにあたる場所にHDFSを、Chubbyにあたる場所にZooKeeperを据え、タブレット・列ファミリ・SSTableに相当する仕組みをそのまま持つ。

Apache Cassandraは別の系譜との合流点になった。データモデルはBigtable由来の列ファミリの発想を受け継ぎつつ、分散のさせ方はAmazonのDynamo——コンシステントハッシュとマスターレスな構成——から採り入れた。「Bigtableのデータモデル＋Dynamoの分散」という組み合わせである。こうしてBigtableは、ワイドカラム型（wide-column）と呼ばれるNoSQLの一群の原型になった。

ストレージエンジンの側面でも影響は大きい。SSTableとコンパクションによる書き込み最適化、すなわちLSM-Treeは、Bigtableが大規模な実運用で通用することを証明した代表例だ。GoogleのLevelDB、そこから派生したRocksDBをはじめ、数多くの現代的なデータベースがこの構造を採る。ランダムな書き込みをシーケンシャルな追記に変えて速度を稼ぐこの考え方と、更新箇所を直接書き換えるB-Treeとの違いは、B-TreeとLSM-Treeの比較で詳しく扱う。

Google自身も歩みを進めた。行単位を超えたトランザクションと、地理的に分散しても強い整合性を保つ性質を求めて、BigtableはのちにSpannerへと発展していく。とはいえ、疎な多次元マップというデータモデルと、SSTable・GFS・Chubbyという役割分担の骨格は、今日のクラウド上のマネージドなワイドカラムサービスにまで、はっきりと受け継がれている。

まとめ

Bigtableが解いたのは、「構造化された巨大データを、コモディティサーバー数千台の上でどう扱うか」という問題だった。答えは、(行キー, 列キー, タイムスタンプ) をキーとする疎な多次元マップというデータモデルに集約される。行キーで辞書順にソートしてタブレットへ分割し、列は列ファミリにまとめ、セルは複数バージョンを持つ。物理層は不変のSSTableをGFSに置き、位置情報とロックはChubbyが束ねる。読み書きは行単位でアトミックだ。

この設計は、HBaseやCassandraといったワイドカラム型NoSQL、そしてLSM-Tree系ストレージの土台として、いまも動き続けている。原理を一度つかめば、これらのシステムに触れるときの見通しが一気に良くなるはずだ。分散システムを形づくった他の名論文は論文で辿る分散システムから辿れる。