(57)【要約】【課題】複数のレプリカを記憶する分散ストレージにおいて、一連のデータを多くのサーバに配置したい場合と、少数のサーバに配置したい場合の両方に対応すると共に、同一データのレプリカを同一サーバに記憶させないこと。【解決手段】第１配置先決定部２３がデータが分散して配置されるように１stレプリカの配置先を決定する。また、第２配置先決定部２５がデータが同一のサーバに連続して記憶され、かつ１stレプリカと異なるサーバに記憶されるように２ndレプリカの配置を決定する。また、データ分散テーブル２２が１stレプリカと２ndレプリカの配置先のサーバの識別子をハッシュ範囲毎に記憶し、最終送付先記憶部２４が２ndレプリカの最終配布先のサーバの識別子を記憶する。そして、第２配置先決定部２５は、データ分散テーブル２２及び最終送付先記憶部２４に基づいて２ndレプリカの配置先を決定する。【選択図】図３
2015141451.tif 000002
【特許請求の範囲】
【請求項１】
複数の記憶ノードを用いてデータの複数のレプリカを記憶する記憶装置において、
第１のレプリカの記憶ノードへの配置について、データを記憶ノードに分散して記憶させる配置を決定する第１の決定部と、
第２のレプリカの記憶ノードへの配置について、データを同一の記憶ノードに連続して記憶させ、かつ、第１のレプリカを記憶する記憶ノードと異なる記憶ノードに記憶させる配置を決定する第２の決定部と、
を備えたことを特徴とする記憶装置。
【請求項２】
第１のレプリカ及び第２のレプリカの配置先の記憶ノードを識別する識別子を記憶する配置先記憶部と、
データの最終送付先の記憶ノードを識別する識別子を記憶する最終送付先記憶部とをさらに備え、
前記第２の決定部は、前記配置先記憶部及び前記最終送付先記憶部に基づいて第２のレプリカの記憶ノードへの配置を決定することを特徴とする請求項１に記載の記憶装置。
【請求項３】
前記第２の決定部は、ハッシュ値を算出して第２のレプリカの配置先を選定し、選定した配置先が前記最終送付先と異なる場合には、前記ハッシュ値を含むハッシュ範囲を複数に分割することによって前記ハッシュ値に基づく第２のレプリカの配置先を前記最終送付先と同じにすることを特徴とする請求項２に記載の記憶装置。
【請求項４】
前記第２の決定部は、前記ハッシュ範囲の分割を所定の回数繰り返しても第２のレプリカの配置先を前記最終送付先と同じにすることができない場合に、前記ハッシュ値に基づいて選定した配置先への第２のレプリカの配置を決定し、前記最終送付先を該配置先に更新することを特徴とする請求項３に記載の記憶装置。
【請求項５】
同一記憶ノードから読み出したいデータであるか否かを判定し、判定結果に基づいてデータを読み出す記憶ノードを決定する読出部をさらに備えたことを特徴とする請求項１〜４のいずれか１つに記載の記憶装置。
【請求項６】
複数の記憶ノードを用いてデータの複数のレプリカを記憶する記憶装置による複製方法において、
第１のレプリカの記憶ノードへの配置について、データを記憶ノードに分散して記憶させる配置を決定し、
第２のレプリカの記憶ノードへの配置について、データを同一の記憶ノードに連続して記憶させ、かつ、第１のレプリカを記憶する記憶ノードと異なる記憶ノードに記憶させる配を決定する
処理を含むことを特徴とする複製方法。
【請求項７】
複数の記憶ノードを用いてデータの複数のレプリカを記憶する分散ストレージが有するコンピュータで実行される複製プログラムにおいて、
第１のレプリカの記憶ノードへの配置について、データを記憶ノードに分散して記憶させる配置を決定し、
第２のレプリカの記憶ノードへの配置について、データを同一の記憶ノードに連続して記憶させ、かつ、第１のレプリカを記憶する記憶ノードと異なる記憶ノードに記憶させる配を決定する
処理を前記コンピュータに実行させることを特徴とする複製プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、記憶装置、複製方法及び複製プログラムに関する。
【背景技術】
【０００２】
複数のサーバを記憶ノードとしてデータを分散して記憶するデータ分散方法の代表的な方法に、コンシステントハッシュ法がある。コンシステントハッシュ法では、予め用意されたハッシュ関数により、各サーバ及びデータに対してハッシュ値が求められる。例えば、サーバのＩＰアドレスやデータの名前から数値がハッシュ値として計算される。また、ハッシュ関数の値域はリング形態のハッシュ空間で表される。
【０００３】
図８は、リング形態のハッシュ空間の一例を示す図である。図８において、あるサーバは、リング上のある範囲のハッシュ値を持つデータを担当する。例えば、「サーバＳ００」は、黒塗りされた範囲のデータを担当し、「サーバＳ１１」は、斜線で模様づけされた範囲のデータを担当する。
【０００４】
そして、データの配置については、データ名のハッシュ値からリング上の位置が求まり、さらに担当するサーバが決まり、決まったサーバに第１番目の複製（１stレプリカ）が配置される。第２番目のレプリカ（２ndレプリカ）は、例えばリングを時計回りに回った次の領域を担当するサーバ（「データ１」の場合は「サーバＳ１１」）に配置される。
【０００５】
２ndレプリカの配置の仕方はリングの時計回りの次の領域以外の選び方もあるが、サーバが一つ故障してもデータにアクセスできることが複数のレプリカを持つ目的であるから、２つのレプリカを同一のサーバに置かないように２ndレプリカの配置を選ぶ必要がある。例えば、１stレプリカ用にはデータの名前からハッシュ値を求め、２ndレプリカ用には違う値からハッシュ値を求めて同じリング上で配置サーバを決めたとすると、２つのハッシュ値が同一の担当範囲にはいり、レプリカが同一のサーバに配置されるかもしれない。
【０００６】
この場合、２つのレプリカが配置されたサーバが故障すると２つのレプリカへのアクセスが不可能となり、データの消失を招くことになる。なお、データの名前からハッシュ値を求める以外のハッシュ値の求め方としては、例えば、名前を逆さにする、あるいはデータの値自体からハッシュ値を求めるなどの方法がある。
【０００７】
また、複数のレプリカを記憶する分散データ管理システムで、データの値から得られる値に基づいて選択したノードにデータを書き込むと共に、メタデータから得られる値に基づいて選択したノードにデータを書き込む従来技術がある（例えば、特許文献１参照）。
【０００８】
また、分散システム内の指定された範囲内にあるデータ蓄積域にデータ要求側が要求する可能性のあるデータのレプリカを事前に生成、蓄積しておき、データ要求側から要求を受信すると、レプリカを用いて応答する従来技術がある（例えば、特許文献２参照）。また、ストレージノードの容量、データ記憶コスト、場所などの特徴に基づいてレプリカの配置を決定する従来技術がある（例えば、特許文献３参照）。
【先行技術文献】
【特許文献】
【０００９】
【特許文献１】特開２０１０−２７１７９８号公報
【特許文献２】特開２００７−１３３５０３号公報
【特許文献３】特表２０１２−５２４９４７号公報
【発明の概要】
【発明が解決しようとする課題】
【００１０】
コンシステントハッシュ方式は、データの名前をハッシュ関数によりハッシュすることで、ほぼ均等にデータが分配されるという特性を持つ。レプリカも、リング上で次の領域を担当するサーバに置かれるので、同様にほぼ均等に分配されることになる。
【００１１】
一方、データの利用を考えると、一連のデータをなるべく多くのサーバに配置したい場合と、なるべく少数のサーバに配置したい場合がある。例えば、動画を分割して、データＡ、データＢ、・・・のようにしたとき、動画として再生したい場合は、順番に読まれるので、なるべく１つのサーバにまとめてデータを置きたい。一方、動画の解析（色の分布を調べるなど）の場合は、並列に読み出して高速に処理するためにデータをなるべく多くのサーバに配置した方が有利になる。
【００１２】
このように、データはその使われ方によって、なるべく多くのサーバに分散しておいた方がよい場合と、なるべく少数のサーバにまとめた方がよい場合とがある。しかしながら、一般にデータがどう使われるかは、処理によって変わるので、予めどちらかだけのデータ配置にすべきかを決めることはできないという問題がある。また、同一データのレプリカは同一サーバに記憶させてはいけないことは必須の要件である。
【００１３】
本発明は、１つの側面では、一連のデータを多くのサーバに配置したい場合と、少数のサーバに配置したい場合の両方に対応すると共に、同一データのレプリカを同一サーバに記憶させない記憶装置、複製方法及び複製プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１４】
本願の開示する記憶装置は、１つの態様において、複数の記憶ノードを用いてデータの複数のレプリカを記憶する記憶装置であり、第１の決定部と第２の決定部とを備える。第１の決定部は、データが記憶ノードに分散して記憶されるように第１のレプリカの記憶ノードへの配置を決定する。第２の決定部は、データが同一の記憶ノードに連続して記憶され、かつ、第１のレプリカを記憶する記憶ノードと異なる記憶ノードに記憶されるように第２のレプリカの記憶ノードへの配置を決定する。
【発明の効果】
【００１５】
１実施態様によれば、一連のデータを多くのサーバに配置したい場合と、少数のサーバに配置したい場合の両方に対応すると共に、同一データのレプリカを同一サーバに記憶させないようにすることができる。
【図面の簡単な説明】
【００１６】
【図１】図１は、実施例に係る分散ストレージの構成を示す図である。
【図２】図２は、実施例に係る分散ストレージによるレプリカ配置を説明するための図である。
【図３】図３は、複製装置の機能構成を示す図である。
【図４】図４は、第２配置先決定部がデータ分散テーブルの行を増やす場合の例を示す図である。
【図５】図５は、２ndレプリカの配置処理のフローを示すフローチャートである。
【図６】図６は、読み出し処理のフローを示すフローチャートである。
【図７】図７は、実施例に係る複製プログラムを実行するコンピュータのハードウェア構成を示す図である。
【図８】図８は、リング形態のハッシュ空間の一例を示す図である。
【発明を実施するための形態】
【００１７】
以下に、本願の開示する記憶装置、複製方法及び複製プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例は開示の技術を限定するものではない。
【実施例】
【００１８】
まず、実施例に係る分散ストレージの構成について説明する。図１は、実施例に係る分散ストレージの構成を示す図である。図１に示すように、分散ストレージ１は、複数の複製装置２と、複数のサーバ３とを有する。
【００１９】
複製装置２は、分散ストレージ１のユーザが分散ストレージ１のアクセスに使用するクライアント５からインターネット６を介してデータアクセス要求を受け付ける装置である。複製装置２は、データの書き込み要求をクライアント５から受け付けると、データの２つのレプリカを異なるサーバ３に転送する。
【００２０】
また、複製装置２は、データの読み出し要求をクライアント５から受け付けると、データのレプリカを記憶する２つのサーバ３のいずれかからデータを読み出してクライアント５に送信する。なお、複製装置２とクライアント５は１対１に対応する。
【００２１】
サーバ３は、データのレプリカをＨＤＤ（Hard  Disk  Drive）に記憶する記憶ノードである。なお、複数の複製装置２は、複数のサーバ３とＬＡＮ（Local  Area  Network）４を介して接続されるが、他のネットワークを介して接続されてもよい。また、複製装置２間は通信が可能である。
【００２２】
次に、実施例に係る分散ストレージ１によるレプリカ配置について説明する。図２は、実施例に係る分散ストレージ１によるレプリカ配置を説明するための図である。図２に示すように、複製装置２はレプリカの配置に用いられるデータ分散テーブル２２と、２ndレプリカの最終送付先のサーバ３の識別子を記憶する最終送付先記憶部２４とを有する。
【００２３】
複製装置２は、１stレプリカをデータ分散テーブル２２の１st列に識別子が記憶されたいずれかのサーバ３からデータのハッシュ値に基づいて選択されたサーバ３に１stレプリカを配置する。また、複製装置２は、２ndレプリカを最終送付先記憶部２４が識別子を記憶するサーバ３に配置し、データ分散テーブル２２の２nd列に送付先のサーバ３の識別子を記憶する。
【００２４】
ただし、複製装置２は、最終送付先記憶部２４が識別子を記憶するサーバ３が１stレプリカを配置したサーバ３と同じである場合には、ハッシュ空間を示すリングで最終送付先の次のサーバ３に２ndレプリカを配置する。そして、複製装置２は、２ndレプリカを配置したサーバ３の識別子で最終送付先記憶部２４を更新し、データ分散テーブル２２の２nd列に送付先のサーバ３の識別子を記憶する。
【００２５】
例えば、データから計算されたハッシュ値が「ａｂｃ」である場合には、複製装置２は、１stレプリカをデータ分散テーブル２２の１st列に識別子「Ｃ」が記憶された「サーバＣ」に配置する。そして、複製装置２は、２ndレプリカを最終送付先記憶部２４に識別子「Ｄ」が記憶された「サーバＤ」に配置し、データ分散テーブル２２の２nd列に送付先のサーバ３の識別子「Ｄ」を記憶する。
【００２６】
このように、複製装置２は、データのハッシュ値に基づいて選択されたサーバ３に１stレプリカを配置する。したがって、複製装置２は、１stレプリカを用いて一連のデータを多くのサーバ３に分散して配置することができる。このため、例えば色の分布を調べるなどの動画解析で、分散ストレージ１は、データを並列に読み出すことができ、高速にデータを読み出すことができる。
【００２７】
また、複製装置２は、データの最終送付先に２ndレプリカを配置する。したがって、複製装置２は、２ndレプリカを用いて一連のデータを同一のサーバ３に配置することができる。このため、例えば複数のファイルに分割して分散ストレージ１に格納した動画を再生する場合など、分散ストレージ１は、一連のファイルを同一サーバ３から高速に読み出すことができる。
【００２８】
また、複製装置２は、最終送付先が１stレプリカの配置先と同じである場合には、ハッシュ空間を示すリングで最終送付先の次のサーバ３に２ndレプリカを配置する。したがって、複製装置２は、１stレプリカと２ndレプリカを異なるサーバ３に配置することができる。
【００２９】
次に、複製装置２の機能構成について説明する。図３は、複製装置２の機能構成を示す図である。図３に示すように、複製装置２は、受信部２１と、データ分散テーブル２２と、第１配置先決定部２３と、最終送付先記憶部２４と、第２配置先決定部２５と、転送部２６と、読出部２７と、テーブル同期部２８とを有する。
【００３０】
受信部２１は、クライアント５から分散ストレージ１へのアクセス要求を受信し、データの書き込み要求であればアクセス要求を第１配置先決定部２３及び第２配置先決定部２５に渡し、データの読み出し要求であればアクセス要求を読出部２７に渡す。
【００３１】
データ分散テーブル２２は、レプリカの配置先の決定に用いられるテーブルであり、ハッシュ範囲と各レプリカの配置先のサーバ３の識別子を対応させて記憶する。図２に示した例では、データ分散テーブル２２は、ハッシュ範囲毎に、１stと２ndを記憶する。１stは、１stレプリカの配置先のサーバ３の識別子を示し、２ndは、２ndレプリカの配置先のサーバ３の識別子を示す。１stは、ハッシュ範囲から静的に決定される配置先を示し、２ndは、ハッシュ範囲、最終送付先などから動的に決定される配置先を示す。２ndの初期値は、空白である。
【００３２】
図２に示した例では、データ分散テーブル２２は、ハッシュ範囲「０００〜ａａａ」に対応付けて、１stレプリカの配置先のサーバ３の識別子として静的に決定される「Ａ」を記憶し、２ndレプリカの配置先のサーバ３の識別子はこの時点では記憶していない。また、データ分散テーブル２２は、ハッシュ範囲「ａａａ〜ａｆａ」に対応付けて、１stレプリカの配置先のサーバ３の識別子として静的に決定される「Ｃ」を記憶し、２ndレプリカの配置先のサーバ３の識別子として動的に決定された「Ｄ」を記憶する。
【００３３】
データ分散テーブル２２は、複数の複製装置２で同一の情報を記憶する。したがって、データ分散テーブル２２の情報は、複製装置２の間で同期がとられる。また、データ分散テーブル２２の行数はサーバ数に比べて非常に大きく、例えばサーバ数の１万倍程度である。
【００３４】
第１配置先決定部２３は、データの書き込み要求を受信部２１から受け取り、書き込みデータからハッシュ値を計算する。そして、第１配置先決定部２３は、１stレプリカの配置先をハッシュ値及びデータ分散テーブル２２に基づいて決定し、決定した配置先を書き込みデータと共に転送部２６に渡す。
【００３５】
最終送付先記憶部２４は、２ndレプリカの最終送付先のサーバ３の識別子を記憶する。複製装置２はクライアント５と１対１に対応するため、最終送付先記憶部２４は、クライアント５毎に最終送付先のサーバ３の識別子を記憶する。最終送付先記憶部２４の初期値はランダムに決定される。
【００３６】
第２配置先決定部２５は、データの書き込み要求を受信部２１から受け取り、書き込みデータからハッシュ値を計算する。そして、第２配置先決定部２５は、２ndレプリカの配置先をハッシュ値、データ分散テーブル２２及び最終送付先記憶部２４に基づいて決定し、決定した配置先を書き込みデータと共に転送部２６に渡す。
【００３７】
第２配置先決定部２５は、クライアント５から書き込みが行われる一連のデータの２ndレプリカが、なるべく同一のサーバ３に配置されるように配置先を決定する。具体的には、第２配置先決定部２５は、データのハッシュ値に対応するデータ分散テーブル２２の２ndの列が空白ならば、２ndの列を最終送付先記憶部２４が記憶する値に設定し、最終送付先に２ndレプリカを配置する。これで、このクライアント５から前回書かれた２ndレプリカと同じサーバ３に２ndレプリカが配置されることになる。
【００３８】
ただし、１st列と最終送付先記憶部２４が記憶する値が同一の場合は、そのままでは２つのレプリカが同一のサーバ３に置かれてしまう。そのような場合には、第２配置先決定部２５は、２ndレプリカを前回書いたサーバ３に続けて書くことを諦めて、最終送付先記憶部２４が記憶する値をハッシュ空間を示すリング上で時計方向に一つ移動した値に変更する。
【００３９】
データのハッシュ値に対応するデータ分散テーブル２２の２ndの列が最終送付先記憶部２４が記憶する値と等しいならば、第２配置先決定部２５は、最終送付先記憶部２４が示すサーバ３に２ndレプリカを配置する。なお、２ndの列が最終送付先記憶部２４が記憶する値と等しいときは、それまでの処理により１st列と２nd列の値が等しいことはない。
【００４０】
データのハッシュ値に対応するデータ分散テーブル２２の２ndの列が空白でもなく、最終送付先記憶部２４が記憶する値と等しくもない場合は、第２配置先決定部２５は、このままでは、前回書いたサーバ３に２ndレプリカを続けて書くことができない。そこで、第２配置先決定部２５は、データ分散テーブル２２のハッシュ値に対応する行の担当範囲を複数の行に分割することを所定の最大回（例えば１０回）に渡って試みる。
【００４１】
具体的には、第２配置先決定部２５は、ハッシュ値に対応する行をｎ（例えば１００）行に分け、それまで２ndレプリカを保持していたサーバ３（２nd列に書かれているサーバ３）に増やした行のどの行に対応するデータを保持しているかを聞く。そして、第２配置先決定部２５は、２ndレプリカを保持していたサーバ３が回答した行の２nd列に分割前の２nd列に書かれていた値を設定する。これにより、データのハッシュ値に対応するデータ分散テーブル２２の２ndの列が空白になり、最終送付先と同じサーバ３に２ndレプリカを配置することができる可能性がでる。
【００４２】
ただし、所定の最大回分割を試みても２nd列が空白にならない場合には、第２配置先決定部２５は、２ndレプリカを前回書いたサーバ３に続けて書くことを諦める。そして、第２配置先決定部２５は、２nd列の示すサーバ３にデータを配置すると共に、最終送付先記憶部２４をそのサーバ３の識別子に更新する。
【００４３】
このように、第２配置先決定部２５は、２ndレプリカの配置先を予め決めておくのではなく、データを蓄積していく過程で決めて行く。したがって、分散ストレージ１は、２ndレプリカの配置状況に応じて適切に新たな２ndレプリカを配置することができる。
【００４４】
図４は、第２配置先決定部２５がデータ分散テーブル２２の行を増やす場合の例を示す図である。ハッシュ値が「ａｄａ」のデータＹを書き込み済で、データ分散テーブル２２が図４（ａ）に示す状態であるとする。なお、ハッシュ範囲「ｐｐｐ〜ｑｑｑ」は、ハッシュ値が「ｐｐｐ」以上「ｑｑｑ」未満を示す。
【００４５】
このとき、最終送付先記憶部２４の値＝Ｂである複製装置２から、ハッシュ値が「ａｂｃ」であるデータＸを書き込む場合、データＸのハッシュ値「ａｂｃ」を担当するのは、データ分散テーブル２２のハッシュ範囲から２行目になる。したがって、図４（ａ）の２行目の１st列の値「Ｃ」より、１stレプリカはサーバＣに配置される。
【００４６】
データ分散テーブル２２の２行目の２nd列はＤであり、空白でも、最終送付先記憶部２４が記憶する値＝Ｂと等しくもないので、第２配置先決定部２５は、データ分散テーブル２２の行数を増やす。この例では、第２配置先決定部２５は４行増やす。
【００４７】
そして、第２配置先決定部２５は、元々の２行目の２ndレプリカに対応するデータを持っているサーバ３の識別子は「Ｄ」なので、行数を増やした部分のどの行に２nd列の識別子を設定すべきかをサーバＤに聞き、サーバＤが回答した行の２nd列に「Ｄ」を設定する。
【００４８】
図４（ｂ）は、第２配置先決定部２５によるデータ分散テーブル２２のアップデート結果を示す。図４（ｂ）に示すように、ハッシュ値が「ａｄａ」であるデータＹは、行を増加させたデータ分散テーブル２２では５行目で管理されるので、５行目の２ndは「Ｄ」になる。一方、その他の増加した行に対応する２ndレプリカは存在しないので、その他の増加した行に対応する２nd列は空白となる。
【００４９】
そして、図４（ｂ）のデータ分散テーブル２２でデータＸのハッシュ値「ａｂｃ」を担当するのは、３行目になる。３行目の２nd列は空白であり、第２配置先決定部２５は、最終送付先記憶部２４が示す、前回２ndレプリカを書き込んだサーバＢを２ndレプリカの配置先とし、データ分散テーブル２２を図４（ｃ）に示すように更新する。
【００５０】
図３に戻って、転送部２６は、第１配置先決定部２３又は第２配置先決定部２５からデータとデータの送信先指定とを受け取り、指定された送信先サーバ３にデータを送信する。
【００５１】
読出部２７は、受信部２１からデータの読み出し要求を受け取り、データを読み出すサーバ３を特定する。データの読み出し要求には同一サーバ３から読み出したいデータであるか否かが指定されており、読出部２７は、同一サーバ３から読み出したいデータであるか否かの指定とデータ分散テーブル２２に基づいてデータを読み出すサーバ３を特定する。
【００５２】
すなわち、読出部２７は、同一サーバ３から読み出したいデータである場合には、データ分散テーブル２２の２nd列を用いてデータを読み出すサーバ３を特定する。一方、同一サーバ３から読み出したいデータでない場合には、読出部２７は、データ分散テーブル２２の１st列を用いてデータを読み出すサーバ３を特定する。そして、読出部２７は、特定したサーバ３からデータを読み出す。
【００５３】
テーブル同期部２８は、他の複製装置２との間でデータ分散テーブル２２の情報の同期をとる。テーブル同期部２８は、行の増加や２nd列の更新などがあると、他の複製装置２との間で同期を行う。
【００５４】
次に、２ndレプリカの配置処理のフローについて説明する。図５は、２ndレプリカの配置処理のフローを示すフローチャートである。図５に示すように、第２配置先決定部２５は、まずｃｏｕｎｔを「１」で初期化する（ステップＳ１）。ここで、ｃｏｕｎｔは、データ分散テーブル２２の行を分割する回数を数えるためのカウンタである。
【００５５】
そして、第２配置先決定部２５は、データのハッシュ値を求め、データ分散テーブル２２のハッシュ範囲がデータのハッシュ値を含む行のｉｄを特定する（ステップＳ２）。ここで、ｉｄは行の番号である。そして、第２配置先決定部２５は、データ分散テーブル２２の２nd列のｉｄ行の識別子を判定する（ステップＳ３）。
【００５６】
その結果、データ分散テーブル２２の２nd列のｉｄ行の識別子が最終送付先記憶部２４が記憶する値と等しい場合には、転送部２６が、データをデータ分散テーブルの２nd列のｉｄ行が示すサーバ３に転送する（ステップＳ７）。
【００５７】
また、データ分散テーブル２２の２nd列のｉｄ行の識別子が空白である場合には、第２配置先決定部２５は、データ分散テーブル２２のｉｄ行の１st列の識別子と最終送付先記憶部２４が記憶する値が一致するか否かを判定する（ステップＳ４）。その結果、一致する場合には、第２配置先決定部２５は、最終送付先記憶部２４が記憶する値をリング上で次のサーバ３の識別子に変更し（ステップＳ５）、一致しない場合には、ステップＳ６に進む。
【００５８】
そして、第２配置先決定部２５は、データ分散テーブル２２の２nd列のｉｄ行に最終送付先記憶部２４が記憶する値を代入する（ステップＳ６）。そして、転送部２６が、データをデータ分散テーブルの２nd列のｉｄ行が示すサーバ３に転送する（ステップＳ７）。
【００５９】
また、データ分散テーブル２２の２nd列のｉｄ行の識別子が最終送付先記憶部２４が記憶する値と等しくなく、かつ、空白でもない場合には、第２配置先決定部２５は、ｃｏｕｎｔに「１」を加える（ステップＳ８）。そして、第２配置先決定部２５は、ｃｏｕｎｔの値が所定の最大回数より大きいか否かを判定する（ステップＳ９）。
【００６０】
その結果、ｃｏｕｎｔの値が所定の最大回数より大きくない場合には、第２配置先決定部２５は、データ分散テーブル２２のｉｄ行をｎ行に分ける（ステップＳ１０）。ここで、ｎは例えば１００である。また、分けて得られる各行の１st列は元と同じであり、２nd列は空白である。例えば、図４（ｂ）では、ｎを５として、ハッシュ範囲「ａａａ〜ａｆａ」の行が５行に分けられ、分けられた各行の１st列は元のハッシュ範囲「ａａａ〜ａｆａ」の１st列と同じ「Ｃ」となる。
【００６１】
そして、第２配置先決定部２５は、ｉｄ行に相当するデータを格納しているサーバ３に対し、増やしたどの行に対応させてデータを保持しているかを聞き、その行の２nd列にそのサーバ３の識別子を設定する（ステップＳ１１）。例えば、図４（ｂ）では、ハッシュ値が「ａｄａ」であるデータＹは、「サーバＤ」が格納しているので、第２配置先決定部２５は、増やしたどの行に対応させてデータを保持しているかを「サーバＤ」に聞く。そして、第２配置先決定部２５は、「サーバＤ」から５行目であると知らされると、５行目の２nd列を「Ｄ」に設定する。そして、第２配置先決定部２５は、ステップＳ２に戻る。そして、データＸのハッシュ値「ａｂｃ」を担当するのは、データ分散テーブル２２の３行目になるので、ステップＳ２において、第２配置先決定部２５は、ｉｄを「３」として特定する。そして、ステップＳ６において、第２配置先決定部２５は、図４（ｃ）に示すように、データ分散テーブル２２の３行目に、最終送付先記憶部２４が記憶する「Ｂ」を代入する。
【００６２】
一方、ｃｏｕｎｔの値が所定の最大回数より大きい場合には、転送部２６が、データをデータ分散テーブル２２の２nd列のｉｄ行が示すサーバ３に転送する（ステップＳ１２）。また、第２配置先決定部２５は、最終送付先記憶部２４の値を転送先のサーバ３の識別子に更新する（ステップＳ１３）。
【００６３】
このように、第２配置先決定部２５がハッシュ値とデータ分散テーブル２２と最終送付先記憶部２４に基づいて２ndレプリカの配置を決定することで、分散ストレージ１は２ndレプリカを用いて一連のデータをできる限り同一のサーバ３に格納することができる。
【００６４】
次に、読み出し処理のフローについて説明する。図６は、読み出し処理のフローを示すフローチャートである。図６に示すように、読出部２７は、データのハッシュ値を求め、データ分散テーブル２２の該当行のｉｄを特定する（ステップＳ２１）。
【００６５】
そして、読出部２７は、読み出し要求に基づいて、同一サーバ３から読み出したいデータであるか否かを判定する（ステップＳ２２）。その結果、同一サーバ３から読み出したいデータである場合には、読出部２７は、データ分散テーブル２２の２nd列のｉｄ行が示すサーバ３からデータを読み出す（ステップＳ２３）。
【００６６】
一方、同一サーバ３から読み出したいデータでない場合には、読出部２７は、データ分散テーブル２２の１st列のｉｄ行が示すサーバ３からデータを読み出す（ステップＳ２４）。
【００６７】
このように、読出部２７が読み出し要求に基づいて１stレプリカ又は２ndレプリカを読み出すことによって、分散ストレージ１はクライアント５の要求に適したレプリカを用いて高速にデータを読み出すことができる。
【００６８】
上述してきたように、実施例では、第１配置先決定部２３がデータが分散して配置されるように１stレプリカの配置先を決定する。また、第２配置先決定部２５がデータが同一のサーバ３に連続して記憶され、かつ１stレプリカと異なるサーバに記憶されるように２ndレプリカの配置を決定する。したがって、分散ストレージ１は、一連のデータを多くのサーバに配置したい場合と、少数のサーバに配置したい場合の両方に対応すると共に、同一データのレプリカを同一サーバに記憶させないようにすることができる。
【００６９】
また、実施例では、データ分散テーブル２２が１stレプリカと２ndレプリカの配置先のサーバ３の識別子をハッシュ範囲毎に記憶し、最終送付先記憶部２４が２ndレプリカの最終配布先のサーバ３の識別子を記憶する。そして、第２配置先決定部２５は、データのハッシュ値、データ分散テーブル２２及び最終送付先記憶部２４に基づいて２ndレプリカの配置先を決定する。したがって、第２配置先決定部２５は、データが同一のサーバ３に連続して記憶され、かつ１stレプリカと異なるサーバに記憶されるように２ndレプリカの配置を決定することができる。
【００７０】
また、実施例では、ハッシュ値に基づく２ndレプリカの配置先と、最終送付先記憶部２４に基づく最終送付先が異なる場合に、第２配置先決定部２５は、ハッシュ範囲を分割して両者が一致するよう試みる。したがって、第２配置先決定部２５は、一連のデータができるだけ同一のサーバ３に記憶されるように、２ndレプリカを配置することができる。
【００７１】
また、実施例では、第２配置先決定部２５は、ハッシュ範囲の分割を所定の回数繰り返してもハッシュ値に基づく配置先と最終送付先を一致させることができない場合に、ハッシュ値に基づく配置先に２ndレプリカを配置する。したがって、データが同一のサーバ３だけに過度に集中することを防ぐことができる。
【００７２】
なお、実施例では、複製装置２について説明したが、複製装置２が有する構成をソフトウェアによって実現することで、同様の機能を有する複製プログラムを得ることができる。そこで、複製プログラムを実行するコンピュータについて説明する。なお、コンピュータは、複数の複製プログラムを実行することができる。
【００７３】
図７は、実施例に係る複製プログラムを実行するコンピュータのハードウェア構成を示す図である。図７に示すように、コンピュータ３０は、メインメモリ３１と、ＣＰＵ（Central  Processing  Unit）３２と、ＬＡＮインタフェース３３と、ＨＤＤ３４とを有する。また、コンピュータ３０は、スーパーＩＯ（Input  Output）３５と、ＤＶＩ（Digital  Visual  Interface）３６と、ＯＤＤ（Optical  Disk  Drive）３７とを有する。
【００７４】
メインメモリ３１は、プログラムやプログラムの実行途中結果などを記憶するメモリである。ＣＰＵ３２は、メインメモリ３１からプログラムを読み出して実行する中央処理装置である。ＣＰＵ３２は、メモリコントローラを有するチップセットを含む。
【００７５】
ＬＡＮインタフェース３３は、コンピュータ３０をＬＡＮ経由で他のコンピュータに接続するためのインタフェースである。ＨＤＤ３４は、プログラムやデータを格納するディスク装置であり、スーパーＩＯ３５は、マウスやキーボードなどの入力装置を接続するためのインタフェースである。ＤＶＩ３６は、液晶表示装置を接続するインタフェースであり、ＯＤＤ３７は、ＤＶＤの読み書きを行う装置である。
【００７６】
ＬＡＮインタフェース３３は、ＰＣＩエクスプレスによりＣＰＵ３２に接続され、ＨＤＤ３４及びＯＤＤ３７は、ＳＡＴＡ（Serial  Advanced  Technology  Attachment）によりＣＰＵ３２に接続される。スーパーＩＯ３５は、ＬＰＣ（Low  Pin  Count）によりＣＰＵ３２に接続される。
【００７７】
そして、コンピュータ３０において実行される複製プログラムは、ＤＶＤに記憶され、ＯＤＤ３７によってＤＶＤから読み出されてコンピュータ３０にインストールされる。あるいは、複製プログラムは、ＬＡＮインタフェース３３を介して接続された他のコンピュータシステムのデータベースなどに記憶され、これらのデータベースから読み出されてコンピュータ３０にインストールされる。そして、インストールされた複製プログラムは、ＨＤＤ３４に記憶され、メインメモリ３１に読み出されてＣＰＵ３２によって実行される。
【００７８】
また、実施例では、複製装置が分散ストレージに含まれる場合について説明したが、本発明はこれに限定されるものではなく、例えば、複製プログラムがクライアントに近接するコンピュータやクライアントで実行される場合にも同様に適用することができる。
【００７９】
また、実施例では、ハッシュを用いてレプリカの配置を決定する場合について説明したが、本発明はこれに限定されるものではなく、例えば、順番に配置サーバを交替していく場合など他の方法でレプリカの配置を決定する場合にも同様に適用することができる。
【００８０】
また、実施例では、複製装置とクライアントが１対１に対応する場合について説明したが、本発明はこれに限定されるものではなく、ｍ及びｎを任意の正の整数として、複製装置とクライアントがｍ対ｎに対応する場合にも同様に適用することができる。
【符号の説明】
【００８１】
１    分散ストレージ
２    複製装置
３    サーバ
４    ＬＡＮ
５    クライアント
２１    受信部
２２    データ分散テーブル
２３    第１配置先決定部
２４    最終送付先記憶部
２５    第２配置先決定部
２６    転送部
２７    読出部
２８    テーブル同期部
３０    コンピュータ
３１    メインメモリ
３２    ＣＰＵ
３３    ＬＡＮインタフェース
３４    ＨＤＤ
３５    スーパーＩＯ
３６    ＤＶＩ
３７    ＯＤＤ
【図１】
2015141451.tif 000003
【図２】
2015141451.tif 000004
【図３】
2015141451.tif 000005
【図４】
2015141451.tif 000006
【図５】
2015141451.tif 000007
【図６】
2015141451.tif 000008
【図７】
2015141451.tif 000009
【図８】
2015141451.tif 000010