概要#
Bigtable は、構造化データを管理するための分散ストレージシステムであり、非常に大規模に拡張できるように設計されています：数千台の商用サーバーに分散された PB レベルのデータ。Google 内部の多くのプロジェクトが Bigtable を使用してデータを保存しており、ウェブインデックス、Google Earth、Google Finance などが含まれます。これらのアプリケーションは、データのサイズ（URL からウェブページ、惑星画像まで）や遅延要件（バックグラウンドバッチ処理からリアルタイムデータサービスまで）において、Bigtable に異なる要求を突きつけています。さまざまな要求があるにもかかわらず、Bigtable はこれらすべての Google 製品に対して柔軟で高性能なソリューションを提供することに成功しました。
はじめに#
過去 2 年半の間に、私たちは Google で構造化データを管理するための分散ストレージシステムである Bigtable を設計、実装、展開しました。Bigtable は、PB レベルのデータと数千台のマシンに対して信頼性を持って拡張できるように設計されています。Bigtable は、広範な適用性、拡張性、高性能、高可用性という複数の目標を達成しています。Bigtable は、Google Analytics、Google Finance、Orkut、パーソナライズド検索、Writely、Google Earth など、60 以上の製品やプロジェクトで使用されています。これらの製品は、スループット指向のバッチ処理ジョブからユーザー側の遅延に敏感なサービスまで、さまざまな高負荷のワークロードを処理するために Bigtable を使用しています。これらの製品で使用される Bigtable クラスターは、数台から数千台のサーバーにわたる広範な構成範囲をカバーし、数百 TB のデータを保存しています。
多くの点で、Bigtable はデータベースに似ており、データベースと共有する実装戦略が多くあります。並列データベースやインメモリデータベースは、拡張性と高性能を実現していますが、Bigtable はこれらのシステムとは異なるインターフェースを提供します。Bigtable は完全なリレーショナルデータモデルをサポートしていませんが、代わりにクライアントに対してシンプルなデータモデルを提供し、データのレイアウトとデータ形式の動的制御をサポートし、クライアントが基盤ストレージに表されるデータの局所的な性質を推論できるようにします。データは行と列によってインデックスされ、その名前は任意の文字列であることができます。Bigtable はデータを生の文字列として扱い、クライアントはさまざまな形式の構造化および半構造化データをこれらの文字列にシリアライズします。クライアントは、データ形式を慎重に選択することでデータの局所性を制御できます。最後に、Bigtable のスキーマパラメータは、クライアントがメモリまたはディスクからデータを取得するかどうかを動的に制御できるようにします。
データモデル#
bigtable は、行キー、列キー、およびタイムスタンプによってインデックスされた疎な分散永続化多次元順序ハッシュテーブルであり、各値は生のバイト配列です。
(row: string, column: string, time: int64) -> string
多くの潜在的な Bigtable-like システムを研究した結果、私たちはこのデータモデルを選定しました。実際の設計決定に影響を与えた例として、異なるプロジェクトで使用できる大規模なウェブページコレクションとその関連情報のコピーを維持したいと仮定します。このテーブルを Webtable と呼び、Webtable では URL を行キーとして使用し、ウェブページのさまざまな属性（ウェブページの内容、アンカーポイントなど）を列キーとして使用し、対応する（異なる時間に取得された）内容を値として保存します。以下の図のように：
行#
テーブル内の行キーは任意の文字列であることができます（現在の最大は 64KB）。同じ行キーの下で行われるすべての読み書き操作は原子性を持ち、この設計により、クライアントは同じ行を並行して更新する際のシステムの動作を推測しやすくなります。Bigtable は行キーの辞書順にデータを維持します。テーブル内の行の範囲は動的にパーティションされており、各行範囲は tablet と呼ばれ、分散および負荷分散の基本単位でもあります。このため、小さな行範囲を読み取るのは非常に効率的で、通常はごく少数のマシンと通信するだけで済みます。クライアントは行キーを選択する際にこの特性を利用し、データにアクセスする際により良い局所性を得ることができます。たとえば、Webtable では URL のホスト名部分を反転させることで、同じドメインのウェブページをグループ化します。たとえば、maps.google.com/index.html のデータをキー com.google.maps/index.html の下に保存し、同じドメインのページを互いに近い位置に保存することで、いくつかのホストやドメインの分析をより効率的に行えるようにします。
列ファミリー#
列キーは、列ファミリーと呼ばれる集合にグループ化され、アクセス制御の基本単位を構成します。1 つの列ファミリー内に保存されるすべてのデータタイプは一般的に同じです（同じ列ファミリーのデータを一緒に圧縮します）。列ファミリーは、データが列ファミリー内の任意の列キーに保存される前に作成する必要があります。列ファミリーが作成された後は、その列ファミリー内のすべての列キーが使用可能になります。
私たちの目的は、1 つのテーブル内の異なる列ファミリーの数を少なく（最大で数百）し、操作中に列ファミリーがほとんど変わらないようにすることです。それに対して、1 つのテーブルには無限の数の列が存在する可能性があります。列キーは次の構文で命名できます：ファミリー：識別子。列ファミリーの名前は印刷可能でなければなりませんが、識別子は任意の文字列であることができます。たとえば、Webtable の列ファミリーの 1 つは言語であり、ウェブページの内容を作成するために使用される言語を保存します。私たちは言語列ファミリー内で 1 つの列キーのみを使用し、各ウェブページの言語 ID を保存します。このテーブルのもう 1 つの有用な列ファミリーはアンカーポイント（anchor）であり、このファミリー内の各列キーは個別のアンカーポイントを表します（上の図のように）、その識別子は参照される URL であり、内容はリンクテキストです。
アクセス制御、ディスクおよびメモリの計測は、列ファミリーのレベルで行われます。Webtable の例では、この制御により、さまざまなアプリケーションを管理できます：新しい基礎データを追加するもの、基本データを読み取り、派生した列ファミリーを作成するもの、現在存在するデータを表示することしか許可されないもの（プライバシーの理由からすべての列ファミリーを表示できない場合もあります）。
タイムスタンプ#
Bigtable 内の各セルは、同じデータの複数のバージョンを含むことができ、これらのバージョンはタイムスタンプによってインデックスされます。Bigtable のタイムスタンプは 64 ビット整数です。タイムスタンプは、Bigtable によってマイクロ秒で表される実際の時間に設定されるか、クライアントアプリケーションによって明示的に設定されることがあります。アプリケーションは、衝突を避けるために一意のタイムスタンプを生成する必要があります。セルの異なるバージョンは、降順で保存され、最新のデータが最初に読み取られます。
異なるバージョンのデータを管理する負担を軽減するために、Bigtable では、クライアントが最近の n 個のバージョンのみを保存するか、十分に新しいバージョンのみを保存するように指定できる、2 つの列ファミリー レベルの設定をサポートしています（たとえば、最新の 7 日間に書き込まれたデータ）。
Webtable の例では、取得したウェブページのタイムスタンプを、これらのページが実際に取得された時刻に設定し、上記で説明したガベージコレクションメカニズムにより、各ページの最近の 3 つのバージョンのみを保存します。
API#
Bigtable API は、テーブルおよび列ファミリーの作成と削除の機能を提供し、クラスター、テーブル、および列ファミリーのメタデータを変更する機能も提供します。たとえば、アクセス制御権限を変更することができます。
クライアントアプリケーションは、行を単独で検索して値を読み書きしたり、テーブル内のデータのサブセットを横断したりできます。以下は、RowMutation 抽象を使用して一連のデータ更新を実行する C++ コードの例です（無関係なコードは省略されています）。ここで、Apply 呼び出しは Webtable 上で原子性のある変更を実行し、www.cnn.com 行にアンカーポイントを追加し、異なるアンカーポイントを削除しました。
// テーブルを開く
Table *T = OpenOrDie("/bigtable/web/webtable");
// 新しいアンカーポイントを書き込み、古いアンカーポイントを削除する
RowMutation r1(T, "com.cnn.www");
r1.Set("anchor:www.c-span.org", "CNN");
r1.Delete("anchor:www.abc.com");
Operation op;
Apply(&op, &r1);
以下は、Scanner 抽象を使用して指定された行のすべてのアンカーポイントを横断する C++ コードの例です。クライアントは複数の列ファミリーを横断でき、スキャンによって生成される行、列、およびタイムスタンプの数を制限するための多くのメカニズムがあります。たとえば、スキャンを anchor:*.cnn.com の正規表現に一致するアンカーポイントの列のみを生成するように制限したり、最近 10 日以内のタイムスタンプに該当するアンカーポイントのみを生成したりできます。
Scanner scanner(T);
ScanStream *stream;
stream = scanner.FetchColumnFamily("anchor");
stream->SetReturnAllVersions();
scanner.Lookup("com.cnn.www");
for (; !stream->Done(); stream->Next()) {
printf("%s %s %lld %s\n",
scanner.RowName(),
stream->ColumnName(),
stream->MicroTimestamp(),
stream->Value());
}
Bigtable は、ユーザーがデータをより複雑な方法で処理できるようにするためのさまざまな他の機能もサポートしています。まず、Bigtable は単一行トランザクションをサポートしており、単一行キーの下で原子性のある読み取り - 変更 - 書き込みシーケンスを実行できます。現在、Bigtable は一般的なクロス行トランザクションをサポートしていませんが、クライアントにクロス行バッチ書き込みのインターフェースを提供しています。次に、Bigtable はセルを整数カウンターとして使用することを許可します。最後に、Bigtable はサーバー側のアドレス空間内でクライアントが提供するスクリプトを実行することをサポートしており、このスクリプトは Google が開発したデータ処理用の言語 Sawzall を使用します。現在、Sawzall ベースの API は、クライアントスクリプトを Bigtable に書き込むことをサポートしていませんが、さまざまな形式のデータ変換、任意の式に基づくフィルタリング、さまざまな操作による集約をサポートしています。
Bigtable は、Google が開発した大規模並列計算を実行するためのフレームワークである MapReduce にも使用でき、Bigtable を MapReduce ジョブの入力ソースおよび出力ターゲットとして使用できるようにするための一連のラッパーを作成しました。
基本要素#
Bigtable は、Google の多くの他のインフラストラクチャの上に構築されています。Bigtable は GFS を使用してログおよびデータファイルを保存します。Bigtable クラスターは、一般的に共有のマシンプール内で実行され、広範な他の分散アプリケーションも実行されており、Bigtable プロセスは他の分散アプリケーションプロセスと同じマシンを共有することがよくあります。Bigtable は、ジョブスケジューリング、共有マシン上のリソース管理、マシン障害の処理、マシン状態の監視を行うために、クラスター管理システムに依存しています。
Bigtable は、内部データを保存するために Google SSTable ファイル形式を使用します。SSTable は、永続的で順序付けられた不変のキー値マッピングテーブルを提供し、キーと値は任意のバイト文字列です。SSTable は、指定されたキーに対応する値を検索し、指定されたキー範囲に基づいてすべてのキー値ペアを横断する操作を提供します。
内部的に、各 SSTable はいくつかの連続したブロックを含んでおり（通常、各ブロックのサイズは 64KB ですが、構成可能です）、SSTable の末尾にはブロック位置を特定するためのインデックスブロックがあります。SSTable が開かれると、このブロックはメモリにロードされます。1 回のクエリ操作は、単一のディスク検索によって完了する可能性があります：最初にメモリインデックス内でバイナリ検索を実行して正しいブロックを見つけ、その後ディスク内で対応するブロックを読み取ります。さらに、SSTable はメモリ全体にマッピングされることもでき、ディスク操作なしでクエリやスキャンを実行できます。
Bigtable は、高可用性で永続的な分散ロックサービス Chubby に依存しています。Chubby サービスは 5 つのアクティブなレプリカで構成され、そのうちの 1 つがマスターとして選出され、リクエストの処理を積極的に行います。大多数のレプリカが生存し、互いに通信できるとき、サービスはオンラインになります。Chubby は、故障時にレプリカが一貫性を保つことを保証するために Paxos アルゴリズムを使用します。Chubby は、ディレクトリと小さなファイルで構成される名前空間を提供し、各ディレクトリまたはファイルはロックとして使用でき、単一のファイルの読み書きは原子性を持ちます。Chubby クライアントライブラリは、Chubby ファイルの一貫性キャッシュを提供します。各 Chubby クライアントは、Chubby サービスとのセッションを維持します。リース時間が切れ、リースを更新できない場合、クライアントセッションは期限切れになります。クライアントセッションが期限切れになると、すべてのロックとオープンファイルハンドルが破棄されます。Chubby クライアントは、Chubby ディレクトリおよびファイル上でコールバックを登録して、変更やセッションの期限切れの通知を受け取ることもできます。
Bigtable は、さまざまなタスクを処理するために Chubby を使用します：常に最大 1 つのアクティブなマスターのみが存在することを保証すること、Bigtable データの起動位置を保存すること、tablet サーバーを発見し、tablet サーバーの死亡を確認すること、Bigtable フォーマット情報（各テーブルの列ファミリー情報）を保存すること、アクセス制御リストを保存することです。Chubby が長時間利用できない場合、Bigtable も利用できなくなります。最近、11 の Chubby インスタンスにまたがる 14 の Bigtable クラスターでこの影響を測定しました。Chubby の利用不可（Chubby の中断またはネットワークの問題）により、Bigtable に保存されたデータの一部が利用できなくなる Bigtable サービスの時間の平均パーセンテージは 0.0047% であり、単一のクラスターが Chubby の利用不可の影響を受ける最大パーセンテージは 0.0326% です。
実装#
Bigtable の実装は、各クライアントにリンクされたライブラリ、マスターサービス、および多数の tablet サービスの 3 つの主要なコンポーネントで構成されています。tablet サービスは、クラスター内で動的に追加または削除でき、ワークロードの変化に適応します。
マスターは、テーブルを tablet サーバーに割り当て、新しい tablet サーバーを発見し、期限切れの tablet サーバーを見つけ、tablet サーバーの負荷を均等に分配し、GFS 内のファイルのガベージコレクションを処理します。さらに、テーブルや列ファミリーの作成など、スキーマの変更も処理します。
各 tablet サーバーは、tablet の集合を管理し（一般的に 1 つの tablet サーバーに 10 から 1000 の tablet が存在します）、そのロードされた tablet の読み書きリクエストを処理し、過度に大きな tablet を分割します。
多くの単一マスターの分散ストレージシステムと同様に、クライアントデータは直接マスターに送信されず、tablet サーバーと直接読み書き通信を行います。Bigtable クライアントは、tablet の位置情報を取得するためにマスターに依存しないため、ほとんどのクライアントはマスターと通信しません。最終的に、実際にはマスターの負荷は非常に低いです。
1 つの Bigtable は多くのテーブルを保存し、各テーブルは一連の tablets で構成され、各 tablet は行範囲内の関連するすべてのデータを含みます。最初は各テーブルに 1 つの tablet しかありませんが、テーブルデータが増えると、自動的に複数の tablets に分割されます。デフォルトでは、各 tablet のサイズは 100-200MB です。
Tablet の位置情報#
私たちは、tablet の位置情報を保存するために、B+ ツリーに似た 3 層の階層構造を使用しています。
第 1 層は、root tablet の情報を含む Chubby 上のファイルです。root tablet は、特別な METADATA テーブル内にすべての tablet の位置情報を含んでいます。各 METADATA tablet は、ユーザー tablets の集合を含んでいます。root tablet は実際には METADATA テーブルの最初の tablet であり、決して分割されることはなく、tablet 位置構造が 3 層を超えないようにします。
METADATA テーブルは、tablet の表識別子にその末尾を加えた行キーでエンコードされた行キーに、tablet の位置情報を保存します。各 METADATA 行は、メモリ内に約 1KB のデータを保存します。METADATA tablet は、適度な制限で 128MB を採用しており、これにより私たちの 3 層の位置情報スキームは 2^34 個の tablets、すなわち 2^61 バイトのデータをアドレス指定するのに十分です。（訳注：root metatablet は 128MB / 1KB = 2^17 個のサブエントリを収容でき、各サブエントリも 128MB / 1KB = 2^17 個の第 3 層エントリを収容でき、合計で 2^34 個の tablets を持ち、各 tablet のサイズは 100-200 MB で 128MB を取ると、合計サイズは 2^61 バイトになります。）
クライアントライブラリは tablet の位置情報をキャッシュします。クライアントが tablet の位置を知らない場合、またはキャッシュされた位置情報が正しくない場合、ターゲット tablet の位置情報を再帰的に上に向かって検索します。クライアントのキャッシュが空である場合、アドレッシングアルゴリズムは、3 回のネットワーク往復を必要とし、そのうちの 1 回は Chubby の読み取りを含みます。クライアントのキャッシュが古い場合、アドレッシングアルゴリズムは最大 6 回の往復を要する可能性があります（METADATA tablet が頻繁に移動しないと仮定した場合）、キャッシュが古いことが判明するのは、キャッシュがヒットしなかった場合のみです（訳注：最初にキャッシュを使用し、上に向かって 3 回ヒットしなかった場合、次に上から下に再度 3 回クエリを行います）。
tablet の位置情報はメモリ内に保存されているため、GFS にアクセスする必要はありません。クライアントライブラリを介して tablet の位置情報を事前に取得することで、オーバーヘッドをさらに削減しました：クライアントは METADATA テーブルを読み取るたびに複数の tablets を読み取ります。
METADATA テーブル内には、各 tablet に関連するイベントのすべてのログ（たとえば、tablet がサービスを開始したとき）などの二次情報も保存されており、これらの情報はデバッグやパフォーマンス分析に役立ちます。
Tablet の割り当て#
各 tablet は同時に 1 つの tablet サーバーにのみ割り当てられ、マスターは生存しているすべての tablet サーバーの集合と、現在のすべての tablet の tablet サーバー上の割り当て状況を追跡します。割り当てられていない tablet も含まれます。tablet が未割り当てであり、利用可能な tablet サーバーに十分なスペースがある場合、マスターは tablet をその tablet サーバーに割り当てるために tablet ロードリクエストを送信します。
Bigtable は Chubby を使用して tablet サーバーを継続的に追跡します。tablet サーバーが起動すると、指定された Chubby ディレクトリ内に一意のファイルを作成し、排他ロックを要求します。マスターはこのディレクトリを監視します。
tablet サーバーが排他ロックを失うと、作業を停止します：たとえば、ネットワーク分割によりサーバーが Chubby セッションを失った場合（Chubby は、tablet サーバーがネットワークトラフィックを使用せずに自分がロックを保持しているかどうかを確認できる効率的なメカニズムを提供します）。ファイルが存在する限り、tablet サーバーはファイルの排他ロックを再取得しようとしますが、ファイルが存在しなくなると、tablet サーバーは再びサービスを提供できなくなり、自らを終了させます。いつでも、tablet サーバーが終了する場合（たとえば、クラスター管理システムが tablet サーバーのマシンをクラスターから削除した場合）、保持しているロックを解放しようとします。これにより、マスターは他のサーバーに tablet をより迅速に割り当てることができます。
マスターは、tablet サーバーがその tablets にサービスを提供しなくなったときにそれを検出し、これらの tablets をできるだけ早く再割り当てします。tablet サーバーがその tablets にサービスを提供しなくなったときを検出するために、マスターは定期的に各 tablet サーバーのロック状態を問い合わせます。tablet サーバーがロックを失ったと報告するか、マスターが数回の試行の後にそのサーバーに到達できない場合、マスターは対応するサーバーのファイルの排他ロックを取得しようとします。マスターがロックを取得できる場合、Chubby が生存しており、tablet サーバーが終了したか、Chubby との通信に障害が発生した可能性があるため、マスターはサーバーファイルを削除して、再びサービスを提供できないことを保証します。サーバーファイルが削除されると、マスターは以前にこのサーバーに割り当てられていたすべての tablets を未割り当ての tablets の集合に移動できます。Bigtable クラスターがマスターと Chubby の間のネットワークの影響を受けないようにするために、マスターは Chubby のセッションが期限切れになると自らを終了しますが、前述のように、マスターの障害は tablet サーバー上の tablets の割り当てを変更しません。
クラスター管理システムがマスターを起動すると、変更を行う前に tablet の割り当て状況を把握する必要があります。マスターは次の手順を実行して起動します：1. マスターは Chubby 上で一意のロックを要求し、並行するマスターインスタンスを回避します；2. マスターは Chubby 上の servers ディレクトリをスキャンして生存しているサーバーを見つけます；3. マスターは各生存している tablet サーバーと通信して、各 tablet サーバーがどの tablet を割り当てられているかを確認します；4. マスターは METADATA をスキャンしてすべての tablet を確認し、未割り当ての tablet を見つけるたびに、未割り当ての tablet の集合に追加します（訳注：未割り当て tablet の集合の tablet のみが割り当て可能です）。
複雑な状況は、METADATA tablets が割り当てられた後でなければ METADATA テーブルをスキャンできないことです。したがって、4 番目のスキャンを開始する前に、3 番目のステップで root tablet が見つからなかった場合、マスターは root tablet を未割り当ての集合に追加します。このステップにより、root tablet が割り当てられることが保証されます。root tablet はすべての METADATA tablets の名前を含んでいるため、マスターが root tablet をスキャンした後、すべての tablets を知ることができます。
現在存在する tablets の集合は、次の状況で変更されます：tablet が作成または削除される、2 つの既存の tablet がより大きな tablet に統合される、または 1 つの tablet が 2 つの小さな tablet に分割される。マスターはこれらの変更を追跡できます。なぜなら、彼は最後の項目を除くすべての変更を開始したからです（訳注：作成 / 削除 / 統合はマスターによって実行され、分割はそうではありません）。tablet の分割は特別です。なぜなら、それは tablet サーバーによって実行されるからです。tablet サーバーは、METADATA テーブルに新しい tablet の情報を記録することで分割操作を提出し、分割操作が提出されると、マスターに通知します。この通知が失われた場合（tablet サーバーまたはマスターがダウンした場合）、マスターは tablet サーバーに分割された tablet をロードするように要求するときに発見します。tablet サーバーは METADATA テーブルで要求された tablet のエントリを見つけ、そのエントリには一部しか含まれていないからです（訳注：行範囲によって判断されます）。その後、tablet サーバーはマスターに tablet が分割されたことを通知します。
Tablet のサービス#
tablet の永続的な状態は GFS に保存されます。上の図のように、更新操作は redo ログを含むコミットログを提出します。これらの更新に関して、最近のコミットはメモリ内の memtable と呼ばれる順序付きバッファに保存され、古いコミットは一連の SSTables に保存されます。tablet を復元するために、tablet サーバーは METADATA テーブルから tablet のメタデータを読み取ります：tablet を構成する SSTables のリストと、tablet データを含む可能性のあるすべてのコミットログを指す redo ポインタの集合が含まれます。サーバーは SSTables のインデックスをメモリに読み込み、すべての redo ログを実行して更新を適用し、memtable を再構築します。
tablet サーバーに書き込み操作が到達すると、サーバーは形式が正しいかどうかを確認し、送信者がこの変更を実行する権限を持っているかどうかを確認します。権限は、Chubby ファイルから書き込み者リストを読み取ることで実行されます（ほとんどの場合、キャッシュにヒットします）。有効な変更はコミットログに書き込まれ、グループコミット（group commit）が小さな変更のスループットを向上させるために使用されます。書き込みがコミットされると、そのメモリは memtable に挿入されます。tablet サーバーが読み取り操作を受け取ると、同様に形式と権限が適切かどうかを確認します。合法的な読み取り操作は、memtable と一連の SSTables のマージビューで実行されます。SSTables と memtable はどちらも辞書順にソートされたデータ構造であるため、マージビューは効率的に構築できます。
tablet の分割または統合時には、読み書き操作を継続できます。
コンパクション#
書き込み操作が実行された後、memtable のサイズは増加し、memtable のサイズがしきい値に達すると、memtable は凍結され、新しい memtable が作成されます。凍結された memtable は SSTable に変換され、GFS に書き込まれます。この * マイナーコンパクション（minor compaction）* プロセスには 2 つの目的があります：tablet サーバーのメモリ使用量を縮小し、サーバーのダウン時にコミットログデータを読み取る必要がある回数を減らします。コンパクション中は、読み書き操作を継続できます。
各マイナーコンパクションは新しい SSTable を作成します。この操作が続くと、読み取り操作は任意の数の SSTables の更新をマージする必要があるかもしれません。対照的に、バックグラウンドで定期的にマージコンパクションを実行することで、ファイルの数を制限します。各マージコンパクションは、いくつかの SSTables と memtable の内容を読み取り、新しい SSTable に書き込み、コンパクションが完了した後、入力の SSTable と memtable を破棄できます。
すべての SSTables をマージして 1 つの SSTable にする操作は * メジャーコンパクション（major compaction）* と呼ばれ、非マイナーコンパクションによって生成された SSTables は、古い SSTable にまだ生存しているデータを抑制する特別な削除エントリを含む可能性があります（訳注：よくわかりませんでした）。言い換えれば、メジャーコンパクションによって生成された SSTable は、削除情報や削除されたデータを含まない（訳注：すべてのデータがこの 1 つの SSTable に存在し、削除に関連する情報を保存する必要がない）ことになります。Bigtable は定期的にすべての tablets をスキャンし、メジャーコンパクション操作を実行します。これらのメジャーコンパクション操作により、Bigtable は削除されたデータが使用していたリソースを回収し、削除されたデータがシステムから迅速に消失することを保証します。これは、ストレージに敏感なデータを扱うサービスにとって重要です。
改良#
上記の実装には、ユーザーが要求する高性能、高可用性、信頼性を達成するために、いくつかの最適化が必要です。本節では、これらの改善を強調するために、一部の実装について詳しく説明します。
ローカリティグループ#
クライアントは、複数の列ファミリーをローカリティグループに組み合わせることができ、各 tablet は各ローカリティグループに対して個別の SSTable を作成します。通常一緒にアクセスされない列ファミリーを異なるローカリティグループに分けることで、読み取り効率を向上させることができます。たとえば、Webtable のページメタデータを 1 つのローカリティグループに配置し、ページ内容を別のローカリティグループに配置することで、ページメタデータを読み取る必要があるアプリケーションは、ページの内容を読み取る必要がなくなります。
さらに、各ローカリティグループに基づいて、いくつかの有用な微調整パラメータを指定できます。たとえば、ローカリティグループをメモリ内に保存するように宣言できます。メモリ内の SSTables に保存されたローカリティグループは、tablet サーバーによって遅延ロードされます。ロードされると、このローカリティグループに属する列ファミリーを読み取る際にディスクにアクセスする必要がなくなります。この機能は、小さなブロックですが頻繁にアクセスされるデータにとって非常に便利です：内部的には、METADATA テーブル内でこの機能を使用して列ファミリーを特定しています。
圧縮#
クライアントは、ローカリティグループの SSTables を圧縮するかどうかを制御できます。圧縮する場合は、指定された圧縮形式を使用します。ユーザーが指定した圧縮形式は、各 SSTable ブロックに使用されます（サイズはローカリティグループの微調整パラメータで指定できます）。各ブロックを個別に圧縮すると、スペースを失う可能性がありますが、利点は、SSTable の一部を読み取る際にファイル全体を解凍する必要がないことです。多くのクライアントは、2 ステップのカスタム圧縮形式を使用しており、最初のステップでは Bentley and McIlroy’s scheme を使用して大きなウィンドウ内で長い共通の文字列を圧縮し、2 番目のステップでは、16KB サイズのウィンドウで重複パターンを検索する高速圧縮アルゴリズムを使用します。両方の圧縮プロセスは非常に高速で、現代のマシンではエンコード速度が 100–200 MB/s、デコード速度が 400–1000 MB/s です。
圧縮アルゴリズムを選択する際には、速度よりもスペース削減を重視していますが、この 2 ステップの圧縮モードは予想以上の良い結果を得ています。たとえば、Webtable ではこの圧縮モードを使用してウェブページの内容を保存しています。ある実験では、圧縮されたローカリティグループに大量の文書を保存しました。実験の目的のために、各文書に 1 つのバージョンのみを保存することを制限しました（訳注：同じ文書の複数のバージョンの内容は非常に似ている可能性があります）。この圧縮モードは、10:1 の圧縮比を達成しました。これは、通常の Gzip が HTML ページで 3:1 または 4:1 の圧縮比を得るのに比べてはるかに優れています。理由は、Webtable の行ストレージ方式が、同じホストのすべてのページが近い位置に保存されるため、Bentley-McIlroy アルゴリズムが同じホストのページ上の大量の共有テンプレートを特定できるからです（訳注：多くのウェブページが同じヘッダーやフッター、または他の静的テンプレートを持っている可能性があります）。
多くのアプリケーションは、Webtable のように、類似のデータを最終的に一緒に集約する行名を選択するため、非常に高い圧縮比を達成できます。Bigtable は、複数のバージョンのデータを保存する際には、さらに高い圧縮比を実現します。
読み取り性能のためのキャッシュ#
読み取り性能を改善するために、tablet サーバーは 2 層のキャッシュを使用しています。Scan Cache は高レベルのキャッシュで、tablet サーバーコード内の SSTable インターフェースが返すキー値ペアをキャッシュします。Block Cache は低レベルのキャッシュで、GFS から読み取った SSTables ブロックを直接キャッシュします。Scan Cache は、同じデータを繰り返し読み取るアプリケーションに最も便利であり、Block Cache は、短期間に読み取られるデータが非常に近いアプリケーションに最も便利です（たとえば、順次読み取りや、ホット行上で同じローカリティグループの異なる列をランダムに読み取る場合など）。
ブルームフィルター#
前述のように、読み取り操作は tablet サーバーの状態を構成するすべての SSTables を読み取る必要があります。SSTables がメモリにない場合、多くのディスクアクセスが発生する可能性があるため、クライアントが特定のローカリティグループのためにブルームフィルターを作成するように指定できるようにして、この数を減らします。ブルームフィルターを使用すると、SSTable に指定された行 / 列ペアのデータが含まれているかどうかを確認できます。特定のアプリケーションにとって、tablet サーバーが非常に少量のメモリを使用してブルームフィルターを保存することで、読み取り操作のディスクアクセス数を大幅に減少させることができます。ブルームフィルターを使用することは、存在しない行や列に対するクエリの大部分がディスクにアクセスする必要がないことを意味します。
コミットログの実装#
各 tablet のコミットログを異なるログファイルに書き込むと、GFS には非常に大量のファイルが同時に書き込まれることになります。各 GFS サーバー上の基盤となるファイルシステムの実装に依存して、これらの書き込みは異なる物理ログファイルに書き込むために大量のディスク位置決定（seek）を引き起こす可能性があります。さらに、各 tablet に異なるログファイルへの書き込みは、グループコミット最適化の効率を低下させます。なぜなら、グループが非常に小さくなるからです（訳注：異なるコミットが異なるファイルに書き込まれると、同じグループにまとめることができません）。この問題を修正するために、各 tablet サーバーは変更を単一のコミットログに追加し、同じ物理ログファイル内で異なる tablets の変更を混合します。
単一のログファイルを使用することで、通常の操作で大幅な性能向上が得られますが、復元が複雑になります。tablet サーバーがダウンすると、そのサービスを提供していた tablets は多数の他の tablet サーバーに移動されます：各サーバーは通常、元の tablet サーバー上の非常に少数のデータのみをロードします。tablet の状態を復元するために、新しい tablet サーバーは元の tablet サーバーのコミットログファイルから対応する tablet の変更を再生する必要があります。しかし、この tablet の変更は他の tablet の変更と同じ物理ログファイルに混合されています。1 つの方法は、新しい tablet サーバーがコミットログファイル全体を読み取り、必要な tablet のエントリのみを再生することです。しかし、このモードでは、故障した tablet サーバー上の tablet が 100 台のマシンに割り当てられた場合、ログファイルが 100 回読み取られることになります（各 tablet サーバーが 1 回ずつ読み取ります）。
私たちは、最初にコミットログエントリを <table, row name, log sequence number> をキーとしてソートします。ソートされた出力では、特定の tablet の変更が連続しているため、1 回のディスク位置決定で効率的に順次読み取ることができます。並行してソートするために、ログファイルを 64MB のセグメントに分割し、異なる tablet サーバーで各セグメントを並行してソートします。このソートプロセスはマスターによって調整され、tablet サーバーがいくつかのコミットログファイルから変更を復元する必要があるときに開始されます。
GFS にコミットログを書き込むことは、さまざまな理由で短期間の性能問題を引き起こすことがあります。たとえば、GFS サーバーのマシンが書き込みクラッシュを引き起こしたり、3 つの GFS サーバーへのネットワークパスで混雑が発生したり、負荷が高すぎたりすることがあります。このような理由で、GFS の遅延ピーク時に変更を保護するために、各 tablet サーバーは実際には 2 つのスレッドを同時に使用します。アクティブなログファイルへの書き込み性能が低い場合、ログファイルの書き込みは他のスレッドに切り替えられ、コミットログキュー内の変更は新しいスレッドによって書き込まれます。ログエントリにはシーケンス番号が含まれており、復元プロセスはログスイッチスレッドによって生成された重複エントリを無視できます。
Tablet 復元の高速化#
マスターが tablet を 1 つの tablet サーバーから別の tablet サーバーに移動すると、元の tablet サーバーは対応する tablet に対して最初にマイナーコンパクションを実行します。このコンパクションは、tablet サーバーのコミットログ内の未圧縮状態の数を減らすことで、復元に必要な時間を短縮します。このコンパクションが完了すると、この tablet サーバーはこの tablet に対してサービスを停止し、実際に tablet をアンロードする前に、tablet サーバーはもう 1 回マイナーコンパクションを実行します（通常は非常に迅速に）し、最初のマイナーコンパクションの実行後に到達した他の未圧縮状態を排除します。2 回目のマイナーコンパクションが完了すると、この tablet は他の tablet サーバーにロードされ、ログエントリを復元する必要がなくなります。
不変性の活用#
SSTable キャッシュの他にも、Bigtable システムの多くの他の部分は、実際に生成される SSTables が不変であるために簡素化されています。たとえば、SSTables から読み取るとき、アクセスするファイルシステムで同期操作を行う必要はありません。最終的には、異なる行間の並行通知を非常に効率的に実装できます。唯一の可変で同時に読み書き可能なデータ構造は memtable であり、memtable の読み取り時の競合を減らすために、memtable の各行に対してコピーオンライトを行い、読み取りと書き込みを並行して実行できるようにします。
SSTables が不変であるため、削除されたデータを永久に削除する問題は、廃棄された SSTables のガベージコレクションに変換されます。各 tablet の SSTables は METADATA テーブル内に登録されています。マスターは、マーク・アンド・スイープを使用して SSTables 内の廃棄された SSTables を削除します。METADATA テーブルには、ルート tablet の集合が含まれています。最終的に、不変の SSTables により、私たちは tablets を迅速に分割できるようになり、子 tablets が親 tablet の SSTables を共有できるようにし、各子 tablet に新しい SSTables のセットを生成する必要がなくなります。
教訓#
Bigtable の設計、実装、保守、サポートの過程で、私たちは多くの経験を得て、多くの興味深い教訓を学びました。
私たちが学んだ教訓の 1 つは、大規模な分散システムは、標準的な多くの分散プロトコルで仮定されているネットワーク分割や故障停止エラーだけでなく、さまざまな故障の影響を受けやすいということです。たとえば、私たちはこれらの理由で引き起こされる多くの問題を発見しました：メモリやネットワークの故障、大きな時計のずれ、マシンのハング（応答なし）、持続的な非対称ネットワーク分割、他のシステム（たとえば Chubby）のバグ、GFS のクォータオーバーフロー、計画されたハードウェアメンテナンスや非計画のメンテナンスなど。これらの問題に関して多くの経験を得たため、さまざまなプロトコルを修正することで解決しました。たとえば、RPC メカニズムにチェックサムを追加しました。また、他の部分に対するシステム内の一部の仮定を削除することで、これらの問題に対処しました。たとえば、特定の Chubby が特定の範囲内のエラーのみを返すと仮定しなくなりました。
もう 1 つの教訓は、新しい機能がどのように使用されるかを理解する前に、新機能を追加するのを遅らせることが重要であるということです。たとえば、私たちは最初、API で一般的なトランザクションをサポートすることを計画していました。現在、使用シナリオがないため、実装していません。現在、Bigtable 上で多くの実際のアプリケーションが稼働しており、それらの実際のニーズを調査することができ、大多数のアプリケーションが単一行トランザクションのみを必要としていることがわかりました。ユーザーのニーズに対する分散トランザクションの最も重要な用途は、補助インデックスを維持することであり、それらのニーズを満たすための特別なメカニズムを追加する予定です。この新しいメカニズムは、分散トランザクションよりも一般的ではありませんが（less general）、より効率的で（特に数百行にわたる更新において）、私たちのデータセンター間のレプリカの楽観的な複製スキームとより良く相互作用します（interact better）。
Bigtable をサポートする過程で学んだ実用的な教訓の 1 つは、適切なシステムレベルの監視が非常に重要であるということです（たとえば、Bigtable 自体だけでなく、Bigtable を使用するクライアントも監視すること）。たとえば、私たちは RPC システムを拡張し、単純な RPC に対して、その RPC が行ったすべての重要な操作の詳細なトレースを記録するようにしました。この機能により、tablet データ構造のロック競合、Bigtable への変更の GFS への書き込みが遅すぎる、METADATA tablets が利用できないときに METADATA テーブルへのアクセスがブロックされるなど、多くの問題を発見し修正することができました。もう 1 つの有用な監視の例は、各 Bigtable クラスターが Chubby に登録されていることで、これによりすべてのクラスターを追跡し、そのサイズ、実行中のソフトウェアバージョン、受信したトラフィックの量、遅延が異常に高い問題があるかどうかを監視できます。
私たちが学んだ最も重要な教訓は、シンプルな設計の価値です。私たちのシステムのサイズ（テストコードを除いて約 100000 行）を考慮すると、コードは予期しない方法で発展し、コードと設計の明確さが保守とデバッグに大きな影響を与えることがわかりました。たとえば、私たちの tablet-server メンバーシッププロトコル。最初のプロトコルは非常にシンプルでした：マスターは定期的に tablet-server にリースを発行し、tablet servers はリースが期限切れになると自らを終了します。不幸なことに、ネットワークの問題が発生した場合、このプロトコルは可用性を大幅に低下させ、マスターの回復時間に非常に敏感でした。私たちは何度も再設計し、良好なパフォーマンスを示すプロトコルを得るまで続けました。しかし、その結果、このプロトコルは非常に複雑であり、Chubby のあまり他のアプリケーションで使用されない特性の動作に依存していました。
私たちは、いくつかのあいまいな境界条件を処理するのに多くの時間を費やしていることを発見しました。Bigtable のコードだけでなく、Chubby コードにも。最終的に、私たちはこのプロトコルを廃止し、一般的な Chubby 特性の動作にのみ依存する新しいシンプルなプロトコルに移行しました。
結論#
私たちは、Bigtable という Google が構造化データを保存するために使用する分散システムを説明しました。Bigtable は 2005 年 4 月から本番環境で使用されており、その前に私たちはそれを設計し、実装するのに約 7 人年を費やしました。2006 年 8 月には、60 以上のプロジェクトが Bigtable を使用しています。私たちのユーザーは、Bigtable が提供する高性能と高可用性を好んでおり、時間の経過とともにリソースの需要が増加するにつれて、クラスターの容量を簡単に拡張できます。
Bigtable の異常なインターフェースを考慮すると、ユーザーが Bigtable を使用することに適応するのがどれほど困難であるかという興味深い問題があります。新しいユーザーは、特にリレーショナルデータベースが提供する一般的なトランザクションの使用に慣れている場合、Bigtable のインターフェースを最も効果的に使用する方法を確信できないことがよくあります。それにもかかわらず、多くの Google 製品が Bigtable を成功裏に使用している事実は、私たちの設計が実際に機能していることを証明しています。
私たちは、補助インデックスのサポート、複数のマスターのレプリカを持つ Bigtable のインフラストラクチャの構築など、Bigtable の新機能を引き続き開発しています。また、Bigtable を製品グループに提供するサービスとして展開し、個々の製品が独自のクラスターを維持する必要がないようにし始めました。サービスクラスターの拡張に伴い、Bigtable 自体のリソース共有の問題を解決する必要があります。
最終的に、私たちは Google が独自に構築したストレージソリューションには大きな利点があることを発見しました。Bigtable のデータモデルを設計する際に、著しい柔軟性を得ることができました。さらに、Bigtable の実装とその依存する Google インフラストラクチャを自分たちで制御できるため、ボトルネックや非効率を迅速に排除できます。