(57)【要約】  分散データベースシステムにおける分散トランザクションのための方法およびシステムについて記載する。一例は、１つ以上のタブレットレプリカを備えるソースグループに分割点を挿入する要求を識別するステップを含み、各タブレットは、分散データベースシステム内のテーブルからのデータの少なくとも一部を含み、分割点は、ソースグループ内のデータを第１の範囲および第１の範囲とは異なる第２の範囲に分割し、当該一例はさらに、要求に応答して、ソースグループの第１の範囲内のファイル名のリストを、１つ以上のタブレットレプリカを備える第１のターゲットグループに送信するステップと、第１の範囲内のファイル名のリストによって表わされるファイルの仮想コピーを第１のターゲットグループにおいて作成するステップとを含み、仮想コピーは、ファイルのデータを複製することなく、ファイルのデータの各々を新たな名前を用いて利用できるようにする。
2019519025.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上のプロセッサによって実行される、分散データベースシステムにおける分散トランザクションのためのコンピュータによって実行される方法であって、
ソースグループに分割点を挿入する要求を識別するステップを備え、前記ソースグループは、１つ以上のタブレットレプリカを備え、各タブレットは、前記分散データベースシステム内のテーブルからのデータの少なくとも一部を含み、前記分割点は、前記ソースグループ内の前記データを第１の範囲および前記第１の範囲とは異なる第２の範囲に分割し、前記方法はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記ソースグループの前記第１の範囲内のファイル名のリストを第１のターゲットグループに送信するステップを備え、前記第１のターゲットグループは、１つ以上のタブレットレプリカを備え、前記方法はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記第１の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第１のターゲットグループにおいて作成するステップを備え、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルのデータの各々を新たな名前を用いて利用できるようにする、方法。
【請求項２】
前記第１の範囲内の前記ファイルを前記第１のターゲットグループに追加するステップと、
前記第１のターゲットグループが前記ソースグループにおける前記第１の範囲内の前記ファイルにもはや依存していないことを前記ソースグループに知らせるステップと、
前記第１の範囲内の前記ファイルを前記ソースグループから削除するステップとを備える、請求項１に記載の方法。
【請求項３】
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記ソースグループの前記第２の範囲内のファイル名のリストを第２のターゲットグループに送信するステップを備え、前記第２のターゲットグループは、１つ以上のタブレットレプリカを備え、前記方法はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記第２の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第２のターゲットグループにおいて作成するステップを備え、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルの内容の各々を新たな名前の下で利用できるようにする、請求項１に記載の方法。
【請求項４】
前記第１の範囲内のインメモリバッファード更新情報の内容を前記ソースグループから送信するステップと、
前記第１のターゲットグループにおいて、前記ソースグループからの前記第１の範囲内の前記インメモリバッファード更新情報の内容を、前記第１のターゲットグループの前記インメモリバッファード更新情報に追加するステップとを備える、請求項１に記載の方法。
【請求項５】
前記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される、請求項１に記載の方法。
【請求項６】
各グループ内のタブレットの大部分は、前記投票フェーズにおいて前記分散トランザクションが完了するようにコミットしなければならない、請求項５に記載の方法。
【請求項７】
前記投票フェーズにおけるアボートへの投票に応答して、各グループは、前記トランザクションをアンドゥする、請求項５に記載の方法。
【請求項８】
分散データベースにおいて分散トランザクションを実行するためのシステムであって、
データを格納するためのメモリと、
前記メモリにアクセスして動作を実行するように動作可能な１つ以上のプロセッサとを備え、前記動作は、
ソースグループに分割点を挿入する要求を識別するステップを備え、前記ソースグループは、１つ以上のタブレットレプリカを備え、各タブレットは、前記分散データベースシステム内のテーブルからのデータの少なくとも一部を含み、前記分割点は、前記ソースグループ内の前記データを第１の範囲および前記第１の範囲とは異なる第２の範囲に分割し、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記ソースグループの前記第１の範囲内のファイル名のリストを第１のターゲットグループに送信するステップを備え、前記第１のターゲットグループは、１つ以上のタブレットレプリカを備え、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記第１の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第１のターゲットグループにおいて作成するステップを備え、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルのデータの各々を新たな名前を用いて利用できるようにする、システム。
【請求項９】
前記動作は、
前記第１の範囲内の前記ファイルを前記第１のターゲットグループに追加するステップと、
前記第１のターゲットグループが前記ソースグループにおける前記第１の範囲内の前記ファイルにもはや依存していないことを前記ソースグループに知らせるステップと、
前記第１の範囲内の前記ファイルを前記ソースグループから削除するステップとを備える、請求項８に記載のシステム。
【請求項１０】
前記動作は、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記ソースグループの前記第２の範囲内のファイル名のリストを第２のターゲットグループに送信するステップを備え、前記第２のターゲットグループは、１つ以上のタブレットレプリカを備え、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記第２の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第２のターゲットグループにおいて作成するステップを備え、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルの内容の各々を新たな名前の下で利用できるようにする、請求項８に記載のシステム。
【請求項１１】
前記動作は、
前記第１の範囲内のインメモリバッファード更新情報の内容を前記ソースグループから送信するステップと、
前記第１のターゲットグループにおいて、前記ソースグループからの前記第１の範囲内の前記インメモリバッファード更新情報の内容を、前記第１のターゲットグループの前記インメモリバッファード更新情報に追加するステップとを備える、請求項８に記載のシステム。
【請求項１２】
前記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される、請求項８に記載のシステム。
【請求項１３】
各グループ内のタブレットの大部分は、前記分散トランザクションが完了するようにコミットしなければならない、請求項１２に記載のシステム。
【請求項１４】
前記投票フェーズにおけるアボートへの投票に応答して、各グループは、前記トランザクションをアンドゥする、請求項１２に記載のシステム。
【請求項１５】
命令を格納する非一時的なコンピュータ読取可能な媒体であって、前記命令は、実行されたときに、少なくとも１つのプロセッサに、分散データベースにおいて分散トランザクションを実行するための動作を行わせるように動作可能であり、前記動作は、
ソースグループに分割点を挿入する要求を識別するステップを備え、前記ソースグループは、１つ以上のタブレットレプリカを備え、各タブレットは、前記分散データベースシステム内のテーブルからのデータの少なくとも一部を含み、前記分割点は、前記ソースグループ内の前記データを第１の範囲および前記第１の範囲とは異なる第２の範囲に分割し、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記ソースグループの前記第１の範囲内のファイル名のリストを第１のターゲットグループに送信するステップを備え、前記第１のターゲットグループは、１つ以上のタブレットレプリカを備え、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記第１の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第１のターゲットグループにおいて作成するステップを備え、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルのデータの各々を新たな名前を用いて利用できるようにする、コンピュータ読取可能な媒体。
【請求項１６】
前記動作は、
前記第１の範囲内の前記ファイルを前記第１のターゲットグループに追加するステップと、
前記第１のターゲットグループが前記ソースグループにおける前記第１の範囲内の前記ファイルにもはや依存していないことを前記ソースグループに知らせるステップと、
前記第１の範囲内の前記ファイルを前記ソースグループから削除するステップとを備える、請求項１５に記載のコンピュータ読取可能な媒体。
【請求項１７】
前記動作は、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記ソースグループの前記第２の範囲内のファイル名のリストを第２のターゲットグループに送信するステップを備え、前記第２のターゲットグループは、１つ以上のタブレットレプリカを備え、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、前記第２の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第２のターゲットグループにおいて作成するステップを備え、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルの内容の各々を新たな名前の下で利用できるようにする、請求項１５に記載のコンピュータ読取可能な媒体。
【請求項１８】
前記動作は、
前記第１の範囲内のインメモリバッファード更新情報の内容を前記ソースグループから送信するステップと、
前記第１のターゲットグループにおいて、前記ソースグループからの前記第１の範囲内の前記インメモリバッファード更新情報の内容を、前記第１のターゲットグループの前記インメモリバッファード更新情報に追加するステップとを備える、請求項１５に記載のコンピュータ読取可能な媒体。
【請求項１９】
前記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される、請求項１５に記載のコンピュータ読取可能な媒体。
【請求項２０】
各グループ内のタブレットの大部分は、前記分散トランザクションが完了するようにコミットしなければならず、
前記投票フェーズがアボートへの投票を含んでいれば、各グループは、前記トランザクションをアンドゥする、請求項１９に記載のコンピュータ読取可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
背景
本明細書は、一般に、分散データベースシステムにおいて大きなグループを分割することに関する。
【背景技術】
【０００２】
分散データベースにおいてデータを再区分する際、多くの場合、移動させるべきデータの大きな塊がコピーされる。現行の再区分の実施に必要な時間およびリソースは、特に重い書き込み負荷で大きなグループを分割しようとするときに問題を引き起こすことが多く、その結果、サイズ閾値の何倍も大きくなる分割も珍しいことではない。したがって、分散データベースにおいて大きなグループを素早く効率的に分割するための機構が必要になっている。
【発明の概要】
【課題を解決するための手段】
【０００３】
概要
概して、本明細書に記載されている主題の一局面は、分散データベースシステムにおける分散トランザクションのためのアクションを含むシステムおよびデータ処理装置によって実行される方法の状態で実施され得て、上記システムおよび方法は、ソースグループに分割点を挿入する要求を識別するステップを含み、上記ソースグループは、１つ以上のタブレットレプリカを備え、各タブレットは、上記分散データベースシステム内のテーブルからのデータの少なくとも一部を含み、上記分割点は、上記ソースグループ内の上記データを第１の範囲および上記第１の範囲とは異なる第２の範囲に分割し、上記方法はさらに、上記ソースグループに上記分割点を挿入する上記要求に応答して、上記ソースグループの上記第１の範囲内のファイル名のリストを第１のターゲットグループに送信するステップを含み、上記第１のターゲットグループは、１つ以上のタブレットレプリカを備え、上記方法はさらに、上記ソースグループに上記分割点を挿入する上記要求に応答して、上記第１の範囲内の上記ファイル名のリストによって表わされるファイルの仮想コピーを上記第１のターゲットグループにおいて作成するステップを含み、上記仮想コピーは、上記ファイルのデータを複製することなく、上記ファイルの内容の各々を新たな名前の下で利用できるようにする。
【０００４】
上記システムおよび方法はさらに、上記第１の範囲内の上記ファイルを上記第１のターゲットグループに追加するステップと、上記第１のターゲットグループが上記ソースグループにおける上記第１の範囲内の上記ファイルにもはや依存していないことを上記ソースグループに知らせるステップと、上記第１の範囲内の上記ファイルを上記ソースグループから削除するステップとを含み得る。さらに、上記ソースグループに上記分割点を挿入する上記要求に応答して、上記ソースグループの上記第２の範囲内のファイル名のリストを第２のターゲットグループに送信し得て、上記第２のターゲットグループは、１つ以上のタブレットレプリカを含み、上記ソースグループに上記分割点を挿入する上記要求に応答して、上記第２の範囲内の上記ファイル名のリストによって表わされるファイルの仮想コピーを上記第２のターゲットグループにおいて作成し得て、上記仮想コピーは、上記ファイルのデータを複製することなく、上記ファイルの内容の各々を新たな名前の下で利用できるようにする。
【０００５】
また、上記システムおよび方法は、上記第１の範囲内のインメモリバッファード更新情報（in-memory buffered updates）の内容を上記ソースグループから送信するステップと、上記第１のターゲットグループにおいて、上記ソースグループからの上記第１の範囲内の上記インメモリバッファード更新情報の内容を、上記ターゲットグループの上記インメモリバッファード更新情報に追加するステップとを含み得る。
【０００６】
特定の実施形態によれば、上記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される。各グループ内のタブレットの大部分は、上記投票フェーズにおいて上記分散トランザクションが完了するようにコミットしなければならない。上記投票フェーズにおけるアボートへの投票に応答して、各グループは、上記トランザクションをアンドゥする。
【０００７】
本明細書に記載されている主題の１つ以上の実現例の詳細は、添付の図面および以下の説明に記載されている。主題の他の特徴、局面および潜在的利点は、明細書、図面および特許請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【０００８】
【図１】分散ストレージシステムにおいて大きなグループを分割するための例示的な環境の図である。
【図２】分散ストレージシステムにおいて大きなグループを分割するためのプロセスにおける例示的な分散データベースグループの図である。
【図３】分散ストレージシステムにおいて分散トランザクションを連携させるための例示的なプロセスのスイムレーン図である。
【図４】分散ストレージシステムにおいて大きなグループを分割するための例示的なプロセスのフローチャートである。
【図５】本明細書に記載されているシステムおよび方法を実現するために使用され得るコンピューティングデバイスの図である。
【発明を実施するための形態】
【０００９】
さまざまな図の中の同様の参照番号および名称は、同様の要素を示す。
詳細な説明
分散データベースにおいてデータを再区分する際、標準的な実現例では、移動させるべきデータ全体がコピーされる。たとえば、データを分割することまたは複製レベルを変更することは、新たな構成においてデータの全く新しいコピーを作成することを必要とする。本明細書に記載されている実施形態は、可能なときにはいつでもデータのオンディスクコピーを共有することによってこの余分なコピーを回避するための機構を提供する。たとえば、データを分割する際、２つのパーティションの新たなコピーを作成するのではなく、既存のパーティションを２つの別々の部分として使用できるようにする既存のパーティションの仮想ビューが提供されてもよい。データの新たなコピーが作成されるときだけ、たとえばデータをよりコンパクトな形式に書き換えるとき（すなわち、「圧縮」時）だけ、仮想コピーをデータの実際のコピーに分解する必要がある。特定の実施形態によれば、データベースは、グループに区分され、各グループは、複製されたタブレットセットである。タブレットは、レイヤとも呼ばれる変更不可ファイルのリストと、バッファード更新情報のインメモリ表現とを含む。グループは、２つ以上のグループに分割されてもよく、２つ以上のグループが併合されてもよく、またはあるグループから異なる複製構成を有する別のグループに（たとえば、米国内のみのタブレットを有するグループから欧州内のみのタブレットを有するグループに）データを移動させてもよい。
【００１０】
本明細書に記載されている実施形態は、複製されたパーティション間でデータをさらに効率的に移動させることを可能にする。複製されたパーティションは、グループであり、各グループは、１つ以上のタブレットで構成され、当該１つ以上のタブレットの各々は、データのコピーを保持する。各タブレットは、厳密に１つのサーバによって提供されてもよい。タブレットは、行空間または行のシーケンスの複数のパーティションを封入し得るコンテナであってもよいデータ構造である。データは、たとえばあるグループから２つの新たなグループに移動することによって、ある分割点において分割可能である。第１のグループは、データの範囲の（すなわち、分割点までの）下方部分を受信し得て、第２のグループは、データの範囲の後半部分を受信し得て、当該範囲は、ソースグループから除去され得る。同様に、データは、２つのソースグループから１つのターゲットグループに移動することによって併合可能である。データの移動は、全てのタブレットにおいて実質的に同時に行われなければならない。そうするために、システムは、たとえば、ソースグループと、ターゲットグループと、範囲をグループにマッピングするメタデータを含むシステムテーブルとを含む分散トランザクションをコミットする。この分散トランザクションは、当該移動を記述し、分割点およびどの範囲がどのターゲットに行くかを含む。各グループは、トランザクションを複製し、これは、各タブレットがトランザクションを適用することを保証する。ソースタブレットは、トランザクションを適用すると、現在の内容のスナップショットを取ってそれを保存する。ターゲットタブレットは、トランザクションを適用すると、移動させるべき範囲を転送するようにソースタブレットに連絡する。タブレットの状態は、クラスタファイルシステムに格納される変更不可ファイルと、バッファード更新情報のインメモリ状態とに分割される。ソースタブレットは、スナップショット内の全てのファイル名のリストおよび転送すべき範囲に分類される全てのインメモリ更新情報の内容を送信することによって、範囲をターゲットタブレットに転送する。ターゲットタブレットは、内容をインメモリバッファード更新情報に追加し、全てのファイルのスナップショットを作成し、要求される範囲にファイル内容を限定するフィルタで包まれた状態で、スナップショットを作成されたファイルを内容に追加する。これらのスナップショットは、元になるデータを複製する必要なしにファイルの内容を新たな名前の下で利用できるようにすることによって、シンボリックリンクと同様である。インメモリバッファード更新情報からのデータは、たとえば伝送制御プロトコル（transmission control protocol：ＴＣＰ）接続を介してグループ間でストリーミングされ得る。次いで、ターゲットグループは、ターゲットグループがソースファイルをもはや必要としておらず、ソースグループがそれらのファイルを削除してもよいということをソースグループに知らせる。一般に、ソースグループは、次の周期的圧縮時にファイルを書き換えるときにファイルを削除する。
【００１１】
本明細書に記載されている技術は、以下の利点を提供することができる。たとえば、このアプローチにより、時間の点でも空間の点でもさらに効率的に分割を行うことが可能になり、基準の種類が多くなる結果としてさらに頻繁にデータを再区分することが可能になる。たとえば、オーバーロードパーティションは、素早く効率的に分割され得る。
【００１２】
したがって、本開示には、分散ストレージシステムにおいて大きなグループを分割するための技術が記載されている。分散データベースシステムにおける分散トランザクションのための１つの例示的な方法は、ソースグループに分割点を挿入する要求を識別するステップを含み、上記ソースグループは、１つ以上のタブレットレプリカを含み、各タブレットは、上記分散データベースシステム内のテーブルからのデータの少なくとも一部を含み、上記分割点は、上記ソースグループ内の上記データを第１の範囲および上記第１の範囲とは異なる第２の範囲に分割する。上記ソースグループに上記分割点を挿入する上記要求に応答して、上記ソースグループの上記第１の範囲内のファイル名のリストを第１のターゲットグループに送信し、上記第１のターゲットグループは、１つ以上のタブレットレプリカを含む。上記第１の範囲内の上記ファイル名のリストによって表わされるファイルの仮想コピーを上記第１のターゲットグループにおいて作成し、上記仮想コピーは、上記ファイルのデータを複製することなく、上記ファイルのデータの各々を新たな名前の下で利用できるようにする。
【００１３】
上記第１の範囲内の上記ファイルを上記第１のターゲットグループに追加し得て、上記第１のターゲットグループが上記ソースグループにおける上記第１の範囲内の上記ファイルにもはや依存していないことを上記ソースグループに知らせ得る。これに応答して、上記第１の範囲内の上記ファイルを上記ソースグループから削除し得る。さらに、上記ソースグループに上記分割点を挿入する上記要求に応答して、上記ソースグループの上記第２の範囲内のファイル名のリストを第２のターゲットグループに送信し得て、上記第２のターゲットグループは、１つ以上のタブレットレプリカを含む。また、上記第２の範囲内の上記ファイル名のリストによって表わされるファイルの仮想コピーを上記第２のターゲットグループにおいて作成し得て、上記仮想コピーは、上記ファイルのデータを複製することなく、上記ファイルの内容の各々を新たな名前の下で利用できるようにする。さらに、上記第１の範囲内のインメモリバッファード更新情報の内容を上記ソースグループから送信し、上記第１のターゲットグループにおいて、上記ターゲットグループの上記インメモリバッファード更新情報に追加し得る。
【００１４】
特定の実施形態によれば、上記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される。各グループ内のタブレットの大部分は、上記投票フェーズにおいて上記分散トランザクションが完了するようにコミットしなければならない。一方、上記投票フェーズにおけるアボートへの投票に応答して、各グループは、上記トランザクションをアンドゥする。
【００１５】
概して、本発明の実施形態によれば、分割点の挿入または除去に関連付けられたデータの移動は、ソースグループとターゲットグループとをパティシパントとして含むトランザクションによって実行される。トランザクションは、新たなデータ場所を反映するための適切なメタデータテーブルを更新し得て、分割点を更新し得て、移動を反映するためのソースグループおよび送信先グループにおける分割点のメタデータテーブルを更新し得る。トランザクションは、移動させるべきユーザデータの範囲および適用すべき任意の分割オフセットを指定するソースグループおよびターゲットグループのための範囲データも含み得る。ソースグループのソースタブレットは、範囲データを適用すると、現在のレイヤスタックを保存し、それをターゲットグループのターゲットタブレットに提供するように準備し得る。ターゲットタブレットは、同一ゾーン内のソースタブレットからこれらのレイヤを検索し得て、ゾーンは、管理デプロイメントの単位である。ゾーンセットは、データを複製することができる場所セットであってもよい。ゾーンは、それぞれ新たなデータセンタの利用が開始されるときおよび古いデータセンタがオフにされるときに、稼働中のシステムに追加されたり、稼働中のシステムから除去されたりし得る。たとえば異なるアプリケーションのデータを同一データセンタ内の異なるサーバセットに区分しなければならない場合、データセンタには１つ以上のゾーンがあってもよい。ターゲットタブレットがソースタブレットの現在のレイヤスタックを検索した後、鍵から値への永続的な順序付けられた変更不可マップであるテーブルのレイヤのスナップショットがターゲットタブレットによって作成され得る。それらの移動されたレイヤを同期分解するのではなく、ターゲットタブレットは、移動させるべき範囲を指定する適用ループに１つ以上のプロキシレイヤを挿入し得る。これらのプロキシレイヤは、移動されているがまだ分解されていない範囲の読み取りを失敗させ得て、再試行可能なエラーを返す。このように、ターゲットタブレットは、移動された範囲をバックグラウンドにおいて分解しながら適用ループを継続し得る。ソースグループの削除は、ソースグループを削除する前に、移動されているがまだターゲットグループによって解放されていない全ての範囲の内容をターゲットグループ内の複製されたテーブルに書き込むことによって実現することができ、これにより、たとえターゲットグループのいくつかのタブレットが利用できなくても、ソースグループがソースグループ自体を削除することが可能になり得る。この例は、ある分割点の挿入または除去に関連して記載されているが、同一のシステムおよび方法は、多くの分割点の挿入または除去にも適用される。
【００１６】
図１は、分散ストレージシステムにおいて大きなグループを分割するための例示的な環境１００の図である。示されているように、環境１００は、分散ストレージシステム１１０を含み、分散ストレージシステム１１０は、各々が複数のデータグループ１１４を管理する複数のサーバ１１２を含む。動作時、クライアント１２０は、要求１２２を分散ストレージシステム１１０に送信し得る。分散ストレージシステム１１０は、要求１２２を処理し得て、応答１２４をクライアント１２０に送信し得る。
【００１７】
分散ストレージシステム１１０は、ローカルまたはプライベートネットワーク（図示せず）によって接続された複数のサーバ１１２を含む分散システムであってもよい。一部の例では、ローカルまたはプライベートネットワークは、完全に単一の施設内に位置していてもよいが、他の例では、ローカルまたはプライベートネットワークは、大きな領域をカバーして複数の施設を相互接続してもよい。サーバ１１２は、クライアント１２０が要求したときにデータを格納、検索および更新することによってクライアント要求１２２を提供する目的で、互いに通信し得る。場合によっては、分散ストレージシステム１１０は、分散データベースであってもよく、分散ファイルシステムであってもよく、または他のタイプの分散ストレージであってもよい。分散ストレージシステム１１０は、システム内のサーバ１１２の動作を管理して取りまとめるための構成要素も含んでもよい。
【００１８】
分散ストレージシステム１１０において、各サーバ１１２は、プロセッサと、分散ストレージシステム１１０によって管理されるデータを格納するためのハードドライブなどのストレージデバイスとを含むコンピューティングデバイスであってもよい。場合によっては、データは、分散ポリシーに従ってさまざまなサーバ１１２に分散されてもよい。たとえば、分散ポリシーは、冗長性を維持するために分散ストレージシステム１１０内の特定のテーブルまたはファイルを特定のいくつかのサーバ１１２に格納しなければならないことを規定し得る。また、分散ポリシーは、たとえば地理的冗長性を維持するためにデータを複数の異なる場所に格納しなければならないことも規定し得る。場合によっては、サーバ１１２は、直接接続された永続性ストレージの代わりに、分散ファイルシステムなどの外部ストレージデバイスまたはシステムを利用してもよい。
【００１９】
各サーバ１１２は、１つ以上のデータグループ１１４を管理し得る。データグループ１１４は、分散ストレージシステム１１０によって管理されるデータセット全体の一部を含み得る。各データグループ１１４は、分散データベース内のテーブルの一部からのデータ、分散ファイルシステムからの１つ以上のファイル、または分散ストレージシステム１１０内のデータの他のパーティションを含み得る。動作時、各要求１２２が分散ストレージシステム１１０によって分析されて、当該要求が関係する特定のデータグループ１１４を要求ターゲットに基づいて判断し得る。次いで、分散ストレージシステムは、特定のデータグループ１１４を管理する特定のサーバ１１２に当該要求をルーティングし得る。
【００２０】
場合によっては、クライアント１２０は、分散ストレージシステム１１０のユーザであってもよい。また、クライアント１２０は、分散ストレージシステム１１０を使用してデータを格納および検索するエンティティ（たとえば、ウェブサイトまたはアプリケーション）であってもよい。各クライアント１２０は、各クライアント１２０が分散ストレージシステム１１０に送信する各要求１２２についての情報を記録し得る。場合によっては、各クライアント１２０は、分散ストレージシステム１１０に送信される要求全体の記録を格納してもよい。また、各クライアントは、たとえば同一の要求パラメータセットで送信される要求の総数を格納するなど、分散ストレージシステムに送信される要求１２２の概要も格納してもよい。
【００２１】
図２は、分散ストレージシステムにおいて大きなグループを分割するためのプロセスにおける例示的な分散データベース２００グループの図である。たとえば特定のグループに格納されるデータが大きくなり過ぎると、データを２つ以上の範囲に分割するために新たな分割点がグループに追加され得る。グループ２１０は、１つ以上のタブレット２１２〜２１６を含み得て、グループ２１０内のタブレット２１２〜２１６は、互いのレプリカ、すなわちタブレットレプリカであってもよい。グループ２１０にエラーが無い場合、グループ２１０内の全てのタブレット２１２〜２１６は同一である。各グループ２１０は、当該グループのリーダとして選択されているリーダタブレットを含み得る。リーダタブレットは、マスタコピーと同様に、当該グループ内のデータのための権限者の役割を果たし、当該リーダが応答することを停止すると、別のタブレットがリーダタブレットとして選択される。
【００２２】
鍵空間における分割点は、グループ間の境界を決定し、ひいてはデータの負荷またはバイトの分散を決定する。動作効率のためには、１つのシャードに多過ぎる読み書きを実行させることは望ましくない。したがって、分散ポリシーは、各グループにおける記録の数または各グループについてのデータもしくはＣＰＵ負荷利用のサイズに対する限界値を含み得る。データのリバランシングに対処するために、分割点は必要に応じて定期的に追加されたり除去されたりしてもよい。
【００２３】
たとえば、図２に示されるように、分割点２２５がソースグループ２２０に追加されると、ターゲットグループ２３０は、分割点２２５までのデータを含む第１の範囲をソースグループ２２０から割り当てられ得る。いくつかの実施形態では、分割点２２５以降のデータの後半部分を含む第２の範囲は、ソースグループ２２０に割り当てられたままである場合もあれば、異なるターゲットグループ２４０に割り当てられる場合もある。
【００２４】
図３は、分散ストレージシステムにおいて分散トランザクションを連携させるための例示的なプロセス３００のスイムレーン図である。図３に示されるように、連携は、投票フェーズとコミットフェーズとを含む２フェーズコミットプロトコルによって実現される。２フェーズコミットプロトコルは、総意によってトランザクションをコミットするかアボートするかに関して分散トランザクションに参加する全てのプロセスを連携させるタイプのアトミックコミットメントプロトコルである。障害が発生しなければ、プロトコルの２つのフェーズは以下の説明に従って進む。
【００２５】
まず、投票フェーズは、トランザクションの全ての参加しているプロセス（すなわち、パティシパント）を準備してトランザクションをコミットまたはアボートするために必要な手段を取り、たとえばパティシパントのローカル部分の実行が適切に終了した場合にはコミットに投票し、たとえばローカル部分で問題が検出された場合にはアボートに投票する試みをコーディネータが処理するフェーズである。たとえば、トランザクションにおける１つのグループがコーディネータ３２０として選択されてもよく、トランザクションにおける残りのグループがパティシパント３３０であってもよい。２つの異なるグループ間のトランザクションにおいて、各グループ内のタブレットの大部分はコミットに同意しなければならないため、これらのグループは両方ともコミットに投票する。
【００２６】
次に、コミットフェーズは、パティシパント３３０の投票に基づいて、全てのパティシパント３３０がコミットに投票した場合にはコミットし、そうでない場合にはトランザクションをアボートすることをコーディネータ３２０が決定するフェーズである。コーディネータ３２０は、結果を全てのパティシパント３３０に通知し、次いで、パティシパント３３０は、ローカルトランザクションリソース（たとえば、データベースデータ）を用いて、コミットまたはアボートするための必要なアクションを進める。
【００２７】
投票フェーズにおいて、コーディネータ３２０は、コミットクエリメッセージ３０５を全てのパティシパント３３０に送信し、コーディネータ３２０は、全てのパティシパント３３０から回答を受信するまで待機する。パティシパント３３０は、コミットする準備をするか障害が発生するとアボートするかして（３１５）、コミットすることを求められる時点までトランザクションを実行する。各パティシパントは、パティシパントのアクションが成功した場合には同意メッセージ３２５、すなわちコミットへの投票で回答し、パティシパントがコミットを不可能にする障害に遭遇した場合にはアボートメッセージ、すなわちアボートへの投票で回答する。
【００２８】
コミットフェーズでは、コーディネータ３２０は、各パティシパント３３０からの投票に応答して、コミットするかアボートするか（３３５）を判断する。コーディネータ３２０が投票フェーズ中に全てのパティシパント３３０から同意メッセージを受信すると、コーディネータ３２０は、コミットメッセージ３４５を全てのパティシパント３３０に送信する。各パティシパント３３０は、動作を完了し（３５５）、トランザクション中に保持されていた全てのロックおよびリソースを解放し、通知３６５をコーディネータ３２０に送信する。全ての通知が受信されると、コーディネータ３２０はトランザクションを完了し、プロセスは終了する（３７５）。投票フェーズ中にいずれかのパティシパント３３０がアボートに投票する（３２５）か、またはコーディネータ３２０のタイムアウトが切れると、コーディネータ３２０は、ロールバックメッセージ３４５を全てのパティシパント３３０に送信する。各パティシパント３３０は、トランザクションをアンドゥし（３５５）、トランザクション中に保持されていたリソースおよびロックを解放し、通知３６５をコーディネータ３２０に送信する。全ての通知が受信されると、コーディネータ３２０はトランザクションをアンドゥし、プロセスは終了する（３７５）。
【００２９】
図４は、分散ストレージシステムにおいて大きなグループを分割するための例示的なプロセス４００のフローチャートである。４０５において、ソースグループに分割点を挿入する要求を識別する。ソースグループは、１つ以上のタブレットレプリカを含み得て、各タブレットは、分散データベースシステム内のテーブルからのデータの少なくとも一部を含む。分割点は、ソースグループ内のデータを第１の範囲および第１の範囲とは異なる第２の範囲に分割し得る。ソースグループに分割点を挿入する要求に応答して、４１０において、ソースグループの第１の範囲内のファイル名のリストを第１のターゲットグループに送信し得る。第１のターゲットグループは、１つ以上のタブレットレプリカを含み得る。この例は分割点を挿入または除去することに関連して記載されているが、同じシステムおよび方法は、多くの分割点を同時にまたは実質的に同時に挿入または除去することにも適用される。
【００３０】
４１５において、第１の範囲内のファイル名のリストによって表わされるファイルの仮想コピーを第１のターゲットグループにおいて作成し得る。仮想コピーまたはスナップショットは、シンボリックリンクと同様である。なぜなら、仮想コピーまたは参照ファイルは、ファイルの元になるデータの複製を必要とすることなく、ファイルの内容の各々を新たな名前の下で利用できるようにするからである。
【００３１】
４２０において、第１の範囲内のインメモリバッファード更新情報の内容をソースグループから第１のターゲットグループに送信し得る。さらに、ソースグループからの第１の範囲内のインメモリバッファード更新情報の内容を、第１のターゲットグループのインメモリバッファード更新情報に追加し得る。
【００３２】
４２５において、第１の範囲内のファイルを第１のターゲットグループに追加し得て、第１のターゲットグループがソースグループにおける第１の範囲内のファイルにもはや依存していないことをソースグループに知らせ得る。これに応答して、第１の範囲内のファイルをソースグループから削除し得る。たとえば、ソースグループは、ソースグループが次の周期的圧縮時にファイルを書き換えるときに第１の範囲内のファイルを削除してもよい。
【００３３】
特定の実施形態では、プロセスは、ソースグループに分割点を挿入する要求に応答して、ソースグループの第２の範囲内のファイル名のリストを第２のターゲットグループに送信することをさらに含み得て、第２のターゲットグループは、１つ以上のタブレットレプリカを含む。また、第２の範囲内のファイル名のリストによって表わされるファイルの仮想コピーを第２のターゲットグループにおいて作成し得て、仮想コピーは、ファイルのデータを複製することなくファイルの内容の各々を新たな名前の下で利用できるようにする。特定の実施形態によれば、分散トランザクションのプロセスは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される。各グループ内のタブレットの大部分は、投票フェーズにおいて分散トランザクションが完了するようにコミットしなければならない。一方、投票フェーズにおけるアボートへの投票に応答して、各グループはトランザクションをアンドゥする。
【００３４】
図５は、本明細書に記載されているシステムおよび方法を実現するためにクライアントまたは単一のサーバもしくは複数のサーバのいずれかとして使用され得るコンピューティングデバイス５００，５５０のブロック図である。コンピューティングデバイス５００は、ラップトップ、デスクトップ、ワークステーション、パーソナルデジタルアシスタント、サーバ、ブレードサーバ、メインフレームおよび他の適切なコンピュータなどのさまざまな形態のデジタルコンピュータを表わすよう意図されている。コンピューティングデバイス５５０は、パーソナルデジタルアシスタント、携帯電話、スマートフォンおよび他の同様のコンピューティングデバイスなどのさまざまな形態のモバイル機器を表わすよう意図されている。さらに、コンピューティングデバイス５００または５５０は、ユニバーサルシリアルバス（Universal Serial Bus：ＵＳＢ）フラッシュドライブを含んでもよい。ＵＳＢフラッシュドライブは、オペレーティングシステムおよび他のアプリケーションを格納し得る。ＵＳＢフラッシュドライブは、別のコンピューティングデバイスのＵＳＢポートに挿入することができる無線送信機またはＵＳＢコネクタなどの入出力コンポーネントを含んでもよい。ここに示されているコンポーネント、それらの接続および関係、ならびにそれらの機能は、単なる例示であるよう意図されており、本明細書に記載されているおよび／または本明細書にクレームされている発明の実現例を限定することを意図したものではない。
【００３５】
コンピューティングデバイス５００は、プロセッサ５０２と、メモリ５０４と、ストレージデバイス５０６と、メモリ５０４および高速拡張ポート５１０に接続する高速インターフェイス５０８と、低速バス５１４およびストレージデバイス５０６に接続する低速インターフェイス５１２とを含む。コンポーネント５０２，５０４，５０６，５０８，５１０および５１２の各々は、さまざまなバスを用いて相互接続され、共通のマザーボード上に搭載される場合もあれば、適宜他の態様で搭載される場合もある。プロセッサ５０２は、コンピューティングデバイス５００内で実行するために命令を処理し得て、当該命令は、高速インターフェイス５０８に結合されたディスプレイ５１６などの外部入出力デバイス上にＧＵＩのためのグラフィック情報を表示するための、メモリ５０４内またはストレージデバイス５０６上に格納された命令を含む。他の実現例では、複数のメモリおよび複数タイプのメモリとともに、複数のプロセッサおよび／または複数のバスが適宜使用されてもよい。また、複数のコンピューティングデバイス５００が接続されてもよく、各デバイスは、（たとえば、サーババンク、ブレードサーバのグループ、またはマルチプロセッサシステムとして）必要な動作の一部を提供する。
【００３６】
メモリ５０４は、コンピューティングデバイス５００内の情報を格納する。一実現例では、メモリ５０４は、単一の揮発性メモリユニットまたは複数の揮発性メモリユニットである。別の実現例では、メモリ５０４は、単一の不揮発性メモリユニットまたは複数の不揮発性メモリユニットである。また、メモリ５０４は、磁気ディスクまたは光ディスクなどの別の形態のコンピュータ読取可能な媒体であってもよい。
【００３７】
ストレージデバイス５０６は、コンピューティングデバイス５００に大容量ストレージを提供することができる。一実現例では、ストレージデバイス５０６は、フロッピー（登録商標）ディスクデバイス、ハードディスクデバイス、光ディスクデバイス、テープデバイス、フラッシュメモリもしくは他の同様のソリッドステートメモリデバイス、または、ストレージエリアネットワークもしくは他の構成内のデバイスを含むデバイスのアレイなどのコンピュータ読取可能な媒体であってもよく、またはコンピュータ読取可能な媒体を含んでもよい。コンピュータプログラム製品は、情報担体内で有形に実施され得る。コンピュータプログラム製品は、実行されたときに上記の方法などの１つ以上の方法を実行する命令も含んでもよい。情報担体は、メモリ５０４、ストレージデバイス５０６またはメモリオンプロセッサ５０２などのコンピュータまたは機械読取可能な媒体である。
【００３８】
高速コントローラ５０８は、コンピューティングデバイス５００のための帯域幅を多く使用する動作を管理するのに対して、低速コントローラ５１２は、帯域幅をそれほど使用しない動作を管理する。このような機能の割り当ては、例示に過ぎない。一実現例では、高速コントローラ５０８は、メモリ５０４、ディスプレイ５１６（たとえば、グラフィックスプロセッサまたは加速装置を介して）、および高速拡張ポート５１０に結合され、高速拡張ポート５１０は、さまざまな拡張カード（図示せず）を受け付け得る。当該実現例では、低速コントローラ５１２は、ストレージデバイス５０６および低速拡張ポート５１４に結合される。さまざまな通信ポート（たとえば、ＵＳＢ、ブルートゥース（登録商標）、イーサネット（登録商標）、ワイヤレスイーサネット）を含み得る低速拡張ポートは、たとえばネットワークアダプタを介して、キーボード、ポインティングデバイス、スキャナ、またはスイッチもしくはルータなどのネットワーキングデバイスなどの１つ以上の入出力デバイスに結合されてもよい。
【００３９】
コンピューティングデバイス５００は、図に示されるように複数の異なる形態で実現されてもよい。たとえば、コンピューティングデバイス５００は、標準的なサーバ５２０として実現されてもよく、またはこのようなサーバのグループの状態で複数回実現されてもよい。また、コンピューティングデバイス５００は、ラックサーバシステム５２４の一部として実現されてもよい。また、コンピューティングデバイス５００は、ラップトップコンピュータ５２２などのパーソナルコンピュータとして実現されてもよい。代替的に、コンピューティングデバイス５００からのコンポーネントは、デバイス５５０などのモバイルデバイス（図示せず）内の他のコンポーネントと組み合わせられてもよい。このようなデバイスの各々は、コンピューティングデバイス５００，５５０のうちの１つ以上を含んでもよく、システム全体が、互いに通信する複数のコンピューティングデバイス５００，５５０で構成されてもよい。
【００４０】
コンピューティングデバイス５５０は、いくつかあるコンポーネントの中で特に、プロセッサ５５２と、メモリ５６４と、ディスプレイ５５４などの入出力デバイスと、通信インターフェイス５６６と、送受信機５６８とを含む。デバイス５５０は、さらなるストレージを提供するためにマイクロドライブまたは他のデバイスなどのストレージデバイスも備えていてもよい。コンポーネント５５０，５５２，５６４，５５４，５６６および５６８の各々は、さまざまなバスを使用して相互接続され、コンポーネントのうちのいくつかは、共通のマザーボード上に搭載される場合もあれば、適宜他の態様で搭載される場合もある。
【００４１】
プロセッサ５５２は、メモリ５６４に格納された命令を含む命令をコンピューティングデバイス５５０内で実行することができる。プロセッサは、別々の複数のアナログプロセッサおよびデジタルプロセッサを含むチップのチップセットとして実現されてもよい。さらに、プロセッサは、複数のアーキテクチャのうちのいずれかを用いて実現されてもよい。たとえば、プロセッサ５１０は、ＣＩＳＣ（Complex Instruction Set Computers：複合命令セットコンピュータ）プロセッサ、ＲＩＳＣ（Reduced Instruction Set Computer：縮小命令セットコンピュータ）プロセッサ、またはＭＩＳＣ（Minimal Instruction Set Computer：最小命令セットコンピュータ）プロセッサであってもよい。プロセッサは、たとえば、ユーザインターフェイスの制御、デバイス５５０によって実行されるアプリケーション、およびデバイス５５０による無線通信などの、デバイス５５０の他のコンポーネントの連携を提供してもよい。
【００４２】
プロセッサ５５２は、ディスプレイ５５４に結合された制御インターフェイス５５８およびディスプレイインターフェイス５５６を介してユーザと通信し得る。ディスプレイ５５４は、たとえばＴＦＴ（Thin-Film-Transistor Liquid Crystal Display：薄膜トランジスタ液晶ディスプレイ）ディスプレイもしくはＯＬＥＤ（Organic Light Emitting Diode：有機発光ダイオード）ディスプレイ、または他の適切なディスプレイ技術であってもよい。ディスプレイインターフェイス５５６は、ディスプレイ５５４を駆動してグラフィック情報および他の情報をユーザに提示するための適切な回路を備え得る。制御インターフェイス５５８は、ユーザからコマンドを受信し、当該コマンドを変換してプロセッサ５５２に送信し得る。また、デバイス５５０と他のデバイスとの近接エリア通信を可能にするために、外部インターフェイス５６２がプロセッサ５５２と通信するように設けられてもよい。外部インターフェイス５６２は、たとえば、いくつかの実現例では有線通信を提供してもよく、または他の実現例では無線通信を提供してもよく、複数のインターフェイスも使用してもよい。
【００４３】
メモリ５６４は、コンピューティングデバイス５５０内の情報を格納する。メモリ５６４は、コンピュータ読取可能な媒体、揮発性メモリユニットまたは不揮発性メモリユニットのうちの１つ以上として実現されてもよい。また、拡張メモリ５７４が設けられて、拡張インターフェイス５７２を介してデバイス５５０に接続されてもよく、拡張インターフェイス５７２は、たとえばＳＩＭＭ（Single In Line Memory Module：シングル・インライン・メモリ・モジュール）カードインターフェイスを含み得る。このような拡張メモリ５７４は、デバイス５５０に対して追加の記憶領域を提供してもよく、またはデバイス５５０のためにアプリケーションもしくは他の情報を格納してもよい。具体的には、拡張メモリ５７４は、上記のプロセスを実行または補完するための命令を含んでもよく、セキュリティ保護された情報も含んでもよい。したがって、たとえば、拡張メモリ５７４は、デバイス５５０のためのセキュリティモジュールとして提供されてもよく、デバイス５５０の安全な使用を可能にする命令でプログラムされてもよい。また、ハッキングできない態様でＳＩＭＭカードに識別情報を載せるなど、追加情報とともに、セキュリティ保護されたアプリケーションがＳＩＭＭカードを介して提供されてもよい。
【００４４】
以下に記載するように、メモリは、たとえばフラッシュメモリおよび／またはＮＶＲＡＭメモリを含んでもよい。一実現例では、コンピュータプログラム製品は、情報担体内で有形に実施される。コンピュータプログラム製品は、実行されたときに上記の方法などの１つ以上の方法を実行する命令を含む。情報担体は、たとえば送受信機５６８または外部インターフェイス５６２の上方に受けられ得るメモリ５６４、拡張メモリ５７４またはメモリオンプロセッサ５５２などのコンピュータまたは機械読取可能な媒体である。
【００４５】
デバイス５５０は、必要に応じてデジタル信号処理回路を含み得る通信インターフェイス５６６を介して無線通信してもよい。通信インターフェイス５６６は、とりわけＧＳＭ（登録商標）音声電話、ＳＭＳ、ＥＭＳもしくはＭＭＳメッセージング、ＣＤＭＡ、ＴＤＭＡ、ＰＤＣ、ＷＣＤＭＡ（登録商標）、ＣＤＭＡ２０００またはＧＰＲＳなどのさまざまなモードまたはプロトコルの下での通信を提供し得る。このような通信は、たとえば無線周波数送受信機５６８を介して行われてもよい。また、ブルートゥース、ＷｉＦｉまたは他のこのような送受信機（図示せず）などを用いて狭域通信が行われてもよい。また、ＧＰＳ（グローバルポジショニングシステム）受信機モジュール５７０は、さらなるナビゲーションおよび位置関連の無線データをデバイス５５０に提供し得て、当該データは、デバイス５５０上で実行されるアプリケーションによって適宜使用され得る。
【００４６】
また、デバイス５５０は、音声コーデック５６０を用いて可聴に通信してもよく、音声コーデック５６０は、音声情報をユーザから受信し、当該音声情報を使用可能なデジタル情報に変換し得る。さらに、音声コーデック５６０は、話者を介するなどして、たとえばデバイス５５０の受話器においてユーザのために可聴音を生成し得る。このような音は、音声電話からの音声を含んでもよく、記録された音（たとえば、音声メッセージ、音楽ファイルなど）を含んでもよく、デバイス５５０上で動作するアプリケーションによって生成された音も含んでもよい。
【００４７】
コンピューティングデバイス５５０は、図に示されるように複数の異なる形態で実現されてもよい。たとえば、コンピューティングデバイス５５０は、携帯電話５８０として実現されてもよい。また、コンピューティングデバイス５５０は、スマートフォン５８２、パーソナルデジタルアシスタントまたは他の同様のモバイルデバイスの一部として実現されてもよい。
【００４８】
本明細書に記載されているシステムおよび技術のさまざまな実現例は、デジタル電子回路、集積回路、特別に設計されたＡＳＩＣ（特定用途向け集積回路）、コンピュータハードウェア、ファームウェア、ソフトウェア、および／または、それらの組み合わせで実現されてもよい。これらのさまざまな実現例は、プログラム可能なシステム上で実行可能および／または解釈可能である１つ以上のコンピュータプログラムでの実現例を含み得て、当該プログラム可能なシステムは、少なくとも１つのプログラム可能なプロセッサと、少なくとも１つの入力デバイスと、少なくとも１つの出力デバイスとを含み、当該少なくとも１つのプログラム可能なプロセッサは、ストレージシステムとデータおよび命令を送受信するように結合された特殊目的または汎用プロセッサであってもよい。
【００４９】
これらのコンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーションまたはコードとしても知られている）は、プログラム可能なプロセッサのための機械命令を含み、高水準手続き型および／もしくはオブジェクト指向プログラミング言語で実現されてもよく、ならびに／またはアセンブリ／機械言語で実現されてもよい。本明細書で使用される「機械読取可能な媒体」および「コンピュータ読取可能な媒体」という用語は、機械読取可能な信号として機械命令を受信する機械読取可能な媒体を含む、機械命令および／またはデータをプログラム可能なプロセッサに提供するために使用される任意のコンピュータプログラム製品、装置および／またはデバイス（たとえば、磁気ディスク、光ディスク、メモリ、プログラマブルロジックデバイス（Programmable Logic Device：ＰＬＤ））を指す。「機械読取可能な信号」という用語は、機械命令および／またはデータをプログラム可能なプロセッサに提供するために使用される任意の信号を指す。
【００５０】
ユーザとの対話を提供するために、本明細書に記載されているシステムおよび技術は、コンピュータ上で実現されてもよく、当該コンピュータは、ユーザに対して情報を表示するためのディスプレイデバイス（たとえば、ＣＲＴ（cathode ray tube：陰極線管）またはＬＣＤ（liquid crystal display：液晶ディスプレイ）モニタ）と、キーボードと、ユーザが入力をコンピュータに提供することができるポインティングデバイス（たとえば、マウスまたはトラックボール）とを有する。ユーザとの対話を提供するために他の種類のデバイスも使用されてもよい。たとえば、ユーザに提供されるフィードバックは、任意の形態の感覚フィードバック（たとえば、視覚フィードバック、聴覚フィードバックまたは触覚フィードバック）であってもよく、ユーザからの入力は、音響入力、音声入力または触知可能入力を含む任意の形態で受信されてもよい。
【００５１】
本明細書に記載されているシステムおよび技術は、バックエンドコンポーネント（たとえば、データサーバ）を含むコンピューティングシステムで実現されてもよく、またはミドルウェアコンポーネント（たとえば、アプリケーションサーバ）を含むコンピューティングシステムで実現されてもよく、またはフロントエンドコンポーネント（たとえば、ユーザが本明細書に記載されているシステムおよび技術の実現例と対話することができるグラフィカルユーザインターフェイスまたはウェブブラウザを有するクライアントコンピュータ）を含むコンピューティングシステムで実現されてもよく、またはこのようなバックエンドコンポーネント、ミドルウェアコンポーネントまたはフロントエンドコンポーネントの任意の組み合わせを含むコンピューティングシステムで実現されてもよい。システムのコンポーネントは、デジタルデータ通信の任意の形態または媒体（たとえば、通信ネットワーク）によって相互接続されてもよい。通信ネットワークの例としては、ローカルエリアネットワーク（「ＬＡＮ」）、ワイドエリアネットワーク（「ＷＡＮ」）、ピアツーピアネットワーク（アドホックまたはスタティック要素を有する）、グリッドコンピューティングインフラストラクチャおよびインターネットが挙げられる。
【００５２】
コンピューティングシステムは、クライアントとサーバとを含み得る。クライアントおよびサーバは、一般に互いに離れており、通常は通信ネットワークを介して対話する。クライアントとサーバとの関係は、コンピュータプログラムがそれぞれのコンピュータ上で実行されて互いにクライアント−サーバ関係を有することによって生じる。
【００５３】
本明細書には、分散データベースシステムにおける分散トランザクションのための方法およびシステムが記載されている。本明細書に記載されている一例は、１つ以上のタブレットレプリカを備えるソースグループに分割点を挿入する要求を識別するステップを含み、各タブレットは、上記分散データベースシステム内のテーブルからのデータの少なくとも一部を含み、上記分割点は、上記ソースグループ内のデータを第１の範囲および上記第１の範囲とは異なる第２の範囲に分割し、上記一例はさらに、上記要求に応答して、上記ソースグループの上記第１の範囲内のファイル名のリストを、１つ以上のタブレットレプリカを備える第１のターゲットグループに送信するステップと、上記第１の範囲内の上記ファイル名のリストによって表わされるファイルの仮想コピーを上記第１のターゲットグループにおいて作成するステップとを含み、上記仮想コピーは、上記ファイルのデータを複製することなく、上記ファイルのデータの各々を新たな名前を用いて利用できるようにする。
【００５４】
いくつかの実現例について詳細に上記したが、他の変形例も可能である。また、図面に示されている論理フローは、望ましい結果を達成するために、示されている特定の順序またはシーケンシャルな順序を必要とするものではない。他のステップが設けられてもよく、または記載されているフローからステップが除去されてもよく、記載されているシステムに他のコンポーネントが追加されてもよく、または記載されているシステムからコンポーネントが除去されてもよい。したがって、他の実現例は、以下の特許請求の範囲の範囲内である。
【図１】
2019519025.tif 000003
【図２】
2019519025.tif 000004
【図３】
2019519025.tif 000005
【図４】
2019519025.tif 000006
【図５】
2019519025.tif 000007
【手続補正書】
【提出日】平成30年12月21日(2018.12.21)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
１つ以上のプロセッサによって実行される、分散データベースシステムにおける分散トランザクションのためのコンピュータによって実行される方法であって、
ソースグループに分割点を挿入する要求を識別するステップを備え、前記ソースグループは、１つ以上のタブレットレプリカを備え、各タブレットは、前記分散データベースシステム内のテーブルからのデータの少なくとも一部を含む変更不可ファイルまたはレイヤのリストを備え、前記分割点は、前記ソースグループ内の前記データを第１の範囲および前記第１の範囲とは異なる第２の範囲に分割し、前記方法はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、
前記ソースグループの前記第１の範囲内のファイル名のリストを複数のターゲットグループの第１のターゲットグループに送信するステップであって、前記第１のターゲットグループは、１つ以上のタブレットレプリカを備えるステップと、
前記第１の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第１のターゲットグループにおいて作成するステップであって、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルのデータの各々を新たな名前を用いて利用できるようにするステップと、
前記ソースグループと前記ターゲットグループとを含む分散トランザクションを適用するステップであって、前記分散トランザクションは、新たなデータ場所を反映するためのメタデータテーブル、分割点、および移動を反映するための前記ソースグループおよびターゲットグループにおけるメタデータ分割点を更新し、前記分散トランザクションは、前記ソースグループおよびターゲットグループのための範囲データをさらに備え、前記範囲データは、移動させるべきユーザデータの範囲を指定する、ステップと、
前記ソースグループのソースタブレットによって前記範囲データを適用し、現在のレイヤスタックを保存し、前記第１のターゲットグループのターゲットタブレットに提供されるように前記現在のレイヤスタックを準備するステップと、
前記ソースタブレットの前記現在のレイヤスタックを検索し、移動させるべき前記範囲を指定する適用ループに１つ以上のプロキシレイヤを挿入するステップと、
前記ソースグループを削除する前に、移動された全ての範囲の内容を前記第１のターゲットグループ内の複製されたテーブルに書き込むステップとを備える、方法。
【請求項２】
前記第１の範囲内の前記ファイルを前記第１のターゲットグループに追加するステップと、
前記第１のターゲットグループが前記ソースグループにおける前記第１の範囲内の前記ファイルにもはや依存していないことを前記ソースグループに知らせるステップと、
前記第１の範囲内の前記ファイルを前記ソースグループから削除するステップとを備える、請求項１に記載の方法。
【請求項３】
前記ソースグループに前記分割点を挿入する前記要求に応答して、
前記ソースグループの前記第２の範囲内のファイル名のリストを第２のターゲットグループに送信するステップであって、前記第２のターゲットグループは、１つ以上のタブレットレプリカを備えるステップと、
前記第２の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第２のターゲットグループにおいて作成するステップであって、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルの内容の各々を新たな名前の下で利用できるようにするステップと、をさらに備える、請求項１または請求項２に記載の方法。
【請求項４】
前記第１の範囲内のインメモリバッファード更新情報の内容を前記ソースグループから送信するステップと、
前記第１のターゲットグループにおいて、前記ソースグループからの前記第１の範囲内の前記インメモリバッファード更新情報の内容を、前記第１のターゲットグループの前記インメモリバッファード更新情報に追加するステップとを備える、請求項１〜請求項３のいずれか１項に記載の方法。
【請求項５】
前記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される、請求項１〜請求項４のいずれか１項に記載の方法。
【請求項６】
各グループ内のタブレットの大部分は、前記投票フェーズにおいて前記分散トランザクションが完了するようにコミットしなければならない、請求項５に記載の方法。
【請求項７】
前記投票フェーズにおけるアボートへの投票に応答して、各グループは、前記分散トランザクションをアンドゥする、請求項５に記載の方法。
【請求項８】
分散データベースにおいて分散トランザクションを実行するためのシステムであって、
データを格納するためのメモリと、
前記メモリにアクセスして動作を実行するように動作可能な１つ以上のプロセッサとを備え、前記動作は、
ソースグループに分割点を挿入する要求を識別するステップを備え、前記ソースグループは、１つ以上のタブレットレプリカを備え、各タブレットは、前記分散データベース内のテーブルからのデータの少なくとも一部を含む変更不可ファイルまたはレイヤのリストを備え、前記分割点は、前記ソースグループ内の前記データを第１の範囲および前記第１の範囲とは異なる第２の範囲に分割し、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、
前記ソースグループの前記第１の範囲内のファイル名のリストを複数のターゲットグループの第１のターゲットグループに送信するステップであって、前記第１のターゲットグループは、１つ以上のタブレットレプリカを備えるステップと、
前記第１の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第１のターゲットグループにおいて作成するステップであって、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルのデータの各々を新たな名前を用いて利用できるようにするステップと、
前記ソースグループと前記ターゲットグループとを含む分散トランザクションを適用するステップであって、前記分散トランザクションは、新たなデータ場所を反映するためのメタデータテーブル、分割点、および移動を反映するための前記ソースグループおよびターゲットグループにおけるメタデータ分割点を更新し、前記分散トランザクションは、前記ソースグループおよびターゲットグループのための範囲データをさらに備え、前記範囲データは、移動させるべきユーザデータの範囲を指定するステップと、
前記ソースグループのソースタブレットによって前記範囲データを適用し、現在のレイヤスタックを保存し、前記第１のターゲットグループのターゲットタブレットに提供されるように前記現在のレイヤスタックを準備するステップと、
前記ソースタブレットの前記現在のレイヤスタックを検索し、移動させるべき前記範囲を指定する適用ループに１つ以上のプロキシレイヤを挿入するステップと、
前記ソースグループを削除する前に、移動された全ての範囲の内容を前記第１のターゲットグループ内の複製されたテーブルに書き込むステップとを備える、システム。
【請求項９】
前記動作は、
前記第１の範囲内の前記ファイルを前記第１のターゲットグループに追加するステップと、
前記第１のターゲットグループが前記ソースグループにおける前記第１の範囲内の前記ファイルにもはや依存していないことを前記ソースグループに知らせるステップと、
前記第１の範囲内の前記ファイルを前記ソースグループから削除するステップとを備える、請求項８に記載のシステム。
【請求項１０】
前記動作は、
前記ソースグループに前記分割点を挿入する前記要求に応答して、
前記ソースグループの前記第２の範囲内のファイル名のリストを第２のターゲットグループに送信するステップであって、前記第２のターゲットグループは、１つ以上のタブレットレプリカを備えるステップと、
前記第２の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第２のターゲットグループにおいて作成するステップであって、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルの内容の各々を新たな名前の下で利用できるようにするステップである、請求項８または請求項９に記載のシステム。
【請求項１１】
前記動作は、
前記第１の範囲内のインメモリバッファード更新情報の内容を前記ソースグループから送信するステップと、
前記第１のターゲットグループにおいて、前記ソースグループからの前記第１の範囲内の前記インメモリバッファード更新情報の内容を、前記第１のターゲットグループの前記インメモリバッファード更新情報に追加するステップとを備える、請求項８〜請求項１０のいずれか１項に記載のシステム。
【請求項１２】
前記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される、請求項８〜請求項１１のいずれか１項に記載のシステム。
【請求項１３】
各グループ内のタブレットの大部分は、前記分散トランザクションが完了するようにコミットしなければならない、請求項１２に記載のシステム。
【請求項１４】
前記投票フェーズにおけるアボートへの投票に応答して、各グループは、前記分散トランザクションをアンドゥする、請求項１２に記載のシステム。
【請求項１５】
プログラムであって、少なくとも１つのプロセッサによって実行されることにより、分散データベースにおいて分散トランザクションを実行するための動作を行わせ、前記動作は、
ソースグループに分割点を挿入する要求を識別するステップを備え、前記ソースグループは、１つ以上のタブレットレプリカを備え、各タブレットは、分散データベースシステム内のテーブルからのデータの少なくとも一部を含む変更不可ファイルまたはレイヤのリストを備え、前記分割点は、前記ソースグループ内の前記データを第１の範囲および前記第１の範囲とは異なる第２の範囲に分割し、前記動作はさらに、
前記ソースグループに前記分割点を挿入する前記要求に応答して、
前記ソースグループの前記第１の範囲内のファイル名のリストを複数のターゲットグループの第１のターゲットグループに送信するステップであって、前記第１のターゲットグループは、１つ以上のタブレットレプリカを備えるステップと、
前記第１の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第１のターゲットグループにおいて作成するステップであって、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルのデータの各々を新たな名前を用いて利用できるようにするステップと、
前記ソースグループと前記ターゲットグループとを含む分散トランザクションを適用するステップであって、前記分散トランザクションは、新たなデータ場所を反映するためのメタデータテーブル、分割点、および移動を反映するための前記ソースグループおよびターゲットグループにおけるメタデータ分割点を更新し、前記分散トランザクションは、前記ソースグループおよびターゲットグループのための範囲データをさらに備え、前記範囲データは、移動させるべきユーザデータの範囲を指定するステップと、
前記ソースグループのソースタブレットによって前記範囲データを適用し、現在のレイヤスタックを保存し、前記第１のターゲットグループのターゲットタブレットに提供されるように前記現在のレイヤスタックを準備するステップと、
前記ソースタブレットの前記現在のレイヤスタックを検索し、移動させるべき前記範囲を指定する適用ループに１つ以上のプロキシレイヤを挿入するステップと、
前記ソースグループを削除する前に、移動された全ての範囲の内容を前記第１のターゲットグループ内の複製されたテーブルに書き込むステップとを備える、プログラム。
【請求項１６】
前記動作は、
前記第１の範囲内の前記ファイルを前記第１のターゲットグループに追加するステップと、
前記第１のターゲットグループが前記ソースグループにおける前記第１の範囲内の前記ファイルにもはや依存していないことを前記ソースグループに知らせるステップと、
前記第１の範囲内の前記ファイルを前記ソースグループから削除するステップとを備える、請求項１５に記載のプログラム。
【請求項１７】
前記動作は、
前記ソースグループに前記分割点を挿入する前記要求に応答して、
前記ソースグループの前記第２の範囲内のファイル名のリストを第２のターゲットグループに送信するステップであって、前記第２のターゲットグループは、１つ以上のタブレットレプリカを備えるステップと、
前記第２の範囲内の前記ファイル名のリストによって表わされるファイルの仮想コピーを前記第２のターゲットグループにおいて作成するステップであって、前記仮想コピーは、前記ファイルのデータを複製することなく、前記ファイルの内容の各々を新たな名前の下で利用できるようにするステップとを備える、請求項１５または請求項１６に記載のプログラム。
【請求項１８】
前記動作は、
前記第１の範囲内のインメモリバッファード更新情報の内容を前記ソースグループから送信するステップと、
前記第１のターゲットグループにおいて、前記ソースグループからの前記第１の範囲内の前記インメモリバッファード更新情報の内容を、前記第１のターゲットグループの前記インメモリバッファード更新情報に追加するステップとを備える、請求項１５〜請求項１７のいずれか１項に記載のプログラム。
【請求項１９】
前記分散トランザクションは、投票フェーズとコミットフェーズとを備える２フェーズコミットプロトコルに従って実行される、請求項１５〜請求項１８のいずれか１項に記載のプログラム。
【請求項２０】
各グループ内のタブレットの大部分は、前記分散トランザクションが完了するようにコミットしなければならず、
前記投票フェーズがアボートへの投票を含んでいれば、各グループは、前記分散トランザクションをアンドゥする、請求項１９に記載のプログラム。
【国際調査報告】
2019519025.tif 000008
2019519025.tif 000009
2019519025.tif 000010