【手続補正書】
【提出日】平成29年5月25日(2017.5.25)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
コンピュータによって実行される方法であって、
複数シャードシステム内のシャードの量が変化したことを判断するステップと、
前記シャードの量が変化したとの判断に応答して、クライアントが前記複数シャードシステムに格納されたデータ項目に対して第１の態様で特定のタイプの動作を実行する通常状態から、前記クライアントが前記複数シャードシステムに格納されたデータ項目に対して、前記第１の態様とは異なる第２の態様で、前記クライアントがいかなるデータ項目に対しても排他的ロックを取得することなく前記特定のタイプの動作を実行するリバランシング状態に前記クライアントを遷移させるステップと、
前記クライアントが前記リバランシング状態にある間に、１つ以上の特定のデータ項目について、前記クライアントが前記リバランシング状態に遷移する前に前記１つ以上の特定のデータ項目が格納されていたソースシャードとは別の宛先シャードを判断するステップと、
前記クライアントが前記リバランシング状態にある間に前記１つ以上のデータ項目を前記ソースシャードから前記宛先シャードに移動させるステップとを備える、コンピュータによって実行される方法。
【請求項２】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、排他的ロックを取得することなく、前記１つ以上のデータ項目の移動に非同期的に、データ項目に対して前記特定のタイプの動作を前記第２の態様で実行するステップをさらに備える、請求項１に記載のコンピュータによって実行される方法。
【請求項３】
前記シャードの量の変化の後の前記複数シャードシステム内の前記シャードの量に少なくとも部分的に基づいて前記データ項目のプライマリキーをハッシュすることによって、前記１つ以上の特定のデータ項目についての前記宛先シャードを判断するステップと、
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されたとの判断に応答して、前記リバランシング状態から前記通常状態に前記クライアントを遷移させるステップとをさらに備える、請求項１または２に記載のコンピュータによって実行される方法。
【請求項４】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で追加タイプの動作を実行するステップをさらに備え、前記追加タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が追加されたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が追加されることになる特定の宛先シャードを判断することと、
前記ソースシャード上のデータ項目が前記第１のデータ項目のプライマリキーを有していないことを判断することと、
前記宛先シャード上のデータ項目が真のトゥームストーン属性値も前記第１のデータ項目のプライマリキーも有していないことを判断することと、
前記第１のデータ項目を前記宛先シャードに挿入することと、によって実行される、請求項１〜３のいずれか１項に記載のコンピュータによって実行される方法。
【請求項５】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で追加タイプの動作を実行するステップをさらに備え、前記追加タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が追加されたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が追加されることになる特定の宛先シャードを判断することと、
前記ソースシャード上のデータ項目が前記第１のデータ項目のプライマリキーを有していないことを判断することと、
前記宛先シャード上の第２のデータ項目が真のトゥームストーン属性値も前記第１のデータ項目のプライマリキーも有していることを判断することと、
前記第１のデータ項目の属性値を前記第２のデータ項目の属性に割り当てることと、
前記第２のデータ項目のトゥームストーン属性値を偽に設定することと、によって実行される、請求項１〜４のいずれか１項に記載のコンピュータによって実行される方法。
【請求項６】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で更新タイプの動作を実行するステップをさらに備え、前記更新タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が位置することになる特定の宛先シャードを判断することと、
前記ソースシャード上のデータ項目が前記第１のデータ項目のプライマリキーを有していないことを判断することと、
前記宛先シャード上の第２のデータ項目が偽のトゥームストーン属性値も前記第１のデータ項目のプライマリキーも有していることを判断することと、
前記第１のデータ項目の属性値を前記第２のデータ項目の属性に割り当てることと、によって実行される、請求項１〜５のいずれか１項に記載のコンピュータによって実行される方法。
【請求項７】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で更新タイプの動作を実行するステップをさらに備え、前記更新タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が位置することになる特定の宛先シャードを判断することと、
前記ソースシャード上の第２のデータ項目が前記第１のデータ項目のプライマリキーも偽のトゥームストーン属性値も有していることを判断することと、
前記宛先シャード上の第３のデータ項目が前記第１のデータ項目のプライマリキーを有していることを判断することと、
前記第１のデータ項目の属性値を前記第３のデータ項目の属性に割り当てることと、
前記第３のデータ項目のバージョン番号を前記第２のデータ項目のバージョン番号とは異なる値に設定することと、によって実行される、請求項１〜６のいずれか１項に記載のコンピュータによって実行される方法。
【請求項８】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で更新タイプの動作を実行するステップをさらに備え、前記更新タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が位置することになる特定の宛先シャードを判断することと、
前記ソースシャード上の第２のデータ項目が前記第１のデータ項目のプライマリキーも偽のトゥームストーン属性値も有していることを判断することと、
前記宛先シャード上のデータ項目が前記第１のデータ項目のプライマリキーを有していないことを判断することと、
前記第２のデータ項目のバージョン番号とは異なるバージョン番号を有する前記第１のデータ項目を前記宛先シャードに挿入することと、によって実行される、請求項１〜７のいずれか１項に記載のコンピュータによって実行される方法。
【請求項９】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で削除タイプの動作を実行するステップをさらに備え、前記削除タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が位置することになる特定の宛先シャードを判断することと、
前記ソースシャード上の第２のデータ項目が前記第１のデータ項目のプライマリキーを有していることを判断することと、
前記第２のデータ項目のバージョン番号とは異なるバージョン番号を有する前記第１のデータ項目を前記宛先シャードに更新／挿入することと、
前記宛先シャード上の前記第１のデータ項目のトゥームストーン属性値を真に設定することと、によって実行される、請求項１〜８のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１０】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で削除タイプの動作を実行するステップをさらに備え、前記削除タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が位置することになる特定の宛先シャードを判断することと、
前記ソースシャード上のデータ項目が前記第１のデータ項目のプライマリキーを有していないことを判断することと、
前記宛先シャード上の第２のデータ項目が前記第１のデータ項目のプライマリキーを有していることを判断することと、
前記第２のデータ項目のトゥームストーン属性値を真に設定することと、によって実行される、請求項１〜９のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１１】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーに対して前記第２の態様で取得タイプの動作を実行するステップをさらに備え、前記取得タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記プライマリキーを有するデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記プライマリキーを有するデータ項目が位置することになる特定の宛先シャードを判断することと、
前記宛先シャード上の第１のデータ項目が前記プライマリキーおよび偽のトゥームストーン属性値を有していることを判断することと、
前記第１のデータ項目の属性値を読取ることと、によって実行される、請求項１〜１０のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１２】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーに対して前記第２の態様で取得タイプの動作を実行するステップをさらに備え、前記取得タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記プライマリキーを有するデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記プライマリキーを有するデータ項目が位置することになる特定の宛先シャードを判断することと、
前記宛先シャード上のデータ項目が前記プライマリキーを有していないことを判断することと、
前記ソースシャード上の第１のデータ項目が前記プライマリキーおよび偽のトゥームストーン属性値を有していることを判断することと、
前記第１のデータ項目の属性値を読取ることと、によって実行される、請求項１〜１１のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１３】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーに対して前記第２の態様で取得タイプの動作を実行するステップをさらに備え、前記取得タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記プライマリキーを有するデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記プライマリキーを有するデータ項目が位置することになる特定の宛先シャードを判断することと、
前記宛先シャード上のデータ項目が前記プライマリキーを有していないことを第１の時点で判断することと、
前記ソースシャード上のデータ項目が前記プライマリキーを有していないことを判断することと、
前記宛先シャード上の第１のデータ項目が前記プライマリキーおよび偽のトゥームストーン属性値を有していることを第２の時点で判断することと、
前記第１のデータ項目の属性値を読取ることと、によって実行される、請求項１〜１２のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１４】
前記１つ以上のデータ項目を前記ソースシャードから前記宛先シャードに移動させるステップは、
システム全体にわたるバージョン番号をインクリメントするステップと、
前記システム全体にわたるバージョン番号よりも小さなバージョン番号を有する各々の第１のデータ項目について、前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が位置することになる第１の宛先シャードを判断するステップと、
（ａ）前記システム全体にわたるバージョン番号よりも小さなバージョン番号を有し、（ｂ）前記シャードの量の変化の後に第２のデータ項目が位置することになる第２の宛先シャードとは異なるソースシャード上に位置する各々の第２のデータ項目について、前記システム全体にわたるバージョン番号を有する前記第２のデータ項目のコピーを前記第２の宛先シャードに挿入するステップと、
（ａ）前記システム全体にわたるバージョン番号よりも小さなバージョン番号を有し、（ｂ）前記シャードの量の変化の後に第３のデータ項目が位置することになる第３の宛先シャード上にすでに位置している各々の第３のデータ項目について、前記第３のデータ項目のバージョン番号を前記システム全体にわたるバージョン番号に変化させるステップとを備える、請求項１〜１３のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１５】
前記１つ以上のデータ項目を前記ソースシャードから前記宛先シャードに移動させるステップは、システム全体にわたるバージョン番号をインクリメントするステップを備え、
前記１つ以上のデータ項目の移動が完了した時点で前記複数シャードシステム内の１つ以上のシャードに対してペンディングになっているクエリセットを判断するステップと、
前記クエリセットにおける全てのクエリが終了するのを待機するステップと、
前記クエリセットにおける全てのクエリが終了した後に、前記システム全体にわたるバージョン番号とは異なるバージョン番号属性値を有する全てのデータ項目コピーを前記複数シャードシステム内の全てのシャードから除去するステップと、
前記クエリセットにおける全てのクエリが終了した後に、真のトゥームストーン属性値を有する全てのデータ項目コピーを前記複数シャードシステム内の全てのシャードから除去するステップとをさらに備える、請求項１〜１４のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１６】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記複数シャードシステム内の各々の特定のシャードについて、（ａ）前記特定のシャード上に位置しかつ（ｂ）指定のクエリ基準を満たすデータ項目を有する前記特定のシャードについての事前結果キューを投入するステップと、
各々の特定のシャードの事前結果キューについて、前記シャードの事前結果キューにおけるデータ項目のプライマリキーに少なくとも部分的に基づいて、前記シャードの事前結果キューにおけるデータ項目を分類するステップと、
全てのシャードの事前結果キューが空になるまで、動作を繰返し実行するステップとをさらに備え、前記動作は、
前記複数シャードシステム内の全てのシャードの事前結果キューのトップに現在位置しているデータ項目を備えるセットから第１のデータ項目を選択することと、
真のトゥームストーン属性値を有していない各々の第１のデータ項目を最終結果セットに追加することと、
前記第１のデータ項目のプライマリキーに一致するプライマリキーを有する全てのデータ項目コピーを全てのシャードの事前結果キューから除去することとを備え、
全てのシャードの事前結果キューが空になった後に、前記最終結果セットにおけるデータ項目をクエリ結果として返すステップをさらに備える、請求項１〜１５のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１７】
前記複数シャードシステム内の全てのシャードの事前結果キューのトップに現在位置しているデータ項目を備える前記セットから前記第１のデータ項目を選択することは、
前記セットにおけるデータ項目のプライマリキーのうち、最小のプライマリキーを有するデータ項目のサブセットを前記セットから選択することと、
前記サブセットにおけるデータ項目のバージョン番号属性値のうち、最大のバージョン番号属性値を有するデータ項目を前記第１のデータ項目から選択することとを備える、請求項１６に記載のコンピュータによって実行される方法。
【請求項１８】
前記１つ以上のデータ項目が前記ソースシャードから前記宛先シャードに移動されている間に、前記クライアントが、プライマリキーを有する第１のデータ項目に対して前記第２の態様で削除タイプの動作を実行しようと試みたり、実行することに失敗したりするステップをさらに備え、前記削除タイプの動作は、少なくとも部分的に、
前記シャードの量の変化の前の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の前に前記第１のデータ項目が位置していたであろう特定のソースシャードを判断することと、
前記シャードの量の変化の後の前記複数シャードシステム内のシャードの量に少なくとも部分的に基づいて、前記シャードの量の変化の後に前記第１のデータ項目が位置することになる特定の宛先シャードを判断することと、
前記ソースシャード上のデータ項目が前記第１のデータ項目のプライマリキーを有していないことを判断することと、
前記宛先シャード上のデータ項目が前記第１のデータ項目のプライマリキーを有していないことを判断することと、
前記第１のデータ項目が存在していないことにより削除動作が失敗したことを示すデータを生成することと、によって実行される、請求項１〜１７のいずれか１項に記載のコンピュータによって実行される方法。
【請求項１９】
システムであって、
データ項目を格納する複数のデータベースシャードと、
複数のクライアントとを備え、前記複数のクライアントは、前記複数のデータベースシャードの量の変化に応答して、前記複数のクライアントの各クライアントが第１の態様で前記データ項目に対して特定のタイプの動作を実行するように構成される通常状態から、前記複数のクライアントの各クライアントが前記第１の態様とは異なる第２の態様で、前記クライアントがいかなるデータ項目に対しても排他的ロックを取得することなく前記データ項目に対して前記特定のタイプの動作を実行するように構成されるリバランシング状態に遷移するように構成され、前記システムはさらに、
少なくとも１つの計算装置を備え、前記少なくとも１つの計算装置は、（ａ）前記複数のクライアントが前記リバランシング状態にある間に、１つ以上の特定のデータ項目について、前記複数のクライアントの各クライアントが前記通常状態にあった間に前記１つ以上の特定のデータ項目が格納されていたソースシャードとは別の宛先シャードを判断し、（ｂ）前記複数のクライアントの各クライアントが前記リバランシング状態にある間に前記１つ以上のデータ項目を前記ソースシャードから前記宛先シャードに移動させるように構成される、システム。
【請求項２０】
プロセッサによって実行可能な命令を含むコンピュータ読取可能プログラムあって、前記プロセッサによって実行可能な命令は、
複数シャードシステム内のシャードの量が変化したことを１つ以上のプロセッサに判断させるための命令と、
前記シャードの量が変化したとの判断に応答して、クライアントが前記複数シャードシステムに格納されたデータ項目に対して第１の態様で特定のタイプの動作を実行する通常状態から、前記クライアントが前記複数シャードシステムに格納されたデータ項目に対して、前記第１の態様とは異なる第２の態様で、前記クライアントがいかなるデータ項目に対しても排他的ロックを取得することなく前記特定のタイプの動作を実行するリバランシング状態に前記クライアントを遷移させることを１つ以上のプロセッサにさせるための命令と、
前記クライアントが前記リバランシング状態にある間に、１つ以上の特定のデータ項目について、前記クライアントが前記リバランシング状態に遷移する前に前記１つ以上の特定のデータ項目が格納されていたソースシャードとは別の宛先シャードを１つ以上のプロセッサに判断させるための命令と、
前記クライアントが前記リバランシング状態にある間に前記１つ以上のデータ項目を前記ソースシャードから前記宛先シャードに移動させることを１つ以上のプロセッサにさせるための命令とを備える、コンピュータ読取可能プログラム。