ストレージ制御方法、情報処理装置およびプログラム
【課題】データの移動量を低減できる。
【解決手段】制御部１ｂは、第１のノード２に割り当てるハッシュ値の範囲と第２のノード２ａに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノード２に割り当てるハッシュ値の範囲を拡大する。制御部１ｂは、第２のノード２ａに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを、第２のノード２ａから第１のノード２に移動させる。
【解決手段】制御部１ｂは、第１のノード２に割り当てるハッシュ値の範囲と第２のノード２ａに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノード２に割り当てるハッシュ値の範囲を拡大する。制御部１ｂは、第２のノード２ａに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを、第２のノード２ａから第１のノード２に移動させる。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はストレージ制御方法、情報処理装置およびプログラムに関する。
【背景技術】
【０００２】
現在、分散ストレージシステムが利用されている。分散ストレージシステムは、ネットワークで接続された複数のストレージノードを備える。複数のストレージノードにデータを分散配置することで、データアクセスの高速化を図れる。
【０００３】
分散ストレージシステムでは、ストレージノードに配置するデータの管理が行われる。例えば、サーバ装置がストレージ記憶装置の負荷を監視し、当該負荷に応じて、顧客データを別筐体のストレージ装置に再配置して、アクセスを分散する提案がある。また、例えば、ホスト計算機が、複数のストレージサブシステム上の物理ディスクを束ねた仮想ディスクを管理し、当該仮想ディスクへの入出力要求を制御する提案もある。
【０００４】
ところで、ＫＶＳ（Key - Value Store）と呼ばれる手法を用いた分散ストレージシステムがある。ＫＶＳでは、何れかのストレージノードに、データ（ｖａｌｕｅ）にキー（ｋｅｙ）を付与した（ｋｅｙ，ｖａｌｕｅ）のペアを保存する。保存したデータを取得する際は、キーを指定して、対応するデータを取得する。キーに応じて異なるストレージノードにデータを格納することで、データを分散配置する。
【０００５】
ＫＶＳでは、キーから算出されるハッシュ値に応じて、データ格納先のストレージノードを判定することがある。各ストレージノードには、それぞれが担当するハッシュ値の範囲を割り当てておく。例えば、第１ノードにハッシュ値“１１〜５０”、第２ノードにハッシュ値“５１〜９０”などのように担当範囲が割り当てられる。この方法は、Consistent Hashingと呼ばれることもある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−５０００７号公報
【特許文献２】特開２０１０−１２８６３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
分散ストレージシステムでは、各ストレージノードにハッシュ値の範囲を割り当てた後に、ストレージノードによってデータ量や受付アクセス数に偏りが生じることがある。その場合、偏りを解消するため、ハッシュ値の範囲の割り当てを変更したいことがある。
【０００８】
しかし、あるストレージノードに対するハッシュ値の範囲の割り当てを一度解除して再定義するという方法を用いると、解除に伴うデータの退避および再定義に伴うデータの引き継ぎという大量のデータ移動が、ストレージノード間で発生する可能性がある。また、当該方法では、変更前に当該ストレージノードが保持しているデータであって変更後も引き続き保持するデータについても移動が発生してしまい、非効率的となる。
【０００９】
一側面では、本発明は、データの移動量を低減できるストレージ制御方法、情報処理装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
一実施態様では、複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムが実行するストレージ制御方法が提供される。このストレージ制御方法では、第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノードに割り当てるハッシュ値の範囲を拡大する。第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを検索し、検索されたデータを第２のノードから第１のノードに移動する。
【００１１】
また、一実施態様では、複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられる情報処理装置が提供される。この情報処理装置は、記憶部と制御部とを有する。記憶部は、複数のノードに割り当てたハッシュ値の範囲を示す情報を記憶する。制御部は、第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノードに割り当てるハッシュ値の範囲を拡大し、第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを、第２のノードから第１のノードに移動させる。
【００１２】
また、一実施態様では、コンピュータに実行させるプログラムであって、複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられるプログラムが提供される。
【発明の効果】
【００１３】
一実施態様によれば、データの移動量を低減できる。
【図面の簡単な説明】
【００１４】
【図１】第１の実施の形態の情報処理システムを示す図である。
【図２】第２の実施の形態の分散ストレージシステムを示す図である。
【図３】ストレージ制御装置のハードウェア例を示す図である。
【図４】第２の実施の形態のソフトウェア例を示すブロック図である。
【図５】ハッシュ値の担当範囲の割当例を示す図である。
【図６】担当管理テーブルの例を示す図である。
【図７】ノード利用管理テーブルの例を示す図である。
【図８】担当範囲を拡大する処理例を示すフローチャートである。
【図９】移設するハッシュ値範囲の例を示す図である。
【図１０】Ｒｅａｄ要求受信時の処理例を示すフローチャートである。
【図１１】Ｗｒｉｔｅ要求受信時の処理例を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理システムを示す図である。この情報処理システムは、キーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムである。この情報処理システムは、情報処理装置１、第１のノード２および第２のノード２ａを含む。情報処理装置１、第１のノード２および第２のノード２ａは、ネットワークで接続されている。
【００１６】
例えば、第１のノード２には、（ｋｅｙ，ｖａｌｕｅ）のペアとして、（ｋｅｙ１，ｖａｌｕｅ１）、（ｋｅｙ２，ｖａｌｕｅ２）、（ｋｅｙ３，ｖａｌｕｅ３）が格納されている。第１のノード２が担当するハッシュ値の範囲には、ハッシュ値Ｈ（ｋｅｙ１），Ｈ（ｋｅｙ２），Ｈ（ｋｅｙ３）が含まれる。また、例えば、第２のノード２ａには、（ｋｅｙ，ｖａｌｕｅ）のペアとして、（ｋｅｙ４，ｖａｌｕｅ４）、（ｋｅｙ５，ｖａｌｕｅ５）、（ｋｅｙ６，ｖａｌｕｅ６）が格納されている。第２のノード２ａが担当するハッシュ値の範囲には、ハッシュ値Ｈ（ｋｅｙ４），Ｈ（ｋｅｙ５），Ｈ（ｋｅｙ６）が含まれる。ここで、Ｈ（ｋｅｙＮ）は、ｋｅｙＮから算出されたハッシュ値である（Ｎ＝１，２，３，４，５，６）。第１のノード２および第２のノード２ａにそれぞれ割り当てられたハッシュ値の担当範囲は隣接している。
【００１７】
情報処理装置１は、ＣＰＵ（Central Processing Unit）などのプロセッサとＲＡＭ（Random Access Memory）などのメモリとを備えてもよく、メモリに記憶されたプログラムをプロセッサが実行するコンピュータであってもよい。情報処理装置１は、記憶部１ａおよび制御部１ｂを有する。
【００１８】
記憶部１ａは、第１のノード２および第２のノード２ａに割り当てたハッシュ値の範囲を示す情報を記憶する。記憶部１ａは、ＲＡＭやＨＤＤ（Hard Disk Drive）によって実装されてもよい。
【００１９】
制御部１ｂは、記憶部１ａを参照して、各ノードに割り当てるハッシュ値の範囲を変更する。制御部１ｂは、第１のノード２に割り当てるハッシュ値の範囲と第２のノード２ａに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノード２に割り当てるハッシュ値の範囲を拡大する。第１のハッシュ値は、Ｈ（ｋｅｙ３）とＨ（ｋｅｙ４）との間の値であるとする。また、第２のハッシュ値は、Ｈ（ｋｅｙ４）とＨ（ｋｅｙ５）との間の値であるとする。この場合、制御部１ｂが第１のノード２に割り当てるハッシュ値の範囲を拡大すると、第１のノード２の担当範囲にＨ（ｋｅｙ４）が含まれることになる。
【００２０】
制御部１ｂは、第２のノード２ａに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを検索し、検索されたデータを第２のノード２ａから第１のノード２に移動する。例えば、制御部１ｂは、第１のハッシュ値と第２のハッシュ値との間に存在するハッシュ値Ｈ（ｋｅｙ４）に対応する“ｖａｌｕｅ４”を検索する。制御部１ｂは、検索した“ｖａｌｕｅ４”を第１のノード２に移動する。
【００２１】
なお、制御部１ｂは、移動対象のハッシュ値範囲を第２のノード２ａに通知して、第２のノード２ａに当該検索を行わせてもよい。また、第２のノード２ａが、移動対象として検索した“ｖａｌｕｅ４”を第１のノード２に移動してもよい。すなわち、制御部１ｂは、検索されたデータの第１のノード２への移動を、第２のノード２ａに行わせてもよい。
【００２２】
情報処理装置１によれば、制御部１ｂにより、第１のノード２に割り当てるハッシュ値の範囲と第２のノード２ａに割り当てるハッシュ値の範囲との境界が、第１のハッシュ値から第２のハッシュ値にシフトされることで、第１のノード２に割り当てるハッシュ値の範囲が拡大される。制御部１ｂにより、第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータが検索され、検索されたデータが第２のノード２ａから第１のノード２に移動される。これにより、第１のノード２および第２のノード２ａの間で、移動するデータ量を低減できる。
【００２３】
例えば、第１のノード２の担当範囲を拡大する際、第１のノード２の全データを第２のノード２ａに移動して、第１のノード２の担当範囲を削除し、その後、第１のノード２に拡大後の担当範囲を追加する方法も考えられる。しかし、この方法では、元々第１のノード２に存在していたデータを第２のノード２ａに移動し、担当範囲の再設定後に当該データを第２のノード２ａから第１のノード２に移動する処理が生ずる。このため、元々第１のノード２に存在していたデータの無駄な移動が生じ、移動するデータ量が大きい。
【００２４】
一方、情報処理装置１によれば、担当範囲の拡大によって、第１のノード２が新たに担当するハッシュ値範囲のデータを検索して、該データを第２のノード２ａから第１のノード２に移動させる。このため、第１のノード２の担当範囲の削除／追加を行う場合に比べて、データの無駄な移動が生じない。例えば、元々第１のノード２に存在していたデータの移動が行われない。よって、移動するデータ量を低減でき、担当範囲を拡大する処理を効率的に実行できる。
【００２５】
［第２の実施の形態］
図２は、第２の実施の形態の分散ストレージシステムを示す図である。第２の実施の形態の分散ストレージシステムは、ＫＶＳの手法によりデータを複数のストレージノードに分散配置する。第２の実施の形態の分散ストレージシステムは、ストレージ制御装置１００、ストレージノード２００，２００ａ，２００ｂ、ディスク装置３００，３００ａ，３００ｂおよびクライアント４００を含む。
【００２６】
ネットワーク１０には、ストレージ制御装置１００、ストレージノード２００，２００ａ，２００ｂおよびクライアント４００が接続されている。ネットワーク１０はＬＡＮ（Local Area Network）でもよい。ネットワーク１０はインターネットなどの広域ネットワークでもよい。
【００２７】
ストレージ制御装置１００は、ストレージノード２００，２００ａ，２００ｂのハッシュ値の担当範囲の変更を制御するサーバコンピュータである。
ストレージノード２００には、ディスク装置３００が接続されている。ストレージノード２００ａには、ディスク装置３００ａが接続されている。ストレージノード２００ｂには、ディスク装置３００ｂが接続されている。ストレージノード２００，２００ａ，２００ｂとディスク装置３００，３００ａ，３００ｂとの間のインタフェースには、例えばＳＣＳＩ（Small Computer System Interface）やファイバチャネル（Fibre Channel）などを用いてもよい。ストレージノード２００，２００ａ，２００ｂは、それぞれディスク装置３００，３００ａ，３００ｂからのデータの読出し（Ｒｅａｄ）、および、ディスク装置３００，３００ａ，３００ｂへのデータの書込み（Ｗｒｉｔｅ）を実行するサーバコンピュータである。
【００２８】
ディスク装置３００，３００ａ，３００ｂは、データを記憶する記憶装置である。ディスク装置３００，３００ａ，３００ｂは、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）などの記憶デバイスを備える。ディスク装置３００，３００ａ，３００ｂは、ストレージノード２００，２００ａ，２００ｂに内蔵されてもよい。
【００２９】
クライアント４００は、分散ストレージシステムに格納されたデータにアクセスするクライアントコンピュータである。例えば、クライアント４００は、ユーザが操作する端末装置である。クライアント４００は、ストレージノード２００，２００ａ，２００ｂの何れかにデータの読出しを要求する（Ｒｅａｄ要求）。クライアント４００は、ストレージノード２００，２００ａ，２００ｂの何れかに、データの書込みを要求する（Ｗｒｉｔｅ要求）。
【００３０】
ここで、ディスク装置３００，３００ａ，３００ｂは、キー（ｋｅｙ）とデータ（ｖａｌｕｅ）のペア（ｋｅｙ，ｖａｌｕｅ）を記憶する。ストレージノード２００，２００ａ，２００ｂは、キーを指定したデータのＲｅａｄ要求があると、当該キーに対応するデータを読み出す。ストレージノード２００，２００ａ，２００ｂは、キーを指定したデータのＷｒｉｔｅ要求があると、当該キーに対応するデータを更新する。このとき、ストレージノード２００，２００ａ，２００ｂは、キーから算出されるハッシュ値に基づいて、アクセス対象のデータが何れのストレージノードの担当下にあるか判断する。
【００３１】
キーに対するハッシュ値は、例えば、ＭＤ５（Message Digest algorithm 5）を用いて算出できる。ＳＨＡ（Secure Hash Algorithm）など他のハッシュ関数を用いてもよい。
図３は、ストレージ制御装置のハードウェア例を示す図である。ストレージ制御装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、ディスクドライブ１０６および通信部１０７を有する。各ユニットがストレージ制御装置１００のバスに接続されている。ストレージノード２００，２００ａ，２００ｂおよびクライアント４００もストレージ制御装置１００と同様のハードウェアを用いて実装できる。
【００３２】
ＣＰＵ１０１は、ストレージ制御装置１００の情報処理を制御するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されているプログラムやデータの少なくとも一部を読み出し、ＲＡＭ１０２に展開してプログラムを実行する。なお、ストレージ制御装置１００は、複数のプロセッサを設けて、プログラムを分散して実行してもよい。
【００３３】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムや処理に用いるデータを一時的に記憶する揮発性メモリである。なお、ストレージ制御装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えていてもよい。
【００３４】
ＨＤＤ１０３は、ＯＳ（Operating System）プログラムやアプリケーションプログラムなどのプログラムおよびデータを記憶する不揮発性の記憶装置である。ＨＤＤ１０３は、ＣＰＵ１０１の命令に従って、内蔵の磁気ディスクに対してデータの読み書きを行う。なお、ストレージ制御装置１００は、ＨＤＤ以外の種類の不揮発性の記憶装置（例えば、ＳＳＤなど）を備えてもよく、複数の記憶装置を備えていてもよい。
【００３５】
画像信号処理部１０４は、ＣＰＵ１０１の命令に従って、ストレージ制御装置１００に接続されたディスプレイ１１に画像を出力する。ディスプレイ１１としては、例えば、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイを用いることができる。
【００３６】
入力信号処理部１０５は、ストレージ制御装置１００に接続された入力デバイス１２から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス１２としては、例えば、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００３７】
ディスクドライブ１０６は、記録媒体１３に記録されたプログラムやデータを読み取る駆動装置である。記録媒体１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。ディスクドライブ１０６は、例えば、ＣＰＵ１０１の命令に従って、記録媒体１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３８】
通信部１０７は、ネットワーク１０を介してストレージノード２００，２００ａ，２００ｂおよびクライアント４００と通信を行う通信インタフェースである。通信部１０７は、有線通信インタフェースでもよいし、無線通信インタフェースでもよい。
【００３９】
図４は、第２の実施の形態のソフトウェア例を示すブロック図である。図４に示すユニットの一部または全部は、ストレージ制御装置１００、ストレージノード２００およびクライアント４００が実行するプログラムのモジュールであってもよい。また、図４に示すユニットの一部または全部は、ＦＰＧＡ（Field Programmable Gate Array）やＡＳＩＣ（Application Specific Integrated Circuit）などの電子回路であってもよい。ストレージノード２００ａ，２００ｂもストレージノード２００と同様のユニットを用いて実装できる。
【００４０】
ストレージ制御装置１００は、記憶部１１０、ネットワークＩ／Ｏ（Input / Output）部１２０および担当範囲制御部１３０を有する。
記憶部１１０は、担当管理テーブルおよびノード利用管理テーブルを記憶する。担当管理テーブルは、ストレージノード２００，２００ａ，２００ｂが担当するハッシュ値の範囲を定義したデータである。ノード利用管理テーブルは、ストレージノード２００，２００ａ，２００ｂの利用状況を記録したデータである。記憶部１１０は、ＲＡＭ１０２に確保された記憶領域でもよいし、ＨＤＤ１０３に確保された記憶領域であってもよい。
【００４１】
ネットワークＩ／Ｏ部１２０は、ストレージノード２００，２００ａ，２００ｂから受信したデータを、担当範囲制御部１３０に出力する。ネットワークＩ／Ｏ部１２０は、担当範囲制御部１３０から取得したデータを、ストレージノード２００，２００ａ，２００ｂに送信する。
【００４２】
担当範囲制御部１３０は、ストレージノード２００，２００ａ，２００ｂのハッシュ値の担当範囲の変更を制御する。担当範囲制御部１３０は、ストレージノード２００，２００ａ，２００ｂの利用状況に応じて、または、システム管理者の操作入力に応じて、担当範囲の割り当てを変更する。担当範囲制御部１３０は、担当範囲の変更に伴い、ストレージノード間で移動させるデータを検索する。担当範囲制御部１３０は、移動させるデータが存在する場合、対象のストレージノード間で当該データを移動する。担当範囲制御部１３０は、担当範囲の変更に伴い、記憶部１１０に記憶された担当管理テーブルを更新する。担当範囲制御部１３０は、担当管理テーブルの更新内容を示す更新データをネットワークＩ／Ｏ部１２０に出力する。
【００４３】
ストレージノード２００は、記憶部２１０、ネットワークＩ／Ｏ部２２０、ディスクＩ／Ｏ部２３０、ノード一覧管理部２４０、担当ノード判定部２５０および監視部２６０を有する。
【００４４】
記憶部２１０は、担当管理テーブルを記憶する。当該担当管理テーブルは、記憶部１１０に格納される担当管理テーブルと同じ内容である。記憶部２１０は、ストレージノード２００上のＲＡＭに確保された記憶領域でもよいし、ストレージノード２００上のＨＤＤに確保された記憶領域であってもよい。
【００４５】
ネットワークＩ／Ｏ部２２０は、ストレージ制御装置１００、ストレージノード２００ａ，２００ｂおよびクライアント４００から受信したデータを、ディスクＩ／Ｏ部２３０および担当ノード判定部２５０に出力する。ネットワークＩ／Ｏ部２２０は、ディスクＩ／Ｏ部２３０、担当ノード判定部２５０および監視部２６０から取得したデータを、ストレージ制御装置１００、ストレージノード２００ａ，２００ｂおよびクライアント４００に送信する。
【００４６】
ディスクＩ／Ｏ部２３０は、担当ノード判定部２５０の指示により、ディスク装置３００からデータの読出しを行う。また、ディスクＩ／Ｏ部２３０は、担当ノード判定部２５０の指示により、ディスク装置３００にデータの書込みを行う。
【００４７】
ノード一覧管理部２４０は、ネットワークＩ／Ｏ部２２０がストレージ制御装置１００から受信した更新データに基づいて、記憶部２１０に記憶された担当管理テーブルを更新する。ノード一覧管理部２４０は、担当ノード判定部２５０からの要求により、担当管理テーブルの内容を担当ノード判定部２５０に応答する。
【００４８】
担当ノード判定部２５０は、ネットワークＩ／Ｏ部２２０がクライアント４００から受信したＲｅａｄ要求に基づき、担当ノードを判定する。Ｒｅａｄ要求には、読出し対象のデータに対応するキーが含まれる。担当ノードとは、当該キーから算出されるハッシュ値を担当しているストレージノードである。担当ノード判定部２５０は、算出したハッシュ値とノード一覧管理部２４０から取得する担当管理テーブルとに基づいて、担当ノードを判定できる。担当ノード判定部２５０は、自ノードが担当ノードであれば、ディスクＩ／Ｏ部２３０に読出しを指示する。担当ノード判定部２５０は、自ノード以外のノードが担当ノードであれば、ネットワークＩ／Ｏ部２２０を介して、当該担当ノードにＲｅａｄ要求を転送する。
【００４９】
監視部２６０は、ストレージノード２００の利用状況を監視する。監視部２６０は、監視結果を含む監視データを、ネットワークＩ／Ｏ部２２０を介して、ストレージ制御装置１００に定期的に送信する。利用状況には、例えば、ディスク装置３００が記憶しているデータ量、ディスク装置３００の空き容量およびディスク装置３００へのアクセス数などが含まれる。
【００５０】
クライアント４００は、ネットワークＩ／Ｏ部４１０およびアクセス部４２０を有する。
ネットワークＩ／Ｏ部４１０は、アクセス部４２０からデータのＲｅａｄ要求やＷｒｉｔｅ要求を取得し、ストレージノード２００，２００ａ，２００ｂの何れかに送信する。ネットワークＩ／Ｏ部４１０は、ストレージノード２００，２００ａ，２００ｂからデータを受信すると、アクセス部４２０に出力する。
【００５１】
アクセス部４２０は、読出し対象のデータのキーを含むＲｅａｄ要求を生成して、ネットワークＩ／Ｏ部４１０に出力する。アクセス部４２０は、更新対象のデータのキーを含むＷｒｉｔｅ要求を生成して、ネットワークＩ／Ｏ部４１０に出力する。
【００５２】
なお、第２の実施の形態のストレージ制御装置１００は、第１の実施の形態の情報処理装置１の一例である。担当範囲制御部１３０は、制御部１ｂの一例である。
図５は、ハッシュ値の担当範囲の割当例を示す図である。第２の実施の形態の分散ストレージシステムでは、利用可能なハッシュ値の範囲は“０〜９９”である。ただし、“９９”の次の値は“０”である。そのうちの複数の範囲がストレージノード２００，２００ａ，２００ｂに割り当てられている。ここで、ラベル“Ａ”は、ストレージノード２００の識別情報である。ラベル“Ｂ”は、ストレージノード２００ａの識別情報である。ラベル“Ｃ”は、ストレージノード２００ｂの識別情報である。各ラベルの位置は、各担当範囲の開始位置である。
【００５３】
図５では、各ラベル位置に対応する値を含むハッシュ値範囲Ｒ１，Ｒ２，Ｒ３が示されている。ハッシュ値範囲Ｒ１は“１０〜３９”であり、ストレージノード２００の担当範囲である。ハッシュ値範囲Ｒ２は“４０〜８９”であり、ストレージノード２００ａの担当範囲である。ハッシュ値範囲Ｒ３は“９０〜９９”、“０〜９”であり、ストレージノード２００ｂの担当範囲である。ハッシュ値範囲Ｒ３は、“９９”および“０”を跨いだ領域である。
【００５４】
第２の実施の形態の分散ストレージシステムでは、担当範囲の一端の値を、ストレージノード２００，２００ａ，２００ｂに対して指定することで、ストレージノード２００，２００ａ，２００ｂの担当範囲を割り当てる。例えば、担当範囲の両端の値のうち小さい方（開始位置）を指定する場合、ストレージノード２００にハッシュ値“１０”を、ストレージノード２００ａにハッシュ値“４０”を指定する。これにより、ストレージノード２００の担当範囲が“１０〜３９”となる。ハッシュ値範囲Ｒ３のように、当該範囲が“０”を跨ぐ場合には、例外として、両端の値のうち大きい方が開始位置となる。この場合、例えば、ハッシュ値“９０”を指定することで、“０”を跨いだ範囲を指定できる。
【００５５】
なお、担当範囲の両端の値のうち大きい方（終了位置）を指定して、担当範囲を割り当ててもよい。例えば、ストレージノード２００にハッシュ値“３９”を、ストレージノード２００ａにハッシュ値“８９”を、ストレージノード２００ｂにハッシュ値“９”を指定する。すると、図５で示したハッシュ値範囲Ｒ１，Ｒ２，Ｒ３と同等の担当範囲を、ストレージノード２００，２００ａ，２００ｂに割り当てることができる。この場合も、“０”を跨ぐ範囲については、例外として、両端の値のうち小さい方が終了位置となる。よって、両端の値のうち小さい方を指定することで、“０”を跨いだ範囲を指定できる。
【００５６】
以下の説明では、ストレージノード２００，２００ａ，２００ｂに、担当範囲の開始位置を指定することで、当該担当範囲を割り当てるものとする。ここで、ストレージノード２００，２００ａ，２００ｂには、担当範囲を更に分割したブロック単位で担当範囲が割り当てられる。また、ストレージノード２００，２００ａ，２００ｂの利用状況もブロック単位で管理される。
【００５７】
図６は、担当管理テーブルの例を示す図である。担当管理テーブル１１１は、記憶部１１０に記憶される。また、担当管理テーブル１１１と同様の担当管理テーブルが、記憶部２１０およびストレージノード２００ａ，２００ｂにも格納される。担当管理テーブル１１１は、ブロック開始位置およびノードの項目を含む。
【００５８】
ブロック開始位置の項目には、ブロックの開始位置に対応するハッシュ値が登録される。ノードの項目には、ストレージノード２００，２００ａ，２００ｂのラベルが登録される。例えば、ブロック開始位置が“０”、“１０”のレコードが存在する。この場合、前者のレコードは、ハッシュ値範囲“０〜９”のブロックが、ストレージノード２００ｂ（ラベル“Ｃ”）に割り当てられていることを示す。
【００５９】
図７は、ノード利用管理テーブルの例を示す図である。ノード利用管理テーブル１１２は、記憶部１１０に記憶される。ノード利用管理テーブル１１２は、ブロック開始位置、データ量、空き容量、アクセス数および総転送量の項目を含む。
【００６０】
ブロック開始位置の項目には、ブロックの開始位置に対応するハッシュ値が登録される。データ量の項目には、当該ブロックに記憶済のデータ量（例えば、ＧＢ（Giga Byte）単位）が登録される。空き容量の項目には、当該ブロックの空き容量（例えば、ＧＢ単位）が登録される。アクセス数の項目には、当該ブロックに対する読出し／書込みの総アクセス数が登録される。総転送量の項目には、当該ブロックに対する読出し／書込みに伴うデータの転送量（例えば、ＧＢ単位）の総和が登録される。
【００６１】
図８は、担当範囲を拡大する処理例を示すフローチャートである。以下、図８に示す処理をステップ番号に沿って説明する。
（ステップＳ１１）担当範囲制御部１３０は、ハッシュ値の担当範囲を拡大するストレージノードを決定する。例えば、担当範囲制御部１３０は、記憶部１１０に記憶されたノード利用管理テーブル１１２に基づいて、何れのストレージノードを対象とするか決定する。例えば、最もデータ量の小さいノードを選ぶ、最もデータ量の大きいノードの担当範囲に隣接する範囲を担当するノードを選ぶ、などの方法により対象を決定することが考えられる。あるいは、システム管理者の操作入力により指定されたノードを、担当範囲の拡大対象としてもよい。ここでは、ストレージノード２００ｂを担当範囲の拡大対象に決定したとする。
【００６２】
（ステップＳ１２）担当範囲制御部１３０は、ノード利用管理テーブル１１２を参照して、ハッシュ値範囲Ｒ３の両端のうち拡大する側（開始位置側か終了位置側か）を決定する。例えば、データ量のより大きいストレージノードの担当範囲と隣接する側とする、予め定められた側（開始位置側）とする、などが考えられる。あるいは、システム管理者の操作入力により指定された側を拡大対象に決定してもよい。ここでは、ハッシュ値範囲Ｒ３の開始位置側を拡大する側に決定したとする。この場合、ハッシュ値範囲Ｒ３の開始位置（ハッシュ値範囲Ｒ２，Ｒ３の境界）をストレージノード２００ａが担当するハッシュ値範囲Ｒ２側へシフトして、ハッシュ値範囲Ｒ３を拡大することになる。
【００６３】
（ステップＳ１３）担当範囲制御部１３０は、記憶部１１０に記憶された担当管理テーブル１１１およびノード利用管理テーブル１１２に基づき、ハッシュ値範囲Ｒ３の開始位置のシフト量を決定する。例えば、ストレージノード２００ａ，２００ｂのデータ量が均等になる（あるいは、均等に近くなる）ブロック開始位置“７０”をハッシュ値範囲Ｒ３の新たな開始位置とする（シフト量は“２０”）。この場合、当該新たな開始位置“７０”と元の開始位置“９０”との間の範囲“７０〜８９”がストレージノード２００ａからストレージノード２００ｂに移設する範囲である。また、例えば、担当するハッシュ値範囲に含まれるハッシュ値の個数に基づいて、シフト量を決定してもよい。例えば、移動後に各ノードが担当するハッシュ値範囲に含まれるハッシュ値の個数が均一になるようにシフト量を決定することが考えられる。
【００６４】
（ステップＳ１４）担当範囲制御部１３０は、担当管理テーブル１１１を更新する。具体的には、ブロック開始位置“７０”、“８０”の設定（ラベル“Ｂ”）をストレージノード２００ｂのラベル“Ｃ”に変更する。担当範囲制御部１３０は、当該変更内容を示す更新データをネットワークＩ／Ｏ部１２０に出力する。ネットワークＩ／Ｏ部１２０は、更新データをストレージノード２００，２００ａ，２００ｂに送信する。ストレージノード２００，２００ａ，２００ｂは、更新データを受信すると、自ノードの担当管理テーブルを更新する。
【００６５】
（ステップＳ１５）担当範囲制御部１３０は、ステップＳ１３で決定した範囲“７０〜８９”に属する差分のデータを検索し、ストレージノード２００ａからストレージノード２００ｂに移動する。例えば、担当範囲制御部１３０は、ストレージノード２００ａに当該範囲にハッシュ値が属するデータを問い合わせて、ストレージノード２００ａからストレージノード２００ｂに当該データを移動する。また、例えば、担当範囲制御部１３０は、ディスク装置３００ａにおける当該範囲に対応するアドレス（ディレクトリ名やセクタ番号など）をブロックに対応付けて管理してもよい。例えば、担当管理テーブル１１１の各ブロック開始位置に対応付けて、当該アドレスを登録することが考えられる。このようにすれば、担当範囲制御部１３０は、移動対象のデータの格納位置を当該アドレスに基づいて検索できる。担当範囲制御部１３０は、移動対象範囲をストレージノード２００ａに通知して、ストレージノード２００ａにより該移動対象範囲のデータをストレージノード２００ｂへ移動させてもよい。
【００６６】
このように、担当範囲制御部１３０は、ストレージノード２００ｂに対してストレージノード２００ａとの境界側を、担当範囲を拡大させる側と決定する。担当範囲制御部１３０は、ハッシュ値範囲Ｒ３の開始位置（ハッシュ値範囲Ｒ２，Ｒ３の境界値）をハッシュ値範囲Ｒ２側にシフトさせる。シフト量は、ストレージノード２００ａ，２００ｂの利用状況により決定する。そして、シフト分のハッシュ値範囲に属するデータを、ストレージノード２００ａからストレージノード２００ｂに移動する。
【００６７】
なお、ステップＳ１１〜Ｓ１３では、上述した方法以外の方法で、担当を拡大するストレージノードおよび担当範囲の開始位置のシフト量を決定してもよい。例えば、次の（１）、（２）の何れかの方法を用いることも考えられる。
【００６８】
（１）空き容量が少ないノードを担当範囲の拡大対象として、空き容量の多いノードからハッシュ値範囲の一部を移設するように決定する。そして、両ノードの空き容量が均等になるように開始位置のシフト量を決定する。各ノードの空き容量は、ノード利用管理テーブル１１２で照会できる（例えば、ノードごとにブロックの空き容量の和をとれば、ノードごとの空き容量の総和が得られる）。これにより、当該空き容量が少ないノードの空き容量の増加を図れる。
【００６９】
（２）負荷の小さい（アクセス数や総転送量など）ノードを担当範囲の拡大対象として、負荷の大きいノードからハッシュ値範囲の一部を移設するように決定する。そして、両ノードの負荷が均等になるように開始位置のシフト量を決定する。各ノードの負荷は、ノード利用管理テーブル１１２で照会できる（例えば、ノードごとにブロックのアクセス数の和をとれば、ノードごとのアクセス数の総和が得られる）。これにより、各ノードの負荷分散を図れる。
【００７０】
更に、例示した複数の方法を組み合わせてシフト量を決定してもよい。例えば、データ量を均等にするシフト量を決定した後、両ノードのアクセス数の差がより小さくなるようにシフト量を調整することも考えられる。例えば、まず、ハッシュ値範囲Ｒ３の開始位置を開始位置“７０”に仮決定する（シフト量“２０”に仮決定）。そして、ストレージノード２００ａ，２００ｂのアクセス数の差が小さくなるように、開始位置を“６０”に決定する（シフト量“３０”に決定）。
【００７１】
なお、上記（２）では、負荷として、各ストレージノードのＣＰＵ使用率などの他の指標を用いてもよい。その場合、例えば、ストレージ制御装置１００は、各ストレージノードからＣＰＵ使用率などの指標を収集する。
【００７２】
また、担当範囲制御部１３０は、ブロック単位でデータの移動を行う。このため、ブロックを移設する順序を、任意に決定できる。例えば、対象ブロックごとの利用状況に基づいて順序を決定することが考えられる。より具体的には、現在アクセス中のデータを多く含むブロック程、後回しにすることが考えられる。また、例えば、システム管理者の操作入力により指定された順序とすることが考えられる。
【００７３】
また、上記ステップＳ１４，Ｓ１５を逆の順序で行ってもよい。
図９は、移設するハッシュ値範囲の例を示す図である。図９では、図５に示したハッシュ値範囲Ｒ３をハッシュ値範囲Ｒ２側へシフト量“２０”だけ拡大した場合を例示している。ハッシュ値範囲Ｒ２ａは、ストレージノード２００ａの変更後の担当範囲である。ハッシュ値範囲Ｒ２ａでは、ハッシュ値範囲Ｒ３の拡大に伴って、終了位置が“６９”にシフトしている。
【００７４】
ハッシュ値範囲Ｒ３ａは、ストレージノード２００ｂの変更後の担当範囲である。ハッシュ値範囲Ｒ３ａでは、開始位置が“９０”から“７０”にシフトしている。
ハッシュ値範囲Ｒ２ｂは、ハッシュ値範囲Ｒ２，Ｒ３ａの重なり合う領域であり、“７０〜８９”の範囲である。ハッシュ値範囲Ｒ２ｂは、ストレージノード２００ａからストレージノード２００ｂに移設する範囲である。ハッシュ値範囲Ｒ２ｂに属するデータが、ストレージノード２００ａからストレージノード２００ｂへの移動対象データである。
【００７５】
このように、ストレージ制御装置１００は、ハッシュ値範囲Ｒ３の開始位置（ハッシュ値範囲Ｒ２，Ｒ３の境界）をシフトさせることで、ハッシュ値範囲Ｒ３をハッシュ値範囲Ｒ３ａへ拡大する。そして、ハッシュ値範囲Ｒ２ｂに属するデータをストレージノード２００ａからストレージノード２００ｂへ移動する。
【００７６】
ここで、例えば、ハッシュ値範囲Ｒ３を拡大する際、ハッシュ値範囲Ｒ３を削除して、ハッシュ値範囲Ｒ３のデータをストレージノード２００ａに移動してから、ストレージノード２００ｂにハッシュ値範囲Ｒ３ａを割り当てる方法も考えられる。この場合、ハッシュ値範囲Ｒ３に属する全データをストレージノード２００ａに移動する（ハッシュ値範囲Ｒ３に属していたデータはハッシュ値範囲Ｒ２に属することとなる）。そして、ハッシュ値範囲Ｒ３ａの割当後、ハッシュ値範囲Ｒ３ａに属するデータを、ストレージノード２００ａからストレージノード２００ｂに移動する。しかし、この方法では、元々ストレージノード２００ｂに存在していたデータ（ハッシュ値範囲Ｒ３に属していたデータ）の無駄な移動が生じ、移動するデータ量が大きい。
【００７７】
一方、ストレージ制御装置１００によれば、ハッシュ値範囲Ｒ３の削除を伴わないので、ハッシュ値範囲Ｒ３に属するデータのストレージノード２００ａへの移動が生じない。データの移動は、差分のデータ、すなわち、ハッシュ値範囲Ｒ２ｂに属するデータの移動で済む。よって、移動するデータ量を低減できる。ストレージノード２００の担当範囲を拡大する処理を効率的に実行できる。
【００７８】
なお、ストレージ制御装置１００をストレージノード２００，２００ａ，２００ｂとは別個に設ける場合を例示したが、担当範囲制御部１３０の機能をストレージノード２００，２００ａ，２００ｂの何れかまたは全部に設けてもよい。何れかのストレージノードに担当範囲制御部１３０の機能を設ける場合、当該ストレージノードが他のストレージノードの情報を収集して、一元管理する。全部のストレージノードに担当範囲制御部１３０の機能を設ける場合、全部のストレージノードの情報を各ストレージノードで共有し、それぞれのストレージノードが、所定のタイミングで担当範囲制御部１３０の機能を発揮すればよい。所定のタイミングとしては、例えば、ストレージノードが自身の空き容量が閾値よりも小さくなったことを検知したタイミングが考えられる。この場合、当該ストレージノードは、自身の空き容量を増やすように担当範囲の拡大を行う。あるいは、所定のタイミングとしては、例えば、ストレージノードが自身の負荷（例えば、アクセス数）が閾値を上回ったことを検知したタイミングが考えられる。この場合、当該ストレージノードは、負荷が分散されるように担当範囲の拡大を行う。
【００７９】
ここで、あるストレージノードの担当範囲の変更に伴うデータ移動の最中に、移設対象の範囲に属するデータへのクライアント４００からのアクセスが発生することもある。このとき、ストレージノード２００，２００ａ，２００ｂの担当管理テーブルには、変更後の担当範囲がデータ移動よりも先に登録されるので、アクセス先のノードに対象のキーに対応するデータが存在しないことがある。その場合にも、ストレージノード２００，２００ａ，２００ｂは当該アクセスに適切に対処できることが望ましい。そこで、以下では、データ移動の最中にクライアント４００からデータへのアクセスがあった場合の処理を説明する。まず、データのＲｅａｄ要求を受信した場合の処理例を説明する。
【００８０】
図１０は、Ｒｅａｄ要求受信時の処理例を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。
（ステップＳ２１）ネットワークＩ／Ｏ部２２０は、クライアント４００からＲｅａｄ要求を受信する。ネットワークＩ／Ｏ部２２０は、担当ノード判定部２５０にＲｅａｄ要求を出力する。
【００８１】
（ステップＳ２２）担当ノード判定部２５０は、Ｒｅａｄ要求が自ノードへのアクセスか否かを判断する。自ノードへのアクセスである場合、処理をステップＳ２４に進める。自ノード以外のノードへのアクセスである場合、処理をステップＳ２３に進める。自ノードの担当範囲は、記憶部２１０に記憶された担当管理テーブルにより特定できる。自ノードへのアクセスか否かは、Ｒｅａｄ要求に含まれるキーから算出されるハッシュ値が、自ノードの担当範囲に属するか否かにより判断できる。ハッシュ値が自ノードの担当範囲に属する場合、自ノードへのアクセスである。ハッシュ値が自ノードの担当範囲に属さない場合、自ノード以外のノードへのアクセスである。
【００８２】
（ステップＳ２３）担当ノード判定部２５０は、アクセス対象のハッシュ値が属する範囲を担当する担当ノードを、担当管理テーブルを参照して特定する。担当ノード判定部２５０は、特定した担当ノードにＲｅａｄ要求を転送する。そして、処理を終了する。
【００８３】
（ステップＳ２４）担当ノード判定部２５０は、キーに対応するＲｅａｄ対象のデータが移動済であるか否かを判断する。移動済でない場合、処理をステップＳ２５に進める。移動済である場合、処理をステップＳ２６に進める。ここで、移動済でない場合とは、例えば、ストレージノード２００の担当範囲を拡大済であるが、拡大した範囲に属する当該データのストレージノード２００への移動が未完了である場合である。この場合、Ｒｅａｄ対象のデータは、当該データの移動元のストレージノードに存在している。
【００８４】
（ステップＳ２５）担当ノード判定部２５０は、当該データの移動元のストレージノード（移動元ノード）を、クライアント４００に応答する。移動元ノードとは、担当範囲の拡大に伴って、ストレージノード２００が現在通信している相手ノードである。クライアント４００は、当該移動元ノードに、再度Ｒｅａｄ要求を送信する。そして、処理を終了する。
【００８５】
（ステップＳ２６）担当ノード判定部２５０は、キーに対応するデータの読出しをディスクＩ／Ｏ部２３０に指示する。ディスクＩ／Ｏ部２３０は、ディスク装置３００から当該データの読出しを行う。
【００８６】
（ステップＳ２７）ディスクＩ／Ｏ部２３０は、読出したデータをネットワークＩ／Ｏ部２２０に出力する。ネットワークＩ／Ｏ部２２０は、ディスクＩ／Ｏ部２３０から取得した当該データを、クライアント４００に送信する。
【００８７】
このように、ストレージノード２００，２００ａ，２００ｂは、Ｒｅａｄ要求があったときに、Ｒｅａｄ対象のデータが未移動である場合、移動元ノードを応答する。クライアント４００は、当該応答に基づいて、移動元ノードに再度Ｒｅａｄ要求を送信し、当該データに適切にアクセスできる。
【００８８】
なお、ステップＳ２３において、Ｒｅａｄ要求を受信した担当ノードも、上記ステップＳ２１〜Ｓ２７の処理を行うことで、Ｒｅａｄ要求を適切に処理できる。
また、ステップＳ２５において、Ｒｅａｄ要求を受信した移動元ノードも、上記ステップＳ２１〜Ｓ２７の処理を行うことで、Ｒｅａｄ要求を適切に処理できる。
【００８９】
更に、ステップＳ２５では、移動対象のデータに対するＲｅａｄ要求につき、移動元ノードを応答して、クライアント４００にリトライさせる例を示した。一方、アクセスを受け付けたノードと移動元ノードとの間でＲｅａｄ要求を送受信して、Ｒｅａｄ対象のデータをクライアント４００に応答してもよい。例えば、クライアント４００からＲｅａｄ要求を受信したノードが、移動元ノードにＲｅａｄ要求を転送する。移動元ノードは、当該Ｒｅａｄ要求に応じたデータをクライアント４００に応答する。
【００９０】
次に、データのＷｒｉｔｅ要求を受信した場合の処理例を説明する。
図１１は、Ｗｒｉｔｅ要求受信時の処理例を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。
【００９１】
（ステップＳ３１）ネットワークＩ／Ｏ部２２０は、クライアント４００からＷｒｉｔｅ要求を受信する。ネットワークＩ／Ｏ部２２０は、担当ノード判定部２５０にＷｒｉｔｅ要求を出力する。
【００９２】
（ステップＳ３２）担当ノード判定部２５０は、Ｗｒｉｔｅ要求が自ノードへのアクセスか否かを判断する。自ノードへのアクセスである場合、処理をステップＳ３４に進める。自ノード以外のノードへのアクセスである場合、処理をステップＳ３３に進める。
【００９３】
（ステップＳ３３）担当ノード判定部２５０は、アクセス対象のハッシュ値が属する範囲を担当する担当ノードを、記憶部２１０に記憶された担当管理テーブルを参照して特定する。担当ノード判定部２５０は、特定した担当ノードにＷｒｉｔｅ要求を転送する。そして、処理を終了する。
【００９４】
（ステップＳ３４）担当ノード判定部２５０は、キーに対応するデータの書込み（更新）をディスクＩ／Ｏ部２３０に指示する。ディスクＩ／Ｏ部２３０は、ディスク装置３００に当該データの書込みを行う。ディスクＩ／Ｏ部２３０は、ネットワークＩ／Ｏ部２２０を介して、クライアント４００に書込み完了を応答する。
【００９５】
（ステップＳ３５）担当ノード判定部２５０は、ステップＳ３４で書込みを行ったデータがストレージノード２００の担当範囲の拡大に伴うデータ移動の対象であるか否かを判断する。移動対象である場合、処理をステップＳ３６に進める。移動対象でない場合、処理を終了する。例えば、担当ノード判定部２５０は、次の（１）〜（３）の条件が全て満たされるときに、当該データが移動対象であると判断できる。（１）自ノードが、担当範囲の拡大に伴い移動元ノードからデータを移動中である。（２）アクセス対象のキーから算出されるハッシュ値が拡大後の担当範囲に属する。（３）当該キーに対応するデータを移動元ノードから未だ移動していない。
【００９６】
（ステップＳ３６）担当ノード判定部２５０は、ステップＳ３４で書込みを行ったデータを移動元ノードからの移動対象から除外する。例えば、担当ノード判定部２５０は、当該データに対応するキーのデータを、移動せずに削除するよう移動元ノードに依頼する。また、例えば、担当ノード判定部２５０は、当該キーのデータを移動元ノードから受信したとき、当該データを破棄する。
【００９７】
このように、ストレージノード２００，２００ａ，２００ｂは、Ｗｒｉｔｅ要求があったときに、データの書込みを行い、移動元ノードから受信するデータによって、書き込んだデータが更新されないようにする。これにより、新しいデータが古いデータで上書きされるのを防止できる。
【００９８】
なお、ステップＳ３３において、Ｗｒｉｔｅ要求を受信した担当ノードも、上記ステップＳ３１〜Ｓ３６の処理を行うことで、Ｗｒｉｔｅ要求を適切に処理できる。
また、ステップＳ３４では、更新対象のデータが未移動であれば、移動元ノードにＷｒｉｔｅ要求を転送して、移動元ノードにデータの更新を実行させてもよい。更に、ステップＳ３４では、更新対象のデータが未移動であれば、当該データの移動を先に行ってから、当該データの更新を行ってもよい。
【００９９】
更に、上述の例では、担当範囲を拡大したとき、ストレージノード２００，２００ａ，２００ｂが保持する担当範囲テーブルを更新した後に、データの移動を行うものとしたが、これらの手順を逆の順序で行ってもよい。具体的には、担当範囲制御部１３０は、担当範囲を拡大する場合、データの移動を行ったあとに、ストレージノード２００，２００ａ，２００ｂが保持する担当範囲テーブルを更新するようにしてもよい。
【０１００】
この場合、移設中の範囲に属するデータに対してクライアント４００からアクセスがあると、移動先のストレージノードに当該データが移動済で、アクセスを受けたストレージノードに当該データが存在しないことがある。その場合には、アクセスを受けたストレージノードが、移動先のストレージノードをクライアント４００に応答すればよい。そうすれば、クライアント４００は、移動先のストレージノードに対し、改めて当該データへアクセスできる。
【符号の説明】
【０１０１】
１ 情報処理装置
１ａ 記憶部
１ｂ 制御部
２ 第１のノード
２ａ 第２のノード
【技術分野】
【０００１】
本発明はストレージ制御方法、情報処理装置およびプログラムに関する。
【背景技術】
【０００２】
現在、分散ストレージシステムが利用されている。分散ストレージシステムは、ネットワークで接続された複数のストレージノードを備える。複数のストレージノードにデータを分散配置することで、データアクセスの高速化を図れる。
【０００３】
分散ストレージシステムでは、ストレージノードに配置するデータの管理が行われる。例えば、サーバ装置がストレージ記憶装置の負荷を監視し、当該負荷に応じて、顧客データを別筐体のストレージ装置に再配置して、アクセスを分散する提案がある。また、例えば、ホスト計算機が、複数のストレージサブシステム上の物理ディスクを束ねた仮想ディスクを管理し、当該仮想ディスクへの入出力要求を制御する提案もある。
【０００４】
ところで、ＫＶＳ（Key - Value Store）と呼ばれる手法を用いた分散ストレージシステムがある。ＫＶＳでは、何れかのストレージノードに、データ（ｖａｌｕｅ）にキー（ｋｅｙ）を付与した（ｋｅｙ，ｖａｌｕｅ）のペアを保存する。保存したデータを取得する際は、キーを指定して、対応するデータを取得する。キーに応じて異なるストレージノードにデータを格納することで、データを分散配置する。
【０００５】
ＫＶＳでは、キーから算出されるハッシュ値に応じて、データ格納先のストレージノードを判定することがある。各ストレージノードには、それぞれが担当するハッシュ値の範囲を割り当てておく。例えば、第１ノードにハッシュ値“１１〜５０”、第２ノードにハッシュ値“５１〜９０”などのように担当範囲が割り当てられる。この方法は、Consistent Hashingと呼ばれることもある。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２００５−５０００７号公報
【特許文献２】特開２０１０−１２８６３０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
分散ストレージシステムでは、各ストレージノードにハッシュ値の範囲を割り当てた後に、ストレージノードによってデータ量や受付アクセス数に偏りが生じることがある。その場合、偏りを解消するため、ハッシュ値の範囲の割り当てを変更したいことがある。
【０００８】
しかし、あるストレージノードに対するハッシュ値の範囲の割り当てを一度解除して再定義するという方法を用いると、解除に伴うデータの退避および再定義に伴うデータの引き継ぎという大量のデータ移動が、ストレージノード間で発生する可能性がある。また、当該方法では、変更前に当該ストレージノードが保持しているデータであって変更後も引き続き保持するデータについても移動が発生してしまい、非効率的となる。
【０００９】
一側面では、本発明は、データの移動量を低減できるストレージ制御方法、情報処理装置およびプログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
一実施態様では、複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムが実行するストレージ制御方法が提供される。このストレージ制御方法では、第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノードに割り当てるハッシュ値の範囲を拡大する。第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを検索し、検索されたデータを第２のノードから第１のノードに移動する。
【００１１】
また、一実施態様では、複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられる情報処理装置が提供される。この情報処理装置は、記憶部と制御部とを有する。記憶部は、複数のノードに割り当てたハッシュ値の範囲を示す情報を記憶する。制御部は、第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノードに割り当てるハッシュ値の範囲を拡大し、第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを、第２のノードから第１のノードに移動させる。
【００１２】
また、一実施態様では、コンピュータに実行させるプログラムであって、複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられるプログラムが提供される。
【発明の効果】
【００１３】
一実施態様によれば、データの移動量を低減できる。
【図面の簡単な説明】
【００１４】
【図１】第１の実施の形態の情報処理システムを示す図である。
【図２】第２の実施の形態の分散ストレージシステムを示す図である。
【図３】ストレージ制御装置のハードウェア例を示す図である。
【図４】第２の実施の形態のソフトウェア例を示すブロック図である。
【図５】ハッシュ値の担当範囲の割当例を示す図である。
【図６】担当管理テーブルの例を示す図である。
【図７】ノード利用管理テーブルの例を示す図である。
【図８】担当範囲を拡大する処理例を示すフローチャートである。
【図９】移設するハッシュ値範囲の例を示す図である。
【図１０】Ｒｅａｄ要求受信時の処理例を示すフローチャートである。
【図１１】Ｗｒｉｔｅ要求受信時の処理例を示すフローチャートである。
【発明を実施するための形態】
【００１５】
以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理システムを示す図である。この情報処理システムは、キーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムである。この情報処理システムは、情報処理装置１、第１のノード２および第２のノード２ａを含む。情報処理装置１、第１のノード２および第２のノード２ａは、ネットワークで接続されている。
【００１６】
例えば、第１のノード２には、（ｋｅｙ，ｖａｌｕｅ）のペアとして、（ｋｅｙ１，ｖａｌｕｅ１）、（ｋｅｙ２，ｖａｌｕｅ２）、（ｋｅｙ３，ｖａｌｕｅ３）が格納されている。第１のノード２が担当するハッシュ値の範囲には、ハッシュ値Ｈ（ｋｅｙ１），Ｈ（ｋｅｙ２），Ｈ（ｋｅｙ３）が含まれる。また、例えば、第２のノード２ａには、（ｋｅｙ，ｖａｌｕｅ）のペアとして、（ｋｅｙ４，ｖａｌｕｅ４）、（ｋｅｙ５，ｖａｌｕｅ５）、（ｋｅｙ６，ｖａｌｕｅ６）が格納されている。第２のノード２ａが担当するハッシュ値の範囲には、ハッシュ値Ｈ（ｋｅｙ４），Ｈ（ｋｅｙ５），Ｈ（ｋｅｙ６）が含まれる。ここで、Ｈ（ｋｅｙＮ）は、ｋｅｙＮから算出されたハッシュ値である（Ｎ＝１，２，３，４，５，６）。第１のノード２および第２のノード２ａにそれぞれ割り当てられたハッシュ値の担当範囲は隣接している。
【００１７】
情報処理装置１は、ＣＰＵ（Central Processing Unit）などのプロセッサとＲＡＭ（Random Access Memory）などのメモリとを備えてもよく、メモリに記憶されたプログラムをプロセッサが実行するコンピュータであってもよい。情報処理装置１は、記憶部１ａおよび制御部１ｂを有する。
【００１８】
記憶部１ａは、第１のノード２および第２のノード２ａに割り当てたハッシュ値の範囲を示す情報を記憶する。記憶部１ａは、ＲＡＭやＨＤＤ（Hard Disk Drive）によって実装されてもよい。
【００１９】
制御部１ｂは、記憶部１ａを参照して、各ノードに割り当てるハッシュ値の範囲を変更する。制御部１ｂは、第１のノード２に割り当てるハッシュ値の範囲と第２のノード２ａに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、第１のノード２に割り当てるハッシュ値の範囲を拡大する。第１のハッシュ値は、Ｈ（ｋｅｙ３）とＨ（ｋｅｙ４）との間の値であるとする。また、第２のハッシュ値は、Ｈ（ｋｅｙ４）とＨ（ｋｅｙ５）との間の値であるとする。この場合、制御部１ｂが第１のノード２に割り当てるハッシュ値の範囲を拡大すると、第１のノード２の担当範囲にＨ（ｋｅｙ４）が含まれることになる。
【００２０】
制御部１ｂは、第２のノード２ａに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータを検索し、検索されたデータを第２のノード２ａから第１のノード２に移動する。例えば、制御部１ｂは、第１のハッシュ値と第２のハッシュ値との間に存在するハッシュ値Ｈ（ｋｅｙ４）に対応する“ｖａｌｕｅ４”を検索する。制御部１ｂは、検索した“ｖａｌｕｅ４”を第１のノード２に移動する。
【００２１】
なお、制御部１ｂは、移動対象のハッシュ値範囲を第２のノード２ａに通知して、第２のノード２ａに当該検索を行わせてもよい。また、第２のノード２ａが、移動対象として検索した“ｖａｌｕｅ４”を第１のノード２に移動してもよい。すなわち、制御部１ｂは、検索されたデータの第１のノード２への移動を、第２のノード２ａに行わせてもよい。
【００２２】
情報処理装置１によれば、制御部１ｂにより、第１のノード２に割り当てるハッシュ値の範囲と第２のノード２ａに割り当てるハッシュ値の範囲との境界が、第１のハッシュ値から第２のハッシュ値にシフトされることで、第１のノード２に割り当てるハッシュ値の範囲が拡大される。制御部１ｂにより、第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が第１のハッシュ値と第２のハッシュ値との間に属するデータが検索され、検索されたデータが第２のノード２ａから第１のノード２に移動される。これにより、第１のノード２および第２のノード２ａの間で、移動するデータ量を低減できる。
【００２３】
例えば、第１のノード２の担当範囲を拡大する際、第１のノード２の全データを第２のノード２ａに移動して、第１のノード２の担当範囲を削除し、その後、第１のノード２に拡大後の担当範囲を追加する方法も考えられる。しかし、この方法では、元々第１のノード２に存在していたデータを第２のノード２ａに移動し、担当範囲の再設定後に当該データを第２のノード２ａから第１のノード２に移動する処理が生ずる。このため、元々第１のノード２に存在していたデータの無駄な移動が生じ、移動するデータ量が大きい。
【００２４】
一方、情報処理装置１によれば、担当範囲の拡大によって、第１のノード２が新たに担当するハッシュ値範囲のデータを検索して、該データを第２のノード２ａから第１のノード２に移動させる。このため、第１のノード２の担当範囲の削除／追加を行う場合に比べて、データの無駄な移動が生じない。例えば、元々第１のノード２に存在していたデータの移動が行われない。よって、移動するデータ量を低減でき、担当範囲を拡大する処理を効率的に実行できる。
【００２５】
［第２の実施の形態］
図２は、第２の実施の形態の分散ストレージシステムを示す図である。第２の実施の形態の分散ストレージシステムは、ＫＶＳの手法によりデータを複数のストレージノードに分散配置する。第２の実施の形態の分散ストレージシステムは、ストレージ制御装置１００、ストレージノード２００，２００ａ，２００ｂ、ディスク装置３００，３００ａ，３００ｂおよびクライアント４００を含む。
【００２６】
ネットワーク１０には、ストレージ制御装置１００、ストレージノード２００，２００ａ，２００ｂおよびクライアント４００が接続されている。ネットワーク１０はＬＡＮ（Local Area Network）でもよい。ネットワーク１０はインターネットなどの広域ネットワークでもよい。
【００２７】
ストレージ制御装置１００は、ストレージノード２００，２００ａ，２００ｂのハッシュ値の担当範囲の変更を制御するサーバコンピュータである。
ストレージノード２００には、ディスク装置３００が接続されている。ストレージノード２００ａには、ディスク装置３００ａが接続されている。ストレージノード２００ｂには、ディスク装置３００ｂが接続されている。ストレージノード２００，２００ａ，２００ｂとディスク装置３００，３００ａ，３００ｂとの間のインタフェースには、例えばＳＣＳＩ（Small Computer System Interface）やファイバチャネル（Fibre Channel）などを用いてもよい。ストレージノード２００，２００ａ，２００ｂは、それぞれディスク装置３００，３００ａ，３００ｂからのデータの読出し（Ｒｅａｄ）、および、ディスク装置３００，３００ａ，３００ｂへのデータの書込み（Ｗｒｉｔｅ）を実行するサーバコンピュータである。
【００２８】
ディスク装置３００，３００ａ，３００ｂは、データを記憶する記憶装置である。ディスク装置３００，３００ａ，３００ｂは、ＨＤＤ（Hard Disk Drive）やＳＳＤ（Solid State Drive）などの記憶デバイスを備える。ディスク装置３００，３００ａ，３００ｂは、ストレージノード２００，２００ａ，２００ｂに内蔵されてもよい。
【００２９】
クライアント４００は、分散ストレージシステムに格納されたデータにアクセスするクライアントコンピュータである。例えば、クライアント４００は、ユーザが操作する端末装置である。クライアント４００は、ストレージノード２００，２００ａ，２００ｂの何れかにデータの読出しを要求する（Ｒｅａｄ要求）。クライアント４００は、ストレージノード２００，２００ａ，２００ｂの何れかに、データの書込みを要求する（Ｗｒｉｔｅ要求）。
【００３０】
ここで、ディスク装置３００，３００ａ，３００ｂは、キー（ｋｅｙ）とデータ（ｖａｌｕｅ）のペア（ｋｅｙ，ｖａｌｕｅ）を記憶する。ストレージノード２００，２００ａ，２００ｂは、キーを指定したデータのＲｅａｄ要求があると、当該キーに対応するデータを読み出す。ストレージノード２００，２００ａ，２００ｂは、キーを指定したデータのＷｒｉｔｅ要求があると、当該キーに対応するデータを更新する。このとき、ストレージノード２００，２００ａ，２００ｂは、キーから算出されるハッシュ値に基づいて、アクセス対象のデータが何れのストレージノードの担当下にあるか判断する。
【００３１】
キーに対するハッシュ値は、例えば、ＭＤ５（Message Digest algorithm 5）を用いて算出できる。ＳＨＡ（Secure Hash Algorithm）など他のハッシュ関数を用いてもよい。
図３は、ストレージ制御装置のハードウェア例を示す図である。ストレージ制御装置１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、ディスクドライブ１０６および通信部１０７を有する。各ユニットがストレージ制御装置１００のバスに接続されている。ストレージノード２００，２００ａ，２００ｂおよびクライアント４００もストレージ制御装置１００と同様のハードウェアを用いて実装できる。
【００３２】
ＣＰＵ１０１は、ストレージ制御装置１００の情報処理を制御するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されているプログラムやデータの少なくとも一部を読み出し、ＲＡＭ１０２に展開してプログラムを実行する。なお、ストレージ制御装置１００は、複数のプロセッサを設けて、プログラムを分散して実行してもよい。
【００３３】
ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムや処理に用いるデータを一時的に記憶する揮発性メモリである。なお、ストレージ制御装置１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数個のメモリを備えていてもよい。
【００３４】
ＨＤＤ１０３は、ＯＳ（Operating System）プログラムやアプリケーションプログラムなどのプログラムおよびデータを記憶する不揮発性の記憶装置である。ＨＤＤ１０３は、ＣＰＵ１０１の命令に従って、内蔵の磁気ディスクに対してデータの読み書きを行う。なお、ストレージ制御装置１００は、ＨＤＤ以外の種類の不揮発性の記憶装置（例えば、ＳＳＤなど）を備えてもよく、複数の記憶装置を備えていてもよい。
【００３５】
画像信号処理部１０４は、ＣＰＵ１０１の命令に従って、ストレージ制御装置１００に接続されたディスプレイ１１に画像を出力する。ディスプレイ１１としては、例えば、ＣＲＴ（Cathode Ray Tube）ディスプレイや液晶ディスプレイを用いることができる。
【００３６】
入力信号処理部１０５は、ストレージ制御装置１００に接続された入力デバイス１２から入力信号を取得し、ＣＰＵ１０１に出力する。入力デバイス１２としては、例えば、マウスやタッチパネルなどのポインティングデバイス、キーボードなどを用いることができる。
【００３７】
ディスクドライブ１０６は、記録媒体１３に記録されたプログラムやデータを読み取る駆動装置である。記録媒体１３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。ディスクドライブ１０６は、例えば、ＣＰＵ１０１の命令に従って、記録媒体１３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。
【００３８】
通信部１０７は、ネットワーク１０を介してストレージノード２００，２００ａ，２００ｂおよびクライアント４００と通信を行う通信インタフェースである。通信部１０７は、有線通信インタフェースでもよいし、無線通信インタフェースでもよい。
【００３９】
図４は、第２の実施の形態のソフトウェア例を示すブロック図である。図４に示すユニットの一部または全部は、ストレージ制御装置１００、ストレージノード２００およびクライアント４００が実行するプログラムのモジュールであってもよい。また、図４に示すユニットの一部または全部は、ＦＰＧＡ（Field Programmable Gate Array）やＡＳＩＣ（Application Specific Integrated Circuit）などの電子回路であってもよい。ストレージノード２００ａ，２００ｂもストレージノード２００と同様のユニットを用いて実装できる。
【００４０】
ストレージ制御装置１００は、記憶部１１０、ネットワークＩ／Ｏ（Input / Output）部１２０および担当範囲制御部１３０を有する。
記憶部１１０は、担当管理テーブルおよびノード利用管理テーブルを記憶する。担当管理テーブルは、ストレージノード２００，２００ａ，２００ｂが担当するハッシュ値の範囲を定義したデータである。ノード利用管理テーブルは、ストレージノード２００，２００ａ，２００ｂの利用状況を記録したデータである。記憶部１１０は、ＲＡＭ１０２に確保された記憶領域でもよいし、ＨＤＤ１０３に確保された記憶領域であってもよい。
【００４１】
ネットワークＩ／Ｏ部１２０は、ストレージノード２００，２００ａ，２００ｂから受信したデータを、担当範囲制御部１３０に出力する。ネットワークＩ／Ｏ部１２０は、担当範囲制御部１３０から取得したデータを、ストレージノード２００，２００ａ，２００ｂに送信する。
【００４２】
担当範囲制御部１３０は、ストレージノード２００，２００ａ，２００ｂのハッシュ値の担当範囲の変更を制御する。担当範囲制御部１３０は、ストレージノード２００，２００ａ，２００ｂの利用状況に応じて、または、システム管理者の操作入力に応じて、担当範囲の割り当てを変更する。担当範囲制御部１３０は、担当範囲の変更に伴い、ストレージノード間で移動させるデータを検索する。担当範囲制御部１３０は、移動させるデータが存在する場合、対象のストレージノード間で当該データを移動する。担当範囲制御部１３０は、担当範囲の変更に伴い、記憶部１１０に記憶された担当管理テーブルを更新する。担当範囲制御部１３０は、担当管理テーブルの更新内容を示す更新データをネットワークＩ／Ｏ部１２０に出力する。
【００４３】
ストレージノード２００は、記憶部２１０、ネットワークＩ／Ｏ部２２０、ディスクＩ／Ｏ部２３０、ノード一覧管理部２４０、担当ノード判定部２５０および監視部２６０を有する。
【００４４】
記憶部２１０は、担当管理テーブルを記憶する。当該担当管理テーブルは、記憶部１１０に格納される担当管理テーブルと同じ内容である。記憶部２１０は、ストレージノード２００上のＲＡＭに確保された記憶領域でもよいし、ストレージノード２００上のＨＤＤに確保された記憶領域であってもよい。
【００４５】
ネットワークＩ／Ｏ部２２０は、ストレージ制御装置１００、ストレージノード２００ａ，２００ｂおよびクライアント４００から受信したデータを、ディスクＩ／Ｏ部２３０および担当ノード判定部２５０に出力する。ネットワークＩ／Ｏ部２２０は、ディスクＩ／Ｏ部２３０、担当ノード判定部２５０および監視部２６０から取得したデータを、ストレージ制御装置１００、ストレージノード２００ａ，２００ｂおよびクライアント４００に送信する。
【００４６】
ディスクＩ／Ｏ部２３０は、担当ノード判定部２５０の指示により、ディスク装置３００からデータの読出しを行う。また、ディスクＩ／Ｏ部２３０は、担当ノード判定部２５０の指示により、ディスク装置３００にデータの書込みを行う。
【００４７】
ノード一覧管理部２４０は、ネットワークＩ／Ｏ部２２０がストレージ制御装置１００から受信した更新データに基づいて、記憶部２１０に記憶された担当管理テーブルを更新する。ノード一覧管理部２４０は、担当ノード判定部２５０からの要求により、担当管理テーブルの内容を担当ノード判定部２５０に応答する。
【００４８】
担当ノード判定部２５０は、ネットワークＩ／Ｏ部２２０がクライアント４００から受信したＲｅａｄ要求に基づき、担当ノードを判定する。Ｒｅａｄ要求には、読出し対象のデータに対応するキーが含まれる。担当ノードとは、当該キーから算出されるハッシュ値を担当しているストレージノードである。担当ノード判定部２５０は、算出したハッシュ値とノード一覧管理部２４０から取得する担当管理テーブルとに基づいて、担当ノードを判定できる。担当ノード判定部２５０は、自ノードが担当ノードであれば、ディスクＩ／Ｏ部２３０に読出しを指示する。担当ノード判定部２５０は、自ノード以外のノードが担当ノードであれば、ネットワークＩ／Ｏ部２２０を介して、当該担当ノードにＲｅａｄ要求を転送する。
【００４９】
監視部２６０は、ストレージノード２００の利用状況を監視する。監視部２６０は、監視結果を含む監視データを、ネットワークＩ／Ｏ部２２０を介して、ストレージ制御装置１００に定期的に送信する。利用状況には、例えば、ディスク装置３００が記憶しているデータ量、ディスク装置３００の空き容量およびディスク装置３００へのアクセス数などが含まれる。
【００５０】
クライアント４００は、ネットワークＩ／Ｏ部４１０およびアクセス部４２０を有する。
ネットワークＩ／Ｏ部４１０は、アクセス部４２０からデータのＲｅａｄ要求やＷｒｉｔｅ要求を取得し、ストレージノード２００，２００ａ，２００ｂの何れかに送信する。ネットワークＩ／Ｏ部４１０は、ストレージノード２００，２００ａ，２００ｂからデータを受信すると、アクセス部４２０に出力する。
【００５１】
アクセス部４２０は、読出し対象のデータのキーを含むＲｅａｄ要求を生成して、ネットワークＩ／Ｏ部４１０に出力する。アクセス部４２０は、更新対象のデータのキーを含むＷｒｉｔｅ要求を生成して、ネットワークＩ／Ｏ部４１０に出力する。
【００５２】
なお、第２の実施の形態のストレージ制御装置１００は、第１の実施の形態の情報処理装置１の一例である。担当範囲制御部１３０は、制御部１ｂの一例である。
図５は、ハッシュ値の担当範囲の割当例を示す図である。第２の実施の形態の分散ストレージシステムでは、利用可能なハッシュ値の範囲は“０〜９９”である。ただし、“９９”の次の値は“０”である。そのうちの複数の範囲がストレージノード２００，２００ａ，２００ｂに割り当てられている。ここで、ラベル“Ａ”は、ストレージノード２００の識別情報である。ラベル“Ｂ”は、ストレージノード２００ａの識別情報である。ラベル“Ｃ”は、ストレージノード２００ｂの識別情報である。各ラベルの位置は、各担当範囲の開始位置である。
【００５３】
図５では、各ラベル位置に対応する値を含むハッシュ値範囲Ｒ１，Ｒ２，Ｒ３が示されている。ハッシュ値範囲Ｒ１は“１０〜３９”であり、ストレージノード２００の担当範囲である。ハッシュ値範囲Ｒ２は“４０〜８９”であり、ストレージノード２００ａの担当範囲である。ハッシュ値範囲Ｒ３は“９０〜９９”、“０〜９”であり、ストレージノード２００ｂの担当範囲である。ハッシュ値範囲Ｒ３は、“９９”および“０”を跨いだ領域である。
【００５４】
第２の実施の形態の分散ストレージシステムでは、担当範囲の一端の値を、ストレージノード２００，２００ａ，２００ｂに対して指定することで、ストレージノード２００，２００ａ，２００ｂの担当範囲を割り当てる。例えば、担当範囲の両端の値のうち小さい方（開始位置）を指定する場合、ストレージノード２００にハッシュ値“１０”を、ストレージノード２００ａにハッシュ値“４０”を指定する。これにより、ストレージノード２００の担当範囲が“１０〜３９”となる。ハッシュ値範囲Ｒ３のように、当該範囲が“０”を跨ぐ場合には、例外として、両端の値のうち大きい方が開始位置となる。この場合、例えば、ハッシュ値“９０”を指定することで、“０”を跨いだ範囲を指定できる。
【００５５】
なお、担当範囲の両端の値のうち大きい方（終了位置）を指定して、担当範囲を割り当ててもよい。例えば、ストレージノード２００にハッシュ値“３９”を、ストレージノード２００ａにハッシュ値“８９”を、ストレージノード２００ｂにハッシュ値“９”を指定する。すると、図５で示したハッシュ値範囲Ｒ１，Ｒ２，Ｒ３と同等の担当範囲を、ストレージノード２００，２００ａ，２００ｂに割り当てることができる。この場合も、“０”を跨ぐ範囲については、例外として、両端の値のうち小さい方が終了位置となる。よって、両端の値のうち小さい方を指定することで、“０”を跨いだ範囲を指定できる。
【００５６】
以下の説明では、ストレージノード２００，２００ａ，２００ｂに、担当範囲の開始位置を指定することで、当該担当範囲を割り当てるものとする。ここで、ストレージノード２００，２００ａ，２００ｂには、担当範囲を更に分割したブロック単位で担当範囲が割り当てられる。また、ストレージノード２００，２００ａ，２００ｂの利用状況もブロック単位で管理される。
【００５７】
図６は、担当管理テーブルの例を示す図である。担当管理テーブル１１１は、記憶部１１０に記憶される。また、担当管理テーブル１１１と同様の担当管理テーブルが、記憶部２１０およびストレージノード２００ａ，２００ｂにも格納される。担当管理テーブル１１１は、ブロック開始位置およびノードの項目を含む。
【００５８】
ブロック開始位置の項目には、ブロックの開始位置に対応するハッシュ値が登録される。ノードの項目には、ストレージノード２００，２００ａ，２００ｂのラベルが登録される。例えば、ブロック開始位置が“０”、“１０”のレコードが存在する。この場合、前者のレコードは、ハッシュ値範囲“０〜９”のブロックが、ストレージノード２００ｂ（ラベル“Ｃ”）に割り当てられていることを示す。
【００５９】
図７は、ノード利用管理テーブルの例を示す図である。ノード利用管理テーブル１１２は、記憶部１１０に記憶される。ノード利用管理テーブル１１２は、ブロック開始位置、データ量、空き容量、アクセス数および総転送量の項目を含む。
【００６０】
ブロック開始位置の項目には、ブロックの開始位置に対応するハッシュ値が登録される。データ量の項目には、当該ブロックに記憶済のデータ量（例えば、ＧＢ（Giga Byte）単位）が登録される。空き容量の項目には、当該ブロックの空き容量（例えば、ＧＢ単位）が登録される。アクセス数の項目には、当該ブロックに対する読出し／書込みの総アクセス数が登録される。総転送量の項目には、当該ブロックに対する読出し／書込みに伴うデータの転送量（例えば、ＧＢ単位）の総和が登録される。
【００６１】
図８は、担当範囲を拡大する処理例を示すフローチャートである。以下、図８に示す処理をステップ番号に沿って説明する。
（ステップＳ１１）担当範囲制御部１３０は、ハッシュ値の担当範囲を拡大するストレージノードを決定する。例えば、担当範囲制御部１３０は、記憶部１１０に記憶されたノード利用管理テーブル１１２に基づいて、何れのストレージノードを対象とするか決定する。例えば、最もデータ量の小さいノードを選ぶ、最もデータ量の大きいノードの担当範囲に隣接する範囲を担当するノードを選ぶ、などの方法により対象を決定することが考えられる。あるいは、システム管理者の操作入力により指定されたノードを、担当範囲の拡大対象としてもよい。ここでは、ストレージノード２００ｂを担当範囲の拡大対象に決定したとする。
【００６２】
（ステップＳ１２）担当範囲制御部１３０は、ノード利用管理テーブル１１２を参照して、ハッシュ値範囲Ｒ３の両端のうち拡大する側（開始位置側か終了位置側か）を決定する。例えば、データ量のより大きいストレージノードの担当範囲と隣接する側とする、予め定められた側（開始位置側）とする、などが考えられる。あるいは、システム管理者の操作入力により指定された側を拡大対象に決定してもよい。ここでは、ハッシュ値範囲Ｒ３の開始位置側を拡大する側に決定したとする。この場合、ハッシュ値範囲Ｒ３の開始位置（ハッシュ値範囲Ｒ２，Ｒ３の境界）をストレージノード２００ａが担当するハッシュ値範囲Ｒ２側へシフトして、ハッシュ値範囲Ｒ３を拡大することになる。
【００６３】
（ステップＳ１３）担当範囲制御部１３０は、記憶部１１０に記憶された担当管理テーブル１１１およびノード利用管理テーブル１１２に基づき、ハッシュ値範囲Ｒ３の開始位置のシフト量を決定する。例えば、ストレージノード２００ａ，２００ｂのデータ量が均等になる（あるいは、均等に近くなる）ブロック開始位置“７０”をハッシュ値範囲Ｒ３の新たな開始位置とする（シフト量は“２０”）。この場合、当該新たな開始位置“７０”と元の開始位置“９０”との間の範囲“７０〜８９”がストレージノード２００ａからストレージノード２００ｂに移設する範囲である。また、例えば、担当するハッシュ値範囲に含まれるハッシュ値の個数に基づいて、シフト量を決定してもよい。例えば、移動後に各ノードが担当するハッシュ値範囲に含まれるハッシュ値の個数が均一になるようにシフト量を決定することが考えられる。
【００６４】
（ステップＳ１４）担当範囲制御部１３０は、担当管理テーブル１１１を更新する。具体的には、ブロック開始位置“７０”、“８０”の設定（ラベル“Ｂ”）をストレージノード２００ｂのラベル“Ｃ”に変更する。担当範囲制御部１３０は、当該変更内容を示す更新データをネットワークＩ／Ｏ部１２０に出力する。ネットワークＩ／Ｏ部１２０は、更新データをストレージノード２００，２００ａ，２００ｂに送信する。ストレージノード２００，２００ａ，２００ｂは、更新データを受信すると、自ノードの担当管理テーブルを更新する。
【００６５】
（ステップＳ１５）担当範囲制御部１３０は、ステップＳ１３で決定した範囲“７０〜８９”に属する差分のデータを検索し、ストレージノード２００ａからストレージノード２００ｂに移動する。例えば、担当範囲制御部１３０は、ストレージノード２００ａに当該範囲にハッシュ値が属するデータを問い合わせて、ストレージノード２００ａからストレージノード２００ｂに当該データを移動する。また、例えば、担当範囲制御部１３０は、ディスク装置３００ａにおける当該範囲に対応するアドレス（ディレクトリ名やセクタ番号など）をブロックに対応付けて管理してもよい。例えば、担当管理テーブル１１１の各ブロック開始位置に対応付けて、当該アドレスを登録することが考えられる。このようにすれば、担当範囲制御部１３０は、移動対象のデータの格納位置を当該アドレスに基づいて検索できる。担当範囲制御部１３０は、移動対象範囲をストレージノード２００ａに通知して、ストレージノード２００ａにより該移動対象範囲のデータをストレージノード２００ｂへ移動させてもよい。
【００６６】
このように、担当範囲制御部１３０は、ストレージノード２００ｂに対してストレージノード２００ａとの境界側を、担当範囲を拡大させる側と決定する。担当範囲制御部１３０は、ハッシュ値範囲Ｒ３の開始位置（ハッシュ値範囲Ｒ２，Ｒ３の境界値）をハッシュ値範囲Ｒ２側にシフトさせる。シフト量は、ストレージノード２００ａ，２００ｂの利用状況により決定する。そして、シフト分のハッシュ値範囲に属するデータを、ストレージノード２００ａからストレージノード２００ｂに移動する。
【００６７】
なお、ステップＳ１１〜Ｓ１３では、上述した方法以外の方法で、担当を拡大するストレージノードおよび担当範囲の開始位置のシフト量を決定してもよい。例えば、次の（１）、（２）の何れかの方法を用いることも考えられる。
【００６８】
（１）空き容量が少ないノードを担当範囲の拡大対象として、空き容量の多いノードからハッシュ値範囲の一部を移設するように決定する。そして、両ノードの空き容量が均等になるように開始位置のシフト量を決定する。各ノードの空き容量は、ノード利用管理テーブル１１２で照会できる（例えば、ノードごとにブロックの空き容量の和をとれば、ノードごとの空き容量の総和が得られる）。これにより、当該空き容量が少ないノードの空き容量の増加を図れる。
【００６９】
（２）負荷の小さい（アクセス数や総転送量など）ノードを担当範囲の拡大対象として、負荷の大きいノードからハッシュ値範囲の一部を移設するように決定する。そして、両ノードの負荷が均等になるように開始位置のシフト量を決定する。各ノードの負荷は、ノード利用管理テーブル１１２で照会できる（例えば、ノードごとにブロックのアクセス数の和をとれば、ノードごとのアクセス数の総和が得られる）。これにより、各ノードの負荷分散を図れる。
【００７０】
更に、例示した複数の方法を組み合わせてシフト量を決定してもよい。例えば、データ量を均等にするシフト量を決定した後、両ノードのアクセス数の差がより小さくなるようにシフト量を調整することも考えられる。例えば、まず、ハッシュ値範囲Ｒ３の開始位置を開始位置“７０”に仮決定する（シフト量“２０”に仮決定）。そして、ストレージノード２００ａ，２００ｂのアクセス数の差が小さくなるように、開始位置を“６０”に決定する（シフト量“３０”に決定）。
【００７１】
なお、上記（２）では、負荷として、各ストレージノードのＣＰＵ使用率などの他の指標を用いてもよい。その場合、例えば、ストレージ制御装置１００は、各ストレージノードからＣＰＵ使用率などの指標を収集する。
【００７２】
また、担当範囲制御部１３０は、ブロック単位でデータの移動を行う。このため、ブロックを移設する順序を、任意に決定できる。例えば、対象ブロックごとの利用状況に基づいて順序を決定することが考えられる。より具体的には、現在アクセス中のデータを多く含むブロック程、後回しにすることが考えられる。また、例えば、システム管理者の操作入力により指定された順序とすることが考えられる。
【００７３】
また、上記ステップＳ１４，Ｓ１５を逆の順序で行ってもよい。
図９は、移設するハッシュ値範囲の例を示す図である。図９では、図５に示したハッシュ値範囲Ｒ３をハッシュ値範囲Ｒ２側へシフト量“２０”だけ拡大した場合を例示している。ハッシュ値範囲Ｒ２ａは、ストレージノード２００ａの変更後の担当範囲である。ハッシュ値範囲Ｒ２ａでは、ハッシュ値範囲Ｒ３の拡大に伴って、終了位置が“６９”にシフトしている。
【００７４】
ハッシュ値範囲Ｒ３ａは、ストレージノード２００ｂの変更後の担当範囲である。ハッシュ値範囲Ｒ３ａでは、開始位置が“９０”から“７０”にシフトしている。
ハッシュ値範囲Ｒ２ｂは、ハッシュ値範囲Ｒ２，Ｒ３ａの重なり合う領域であり、“７０〜８９”の範囲である。ハッシュ値範囲Ｒ２ｂは、ストレージノード２００ａからストレージノード２００ｂに移設する範囲である。ハッシュ値範囲Ｒ２ｂに属するデータが、ストレージノード２００ａからストレージノード２００ｂへの移動対象データである。
【００７５】
このように、ストレージ制御装置１００は、ハッシュ値範囲Ｒ３の開始位置（ハッシュ値範囲Ｒ２，Ｒ３の境界）をシフトさせることで、ハッシュ値範囲Ｒ３をハッシュ値範囲Ｒ３ａへ拡大する。そして、ハッシュ値範囲Ｒ２ｂに属するデータをストレージノード２００ａからストレージノード２００ｂへ移動する。
【００７６】
ここで、例えば、ハッシュ値範囲Ｒ３を拡大する際、ハッシュ値範囲Ｒ３を削除して、ハッシュ値範囲Ｒ３のデータをストレージノード２００ａに移動してから、ストレージノード２００ｂにハッシュ値範囲Ｒ３ａを割り当てる方法も考えられる。この場合、ハッシュ値範囲Ｒ３に属する全データをストレージノード２００ａに移動する（ハッシュ値範囲Ｒ３に属していたデータはハッシュ値範囲Ｒ２に属することとなる）。そして、ハッシュ値範囲Ｒ３ａの割当後、ハッシュ値範囲Ｒ３ａに属するデータを、ストレージノード２００ａからストレージノード２００ｂに移動する。しかし、この方法では、元々ストレージノード２００ｂに存在していたデータ（ハッシュ値範囲Ｒ３に属していたデータ）の無駄な移動が生じ、移動するデータ量が大きい。
【００７７】
一方、ストレージ制御装置１００によれば、ハッシュ値範囲Ｒ３の削除を伴わないので、ハッシュ値範囲Ｒ３に属するデータのストレージノード２００ａへの移動が生じない。データの移動は、差分のデータ、すなわち、ハッシュ値範囲Ｒ２ｂに属するデータの移動で済む。よって、移動するデータ量を低減できる。ストレージノード２００の担当範囲を拡大する処理を効率的に実行できる。
【００７８】
なお、ストレージ制御装置１００をストレージノード２００，２００ａ，２００ｂとは別個に設ける場合を例示したが、担当範囲制御部１３０の機能をストレージノード２００，２００ａ，２００ｂの何れかまたは全部に設けてもよい。何れかのストレージノードに担当範囲制御部１３０の機能を設ける場合、当該ストレージノードが他のストレージノードの情報を収集して、一元管理する。全部のストレージノードに担当範囲制御部１３０の機能を設ける場合、全部のストレージノードの情報を各ストレージノードで共有し、それぞれのストレージノードが、所定のタイミングで担当範囲制御部１３０の機能を発揮すればよい。所定のタイミングとしては、例えば、ストレージノードが自身の空き容量が閾値よりも小さくなったことを検知したタイミングが考えられる。この場合、当該ストレージノードは、自身の空き容量を増やすように担当範囲の拡大を行う。あるいは、所定のタイミングとしては、例えば、ストレージノードが自身の負荷（例えば、アクセス数）が閾値を上回ったことを検知したタイミングが考えられる。この場合、当該ストレージノードは、負荷が分散されるように担当範囲の拡大を行う。
【００７９】
ここで、あるストレージノードの担当範囲の変更に伴うデータ移動の最中に、移設対象の範囲に属するデータへのクライアント４００からのアクセスが発生することもある。このとき、ストレージノード２００，２００ａ，２００ｂの担当管理テーブルには、変更後の担当範囲がデータ移動よりも先に登録されるので、アクセス先のノードに対象のキーに対応するデータが存在しないことがある。その場合にも、ストレージノード２００，２００ａ，２００ｂは当該アクセスに適切に対処できることが望ましい。そこで、以下では、データ移動の最中にクライアント４００からデータへのアクセスがあった場合の処理を説明する。まず、データのＲｅａｄ要求を受信した場合の処理例を説明する。
【００８０】
図１０は、Ｒｅａｄ要求受信時の処理例を示すフローチャートである。以下、図１０に示す処理をステップ番号に沿って説明する。
（ステップＳ２１）ネットワークＩ／Ｏ部２２０は、クライアント４００からＲｅａｄ要求を受信する。ネットワークＩ／Ｏ部２２０は、担当ノード判定部２５０にＲｅａｄ要求を出力する。
【００８１】
（ステップＳ２２）担当ノード判定部２５０は、Ｒｅａｄ要求が自ノードへのアクセスか否かを判断する。自ノードへのアクセスである場合、処理をステップＳ２４に進める。自ノード以外のノードへのアクセスである場合、処理をステップＳ２３に進める。自ノードの担当範囲は、記憶部２１０に記憶された担当管理テーブルにより特定できる。自ノードへのアクセスか否かは、Ｒｅａｄ要求に含まれるキーから算出されるハッシュ値が、自ノードの担当範囲に属するか否かにより判断できる。ハッシュ値が自ノードの担当範囲に属する場合、自ノードへのアクセスである。ハッシュ値が自ノードの担当範囲に属さない場合、自ノード以外のノードへのアクセスである。
【００８２】
（ステップＳ２３）担当ノード判定部２５０は、アクセス対象のハッシュ値が属する範囲を担当する担当ノードを、担当管理テーブルを参照して特定する。担当ノード判定部２５０は、特定した担当ノードにＲｅａｄ要求を転送する。そして、処理を終了する。
【００８３】
（ステップＳ２４）担当ノード判定部２５０は、キーに対応するＲｅａｄ対象のデータが移動済であるか否かを判断する。移動済でない場合、処理をステップＳ２５に進める。移動済である場合、処理をステップＳ２６に進める。ここで、移動済でない場合とは、例えば、ストレージノード２００の担当範囲を拡大済であるが、拡大した範囲に属する当該データのストレージノード２００への移動が未完了である場合である。この場合、Ｒｅａｄ対象のデータは、当該データの移動元のストレージノードに存在している。
【００８４】
（ステップＳ２５）担当ノード判定部２５０は、当該データの移動元のストレージノード（移動元ノード）を、クライアント４００に応答する。移動元ノードとは、担当範囲の拡大に伴って、ストレージノード２００が現在通信している相手ノードである。クライアント４００は、当該移動元ノードに、再度Ｒｅａｄ要求を送信する。そして、処理を終了する。
【００８５】
（ステップＳ２６）担当ノード判定部２５０は、キーに対応するデータの読出しをディスクＩ／Ｏ部２３０に指示する。ディスクＩ／Ｏ部２３０は、ディスク装置３００から当該データの読出しを行う。
【００８６】
（ステップＳ２７）ディスクＩ／Ｏ部２３０は、読出したデータをネットワークＩ／Ｏ部２２０に出力する。ネットワークＩ／Ｏ部２２０は、ディスクＩ／Ｏ部２３０から取得した当該データを、クライアント４００に送信する。
【００８７】
このように、ストレージノード２００，２００ａ，２００ｂは、Ｒｅａｄ要求があったときに、Ｒｅａｄ対象のデータが未移動である場合、移動元ノードを応答する。クライアント４００は、当該応答に基づいて、移動元ノードに再度Ｒｅａｄ要求を送信し、当該データに適切にアクセスできる。
【００８８】
なお、ステップＳ２３において、Ｒｅａｄ要求を受信した担当ノードも、上記ステップＳ２１〜Ｓ２７の処理を行うことで、Ｒｅａｄ要求を適切に処理できる。
また、ステップＳ２５において、Ｒｅａｄ要求を受信した移動元ノードも、上記ステップＳ２１〜Ｓ２７の処理を行うことで、Ｒｅａｄ要求を適切に処理できる。
【００８９】
更に、ステップＳ２５では、移動対象のデータに対するＲｅａｄ要求につき、移動元ノードを応答して、クライアント４００にリトライさせる例を示した。一方、アクセスを受け付けたノードと移動元ノードとの間でＲｅａｄ要求を送受信して、Ｒｅａｄ対象のデータをクライアント４００に応答してもよい。例えば、クライアント４００からＲｅａｄ要求を受信したノードが、移動元ノードにＲｅａｄ要求を転送する。移動元ノードは、当該Ｒｅａｄ要求に応じたデータをクライアント４００に応答する。
【００９０】
次に、データのＷｒｉｔｅ要求を受信した場合の処理例を説明する。
図１１は、Ｗｒｉｔｅ要求受信時の処理例を示すフローチャートである。以下、図１１に示す処理をステップ番号に沿って説明する。
【００９１】
（ステップＳ３１）ネットワークＩ／Ｏ部２２０は、クライアント４００からＷｒｉｔｅ要求を受信する。ネットワークＩ／Ｏ部２２０は、担当ノード判定部２５０にＷｒｉｔｅ要求を出力する。
【００９２】
（ステップＳ３２）担当ノード判定部２５０は、Ｗｒｉｔｅ要求が自ノードへのアクセスか否かを判断する。自ノードへのアクセスである場合、処理をステップＳ３４に進める。自ノード以外のノードへのアクセスである場合、処理をステップＳ３３に進める。
【００９３】
（ステップＳ３３）担当ノード判定部２５０は、アクセス対象のハッシュ値が属する範囲を担当する担当ノードを、記憶部２１０に記憶された担当管理テーブルを参照して特定する。担当ノード判定部２５０は、特定した担当ノードにＷｒｉｔｅ要求を転送する。そして、処理を終了する。
【００９４】
（ステップＳ３４）担当ノード判定部２５０は、キーに対応するデータの書込み（更新）をディスクＩ／Ｏ部２３０に指示する。ディスクＩ／Ｏ部２３０は、ディスク装置３００に当該データの書込みを行う。ディスクＩ／Ｏ部２３０は、ネットワークＩ／Ｏ部２２０を介して、クライアント４００に書込み完了を応答する。
【００９５】
（ステップＳ３５）担当ノード判定部２５０は、ステップＳ３４で書込みを行ったデータがストレージノード２００の担当範囲の拡大に伴うデータ移動の対象であるか否かを判断する。移動対象である場合、処理をステップＳ３６に進める。移動対象でない場合、処理を終了する。例えば、担当ノード判定部２５０は、次の（１）〜（３）の条件が全て満たされるときに、当該データが移動対象であると判断できる。（１）自ノードが、担当範囲の拡大に伴い移動元ノードからデータを移動中である。（２）アクセス対象のキーから算出されるハッシュ値が拡大後の担当範囲に属する。（３）当該キーに対応するデータを移動元ノードから未だ移動していない。
【００９６】
（ステップＳ３６）担当ノード判定部２５０は、ステップＳ３４で書込みを行ったデータを移動元ノードからの移動対象から除外する。例えば、担当ノード判定部２５０は、当該データに対応するキーのデータを、移動せずに削除するよう移動元ノードに依頼する。また、例えば、担当ノード判定部２５０は、当該キーのデータを移動元ノードから受信したとき、当該データを破棄する。
【００９７】
このように、ストレージノード２００，２００ａ，２００ｂは、Ｗｒｉｔｅ要求があったときに、データの書込みを行い、移動元ノードから受信するデータによって、書き込んだデータが更新されないようにする。これにより、新しいデータが古いデータで上書きされるのを防止できる。
【００９８】
なお、ステップＳ３３において、Ｗｒｉｔｅ要求を受信した担当ノードも、上記ステップＳ３１〜Ｓ３６の処理を行うことで、Ｗｒｉｔｅ要求を適切に処理できる。
また、ステップＳ３４では、更新対象のデータが未移動であれば、移動元ノードにＷｒｉｔｅ要求を転送して、移動元ノードにデータの更新を実行させてもよい。更に、ステップＳ３４では、更新対象のデータが未移動であれば、当該データの移動を先に行ってから、当該データの更新を行ってもよい。
【００９９】
更に、上述の例では、担当範囲を拡大したとき、ストレージノード２００，２００ａ，２００ｂが保持する担当範囲テーブルを更新した後に、データの移動を行うものとしたが、これらの手順を逆の順序で行ってもよい。具体的には、担当範囲制御部１３０は、担当範囲を拡大する場合、データの移動を行ったあとに、ストレージノード２００，２００ａ，２００ｂが保持する担当範囲テーブルを更新するようにしてもよい。
【０１００】
この場合、移設中の範囲に属するデータに対してクライアント４００からアクセスがあると、移動先のストレージノードに当該データが移動済で、アクセスを受けたストレージノードに当該データが存在しないことがある。その場合には、アクセスを受けたストレージノードが、移動先のストレージノードをクライアント４００に応答すればよい。そうすれば、クライアント４００は、移動先のストレージノードに対し、改めて当該データへアクセスできる。
【符号の説明】
【０１０１】
１ 情報処理装置
１ａ 記憶部
１ｂ 制御部
２ 第１のノード
２ａ 第２のノード
【特許請求の範囲】
【請求項１】
複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムが実行するストレージ制御方法であって、
第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、前記第１のノードに割り当てるハッシュ値の範囲を拡大し、
前記第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するデータを検索し、検索されたデータを前記第２のノードから前記第１のノードに移動する、
ストレージ制御方法。
【請求項２】
前記複数のノードのデータ格納状況およびアクセス処理状況の少なくとも一方に基づいて、前記複数のノードの中から、割り当てるハッシュ値の範囲を拡大する前記第１のノードを選択する、請求項１記載のストレージ制御方法。
【請求項３】
前記複数のノードの中から前記第１のノードを選択し、割り当てられているハッシュ値の範囲が前記第１のノードと隣接するノードを前記第２のノードとして選択する、請求項１または２記載のストレージ制御方法。
【請求項４】
シフト後の境界である前記第２のハッシュ値を、前記第１および第２のノードに割り当てられているハッシュ値の個数に基づいて決定する、請求項１乃至３の何れか一項に記載のストレージ制御方法。
【請求項５】
データの移動が完了する前に、ハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するキーを指定したアクセスを、前記第１のノードで受け付け可能とし、
前記第１のノードにおいて、アクセスで指定されたキーに対応するデータが移動済みか否かを判定し、判定結果に応じた方法で当該アクセスを処理する、
請求項１乃至４の何れか一項に記載のストレージ制御方法。
【請求項６】
複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられる情報処理装置であって、
前記複数のノードに割り当てたハッシュ値の範囲を示す情報を記憶する記憶部と、
第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を第１のハッシュ値から第２のハッシュ値にシフトすることで、前記第１のノードに割り当てるハッシュ値の範囲を拡大し、前記第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するデータを、前記第２のノードから前記第１のノードに移動させる制御部と、
を有する情報処理装置。
【請求項７】
複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられるプログラムであって、コンピュータに、
第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、前記第１のノードに割り当てるハッシュ値の範囲を拡大し、
前記第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するデータを、前記第２のノードから前記第１のノードに移動させる、
処理を実行させるプログラム。
【請求項１】
複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムが実行するストレージ制御方法であって、
第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、前記第１のノードに割り当てるハッシュ値の範囲を拡大し、
前記第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するデータを検索し、検索されたデータを前記第２のノードから前記第１のノードに移動する、
ストレージ制御方法。
【請求項２】
前記複数のノードのデータ格納状況およびアクセス処理状況の少なくとも一方に基づいて、前記複数のノードの中から、割り当てるハッシュ値の範囲を拡大する前記第１のノードを選択する、請求項１記載のストレージ制御方法。
【請求項３】
前記複数のノードの中から前記第１のノードを選択し、割り当てられているハッシュ値の範囲が前記第１のノードと隣接するノードを前記第２のノードとして選択する、請求項１または２記載のストレージ制御方法。
【請求項４】
シフト後の境界である前記第２のハッシュ値を、前記第１および第２のノードに割り当てられているハッシュ値の個数に基づいて決定する、請求項１乃至３の何れか一項に記載のストレージ制御方法。
【請求項５】
データの移動が完了する前に、ハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するキーを指定したアクセスを、前記第１のノードで受け付け可能とし、
前記第１のノードにおいて、アクセスで指定されたキーに対応するデータが移動済みか否かを判定し、判定結果に応じた方法で当該アクセスを処理する、
請求項１乃至４の何れか一項に記載のストレージ制御方法。
【請求項６】
複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられる情報処理装置であって、
前記複数のノードに割り当てたハッシュ値の範囲を示す情報を記憶する記憶部と、
第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を第１のハッシュ値から第２のハッシュ値にシフトすることで、前記第１のノードに割り当てるハッシュ値の範囲を拡大し、前記第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するデータを、前記第２のノードから前記第１のノードに移動させる制御部と、
を有する情報処理装置。
【請求項７】
複数のノードを有しておりキーと対応付けられたデータを当該キーから算出されるハッシュ値に応じたノードに格納するシステムの制御に用いられるプログラムであって、コンピュータに、
第１のノードに割り当てるハッシュ値の範囲と第２のノードに割り当てるハッシュ値の範囲との境界を、第１のハッシュ値から第２のハッシュ値にシフトすることで、前記第１のノードに割り当てるハッシュ値の範囲を拡大し、
前記第２のノードに格納されたデータの一部であって、キーから算出されるハッシュ値が前記第１のハッシュ値と前記第２のハッシュ値との間に属するデータを、前記第２のノードから前記第１のノードに移動させる、
処理を実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２０１３−４５３７８（Ｐ２０１３−４５３７８Ａ）
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願番号】特願２０１１−１８４３０８（Ｐ２０１１−１８４３０８）
【出願日】平成２３年８月２６日（２０１１．８．２６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年３月４日（２０１３．３．４）
【国際特許分類】
【出願日】平成２３年８月２６日（２０１１．８．２６）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]