JP5607059B2 - パーティション化した拡張可能で可用性の高い構造化ストレージにおけるパーティション管理 - Google Patents

Description

サーバファーム、ウェブサービスなどを含む分散システムは、大量のコンピューティングリソース及びストレージリソースを提供するためにますます普及してきた。例えば、分散ストレージシステムは、様々なアプリケーションについての大量のデータを格納し、取り出すために利用されてきた。場合によっては、ストレージシステムは、データをより効率的に格納し、取り出し、クエリを行うために構造化ストレージを利用する。構造化ストレージシステムは、ネットワークを通じて複数のノードにわたってデータを格納することができる。かかるストレージを提供するために所望されるコンピューティングリソースの量が増加するにつれて、かかるストレージシステムは、追加のコンピュータデバイスを追加することにより追加のリソースを必要に応じて追加することができる柔軟なトポロジを与えることで、「拡大する」ことができる。従って、構造化ストレージシステムは、格納されるデータを例えばペタバイトからエクサバイトまで拡張可能であるかもしれない。結果として、データが常にアクセス可能であってデータ損失を防ぐのに耐久性があるように、かかる構造化ストレージシステム内のデータを管理するのは複雑なことが多い。

この概要は、詳細な説明において更に後述される単純化された形式の概念の抜粋を紹介するために提供される。この概要は、請求された内容の重要な特徴または基本的特徴を特定することを意図していないし、請求された内容の範囲を決定する際の助けとして用いられることも意図していない。

本発明の実施形態は、構造化データストレージシステムにおけるパーティション管理に関する。ストアにおいて、構造化データは、いくつかのパーティションに分割され、異なるサーバがサービスを提供することができる。パーティションマップは、これらのパーティションの位置を追跡するために用いられる。より具体的には、パーティションマップを用いて、クライアントは、どのサーバが特定のデータを扱っているかを知ることができる。詳細な負荷情報が、パーティションについて追跡される。パーティションは、サーバにわたる負荷分散を実現するためにサーバの間で移動することができる。いくつかの実施形態において、より良い負荷分散を実現するために、高負荷を有するパーティションが、分割のために特定される。パーティションを分割する位置が決定されて、パーティションは子パーティションを作成するために分割される。子パーティションは、いくつかの実施形態において別のサーバにアンロードすることができる。パーティションマップは、パーティションが子パーティションに分割されたことを示すために更新される。いくつかの実施形態において、２つ以上のパーティションが、マージするために特定される。パーティションはマージされて、パーティションマップはマージされたパーティションを示すために更新される。

構造化ストレージはストリームシステムの上部に構築される。ストリームシステムは、アペンド専用のファイルシステムのインタフェースを示す。ストリームは、アペンド専用ファイルに類似している。各パーティションは、パーティションに付随するストリームのセットを有する。パーティションの全ての持続的状態は、パーティションが付随するストリームのセットにおいて保たれる。ストリームのセットの中に、パーティションについてのメタデータストリームが存在する。メタデータストリームは、パーティションの全ての他のストリームに対するポインタを、パーティションに含まれる全ての行についてのパーティションのキーの範囲などのそのパーティションの基本的情報と同様に含む。

本発明は、添付の図面を参照して以下に詳述される。
本発明の実施形態を実施する際に使用するのに適した例示的なコンピュータ環境のブロック図である。 本発明の実施形態に基づくテーブル構造を表す図である。 本発明の実施形態を実施することができる例示的なシステムを示すブロック図である。 本発明の実施形態に基づくパーティションを示すブロック図である。 本発明の実施形態に基づくパーティションを分割する方法を示すフロー図である。 本発明の実施形態に基づく２つの子パーティションに分割されている親パーティションの例を表す図である。 本発明の別の実施形態に基づくパーティションを分割する方法を示すフロー図である。 本発明の実施形態に基づくマージされたパーティションにパーティションをマージする方法を示すフロー図である。 本発明の実施形態に基づくこわれたパーティションを修復する方法を示すフロー図である。 本発明の実施形態に基づくパーティションのバージョン管理及び更新の方法を示すフロー図である。

本発明の内容は、法定の要件を満たすために本明細書において具体性を持って説明されている。しかしながら、この説明自体は、本特許の範囲を限定することを意図していない。むしろ、本発明者は、請求された発明がまた、他の現在の技術または将来の技術と関連して、本明細書において説明されているステップと異なるステップまたは同様のステップの組合せを含むような他の方法で具現化されてもよいと考える。更に、用語「ステップ」及び／または「ブロック」は、用いられる方法の異なる要素を暗示するために本明細書において用いることができるが、当該用語は、本明細書において開示される様々なステップの中でまたは様々なステップ同士の間のいかなる特定の順序も意味すると解釈すべきでない。但し、個々のステップの順序が明示的に説明されている場合は除く。

本発明の実施形態は、拡張可能で可用性が高くかつ耐久性のある構造化ストレージを提供する。構造化ストレージは多数のテーブルで表され、テーブルの各々は複数の行を含み、各行はデータエンティティを表す。テーブルは複数のパーティションに分割され、各パーティションはテーブルからの所定範囲の行を含む。パーティションは、テーブルサーバに格納されて、テーブルマスタを用いて管理される。

いくつかの実施形態において、パーティションは、負荷分散目的のために分割される。負荷分散情報は、テーブルサーバ及びパーティションについて追跡される。負荷分散情報に基づいて、テーブルマスタは、パーティションの負荷分散することを決定して、負荷を分散するために異なるノードにパーティションを再割り当てすることができる。さらに、いくつかのパーティションについて、テーブルマスタは、現在の負荷を分散するためにパーティションを分割することを決定することができる。テーブルマスタは、分割比を決定して、分割の位置決めをするためのキー情報について、パーティションにサービスを提供しているテーブルサーバにクエリを行う。テーブルサーバから受信されるキー情報に基づいて、テーブルマスタは、テーブルサーバにパーティションを分割するよう命令する。分割要求を受信すると、テーブルサーバは、対象パーティションをアンロードして、子パーティションを作成し、子パーティションへのサービスの提供を開始する。いくつかの実施形態において、子パーティションは、別のテーブルサーバに割り当てることができる。パーティションマップは、子パーティションにサービスを提供しているテーブルサーバ（または複数のテーブルサーバ）を示すために更新される。

いくつかの実施形態において、パーティションはマージされる。この場合もやはり、負荷分散情報は、テーブルサーバ及びパーティションについて追跡される。負荷分散情報に基づいて、２又はそれ以上のパーティションがマージするために特定される。パーティションにサービスを提供しているテーブルサーバ（または複数のテーブルサーバ）は、パーティションにサービスを提供するのを止めるように命令される。パーティションは、マージされてテーブルサーバにロードされるが、テーブルサーバは、マージされたパーティションへのサービス提供を開始する。パーティションマップは、マージされたパーティションにサービスを提供しているテーブルサーバを示すために更新される。

従って、１つの態様において、本発明の実施形態は、構造化ストレージシステム内の１つまたは複数のコンピュータデバイスによって実施される方法を対象とする。構造化ストレージシステム内の構造化ストレージは１つまたは複数のテーブルで表され、各テーブルは複数の行を含み、各行は構造化ストレージシステムによって格納されるデータエンティティを表しており、行を特定するための１つまたは複数のキーを含んでおり、複数の行は複数のパーティションの間で分割され、各パーティションはテーブル内の複数の行からのある範囲の行を含んでおり、複数のパーティションは複数のテーブルサーバに格納され、テーブルマスタは複数のテーブルサーバへのパーティションの割り当てを制御する。本方法はパーティションを子パーティションに分割するためのものであって、パーティションについての負荷情報に基づいて分割するためのパーティションを特定することを含み、負荷情報はパーティションの２又はそれ以上の部分の各々の負荷を特定する情報を含む。本方法はまた、テーブルマスタによって、パーティションの２つ以上の部分の各々の負荷に基づいてパーティションを分割するための分割比が決定されることを含む。本方法は、分割比に対応するパーティション内の実際の位置を示すキー情報についてテーブルサーバにクエリを行うことをさらに含む。本方法はまた、テーブルサーバからテーブルマスタにおけるキー情報を受信することを含み、キー情報は、分割比に対応するパーティション内の実際の位置を示す。本方法は、テーブルマスタからテーブルサーバに分割要求を送信することをさらに含み、分割要求は、キー情報に基づいてパーティションを分割することを示す。本方法はまた、キー情報に対応する位置でパーティションを分割して子パーティションを作成することを含む。本方法は、テーブルマスタに分割の完了を通知することをさらに含む。本方法は、子パーティションに分割されているパーティションに基づいてパーティションマップを更新することをさらに含み、パーティションマップは、複数のパーティションと複数のパーティションにサービスを提供する複数テーブルサーバとの間のマッピングを格納する。

本発明の別の実施形態において、態様は、１つまたは複数のテーブルで表される構造化ストレージシステムを管理する方法を実行するためのコンピュータ使用可能命令を格納する１つまたは複数のコンピュータ記憶媒体を対象とする。各テーブルは複数の行を含み、各行は構造化ストレージシステムによって格納されるデータエンティティを表しており、行を特定するための１つまたは複数のキーを含んでおり、複数の行は複数のパーティションの間で分割され、各パーティションはテーブル内の複数の行からの所定範囲の行を含み、複数のパーティションは複数のテーブルサーバに格納され、テーブルマスタは複数のテーブルサーバへのパーティションの割り当てを制御する。本方法は、テーブルのうちの少なくとも２つのパーティションを、マージされたパーティションにマージするためのものであって、複数のテーブルサーバの複数のパーティションについての負荷情報を追跡することを含む。本方法はまた、テーブルマスタによって、負荷情報に基づいてマージするための少なくとも２つのパーティションを特定することを含む。本方法は、テーブルマスタによって、マージされたパーティションについてのメタデータストリームを作成することをさらに含む。本方法はまた、少なくとも２つのパーティションにサービスを提供している少なくとも１つのテーブルサーバから少なくとも２つのパーティションをアンロードすることを含む。本方法は、テーブルマスタによって、複数のテーブルサーバから選択されたテーブルサーバにマージされたパーティションを割り当てることをさらに含む。本方法は、選択されたテーブルサーバにおいてマージされたパーティションをロードしてサービスを提供することをさらに含む。

本発明のさらなる実施形態は、１つまたは複数のテーブルで表される構造化ストレージシステムを管理する方法を実行するためのコンピュータ使用可能命令を格納する１つまたは複数のコンピュータ記憶媒体を対象とする。各テーブルは複数の行を含み、各行は構造化ストレージシステムによって格納されるデータエンティティを表しておりかつ行を特定するための１つまたは複数のキーを含み、複数の行は複数のパーティションの間で分割され、各パーティションはテーブル内の複数の行からの所定範囲の行を含み、複数のパーティションは複数のテーブルサーバに格納され、テーブルマスタは複数のテーブルサーバへのパーティション割り当てを制御することを特徴とする。本方法は、少なくとも２つの子パーティションにテーブルのパーティションを分割するためのものであって、複数のテーブルサーバの複数のパーティションについての負荷情報を追跡することを含む。本方法はまた、テーブルマスタによって、負荷情報に基づいて分割するためのパーティションを特定することを含み、パーティションについての負荷情報はパーティションの異なる部分の異なる負荷を特定することを特徴とする。本方法は、テーブルマスタにおいて、パーティションを分割するための分割比を決定することをさらに含み、分割比はロード情報に基づいて特定されかつパーティション内のポイントを表しており、パーティションにおいてパーティションの第１の部分が第１の負荷の量を含みかつパーティションの第２の部分が第２の負荷の量を含むことを特徴とする。本方法はまた、テーブルマスタからテーブルサーバに要求を送信することをさらに含み、キー情報のための要求は、分割比に対応するパーティション内の実際の位置を特定する。本方法はまた、テーブルサーバによって、分割比に対応するパーティション内の実際の位置を特定するキー情報を決定することと、テーブルサーバからテーブルマスタへキー情報を伝えることとを含む。本方法は、テーブルマスタにおいて、子パーティションの各々についてのメタデータストリームを構築することをさらに含む。本方法はまた、テーブルマスタからテーブルサーバに分割要求を送信することと、テーブルサーバにおいてパーティションから子パーティションを作ることとをさらに含む。本方法はまた、テーブルサーバにおいてパーティションにサービスを提供するのを止めることと、テーブルサーバにおいて子パーティションをロードしてサービスを提供することとを含む。本方法は、テーブルサーバからテーブルマスタに分割の完了通知を送信することをさらに含む。本方法はまた、子パーティションに分割されているパーティションに基づいてパーティションマップを更新することをさらに含み、パーティションマップは、複数のパーティションと複数のパーティションにサービスを提供している複数のテーブルサーバとの間のマッピングを格納する。

本発明の実施形態の概要を簡単に説明したが、本発明の実施形態を実施することができる例示的な動作環境は、本発明の様々な態様についての一般的な内容を提供するために以下に説明されている。最初に特に図１を参照すると、本発明の実施形態を実施するための例示的な動作環境が示されていて、コンピュータデバイス１００と概して表されている。コンピュータデバイス１００は、適切なコンピュータ環境のうちのほんの１つの例であって、本発明の使用の範囲または機能の範囲に関していかなる限定も示唆することを意図していない。コンピュータデバイス１００は、示されるコンポーネントのうちのいずれか１つまたは組合せに関していかなる従属性も要件も有すると解釈されてはならない。

本発明は、コンピュータもしくはパーソナルデータアシスタントまたは他の携帯端末などの他のマシンによって実行される、プログラムモジュールなどのコンピュータ実行可能命令を含む、コンピュータコードまたはマシン使用可能命令についての一般的な文脈で説明することができる。通常、ルーチン、プログラム、オブジェクト、コンポーネント、データ構造等を含むプログラムモジュールは、特定のタスクを実行するかまたは特定の抽象データ型を実施するコードを言う。本発明は、携帯端末、家庭用電化製品、汎用コンピュータ、より専門的なコンピュータデバイス等を含む様々なシステム構成において実施することができる。本発明はまた、通信ネットワークを介して接続されたリモート処理デバイスがタスクを実行する分散コンピュータ環境において実施することができる。

図１を参照すると、コンピュータデバイス１００は、以下のデバイスを直接または間接的に接続するバス１１０を含む。以下のデバイスは、メモリ１１２、１つまたは複数のプロセッサ１１４、１つまたは複数のプレゼンテーションコンポーネント１１６、入力／出力ポート１１８、入力／出力コンポーネント１２０及び例示的な電力供給装置１２２である。バス１１０は、（アドレスバス、データバスまたはこれらの組合せなどの）１つまたは複数のバスであってもよいものを表す。図１の様々なブロックは明確にするために線で示されているが、実際には、様々なコンポーネントを図で表現することはそれほど明らかでなく、比喩的には、これらの線はより正確にははっきりとせずあいまいである。例えば、ディスプレイデバイスなどのプレゼンテーションコンポーネントは、Ｉ／Ｏコンポーネントであると考えられるかもしれない。また、プロセッサはメモリを有している。技術の性質はこのようなものであると認められ、図１の図は単に本発明の１つまたは複数の実施形態と関連して用いることができる例示的なコンピュータデバイスを示すだけであるとあらためて表明される。全てが図１の範囲内と考えられて「コンピュータデバイス」と称されるので、「ワークステーション」、「サーバ」、「ラップトップ」、「携帯端末」等のようなかかるカテゴリの間で区別はされない。

コンピュータデバイス１００は通常、様々なコンピュータ可読媒体を含む。コンピュータ可読媒体は、コンピュータデバイス１００がアクセスすることができかつ揮発性及び不揮発性の媒体、着脱自在及び固定式の媒体を含むいずれかの利用可能な媒体とすることができる。一例であってこの例に限定されないが、コンピュータ可読媒体は、コンピュータ記憶媒体及び通信媒体を含むことができる。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータなどの情報を記憶するためのいずれかの方法または技術で実施される揮発性及び不揮発性、着脱自在及び固定式の媒体を含む。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ディスク記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置もしくは他の磁気記憶デバイス、または所望の情報を格納するために用いることができかつコンピュータデバイス１００がアクセスすることができるあらゆる他の媒体を含むが、これらに限定されるものではない。通信媒体は通常、コンピュータ可読命令、データ構造、プログラムモジュールまたは他のデータを搬送波もしくは他のトランスポートメカニズムなどの変調されたデータ信号に具現化し、任意の情報送達媒体を含む。用語「変調されたデータ信号」は、信号の特徴のうちの１つまたは複数をその信号内に情報をコード化するような方式に設定又は変更した信号を意味する。例であって限定ではないが、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体並びに音響、ＲＦ、赤外線及び他の無線媒体などの無線媒体を含む。上記のうちのいずれかの組合せも、コンピュータ可読媒体の範囲内に含まれるべきである。

メモリ１１２は、揮発性及び／または不揮発性のメモリの形のコンピュータ記憶媒体を含む。メモリは、着脱自在、固定式、またはこれらの組合せであってもよい。例示的なハードウェアデバイスは、ソリッドステートメモリ、ハードドライブ、光ディスクドライブ等を含む。コンピュータデバイス１００は、メモリ１１２またはＩ／Ｏコンポーネント１２０などの様々なエンティティからデータを読み出す１つまたは複数のプロセッサを含む。プレゼンテーションコンポーネント（または複数のプレゼンテーションコンポーネント）１１６は、ユーザまたは他のデバイスにデータ指示を示す。例示的なプレゼンテーションコンポーネントは、ディスプレイデバイス、スピーカ、印刷コンポーネント、振動コンポーネント等を含む。

Ｉ／Ｏポート１１８は、コンピュータデバイス１００がＩ／Ｏコンポーネント１２０を含む他のデバイスに論理的に接続できるようにする。他のデバイスのうちのいくつかは、内蔵されていてもよい。例示的なコンポーネントは、マイクロホン、ジョイスティック、ゲームパッド、衛星放送受信アンテナ、スキャナ、プリンタ、無線デバイス、ネットワークデバイス等を含む。

高レベルのデータモデル
本発明の実施形態に基づき、構造化ストレージはテーブルで表され、そこでテーブルは行のセットを含む。例として、図２は、本発明の実施形態に基づくテーブル２００の一部を示す。行２０２などのテーブル２００の各行は、データエンティティを表し、プロパティのセットを含む。プロパティのセットは、一連の列おいて特定され、プロパティ２０４、２０６及び２０８を含む（列２０８のデータ値は、簡略化するためにかつ明確化するために空のままである）。プロパティ／列は、例えば、名前、型を持つ値対または複数の型を持つ値のマッピングに対する名前であってもよい。行及び／または各個々のプロパティは、バージョン管理されていてもよいしバージョン管理されていなくてもよい。テーブル自体は、テーブル内のどの行も同じ型を備えた同じプロパティを有する固定スキーマを有することができるかまたは、どの行も格納されたプロパティ及び型の異なるセットを有することができる強制されたスキーマを有しないことができる。

構造化ストアで行なわれるオペレーションの標準セットは、テーブル、行及びプロパティを挿入し、更新し、削除する能力を含む。更に、テーブル、行及びプロパティを介して走査及びクエリを行って特定された走査／クエリに一致するテーブル、行またはプロパティのセットを見つける機能が提供される。

パーティション分割
テーブルは数十億又は数兆の行及びテラバイト／ペタバイトのデータまで大きくなることができ、テーブルは、テーブルの異なる部分へのトラフィック／負荷を処理するために何千ものサーバに分散されることを必要とするかもしれない。構造化ストレージについてのこの拡張性を実現するために、実施形態では、サーバを介してテーブル及び行を分散するためにパーティション分割することが採用される。パーティション分割することはテーブル内の行をパーティションにグループ化し／分け、次に、パーティションは、異なるサーバに割り当てられて、異なるサーバからサービスを提供される（異なるサーバに対する読み出し及び書き込みを提供する）。

テーブルを拡張可能にするために、テーブルは、パーティションキーを形成するプロパティと称される１つから多数のキーを有する。例えば、図２のテーブル２００を参照すると、テーブル２００の第１の列２０４は、各行／エンティティについてのパーティションキーを含む。所定のテーブルについての１より多くのパーティションキーのプロパティ／列がある場合、結合されたプロパティ／列はそのテーブルについての複合パーティションキーを形成する。行についてのパーティションキーの値は、エンティティ／行が属するパーティションを特定するために用いられる。同じパーティションキー値を有する行は、同じパーティションにグループ化されると考えられる。

パーティションキーに加えて、各行は、ゼロから多数の追加の行キーのプロパティ／列を有していてもよい。例えば、図２のテーブル２００を再び参照すると、テーブル２００の第２の列２０６は、各行／エンティティについての行キーを含む。行キーは、パーティション内の行の一意のＩＤを表す。行キーと組み合わせられたパーティションキーは、テーブル内の行／エンティティについての主キー（一意のＩＤ）を表す。主キーは、テーブル内のパーティションについての主ソート順序を表す。行キーが存在しない場合、パーティションキーは主キーであって、テーブル内の各エンティティを一意に特定しなければならない。下記の説明は単一のパーティションキー及び単一の行キーに関して本発明の実施形態を検討するが、同じ事は、複数のパーティションキー及び／または行キーが用いられる場合にも当てはまる。

パーティションキーは同じパーティションキー「値」を有する行をグループ化するために用いられ、一方、行キーは、パーティション内の行の一意のＩＤを表す。パーティションキー値に基づいてテーブル行を分割することは、本明細書においてテーブルをパーティション分割することと称される。これは、テーブルの行をパーティションにグループ化する／分割する。パーティションは同じパーティションキー値を有する行のセットであり、よって同じパーティションキーを有する行の全ては常に同じパーティションに格納される。従って、同じパーティションキー値を有する２つの行は、同じパーティション内にあって、２つのパーティションにわたって分割されない。更に、いくつかの実施形態において、異なるパーティションキー値を有する複数の行を、これらのキー値がパーティションキー名前空間において隣接しているように見える限り、同じパーティションにグループ化できるまで、パーティションの定義は拡張される。図２のテーブル２００を参照する例として、第１のパーティション（Ｐ１ ２１０）、第２パーティション（Ｐ２ ２１２）、第３のパーティション（Ｐ３ ２１４）及び第４のパーティション（Ｐ４ ２１６）を含む４つのパーティションが示される。図２に示すように、いくつかのパーティションは、単一のパーティションキー値の行を含み、一方、他のパーティションは複数のパーティションキー値の行を含む。前者の例として、Ｐ１ ２１０は１というパーティションキー値を有する全ての行を含み、Ｐ２ ２１２は２というパーティションキー値を有する全ての行を含む。後者の例として、Ｐ３ ２１４は、パーティションキー値３、４または５を有する全ての行を含み、Ｐ４ ２１６は、６または７のパーティションキー値を有する全ての行を含む。

パーティション分割することの利点は、以下のことを含むがこれらに限定されるものではない。以下のことは、（１）テーブルをパーティションに分割しかつデータのアクセスパターン及びトラフィックの必要性に基づいてサーバを介してパーティションを分散することによってテーブルへのアクセスを拡張する能力、及び（２）同じパーティションの行はグループ化されて、同じテーブルサーバからアクセスされ、同じテーブルサーバは、オペレーションがパーティション内でスコープされると、より効果的なクエリ、走査及びキャッシングを可能にすることである。たかだかパーティション内のこれらの行がスキャンされる必要があるだけなので、パーティションのスキャンはより効率的である。クエリを行うときにパーティションキーを特定しなければテーブル全体にわたって詳しく検討しなければならない可能性がある代わりに、パーティションのスキャンは、パーティションについての単一のテーブルサーバからアクセスされるからである。

高レベルのアーキテクチャ
本発明の実施形態に基づいて、本明細書において「テーブルサーバ」と称されるサーバのセットは、構造化ストレージシステムを格納して構造化ストレージシステムへのアクセスを提供する。更に、本明細書において「テーブルマスタ」と称されるサーバのセットは、テーブルサーバを管理する。「テーブルクライアント」は、構造化ストレージにアクセスできるアプリケーションを提供する。

ここで図３を参照すると、本発明の実施形態に基づくシステム３００の高レベルのアーキテクチャを示すブロック図が提供される。本明細書において説明されるこの配列及び他の配列は、例としてだけ記載されていると理解されなければならない。他の配列及び要素（例えば、マシン、インタフェース、機能、順序及び機能のグループ化等）は、示されたこれらものに加えてまたはこれらのものの代わりに用いることができ、いくつかの要素は完全に省略することができる。更に、本明細書において説明される要素の多くは、機能エンティティである。機能エンティティは、個別のコンポーネントもしくは分散コンポーネントとしてまたは他のコンポーネントとともに、かつあらゆる適切な組合せ及び位置において実装することができる。１つまたは複数のエンティティによって実行されると本明細書において説明される様々な機能は、ハードウェア、ファームウェア及び／またはソフトウェアによって実行されてもよい。例えば、様々な機能は、メモリに格納されたプロセッサ実行命令によって実行されてもよい。

図示されていない他のコンポーネントの中で、システム３００は通常、テーブルマスタ３０２、テーブルサーバ３０４、３０６、３０８、３１０及びテーブルクライアント３１２を含む。各々は、例えば、図１を参照して説明されるコンピュータデバイス１００などのコンピュータデバイスのいずれのタイプにも存在することができる。システム３００のコンポーネントはネットワークを介して互いに通信することができる。ネットワークは、１つまたは複数のローカルリアネットワーク（ＬＡＮ）及び／またはワイドエリアネットワーク（ＷＡＮ）を含むがこれらに限定されなくてもよい。単一のテーブルマスタ、４つのテーブルサーバ及び単一のテーブルクライアントだけが図３に示されているが、テーブルマスタ、テーブルサーバ及びテーブルクライアントの任意の数を、本発明の実施形態の範囲内のシステム３００内で用いることができると理解されるべきである。

テーブルマスタ３０２は、以下のことに関与する。以下のことは、（１）パーティションをテーブルサーバ３０４、３０６、３０８、３１０に割り当てること、（２）パーティションが障害によりサービスを提供されない場合を素早く判断してパーティションを異なるテーブルサーバに再割り当てすること、（３）テーブルサーバ３０４、３０６、３０８、３１０の間のパーティションの負荷分散を制御すること、及び（４）テーブルサーバ３０４、３０６、３０８、３１０のヘルスをモニタすること、である。

テーブルサーバ３０４、３０６、３０８、３１０の各々は、テーブルマスタによってこれらに割り当てられたパーティションへの読み出しアクセス及び書き込みアクセスを提供することに関与する。テーブルサーバ３０４、３０６、３０８、３１０の各々は、ゼロから多数のパーティションをホストすることができる。図３の例において、ＴＳ１ ３０４は、パーティションＰ１及びＰ４をホストし、ＴＳ２ ３０６はパーティションＰ２及びＰ７をホストし、ＴＳ３ ３０８はパーティションＰ３をホストし、ＴＳ４ ３１０はパーティションＰ５及びＰ６をホストする。

テーブルクライアント３１２は、アプリケーションにリンクされて、テーブルサーバ３０４、３０６、３０８、３１０によって維持されるパーティションにコマンドを発行するために用いられる。テーブルクライアント３１２は、パーティションマップを用いてパーティションにサービスを提供しているテーブルサーバを決定し、そのテーブルサーバにコマンドを送信する。テーブルクライアント３１２はまた、テーブルサーバから戻る結果を受信して、アプリケーションに結果を渡す。パーティションマップは、特別なテーブルであり、これはパーティションとパーティションにサービスを提供しているテーブルサーバとの間のマッピングを格納し、テーブルマスタ３０２によって維持される。

図４に表されるように、内部で、テーブルサーバにおいてサービスを提供されるパーティション４００は、３つの主要部分を含む。更新ログ４０２、１つから多数のメモリテーブル４０４、及びゼロから多数のファイルテーブル４０６である。更新ログ４０２は、永続ストレージ内のパーティションに対する最近の変化を記録する。メモリテーブル４０４は、更新ログの最近の（差分）更新のメモリ内バージョンである。これらは、パーティション４００に対する最近の差分変更である。メモリテーブル４０４が十分に大きくなるかまたはその中で十分な変化がある場合、メモリテーブル４０４は、チェックポイントが付されてストレージに対して持続されるファイルテーブル４０６になる。このことが生じると、チェックポイントが付されたメモリテーブル４０４までの更新ログ４０２内の要求の全ては、更新ログ４０２から除去することができる。以前に説明したように、パーティションは、ストリームのセットを有してパーティションの持続的な状態を格納する。更新ログ４０２は、これらのストリームのうちの１つに格納されるが、これらは更新ログストリームと称される。全てのファイルテーブル４０６は、これらのストリームのうちの１つに格納されるが、これらは、ファイルテーブルストリームと称される。

テーブルサーバがパーティションをロードすると、テーブルサーバは、パーティションが最後にアンロードされた直前の状態に戻るメモリテーブルを再構築するために、最新のチェックポイント以後の更新ログ内の全ての要求を再現する。

テーブルサーバにおいてパーティションにアクセスすると、テーブルサーバは、全ての最近の変更を見るためにメモリテーブル内に一致する行があるかどうかを最初によくチェックし、一致がない場合、テーブルサーバはデータについてのそのページのキャッシュ及びファイルテーブルを調べる。

パーティション及び複数のファイルテーブルについての複数のメモリテーブルが存在してもよい。１つのメモリテーブルがいっぱいになると、チェックポイントが付されてファイルテーブルになる必要があるので、複数のメモリテーブルが存在してもよい。このことが生じている間に、現在のメモリテーブルはリードオンリであるよう設定されるがチェックポイントが行われ、新しいメモリテーブルが書き込みのためにパーティションについて作成される。従って、パーティションは常に最近の（差分）更新のために用いられている１つのメモリテーブルを有し、パーティションはゆっくりとチェックポイントが付される１つまたは複数のメモリテーブルを有することができる。一旦メモリテーブルはチェックポイントが付されてファイルテーブルになると、メモリテーブルは削除されてもよいしまたは不要なデータとして集められてもよい。

パーティションに対して行われたチェックポインティングの全てにより、パーティションについての複数のファイルテーブルのチェックポイントが存在してもよい。これによって、データがファイルテーブルから読み出され必要があるときに、複数のファイルテーブルが見られる必要がありかつ最近のものから最も古いものまで調べられる可能性がある。これは、書き込まれた最近のファイルテーブルがパーティションについての最近の変更を含むからである。十分なファイルテーブルをパーティションについてチェックポイントを行うと、パーティションについて調べられているデータを見つけるためにサーチされる必要があるファイルテーブルの数を減らすために、テーブルサーバは、ファイルテーブルを新しくマージされたファイルテーブルにゆっくりと圧縮する／マージする。

拡張可能で可用性の高い耐久性のある構造化ストレージ
本発明の実施形態は、パーティション分割、負荷分散及びスロットリングを用いて、拡張可能な構造化ストレージシステムを提供する。拡張可能性は、以下のことによって提供される。以下のことは、（１）テーブルをパーティションに分割して、パーティションをデータセンタ内の多数のサーバに分散させること、（２）負荷分散を用いて、高負荷のテーブルサーバからより軽負荷のテーブルサーバへパーティションを移動すること、及び（３）送信されている過剰なトラフィックを有するパーティションに要求を入れることを調整するかまたは、送信されている過剰なトラフィックを有するテーブルサーバに要求を入れること、である。

拡張可能性は、パーティションの異なる部分への負荷に基づいてテーブルをパーティションに自動的に分割してテーブルサーバにわたって負荷分散することによって提供される。負荷分散はシステムを作業負荷に動的に適応させ、多数のマシンにわたって負荷を分散し、これによって全ての物理的なリソースを効率的に利用してより良い拡張可能性を実現する。更に、スロットリングはシステムを高負荷から保護し、効率的な型／最適化された型でシステムを動作させ続ける。

可用性はテーブルマスタによってサービスを提供されていないパーティションを特定し、パーティションを異なるテーブルサーバに割り当てて、パーティションマップを更新することにより提供するが、パーティションマップによって、テーブルクライアントはそこにアクセスするためのパーティションの新しい位置を見つけられるようになる。ノード／ネットワークの障害の場合にパーティションを素早く再割当てすることによって、全てのパーティションはアクセス可能に保持され、高いシステム可用性が生み出される。

耐久性は、パーティションのデータの全てを複製されたスリーム層に格納することによって提供される。ストリーム層は、ストリーム（ファイルに類似している）にデータを書き込みかつそこから読み出すためのインタフェースのようなファイルシステムを提供し、ストリーム層は、システム内のテーブルサーバのうちのいずれからでも常に耐久性があって可用性があるデータが複製されることを確実にするための完全な機能を提供する。従って、パーティションマップを含むパーティション情報はログを更新し、ファイルテーブルはストリーム層に格納される。

効率的なストリームレベルのオペレーション
ストリーム層は、ストリームの領域を別のストリームに効率的にハードリンクする機能を提供する。ストリーム層の各ストリームは、エクステントと称されるデータブロックのリストを構成する。ストリーム内のデータは実際に、これらのエクステント内に格納される。ストリームは、エクステントの順序付けられたリストである。所定のエクステントは複数のストリーム内に存在することができるかまたは、同じストリームの順序付けられたエクステントのリストにおいて複数回現われることさえできる。ストリーム層は、インタフェースを提供して、別のストリーム内に存在する既存のエクステントのセットをリンクすることによってストリームを構成する。実際のデータのコピーはこのプロセス内に含まれていないので、非常に効率的である。ストリーム層は、各エクステントの参照数を維持する。一旦エクステントがエクステントを示しているストリームを有しなくなると、ストリーム層はシステムから不要なデータを集める／このエクステントを削除する。

ストリーム層はまた、１つのアトミックトランザクションにおいて、作成、削除、ストリーム名の変更及びストリームへのエクステントのハードリンクなどの複数のストリームレベルのオペレーションを有する能力をサポートする。

構造化ストレージシステムは、これらの特徴を広く利用して、パーティションのストリームのもはやサポートされない部分について効率的に不要データ収集する。１つの例が、一旦パーティションのチェックポイントが作成されると、チェックポイントより前の更新ログ内の全てのメッセージがもはや用いられないことである。これらの特徴は、更新ログストリームと同じ名前の新しいストリームをアトミックに作成することによって更新ログを効率的に切り捨てるために用いられ、まだ使用中のエクステントを元のストリームから新しいストリームへハードリンクし、元のストリームを削除する。全てのこれらのことは１つのアトミックトランザクションにおいて行われる。これは、障害処理論理を著しく単純化する。同様のスキームも、パーティションのファイルテーブルストリーム及びメタデータストリームなどの他のストリームに用いられる。

構造化ストレージシステムはまた、後の方のセクションにおいて説明したように、これらの特徴を広く利用してパーティションの分割及びマージを効率的に実施する。より具体的には、これらの特徴は、あらゆるビットを物理的にコピーまたは移動する必要なしに、元のパーティション（または複数の元のパーティション）から分割／マージで作成された子パーティション（または複数の子パーティション）へデータを効率的に参照するために用いられる。

パーティションの分割、マージ、負荷分散
本発明のいくつかの実施形態は、ストレージシステム内のテーブルサーバの間で負荷分散のバランスを取る。通常、テーブルサーバは、各パーティションの負荷を追跡し、この情報をテーブルマスタに周期的に報告する。テーブルマスタは、テーブルサーバの中でパーティションを移動することによって負荷分散を決定する。これは、元のテーブルサーバから対象パーティションをアンロードして、パーティションを他のテーブルサーバに割り当てることによって実現される。

最適化として、本発明のいくつかの実施形態は、パーティションがアンロードされる前にまたはアンロードされるときに、テーブルマスタにテーブルサーバに対する「アンロードする準備をせよ」という要求を送信させることができる。テーブルサーバは、この要求を受信すると、パーティションが再びロードされるときにリプレイされる必要があるログの量を減らすために、パーティションでチェックポイントを付す。このことは、パーティションにサービスを提供するための利用可能なＳＬＡを満足するように提供される。

単一のパーティションが相対的により高負荷を有する場合、パーティションを２又はそれ以上のパーティションに分割することが望ましくなり、これは、パーティションが１より多くのパーティションキー値を含む場合にだけ可能である。その後、子パーティションのうちの１つまたは複数は、異なるテーブルサーバにアンロードされて負荷分散を実現することができる。

負荷分散追跡のために、サンプリングメカニズムが各テーブルサーバによって用いられて、メモリを多量に消費することなしに各パーティション内のきめ細かい負荷情報を追跡する。負荷情報を追跡するために、パーティションは、本明細書において「バケット」と称される、複数のパーティションキー範囲へ分割され、各バケットに対応する負荷が追跡される。より具体的には、テーブルサーバは、これらのバケットに分類される要求を確率的にサンプリングし、複数のバケットにわたる負荷分散を追跡する。例えば、図２のテーブル２００内のパーティションＰ３ ２１４を参照すると、パーティションは負荷追跡目的のために２つのバケットに分割することができる。第１のバケットは３のパーティションキー値を有する行を含み、第２のバケットは４というパーティションキー値及び５というパーティションキー値を有する行を含む。実施形態において、バケットの境界は常に、パーティションキー値上に存在しなければならない。即ち、同じパーティションキー値を有する行は、常に同じバケット内に存在する。例えば、３というパーティションキー値を有する行は、負荷追跡目的及び分割目的のために２つのバケットに分割することができない。

いくつかの実施形態において、集められたトラフィックサンプルに基づいて、バケットの境界を、パーティション内のキーにわたってトラフィック分散をより正確に追跡するために動的に調整することができる。即ち、２つの既存のバケットが他のバケットと比較して多くの負荷を有していない場合、バケットは単一のバケットにマージされる。逆に、１つのバケットが全ての他のバケットよりかなり多くの負荷を含む場合、そのバケットは可能ならば２つに分割することができる。例えば、以前の例において、第２のバケットが第１のバケットと比較して過剰な負荷を含む場合、第２のバケットはより小さい２つのバケットに分割されることができ、そのうちの１つはパーティションキー値４を有する行を含み、そのうちのもう１つはパーティションキー値５を有する行を含む。更に、パーティションキー値３を含む第１のバケットがほとんど負荷を有していない場合、第１のバケットはパーティションキー値４を含んでいるバケットとマージすることができる。このバケットサイズのモニタ及び調整は、オンザフライで動的にすべて行われる。１つのパーティション内でパーティションキーにわたって負荷分散を追跡するために用いられるバケットレベルのサンプリングスキームの他に、テーブルサーバはまた、全パーティションの作業負荷の総量を追跡する。全パーティションの作業負荷の総量は、テーブルマスタに伝えられる。従って、パーティションが負荷に基づいて分割される必要がある場合、どこでパーティションが分割されなければならないかを決定するためのかなり正確な負荷分散情報が、テーブルサーバ及びテーブルマスタの両方に利用可能である。

ここで図５を参照すると、本発明の実施形態に基づくパーティションの分割方法５００を示すフロー図が提供される。図５の実施形態において、親パーティションＰ１は、２つの子パーティションであるＰ１’（行のサブセットだけを含むよう修正される元のパーティション）及びＰ２（残りの行を含む新しいパーティション）に分割される。図５は、パーティションを２つの子パーティションに分割することを検討するが、パーティションは本発明の実施形態に基づいて２つ以上の子パーティションに分割することができると理解されるべきである。

最初に、ブロック５０２に示すように、負荷分散情報が、テーブルサーバ、パーティション及び／またはパーティションの一部（即ち、「バケット」）について追跡される。上記のようにパーティションの部分レベルできめ細かい負荷情報を追跡することによって、どこでパーティションを分割するかについての決定することができる。負荷情報は、テーブルサーバによって追跡されて、テーブルマスタに周期的に提供される。現在の実施形態において、テーブルマスタに送信された負荷情報は、各パーティションの総負荷及び各テーブルサーバの負荷を含む。いくつかの他の実施形態は、バケットレベルの情報を含む全ての負荷追跡情報をテーブルマスタに提供することができる。パーティションが負荷分散及び分割を決定する際に役立つ追加の情報、制約事項及びヒントが、テーブルサーバからテーブルマスタに提供される。例えば、バケット情報の分散に基づいて、テーブルサーバは、深刻さの度合を用いてパーティションが「分割するのを認めたがらない」ことを分類する。高い度合では、テーブルマスタはテーブルサーバがパーティションを分割しようとしないのでパーティションについての分割を要求するべきでないことを意味し、中間の度合では、テーブルサーバがパーティションを分割しないことを選択することができる特定の状況が存在しかつテーブルマスタがその決定を無効にすることができることを意味し、低い度合では、テーブルサーバがテーブルマスタに従ってテーブルマスタからの指示を聞いて受け取ることを意味する。

テーブルマスタは、負荷情報を用いて、負荷分散の決定を行う。負荷分散の決定は、パーティションを分割するかどうか、パーティションをマージするかどうか、及び／またはテーブルサーバの中でパーティションを移動するかどうかを含む。図５の本実施形態では、テーブルマスタは、ブロック５０４に示すように、負荷分散情報に基づいてパーティション（Ｐ１）を分割すること決定する。

ブロック５０６において、テーブルマスタは、パーティションを分割するための分割比を決定する。 分割比は、パーティションが分割されるべき位置を決定するための負荷比を表す。例えば、テーブルマスタは、３０％／７０％の負荷ポイントでパーティションを分割することを決定することができる。換言すれば、パーティションは、パーティションの第１の部分に対する負荷が３０％でありかつパーティションの残り部分に対する負荷が７０％であるポイントにおいて分割されなければならない。ブロック５０８において、テーブルマスタは、分割のために特定されたパーティションをホストしているテーブルサーバに要求を送信する。特に、テーブルマスタは、パーティションにおける分割比に対応する位置を特定しているキー情報を要求する。要求に応じて、テーブルサーバは、ブロック５１０で示されるように、分割比に基づいてパーティションを分割するための実際のパーティションキー位置を特定する。実際の位置は、分割比によって特定される負荷分散との一致を実現しようとする。但し、実際の負荷分散は変化することができる。例えば、テーブルマスタによって要求される分割比は、３０％／７０％の負荷分散であってもよいが、提供することができる一番近い一致が、３５％／６５％の負荷分散であってもよい。

いくつかの実施形態では、分割のための実際の位置は、パーティションキー情報を用いて特定される。例えば、図２のパーティションＰ３ ２１４が３というパーティションキー値と４というパーティションキー値との間で分割されることになっていた場合、分割を特定しているキー情報は、３というパーティションキー値及び／または４というパーティションキー値であってもよい。いずれかのかつ全てのかかる変化形は、本発明の実施形態の範囲内であるべきであると考えられる。ブロック５１２に示すように、テーブルサーバは、分割比についてのキー情報をテーブルマスタに返す。

ブロック５１４に示すように、テーブルマスタは、子パーティションのうちの１つとして新しいパーティション（Ｐ２）についてのストリームを構築する。パーティションの全ての永続的状態は、そのパーティションについての「ストリーム」に保持される。パーティションについてのメタデータストリームが存在し、メタデータストリームは、パーティションの全ての他のストリームに対するポインタを、パーティションに含まれる全ての行のパーティションキー範囲などの、そのパーティションの基本的情報と同様に含む。このステップにおいて、テーブルマスタは、分割比に対応する正しいパーティションキー範囲の情報を有する新しいパーティション（Ｐ２）についてのメタデータストリームを作成することに関与する。更に、ブロック５１６において、テーブルマスタは、テーブルサーバに分割要求を送信する。分割要求は、テーブルマスタからテーブルサーバへの次のわずかな時間において提供されてもよい。

いくつかの実施形態において、適切なマスタログが障害を処理するために書かれる。対応するステップが完了した後に、テーブルマスタは各ステップのログを取り、その結果、マスタ障害の場合には、ログをリプレイすることができ、テーブルマスタは、中止されたところから分割を再開することができる。

分割要求を受信した後に、ブロック５１８に示すように、テーブルサーバは、元のパーティション（Ｐ１）にサービスを提供するのを止めてアンロードする。ブロック５２０に示すように、テーブルサーバはまた、元のパーティションから２つの子パーティション（Ｐ１’及びＰ２）を構築する。テーブルサーバは、元のパーティション（Ｐ１）内の情報に基づいて、新しいパーティション（Ｐ２）についてのストリーム（メタデータストリームを除く）を構築する。より具体的には、Ｐ２のキー範囲に属するデータの一部は、下層のストリーム層の特徴を用いて、パーティションＰ１からパーティションＰ２のストリームに効率的にコピーされる／ハードリンクされる。子パーティションＰ１’は、Ｐ１のキー範囲を調整することによって「作成」される。子パーティションＰ１’は、元のパーティションＰ１と同じストリームのセットを用いる。Ｐ１’のメタデータは、減少したキー範囲に適応するよう変更される。

ブロック５２２に示すように、テーブルサーバは両方の子パーティション（Ｐ１’及びＰ２）をロードし、これらのパーティションへのサービスの提供を開始する。更に、ブロック５２４に示すように、テーブルサーバは、分割の完了についてテーブルマスタに通知する。この通知は、テーブルサーバからテーブルマスタへの次のわずかな時間において提供されてもよい。ブロック５２６に示すように、テーブルサーバからの分割完了通知に応じて、テーブルマスタは、パーティションマップを更新して新しいパーティションを示す。この時点で、テーブルマスタは、分割が完了したと見なすことができる。ブロック５２８に示すように、テーブルマスタは、それがパーティションマップに一致するため、新しく作成された子パーティション（Ｐ２）を含む新しい割り当てをテーブルサーバに送信する。

いくつかの実施形態において、パーティションが分割された後に、テーブルマスタは、元のパーティションが存在しているテーブルサーバから別のテーブルサーバに子パーティションを移動することを決定できる。これによって、テーブルマスタはネットワークを介して負荷を効果的に分散できるようになる。パーティションの移動は、１つのテーブルサーバからパーティションをアンロードしてパーティションを別のテーブルサーバに割り当てることによって実現される。

本発明の他の実施形態において、図５を参照して上記した分割プロトコルのパフォーマンスは、ブロック５１８において、元のパーティションがアンロードされる前に、新しい子パーティションを作成することによって改善することができる。上記の方法５００に対する他の変化形も、当業者に明らかになり、本発明の実施形態の範囲内である。

図６は、本発明の実施形態に基づいて図２のＰ３ ２１４を分割する例を示す。特に、図６は、ＴＳ３ ３０８に存在するＰ３ ２１４の分割を行なうために図３のテーブルマスタ３０２とＴＳ３ ３０８との間の相互作用を示す。最初に、符号６０２に示すように、テーブルマスタ３０２は、ＴＳ３ ３０８に要求を送信して、Ｐ３ ２１４を分割するための位置を特定するキー情報についてクエリを行う。要求は０．３の分割比を特定し、分割比は、テーブルマスタがＰ３ ２１４の負荷の３０％を受信したＰ３ ２１４のうちの１つの部分と負荷の７０％を受信した残りの部分との間の位置でＰ３ ２１４を分割することを所望していることを示す。

テーブルマスタ３０２からの要求に応じて、ＴＳ３ ３０８は、テーブルマスタ３０２によって特定される分割比に対応するキー情報を決定する。キー情報は、分割比としてテーブルマスタ３０２によって特定される３０％／７０％の負荷分散に基づいて、Ｐ３ ２１４の２つの部分同士の間の位置を表す。この例では、ＴＳ３ ３０８は、３というパーティションキー値を有する行の負荷は負荷の約３０％を有し、一方残りの行の負荷は負荷の約７０％を有すると決定する。このように、この例におけるＴＳ３ ３０８によって決定されるキー情報は、４というパーティションキー値である。様々な実施形態において、他のキー情報が、Ｐ３ ２１４が分割されなければならない位置を特定するために提供されてもよいと理解されるべきである。

符号６０６において、ＴＳ３ ２１４はキー情報（即ち、４というパーティションキー値）をテーブルマスタ３０２に伝える。符号６０８において、テーブルマスタ３０２は、新規なパーティションであるＰＮについてのストリームを構築する。更に、符号６１０に示すように、テーブルマスタ３０２は、テーブルマスタに分割要求を送信する。この例の分割要求は、子パーティションの各々についての所定の範囲を特定する。特に、１つの子パーティションであるＰ３’について、分割要求は、３という低パーティションキー値及び４という高いパーティションキーを示し、Ｐ３’は３というパーティションキー値を有する行を含むことを示す。他の子パーティションであるＰＮについて、分割要求は、４という低パーティションキー値及び６という高パーティションキー値を示し、ＰＮは４というパーティションキー値を有する行を、５というパーティションキー値を有する行と同様に含むことを示す。

符号６１２において、分割要求に基づいて、ＴＳ３は元のパーティションであるＰ３ ２１４にサービスを提供するのを止める。更に、ＴＳ３ ３０８は、符号６１４に示すように、Ｐ３をＰ３’及びＰＮに分割し、符号６１６に示すように、Ｐ３’及びＰＮへのサービスの提供を開始する。符号６１８に示すように、次に、ＴＳ３ ３０８はテーブルマスタ３０２に分割の完了通知を送信する。テーブルマスタ３０２は、符号６２０においてパーティションマップを更新して子パーティションを示す。

ここで図７を参照すると、本発明の別の実施形態に基づいてパーティションを分割する方法７００を示すフロー図が提供される。図７の実施形態において、親パーティションＰ１は、２つの新しい子パーティションＰ２及びＰ３に分割され、これらの各々は親パーティションＰ１からの行の一部を含む。図７はパーティションを２つの子パーティションに分割することを検討しているが、パーティションは、本発明の実施形態に基づいて２つより多くの子パーティションに分割することができると理解されるべきである。

図５の方法５００と同様に、ブロック７０２に示すように、負荷分散情報が最初に追跡される。負荷分散情報によって、テーブルマスタは、パーティションを分割するかどうか、パーティションをマージするかどうか、及び／またはテーブルサーバの中でパーティションを移動するかどうかを含む負荷分散の決定を行えるようになる。図７の本実施形態において、ブロック７０４に示すように、テーブルマスタは、負荷分散情報に基づいてパーティション（Ｐ１）を分割することを決定する。

ブロック７０６において、テーブルマスタは、パーティションを分割するための分割比を決定する。前述のように、分割比は、パーティションが分割されるべき位置を決定するための負荷比を表す。例えば、テーブルマスタは、３０％／７０％の負荷ポイントでパーティションを分割することを決定できる。ブロック７０８において、テーブルマスタは、分割のために特定されるパーティションをホストしているテーブルサーバに要求を送信する。特に、テーブルマスタは、パーティションにおける分割比に対応する位置を特定するキー情報を要求する。ブロック７１０に示すように、要求に応じて、テーブルサーバは、分割比に基づいてパーティションを分割するための実際の位置を特定する。ブロック７１２に示すように、テーブルサーバは、分割比についてのキー情報をテーブルマスタに返す。

ブロック７１４に示すように、テーブルマスタは、新規なパーティション（Ｐ２及びＰ３）についてのメタデータストリームを構築する。いくつかの実施形態において、適切なマスタログが、障害を処理するために書き込まれる。テーブルマスタは、対応するステップが完了した後に各ステップのログを取り、その結果、マスタの障害の場合には、ログをリプレイすることができ、テーブルマスタは、中止されたところから分割を再開することができる。更に、ブロック７１６において、テーブルマスタは、分割要求をテーブルサーバに送信する。分割要求は、テーブルマスタからテーブルサーバへの次のわずかな時間において提供されてもよい。

ブロック７１８に示すように、分割要求に応じて、テーブルサーバは、元のパーティション（Ｐ１）から２つの子パーティション（Ｐ２及びＰ３）を構築する。テーブルサーバは、元のパーティション（Ｐ１）に基づいて（メタデータストリーム以外の）新規なパーティション（Ｐ２及びＰ３）についてのストリームを構築する。より具体的には、Ｐ２のキー範囲に属するデータ部分は、下層のストリーム層の特徴を用いてパーティションＰ１からパーティションＰ２のストリームに効率的にコピーされる／ハードリンクされる。同様に、Ｐ３のキー範囲に属するデータ部分は、下層のストリーム層の同じ特徴を用いてパーティションＰ１からパーティションＰ３のストリームに効率的にコピーされる／ハードリンクされる。

ブロック７２０に示すように、テーブルサーバは、元のパーティションにサービスを提供するのをやめてアンロードする。更に、ブロック７２２に示すように、テーブルサーバは、両方の子パーティション（Ｐ２及びＰ３）をロードして、これらのパーティションへのサービスの提供を開始する。ブロック７２４に示すように、テーブルサーバは、分割の完了についてテーブルマスタに通知する。この通知は、テーブルサーバからテーブルマスタへの次のわずかな時間において提供されてもよい。ブロック７２６に示すように、テーブルサーバからの分割の完了通知に応じて、テーブルマスタは、パーティションマップを更新して新規なパーティションを示す。この時点で、テーブルマスタは、分割が完了したと見なすことができる。ブロック７２８に示すように、新規な割り当てがパーティションマップに一致するように、テーブルマスタは新しく作成した子パーティション（Ｐ２及びＰ３）を含む新規な割り当てをテーブルサーバに送信する。

いくつかの例では、テーブルマスタは、例えば負荷分散情報に基づいて、２又はそれ以上のパーティションを単一のパーティションにマージすることを決定できる。１つの実施形態において、マージは、２つの隣接する（即ち、テーブル内の連続する行において隣接する）パーティションが相対的に低い負荷を有する場合に行なわれる。パーティションを単一のパーティションにマージすることは、システム内のパーティションの数を減じるために有利であるかもしれない。

従って、図８は、本発明の実施形態に基づいてパーティションをマージする方法８００を示すフロー図を示す。ブロック８０２に示すように、負荷分散情報が、最初に追跡される。ブロック８０４に示すように、テーブルマスタは、負荷分散情報に基づいて、２つのパーティション（Ｐ１及びＰ２）が新規なパーティション（Ｐ３）にマージされるべきと判断することができる。実施形態において、連続していてばらばらでないパーティションキー範囲を形成するパーティションだけが、マージされ得る。

ブロック８０６に示すように、テーブルマスタが２つのパーティションをマージすることを決定する場合、テーブルマスタは、２つのパーティションにサービスを提供するテーブルサーバ（または複数のテーブルサーバ）に、「マージを準備せよ」というメッセージ（または複数のメッセージ）を送信する。いくつかの例では、両方のパーティションが単一のテーブルサーバに存在することができるが、他の例では、パーティションは異なるテーブルサーバに存在する。「マージを準備せよ」というメッセージは、マージされたパーティションについてのロード時間を減少するために、マージに先立ってパーティションを圧縮する機会をテーブルサーバ（または複数のテーブルサーバ）に与える。

テーブルマスタは、ブロック８０８においてマージされたパーティション（Ｐ３）についてメタデータストリームを作成し、ブロック８１０において親パーティションが存在するテーブルサーバ（または複数のテーブルサーバ）から２つの親パーティション（Ｐ１及びＰ２）をアンロードする。ブロック８１２に示すように、次に、テーブルマスタは、パーティションマップを更新する（古いパーティションエントリをアトミックに除去して、新規なパーティションエントリを挿入する）。テーブルマスタの全体像から、マージトランザクションは、この時点で完了している。テーブルマスタのフェールオーバの場合、新規なマージされたパーティションは、ブートストラップの間持続されるパーティションマップにおいて見出されるからである。

ブロック８１４に示すように、テーブルマスタは、マージされたパーティション（Ｐ３）をテーブルサーバに割り当てる。マージされたパーティションを割り当てるテーブルサーバは、システム内のいかなるテーブルサーバであってもよい。例えば、割り当てられたテーブルサーバは、親パーティションのうちの１つまたは両方が存在したテーブルサーバであってもよいしまたは、システム内の異なるテーブルサーバであってもよい。

ブロック８１６に示すように、割り当てが行われると、テーブルサーバはマージされたパーティションをロードする。マージされたパーティションのメタデータストリームから、テーブルサーバは、これがマージされたパーティションであると知って、テーブルサーバは、下層のストリーム層からの特徴を用いて親パーティションからのデータを効率的にコピーする／ハードリンクすることによって親パーティションからマージされたパーティションのストリームを構築する。構築が行われた後に、テーブルサーバは、このイベントをマージされたパーティションのメタデータストリームへ記録して（この次このパーティションをロードするときに、ストリームが再び構築されないように）、親パーティションのストリームを削除する。

こわれたパーティション分割の状態からの回復
耐久性のある構造化ストレージシステムは、システム状態のバグから回復することが可能でなければならない。この能力を実現するために、本発明の実施形態における構造化ストレージシステムは、アペンド専用のストアに構築され、全ての削除されたデータは、システム内のあらゆるデータ破損を発見するのに十分長いとみなされる最小限の時間にわたって保持される。

ここで図９を参照すると、本発明の実施形態に基づいてこわれたパーティション状態からパーティションを回復する方法９００を示すフロー図が提供される。最初に、ブロック９０２に示すように、こわれたパーティションが特定される。パーティションがこわれてサービスが提供されない場合、サービスを提供されていないとしてパーティションを示す警告が行われる。これによって、そのパーティションのデータに対する可用性の一時的な損失が生じるかもしれない。

ブロック９０４で示すように、こわれたパーティションは、一貫性のあるパーティション状態に回復される。システムは、以下のいずれかを行うことができる。（ａ）パーティションを修理する。パーティションに対する全ての以前の変更はアペンド専用のストアに格納されており、アペンド専用ストアは、あらゆるデータを失うことなくパーティションを修復できるからである。または（ｂ）パーティションを時間内に以前のポイントにロールバックする。以前のポイントは、ロールバック時間と障害の時間との間に生じた変更の損失を潜在的にもたらす。一旦パーティションが修理されると、パーティションは構造化データの読み出し及び書き込みのためのサービスを再び提供されるために利用できる。

パーティションのロールバックの間、システムは、まだ有効な状態にある最近のチェックポイントを見つけ、最近のチェックポイントがまだ存在するならば、対応するログとともにチェックポイントを使用してパーティション状態を再構築する。

パーティションのロールバックの間、一部の例では、パーティションの現在のメタデータ及びデータコンテンツは、パーティション状態を回復するために不十分である。そのような場合、システムは、対象パーティションを含む最近の分割及びマージの間の、対象パーティションの親（または複数の親）を含む、他の関連するパーティションからのデータを使用する。より具体的には、システムは、親パーティション及び対象パーティションから最近の有効なチェックポイントの状態をマージすることによってパーティションの状態を再構築する。

ブロック９０６に示すように、全てのパーティションが回復するかまたは再構築された後に、パーティションマップは、再構築されたシステムの全てのパーティションのキー範囲を一致させるために修正される。このことは、システムをグローバルな一貫性のある状態へ戻す。

パーティションのバージョン管理及びアップグレード
テーブルサーバコードのアップグレードを行うと、アップグレードは、一度にテーブルサーバのサブセットだけで実行される。このように、テーブルサーバはＮ個のアップグレード領域に分解され、各アップグレード領域は１つずつアップグレードすることができる。

図１０を参照すると、本発明の実施形態に基づくアップグレードの間、パーティションをバージョン管理する方法１０００を示すフロー図が提供される。ブロック１００２に示すように、パーティションは、アップグレードプロセスの間、次にアップグレードされることになっている対象アップグレード領域内のテーブルサーバから移動することができる。ブロック１００４に示すように、新しいテーブルサーバコードのバージョンは、対象アップグレード領域内でテーブルサーバに配置される。

ブロック１００６に示すように、アップグレードプロセスの間、パーティションは、新規のテーブルサーバコードのバージョンを有するテーブルサーバに割り当てられて、潜在的に新規なデータフォーマットを用いて修正が開始することができる。この修正の後、パーティションは、より新規なアップグレードされたテーブルサーバによってだけサービスが提供されて、より古いバージョンのテーブルサーバによってはサービスが提供されない。このように、一旦パーティションがバージョンＮのテーブルサーバによってサービスを提供されると、ブロック１００８に示すように、システムによって、パーティションがバージョンＮ又はそれより後の（またはそうでなければ互換性を持つテーブルサーバのバージョン）テーブルサーバによってだけサービスを提供されることが確実にされる。

このことは、本発明の実施形態の範囲内の多くの異なるやり方で実現することができる。例えば、１つの実施形態において、バージョン番号は、各パーティション、テーブルサーバ及びテーブルマスタについて追跡される。アップグレードが生じると、パーティションにサービスを提供しているテーブルサーバがより大きいバージョン番号であるならば、パーティションは、そのバージョン番号を引き受ける。そのポイントが存在する位置から、パーティションはそのバージョンまたはより大きいバージョンのテーブルサーバによってだけサービスを提供されることができる。

別の実施形態において、各テーブルサーバがアップグレードされるとすぐに、テーブルサーバは、そのバージョンを示すためにテーブルマスタに通信する。テーブルマスタは、最新のテーブルサーババージョンを追跡し、割り当てられることになっているパーティションを最新バージョン（またはそうでなければ互換性を持つバージョン）を有するテーブルサーバに割り当てることだけができる。

また別の実施形態において、パーティションのバージョンは、パーティションメタデータとともに持続される。テーブルサーバは、テーブルマスタに割り当てられたパーティションのバージョンをテーブルマスタに通知する。テーブルサーバはまた、テーブルサーバ自身のバージョン番号をテーブルマスタに報告する。これによってテーブルマスタは、パーティションのバージョンをテーブルサーバのバージョンと同様に追跡する。このように、テーブルマスタによって、パーティションが互換性を持つバージョンのテーブルサーバに割り当てることができることが確実になる。

結論
本発明は、限定的であるよりはむしろ説明的であるようあらゆる点で意図された特定の実施形態に関して説明されてきた。本発明がその範囲から逸脱することなく関係している代替実施形態が当業者に明らかになるだろう。

前述のことから、本発明は、システム及び方法に明らかであってかつ特有である他の利点とともに、上記の全ての目的及びオブジェクトを実現することにうまく適合している。特定の特徴及びサブコンビネーションは有用であって、他の特徴及びサブコンビネーションを参照することなしに用いることができると理解される。これは、特許請求の範囲内にあると意図されておりかつ実際に特許請求の範囲内にある。

Claims (15)

1. 構造化ストレージが１つまたは複数のテーブルによって表される、構造化ストレージシステム内の１つまたは複数のコンピュータデバイスによって実施される方法であって、各テーブルは複数の行を含み、各行は前記構造化ストレージシステムによって格納されているデータエンティティを表し、前記行を特定するための１つまたは複数のキーを含んでおり、前記複数の行は複数のパーティションの間で分割され、各パーティションは前記テーブル内の前記複数の行からのある範囲の行を含み、前記複数のパーティションは複数のテーブルサーバに格納され、テーブルマスタが前記複数のテーブルサーバへのパーティションの割り当てを制御し、前記方法はパーティションを子パーティションに分割し、
   前記パーティションについての負荷情報に基づいて分割するための前記パーティションを特定することであって、前記負荷情報は、前記パーティションのうちの２又はそれ以上の部分の各々の読み込み及び書き出しの要求を特定する情報を含むことと、
   前記テーブルマスタによって、前記パーティションの前記２又はそれ以上の部分の各々の負荷に基づいて前記パーティションを分割するための分割比を決定することと、
   前記分割比に対応する前記パーティション内の実際の位置を示しているキー情報についてテーブルサーバにクエリを行うことと、
   前記テーブルサーバから前記テーブルマスタにおいてキー情報を受信することであって、前記キー情報は、前記分割比に対応する前記パーティション内の前記実際の位置を示すことと、
   前記テーブルマスタから前記テーブルサーバに分割要求を送信することであって、前記分割要求は、前記キー情報に基づいて前記パーティションを分割するよう指示することと、
   前記キー情報に対応する位置で前記パーティションを分割して前記子パーティションを作成することと、
   前記テーブルマスタに分割の完了を通知することと、
   前記子パーティションに分割されている前記パーティションに基づいてパーティションマップを更新することであって、前記パーティションマップは、前記複数のパーティションと前記複数のパーティションにサービスを提供している前記複数のテーブルサーバとの間のマッピングを格納することと、
   を含むことを特徴とする方法。
2. 前記テーブルマスタにおいて、前記子パーティションのうちの少なくとも１つについてのストリームを構築することをさらに含むことを特徴とする請求項１に記載の方法。
3. 前記パーティションを分割することは、
   前記テーブルサーバから前記パーティションにサービスを提供するのを止めることと、
   前記パーティションから前記子パーティションを構築することと、
   前記テーブルサーバから前記子パーティションをロードしてサービスを提供することを含み、
   前記パーティションにサービスを提供するのを止めることは、前記パーティションのチェックポイントを作成してパーティションの再ロードの間にリプレイされるべきログの量を減らすことであって、前記パーティションの前記チェックポイントを作成することは、アトミックに、新しいログストリームを作成し、前記チェックポイントの後に古いログストリームから新しいログストリームへエクステントをハードリンクし、前記古いログストリームを削除し、前記新しいログストリームの名前を前記古いログストリームの名前に変えることにより、チェックポイントの間にログストリームを効率的に打ち切ること、を含むこと、
   を特徴とする請求項１に記載の方法。
4. 前記パーティションから前記子パーティションを構築することは、費用のかかるデータコピーを行うことなしに、前記パーティションのストリームから、エクステントをアトミックにハードリンクすることによって、前記子パーティションのストリームを効率的に構築することを含むことを特徴とする請求項３に記載の方法。
5. 第２のテーブルサーバに前記子パーティションのうちの少なくとも１つを割り当てることと、パーティションマップを更新して前記子パーティションのうちの少なくとも１つが前記第２のテーブルサーバに位置することを示すことと、
   をさらに含むことを特徴とする請求項１に記載の方法。
6. マージすることによって前記負荷情報に基づく前記パーティションのうちの２つ以上の部分の境界を調整すること、または負荷監視目的のために前記パーティションのうちの２つ以上の部分のうちの少なくとも１つのサブセットを分割すること、をさらに含むことを特徴とする請求項１記載の方法。
7. １つまたは複数のテーブルにより表された構造化ストレージシステムを管理する方法を実行するためのコンピュータ使用可能命令を格納する１つまたは複数のコンピュータ記憶媒体であって、各テーブルは複数の行を含み、各行は前記構造化ストレージシステムによって格納されるデータエンティティを表し、前記行を特定するための１つまたは複数のキーを含んでおり、前記複数の行は複数のパーティションの間で分けられ、各パーティションは前記テーブル内の前記複数の行からの所定の範囲の行を含み、前記複数のパーティションは複数のテーブルサーバに格納され、テーブルマスタは前記複数のテーブルサーバへのパーティション割り当てを制御し、前記方法は、前記テーブルのうちの少なくとも２つのパーティションをマージされたパーティションへとマージする方法であって、
   前記複数のテーブルサーバの前記複数のパーティションについての負荷情報を追跡することであって、前記負荷情報は前記テーブルサーバにおける前記パーティションのそれぞれに対する読み込み及び書き出しの要求を示すことと、
   前記テーブルマスタによって、前記負荷情報に基づいてマージするための前記少なくとも２つのパーティションを特定することと、
   前記テーブルマスタによって、前記マージされたパーティションについてのメタデータストリームを作成するステップと、
   前記少なくとも２つのパーティションにサービスを提供している少なくとも１つのテーブルサーバから前記少なくとも２つのパーティションをアンロードすることと、
   前記テーブルマスタによって、前記マージされたパーティションを前記複数のテーブルサーバから選択されたテーブルサーバに割り当てることと、
   前記選択されたテーブルサーバにおいて前記マージされたパーティションをロードしてサービスを提供することと、
   を含むことを特徴とする１つまたは複数のコンピュータ記憶媒体。
8. 前記少なくとも２つのパーティションは、同じテーブルサーバに格納されることを特徴とする請求項７に記載の１つまたは複数のコンピュータ記憶媒体。
9. 前記選択されたテーブルサーバは、前記少なくとも２つのパーティションのうちの少なくとも１つが、前記マージされたパーティションへとマージされる前に存在していたテーブルサーバを備えることを特徴とする請求項７に記載の１つまたは複数のコンピュータ記憶媒体。
10. 前記マージされたパーティションにマージされている少なくとも２つのパーティションに基づいてパーティションマップを更新することであって、前記パーティションマップは、前記複数のパーティションと前記複数のパーティションにサービスを提供している前記複数のテーブルサーバとの間のマッピングを格納すること、をさらに含むことを特徴とする請求項７に記載の１つまたは複数のコンピュータ記憶媒体。
11. 前記テーブルマスタから前記少なくとも２つのパーティションにサービスを提供している前記少なくとも１つのテーブルサーバにマージを準備せよというメッセージを送信するステップであって、前記マージを準備せよというメッセージは、前記マージされたパーティションについてのロード時間を減らすために、マージする前に、前記少なくとも１つのテーブルサーバに、前記少なくとも２つのパーティションを圧縮させることをさらに含むことを特徴とする請求項７に記載の１つまたは複数のコンピュータ記憶媒体。
12. １つまたは複数のテーブルにより表された構造化ストレージシステムを管理する方法を実行するためのコンピュータ使用可能命令を格納する１つまたは複数のコンピュータ記憶媒体であって、各テーブルは複数の行を含み、各行は前記構造化ストレージシステムによって格納されるデータエンティティを表し、前記行を特定するための１つまたは複数のキーを含んでおり、前記複数の行は複数のパーティションの間で分割され、各パーティションは前記テーブル内の前記複数の行からの行の連続的な範囲を含んでいて、前記複数のパーティションは複数のテーブルサーバに格納され、テーブルマスタが前記複数のテーブルサーバへのパーティションの割り当てを制御し、前記方法は、前記テーブルのパーティションを少なくとも２つの子パーティションに分割し、
    前記複数のテーブルサーバの前記複数のパーティションについての負荷情報を追跡することであって、前記負荷情報は、パーティションの読み込み及び書き出しの要求を含むことと、
    前記テーブルマスタによって、前記負荷情報に基づいて前記パーティションを分割するために特定することであって、前記パーティションについての前記負荷情報は、前記パーティションの異なる部分の異なる負荷を特定することと、
    前記テーブルマスタにおいて、前記パーティションを分割するための分割比を決定することであって、前記分割比は負荷情報に基づいて特定され、前記パーティション内のポイントを表し、前記パーティションにおいて、前記パーティションの第１の部分は第１の負荷の量を含み、前記パーティションの第２の部分は第２の負荷の量を含むことと、
    前記テーブルマスタから前記テーブルサーバに、前記分割比に対応して、前記パーティション内の実際の位置を特定するキー情報の要求を送信することと、
    前記テーブルサーバによって、前記分割比に対応する前記パーティションの前記実際の場所を特定している前記キー情報を決定することと、
    前記テーブルサーバから前記テーブルマスタへ前記キー情報を伝えることと、
    前記テーブルマスタにおいて、前記子パーティションの各々についてのメタデータストリームを構築することと、
    前記テーブルマスタから前記テーブルサーバに分割要求を送信することと、
    前記テーブルサーバにおいて、前記パーティションから前記子パーティションを構築することと、
    前記テーブルサーバにおいて、前記パーティションにサービスを提供するのを止めることと、
    前記テーブルサーバにおいて、前記子パーティションをロードしてサービスを提供することと、
    前記テーブルサーバから前記テーブルマスタへ分割の完了通知を送信することと、
    前記子パーティションに分割されている前記パーティションに基づいてパーティションマップを更新することであって、前記パーティションマップは、前記複数のパーティションと前記複数のパーティションにサービスを提供する前記複数のテーブルサーバとの間のマッピングを格納することと、
    を含むことを特徴とする１つまたは複数のコンピュータ記憶媒体。
13. 前記子パーティションのうちの少なくとも１つを第２のテーブルサーバに割り当てることと、前記パーティションマップを更新して前記子パーティションのうちの少なくとも１つが前記第２のテーブルサーバに位置することを示すことと、をさらに含むことを特徴とする請求項１２に記載の１つまたは複数のコンピュータ記憶媒体。
14. 前記パーティションにサービスを提供するのを止めることは、前記パーティションのチェックポイントを作成してパーティションの再ロードの間にリプレイされるべきログの前記量を減らすことを備え、前記パーティションの前記チェックポイントを作成することは、アトミックに、新しいログストリームを作成し、前記チェックポイントの後に古いログストリームから前記新しいログストリームへエクステントをハードリンクし、前記古いログストリームを削除し、前記新しいログストリームの名前を前記古いログストリームの名前に変えることにより、チェックポイントの間にログストリームを効果的に打ち切ることを含むことを特徴とする請求項１２に記載の１つまたは複数のコンピュータ記憶媒体。
15. 前記パーティションから前記子パーティションを構築することは、費用のかかるデータコピーを行うことなしに、前記パーティションのストリームからエクステントをアトミックにハードリンクすることによって、前記子パーティションのストリームを効率的に構築することを含むことを特徴とする請求項１２に記載の１つまたは複数のコンピュータ記憶媒体。

Images