(57)【特許請求の範囲】
【請求項１】
分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するステップと、
前記パーティションの前記数についての前記平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行するステップと、
新たに追加されたパーティションと前記新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するステップとを含む、パーティション拡張方法。
【請求項２】
前記各物理ノードのパーティションの数に対する乗算を実行するステップの後に、前記方法は、
各物理ノードの各パーティションのデータのハッシュ値を取得するステップと、
前記データの前記ハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、前記データが位置している前記物理ノードのパーティションの拡張後に得られる数とを取得するステップと、
前記データの前記モジュラス値に従って、前記データが移行されることになる宛先パーティションを決定して、前記宛先パーティションが、前記データが現在位置している前記パーティションと異なる場合には、前記データを前記宛先パーティションに移行するステップとをさらに含む、請求項1に記載のパーティション拡張方法。
【請求項３】
前記各物理ノードのパーティションの数に対する乗算を実行するステップは、
各物理ノードの前記パーティションの前記数を前記パーティションの前記数の少なくとも2倍へと乗算するステップを含む、請求項1または2に記載のパーティション拡張方法。
【請求項４】
前記分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するステップは、
前記分散ストレージシステム内の前記物理ノードすべての前記パーティションの前記数についての前記平均値を周期的に取得するステップ、または
ユーザのトリガ命令に応答して、前記分散ストレージシステム内の前記物理ノードすべての前記パーティションの前記数についての前記平均値を取得するステップを含む、請求項1に記載のパーティション拡張方法。
【請求項５】
分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するように構成される、第1の取得ユニットと、
前記パーティションの前記数についての前記平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行するように構成される、第1の乗算ユニットと、
新たに追加されたパーティションと前記新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するように構成される、マッピングユニットとを備える、パーティション拡張装置。
【請求項６】
前記第1の乗算ユニットが各物理ノードの前記パーティションの前記数に対する乗算を実行した後に、各物理ノードの各パーティションのデータのハッシュ値を取得するように構成される、第2の取得ユニットと、
前記データの前記ハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、前記データが位置している前記物理ノードのパーティションの拡張後に得られる数とを取得するように構成される、第3の取得ユニットと、
前記データの前記モジュラス値に従って、前記データが移行されることになる宛先パーティションを決定して、前記宛先パーティションが、前記データが現在位置している前記パーティションと異なる場合には、前記データを前記宛先パーティションに移行するように構成される、移行ユニットとをさらに備える、請求項5に記載のパーティション拡張装置。
【請求項７】
前記第1の乗算ユニットは、各物理ノードの前記パーティションの前記数を前記パーティションの前記数の少なくとも2倍へと乗算するようにさらに構成される、請求項5または6に記載のパーティション拡張装置。
【請求項８】
前記第1の取得ユニットは、前記分散ストレージシステム内の前記物理ノードすべての前記パーティションの前記数についての前記平均値を周期的に取得するようにさらに構成される、または
ユーザのトリガ命令に応答して、前記分散ストレージシステム内の前記物理ノードすべての前記パーティションの前記数についての前記平均値を取得するようにさらに構成される、請求項5に記載のパーティション拡張装置。
【請求項９】
分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得して、前記パーティションの前記数についての前記平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行して、新たに追加されたパーティションと前記新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するように構成される、プロセッサと、
前記プロセッサによって追加された、前記新たに追加されたパーティションと前記新たに追加されたパーティションが位置している前記物理ノードとの間の前記マッピング関係を記憶するように構成される、メモリとを備える、パーティション拡張装置。
【請求項１０】
前記プロセッサは、各物理ノードの各パーティションのデータのハッシュ値を取得して、前記データの前記ハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、前記データが位置している前記物理ノードのパーティションの拡張後に得られる数とを取得して、前記データの前記モジュラス値に従って、前記データが移行されることになる宛先パーティションを決定して、前記宛先パーティションが、前記データが現在位置している前記パーティションと異なる場合には、前記データを前記宛先パーティションに移行するようにさらに構成される、請求項9に記載のパーティション拡張装置。
【請求項１１】
前記プロセッサは、各物理ノードの前記パーティションの前記数を前記パーティションの前記数の少なくとも2倍へと乗算するようにさらに構成される、請求項9または10に記載のパーティション拡張装置。
【請求項１２】
前記プロセッサは、前記分散ストレージシステム内の前記物理ノードすべての前記パーティションの前記数についての前記平均値を周期的に取得するようにさらに構成される、または
ユーザのトリガ命令に応答して、前記分散ストレージシステム内の前記物理ノードすべての前記パーティションの前記数についての前記平均値を取得するようにさらに構成される、請求項9に記載のパーティション拡張装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージ技術の分野に関し、具体的には、パーティション拡張方法および装置に関する。
【背景技術】
【０００２】
分散ストレージシステムにおいて、分散ハッシュテーブル(DHT)は、一般的に、データの記憶位置を決定するために使用される。すなわち、ハッシュ値は、ハッシュHash関数を使用することによって計算され、データは、ハッシュ値に従って、始まりと終わりが連結している巡回型空間であるハッシュ空間にマッピングされる。ハッシュリングは、各部分がパーティションと称されるいくつかの均等な部分に分割され得るし、パーティションは、物理ノードに均等に分散される。加えて、データとパーティションとの間のマッピング関係およびパーティションと物理ノードとの間のマッピング関係が、構築され、DHTに記憶される。データの読み出しおよび書き込み、分散クラスタの容量拡張、トラブルシューティングなどのすべてが、DHTの変化に依存している。したがって、DHTは、負荷が均等であり、信頼性が高く、ノード上のデータの記憶方式がデータ移行を容易にし、拡張性が高く(すなわち、容量拡張をシステムに対して複数回実行し得る)という目的を実現する必要がある。
【０００３】
従来技術では、システム容量拡張は、新規物理ノードを分散ストレージシステムに追加することによって、すなわち、物理ノードの数を増加することによって実施され得る。具体的な容量拡張方法は、分散ストレージシステムの容量拡張を実施するために、新規物理ノードをシステムに追加するステップと、元の物理ノードにあったパーティションを新規物理ノードに移動するステップとを含み得る。物理ノードのパーティションの数はおおよそ同一となる。
【０００４】
前述のシステム容量拡張を実施する処理において、発明者は、従来技術では少なくとも以下の課題が存在することを見出している。容量拡張が分散ストレージシステムに対して複数回実施されると、物理ノードのパーティションの数は低減していくことになり、システム容量拡張に影響を及ぼす(例えば、各物理ノードにパーティションが4つだけ存在している場合には、システムの容量を、最大、元の容量の4倍までしか拡張することできない)。このことは、貧弱な分散ストレージシステムの拡張性の原因となる。
【発明の概要】
【課題を解決するための手段】
【０００５】
本発明の実施形態は、分散ストレージシステムの容量拡張において物理ノードのパーティションの数を増加させることが可能であり、それによって分散ストレージシステムの拡張性を保証することができるように、パーティション拡張方法および装置を規定している。
【０００６】
前述の目的を達成するために、本発明の実施形態は、以下の技術的解決手法を採用する。
【０００７】
本発明の第1の態様の実施形態は、パーティション拡張方法を規定し、パーティション拡張方法は、
分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するステップと、
パーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行するステップと、
新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するステップとを含む。
【０００８】
第1の態様に準拠する、可能な実施形態においては、各物理ノードのパーティションの数に対する乗算を実行するステップの後に、方法は、
各物理ノードの各パーティションのデータのハッシュ値を取得するステップと、
データのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、データが位置している物理ノードのパーティションの拡張後に得られる数とを取得するステップと、
データのモジュラス値に従って、データが移行されることになる宛先パーティションを決定して、宛先パーティションが、データが現在位置しているパーティションと異なる場合には、データを宛先パーティションに移行するステップとをさらに含む。
【０００９】
第1の態様または前述の可能な実施形態に準拠する、別の可能な実施形態においては、各物理ノードのパーティションの数に対する乗算を実行するステップは、
各物理ノードのパーティションの数をパーティションの数の少なくとも2倍へと乗算するステップを含む。
【００１０】
第1の態様に準拠する、別の可能な実施形態においては、パーティションに対応する新規パーティションとパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するステップの後に、方法は、
分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得するステップと、
拡張後のパーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を再び実行するステップであって、乗算の倍数の各倍数は同一である、ステップとをさらに含む。
【００１１】
第1の態様および前述の可能な実施形態に準拠する、別の可能な実施形態においては、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するステップは、
分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を周期的に取得するステップ、または
ユーザのトリガ命令に応答して、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するステップを含む。
【００１２】
本発明の第2の態様の実施形態は、パーティション拡張装置をさらに規定し、パーティション拡張装置は、
分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するように構成される、第1の取得ユニットと、
パーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行するように構成される、第1の乗算ユニットと、
新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するように構成される、マッピングユニットとを備える。
【００１３】
第2の態様に準拠する、可能な実施形態においては、パーティション拡張装置は、
第1の乗算ユニットが各物理ノードのパーティションの数に対する乗算を実行した後に、各物理ノードの各パーティションのデータのハッシュ値を取得するように構成される、第2の取得ユニットと、
データのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、データが位置している物理ノードのパーティションの拡張後に得られる数とを取得するように構成される、第3の取得ユニットと、
データのモジュラス値に従って、データが移行されることになる宛先パーティションを決定して、宛先パーティションが、データが現在位置しているパーティションと異なる場合には、データを宛先パーティションに移行するように構成される、移行ユニットとをさらに備える。
【００１４】
第2の態様または前述の可能な実施形態に準拠する、別の可能な実施形態においては、第1の乗算ユニットは、各物理ノードのパーティションの数をパーティションの数の少なくとも2倍へと乗算するようにさらに構成される。
【００１５】
第2の態様に準拠する、別の可能な実施形態においては、パーティション拡張装置は、
マッピングユニットが新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加した後に、分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得するように構成される、第4の取得ユニットと、
拡張後のパーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を再び実行するように構成される第2の乗算ユニットであって、乗算の倍数の各倍数は同一である、第2の乗算ユニットとをさらに備える。
【００１６】
第2の態様に準拠する、別の可能な実施形態においては、第1の取得ユニットは、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を周期的に取得するようにさらに構成される、または
ユーザのトリガ命令に応答して、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するようにさらに構成される。
【００１７】
本発明の第3の態様の実施形態は、パーティション拡張装置をさらに規定し、パーティション拡張装置は、
分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得して、パーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行して、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するように構成される、プロセッサと、
プロセッサによって追加された、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を記憶するように構成される、メモリとを備える。
【００１８】
第3の態様に準拠する、可能な実施形態においては、プロセッサは、各物理ノードの各パーティションのデータのハッシュ値を取得して、データのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、データが位置している物理ノードのパーティションの拡張後に得られる数とを取得して、データのモジュラス値に従って、データが移行されることになる宛先パーティションを決定して、宛先パーティションが、データが現在位置しているパーティションと異なる場合には、データを宛先パーティションに移行するようにさらに構成される。
【００１９】
第2の態様に準拠する、別の可能な実施形態においては、プロセッサは、各物理ノードのパーティションの数をパーティションの数の少なくとも2倍へと乗算するようにさらに構成される。
【００２０】
第2の態様に準拠する、別の可能な実施形態においては、プロセッサは、パーティションに対応する新規パーティションとパーティションが位置している物理ノードとの間のマッピング関係がDHTに追加された後に、分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得して、拡張後のパーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を再び実行するようにさらに構成され、乗算の倍数の各倍数は同一である。
【００２１】
第2の態様に準拠する、別の可能な実施形態においては、プロセッサは、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を周期的に取得するようにさらに構成される、または
ユーザのトリガ命令に応答して、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するようにさらに構成される。
【００２２】
本発明の実施形態に規定したパーティション拡張方法および装置では、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値は取得され得るし、パーティションの数についての平均値がプリセット閾値未満である場合には、乗算は各物理ノードのパーティションの数に対して実行され得るし、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係は事前に記憶されている分散ハッシュテーブルDHTに追加され得る。物理ノードのパーティションの数が少ないことにより分散ストレージシステムの拡張性が乏しい従来技術と比較して、本発明の実施形態に規定したパーティション拡張方法および装置では、パーティションの数がプリセット閾値未満である場合には、分散ストレージシステムの容量拡張においてパーティションの数に対する乗算を実行することが可能であり、それによって分散ストレージシステムの拡張性を保証している。
【００２３】
本発明の実施形態または従来技術における技術的解決手法をより明確に記載するために、実施形態または従来技術を記載するにあたり必要となる添付の図面を以下に簡単に説明する。以下の記載における添付の図面は本発明の実施形態のいくつかを示したものにすぎず、当業者は創造的努力をすることなくこれらの添付の図面から他の図面をさらに導出し得ることは明らかであろう。
【図面の簡単な説明】
【００２４】
【図１】本発明の実施形態1によるパーティション拡張方法のフローチャートである。
【図２】本発明の実施形態2によるパーティション拡張方法のフローチャートである。
【図３】本発明の実施形態3によるパーティション拡張装置の概略構造図である。
【図４】本発明の実施形態3によるパーティション拡張装置の別の概略構造図である。
【図５】本発明の実施形態4によるパーティション拡張装置の概略構造図である。
【発明を実施するための形態】
【００２５】
本発明の実施形態の添付の図面を参照して本発明の実施形態の技術的解決手法を以下に明確かつ十分に記載する。記載した実施形態は一部にすぎず、本発明の実施形態のすべてではないことは明らかであろう。創造的努力をすることなく本発明の実施形態に基づいて当業者によって得られる他の実施形態のすべては、本発明の保護範囲に含まれるものとする。
【００２６】
実施形態1
本発明の実施形態は、パーティション拡張方法を規定する。図1に示したように、方法は、以下のステップを含む。
【００２７】
101. パーティション拡張装置が、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得する。
【００２８】
分散ハッシュテーブル(Distributed Hash Table、DHT)を使用してデータを記憶している場合には、分散ストレージシステムは、異なるデータのデータ識別子に従い、ハッシュ関数を使用することによって、データ識別子に対応するデータのハッシュ値Hashを計算し得る。データは、ハッシュ値に従って、始まりと終わりが連結している巡回型空間であるハッシュ空間にマッピングされる。ハッシュリングは、各部分がパーティションと称されるいくつかの均等な部分に分割され得るし、パーティションは、物理ノードに均等に分散される。物理ノードは、分散ストレージシステムの物理アドレスであってもよい。分散ストレージシステムは、分散ストレージシステムの物理アドレスを複数のアドレスセグメントに分割してもよいし、物理アドレスの各セグメントは、物理ノードである。
【００２９】
パーティション拡張装置によって、分散ストレージシステム内の物理ノードのパーティションの数についての平均値を取得するための方法は、パーティション拡張装置によって、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を周期的に取得するステップ、またはパーティション拡張装置によって、ユーザのトリガ命令に応答して、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するステップを含み得る。具体的には、パーティション拡張装置は、取得期間を事前に設定して、その期間に従って、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を自発的に取得してもよい。また、分散ストレージシステムの容量拡張を実行した場合には、パーティション拡張装置は、ユーザのトリガ命令を受信して、トリガ命令に応答して、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得する。
【００３０】
102. パーティションの数についての平均値がプリセット閾値未満である場合には、パーティション拡張装置が、各物理ノードのパーティションの数に対する乗算を実行する。
【００３１】
容量拡張が分散ストレージシステムに対して少なくとも一回実行されると、プリセット閾値が、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を満たす値に設定され得る。
【００３２】
パーティション拡張装置が各物理ノードのパーティションの数に対する乗算を実行した後に、本発明の本実施形態における方法は、パーティション拡張装置によって、各物理ノードの各パーティションのデータのハッシュ値を取得するステップと、パーティション拡張装置によって、データのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、データが位置している物理ノードのパーティションの拡張後に得られる数とを取得するステップと、パーティション拡張装置によって、データのモジュラス値に従って、データが移行されることになる宛先パーティションを決定して、宛先パーティションが、データが現在位置しているパーティションと異なる場合には、パーティション拡張装置によって、データを宛先パーティションに移行するステップとをさらに含む。
【００３３】
103. パーティション拡張装置が、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されているDHTに追加する。
【００３４】
分散ストレージシステムにおいて、DHTは、データの記憶位置を決定するために使用され得る。すなわち、DHTは、データ識別子とパーティションとの間のマッピング関係およびパーティションと物理ノードとの間のマッピング関係を記憶し得る。したがって、各物理ノードのパーティションの数に対する乗算を実行するステップの後に、パーティション拡張装置は、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されているDHTに追加する必要がさらにある。
【００３５】
本発明の本実施形態に規定したパーティション拡張方法においては、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値は取得され得るし、パーティションの数についての平均値がプリセット閾値未満である場合には、乗算は各物理ノードのパーティションの数に対して実行され得るし、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係は事前に記憶されている分散ハッシュテーブルDHTに追加され得る。物理ノードのパーティションの数が少ないことにより分散ストレージシステムの拡張性が乏しい従来技術と比較して、本発明の本実施形態に規定したパーティション拡張方法においては、パーティションの数がプリセット閾値未満である場合には、分散ストレージシステムの容量拡張においてパーティションの数に対する乗算を実行することが可能であり、それによって分散ストレージシステムの拡張性を保証している。
【００３６】
実施形態2
本発明の実施形態は、パーティション拡張方法を規定する。図2に示したように、方法は、以下のステップを含む。
【００３７】
201. パーティション拡張装置が、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得する。
【００３８】
例えば、パーティション拡張装置によって、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するための方法とは、具体的には、以下のように、パーティション拡張装置が、事前に記憶されているDHTにおいて、分散ストレージシステム内の物理ノードの数と、全物理ノードのパーティションの総数とを問い合わせ、パーティション拡張装置が、物理ノードの数と、全物理ノードのパーティションの総数とに従って、物理ノードのパーティションの数についての平均値を計算することであり得る。
【００３９】
物理ノードの数は、分散ストレージシステム内の物理ノードの総数である。パーティション拡張装置によって、物理ノードの数と、全物理ノードのパーティションの総数とに従って、物理ノードのパーティションの数についての平均値を計算する方法とは、具体的には、以下のように、全物理ノードのパーティションの総数を物理ノードの数で除算することによって、パーティション拡張装置によって得られる商を物理ノードのパーティションの数についての平均値として使用することである。例えば、物理ノードの数がA、全物理ノードのパーティションの総数がB、物理ノードのパーティションの数についての平均値がCであるとすると、物理ノードの数、全物理ノードのパーティションの総数、および物理ノードのパーティションの数についての平均値は、C=A/Bという数式を満たさなければならない。
【００４０】
さらに、本実施形態のある適用状況においては、分散ストレージシステムがDHTを使用してデータを記憶している場合には、物理ノードのパーティションの数はおおよそ同一となる。したがって、パーティション拡張装置は、事前に記憶されているDHTにおいて、分散ストレージシステム内の任意の物理ノードのパーティションの数を問い合わせて、物理ノードのパーティションの数を分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値として使用してもよい。
【００４１】
202. パーティション拡張装置が、パーティションの数についての平均値がプリセット閾値未満であるかどうかを決定して、パーティションの数についての平均値がプリセット閾値未満である場合にはステップ203を実行し、またパーティションの数についての平均値がプリセット閾値未満ではない場合にはステップ211を実行する。
【００４２】
203. パーティション拡張装置が、各物理ノードのパーティションの数に対する乗算を実行する。
【００４３】
パーティション拡張装置が各物理ノードのパーティションの数に対する乗算を実行することは、パーティション拡張装置によって、各物理ノードのパーティションの数をパーティションの数の少なくとも2倍へと乗算することを含み得る。
【００４４】
具体的には、パーティション拡張装置は、事前に記憶されているDHT内の各物理ノードのパーティションの数を各物理ノードにおいてパーティションの数の少なくとも2倍へと修正してもよい。
【００４５】
一般的に、パーティション拡張装置が各物理ノードのパーティションの数に対する乗算を実行する場合には、パーティションの数に対する乗算の倍数は2であることに留意されたい。当然のことながら、パーティション拡張装置は、各物理ノードのパーティションの数に対して3倍以上の拡張を実行してもよい。パーティション拡張装置が各物理ノードのパーティションの数に対して2倍の拡張を実行することを、本発明の本実施形態における一例として用いている。しかしながら、各物理ノードのパーティションの数に対するパーティション拡張装置によって実行される乗算の倍数は限定されない。
【００４６】
204. パーティション拡張装置が、各物理ノードの各パーティションのデータのハッシュ値を取得する。
【００４７】
具体的には、パーティション拡張装置は、事前に記憶されているDHTにおいて、各パーティションのデータの識別子に従って、各物理ノードの各パーティションのデータのハッシュ値を問い合わせ得る。パーティション中の異なるデータのハッシュ値は異なる。例えば、パーティションは、データ1と、データ2と、データ3とを含む。データ1のデータ識別子はaでありハッシュ値はHash1である、データ2のデータ識別子はbでありハッシュ値はHash2である、およびデータ3のデータ識別子はcでありハッシュ値はHash3である。
【００４８】
205. パーティション拡張装置が、データのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、データが位置している物理ノードのパーティションの拡張後に得られる数とを取得する。
【００４９】
データが位置している物理ノードのパーティションの拡張後に得られる数は、データが位置している物理ノードのパーティションの拡張前の数を各物理ノードのパーティションの数に対するパーティション拡張装置によって実行される乗算の倍数で乗算することによって得られる積である。
【００５０】
例えば、データKのハッシュ値がHashkであり、データKが位置している物理ノードのパーティションの数がNであり、パーティション拡張装置が各物理ノードのパーティションの数に対してn倍の乗算を実行する場合には、データKが位置している物理ノードのパーティションの拡張後に得られる数はn×Nであり、データKのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値はxkであり、データKが位置している物理ノードのパーティションの拡張後に得られる数はxk=Hashk%(n×N)という数式に基づいた計算によって得られ得る。
【００５１】
206. パーティション拡張装置が、データのモジュラス値に従って、データが移行されることになる宛先パーティションを決定して、宛先パーティションが、データが現在位置しているパーティションと異なる場合には、データを宛先パーティションに移行する。
【００５２】
分散ストレージシステムがデータを記憶する場合には、記憶されることになるデータのハッシュ値Hashは、ハッシュ関数に従って計算され得るし、記憶されることになるデータは、記憶されることになるデータの一部の各々のハッシュ値と分散ストレージシステム内のパーティションの総数とに従って、各記憶用パーティションに分散され、そして分散ストレージシステム内のパーティションは、各物理ノードに均等に分散される。
【００５３】
例えば、いくつかのデータのハッシュ値Hashがそれぞれ、45、46、47、48、…、75であり、パーティションの数がNであるとすると、データの一部の各々のハッシュ値に対するモジュロ演算から得られる結果とパーティションの数とが同一であるデータは、同一のパーティションに分散される、例えば、Hash%Nという数式において、N=3の場合には、データのハッシュ値およびパーティションの数に対するモジュロ演算から得られる剰余は、それぞれ、0、1、2、0、1、2、0、1、2、0、1、2 … 0、1、2、0である。データは、モジュロ演算により得られた剰余に従って、以下の3つのパーティションに分散され得る。
パーティション1(剰余が0):45、48、51、54、57、60、63、66、69、72、75
パーティション2(剰余が1):46、49、52、55、58、61、64、67、70、73
パーティション3(剰余が2):47、50、53、56、59、62、65、68、71、74
【００５４】
例えば、前述のパーティション1を、一例として使用して、パーティション拡張を実行する。この場合には、パーティションの数Nは3である。パーティションの数に対する乗算の倍数nがn=2である場合には、パーティション1が位置している物理ノードのパーティションの拡張後の数は、2×3であり、パーティション1の全データのモジュラス値は、それぞれ、x45=45%(2×3)=3、x48=48%(2×3)=0、x51=51%(2×3)=3、x54=54%(2×3)=0、x57=57%(2×3)=3 … x72=72%(2×3)=0、およびx75=75%(2×3)=3である。
【００５５】
具体的には、パーティションの数に対する乗算の倍数nがn=2である場合には、パーティション拡張装置は、モジュラス値が3であるデータを、新たに追加されたデータが位置している物理ノードのパーティションに移行して、モジュラス値が0であるデータを、元のパーティションで保持してもよい。例えば、パーティション拡張装置は、x45=45%(2×3)=3、x51=51%(2×3)=3、x57=57%(2×3)=3 … x75=75%(2×3)=3に対応するデータを、新たに追加されたデータが位置している物理ノードのパーティションに移行して、x48=48%(2×3)=0、x54=54%(2×3)=0 … x72=72%(2×3)=0に対応するデータを、元のパーティションで保持してもよい。あるいは、パーティション拡張装置は、モジュラス値が0であるデータを、新たに追加されたデータが位置している物理ノードのパーティションに移行して、モジュラス値が3であるデータを、元のパーティションで保持してもよい。例えば、パーティション拡張装置は、x48=48%(2×3)=0、x54=54%(2×3)=0 … x72=72%(2×3)=0に対応するデータを、新たに追加されたデータが位置している物理ノードのパーティションに移行して、x45=45%(2×3)=3、x51=51%(2×3)=3、x57=57%(2×3)=3 … x75=75%(2×3)=3に対応するデータを、元のパーティションで保持してもよい。
【００５６】
前述のパーティション1は一例として使用されていることに留意されたい。パーティションの数に対する乗算の倍数nがn=3である場合には、パーティション1のデータの一部のモジュラス値は、それぞれ、x45=45%(3×3)=0、x48=48%(3×3)=3、x51=51%(3×3)=6、x54=54%(3×3)=0、x57=57%(3×3)=3 … x72=72%(3×3)=0、およびx75=75%(3×3)=3である。パーティション拡張装置は、データのモジュラス値0、3、および6に従って、モジュラス値に対応するデータを移行してもよい。パーティション拡張装置によって、データを宛先パーティションに移行するための方法は、パーティションの数を2倍に乗算するための方法と同様であり、その詳細を本実施形態においては再度記載しない。
【００５７】
207. パーティション拡張装置が、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されているDHTに追加する。
【００５８】
208. パーティション拡張装置が、分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得する。
【００５９】
分散ストレージシステム内の物理ノードすべてのパーティションの数に対する乗算を実行して、パーティションの対応するデータの移行が完了した後に、パーティション拡張装置は、分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得して、取得した平均値に従って、少なくとも一回拡張を実行するために分散ストレージシステム内のパーティションの数が分散ストレージシステムによって必要とされるパーティションの数を満たすかどうかを決定し得る。
【００６０】
パーティション拡張装置によって、分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得するための方法は、本実施形態においては、パーティション拡張装置によって、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するための方法と同様であり、その詳細を本実施形態においては再度記載しないことに留意されたい。
【００６１】
209. パーティション拡張装置が、拡張後のパーティションの数についての平均値がプリセット閾値未満であるかどうかを決定して、拡張後のパーティションの数についての平均値がプリセット閾値未満である場合にはステップ210を実行して、または拡張後のパーティションの数についての平均値がプリセット閾値未満ではない場合にはステップ211を実行する。
【００６２】
210. パーティション拡張装置が、乗算の倍数の各倍数が同一である、各物理ノードのパーティションの数に対する乗算を再び実行する。
【００６３】
拡張後のパーティションの数についての平均値がプリセット閾値未満である場合には、パーティション拡張装置は、各物理ノードのパーティションの数に対する乗算を再び実行してもよい。各物理ノードのパーティションの数に対するパーティション拡張装置によって再び実行される乗算の乗算倍数は、パーティションの数に対するパーティション拡張装置によって一回目に実行された乗算の乗算倍数と同一である。
【００６４】
パーティション拡張装置が各物理ノードのパーティションの数に対する乗算を再び実行した後に、本実施形態の方法は、パーティション拡張装置によって、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されているDHTに追加することをさらに含み得る。
【００６５】
パーティション拡張装置は物理ノードのパーティションの数に対する乗算を少なくとも一回実行し得るし、乗算の倍数の各倍数は同一であり、乗算の倍数は2以上であることに留意されたい。
【００６６】
211. パーティション拡張処理を終了する。
【００６７】
パーティション拡張装置は、分散ストレージシステム内の物理ノードのパーティションの数についての平均値に従って、分散ストレージシステム内の物理ノードのパーティションに対する拡張を少なくとも一回実行し得ることに留意されたい。パーティション拡張の回数は、本発明の本実施形態に限定されない。パーティション拡張装置によって、分散ストレージシステム内の物理ノードのパーティションに対して二回以上拡張を実行するための方法は、本実施形態においては、パーティション拡張方法と同様であり、その詳細を本実施形態においては再度記載しない。
【００６８】
さらに、本実施形態に規定した乗算方法は分散ストレージシステムのパーティション拡張処理だけに適用され得るのではなく別のストレージシステム内のストレージノードの乗算処理にも適用され得るし、本発明の方法の適用範囲は本実施形態に限定されないことに留意されたい。
【００６９】
本発明の本実施形態に規定したパーティション拡張方法においては、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値は取得され得るし、パーティションの数についての平均値がプリセット閾値未満である場合には、乗算は各物理ノードのパーティションの数に対して実行され得るし、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係は事前に記憶されている分散ハッシュテーブルDHTに追加され得る。物理ノードのパーティションの数が少ないことにより分散ストレージシステムの拡張性が乏しい従来技術と比較して、本発明の本実施形態に規定したパーティション拡張方法においては、パーティションの数がプリセット閾値未満である場合には、分散ストレージシステムの容量拡張においてパーティションの数に対する乗算を実行することが可能であり、それによって分散ストレージシステムの拡張性を保証している。
【００７０】
実施形態3
本発明の本実施形態は、パーティション拡張装置を規定する。図3に示したように、装置は、第1の取得ユニット31と、第1の乗算ユニット32と、マッピングユニット33とを備える。
【００７１】
第1の取得ユニット31は、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するように構成される。
【００７２】
第1の乗算ユニット32は、パーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行するように構成される。
【００７３】
マッピングユニット33は、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するように構成される。
【００７４】
図4に示したように、パーティション拡張装置は、第2の取得ユニット34と、第3の取得ユニット35と、移行ユニット36とをさらに備える。
【００７５】
第2の取得ユニット34は、第1の乗算ユニット32が各物理ノードのパーティションの数に対する乗算を実行した後に、各物理ノードの各パーティションのデータのハッシュ値を取得するように構成される。
【００７６】
第3の取得ユニット35は、データのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、データが位置している物理ノードのパーティションの拡張後に得られる数とを取得するように構成される。
【００７７】
移行ユニット36は、データのモジュラス値に従って、データが移行されることになる宛先パーティションを決定して、宛先パーティションが、データが現在位置しているパーティションと異なる場合には、データを宛先パーティションに移行するように構成される。
【００７８】
第1の乗算ユニット32は、各物理ノードのパーティションの数をパーティションの数の少なくとも2倍へと乗算するようにさらに構成される。
【００７９】
パーティション拡張装置は、第4の取得ユニット37と、第2の乗算ユニット38とをさらに備える。
【００８０】
第4の取得ユニット37は、マッピングユニット33が新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加した後に、分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得するように構成される。
【００８１】
第2の乗算ユニット38は、拡張後のパーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を再び実行するように構成され、乗算の倍数の各倍数は同一である。
【００８２】
第1の取得ユニット31は、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を周期的に取得するようにさらに構成される、またはユーザのトリガ命令に応答して、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するようにさらに構成される。
【００８３】
本発明の本実施形態に規定したパーティション拡張装置におけるいくつかの関数モジュールの特定の記載に関しては、方法の実施形態における対応する内容を参照し、その詳細を本実施形態においては再度記載しないことに留意されたい。
【００８４】
本発明の本実施形態に規定したパーティション拡張装置は、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得して、パーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行して、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加することが可能である。物理ノードのパーティションの数が少ないことにより分散ストレージシステムの拡張性が乏しい従来技術と比較して、パーティションの数がプリセット閾値未満である場合には、本発明の本実施形態に規定したパーティション拡張装置は、分散ストレージシステムの容量拡張においてパーティションの数に対する乗算を実行することが可能であり、それによって分散ストレージシステムの拡張性を保証している。
【００８５】
実施形態4
本発明の実施形態は、パーティション拡張装置を規定する。図5に示したように、装置は、プロセッサ41と、メモリ42とを備え得る。
【００８６】
プロセッサ41は、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得して、パーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行して、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加するように構成される。
【００８７】
メモリ42は、プロセッサ41によって追加された新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を記憶するように構成される。
【００８８】
プロセッサ41は、各物理ノードの各パーティションのデータのハッシュ値を取得して、データのハッシュ値に対するモジュロ演算を実行することによって得られるモジュラス値と、データが位置している物理ノードのパーティションの拡張後に得られる数とを取得して、データのモジュラス値に従って、データが移行されることになる宛先パーティションを決定して、宛先パーティションが、データが現在位置しているパーティションと異なる場合には、データを宛先パーティションに移行するようにさらに構成される。
【００８９】
プロセッサ41は、各物理ノードのパーティションの数をパーティションの数の少なくとも2倍へと乗算するようにさらに構成される。
【００９０】
プロセッサ41は、パーティションに対応する新規パーティションとパーティションが位置している物理ノードとの間のマッピング関係がDHTに追加された後に、分散ストレージシステム内の物理ノードすべてのパーティションの拡張後に得られる数についての平均値を取得して、拡張後のパーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を再び実行するようにさらに構成され、乗算の倍数の各倍数は同一である。
【００９１】
プロセッサ41は、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を周期的に取得するようにさらに構成される、またはユーザのトリガ命令に応答して、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得するようにさらに構成される。
【００９２】
本発明の本実施形態に規定したパーティション拡張装置におけるいくつかの関数モジュールの特定の記載に関しては、方法の実施形態における対応する内容を参照し、その詳細を本実施形態においては再度記載しないことに留意されたい。
【００９３】
本発明の本実施形態に規定したパーティション拡張装置は、分散ストレージシステム内の物理ノードすべてのパーティションの数についての平均値を取得して、パーティションの数についての平均値がプリセット閾値未満である場合には、各物理ノードのパーティションの数に対する乗算を実行して、新たに追加されたパーティションと新たに追加されたパーティションが位置している物理ノードとの間のマッピング関係を事前に記憶されている分散ハッシュテーブルDHTに追加することが可能である。物理ノードのパーティションの数が少ないことにより分散ストレージシステムの拡張性が乏しい従来技術と比較して、パーティションの数がプリセット閾値未満である場合には、本発明の本実施形態に規定したパーティション拡張装置は、分散ストレージシステムの容量拡張においてパーティションの数に対する乗算を実行することが可能であり、それによって分散ストレージシステムの拡張性を保証している。
【００９４】
実施形態の前述の記載に基づいて、本発明が、必要となる汎用ハードウェアとともにソフトウェアによって、またはハードウェアのみによって、実装され得ることを、当業者は明確に理解されよう。大抵の状況においては、前者が望ましい実施形態である。そのような理解に基づけば、従来技術に対して本質的にまたは部分的に貢献する本発明の技術的解決手法は、ソフトウェア製品の形式で実装されてもよい。ソフトウェア製品は、コンピュータのフロッピー(登録商標)ディスク、ハードディスク、または光学ディスクなどのコンピュータ可読記憶媒体に記憶され、コンピュータデバイス(パーソナルコンピュータ、サーバ、またはネットワークデバイスであり得る)に本発明の実施形態に記載の方法を実行するように指示するためのいくつかの命令を含む。
【００９５】
前述の記載は、特定の本発明の実施形態を記載したものにすぎず、本発明の保護範囲を限定することを意図したものではない。本発明に記載の技術的範囲において当業者が用意に想到する任意の変形または置換は、本発明の保護範囲に含まれるものとする。したがって、本発明の保護範囲は、特許請求の範囲の保護範囲に従うものとする。
【符号の説明】
【００９６】
31  第1の取得ユニット
32  第1の乗算ユニット
33  マッピングユニット
34  第2の取得ユニット
35  第3の取得ユニット
36  移行ユニット
37  第4の取得ユニット
38  第2の乗算ユニット
41  プロセッサ
42  メモリ
【図１】
0006020867.tif 000002
【図２】
0006020867.tif 000003
【図３】
0006020867.tif 000004
【図４】
0006020867.tif 000005
【図５】
0006020867.tif 000006