データ復元方法及びサーバ装置
【課題】分散型データストレージシステムにおけるデータ復元方法及び装置を提供すること。
【解決手段】本発明は一般に分散型データストレージシステムに関連する。特に本発明は所望のデータ復元レベルを保証するのに必要なデータの観点から分散型データストレージシステムを最適化することに関連する。
【解決手段】本発明は一般に分散型データストレージシステムに関連する。特に本発明は所望のデータ復元レベルを保証するのに必要なデータの観点から分散型データストレージシステムを最適化することに関連する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は一般に分散型データストレージシステムに関連する。特に本発明は所望のデータ復元レベルを保証するのに必要なデータの観点から分散型データストレージシステムを最適化することに関連する。
【背景技術】
【０００２】
ビデオ及びイメージを処理する装置のような大容量データ処理装置の急速な普及とともに、直接的な保存又はバックアップ保存の一環として、膨大なデータ量を安心して格納することが求められている。ネットワーク接続機能を備えたデバイスが益々増加するにつれて、ネットワークで接続されたデバイスにデータを分散して保存することは、費用対効果に優れた手段であると考えられる。そのような分散型データストレージシステムにおいて、一時的な又は永久的なデータ損失(ロス、欠落、欠陥等)に対するデータの安定供給性及び復元性を保証するために、分散型データストレージネットワーク内の複数のネットワーク接続装置に同じデータ項目をコピーする方法が使用されている。これはデータ復元又はデータレプリケーション(data replication)と呼ばれる。データレプリケーションという用語は広義に解釈する必要があり、単にデータを復元(回復、再現、反復、複製等)するだけでなく、符号又はコードを消去又は再生成するような符号化技術(コーディング技術)を利用することも包含する。装置の故障や装置が利用可能でないことに起因する永続的又は一時的なデータロスに対処する観点からは、レプリケーション因子(replication factor)は大きいことが望ましい(すなわち、複製数は大きいことが望ましい)。しかしながら、必要な通信サイズや保存容量等によるコスト(いわゆる「レプリケーションコスト」)を減らす観点からは、レプリケーション因子は小さいことが望ましい。
【０００３】
従って、分散した保存データのデータ利用性を高く維持し、データ損失に対する耐性及びレプリケーションコストをともに考慮する解決手段が望まれている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の課題は従来技術における問題を軽減することである。
【課題を解決するための手段】
【０００５】
本発明の一形態による方法は、
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元方法であって、
保存するデータ項目各々について、前記分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現するレプリケーション集合を選択するステップであって、前記所定数個(k個)のストレージ装置は前記データ項目を保存するために選択されており、前記所定数kはレプリケーションレベルを表す、ステップと、
前記レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定するステップであって、該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると止まり、前記タイマが満了すると前記ストレージ装置は切断されたものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でなかった期間を表す、ステップと、
少なくとも1つの前記ストレージ装置が切断されたと判断された場合において、前記レプリケーション集合に属する接続されているストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために新たに選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元するステップと
を有するデータ復元方法である。
【図面の簡単な説明】
【０００６】
【図１】本発明の一形態に相応しい分散型ストレージネットワークアーキテクチャを示す図。
【図２】典型的なピアの休止時間の分布を示す図。
【図３】本発明の一形態による方法を実行する装置の一例を示す図。
【図４】図1の何れかの装置10-16等により実行される本発明による特定の動作例のアルゴリズムを示す図。
【発明を実施するための形態】
【０００７】
ピアトゥピアネットワークのような分散型データネットワーク(distributed data network)の場合、デバイスは継続的にネットワークに出入りしている。分散型データ保存ネットワークの一部をなすデバイスがそのネットワークから本当に又は確実に(definitely)に去ってしまった場合、データ復元レベル又はデータレプリケーションレベルは減少する。データ複製方式による分散型データストレージシステム(data duplication based distributed data storage system)の場合、同じデータ項目を保存しているまだ利用可能な他のデバイスから複製した新たなデータ項目を、ネットワーク内の新たな又は既存のデバイスに設けることで、データ復元レベルは回復する。コードを消去又は再生成することに基づく分散型データストレージシステムの場合、データ項目を複製するのにまだ使用可能な他のデバイスから生成されたデータである新たなデータ項目を、ネットワークの新たな又は既存のデバイスに作成することで、データ復元レベルが回復する。しかしながらデバイスの離脱は必ずしも確定的なものではなく、デバイスを利用できないことは単なる一時的なことかもしれない。従って問題は、デバイスの離脱に起因して減少したデータ復元レベルの復旧を適切な時点で促すために、デバイスが分散型データストレージシステムを本当に離脱してしまったことを如何にして判断するか、ということである。デバイスの単なる一時的な離脱に起因して減少したレプリケーションレベルを復元すると、そのような復元(restoring)は無駄なものであり、ストレージ容量やネットワーク通信等の観点から分散型データストレージシステムのリソースを不必要に浪費してしまうことになる。
【０００８】
分散型データストレージシステムの一部をなすデバイスの動き(振る舞い、挙動、行動、素行等)を観察すると、デバイスは各自自身の接続挙動(connectivity behavior)を有することが分かる。例えば、或るデバイスは常時接続され、別のデバイスは日中の間だけ接続されて夜間は分離され、更に別のデバイスは規則性のない接続挙動を有する。非特許文献1は、ノード毎の不具合の検出は困難であることに言及し、その代わりにノードのグループ毎にデータの利用可能性を予測することを提案している。しかしながらこの非特許文献1に記載されているようにして個々のノードの情報をグループ化すると、グループに属する個々のノードの挙動の情報は失われるので、この文献に記載されている方法は非効率的であり、不要な復元を行うことになってしまう。これに対して本発明は、個々のデバイスの接続挙動に関する情報を活用できるようにし、デバイスが分散型データストレージネットワークを本当に離脱したと推定できる時点を判定し、データ項目の新たな生成を適切な時点で促し、分散型データストレージネットワークのリソースを最適に利用できるようにする。このような判定を行うために本発明は中断時間又はタイムアウト(timeout)を使用し、タイムアウトの値はデバイスの休止時間(downtime)の分布を表す関数により決定され、休止時間の分布はデバイスについて測定された利用可能性挙動(availability behavior)に基づいている。デバイスが離脱した場合、所定の期間についてタイムアウトが計測され始める。タイムアウトが満了する前にデバイスが再接続されると、タイムアウトはリセットされる。しかしながらタイムアウト期間が満了すると、デバイスは分散型データストレージシステムを本当に離脱したと判断され、新たなデータ項目を新たな又は既存のデバイスに作成することで、レプリケーションレベルを復旧する処理から成る復元処理が開始される。新たなデータ項目は、データ項目を保存している残りのデバイスの内の1つ以上の中から複製(データデュプリケーションに基づくデータ復元の場合)又は生成(コードの消去又は再生成に基づくデータ復元の場合)される。従って、偏りのない適切な(fair)タイムアウト期間を決定することが重要である。タイムアウト値が短すぎた場合、一時的な離脱が永久的な離脱と判断されるので、過剰に多くの不要な「復元(repair)」が行われてしまうことになる。不要な復元が多いと、分散型データストレージシステムの輻輳を招くおそれがある。これに対して、タイムアウト値が過剰に長かった場合、タイムアウトの満了前に、いくつかの永久的な離脱が生じると、データの持続性(persistence)が脅かされてしまう。このため本発明ではデバイスの個々の接続挙動に関する情報を活用して、個々のデバイスの接続挙動に適合するタイムアウト期間を決定する。本発明においては、分散型データストレージシステムのデバイス各々のダウンタイムに関連するデータが収集される。
【０００９】
［1］分散型データストレージシステムにおけるデータ復元を最適化する本発明による方法は、
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元方法である。本方法は少なくとも以下のステップを有する：
＿データ項目の保存各々について、レプリケーション集合を選択するステップ。レプリケーション集合は、分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現し、所定数個のストレージ装置はデータ項目を保存するために選択されている。所定数kはレプリケーションレベルを表す。
【００１０】
＿レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定するステップ。該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると終了し、前記タイマが満了すると前記ストレージ装置は切断された(disconnected)ものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でない期間を表す。
【００１１】
＿前記ストレージ装置の内の少なくとも1つが切断されたと判断された場合において、前記レプリケーション集合に属する接続中のストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元するステップ。
【００１２】
［2］本発明の一形態による方法は、前記ストレージ装置に関連する前記タイマが満了した後、前記ストレージ装置が前記分散型データストレージシステムに再接続した場合に、前記ストレージ装置が属していたレプリケーション集合にストレージ装置を復帰させるステップを更に有する。
【００１３】
［3］本発明の一形態による方法において、前記レプリケーション集合における前記ストレージ装置各々について決定されたタイムアウト値が、前記レプリケーション集合について決定されたクリティカル因子(a factor of criticalness)に適合し、該クリティカル因子は前記レプリケーション集合において利用可能なストレージ装置の数と前記レプリケーションレベルとの間の差分に応じて決定される。
【００１４】
［4］本発明の一形態による方法において、前記クリティカル因子は、2つの異なる前記休止時間データの測定値同士の間における、前記レプリケーション集合に属する接続されているストレージ装置数の差分に応じて決定され。
【００１５】
［5］本発明は、ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元を行うサーバにも関連し、該サーバは、以下の手段を有する：
＿データ項目の保存各々について、レプリケーション集合を選択する手段。レプリケーション集合は、分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現し、所定数個のストレージ装置はデータ項目を保存するために選択されている。所定数kはレプリケーションレベルを表す。
【００１６】
＿レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定する手段(320)。該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると終了し、前記タイマが満了すると前記ストレージ装置は切断された(disconnected)ものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でない期間を表す。
【００１７】
＿前記ストレージ装置の内の少なくとも1つが切断されたと判断された場合において(403)、前記レプリケーション集合に属する接続中のストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元する手段。
【００１８】
［6］本発明は、上記のデータ復元方法をコンピュータに実行させるプログラムコード命令を含むコンピュータプログラム及びそのようなコンピュータプログラムを記録した記憶媒体にも関連する。
【実施例１】
【００１９】
本発明による多くの利点は本発明に関する具体的な非限定的な実施例の説明により十分に説明される。
【００２０】
以下、添付図面を参照しながら本発明の実施例を説明する。
【００２１】
図1は本発明の一形態に相応しい分散型データストレージネットワークアーキテクチャを示す。ネットワーク1003にはゲートウェイ12が接続され、ゲートウェイは、ネットワーク1003、サーバ17、別のゲートウェイ14(ネットワーク装置15、16をネットワーク1003に接続する)、及びネットワーク1003に直接接続されるネットワーク装置13等に、ネットワーク装置10及び11を接続する。装置10-16の全部又は一部は、データを保存する各自の能力に応じて及び分散型ストレージネットワークのメンバに準じて、分散型ストレージネットワークにおける分散したストレージ装置と考えてよい。
【００２２】
図1に示すものとは異なるタイプのネットワークが本発明に関して使用されてもよい。例えば、1つ以上のネットワークスイッチングノードを含むネットワーク、1つ以上のサブネットワークを含むネットワーク、及び無線ネットワーク装置に接続するネットワーク等が使用されてもよい。
【００２３】
本発明は、家庭ネットワークをインターネットに接続するホームゲートウェイ、ウェブサーバ、ビデオサーバ、携帯用又は携帯用ではない無線装置等のような任意のタイプのネットワーク装置において使用可能である。
【００２４】
図2は典型的な装置の休止時間又はダウンタイム(downtime)の分布を示す。図示されているように、装置は13時間近辺の平均休止時間を有し、これは例えば夜の間電源を落としている装置に典型的である。本発明の一形態によれば、装置の休止時間のデータは各々の装置自身により個別に測定される。本発明の別の形態によれば、装置の休止時間のデータはこのタスクに特化した又は特化していないセントラルサーバにより収集される。更に別の形態によれば、装置の休止時間のデータは、演算及び情報交換に関するモニタリングプロトコルを通じて収集され、休止時間のデータを収集する処理負担を装置間で分散する。同一のデータ項目又はデータアイテム(data item)を保存している装置又はデバイスは、一群の装置、装置の集合又はクラスタを形成し、「レプリケーション集合(replication set)」と言及される。
【００２５】
一形態によれば、臨界性又はクリティカル性(criticalness)という概念が導入され、これは本発明による方法を更に最適化する。クリティカル性は、例えばレプリケーション集合に属する接続された装置の数が所定のレプリケーション因子kを下回る場合に生じる、データ項目の永久的な損失のおそれとして定義される。クリティカル性は、レプリケーション集合中の全ての装置について規定され、レプリケーション集合に属する装置の個々のタイムアウト値に影響を及ぼす。特定の一形態によれば、レプリケーション集合における接続された装置の数は、次の数式により初期のタイムアウト値(timeout value)にデルタ因子を乗じるようにして直接的に影響する：
timeoutvalue = a/c*timeout value
ここで、aはレプリケーション集合に属する接続された装置として観測された装置数であり、cはレプリケーション集合に属する接続された装置の所望数である。a＞cであった場合、因子a/cは1より大きく、タイムアウト値は増やされることになり、「活発(aggressive)」でないタイムアウト設定となり、レプリケーション集合において離脱した装置の置換(復元又は復旧)を遅らせることになる。a=cであった場合、タイムアウト値は不変のまま残る。a＜cであった場合、タイムアウト値は減少し、より「活発(aggressive)」なタイムアウト設定となり、レプリケーション集合において離脱した装置の置換(復元又は復旧)を加速することになる。
【００２６】
一形態において、クリティカル性は、レプリケーション集合における接続された装置の数を時間経過とともに測定することで決定される。レプリケーション集合における接続された装置数の増加又は減少に基づいて決定される因子に従って、タイムアウトの初期値が、減らされる、同一に維持される又は増やされる。例えば、接続された装置に関する2つの測定値が、2つの異なる週に対して同じ時間数であったとする。
【００２７】
本発明の一形態によれば、タイムアウト値の最適値は次の場合に得られる：
【００２８】
【数１】
ここで、クリティカル性(Criticalness)は、0から1までの範囲内で測定され、0は最小のクリティカル性を表し、1は最大のクリティカル性を表し、PR(H0)はタイムアウトした装置が再接続する既知の(先験的な又は推測された)確率(a priori probability)である。本システムに関し、Pr(H0)は次式により計算できる：
【００２９】
【数２】
ここで、NbrTransientFailuresは擬似誤り(false failures)の数であり、すなわち利用可能でない又は切断された(タイムアウト満了)と判断されたが再接続した装置の数であり、NbrPermanentFailuresは実誤り(real failures)の数であり、すなわち装置は利用可能でない/切断されたままである。
【００３０】
【数３】
という値がレプリケーション集合について算出される。タイムアウトの最適値は次のようにして実行されてもよい。先ず第1ステップにおいて、積分値を計算し、その値が(2)の値より劣っていた場合、第2ステップにおいて、タイムアウト値が減らされ、(1)が真になるまで第1及び第2ステップが反復される。
【００３１】
一形態において、装置の各々が自身の休止時間又はダウンタイムの分布データを保存する。この形態は、装置の利用可能性を一括して監視することを回避でき、装置及びサーバ間の通信を減らせる点で有利である。
【００３２】
上記の様々な形態は、ノードの各々を監視し、各ノードについて、接続及び切断に関する比較的少ないデータ量を保存することができるので、個々のノードの振る舞いに基づくタイムアウト値の最適化(又は適応化)を可能にする。そのような監視は、各ノードに規則的に検査信号(PING信号)を送信するセントラルサーバによって行われてもよいし、或いはセントラル化されていない方法で行われてもよい(検査信号(PING信号)は、インターネットプロトコル(IP)ネットワークにおけるホストへの到達可能性を検査するため、及び元のホストから宛先コンピュータへ送信されたメッセージの往復時間(ラウンドトリップ時間：RTT)を測定するために使用されるコンピュータネットワーク管理手段である)。
【００３３】
図3は本発明の特定の実施形態による装置を示す。本装置は、本発明の特定の形態を実現する装置でもよいし、本発明の特定の形態を実現する特定のセントラル化装置(例えば、サーバ)とすることができ、本発明の特定の形態に特化したものでもよいし或いは特化していないものでもよい。
【００３４】
装置30は、リードオンリメモリ(ROM)300、ランダムアクセスメモリ(RAM)310、中央処理装置(CPU)320、クロック330、ネットワークインタフェース340、グラフィックインタフェース350、及びユーザインタフェース360を有する。これら全ての要素又は素子はデータ及び通信バス370により相互に接続されている。CPU320はROM300のメモリ領域301に保存されているプログラムに従って装置30を制御する。クロック装置330は装置30の各要素に共通のタイミングを提供し、各自の動作を順序付ける及び同期させる。ネットワークインタフェース340は接続部3000を通じて外部装置とデータを送受信する。グラフィックインタフェース350は接続部3001を通じて外部レンダリング装置に接続される。ユーザインタフェース360は接続部3002を介してユーザから入力コマンドを受信する。ROMメモリゾーン301は、本発明による方法を実行するための命令を含む。装置30の電源を投入すると、CPU320は、ROMメモリゾーン301内のプログラム「Prog」をRAMメモリゾーン311にコピー又は複製し、コピーされたプログラムを実行する。コピーされたプログラムを実行する際、プログラムは、実行に必要な変数のメモリ空間をRAMメモリゾーン315内に割り当て、ストレージ装置に関連するレプリケーション集合302及びタイマのタイムアウト値303を各自のRAMメモリ312-313にコピーする。こうして装置30は動作可能になり、新たなデータを保存する要求(リクエスト)を受信すると、本発明による方法が開始される。
【００３５】
一形態によれば、本発明は、例えば専用の素子として(例えば、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)又は大規模集積回路(VLSI)等)、装置に統合された個別的な電子素子群として、完全にハードウェアで実現されてもよいし、或いはハードウェア及びソフトウェアの混合形式で実現されてもよい。
【００３６】
本発明は、本発明の方法ステップをコンピュータに実行させるプログラム命令を含むコンピュータプログラム又はコンピュータプログラム関連製品として実現されてもよい。
【００３７】
図4は例えば図3に示す装置により本発明の方法を実行する場合における特定の動作例を示すアルゴリズムである。アルゴリズムはステップ400から始まり、本方法の実行に必要な変数が初期化される。ステップ401において、データ項目の格納に関するレプリケーション集合が選択される。この選択は例えば図3のCPU320により行われる。そのようなレプリケーション集合は、例えば、データ項目を保存するために分散データストレージシステム内で選択されたストレージ装置の所定数(例えば、k)を表現する。レプリケーション集合の選択は、例えば、データ項目を保存する要求(リクエスト)を受けた際に開始されてもよい。kという数値は予め定められており、データの耐性又は回復力(data resilience)を保証できる値に設定される。所定の数kは「復元レベル又はレプリケーションレベル(replication level)」と言及されてもよい。そして、ステップ402において、レプリケーション集合中の装置に関連するタイマについてタイムアウト値が決定される(装置の各々に特定のタイマが関連付けられている)。この決定は例えば図3のCPU320により行われる。タイマは、レプリケーション集合中の装置の永久的な切断又は利用不可能性(本当に離脱してしまったこと又は本当に利用できないこと)を判定できるようにする。タイマは、関連するストレージ装置の離脱とともに起動され、関連するストレージ装置の再接続により止められる。しかしながら、タイマが満了した場合、関連するそのストレージ装置は分散型ストレージシステムから(本当に)切断されたと判断される。タイムアウト値は、タイムアウトに関連付けられるストレージ装置について測定された休止時間データの分布を表す関数により決定される。休止時間データは、ストレージ装置が分散データストレージシステムの中で利用可能でなかった/分離していた時間期間を表す。ステップ403において、レプリケーション集合に属している少なくとも1つのストレージ装置が切断されたと判断された場合において、レプリケーション集合に属する接続された/利用可能なストレージ装置の数が所定の閾値を下回っていた場合(閾値は、kでもよいが、安全性を高めるためにkより大きな値でもよい)、レプリケーション集合に対して新しい少なくとも1つのストレージ装置を選択することでレプリケーションレベルが復元され、データ項目の中から新たなデータ項目が作成され、その「新たな」ストレージ装置に保存され、「新たな」ストレージ装置がレプリケーション集合に追加される。例えばレプリケーションレベルの復元は例えば図3のCPU320により実行される。
【００３８】
ストレージ装置に関連するタイマが満了した後にそのストレージ装置が分散データストレージネットワークに再接続した場合、すなわち永久的に切断されたとして「誤って」判断された場合に、ストレージ装置が属していたレプリケーション集合に該ストレージ装置を復帰させることで、本方法は更に最適化されてもよい。
【００３９】
一形態において、レプリケーション集合に属するストレージ装置各々について決定されたタイムアウト値は、レプリケーション集合について決定されたクリティカル因子に応じて調整され、そのクリティカル因子は、レプリケーション集合の中で利用可能な装置の数と所定の数kとの間の差分に従って決定される。
【００４０】
本発明方法によりレプリカの修復を適応化、加速又は遅延させる方法は、ノード毎にタイムアウト値を使用するだけでなく、復元の活発さ又は頻度を時間経過とともに適合させる等の点で従来とは異なる特有のものである。タイムアウト値が短すぎて過剰に多くのレプリカ(復元)が生じる場合、タイムアウト値は釣り合いがとれるまで伸張される。タイムアウト値が長すぎた場合、タイムアウト値は短縮され、必要最低限のレプリカ(復元)の数を増やす。このような必要最低限の労力しか要しない本方法は、永続的なノードの喪失であると誤って判断する回数を減らすので、時間経過とともに使用されるリソース量を大幅に減らすことができる。
【符号の説明】
【００４１】
10、11、13、15、16 ネットワーク装置
12、14 ゲートウェイ
17 サーバ
1003 ネットワーク
【先行技術文献】
【非特許文献】
【００４２】
【非特許文献１】JING TIAN et al.,“Probabilistic Failure Detection for Efficient Distributed Storage Maintenance,” Reliable Distributed Systems, 2008, SRDS ’08, IEEE symposium, 6 October 2008
【技術分野】
【０００１】
本発明は一般に分散型データストレージシステムに関連する。特に本発明は所望のデータ復元レベルを保証するのに必要なデータの観点から分散型データストレージシステムを最適化することに関連する。
【背景技術】
【０００２】
ビデオ及びイメージを処理する装置のような大容量データ処理装置の急速な普及とともに、直接的な保存又はバックアップ保存の一環として、膨大なデータ量を安心して格納することが求められている。ネットワーク接続機能を備えたデバイスが益々増加するにつれて、ネットワークで接続されたデバイスにデータを分散して保存することは、費用対効果に優れた手段であると考えられる。そのような分散型データストレージシステムにおいて、一時的な又は永久的なデータ損失(ロス、欠落、欠陥等)に対するデータの安定供給性及び復元性を保証するために、分散型データストレージネットワーク内の複数のネットワーク接続装置に同じデータ項目をコピーする方法が使用されている。これはデータ復元又はデータレプリケーション(data replication)と呼ばれる。データレプリケーションという用語は広義に解釈する必要があり、単にデータを復元(回復、再現、反復、複製等)するだけでなく、符号又はコードを消去又は再生成するような符号化技術(コーディング技術)を利用することも包含する。装置の故障や装置が利用可能でないことに起因する永続的又は一時的なデータロスに対処する観点からは、レプリケーション因子(replication factor)は大きいことが望ましい(すなわち、複製数は大きいことが望ましい)。しかしながら、必要な通信サイズや保存容量等によるコスト(いわゆる「レプリケーションコスト」)を減らす観点からは、レプリケーション因子は小さいことが望ましい。
【０００３】
従って、分散した保存データのデータ利用性を高く維持し、データ損失に対する耐性及びレプリケーションコストをともに考慮する解決手段が望まれている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
本発明の課題は従来技術における問題を軽減することである。
【課題を解決するための手段】
【０００５】
本発明の一形態による方法は、
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元方法であって、
保存するデータ項目各々について、前記分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現するレプリケーション集合を選択するステップであって、前記所定数個(k個)のストレージ装置は前記データ項目を保存するために選択されており、前記所定数kはレプリケーションレベルを表す、ステップと、
前記レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定するステップであって、該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると止まり、前記タイマが満了すると前記ストレージ装置は切断されたものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でなかった期間を表す、ステップと、
少なくとも1つの前記ストレージ装置が切断されたと判断された場合において、前記レプリケーション集合に属する接続されているストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために新たに選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元するステップと
を有するデータ復元方法である。
【図面の簡単な説明】
【０００６】
【図１】本発明の一形態に相応しい分散型ストレージネットワークアーキテクチャを示す図。
【図２】典型的なピアの休止時間の分布を示す図。
【図３】本発明の一形態による方法を実行する装置の一例を示す図。
【図４】図1の何れかの装置10-16等により実行される本発明による特定の動作例のアルゴリズムを示す図。
【発明を実施するための形態】
【０００７】
ピアトゥピアネットワークのような分散型データネットワーク(distributed data network)の場合、デバイスは継続的にネットワークに出入りしている。分散型データ保存ネットワークの一部をなすデバイスがそのネットワークから本当に又は確実に(definitely)に去ってしまった場合、データ復元レベル又はデータレプリケーションレベルは減少する。データ複製方式による分散型データストレージシステム(data duplication based distributed data storage system)の場合、同じデータ項目を保存しているまだ利用可能な他のデバイスから複製した新たなデータ項目を、ネットワーク内の新たな又は既存のデバイスに設けることで、データ復元レベルは回復する。コードを消去又は再生成することに基づく分散型データストレージシステムの場合、データ項目を複製するのにまだ使用可能な他のデバイスから生成されたデータである新たなデータ項目を、ネットワークの新たな又は既存のデバイスに作成することで、データ復元レベルが回復する。しかしながらデバイスの離脱は必ずしも確定的なものではなく、デバイスを利用できないことは単なる一時的なことかもしれない。従って問題は、デバイスの離脱に起因して減少したデータ復元レベルの復旧を適切な時点で促すために、デバイスが分散型データストレージシステムを本当に離脱してしまったことを如何にして判断するか、ということである。デバイスの単なる一時的な離脱に起因して減少したレプリケーションレベルを復元すると、そのような復元(restoring)は無駄なものであり、ストレージ容量やネットワーク通信等の観点から分散型データストレージシステムのリソースを不必要に浪費してしまうことになる。
【０００８】
分散型データストレージシステムの一部をなすデバイスの動き(振る舞い、挙動、行動、素行等)を観察すると、デバイスは各自自身の接続挙動(connectivity behavior)を有することが分かる。例えば、或るデバイスは常時接続され、別のデバイスは日中の間だけ接続されて夜間は分離され、更に別のデバイスは規則性のない接続挙動を有する。非特許文献1は、ノード毎の不具合の検出は困難であることに言及し、その代わりにノードのグループ毎にデータの利用可能性を予測することを提案している。しかしながらこの非特許文献1に記載されているようにして個々のノードの情報をグループ化すると、グループに属する個々のノードの挙動の情報は失われるので、この文献に記載されている方法は非効率的であり、不要な復元を行うことになってしまう。これに対して本発明は、個々のデバイスの接続挙動に関する情報を活用できるようにし、デバイスが分散型データストレージネットワークを本当に離脱したと推定できる時点を判定し、データ項目の新たな生成を適切な時点で促し、分散型データストレージネットワークのリソースを最適に利用できるようにする。このような判定を行うために本発明は中断時間又はタイムアウト(timeout)を使用し、タイムアウトの値はデバイスの休止時間(downtime)の分布を表す関数により決定され、休止時間の分布はデバイスについて測定された利用可能性挙動(availability behavior)に基づいている。デバイスが離脱した場合、所定の期間についてタイムアウトが計測され始める。タイムアウトが満了する前にデバイスが再接続されると、タイムアウトはリセットされる。しかしながらタイムアウト期間が満了すると、デバイスは分散型データストレージシステムを本当に離脱したと判断され、新たなデータ項目を新たな又は既存のデバイスに作成することで、レプリケーションレベルを復旧する処理から成る復元処理が開始される。新たなデータ項目は、データ項目を保存している残りのデバイスの内の1つ以上の中から複製(データデュプリケーションに基づくデータ復元の場合)又は生成(コードの消去又は再生成に基づくデータ復元の場合)される。従って、偏りのない適切な(fair)タイムアウト期間を決定することが重要である。タイムアウト値が短すぎた場合、一時的な離脱が永久的な離脱と判断されるので、過剰に多くの不要な「復元(repair)」が行われてしまうことになる。不要な復元が多いと、分散型データストレージシステムの輻輳を招くおそれがある。これに対して、タイムアウト値が過剰に長かった場合、タイムアウトの満了前に、いくつかの永久的な離脱が生じると、データの持続性(persistence)が脅かされてしまう。このため本発明ではデバイスの個々の接続挙動に関する情報を活用して、個々のデバイスの接続挙動に適合するタイムアウト期間を決定する。本発明においては、分散型データストレージシステムのデバイス各々のダウンタイムに関連するデータが収集される。
【０００９】
［1］分散型データストレージシステムにおけるデータ復元を最適化する本発明による方法は、
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元方法である。本方法は少なくとも以下のステップを有する：
＿データ項目の保存各々について、レプリケーション集合を選択するステップ。レプリケーション集合は、分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現し、所定数個のストレージ装置はデータ項目を保存するために選択されている。所定数kはレプリケーションレベルを表す。
【００１０】
＿レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定するステップ。該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると終了し、前記タイマが満了すると前記ストレージ装置は切断された(disconnected)ものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でない期間を表す。
【００１１】
＿前記ストレージ装置の内の少なくとも1つが切断されたと判断された場合において、前記レプリケーション集合に属する接続中のストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元するステップ。
【００１２】
［2］本発明の一形態による方法は、前記ストレージ装置に関連する前記タイマが満了した後、前記ストレージ装置が前記分散型データストレージシステムに再接続した場合に、前記ストレージ装置が属していたレプリケーション集合にストレージ装置を復帰させるステップを更に有する。
【００１３】
［3］本発明の一形態による方法において、前記レプリケーション集合における前記ストレージ装置各々について決定されたタイムアウト値が、前記レプリケーション集合について決定されたクリティカル因子(a factor of criticalness)に適合し、該クリティカル因子は前記レプリケーション集合において利用可能なストレージ装置の数と前記レプリケーションレベルとの間の差分に応じて決定される。
【００１４】
［4］本発明の一形態による方法において、前記クリティカル因子は、2つの異なる前記休止時間データの測定値同士の間における、前記レプリケーション集合に属する接続されているストレージ装置数の差分に応じて決定され。
【００１５】
［5］本発明は、ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元を行うサーバにも関連し、該サーバは、以下の手段を有する：
＿データ項目の保存各々について、レプリケーション集合を選択する手段。レプリケーション集合は、分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現し、所定数個のストレージ装置はデータ項目を保存するために選択されている。所定数kはレプリケーションレベルを表す。
【００１６】
＿レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定する手段(320)。該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると終了し、前記タイマが満了すると前記ストレージ装置は切断された(disconnected)ものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でない期間を表す。
【００１７】
＿前記ストレージ装置の内の少なくとも1つが切断されたと判断された場合において(403)、前記レプリケーション集合に属する接続中のストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元する手段。
【００１８】
［6］本発明は、上記のデータ復元方法をコンピュータに実行させるプログラムコード命令を含むコンピュータプログラム及びそのようなコンピュータプログラムを記録した記憶媒体にも関連する。
【実施例１】
【００１９】
本発明による多くの利点は本発明に関する具体的な非限定的な実施例の説明により十分に説明される。
【００２０】
以下、添付図面を参照しながら本発明の実施例を説明する。
【００２１】
図1は本発明の一形態に相応しい分散型データストレージネットワークアーキテクチャを示す。ネットワーク1003にはゲートウェイ12が接続され、ゲートウェイは、ネットワーク1003、サーバ17、別のゲートウェイ14(ネットワーク装置15、16をネットワーク1003に接続する)、及びネットワーク1003に直接接続されるネットワーク装置13等に、ネットワーク装置10及び11を接続する。装置10-16の全部又は一部は、データを保存する各自の能力に応じて及び分散型ストレージネットワークのメンバに準じて、分散型ストレージネットワークにおける分散したストレージ装置と考えてよい。
【００２２】
図1に示すものとは異なるタイプのネットワークが本発明に関して使用されてもよい。例えば、1つ以上のネットワークスイッチングノードを含むネットワーク、1つ以上のサブネットワークを含むネットワーク、及び無線ネットワーク装置に接続するネットワーク等が使用されてもよい。
【００２３】
本発明は、家庭ネットワークをインターネットに接続するホームゲートウェイ、ウェブサーバ、ビデオサーバ、携帯用又は携帯用ではない無線装置等のような任意のタイプのネットワーク装置において使用可能である。
【００２４】
図2は典型的な装置の休止時間又はダウンタイム(downtime)の分布を示す。図示されているように、装置は13時間近辺の平均休止時間を有し、これは例えば夜の間電源を落としている装置に典型的である。本発明の一形態によれば、装置の休止時間のデータは各々の装置自身により個別に測定される。本発明の別の形態によれば、装置の休止時間のデータはこのタスクに特化した又は特化していないセントラルサーバにより収集される。更に別の形態によれば、装置の休止時間のデータは、演算及び情報交換に関するモニタリングプロトコルを通じて収集され、休止時間のデータを収集する処理負担を装置間で分散する。同一のデータ項目又はデータアイテム(data item)を保存している装置又はデバイスは、一群の装置、装置の集合又はクラスタを形成し、「レプリケーション集合(replication set)」と言及される。
【００２５】
一形態によれば、臨界性又はクリティカル性(criticalness)という概念が導入され、これは本発明による方法を更に最適化する。クリティカル性は、例えばレプリケーション集合に属する接続された装置の数が所定のレプリケーション因子kを下回る場合に生じる、データ項目の永久的な損失のおそれとして定義される。クリティカル性は、レプリケーション集合中の全ての装置について規定され、レプリケーション集合に属する装置の個々のタイムアウト値に影響を及ぼす。特定の一形態によれば、レプリケーション集合における接続された装置の数は、次の数式により初期のタイムアウト値(timeout value)にデルタ因子を乗じるようにして直接的に影響する：
timeoutvalue = a/c*timeout value
ここで、aはレプリケーション集合に属する接続された装置として観測された装置数であり、cはレプリケーション集合に属する接続された装置の所望数である。a＞cであった場合、因子a/cは1より大きく、タイムアウト値は増やされることになり、「活発(aggressive)」でないタイムアウト設定となり、レプリケーション集合において離脱した装置の置換(復元又は復旧)を遅らせることになる。a=cであった場合、タイムアウト値は不変のまま残る。a＜cであった場合、タイムアウト値は減少し、より「活発(aggressive)」なタイムアウト設定となり、レプリケーション集合において離脱した装置の置換(復元又は復旧)を加速することになる。
【００２６】
一形態において、クリティカル性は、レプリケーション集合における接続された装置の数を時間経過とともに測定することで決定される。レプリケーション集合における接続された装置数の増加又は減少に基づいて決定される因子に従って、タイムアウトの初期値が、減らされる、同一に維持される又は増やされる。例えば、接続された装置に関する2つの測定値が、2つの異なる週に対して同じ時間数であったとする。
【００２７】
本発明の一形態によれば、タイムアウト値の最適値は次の場合に得られる：
【００２８】
【数１】
ここで、クリティカル性(Criticalness)は、0から1までの範囲内で測定され、0は最小のクリティカル性を表し、1は最大のクリティカル性を表し、PR(H0)はタイムアウトした装置が再接続する既知の(先験的な又は推測された)確率(a priori probability)である。本システムに関し、Pr(H0)は次式により計算できる：
【００２９】
【数２】
ここで、NbrTransientFailuresは擬似誤り(false failures)の数であり、すなわち利用可能でない又は切断された(タイムアウト満了)と判断されたが再接続した装置の数であり、NbrPermanentFailuresは実誤り(real failures)の数であり、すなわち装置は利用可能でない/切断されたままである。
【００３０】
【数３】
という値がレプリケーション集合について算出される。タイムアウトの最適値は次のようにして実行されてもよい。先ず第1ステップにおいて、積分値を計算し、その値が(2)の値より劣っていた場合、第2ステップにおいて、タイムアウト値が減らされ、(1)が真になるまで第1及び第2ステップが反復される。
【００３１】
一形態において、装置の各々が自身の休止時間又はダウンタイムの分布データを保存する。この形態は、装置の利用可能性を一括して監視することを回避でき、装置及びサーバ間の通信を減らせる点で有利である。
【００３２】
上記の様々な形態は、ノードの各々を監視し、各ノードについて、接続及び切断に関する比較的少ないデータ量を保存することができるので、個々のノードの振る舞いに基づくタイムアウト値の最適化(又は適応化)を可能にする。そのような監視は、各ノードに規則的に検査信号(PING信号)を送信するセントラルサーバによって行われてもよいし、或いはセントラル化されていない方法で行われてもよい(検査信号(PING信号)は、インターネットプロトコル(IP)ネットワークにおけるホストへの到達可能性を検査するため、及び元のホストから宛先コンピュータへ送信されたメッセージの往復時間(ラウンドトリップ時間：RTT)を測定するために使用されるコンピュータネットワーク管理手段である)。
【００３３】
図3は本発明の特定の実施形態による装置を示す。本装置は、本発明の特定の形態を実現する装置でもよいし、本発明の特定の形態を実現する特定のセントラル化装置(例えば、サーバ)とすることができ、本発明の特定の形態に特化したものでもよいし或いは特化していないものでもよい。
【００３４】
装置30は、リードオンリメモリ(ROM)300、ランダムアクセスメモリ(RAM)310、中央処理装置(CPU)320、クロック330、ネットワークインタフェース340、グラフィックインタフェース350、及びユーザインタフェース360を有する。これら全ての要素又は素子はデータ及び通信バス370により相互に接続されている。CPU320はROM300のメモリ領域301に保存されているプログラムに従って装置30を制御する。クロック装置330は装置30の各要素に共通のタイミングを提供し、各自の動作を順序付ける及び同期させる。ネットワークインタフェース340は接続部3000を通じて外部装置とデータを送受信する。グラフィックインタフェース350は接続部3001を通じて外部レンダリング装置に接続される。ユーザインタフェース360は接続部3002を介してユーザから入力コマンドを受信する。ROMメモリゾーン301は、本発明による方法を実行するための命令を含む。装置30の電源を投入すると、CPU320は、ROMメモリゾーン301内のプログラム「Prog」をRAMメモリゾーン311にコピー又は複製し、コピーされたプログラムを実行する。コピーされたプログラムを実行する際、プログラムは、実行に必要な変数のメモリ空間をRAMメモリゾーン315内に割り当て、ストレージ装置に関連するレプリケーション集合302及びタイマのタイムアウト値303を各自のRAMメモリ312-313にコピーする。こうして装置30は動作可能になり、新たなデータを保存する要求(リクエスト)を受信すると、本発明による方法が開始される。
【００３５】
一形態によれば、本発明は、例えば専用の素子として(例えば、特定用途向け集積回路(ASIC)、フィールドプログラマブルゲートアレイ(FPGA)又は大規模集積回路(VLSI)等)、装置に統合された個別的な電子素子群として、完全にハードウェアで実現されてもよいし、或いはハードウェア及びソフトウェアの混合形式で実現されてもよい。
【００３６】
本発明は、本発明の方法ステップをコンピュータに実行させるプログラム命令を含むコンピュータプログラム又はコンピュータプログラム関連製品として実現されてもよい。
【００３７】
図4は例えば図3に示す装置により本発明の方法を実行する場合における特定の動作例を示すアルゴリズムである。アルゴリズムはステップ400から始まり、本方法の実行に必要な変数が初期化される。ステップ401において、データ項目の格納に関するレプリケーション集合が選択される。この選択は例えば図3のCPU320により行われる。そのようなレプリケーション集合は、例えば、データ項目を保存するために分散データストレージシステム内で選択されたストレージ装置の所定数(例えば、k)を表現する。レプリケーション集合の選択は、例えば、データ項目を保存する要求(リクエスト)を受けた際に開始されてもよい。kという数値は予め定められており、データの耐性又は回復力(data resilience)を保証できる値に設定される。所定の数kは「復元レベル又はレプリケーションレベル(replication level)」と言及されてもよい。そして、ステップ402において、レプリケーション集合中の装置に関連するタイマについてタイムアウト値が決定される(装置の各々に特定のタイマが関連付けられている)。この決定は例えば図3のCPU320により行われる。タイマは、レプリケーション集合中の装置の永久的な切断又は利用不可能性(本当に離脱してしまったこと又は本当に利用できないこと)を判定できるようにする。タイマは、関連するストレージ装置の離脱とともに起動され、関連するストレージ装置の再接続により止められる。しかしながら、タイマが満了した場合、関連するそのストレージ装置は分散型ストレージシステムから(本当に)切断されたと判断される。タイムアウト値は、タイムアウトに関連付けられるストレージ装置について測定された休止時間データの分布を表す関数により決定される。休止時間データは、ストレージ装置が分散データストレージシステムの中で利用可能でなかった/分離していた時間期間を表す。ステップ403において、レプリケーション集合に属している少なくとも1つのストレージ装置が切断されたと判断された場合において、レプリケーション集合に属する接続された/利用可能なストレージ装置の数が所定の閾値を下回っていた場合(閾値は、kでもよいが、安全性を高めるためにkより大きな値でもよい)、レプリケーション集合に対して新しい少なくとも1つのストレージ装置を選択することでレプリケーションレベルが復元され、データ項目の中から新たなデータ項目が作成され、その「新たな」ストレージ装置に保存され、「新たな」ストレージ装置がレプリケーション集合に追加される。例えばレプリケーションレベルの復元は例えば図3のCPU320により実行される。
【００３８】
ストレージ装置に関連するタイマが満了した後にそのストレージ装置が分散データストレージネットワークに再接続した場合、すなわち永久的に切断されたとして「誤って」判断された場合に、ストレージ装置が属していたレプリケーション集合に該ストレージ装置を復帰させることで、本方法は更に最適化されてもよい。
【００３９】
一形態において、レプリケーション集合に属するストレージ装置各々について決定されたタイムアウト値は、レプリケーション集合について決定されたクリティカル因子に応じて調整され、そのクリティカル因子は、レプリケーション集合の中で利用可能な装置の数と所定の数kとの間の差分に従って決定される。
【００４０】
本発明方法によりレプリカの修復を適応化、加速又は遅延させる方法は、ノード毎にタイムアウト値を使用するだけでなく、復元の活発さ又は頻度を時間経過とともに適合させる等の点で従来とは異なる特有のものである。タイムアウト値が短すぎて過剰に多くのレプリカ(復元)が生じる場合、タイムアウト値は釣り合いがとれるまで伸張される。タイムアウト値が長すぎた場合、タイムアウト値は短縮され、必要最低限のレプリカ(復元)の数を増やす。このような必要最低限の労力しか要しない本方法は、永続的なノードの喪失であると誤って判断する回数を減らすので、時間経過とともに使用されるリソース量を大幅に減らすことができる。
【符号の説明】
【００４１】
10、11、13、15、16 ネットワーク装置
12、14 ゲートウェイ
17 サーバ
1003 ネットワーク
【先行技術文献】
【非特許文献】
【００４２】
【非特許文献１】JING TIAN et al.,“Probabilistic Failure Detection for Efficient Distributed Storage Maintenance,” Reliable Distributed Systems, 2008, SRDS ’08, IEEE symposium, 6 October 2008
【特許請求の範囲】
【請求項１】
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元方法であって、
保存するデータ項目各々について、前記分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現するレプリケーション集合を選択するステップであって、前記所定数個(k個)のストレージ装置は前記データ項目を保存するために選択されており、前記所定数kはレプリケーションレベルを表す、ステップと、
前記レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定するステップであって、該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると止まり、前記タイマが満了すると前記ストレージ装置は切断されたものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でなかった期間を表す、ステップと、
少なくとも1つの前記ストレージ装置が切断されたと判断された場合において、前記レプリケーション集合に属する接続されているストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために新たに選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元するステップと
を有するデータ復元方法。
【請求項２】
前記ストレージ装置に関連する前記タイマが満了した後、前記ストレージ装置が前記分散型データストレージシステムに再接続した場合に、前記ストレージ装置が属していたレプリケーション集合に前記ストレージ装置を復帰させるステップを更に有する、請求項1記載のデータ復元方法。
【請求項３】
前記レプリケーション集合に属する前記ストレージ装置各々について決定されたタイムアウト値が、前記レプリケーション集合について決定されたクリティカル因子に適合させられており、該クリティカル因子は前記レプリケーション集合において利用可能なストレージ装置の数と前記レプリケーションレベルとの間の差分に応じて決定される、請求項1又は2に記載のデータ復元方法。
【請求項４】
前記クリティカル因子は、2つの異なる前記休止時間データの測定値同士の間における、前記レプリケーション集合に属する接続されているストレージ装置数の差分に応じて決定される、請求項3記載のデータ復元方法。
【請求項５】
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元のためのサーバ装置であって、
保存するデータ項目各々について、前記分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現するレプリケーション集合を選択する手段であって、前記所定数個(k個)のストレージ装置は前記データ項目を保存するために選択されており、前記所定数kはレプリケーションレベルを表す、手段と、
前記レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定する手段であって、該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると止まり、前記タイマが満了すると前記ストレージ装置は切断されたものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でなかった期間を表す、手段と、
少なくとも1つの前記ストレージ装置が切断されたと判断された場合において、前記レプリケーション集合に属する接続されているストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために新たに選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元する手段と
を有するサーバ装置。
【請求項６】
請求項1記載のデータ復元方法をコンピュータに実行させるプログラムコード命令を含むコンピュータプログラム。
【請求項１】
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元方法であって、
保存するデータ項目各々について、前記分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現するレプリケーション集合を選択するステップであって、前記所定数個(k個)のストレージ装置は前記データ項目を保存するために選択されており、前記所定数kはレプリケーションレベルを表す、ステップと、
前記レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定するステップであって、該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると止まり、前記タイマが満了すると前記ストレージ装置は切断されたものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でなかった期間を表す、ステップと、
少なくとも1つの前記ストレージ装置が切断されたと判断された場合において、前記レプリケーション集合に属する接続されているストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために新たに選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元するステップと
を有するデータ復元方法。
【請求項２】
前記ストレージ装置に関連する前記タイマが満了した後、前記ストレージ装置が前記分散型データストレージシステムに再接続した場合に、前記ストレージ装置が属していたレプリケーション集合に前記ストレージ装置を復帰させるステップを更に有する、請求項1記載のデータ復元方法。
【請求項３】
前記レプリケーション集合に属する前記ストレージ装置各々について決定されたタイムアウト値が、前記レプリケーション集合について決定されたクリティカル因子に適合させられており、該クリティカル因子は前記レプリケーション集合において利用可能なストレージ装置の数と前記レプリケーションレベルとの間の差分に応じて決定される、請求項1又は2に記載のデータ復元方法。
【請求項４】
前記クリティカル因子は、2つの異なる前記休止時間データの測定値同士の間における、前記レプリケーション集合に属する接続されているストレージ装置数の差分に応じて決定される、請求項3記載のデータ復元方法。
【請求項５】
ストレージ装置として少なくとも使用されるネットワーク装置を含む分散型データストレージシステムにおけるデータ復元のためのサーバ装置であって、
保存するデータ項目各々について、前記分散型データストレージシステムにおける所定数個(k個)のストレージ装置を表現するレプリケーション集合を選択する手段であって、前記所定数個(k個)のストレージ装置は前記データ項目を保存するために選択されており、前記所定数kはレプリケーションレベルを表す、手段と、
前記レプリケーション集合に属するストレージ装置各々について、該ストレージ装置に関連するタイマのタイムアウト値を決定する手段であって、該タイマは、前記ストレージ装置が前記分散型データストレージシステムから離脱すると計時し始め且つ前記ストレージ装置が前記分散型データストレージシステムに再接続すると止まり、前記タイマが満了すると前記ストレージ装置は切断されたものと判断され、前記タイムアウト値は前記ストレージ装置について測定された休止時間データの分布を表す関数により決定され、前記休止時間データは、前記分散型データストレージシステムにおいて前記ストレージ装置が利用可能でなかった期間を表す、手段と、
少なくとも1つの前記ストレージ装置が切断されたと判断された場合において、前記レプリケーション集合に属する接続されているストレージ装置の数が所定の閾値を下回っていた場合、少なくとも1つの別のストレージ装置を前記レプリケーション集合のために新たに選択し、該少なくとも1つの別のストレージ装置におけるデータ項目から新たなデータ項目を生成し、該少なくとも1つの別のストレージ装置を前記レプリケーション集合に加えることで、前記レプリケーションレベルを復元する手段と
を有するサーバ装置。
【請求項６】
請求項1記載のデータ復元方法をコンピュータに実行させるプログラムコード命令を含むコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図２】
【図３】
【図４】
【公開番号】特開２０１２−６４２１７（Ｐ２０１２−６４２１７Ａ）
【公開日】平成２４年３月２９日（２０１２．３．２９）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２０２６９２（Ｐ２０１１−２０２６９２）
【出願日】平成２３年９月１６日（２０１１．９．１６）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
【公開日】平成２４年３月２９日（２０１２．３．２９）
【国際特許分類】
【出願番号】特願２０１１−２０２６９２（Ｐ２０１１−２０２６９２）
【出願日】平成２３年９月１６日（２０１１．９．１６）
【出願人】（５０１２６３８１０）トムソン ライセンシング (2,848)
【氏名又は名称原語表記】Ｔｈｏｍｓｏｎ Ｌｉｃｅｎｓｉｎｇ
【住所又は居所原語表記】１−５， ｒｕｅ Ｊｅａｎｎｅ ｄ’Ａｒｃ， ９２１３０ ＩＳＳＹ ＬＥＳ ＭＯＵＬＩＮＥＡＵＸ， Ｆｒａｎｃｅ
【Ｆターム（参考）】
[ Back to top ]