(57)【特許請求の範囲】
【請求項１】
パーティション・バランシング・サブタスクを発行する方法であって、コントローラに適用され、前記コントローラおよび少なくとも２つのノードは記憶システムを形成し、各ノードは少なくとも１つのパーティションを含み、前記方法は、
第２のパーティション・バランシング・タスクが受け取られた後に、第２のパーティション・バランシング・サブタスク・セットを生成するステップであって、前記第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、前記移行パーティションが属するノード、および行き先ノードを記録するステップと、
現行のパーティション・バランシング・サブタスク・セットを検索し、前記第２のパーティション・バランシング・サブタスク・セットと前記現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除するステップと、
前記繰り返されるパーティション・バランシング・サブタスクが削除された後に、各パーティション・バランシング・サブタスクに記録された前記行き先ノードに対して、前記第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するステップと、を含み、
第２のパーティション・バランシング・タスクに従って第２のパーティション・バランシング・サブタスク・セットを生成する前記ステップは、具体的には、
前記第２のパーティション・バランシング・タスクが受け取られた後に、前記記憶システムのターゲット・パーティション分散情報を算出し、前記記憶システムの現行パーティション分散情報を検索し、前記現行パーティション分散情報および前記ターゲット・パーティション分散情報に従ってパーティション分散情報変動を取得し、前記現行パーティション分散情報は、各ノードと前記ノード上のパーティションとの間の対応を記録し、前記ターゲット・パーティション分散情報は、パーティション移行が実行された後に、各ノードと前記ノード上のパーティションとの間の対応を記録し、前記パーティション分散情報変動は、前記現行パーティション分散情報が前記ターゲット・パーティション分散情報になるために、移行する必要がある移行パーティションおよび各移行パーティションの行き先ノードを記録するステップと、
各移行パーティションについて、移行パーティションが属するノードを選択し、各移行パーティションが属するノードおよび前記パーティション分散情報変動に従って、前記第２のパーティション・バランシング・サブタスク・セットを生成するステップと、を含む方法。
【請求項２】
前記パーティション・バランシング・サブタスクを発行する前記ステップの前に、前記方法は、
前記現行のパーティション・バランシング・サブタスク・セットから、完了され得ないパーティション・バランシング・サブタスクを削除するステップをさらに含み、前記完了され得ないパーティション・バランシング・サブタスクは、移行パーティションが属するノードに欠陥があるパーティション・バランシング・サブタスクと、行き先ノードに欠陥があるパーティション・バランシング・サブタスクとを含む、請求項１に記載の方法。
【請求項３】
各移行パーティションについて、移行パーティションが属するノードを選択する前記ステップは、具体的には、
複数のパーティションが前記移行に利用可能である場合に、前記パーティションのデータ完全性を検出し、完全なデータを有する移行パーティションが属するノードを選択するステップである、請求項１に記載の方法。
【請求項４】
第２のパーティション・バランシング・サブタスク・セットを生成する前記ステップは、具体的には、
第１のパーティション・バランシング・タスクが終了する前に、計算によって、前記第２のパーティション・バランシング・サブタスク・セットを生成するステップであって、前記現行のパーティション・バランシング・サブタスク・セットは、第１のパーティション・バランシング・サブタスク・セットにおいて実行されているパーティション・バランシング・サブタスクを含む、請求項１に記載の方法。
【請求項５】
前記発行するステップの後に、前記方法は、
前記パーティション・バランシング・サブタスクの応答メッセージが受け取られる前に、第１のパーティション・バランシング・サブタスクが終了したことをマークするステップをさらに含む、請求項１に記載の方法。
【請求項６】
前記発行するステップの後に、前記方法は、
パーティション・バランシング・サブタスクを受け取るノードによって、前記パーティション・バランシング・サブタスクの行き先ノードとして前記パーティション・バランシング・サブタスクを実行するステップをさらに含む、請求項１に記載の方法。
【請求項７】
前記発行するステップの後に、前記方法は、
前記パーティション・バランシング・サブタスクのための記憶ノードの応答メッセージを受け取り、現行パーティション分散情報を、前記パーティション・バランシング・サブタスクの実行の成功後の状態に更新するステップをさらに含む、請求項１に記載の方法。
【請求項８】
パーティション・バランシング・サブタスクを発行するための装置であって、前記装置および少なくとも２つのノードは記憶システムを形成し、各ノードは少なくとも１つのパーティションを含み、前記装置は、
第２のパーティション・バランシング・タスクが受け取られた後に、第２のパーティション・バランシング・サブタスク・セットを生成するように構成されるパーティション・バランシング・サブタスク生成モジュールであり、前記第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、前記移行パーティションが属するノード、および行き先ノードを記録するパーティション・バランシング・サブタスク生成モジュールと、
現行のパーティション・バランシング・サブタスク・セットを検索し、前記第２のパーティション・バランシング・サブタスク・セットと前記現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除するように構成されるパーティション・バランシング・サブタスク削除モジュールと、
前記繰り返されるパーティション・バランシング・サブタスクが削除された後に、各パーティション・バランシング・サブタスクに記録された前記行き先ノードに対して、前記第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するように構成されるパーティション・バランシング・サブタスク発行モジュールと、を含み、
前記パーティション・バランシング・サブタスク生成モジュールは、具体的には、
前記第２のパーティション・バランシング・タスクが受け取られた後に、前記記憶システムのターゲット・パーティション分散情報を算出し、前記記憶システムの現行パーティション分散情報を検索し、前記現行パーティション分散情報および前記ターゲット・パーティション分散情報に従ってパーティション分散情報変動を取得するように構成され、前記現行パーティション分散情報は、各ノードと前記ノード上のパーティションとの間の対応を記録し、前記ターゲット・パーティション分散情報は、パーティション移行が実行された後に、各ノードと前記ノード上のパーティションとの間の対応を記録し、前記パーティション分散情報変動は、前記現行パーティション分散情報が前記ターゲット・パーティション分散情報になるために、移行する必要がある移行パーティションおよび各移行パーティションの行き先ノードを記録し、
各移行パーティションについて、移行パーティションが属するノードを選択し、各移行パーティションが属するノードおよび前記パーティション分散情報変動に従って、前記第２のパーティション・バランシング・サブタスク・セットを生成するように構成される装置。
【請求項９】
前記パーティション・バランシング・サブタスク削除モジュールは、
前記現行のパーティション・バランシング・サブタスク・セットから、完了され得ないパーティション・バランシング・サブタスクを削除するようにさらに構成され、前記完了され得ないパーティション・バランシング・サブタスクは、移行パーティションが属するノードに欠陥があるパーティション・バランシング・サブタスクと、行き先ノードに欠陥があるパーティション・バランシング・サブタスクとを含む、請求項８に記載の装置。
【請求項１０】
前記パーティション・バランシング・サブタスク生成モジュールによる、各移行パーティションについて、移行パーティションが属するノードを前記選択することは、具体的には、
複数のパーティションが前記移行に利用可能である場合に、前記パーティションのデータ完全性を検出し、完全なデータを有する移行パーティションが属するノードを選択することである、請求項８に記載の装置。
【請求項１１】
前記パーティション・バランシング・サブタスク生成モジュールは、具体的には、
第１のパーティション・バランシング・タスクが終了する前であって前記第２のパーティション・バランシング・タスクが受け取られた後に、計算によって、前記第２のパーティション・バランシング・サブタスク・セットを生成するように構成され、前記現行のパーティション・バランシング・サブタスク・セットは、第１のパーティション・バランシング・サブタスク・セットにおいて実行されているパーティション・バランシング・サブタスクを含む、請求項８に記載の装置。
【請求項１２】
パーティション・バランシング・サブタスク状態マーキングモジュールをさらに含み、前記パーティション・バランシング・サブタスク状態マーキングモジュールは、
各パーティション・バランシング・サブタスクが発行された後であって前記パーティション・バランシング・サブタスクの応答メッセージが受け取られる前に、第１のパーティション・バランシング・タスクが終了したことをマークするように構成される、請求項８に記載の装置。
【請求項１３】
前記パーティション・バランシング・サブタスクのための記憶ノードの応答メッセージを受け取り、現行パーティション分散情報を、前記パーティション・バランシング・サブタスクの実行の成功後の状態に更新するように構成されるパーティション分散情報更新モジュールをさらに含む、請求項８に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報技術の分野に関し、特にタスク処理技術に関する。
【背景技術】
【０００２】
コンピュータ技術およびネットワーク技術の発達に伴って、情報量は等比級数的に増大する傾向があり、人間のデータは先例のないスケールに達し、このような超大規模データの記憶および管理は産業界における大きな課題になっている。超大規模データが従来の集中化した方法で記憶され管理される場合には、高い効率の読み出し／書き込み動作を提供することができず、高拡張性および高可用性を満たすことができない。このような背景において、複数の記憶ノードにより形成される様々な記憶システムが出現した。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
複数の記憶ノードにより形成される記憶システムでは、一般に、単一ポイント不良によって生じるデータ損失を回避するために、同一データの複数のコピーが記憶される。従って、システムの切迫した要件は、データ・コピーの数を安定に保つことである。さらに、記憶システムの持続可能な作業に対する人々の要求が日ごとに急速に大きくなっていくにつれて、分散記憶システムのオンライン容量拡張は、システムの基本機能の欠くことのできない部分になる。それから、システムデータ損傷の場合に、データ回復タスクをどのように発行するかが、現行技術の焦点になる。
【０００４】
本発明は、パーティション・バランシング・サブタスク（partition  balancing  subtask）を発行するための方法、装置およびシステムを提供し、その結果、パーティション移行タスク（partition  migration  task）を発行することができる。
【課題を解決するための手段】
【０００５】
第１の態様では、本発明の実施形態は、パーティション・バランシング・タスクを発行する方法を提供する。本方法はコントローラに適用され、コントローラおよび少なくとも２つのノードは記憶システムを形成し、各ノードは少なくとも１つのパーティションを含む。本方法は、第２のパーティション・バランシング・タスクが受け取られた後に、第２のパーティション・バランシング・サブタスク・セットを生成するステップであって、第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、移行パーティションが属するノード、および行き先ノードを記録するステップと、現行のパーティション・バランシング・サブタスク・セットを検索し、第２のパーティション・バランシング・サブタスク・セットと現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除するステップと、繰り返されるパーティション・バランシング・サブタスクが削除された後に、各パーティション・バランシング・サブタスクに記録された行き先ノードに対して、第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するステップと、を含む。
【０００６】
第１の態様の第１の可能な実現方法では、パーティション・バランシング・サブタスクを発行するステップの前に、本方法は、現行のパーティション・バランシング・サブタスクから、完了され得ないパーティション・バランシング・サブタスクを削除するステップをさらに含み、完了され得ないパーティション・バランシング・サブタスクは、移行パーティションが属するノードに欠陥があるパーティション・バランシング・サブタスクと、行き先ノードに欠陥があるパーティション・バランシング・サブタスクとを含む。
【０００７】
第２の態様では、本発明の一実施形態は、パーティション・バランシング・サブタスクを発行するための装置を提供する。本装置は、第２のパーティション・バランシング・タスクが受け取られた後に、第２のパーティション・バランシング・サブタスク・セットを生成するように構成されるパーティション・バランシング・サブタスク生成モジュールであり、第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、移行パーティションが属するノード、および行き先ノードを記録するパーティション・バランシング・サブタスク生成モジュールと、現行のパーティション・バランシング・サブタスク・セットを検索し、第２のパーティション・バランシング・サブタスク・セットと現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除するように構成されるパーティション・バランシング・サブタスク削除モジュールと、繰り返されるパーティション・バランシング・サブタスクが削除された後に、各パーティション・バランシング・サブタスクに記録された行き先ノードに対して、第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するように構成されるパーティション・バランシング・サブタスク発行モジュールと、を含む。
【０００８】
第２の態様の第１の可能な実現方法では、完了され得ないパーティション・バランシング・サブタスクは、現行のパーティション・バランシング・サブタスクから削除され、完了され得ないパーティション・バランシング・サブタスクは、移行パーティションが属するノードに欠陥があるパーティション・バランシング・サブタスクと、行き先ノードに欠陥があるパーティション・バランシング・サブタスクとを含む。
【０００９】
第３の態様によれば、本発明の一実施形態は、記憶システムを提供し、記憶システムは、第２の態様または第２の態様の第１の可能な実現方法によるパーティション・バランシング・サブタスクを発行するための装置を含み、そして少なくとも２つのノードをさらに含み、ノードは、パーティション・バランシング・サブタスクが受け取られた後に、パーティション・バランシング・サブタスクの行き先ノードとしてパーティション・バランシング・サブタスクを実行する。
【００１０】
第４の態様によれば、本発明の一実施形態は、パーティション・バランシング・タスクを発行する方法を提供する。本方法はコントローラに適用され、コントローラおよび少なくとも２つのノードは記憶システムを形成し、各ノードは少なくとも１つのパーティションを含む。本方法は、第２のパーティション・バランシング・タスクが受け取られた後に、第２のパーティション・バランシング・サブタスク・セットを生成するステップであって、第２のパーティション・バランシング・タスクは、ノード上に起こる欠陥が原因で生成されたパーティション・バランシング・タスクであり、第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、移行パーティションが属するノード、および行き先ノードを記録するステップと、現行のパーティション・バランシング・サブタスク・セットを検索し、現行のパーティション・バランシング・サブタスクから、完了され得ないパーティション・バランシング・サブタスクを削除するステップであって、完了され得ないパーティション・バランシング・サブタスクは移行パーティションが欠陥ノードに属するパーティション・バランシング・サブタスクと、行き先ノードが欠陥ノードであるパーティション・バランシング・サブタスクを含むステップと、繰り返されるパーティション・バランシング・サブタスクが削除された後に、各パーティション・バランシング・サブタスクに記録された行き先ノードに対して、第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するステップと、を含む。
【００１１】
第４の態様の第１の可能な実現方法では、パーティション・バランシング・サブタスクを発行するステップの前に、本方法は、第２のパーティション・バランシング・サブタスク・セットと現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除するステップをさらに含む。
【００１２】
第５の態様によれば、本発明の一実施形態は、パーティション・バランシング・サブタスクを発行するための装置を提供する。本装置は、第２のパーティション・バランシング・タスクが受け取られた後に、第２のパーティション・バランシング・サブタスク・セットを生成するように構成されるパーティション・バランシング・サブタスク生成モジュールであり、第２のパーティション・バランシング・タスクは、ノードに生じる欠陥が原因で生成されたパーティション・バランシング・タスクであり、第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、移行パーティションが属するノード、および行き先ノードを記録するパーティション・バランシング・サブタスク生成モジュールと、現行のパーティション・バランシング・サブタスク・セットを検索し、完了され得ないパーティション・バランシング・サブタスクを、現行のパーティション・バランシング・サブタスクから削除するように構成されるパーティション・バランシング・サブタスク削除モジュールであり、完了され得ないパーティション・バランシング・サブタスクは、移行パーティションが欠陥のあるノードに属するパーティション・バランシング・サブタスクと、行き先ノードに欠陥のあるパーティション・バランシング・サブタスクと、を含むパーティション・バランシング・サブタスク削除モジュールと、繰り返されるパーティション・バランシング・サブタスクが削除された後に、各パーティション・バランシング・サブタスクに記録された行き先ノードに対して、第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するように構成されるパーティション・バランシング・サブタスク発行モジュールと、を含む。
【００１３】
第５の態様の第１の可能な実現方法では、第２のパーティション・バランシング・サブタスク・セットと現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクは、削除される。
【００１４】
本発明の実施形態を適用することによって、現在、パーティション・バランシング・サブタスクが存在する場合には、パーティション・バランシング・サブタスクは発行され続けることができる。それによって、先行するパーティション・バランシング・サブタスクおよび次のパーティション・バランシング・サブタスクの並列処理を実現することができる。
【００１５】
本発明の実施形態または従来技術の技術的対策をより明確に示すために、以下では、実施形態または従来技術を記載するために必要な添付の図面を簡潔に導入する。明らかに、下記の添付の図面は、単に本発明のいくつかの実施形態だけを示し、他の図面はこれらの添付の図面に従ってさらに得ることができる。
【図面の簡単な説明】
【００１６】
【図１】一実施形態によるコントローラの概略構成図である。
【図２】一実施形態によるパーティション・バランシング・サブタスクを発行する方法のフローチャートである。
【図３】一実施形態によるパーティション・バランシング・サブタスクを発行するための装置の概略構成図である。
【図４】パーティション・バランシング・サブタスクを発行するための記憶システムの概略構成図である。
【発明を実施するための形態】
【００１７】
以下では、本発明の実施形態の添付の図面を参照して、本発明の技術的対策を明確かつ完全に記載する。明らかに、記載される実施形態は、本発明の実施形態の全てではなく、その一部にすぎない。本発明の実施形態に基づいて得られる他の全ての実施形態は、本発明の保護範囲に入るものとする。
【００１８】
ノードおよびコントローラによって形成される分散記憶システムにおいて、ノードのいくつかに欠陥がある場合には、これらの欠陥のあるノードのデータは他の正常なノードに移され、それによって、システム全体のデータの信頼性を確実にする。この移行タスクは、パーティション・バランシング・タスク（partition  balancing  task）と呼ぶことができる。パーティション・バランシング・タスクは、ノード間でパーティションを移行するためのタスクである。
【００１９】
既存のデータ移送動作では、第１のノードに欠陥が生じた後、第１のノードの対応するパーティション・バランシング・タスクが実行され、第１のノードのパーティション・バランシング・タスクが終了する前に第２のノードに欠陥が生じた場合には、第２のノードのパーティション・バランシング・タスクは、第１のノードのパーティション・バランシング・タスクが終了した後にのみ実行され得る。
【００２０】
パーティション・バランシング・タスクを実行するためには非常に長い時間がかかり、数十時間あるいはさらに長くなる場合もあるので、第２のノードはパーティション・バランシング・タスクを実行することに常に失敗し、第２のノードのデータはこのような長い時間に回復することに常に失敗する。そして、これは全ての分散記憶システムの信頼性を著しく低下させる。
【００２１】
本発明の一実施形態では、記憶システムはコントローラおよび複数のノードを含む。例えば、記憶システムは少なくとも２つのノードまたは少なくとも３つのノードを含み、これらのノードは第１のノードおよび第２のノードを含む。コントローラは、記憶システムのノードに接続され、これらの記憶ノードを制御する。ノードは記憶媒体、例えばＣＰＵ、メモリおよびハードディスクなどにより形成され、データを記憶するように構成される。記憶ノードは、略してノードと呼ばれてもよい。
【００２２】
ノードはデータを記憶してもよく、データは値によって表現されてもよく、識別子はキーによって表現されてもよく、キーおよび対応する値の組合せはキー値（key-value）と呼ばれる。各ノードには、少なくとも１つのパーティション（partition）がある。例えば、全体の記憶システムは合計２０のパーティションＰ０〜Ｐ１９に分割され、ある特定のハッシュ範囲がパーティションごとに分割され、ハッシュ計算がデータのキーについて実行され、それから、算出されたハッシュ値が属するハッシュ範囲に従って、ハッシュ値に対応するキー値を特定のノードに記憶することが決定されてもよい。
【００２３】
キー値がノードに記憶された後、複数のコピーはコピーグループを形成するためにパーティションごとに記憶されてもよい。そして、同じコピーグループのコピーの内容は同一である。データ損傷が１つまたは複数のコピーに生じた場合には、残りのパーティションのいずれかによって、リカバリが実行されてもよい。各パーティションが具体的に属するノードは、パーティション・バランシング・アルゴリズムに従って決定されてもよい。同じコピーグループのコピーは、異なるノードまたは異なるラックに、あるいは異なる機器室に置かれてもよい。そして、システムの信頼性は、コピーを散在して記憶することによって改善することができる。例えば、ノード１のパーティション１０は、ノード２およびノード３に同時に記憶される。同じパーティションの３つのコピーが記憶される場合には、このようなバックアップ方法は３つのコピーと呼ばれてもよい。別の場合には、パーティションは記憶システム全体で一意的であってもよい。すなわち、他のいかなるコピーも存在しない。
【００２４】
パーティション・バランシング・タスクは、ノード上のパーティションの配分を変更するタスクである。パーティション・バランシング・タスクは、あるノードから別のノードへパーティションを移行させる、すなわち、パーティションのデータを別のノードへ移行させるために実行されてもよい。以下の実施形態では、ノード欠陥がパーティション・バランシング・タスクを起動させることを一例として示し、ノード欠陥により失われたパーティションは移行によって再生する。
【００２５】
実際の場合では、その起動は、別の理由で実行されてもよい。例えば、システム容量を拡張するために、新しいノードを記憶システムに追加する場合に、いくつかのパーティションを既存のノードから新しく追加したノードに移行することが起動されてもよい。違いは、以下の通りである。ノード欠陥により起動されるパーティション・バランシング・タスクが実行される場合には、欠陥ノード上のパーティションのコピーが見いだされる必要があり、そのコピーが移行パーティションとして用いられる。一方、システム容量を拡張する場合には、コピーを検索するステップは存在しないが、移行パーティションは直接に移行される。パーティション・バランシング・タスクは、何らかの要因の変化によって起動されてもよい。その要因としては、例えば記憶システムのノード数の減少、データの冷たさ（coldness）もしくは熱さ（hotness）、ノードの性能、またはノードにより提供されるネットワークバンド幅などがある。
【００２６】
図１は、本発明の一実施例によるコントローラ１の概略構成図であり、コントローラ１は少なくとも２つのノード３に接続される。コントローラは、プロセッサ１１、メモリ１２、およびインターフェース１３を含み、これら３つは互いに接続される。インターフェース１３はノード３の各々に接続され、メモリ１２はプログラムを記憶するように構成され、プロセッサ１１はプログラムを実行するように構成され、プログラムのコードはコンピュータ動作コマンドを含む。プロセッサ１１によるプログラムの実行は、具体的には、以下の実施形態における方法を実現するために用いられる。
【００２７】
図２を参照すると、図２は、本発明の一実施例によるパーティション・バランシング・サブタスクを発行する方法のフローチャートである。パーティション・バランシング・タスクを実行する処理は、以下のステップを含む。
【００２８】
ステップ１１：第１のノードに欠陥がある場合に、コントローラは第１のパーティション・バランシング・タスクを生成する。第１のパーティション・バランシング・タスクを生成した後に、コントローラは、第１のターゲット・パーティション分散情報を算出し、現行パーティション分散情報を問合せて、現行パーティション分散情報および第１のターゲット・パーティション分散情報に従って第１のターゲット・パーティション分散情報変動を生成する。第１のターゲット・パーティション分散情報変動は、パーティション分散情報の変化であり、その変化は、現行パーティション分散情報が第１のターゲット・パーティション分散情報になるために必要である。そして、第１のターゲット・パーティション分散情報変動は、各ノードのノード・パーティション分散情報変動により形成されてもよい。各ノードのノード・パーティション分散情報変動は、移行パーティションと移行パーティションの行き先ノードとの間の対応を記録する。そして、行き先ノードは、移行パーティションがそこに移行する必要があるノードである。パーティション分散情報変動およびノード・パーティション分散情報変動については、本実施形態のステップ１５でまた参照されてもよい。本実施形態では、パーティション分散情報は、記憶システムのノード上のパーティションの配分を記述するために用いられ、具体的には、物理ノード上のパーティションのキー値に対応するデータの配分であってもよい。現行パーティション分散情報は、現時点の各ノードと各ノード上のパーティションとの間の対応を記録する。ターゲット・パーティション分散情報は、第１のパーティション・バランシング・タスクが実行された後、各ノードと各ノード上のパーティションとの間の対応を記録し、具体的には、パーティション移行が第１のパーティション・バランシング・タスクにより実行された後の、各ノードと各ノード上のパーティションとの間の対応である。そして、パーティション分散情報変動は、現行パーティション分散情報がターゲット・パーティション分散情報になるために、移行する必要がある移行パーティションおよび各移行パーティションの行き先ノードを記録する。第１のターゲット・パーティション分散情報は、形成する必要があるパーティション分散情報であり、現行ノード、パーティション分散情報、およびノードの利用可能な状態などの情報に従って、パーティション分散情報アルゴリズムを用いて生成されてもよいパーティション分散情報である。第１のパーティション・バランシング・サブタスク・セットのパーティション・バランシング・サブタスクを実行する処理において、現行パーティション分散情報は段階的に更新される。そして、全てのパーティション・バランシング・サブタスクが実行された後に、第１のターゲット・パーティション分散情報は現行パーティション分散情報になる。コントローラは、各ノードの利用可能な状態を記録してもよい。状態が利用可能な場合には、それは、そのノードが読み出し／書き込みサービスを提供できることを示す。そして、その状態が利用できない場合には、それは、そのノードが読み出し／書き込みサービスを提供できないこと、例えばハードディスクに欠陥があること、またはそのノードの電源が切断されていることなどを示す。
【００２９】
ステップ１２：コントローラは、パーティション分散情報変動に従って、各移行パーティションのソースノードを検索する。ソースノードは、移行パーティションがそこから移行する必要があるノードである。第１のパーティション・バランシング・サブタスク・セットは、移行パーティション、移行パーティションのソースノード、および移行パーティションの行き先ノードに従って生成される。同じ移行パーティションが複数のノードに存在する場合には、複数のノードのうちのいずれか１つが、移行パーティションのソースノードとして選択される。それから、第１のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクは、パーティション・バランシング・サブタスクに記録される行き先ノードに送られる。第１のパーティション・バランシング・サブタスク・セットは、記憶システムのパーティション分散情報が現行パーティション分散情報から第１のターゲット・パーティション分散情報に変化するために実行されることを必要とする一組のパーティション・バランシング・サブタスクである。本実施形態では、第１のノードに欠陥が生じた後、コントローラは第１のノード上の各パーティションのマークを記録する。そして、第１のノード上のパーティションのマークと同じマークのパーティション、すなわち第１のノード上のパーティションのコピーが別のノードに存在する。これらのパーティションが移行パーティションである。このステップでは、２つ以上のコピーがある場合には、コントローラは、移行パーティションのマークを用いることによって、コピーが置かれているノードを検索し、それらのノードのうちの１つをソースノードとして選択する。
【００３０】
第１のパーティション・バランシング・サブタスク・セットは、第１のパーティション・バランシング・タスクに基づいて生成され、少なくとも１つのパーティション・バランシング・サブタスクを含む。各パーティション・バランシング・サブタスクは、移行パーティション、ならびに移行パーティションのソースノードおよび行き先ノードを記録する。ソースノードは、データが移行される元のノードである。移行パーティションは、ソースノード上のデータが移行される元のパーティションである。そして、行き先ノードは、移行パーティションを受け取るノードである。行き先ノードがパーティション・バランシング・サブタスクを受け取った後、ソースノード上の移行パーティションが行き先ノードに移行する。パーティション・バランシング・タスクのために生成された全てのパーティション・バランシング・サブタスクが終了した後に、パーティション・バランシング・タスクの終了がマーク（記録）されてもよい。パーティション・バランシング・サブタスクを終了する方法は、完了または中止であってもよい。
【００３１】
本発明の本実施形態では、移行することまたは外に移行することは、コピーの方法により移行パーティションと同一の新しいパーティションを生成することを指す。移行パーティションはコピーされるパーティションであり、保持されてもよいし、また削除されてもよい。例えば、ノード欠陥によって起動される移行の場合には、移行パーティションをソースノードに保持してもよい。そして、容量拡張によって起動される移行の場合には、移行パーティションをソースノードから削除してもよい。
【００３２】
本発明の本実施形態では、ノード・パーティション分散情報は、パーティション分散情報を形成する。ノード・パーティション分散情報は、ノードとノードに記憶されるパーティションとの間の対応を指し、特定のノード上のパーティションの配分として解釈されてもよい。例えば、＜ノード１；パーティション０、パーティション１００＞は、２つのパーティション、すなわちパーティション０およびパーティション１００がノード１にあることを示す。同様に、＜ノード２；パーティション１、パーティション１０１＞は、２つのパーティション、すなわちパーティション１およびパーティション１０１がノード２にあることを示す。そして、＜ノード３；パーティション３、パーティション３０１＞は、２つのパーティション、すなわちパーティション３およびパーティション３０１がノード３にあることを示す。ノード１がオフラインになることを必要とし、従って、パーティション０およびパーティション１００を移行するタスクが起動されることを仮定する。パーティション・バランシング・アルゴリズムに従って、生成されたターゲット・パーティション分散情報は、ノード・パーティション分散情報の２つの部分を含んでもよい。すなわち、＜ノード２；パーティション１、パーティション１０１、パーティション０＞および＜ノード３；パーティション３、パーティション３０１、パーティション１００＞である。
【００３３】
従って、バランシング・サブタスクは、各パーティションの移行のために確立されることを必要とする。従って、２つのサブタスクが確立されてもよく、それぞれ、ノード１のパーティション０をノード２に移行させるためのパーティション・バランシング・サブタスク、およびノード１のパーティション１００をノード３に移行させるためのパーティション・バランシング・サブタスクである。２つのパーティション・バランシング・サブタスクが完成されると、ターゲット・パーティション分散情報は、記憶システムの実際のパーティション分散情報、すなわち、現行パーティション分散情報になる。別の実施形態では、パーティション・バランシング・サブタスクを、複数のパーティションを移行させるために用いてもよい。例えば、パーティション・バランシング・サブタスクを、ソースノード上の全ての移行パーティションを移行させるために用いてもよい。パーティション・バランシング・サブタスクが複数の移行パーティションを含む場合に、パーティション・バランシング・サブタスクは各移行パーティションに対応するソースノードおよび行き先ノードを記録する。
【００３４】
第１のノードに欠陥が生じた後は、第１のノード上のパーティションはもはや利用することができず、第１のノード上のパーティションのコピーであって別のノードにあるコピーが、移行パーティションの役割をするために検索される。見いだされたコピーは、パーティション・バランシング・タスクを実行することにより移行され、新しいコピーが生成される。これは、第１のノード上のパーティションを回復することと等価である。
【００３５】
本発明の本実施形態では、移行に利用可能なパーティションおよびそのパーティションが属するノードは、第１のターゲット・パーティション分散情報変動に従って検索される。２つ以上のパーティションが移行に利用可能である場合には、それらのパーティションのうちのいずれか１つが移行パーティションとして選択される。別の実施形態では、移行に利用可能なパーティションが検索された後、完全なデータ完全性情報を有するパーティションだけが移行パーティションとして選択され、不完全なデータ完全性を有するパーティションは移行パーティションとして選択されない。
【００３６】
各パーティションはデータ完全性情報を有し、この情報はコントローラに記録されてもよい。データ完全性情報は、パーティションのデータが完全であるかどうかをマークするために用いられる。完全な状態のパーティションは、このパーティションが移行できることを示し、そのパーティションが属するノードは、パーティション・バランシング・サブタスクのソースノードの役割をしてもよい。そして、全てのパーティションのデータは、デフォルトでは完全なものに設定されてもよい。不完全な状態のパーティションは、パーティションのデータが不完全で、移行できないことを示す。例えば、パーティションが生成されて、生成が完了した後、このパーティションが完全であることをマークしてもよい。
【００３７】
ここで、パーティションのデータ完全性を説明するために一例を示す。パーティションＰのデータをノードＢからノードＡまで移行させるためのパーティション・バランシング・サブタスクがあると仮定する。それから移行処理で、ノードＡのパーティションＰは、不完全なデータを有するパーティションであって、従って、別のパーティション・バランシング・サブタスクの移行ノードの役割をすることができない。しかし、移行が終了した後では、ノードＡのパーティションＰは完全なデータを有するパーティションである。
【００３８】
ステップ１３：コントローラによって送られるパーティション・バランシング・サブタスクを受け取るノード、すなわち、パーティション・バランシング・サブタスクの行き先ノードは、データ移送を実行し、そのようにして、パーティション・バランシング・サブタスクによって運ばれる情報に従って、ソースノード上の移行パーティションが行き先ノードにコピーされる。本実施形態では、第１のノード上のパーティションは移行パーティションであり、この移行パーティションのコピーは別のノードに存在する。従って、このステップでは、第１のノードのこのパーティションのコピーであって別のノードにあるコピーが、行き先ノードにコピーされる。各パーティション・バランシング・サブタスクを実行する処理は、以下の通りである。（１）行き先ノードが要求メッセージをソースノードに送り、ソースノード上のパーティションＰのデータの移行を要求する。ここで、パーティションＰは、第１のノード上のパーティションのコピーである。（２）ソースノードが、パーティションＰに属するデータ・キー値を記録するので、メッセージを受け取った後に、ソースノードはソースノード自身の全てのデータのキーを検索して、パーティションＰに属する全てのデータを行き先ノードに送る。（３）ソースノードからデータを受け取った後、行き先ノードが記憶のために行き先ノードのディスクにデータを書き込み、移行が完了する。
【００３９】
さらに、このステップでは、コントローラにより送られたパーティション・バランシング・サブタスクを受け取った後、行き先ノードは応答メッセージをコントローラに送る。応答メッセージを受け取った後、コントローラはパーティション・バランシング・サブタスクの情報をパーティション分散情報に更新する。その結果、その情報は現行パーティション分散情報の一部になる。すなわち、パーティション・バランシング・サブタスクの完了を待つ必要がなく、その代わりに、パーティション分散情報は、パーティション・バランシング・サブタスクの完了後の状態に更新されてもよい。
【００４０】
ステップ１４：コントローラは、各パーティション・バランシング・サブタスクの実行をモニタし、既に実行されたパーティション・バランシング・サブタスクのモニタリングをキャンセルする。モニタリング方法は、以下のようにしてもよい。コントローラは、問合せ要求を各行き先ノードに周期的に送り、行き先ノードからの応答メッセージが、パーティション・バランシング・サブタスクが実行されたことを示す場合には、コントローラは、パーティション・バランシング・サブタスクの終了をマークし、パーティション・バランシング・サブタスクをもはやモニタせず、パーティション・バランシング・サブタスク・リストからパーティション・バランシング・サブタスクを削除する。そして、応答メッセージが、パーティション・バランシング・サブタスクがまだ実行されていないことを示す場合には、パーティション・バランシング・サブタスクをモニタし続ける。
【００４１】
上記の説明は、第１のパーティション・バランシング・タスクの作成および実行に関する。第２のパーティション・バランシング・タスクが、第１のパーティション・バランシング・タスクが終了した後だけ、実行され得る場合には、第２のパーティション・バランシング・タスクを、第１のパーティション・バランシング・タスクが終了する前に実行することは常に失敗する。それによって、第２のパーティション・バランシング・タスクを実行するために極端に長い待ち時間が生じ、システムの信頼性が低下する。本発明の本実施形態では、第２のパーティション・バランシング・タスクは、第１のパーティション・バランシング・タスクが終了する前に、または、第１のパーティション・バランシング・サブタスク・セットの全てのサブタスクが終了する前に実行され始める。すなわち、本発明の本実施形態では、２つのパーティション・バランシング・タスクを並行して実行してもよい。
【００４２】
ステップ１５：第２のノードには欠陥があり、コントローラは第２のパーティション・バランシング・タスクを生成する。コントローラは、第２のパーティション・バランシング・タスクに従って、第２のターゲット・パーティション分散情報を生成する。第２のターゲット・パーティション分散情報は、ノード・パーティション分散情報の少なくとも１つの部分を含む。コントローラは、現行パーティション分散情報を問い合せて、現行パーティション分散情報を第２のターゲット・パーティション分散情報と比較し、そして、現行パーティション分散情報がターゲット・パーティション分散情報になるために必要な第２のパーティション分散情報変動を見いだす。パーティション分散情報変動は、各ノードのノード・パーティション分散情報変動によって形成される。このステップは、原理に関しては、ステップ１１と同じであり、ステップ１１と相互に参照されてもよい。
【００４３】
ノードＡについて、Ｒ１は現行パーティション分散情報のノードＡのノード・パーティション分散情報を表し、Ｒ２は第２のターゲット・パーティション分散情報のノードＡのノード・パーティション分散情報を表す。それからノードＡについて、ノード・パーティション分散情報変動は、Ｒ３＝Ｒ２−（Ｒ２∩Ｒ１）となる。
【００４４】
例えば、現行パーティション分散情報のノードＡのノード・パーティション分散情報は、＜ノードＡ；パーティション１００、パーティション２００、パーティション３００、パーティション４００＞であり、第２のターゲット・パーティション分散情報のノードＡのノード・パーティション分散情報は、＜ノードＡ；パーティション３００、パーティション４００、パーティション５００、パーティション６００＞である。その場合、計算式Ｒ３＝Ｒ２−（Ｒ２∩Ｒ１）によれば、ノードＡのノード・パーティション分散情報変動は、＜ノードＡ；パーティション５００、パーティション６００＞となる。
【００４５】
ステップ１５では、ノード・パーティション分散情報変動Ｒ３を生成する２つの方法がある。１つは、Ｒ２を最初に生成し、過剰なパーティション分散情報を公式Ｒ３＝Ｒ２−（Ｒ２∩Ｒ１）を用いることによって削除する方法である。そして、もう１つは、ノード・パーティション分散情報変動を公式Ｒ３＝Ｒ２−（Ｒ２∩Ｒ１）を用いることによって最初に算出し、それから、ノード・パーティション分散情報変動を直接生成する方法である。コントローラは、ノードからパーティション・バランシング・サブタスクへの応答を受け取った後に、現行パーティション分散情報を更新するので、ステップ１５での問合せによって見いだされる現行パーティション分散情報は、ステップ１１での問合せによって見いだされる現行パーティション分散情報と異なることに留意すべきである。
【００４６】
ステップ１６：コントローラは、第２のパーティション分散情報変動に従って、第２のターゲット・パーティション分散情報を形成するために必要な移行パーティションおよび各移行パーティションが属するノードを検索し、第２のパーティション・バランシング・サブタスク・セットを生成する。第２のパーティション・バランシング・サブタスク・セットは、記憶システムのパーティション分散情報が現行パーティション分散情報から第２のターゲット・パーティション分散情報に変化するために実行される必要がある一組のパーティション・バランシング・サブタスクである。このステップは、原理に関しては、ステップ１２と同じであり、ステップ１２と相互に参照されてもよい。
【００４７】
このステップでは、コントローラが第２のパーティション・バランシング・サブタスク・セットを生成しているときに、複数の候補パーティションが移行に利用可能である場合には、データ完全性が完全であるパーティションが属するノードがソースノードとして選択され、第２のパーティション・バランシング・サブタスク・セットは、ステップ１５のパーティション分散情報変動と組み合わせて共に生成される。ステップ１５およびこのステップで完全性が完全であるパーティションが属するノードをソースノードとして選択することは、実行シーケンスに関して同時並行であってもよいし、あるいは、いずれか一方が最初に実行されてもよいことに留意すべきである。ノード欠陥によって起動されるパーティション移行タスクについては、以下のステップが、ステップ１６で特定のパーティション・バランシング・サブタスクがどのように生成されるかについて説明するための一例である。
【００４８】
（１６１）コピーマッピング規則に従って移行パーティションの全てのコピーを見いだす。例えば、マッピング規則は、以下の通りである。パーティションＰのコピーは、パーティションＰ＋１が属するノードおよびパーティションＰ＋２が属するノードに存在し、全部で３つのコピーがある。それからパーティション１０について、パーティション１０のコピーが置かれたパーティションは、パーティション１１およびパーティション１２であり、見いだされたコピーリストは｛１０，１１，１２｝である。３つのコピーのうちのいずれか１つに欠陥がある場合には、残りのパーティションのいずれか１つを用いることにより、リカバリを実行してもよい。
【００４９】
（１６２）ステップ１６１で見いだされたコピーが位置するノードの状態およびデータ完全性を検出する。ノードの状態が利用可能でない場合、または、ノードのコピーデータが不完全である場合には、そのノードをソースノードとして用いることができない。そして、ノードの状態が利用可能であり、かつ、パーティションの完全性が完全である場合には、そのノードをソースノードとして用いることができる。例えば、第１のパーティション・バランシング・サブタスク・セットにおいて、実行中のパーティション・バランシング・サブタスクに対応する移行パーティションは、不完全なパーティションである。パーティション１０に欠陥がある場合には、パーティション１０の２つのコピーのうち、パーティション１１は完全なパーティションであり、パーティション１２は不完全なパーティションである。その場合、パーティション１１が属するノードがパーティション・バランシング・サブタスクのソースノードとして用いられ、パーティション１１がパーティション移行サブタスクの移行パーティションとして用いられる。
【００５０】
（１６３）移行パーティション１１のソースノード、移行パーティションおよび行き先ノードは、ステップ１５においてノード・パーティション分散情報変動から学習されてもよい。これら３つは、パーティション移行サブタスクを互いに形成する。第２のパーティション・バランシング・サブタスク・セットのパーティション・バランシング・サブタスクは、コントローラのパーティション・バランシング・サブタスク・リストに記録されてもよい。すなわち、パーティション・バランシング・サブタスクは、ソースノード情報およびノード・パーティション分散情報変動から共に生成される。
【００５１】
ステップ１７：コントローラは、ソースノードに欠陥があるパーティション・バランシング・サブタスクおよび行き先ノードに欠陥があるパーティション・バランシング・サブタスクを、第１のパーティション・バランシング・サブタスク・セットから削除する。なぜなら、これらのパーティション・バランシング・サブタスクを完了することができず、ソースノードまたは行き先ノードの欠陥は全て第２のノードの欠陥によって生じるからである。すなわち、第２のノードに欠陥が生じる前では、これらのパーティション・バランシング・サブタスクは、完了され得るパーティション・バランシング・サブタスクであり、そして、第２のノードに欠陥が生じた後では、これらのパーティション・バランシング・サブタスクは完了され得ないパーティション・バランシング・サブタスクである。
【００５２】
ステップ１８：第２のパーティション・バランシング・サブタスク・セットと現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除する。現行のパーティション・バランシング・サブタスク・セットは、第１のパーティション・バランシング・サブタスク・セットにおいてまだ実行されていないパーティション・バランシング・サブタスクを含む。同じパーティション・バランシング・サブタスクが、第１のパーティション・バランシング・サブタスク・セットと第２のパーティション・バランシング・サブタスク・セットとの間に存在する。従って、このステップでは、パーティション・バランシング・サブタスクの反復実行を回避するために、過剰なパーティション・バランシング・サブタスクが削除される。ステップ１７およびステップ１８のいずれかが実行されてもよいし、あるいは、両方が実行されてもよい。そして、両方が実行される場合には、２つのステップの間に時系列はない。すなわち、２つのステップが同時に並行して実行されてもよいし、あるいはどちらかが最初に実行されてもよい。
【００５３】
第１のパーティション・バランシング・タスクおよび第２のパーティション・バランシング・タスクの併合は、ステップ１７およびステップ１８によって実現され、第１のパーティション・バランシング・タスクの存在は第２のパーティション・バランシング・タスクの実行を妨げない。
【００５４】
ステップ１９：コントローラは、ステップ１７およびステップ１８の処理の後、第２のパーティション・バランシング・サブタスク・セットのパーティション・バランシング・サブタスクを、行き先ノードに発行する。
【００５５】
同様に、これらの発行されたパーティション・バランシング・サブタスクは、それらのそれぞれの行き先ノードによって実行され、コントローラがそれらの完了をモニタするために、パーティション・バランシング・サブタスク・リストに記録される。コントローラおよびノードがパーティション・バランシング・サブタスクをどのように具体的に処理するかについての詳細は、ステップ１３およびステップ１４を参照してもよい。
【００５６】
ステップ２０：コントローラは、第１のパーティション・バランシング・タスクが終了したことをマークして、第１のパーティション・バランシング・タスクをモニタすることを停止してもよい。従来技術においては、パーティション・バランシング・サブタスクを受け取った後に、各ノードがコントローラに応答メッセージを返す。そして、コントローラは、パーティション・バランシング・タスクの全てのサブタスク応答メッセージを受け取った後にだけ、パーティション・バランシング・タスクが終了したことをマークすることができる。本発明の本実施形態では、応答メッセージが受け取られたかどうかを決定する必要がなく、ステップ１９が実行された後に、第１のパーティション・バランシング・タスクが終了したことをマークしてもよい。このステップは、任意選択のステップである。
【００５７】
任意選択で、パーティション・バランシング・サブタスクを受け取るノードは、パーティション・バランシング・サブタスクの行き先ノードとして、パーティション・バランシング・サブタスクを実行する。詳細な実行方法については、ステップ１３のサブステップ（１）、（２）および（３）を参照してもよい。
【００５８】
ステップ２１：全てのパーティション・バランシング・サブタスクが終了した後、コントローラは第２のパーティション・バランシング・タスクが終了したことをマークして、第２のパーティション・バランシング・タスクをモニタすることを停止してもよい。このステップは、任意選択のステップである。
【００５９】
２つのパーティション・バランシング・タスクの並列実行は、本発明の本実施形態における一例として示すものであるから、本発明の本実施形態で提供される対策は、３つ以上のパーティション・バランシング・タスクがある場合に、隣接して起動されるいかなる２つのパーティション・バランシング・タスクにも適用されてもよいことに留意すべきである。従って、本発明で提供される対策は、３つ以上のパーティション・バランシング・タスクが並行して実行される場合、例えば、３つの記憶コントローラに次々と欠陥が生じる場合にも適用する。具体的には、３つのパーティション・バランシング・タスクが次々に発生する場合には、これは本実施形態に基本的に類似し、ステップ２０の後の第３のパーティション・バランシング・タスクのためのステップ１４、すなわちステップ２１を実行することと等価であり、そして、元のステップ２１はもはや実行されない。
【００６０】
図２に示すように、本発明の一実施形態は、パーティション・バランシング・サブタスクを発行する方法を提供する。本方法はコントローラに適用され、コントローラおよび少なくとも２つのノードは記憶システムを形成し、各ノードは少なくとも１つのパーティションを含む。本方法は、第２のパーティション・バランシング・タスクが受け取られた後に、第２のパーティション・バランシング・サブタスク・セットを生成するステップであって、第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、移行パーティションが属するノード、および行き先ノードを記録するステップと、現行のパーティション・バランシング・サブタスク・セットを検索し、第２のパーティション・バランシング・サブタスク・セットと現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除するステップと、繰り返されるパーティション・バランシング・サブタスクが削除された後に、各パーティション・バランシング・サブタスクに記録された行き先ノードに対して、第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するステップと、を含む。
【００６１】
パーティション・バランシング・サブタスクを発行するステップの前に、本方法は、現行のパーティション・バランシング・サブタスク・セットから、完了され得ないパーティション・バランシング・サブタスクを削除するステップをさらに含み、完了され得ないパーティション・バランシング・サブタスクは、移行パーティションが属するノードに欠陥があるパーティション・バランシング・サブタスクと、行き先ノードに欠陥があるパーティション・バランシング・サブタスクとを含む。
【００６２】
第２のパーティション・バランシング・タスクに従って第２のパーティション・バランシング・サブタスク・セットを生成するステップは、具体的には、第２のパーティション・バランシング・タスクが受け取られた後に、記憶システムのターゲット・パーティション分散情報を算出し、記憶システムの現行パーティション分散情報を検索し、現行パーティション分散情報およびターゲット・パーティション分散情報に従ってパーティション分散情報変動を取得し、現行パーティション分散情報は、各ノードとノード上のパーティションとの間の対応を記録し、ターゲット・パーティション分散情報は、パーティション移行が実行された後に、各ノードとノード上のパーティションとの間の対応を記録し、パーティション分散情報変動は、現行パーティション分散情報がターゲット・パーティション分散情報になるために、移行する必要がある移行パーティションおよび各移行パーティションの行き先ノードを記録するステップと、各移行パーティションについて、移行パーティションが属するノードを選択し、各移行パーティションが属するノードおよびパーティション分散情報変動に従って、第２のパーティション・バランシング・サブタスク・セットを生成するステップと、を含んでもよい。
【００６３】
各移行パーティションについて、移行パーティションが属するノードを選択するステップは、具体的には、複数のパーティションが移行に利用可能である場合に、パーティションのデータ完全性を検出し、完全なデータを有する移行パーティションが属するノードを選択するステップであってもよい。
【００６４】
第２のパーティション・バランシング・サブタスク・セットを生成するステップは、具体的には、第１のパーティション・バランシング・タスクが終了する前に、計算によって、第２のパーティション・バランシング・サブタスク・セットを生成するステップであってもよく、現行のパーティション・バランシング・サブタスク・セットは、第１のパーティション・バランシング・サブタスク・セットにおいて実行されているパーティション・バランシング・サブタスクを含む。
【００６５】
発行するステップの後に、本方法は、パーティション・バランシング・サブタスクの応答メッセージが受け取られる前に、第１のパーティション・バランシング・タスクが終了したことをマークするステップをさらに含んでもよい。
【００６６】
発行するステップの後に、本方法は、パーティション・バランシング・サブタスクを受け取るノードによって、パーティション・バランシング・サブタスクの行き先ノードとしてパーティション・バランシング・サブタスクを実行するステップをさらに含んでもよい。
【００６７】
発行するステップの後に、本方法は、パーティション・バランシング・サブタスクのための記憶ノードの応答メッセージを受け取り、現行パーティション分散情報を、パーティション・バランシング・サブタスクの実行の成功後の状態に更新するステップをさらに含んでもよい。
【００６８】
図３に示すように、本発明の一実施形態は、上述した方法が適用されてもよいパーティション・バランシング・サブタスクを発行する装置２をさらに提供する。例えば、装置は、コントローラまたは制御機能を有する別の電子デバイスであってもよい。装置２は、パーティション・バランシング・サブタスク生成モジュール２１、パーティション・バランシング・サブタスク削除モジュール２２およびパーティション・バランシング・サブタスク発行モジュール２３を含む。任意選択で、装置は、パーティション・バランシング・サブタスク状態マーキングモジュール２４をさらに含んでもよい。また任意選択で、パーティション分散情報更新モジュール２５をさらに含んでもよい。
【００６９】
パーティション・バランシング・サブタスク生成モジュール２１は、第２のパーティション・バランシング・タスクが受け取られた後、第２のパーティション・バランシング・サブタスク・セットを生成するように構成され、第２のパーティション・バランシング・サブタスク・セットは、少なくとも１つのパーティション・バランシング・サブタスクを含み、各パーティション・バランシング・サブタスクは、移行パーティション、移行パーティションが属するノード、および行き先ノードを記録する。
【００７０】
パーティション・バランシング・サブタスク削除モジュール２２は、パーティション・バランシング・サブタスク生成モジュール２１に接続され、現行のパーティション・バランシング・サブタスク・セットを検索し、第２のパーティション・バランシング・サブタスク・セットと現行のパーティション・バランシング・サブタスク・セットとの間の繰り返されるパーティション・バランシング・サブタスクを削除するように構成される。
【００７１】
パーティション・バランシング・サブタスク発行モジュール２３は、パーティション・バランシング・サブタスク削除モジュール２２に接続され、繰り返されるパーティション・バランシング・サブタスクが削除された後、各パーティション・バランシング・サブタスクに記録された行き先ノードに対して、第２のパーティション・バランシング・サブタスク・セットの各パーティション・バランシング・サブタスクを発行するように構成される。
【００７２】
パーティション・バランシング・サブタスク削除モジュールは、現行のパーティション・バランシング・サブタスク・セットから、完了され得ないパーティション・バランシング・サブタスクを削除するようにさらに構成されてもよく、完了され得ないパーティション・バランシング・サブタスクは、移行パーティションが属するノードに欠陥があるパーティション・バランシング・サブタスクと、行き先ノードに欠陥があるパーティション・バランシング・サブタスクとを含む。
【００７３】
パーティション・バランシング・サブタスク生成モジュールは、具体的には、第２のパーティション・バランシング・タスクが受け取られた後に、記憶システムのターゲット・パーティション分散情報を算出し、記憶システムの現行パーティション分散情報を検索し、現行パーティション分散情報およびターゲット・パーティション分散情報に従ってパーティション分散情報変動を取得するように構成されてもよく、現行パーティション分散情報は、各ノードとノード上のパーティションとの間の対応を記録し、ターゲット・パーティション分散情報は、パーティション移行が実行された後に、各ノードとノード上のパーティションとの間の対応を記録し、パーティション分散情報変動は、現行パーティション分散情報がターゲット・パーティション分散情報になるために、移行する必要がある移行パーティションおよび各移行パーティションの行き先ノードを記録し、さらに本モジュールは、各移行パーティションについて、移行パーティションが属するノードを選択し、各移行パーティションが属するノードおよびパーティション分散情報変動に従って、第２のパーティション・バランシング・サブタスク・セットを生成するように構成されてもよい。
【００７４】
パーティション・バランシング・サブタスク生成モジュールによる、各移行パーティションについて、移行パーティションが属するノードを選択することは、具体的には、複数のパーティションが移行に利用可能である場合に、パーティションのデータ完全性を検出し、完全なデータを有する移行パーティションが属するノードを選択することである。
【００７５】
パーティション・バランシング・サブタスク生成モジュールは、具体的には、第１のパーティション・バランシング・タスクが終了する前であって第２のパーティション・バランシング・タスクが受け取られた後に、計算によって、第２のパーティション・バランシング・サブタスク・セットを生成するように構成され、現行のパーティション・バランシング・サブタスク・セットは、第１のパーティション・バランシング・サブタスク・セットにおいて実行されているパーティション・バランシング・サブタスクを含む。
【００７６】
装置２は、パーティション・バランシング・サブタスク状態マーキングモジュール２４をさらに含んでもよく、それは、パーティション・バランシング・サブタスク発行モジュールに接続され、各パーティション・バランシング・サブタスクが発行された後であってパーティション・バランシング・サブタスクの応答メッセージが受け取られる前に、第１のパーティション・バランシング・タスクが終了したことをマークするように構成される。
【００７７】
装置２は、パーティション分散情報更新モジュール２５をさらに含んでもよく、それは、記憶ノードに接続され、パーティション・バランシング・サブタスクのための記憶ノードの応答メッセージを受け取り、現行パーティション分散情報を、パーティション・バランシング・サブタスクの実行の成功後の状態に更新するように構成される。
【００７８】
図４に示すように、本発明の一実施形態は記憶システムをさらに提供し、本記憶システムは、パーティション・バランシング・サブタスクを発行するための装置および少なくとも２つのノード３を含む。ノード３は、パーティション・バランシング・サブタスクが受け取られた後、パーティション・バランシング・サブタスクの行き先ノードとしてパーティション・バランシング・サブタスクを実行するように構成される。
【００７９】
実現方法に関する上記の説明によって、本発明がソフトウェアおよび必要な汎用ハードウェアによって実現されてもよいこと、また明確にハードウェアによっても実現されてもよいことは明白であるが、しかし、多くの場合、前者が好適な実現方法である。このような理解に基づいて、本質的に本発明または従来技術に貢献する部分の技術的対策は、ソフトウェア製品の形式で実現されてもよい。コンピュータ・ソフトウェア製品は、例えばコンピュータのフロッピー（登録商標）ディスク、ハードディスクまたは光ディスクなどの可読記憶媒体に記憶され、本発明の実施形態に記載された方法を実行するようにコンピュータデバイス（パーソナルコンピュータ、サーバ、またはネットワークデバイスなどであってもよい）を指示するためのいくつかの命令を含む。
【００８０】
上記の説明は、単に本発明の特定の実現方法だけであって、本発明の保護範囲を限定することを意図するものではない。本発明において開示される技術的範囲内のいかなる者によって想到されるいかなる変形または置換であっても、本発明の保護範囲に入るものとする。従って、本発明の保護範囲は、特許請求の範囲の保護範囲に従属するものとする。
【図１】
0005914761.tif 000002
【図２】
0005914761.tif 000003
【図３】
0005914761.tif 000004
【図４】
0005914761.tif 000005