概要#
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 ライクなシステムを研究した結果、私たちはこのデータモデルを選定しました。実際の設計決定に影響を与えた例として、異なるプロジェクトで使用できる大規模なウェブページの集合とその関連情報のコピーを維持したいと仮定します。このテーブルを Webtable と呼び、Webtable では URL を行キーとして使用し、ウェブページの各属性（ウェブページの内容、アンカーポイントなど）を列キーとして使用し、対応する（異なる時間に取得された）内容を値として保存します。以下の図のように：
行#
テーブル内の行キーは任意の文字列であることができます（現在の最大 64KB）。同じ行キーの下で行われるすべての読み書きデータは原子性を持ち、この設計により、クライアントは同じ行を同時に更新する際のシステムの動作を推測しやすくなります。Bigtable は行キーの辞書順にデータを維持します。テーブル内の行の範囲は動的にパーティションされており、各行範囲は tablet と呼ばれ、分散と負荷分散の基本単位でもあります。このため、小さな行範囲を読み取ることは非常に効率的であり、通常は非常に少数のマシンと通信するだけで済みます。クライアントは行キーを選択する際にこの特性を利用し、データにアクセスする際により良い局所性を得ることができます。たとえば、Webtable では、URL のホスト名部分を反転させることで、同じドメインのウェブページをグループ化します。たとえば、maps.google.com/index.html のデータをキー com.google.maps/index.html の下に保存し、同じドメインのページを互いに近い位置に保存することで、いくつかのホストとドメインの分析をより効率的に行えるようにします。
列ファミリー#
列キーは、列ファミリーと呼ばれる集合にグループ化され、アクセス制御の基本単位を形成します。1 つの列ファミリー内に保存されるすべてのデータタイプは一般的に同じです（同じ列ファミリーのデータを一緒に圧縮します）。列ファミリーは、データが列ファミリー内の任意の列キーに保存される前に作成する必要があります。列ファミリーが作成された後は、列ファミリー内のすべての列キーを使用できます。
私たちの目的は、1 つのテーブル内の異なる列ファミリーの数を少なく（最大数百個）し、操作中に列ファミリーがほとんど変更されないことです。対照的に、1 つのテーブルには無限の数の列が存在する可能性があります。列キーは次の構文で名前を付けることができます：ファミリー：識別子。列ファミリーの名前は印刷可能でなければなりませんが、識別子は任意の文字列であることができます。たとえば、Webtable の 1 つの列ファミリーは言語であり、ウェブページの内容を作成するために使用される言語を保存します。言語列ファミリーでは、各ウェブページの言語 ID を保存するために 1 つの列キーのみを使用します。このテーブルのもう 1 つの有用な列ファミリーはアンカー（anchor）であり、このファミリー内の各列キーは個別のアンカーを表します（上記の図のように）、その識別子は参照される URL であり、内容はリンクテキストです。
アクセス制御、ディスクおよびメモリの計測は、列ファミリーのレベルで行われます。Webtable の例では、この制御により、さまざまなアプリケーションを管理できます：いくつかは新しい基礎データを追加し、いくつかは基本データを読み取り、派生した列ファミリーを作成し、いくつかは現在存在するデータを表示することのみを許可されている（プライバシーの理由からすべての列ファミリーを表示できない）ものです。
タイムスタンプ#
Bigtable 内の各セルは、同じデータの複数のバージョンを含むことができ、これらのバージョンはタイムスタンプによってインデックスされます。Bigtable のタイムスタンプは 64 ビット整数です。タイムスタンプは、Bigtable によってマイクロ秒で表される実際の時間に設定されるか、クライアントアプリケーションによって明示的に設定されることがあります。アプリケーションは、衝突を避けるために一意のタイムスタンプを生成する必要があります。セルの異なるバージョンは、減少順に保存され、最新のデータが最初に読み取られます。
異なるバージョンのデータを管理する負担を軽減するために、2 つの列ファミリーのレベル設定をサポートし、Bigtable が自動的にガベージコレクションを行います：クライアントは、最近の n 個のバージョンのみを保存するか、十分に新しいバージョンのみを保存するように指定できます（たとえば、最新の 7 日間に書き込まれたデータ）。
Webtable の例では、取得したウェブページのタイムスタンプを、これらのページが実際に取得された時刻に設定し、上記で説明したガベージコレクションメカニズムにより、各ページの最近の 3 つのバージョンのみを保存します。
API#
Bigtable API は、テーブルや列ファミリーの作成と削除の機能を提供し、クラスター、テーブル、および列ファミリーのメタデータを変更する機能も提供します。たとえば、アクセス制御権限を変更することができます。
クライアントアプリケーションは、Bigtable の値を読み書きし、個別の行を介して値を検索するか、テーブル内のデータのサブセットをスキャンします。以下は、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++ コードです。クライアントは複数の列ファミリーをスキャンし、スキャンによって生成される行、列、およびタイムスタンプの数を制限するための多くのメカニズムがあります。たとえば、スキャンを制限して、アンカー:*.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 が開かれると、このブロックがメモリにロードされます。クエリ操作は、単一のディスク検索によって完了する場合があります：まず、メモリインデックス内で二分探索を実行して正しいブロックを見つけ、その後、ディスクから対応するブロックを読み取ります。さらに、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 に保存されたデータの一部が利用できなくなる平均的なサービス時間の割合は 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 の位置情報を取得するためにマスターに依存しないため、ほとんどのクライアントはマスターと通信しません。最終的に、実際にはマスターの負荷は非常に低いです。
Bigtable は多くのテーブルを保存し、各テーブルは一連の tablets で構成され、各 tablet は行範囲内のすべての関連データを含みます。最初は各テーブルに 1 つの tablet しかありませんが、テーブルデータが増加すると、自動的に複数の tablets に分割されます。デフォルトでは、各 tablet のサイズは 100-200MB の間です。
Tablet の位置情報#
私たちは、tablet の位置情報を保存するために B + ツリーに似た 3 層の階層構造を使用しています。
第 1 層は、Chubby 上に保存されるファイルで、root tablet の情報を含みます。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-200MB で 128MB を取ると、合計サイズは 2^61 バイトになります）
クライアントライブラリは tablet の位置情報をキャッシュします。クライアントが tablet の位置を知らない場合、またはキャッシュされた位置情報が正しくない場合、ターゲット tablet の位置情報を再帰的に上に向かって検索します。クライアントのキャッシュが空である場合、アドレッシングアルゴリズムは 3 回のネットワーク往復を必要とし、その中には 1 回の Chubby 読み取りが含まれます。クライアントのキャッシュが古い場合、アドレッシングアルゴリズムは最大 6 回の往復を要する可能性があります（METADATA tablet が頻繁に移動しないと仮定して）、キャッシュが古くなったことを発見するのは、ヒットしない場合のみです（訳注：最初にキャッシュを使用し、上に向かって 3 回ヒットしない場合、次に上から下に再度 3 回クエリを行います）。
tablet の位置情報がメモリ内に保存されているため、GFS にアクセスする必要はありません。クライアントライブラリを通じて tablet の位置情報を事前取得することで、オーバーヘッドをさらに削減しました：クライアントは METADATA テーブルを読み取るたびに複数の tablet を読み取ります。
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 集合の 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 ファイルから読み取ることで実行されます（ほとんどの場合、キャッシュにヒットします）。有効な変更はコミットログに書き込まれ、小さな変更のスループットを向上させるためにグループコミットが使用されます。書き込みがコミットされると、そのメモリは memtable に挿入されます。tablet サーバーが読み取り操作を受け取ると、同様に形式と権限が適切であるかどうかを確認します。合法的な読み取り操作は、memtable と一連の SSTables のマージビューで実行されます。SSTables と memtable は辞書順にソートされたデータ構造であるため、マージビューは効率的に構築できます。
tablets が分割または統合されるとき、読み書き操作は継続できます。
コンパクション#
書き込み操作が実行された後、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 は削除されたデータが使用していたリソースを回収し、削除されたデータがシステムから迅速に消えることを保証します。これは、ストレージに敏感なデータを扱うサービスにとって重要です。
改良#
上記で説明した実装は、ユーザーが要求する高性能、高可用性、信頼性を達成するために最適化が必要です。このセクションでは、これらの改善を強調するために、一部の実装について詳細に説明します。
ローカリティグループ#
クライアントは、複数の列ファミリーを 1 つのローカリティグループに組み合わせることができます。各 tablet は、各ローカリティグループに対して個別の SSTable を作成します。通常一緒にアクセスされない列ファミリーを異なるローカリティグループに分けることで、読み取り効率を向上させることができます。たとえば、Webtable のページメタデータを 1 つのローカリティグループに配置し、ページコンテンツを別のローカリティグループに配置することで、ページメタデータを読み取る必要があるアプリケーションは、ページの内容を読み取る必要がなくなります。
さらに、各ローカリティグループに基づいていくつかの有用な微調整パラメータを指定できます。たとえば、ローカリティグループをメモリ内に保存するように宣言できます。メモリ内の SSTables に保存されたローカリティグループは、tablet サーバーによって遅延的にメモリにロードされます。一度ロードされると、このローカリティグループに属する列ファミリーを読み取る際にディスクにアクセスする必要がなくなります。この機能は、小さなブロックですが頻繁にアクセスされるデータに非常に役立ちます：内部的には、METADATA テーブル内でこの機能を使用して列ファミリーを特定しています。
圧縮#
クライアントは、ローカリティグループの SSTables を圧縮するかどうかを制御できます。圧縮する場合は、指定された圧縮形式を使用します。ユーザーが指定した圧縮形式は、各 SSTable ブロックに使用されます（サイズはローカリティグループの微調整パラメータで指定できます）。各ブロックを個別に圧縮すると、いくつかのスペースが失われる可能性がありますが、利点は、SSTable の一部を読み取る際にファイル全体を解凍する必要がなくなることです。多くのクライアントは、2 段階のカスタム圧縮形式を使用しています。最初のステップでは、Bentley and McIlroy のスキームを使用して、大きなウィンドウ内で長い共通の文字列を圧縮し、2 番目のステップでは、16KB のサイズのウィンドウで重複パターンを検索する高速圧縮アルゴリズムを使用します。両方の圧縮プロセスは非常に高速で、現代のマシンではエンコード速度が 100–200MB/s、デコード速度が 400–1000MB/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 の変更が連続しているため、単一のディスク位置決めで効率的に順次読み取ることができます。並行してソートするために、ログファイルを 64MB のセグメントに分割し、異なる tablet サーバーで各セグメントを並行してソートします。このソートプロセスはマスターによって調整され、tablet サーバーがいくつかのコミットログファイルから変更を復元する必要があるときに開始されます。
コミットログを GFS に書き込むことは、さまざまな理由で短期間の性能問題を引き起こすことがあります。たとえば、GFS サーバーマシンが書き込みクラッシュを引き起こしたり、3 つの GFS サーバーへのネットワーク経路で混雑が発生したり、負荷が高すぎたりすることがあります。GFS の遅延ピーク時に変更を保護するために、各 tablet サーバーは実際に 2 つのスレッドを同時に使用します。アクティブログファイルへの書き込み性能が低い場合、ログファイルへの書き込みは他のスレッドに切り替わり、コミットログキュー内の変更が新しいスレッドを介して書き込まれます。ログエントリにはシーケンス番号が含まれており、復元プロセスはログスレッドの切り替えによって生成された重複エントリを無視できます。
tablet の復元を加速する#
マスターが tablet を 1 つの tablet サーバーから別の tablet サーバーに移動すると、元の tablet サーバーは、対応する tablet の未圧縮状態の数を減らすために、まずその tablet でマイナーコンパクションを実行します。この圧縮が完了すると、tablet サーバーはその tablet にサービスを提供するのを停止し、実際に tablet をアンロードする前に tablet サーバーは再度マイナーコンパクションを実行します（通常は非常に迅速に）し、最初のマイナーコンパクションの後に到達した残りの未圧縮状態を排除します。2 回目のマイナーコンパクションが完了すると、この tablet は他の tablet サーバーにロードされることができ、ログエントリを復元する必要がなくなります。
不変性の活用#
SSTable キャッシュに加えて、Bigtable システムの多くの他の部分も、実際に生成される SSTables が不変であるために簡素化されています。たとえば、SSTables から読み取るとき、アクセスするファイルシステムでの同期操作を行う必要はありません。最終的に、異なる行間の並行通知を非常に効率的に実現できます。唯一の可変で同時に読み書き可能なデータ構造は memtable です。memtable の読み取り時の競合を減らすために、memtable の各行に対してコピーオンライトを行い、読み取りと書き込みを並行して実行できるようにします。
SSTables が不変であるため、削除されたデータを永久に削除する問題は、廃棄された SSTables のガベージコレクションに変換されます。各 tablet の SSTables は METADATA テーブルに登録されています。マスターは、マーク - クリアを使用して SSTables 内の廃棄された SSTables を削除します。METADATA テーブルには、root tablet の集合が含まれています。最終的に、不変の SSTables により、tablets を迅速に分割できるようになり、子 tablet が親 tablet の SSTables を共有できるようにし、各子 tablet に新しい SSTables のセットを生成する必要がなくなります。
教訓#
Bigtable の設計、実装、保守、サポートの過程で、私たちは多くの経験を得て、多くの興味深い教訓を学びました。
私たちが学んだ教訓の 1 つは、大規模な分散システムが、標準的な多くの分散プロトコルで仮定されるネットワーク分割や停止エラーだけでなく、さまざまな障害の影響を受けやすいということです。たとえば、私たちはこれらの理由によって引き起こされた多くの問題を発見しました：メモリやネットワークの障害、大きな時計の偏差、マシンのハング（応答なし）、持続的な非対称ネットワーク分割、他のシステム（たとえば Chubby）のバグ、GFS のクォータオーバーフロー、計画されたおよび非計画のハードウェアメンテナンスなどです。これらの問題に対処するために、さまざまなプロトコルを修正することで、私たちは多くの問題を解決しました。たとえば、RPC メカニズムにチェックサムを追加しました。また、システム内の一部の部分が他の部分に対して仮定を行うことを削除することで、これらの問題に対処しました。たとえば、特定の Chubby が特定の範囲内のエラーのみを返すと仮定しなくなりました。
もう 1 つの教訓は、新しい機能がどのように使用されるかを理解する前に、新しい機能を追加することを遅らせることが重要であるということです。たとえば、私たちは最初に API で一般的なトランザクションをサポートすることを計画していました。現在、使用シナリオがないため、実装しませんでした。現在、Bigtable で実行されている多くの実際のアプリケーションがあり、それらの実際のニーズを調査することができ、大多数のアプリケーションが単一行トランザクションのみを必要とすることがわかりました。ユーザーのニーズに対する分散トランザクションの最も重要な用途は、補助インデックスを維持することです。私たちはそれらのニーズを満たすために特別なメカニズムを追加することを計画しています。この新しいメカニズムは、分散トランザクションよりも一般的ではありませんが（less general）、より効率的であり（特に数百行の更新に跨る場合）、私たちのデータセンター間のレプリカ楽観的コピーのスキームとより良く相互作用します。
Bigtable をサポートする過程で学んだ実用的な教訓の 1 つは、適切なシステムレベルの監視が非常に重要であるということです（たとえば、Bigtable 自体だけでなく、Bigtable を使用するクライアントも監視すること）。たとえば、私たちは RPC システムを拡張し、単純な RPC に対して、その RPC が行ったすべての重要な操作の詳細なトレースを記録します。この機能により、tablet データ構造のロック競合、Bigtable への変更の書き込みが GFS に対して非常に遅いこと、METADATA tablets が利用できないときに METADATA テーブルにアクセスすることがブロックアクセスを引き起こすことなど、多くの問題を発見し修正することができました。もう 1 つの監視の有用な例は、各 Bigtable クラスターが Chubby に登録されていることで、これによりすべてのクラスターを追跡し、そのサイズ、実行中のソフトウェアバージョン、受信したトラフィックの量、遅延異常の問題があるかどうかを監視できます。
私たちが学んだ最も重要な教訓は、シンプルな設計の価値です。私たちのシステムのサイズ（テストコードを除いて約 100,000 行）を考慮すると、コードは予期しない方法で発展し、コードと設計の明確さが保守とデバッグに大きな影響を与えることがわかりました。たとえば、私たちの tablet-server メンバーシッププロトコル。最初のプロトコルは非常にシンプルでした：マスターは定期的に tablet-server にリースを発行し、tablet サーバーはリースが期限切れになると自分自身を殺します。不幸なことに、ネットワークの問題が発生した場合、このプロトコルは可用性を大幅に低下させ、マスターの回復時間に非常に敏感でした。私たちは、良好なパフォーマンスを示すプロトコルが得られるまで、何度も再設計しました。しかし、その結果、このプロトコルは非常に複雑であり、Chubby の他のアプリケーションではほとんど使用されない特性の動作に依存していました。
私たちは、いくつかのあいまいな境界条件を処理するのに多くの時間を費やしていることに気付きました。Bigtable のコードだけでなく、Chubby コードにも関係しています。最終的に、私たちはこのプロトコルを廃止し、一般的な Chubby の特性にのみ依存する新しいシンプルなプロトコルに移行しました。
結論#
私たちは、Google が構造化データを保存するために使用する分散システムである Bigtable を説明しました。Bigtable は 2005 年 4 月から生産環境で使用されており、その前に設計と実装に約 7 人年を費やしました。2006 年 8 月には、60 以上のプロジェクトが Bigtable を使用しています。私たちのユーザーは、Bigtable が提供する高性能と高可用性を好み、時間の経過とともにリソースの需要が増加するにつれて、クラスターの容量を単純に追加することで拡張できます。
Bigtable の異常なインターフェースを考慮すると、私たちのユーザーが Bigtable を使用することに適応するのがどれほど難しいかという興味深い問題があります。新しいユーザーは、特に関係データベースが提供する一般的なトランザクションの使用に慣れている場合、Bigtable のインターフェースを最も効果的に使用する方法について不確かです。それにもかかわらず、多くの Google 製品が Bigtable を成功裏に使用している事実は、私たちの設計が実際にうまく機能していることを証明しています。
私たちは、補助インデックスのサポートや、複数のマスターのレプリカを持つ Bigtable のインフラストラクチャの構築など、Bigtable の新機能を開発し続けています。また、Bigtable を製品グループに提供するサービスとして展開し、各製品が独自のクラスターを維持する必要がないようにし始めました。サービスクラスターが拡大するにつれて、Bigtable 自体のリソース共有の問題を解決する必要があります。
最終的に、私たちは Google が独自に構築したストレージソリューションには大きな利点があることを発見しました。Bigtable のデータモデルを設計する際に、顕著な柔軟性を得ました。さらに、Bigtable の実装とその依存する Google インフラストラクチャを自分たちで制御できるため、ボトルネックや非効率を迅速に解消できます。