Here is an introduction by kanda.motohiro@gmail.com of the paper "Bigtable: A Distributed Storage System for Structured Data".
以下は、 Bigtable: A Distributed Storage System for Structured Data の kanda.motohiro@gmail.com による抄訳です。
Bigtable: A Distributed Storage System for Structured Data
Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C. Hsieh, Deborah A. Wallach
Mike Burrows, Tushar Chandra, Andrew Fikes, Robert E. Gruber
{fay,jeff,sanjay,wilsonh,kerr,m3b,tushar,fikes,gruber}@google.com
Google, Inc.
概要
Bigtable は、構造化データを管理するための分散ストレージシステムです。それは、ペタバイトのデータが数千のコモディティサーバにあるような、とても大規模サイズにスケールするように設計されました。Google の多くのプロジェクトは、Bigtable にデータを格納します。それらには、ウェブインデクシング、Google Earth そして Google Finance が含まれます。これらのアプリケーションはとても異なる要求を Bigtable に課します。それは、データ長（ウェブページへの URL から、人工衛星画像まで）と遅延要件（バックエンドのバルク処理から、実時間データ提供まで）の両方にわたります。これら異なる要件にかかわらず、Bigtable はこれら全ての Google 製品に対する、柔軟で高性能なソリューションを提供することに成功してきました。この論文で、私たちは Bigtable が提供する単純なデータモデルを述べます。それは、クライアントにデータレイアウトと形式に関してダイナミックな制御を提供します。私たちはまた、Bigtable の設計と実装を述べます。
The Proceedings are published as a collective work, © 2006 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
１． はじめに
この二年半にわたり、私たちは、Google にある構造化されたデータを管理するための、Bigtable と呼ばれる分散ストレージシステムを設計、実装、そして配備してきました。Bigtable は、ペタバイトのデータ、数千のマシンにも安定してスケールするように設計されています。Bigtable は、いくつかのゴールを達成しました。広く使われること、スケーラビリティ、高性能、そして高可用性です。Bigtable は６０以上の Google 製品とプロジェクトで使われています。それらには、Google Analytics, Google Finance, Orkut, Personalized Search, Writely, そして Google Earth が含まれます。これらの製品は Bigtable を、いろいろな過酷な負荷のために使います。それらは、スループット志向のバッチ処理ジョブから、遅延に敏感な、エンドユーザへのデータ提供に及びます。これらの製品で使われる Bigtable クラスタは、一握りから数千のサーバにわたる、広い範囲の構成を持ち、数百テラバイトほどのデータを格納します。
多くの点で、Bigtable はデータベースに似ています。それは多くの実装戦略をデータベースと共用します。並列データベース[14] とメインメモリデータベース [13] はスケーラビリティと高性能を達成してきました。しかし、Bigtable はそれらとは異なるインタフェースを提供します。Bigtable は完全なリレーショナルデータモデルをサポートしません。。その代わりにそれは、データレイアウトと形式についてのダイナミックな制御をサポートする単純なデータモデルをクライアントに提供します。そして、クライアントが、元となるストレージにおけるデータの位置属性を推測することを許します。データは、行とカラム名を使ってインデックスされます。それらは、任意の文字列で構いません。Bigtable はまた、データを、解釈されない文字列として扱いますが、クライアントはしばしばこれらの文字列にいろいろな形式の構造化あるいは半構造化されたデータをシリアライズします。クライアントは、自分のデータの局所性を、自分のスキーマを注意深く選ぶことで制御することができます。最後に、Bigtable スキーマパラメタは、データをメモリとディスクのどちらから提供するのかをクライアントがダイナミックに制御することを許します。
２節はデータモデルをより詳細に述べます。３節は、クライアント API の概要を提供します。４節は Bigtable が依存する、元となる Google インフラストラクチャを簡単に述べます。５節は、Bigtable 実装の基本を説明し、６節は Bigtable の性能を上げるために私たちが行った微調整のいくつかを述べます。７節は、Bigtable の性能の測定結果を提供します。８節で、Bigtable が Google においてどのように使われているかの例をいくつか述べます。９節で、Bigtable を設計、サポートすることで私たちが学んだことをいくつか議論します。最後に、１０節は関連する研究で、１１節は結論です。
２ データモデル
Bigtable は、疎で、分散し、永続的な、複数次元のソーテッドマップです。マップは、行キー、カラムキー、そしてタイムスタンプでインデックスされます。マップにあるそれぞれの値は、解釈されないバイト配列です。
(row:string, column:string, time:int64) → string
私たちは、Bigtable のようなシステムの潜在的な用途をいろいろ調査した後、このデータモデルに落ち着きました。私たちの設計の選択のいくらかを動機づけた、一つの具体的な例として、ウェブページと関連する情報の大きな集合のコピーを維持したいとしましょう。それは多くの異なるプロジェクトで使うことができます。このテーブルを Webtable と呼びます。Webtable において、URL を行キーとして使い、ウェブページのいろいろな属性をカラム名としましょう。そして、ウェブページの内容を、それをフェッチした時のタイムスタンプの下で、contents: カラムに格納しましょう。これを図１に示します。
行
テーブルの行キーは任意の文字列（現在、６４KB までの長さです。しかし、ほとんどのユーザにおいて、１０から１００バイトが典型的長さです）です。単一の行キーの下にあるすべてのデータの読み書きはアトミックです（行にあって、読み書きされる異なるカラムの数によらず）。これは、同じ行に同時実行する更新があるときのシステムの振る舞いをクライアントが容易に推論できるようにするための設計上の決定です。
Bigtable は、データを行キーによる辞書順に維持します。テーブルの行レンジは、ダイナミックにパーティションされます。行レンジのそれぞれを、タブレットと呼びます。それは、分散とロードバランスの単位です。この結果、狭い行レンジのリードは、効率的で、典型的には少ないマシンとの通信しか必要としません。クライアントはこの属性を活用して、行キーを選択し、データアクセスに良い局所性を得ることができます。たとえば、Webtable において、同じドメインにあるページは、URL のホスト名コンポーネントを逆にすることで、連続した行にグループ分けされます。例えば、maps.google.com/index.html のためのデータは、com.google.maps/index.html キーの下に格納します。同じドメインからのページを互いに近くに格納することは、ある種のホストとドメイン解析をより効率的にします。
カラムファミリー
カラムキーは、カラムファミリーと呼ばれる集合にグループ分けされます。それは、アクセス制御の基本的単位となります。あるカラムファミリーに格納されるすべてのデータは、通常は同じ型です（同じカラムファミリーにあるデータは、一緒に圧縮されます）。あるカラムファミリーに属するいずれかのカラムキーにデータを格納する前に、カラムファミリーを作らなくてはいけません。ファミリーを作った後、そのファミリーに属するカラムキーはどれでも使うことができます。あるテーブルにある異なるカラムファミリーの数は、小さく（最大で、数百）、そのファミリーは動作中にほとんど変わらないのが、私たちの意図です。それに対して、テーブルは無限の数のカラムを持つことができます。
カラムキーは、以下のシンタックスで命名されます。family:qualifier。カラムファミリー名は、印字可能でなくてはいけません。qualifier は任意の文字列で構いません。Webtable のカラムファミリーの例は、language です。それはそのウェブページが書かれている言語を格納します。language ファミリーには、一つのカラムキーしか使いません。それは、それぞれのウェブページの言語 ID を格納します。このテーブルのもう一つの便利なカラムファミリーは、anchor です。このファミリーのそれぞれのカラムキーは、図１に示すように、単一のアンカーを表現します。qualifier は、参照するサイトの名前です。セルの内容は、リンクテキストです。
アクセス制御と、ディスクとメモリの両方の割り当ては、カラムファミリーのレベルで行われます。私たちの Webtable の例では、この制御によって複数の異なるタイプのアプリケーションを管理できます。新しいベースデータを追加するもの、ベースデータを読んで、派生するカラムファミリーを作成するもの、そして、既存のデータを読むことだけが許される（そしてプライバシーの理由で、既存のファミリーの全てを読むことができないかもしれない）もの。
タイムスタンプ
Bigtable のそれぞれのセルは、同じデータの複数のバージョンを含むことができます。これらのバージョンは、タイムスタンプでインデックスされます。Bigtable のタイムスタンプは６４ビット整数です。それは、Bigtable によってアサインされることがあります。その場合、それは、マイクロ秒単位の「実際の時刻」を表現します。あるいは、クライアントアプリケーションはそれを明示的にアサインすることもできます。コリジョンを避ける必要のあるアプリケーションは、自分で、一意のタイムスタンプを生成しなければいけません。セルの異なるバージョンは、タイムスタンプの降順に格納されます。なので、最新バージョンが最初に読まれます。
バージョンのあるデータの管理の面倒さを減らすために、カラムファミリーごとの設定が二つサポートされ、自動的にセルバージョンをガーベッジコレクトするように Bigtable に指示します。クライアントは、セルの最近の n バージョンだけが維持されるか、あるいは、十分に新しいバージョンだけが維持される（例えば、最近７日の間に書かれた値だけを維持する）かのどちらかを指定できます。
私たちの Webtable の例では、contents: カラムに格納されるクロールされたページのタイムスタンプを、それらのページのバージョンが実際にクロールされた時刻に設定します。前記のガーベッジコレクション機構によって、全てのページの最近３つのバージョンだけが維持されます。
３ API
Bigtable API は、テーブルとカラムファミリーを作成、削除する関数を提供します。それはまた、クラスタ、テーブル、そしてアクセス権制御などのカラムファミリーメタデータを変更する関数を提供します。
クライアントアプリケーションは、Bigtable に値を書き、削除し、それぞれの行から値を検索し、あるいは、テーブルにあるデータのサブセットにわたって列挙を行うことができます。図２は、RowMutation 関数例を使っていくつかの更新をする C++ コードを示します。（例を短くするために、不要な詳細は除いてあります。）Apply 呼び出しが、Webtable へのアトミックな変更を実行します。それは、www.cnn.com に一つのアンカーを追加し、他のアンカーを削除します。
図３は、Scanner 関数例を使って、特定の行の全てのアンカーを列挙する C++コードを示します。クライアントは、複数のカラムファミリーにわたって列挙を行うことができます。スキャンによって生成される行、カラム、そしてタイムスタンプを限定する機構もいくつかあります。例えば、前記スキャンを、カラムが anchor:*.cnn.com 正規表現にマッチするアンカーだけを生成するように制限することができます。あるいはそのタイムスタンプが、現在時刻よりも１０日以内のアンカーだけを生成できます。
Bigtable は、ユーザがデータをより複雑な方法で操作するための他のいくつかの機能をサポートします。まず、Bigtable は単一行のトランザクションをサポートします。それは単一の行キーの下で格納されるデータに対して、アトミックなリード・モディファイ・ライトシーケンスを実行するために使えます。Bigtable は現在では、複数の行キーにまたがる一般的なトランザクションをサポートしません。なお、クライアントにおいて複数の行キーにまたがるライトをバッチするためのインタフェースを提供します。二つ目に、Bigtable は、サーバのアドレス空間で、クライアントが提供したスクリプトの実行をサポートします。スクリプトは、データを処理するために Google で開発された、Sawzall [28] と呼ばれる言語で書かれます。今のところ、私たちの Sawzall ベースの API は、クライアントスクリプトが Bigtable に書き戻すことは許しません。しかし、それは実際、いろいろな形式のデータ変換、任意の式をもとにするフィルタリング、そしていろいろな演算子による総計を可能とします。
Bigtable は、Google において開発された、大規模並列計算を実行するためのフレームワークである MapReduce [12] とともに使うことができます。私たちは、Bigtable を、MapReduce ジョブの入力ソースとしても、出力ターゲットとしても使うことができるようにするためのラッパーのセットを書きました。
４ 構成要素
Bigtable は Google インフラストラクチャのいくつかの他の要素の上に作られます。Bigtable は、ログとデータファイルを格納するために、分散 Google File System (GFS) [17] を使います。Bigtable クラスタは、典型的には、広い種類の他の分散アプリケーションを走らせる共用マシンプール内で動作します。そして、Bigtable プロセスはしばしば、他のアプリケーションからのプロセスと同じマシンを共用します。Bigtableは、ジョブをスケジュールしたり、共用マシンのリソースを管理したり、マシン障害に対処したり、そしてマシン状態を監視したりする点で、クラスタ管理システムに依存します。
Bigtable データを格納するために、Google SSTable ファイル形式が内部的に使われます。SSTable は、永続的で、順序付けられた、更新不可能な、キーから値へのマップを提供します。キーと値はどちらも任意のバイト文字列です。指定されたキーと関連づいた値を検索したり、指定されたキーの範囲において、全てのキーと値の組を列挙するための操作が提供されます。内部的に、それぞれの SSTable はブロック（典型的には、それぞれのブロックは、６４KB ですが、これは構成可能です）のシーケンスを含みます。ブロックを位置づけるために、ブロックインデックス（SSTable の最後に格納されます）を使います。インデックスは、SSTable がオープンされたときに、メモリにロードされます。検索は、一度のディスクシークで実行されることができます。まず、メモリ上のインデックスで二分探索を実行して正しいブロックを見つけ、次にそのブロックをディスクから読みます。オプションで、SSTable を完全にメモリにマップすることもできます。それにより、検索と走査はディスクを触らないで行えます。
Bigtable は、Chubby [8] と呼ばれる高可用で永続的な分散ロックサービスに依存します。Chubbyサービスは５つのアクティブな複製からなります。そのうちの一つがマスターに選出されて、アクティブに要求を処理します。サービスは、複製の過半数が実行していて、互いに通信できるときにライブです。Chubby は、Paxos アルゴリズム [9, 23] を使って障害があっても複製が矛盾ないように維持します。Chubby はディレクトリと小さなファイルから構成されるネームスペースを提供します。それぞれのディレクトリあるいはファイルは、ロックとして使うことができます。ファイルへの読み書きはアトミックです。Chubby クライアントライブラリは、Chubby ファイルへの矛盾のないキャッシュを提供します。それぞれの Chubby クライアントは、Chubby サービスと、セッションを維持します。クライアントのセッションは、もしそれがセッションリース満了期間内にリースを再更新できないと満了します。クライアントのセッションが満了すると、クライアントはすべてのロックとオープンハンドルを失います。Chubby クライアントは、Chubby ファイルとディレクトリに、変更の通知あるいはセッションの満了を受けるためのコールバックを登録することもできます。
Bigtable は、Chubby をいろいろな仕事のために使います。いかなる時でも最大一つのアクティブなマスターがいることを保証するため、Bigtable データのブートストラップデータ（５．１節を参照）の位置を格納するため、タブレットサーバを発見し、タブレットサーバの終了を後始末する（５．２節を参照）ため、Bigtable スキーマ情報（それぞれのテーブルのカラムファミリー情報）を格納するため、そして、アクセス制御リストを格納するため。もし Chubby がある時間以上使用不可能となったら、Bigtable は使用不可能となります。私たちは最近、１１の Chubby インスタンスをまたがる、１４の Bigtable クラスタにおいてこの効果を測定しました。Chubby が使用不可能である（Chubby の障害あるいはネットワーク問題が原因で）ために Bigtable に格納されたなんらかのデータが使用不可能である Bigtable サーバ時間の平均割合は、0.0047% でした。Chubby が使用不可能であるために最も影響された単一のクラスタにおけるその割合は、0.0326% でした。
５ 実装
Bigtable 実装は、三つの主なコンポーネントを持ちます。それぞれのクライアントにリンクされるライブラリ、一つのマスターサーバ、そして多くのタブレットサーバです。タブレットサーバは、負荷の変化に対応するために、クラスタにダイナミックに追加（あるいは削除）することができます。
マスターは、タブレットをタブレットサーバにアサインしたり、タブレットサーバの追加と満了を検出したり、タブレットサーバの負荷をバランスしたり、そして GFS にあるファイルをガーベッジコレクションしたりする責任を持ちます。さらにそれは、テーブルやカラムファミリーの作成などのスキーマの変更を処理します。
それぞれのタブレットサーバはタブレットのセット（典型的には、タブレットサーバごとに、１０から１０００タブレットがあります）を管理します。タブレットサーバは、自分がロードしているタブレットへの読み書き要求を処理します。そして大きくなりすぎたタブレットを分割することもあります。
多くのシングルマスター分散ストレージシステム[17, 21] でそうであるように、クライアントデータはマスターを通過しません。クライアントは、読み書きのために、タブレットサーバと直接通信します。Bigtable クライアントは、タブレットサーバの位置情報に関して、マスターに依存しないため、ほとんどのクライアントはマスターと一切通信しません。その結果、現実にはマスターの負荷は軽いです。
Bigtable クライアントは多くのテーブルを格納します。それぞれのテーブルはタブレットのセットから構成され、それぞれのタブレットは行レンジに関連するすべてのデータを含みます。最初は、それぞれのテーブルはただ一つのタブレットから構成されます。テーブルが大きくなるにつれ、それは自動的に複数の、デフォルトでほぼ 100-200 MB の大きさの複数のタブレットに分割されます。
５．１ タブレット位置
タブレット位置情報を格納するために、B+-tree [10] に似た、３レベルの階層を使います（図４）。
最初のレベルは、Chubby に格納されているファイルで、ルートタブレットの位置を持ちます。ルートタブレットは、特別の、METADATA テーブルに、全てのタブレットの位置を持ちます。それぞれの METADATA タブレットは、ユーザタブレットのセットの位置を持ちます。ルートタブレットは、METADATA テーブルの最初のタブレットであるだけのことです。しかし、それは特別に扱われます。それは決して分割されません。タブレット位置階層が、３レベル以内であることを保証するためです。
METADATA テーブルは、タブレットの位置を、そのタブレットのテーブル識別子とその最終行をエンコードした行キーの下に格納します。それぞれの METADATA 行は、メモリに、ほぼ 1KB のデータを格納します。128 MB METADATA タブレットという控えめな制限の下で、この３レベル位置スキームは、234 テーブル (あるいは、128 MB タブレットで 261 バイト)をアドレッシングするのに十分です。
クライアントライブラリはタブレット位置をキャッシュします。もしクライアントがタブレットの位置を知らないか、キャッシュされた情報が正しくないと分かったときは、それは、再帰的に、タブレット位置の階層を上ります。クライアントのキャッシュが空の場合、位置アルゴリズムは３回のネットワークラウンドトリップを必要とします。それには、Chubby からの１回のリードが含まれます。クライアントのキャッシュが無効な場合、位置アルゴリズムは最大６回のネットワークラウンドトリップを必要とすることがあります。無効なキャッシュエントリはミスした時だけ判明するからです（METADATA タブレットはあまり速く動かないと仮定します）。タブレット位置はメモリに格納されているため、GFS アクセスは必要ありません。それでも私たちは、一般ケースのコストをさらに減らすために、クライアントライブラリにタブレット位置をプリフェッチさせます。それは、METADATA テーブルを読むときにいつでも、一つ以上のタブレットのメタデータを読みます。
また、私たちは、METADATA テーブルに、二次的な情報を格納します。それは、それぞれのタブレットに関するすべてのイベントのログ（サーバがそれを処理し始めた時など）を含みます。この情報は、デバッグと性能解析に有用です。
５．２ タブレットの割り当て
それぞれのタブレットは一度に一つのタブレットサーバに割り当てられます。マスターは生きているタブレットサーバのセットと、現在の、タブレットのタブレットサーバへの割り当てを追跡します。それは、割り当てられていないタブレットも含みます。もしあるタブレットが割り当てられていなくて、そのタブレットのための十分の余裕があるタブレットサーバがあるならば、マスターはそのタブレットを、そのタブレットサーバにタブレットロード要求を出すことで割り当てます。Bigtable は、Chubby を使ってタブレットサーバを追跡します。タブレットサーバが開始した時、それは、特定の Chubby ディレクトリにある一意の名前のファイルを作り、排他的ロックを取ります。マスターはこのディレクトリ(servers ディレクトリ)を監視して、タブレットサーバを発見します。タブレットサーバはその排他的ロックを失った時、タブレットの提供を止めます。例えば、ネットワーク分割のために、サーバがその Chubby セッションを失った時。(Chubby は、タブレットサーバが自分がまだ自分のロックを持っているかを、ネットワークトラフィックを起こすことなくチェックするための効率的な機構を提供します。)タブレットサーバは、自分のファイルがまだあるならば、それに排他的ロックを再度取ろうと試みます。ファイルが既にない時は、タブレットサーバは決して今後、サービスを提供できないので、自分で停止します。タブレットサーバが終わる時にはいつでも、(例えば、クラスタ管理システムが、そのタブレットサーバのマシンをクラスタから除いたため)、それは自分のロックを放そうとしますから、マスターはそのタブレットをより早く再割り当てできます。
マスターは、タブレットサーバがそのタブレットをもう提供しなくなった時を検出して、それらタブレットをできるだけ早く再割り当てする責任があります。タブレットサーバがそのタブレットをもう提供しなくなった時を検出するために、マスターはそれぞれのタブレットサーバに定期的に、自分のロックの状態を聞きます。もしタブレットサーバが自分のロックを失ったと報告するか、あるいはマスターが最近数回試みても、サーバに到達できない時は、マスターはそのサーバのファイルに排他的ロックを取ろうとします。もしマスターがロックを取れたら、Chubby は生きていて、タブレットサーバが死んでいるか、Chubby に到達することに問題があるかどちらかです。なので、マスターはそのタブレットサーバが決してサービスを提供できないことを保証するため、そのサーバファイルを削除します。サーバのファイルが削除されたら、そのサーバに以前に割り当てられていた全てのタブレットを、割り当てられていないタブレットのセットに移すことができます。Bigtable クラスタが、マスターとChubby の間のネットワーク問題のために脆弱にならないことを保証するため、マスターは、自分と Chubby のセッションが満了した場合、自分から終了します。しかし、前に述べたように、マスターの障害は、タブレットのタブレットサーバへの割り当てを変えません。
クラスタ管理システムがマスターを開始した時、マスターは、タブレットの割り当てを変更する前に、現在のその割り当てを発見する必要があります。マスターは開始時に以下のステップを実行します。(１)マスターは、Chubby にある、一意のマスターロックを取ります。それはマスターが同時に開始するのを防ぎます。(２)マスターは、Chubby の servers ディレクトリを走査して、生きているサーバを見つけます。(３)マスターは、生きている全てのタブレットサーバと通信して、それぞれのサーバにどのタブレットが既に割り当てられているかを発見します。(４)マスターは、METADATA テーブルを走査して、タブレットのセットを確認します。この走査で既に割り当てられていないタブレットが見つかったら、マスターはそのタブレットを、割り当てられていないタブレットのセットに加えます。それは、タブレット割り当ての候補となるタブレットです。
一つ面倒なのは、METADATA テーブルの走査は、METADATA タブレットが割り当てられるまで起き得ないことです。なので、この走査(ステップ4)を始める前に、ステップ３の間にルートタブレットの割り当てが発見されなかったら、マスターはルートタブレットを、割り当てられていないタブレットのセットに加えます。これにより、ルートタブレットが割り当てられることが保証されます。ルートタブレットは、全ての METADATA タブレットの名前を含むので、マスターはルートタブレットを走査した後は、それら全てを知ります。
存在するタブレットのセットは、タブレットが作成、削除された時と、二つの既存のタブレットがマージされて一つのより大きなタブレットになる時、あるいは、既存のタブレットが二つのより小さいタブレットに分割される時にだけ、変化します。マスターは、最後のもの以外の全てを開始するため、これらの変化を追跡できます。タブレット分割は特別に扱われます。タブレットサーバが開始するからです。タブレットサーバは、新しいタブレットの情報を METADATA テーブルに記録することで、分割をコミットします。分割がコミットしたら、それはマスターに通知します。分割通知が失われた時(タブレットサーバあるいはマスターが落ちたために)、マスターは、今は分割したタブレットをロードするようにタブレットサーバに頼んだ時に、新しいタブレットを検出します。タブレットサーバはマスターに、分割を通知します。なぜならば、それが METADATA テーブルに見つけるタブレットエントリは、マスターがロードするように頼んだタブレットの一部しか指定しないからです。
5.３ タブレット提供
タブレットの永続的状態は、図５に示すように、ＧＦＳに格納されています。更新は、redo レコードを格納するコミットログにコミットされます。これらの更新のうち、最近コミットされたものは、memtable と呼ばれるメモリ上のソートされたバッファに格納されます。より古い更新は、SSTable のシーケンスに格納されます。テーブルを回復するために、タブレットサーバはそのメタデータを METADATA テーブルから読みます。このメタデータは、タブレットと、redo ポイントのセットを構成する SSTable の一覧を含みます。それらは、そのタブレットのデータを含む可能性のある任意のコミットログへのポインタです。サーバは SSTableのインデックスをメモリに読んで、redo ポイント以降にコミットされた全ての更新を適用することで、 memtable を再構築します。
タブレットサーバにライト操作が届くと、サーバはそれが正しい形式であり、送信者が変更を行う権限があるかを確かめます。権限の確認は、Chubby ファイル(それはほぼ常に、Chubby クライアントキャッシュにヒットします)から、ライトできる人の一覧を読むことで行います。有効な変更はコミットログに書かれます。多くの小さい変更のスループットを上げるために、グループコミットが使われます[13, 16] 。ライトがコミットされた後、その内容は memtable に挿入されます。
タブレットサーバにリード操作が届くと、同様に、正しい形式であることと、適切な権限があることが確認されます。有効なリード操作は、SSTable のシーケンスと、memtable をマージしたビューに対して行われます。SSTable と、 memtable は、辞書順にソートされたデータ構造なので、マージしたビューは効率的に作れます。
タブレットが分割、マージする時も、到着するリードとライト操作は続行できます。
5.４ コンパクション
ライト操作が進むにつれて、memtable の大きさは増えます。memtable の大きさがしきい値を超えたら、memtable は凍結され、新しい memtable が作られます。凍結した memtable は SSTable に変換されて、 GFS に書かれます。このマイナーコンパクション処理は二つのゴールを持ちます。それはタブレットサーバのメモリ使用量を減らします。そして、このサーバが落ちた時に、回復の間、コミットログから読まなくてはいけないデータの量を減らします。コンパクションをしている間、入ってくる読み書き操作は続行できます。
マイナーコンパクションのたびに、新しい SSTable ができます。このふるまいがチェックなしに続いたら、リード操作は任意の数の SSTable からの更新をマージする必要があるかもしれません。その代わりに、私達は、バックグラウンドで定期的にマージコンパクションをすることで、そのようなファイルの数を制限します。マージコンパクションは、いくつかの SSTable と memtable の内容を読んで、新しい SSTable を書き出します。コンパクションが終わったらすぐに、入力の SSTable と memtable は捨てることができます。
全ての SSTable をただ一つの SSTable に書き換えるマージコンパクションを、メジャーコンパクションと呼びます。メジャーコンパクションでないものによって作られた SSTable は、まだ生きている古い SSTable にある、削除されたデータを抑制するための特別な削除エントリを含むことがあります。それに対して、メジャーコンパクションは、削除情報や、削除されたデータを含まない SSTable を作ります。Bigtable はその全てのタブレットを走査して、それらにメジャーコンパクションを適用します。このメジャーコンパクションにより、Bigtable は削除されたデータが使っていた資源を回収することができ、削除されたデータがシステムから適切な時間内に消えることを保証します。それは、センシティブなデータを格納するサービスにとって重要です。
以降は、原文を読んで下さい。
以上