ストレージ装置、ストレージシステム、データ更新方法およびデータ管理プログラム
【課題】レプリカの更新に要する時間を短縮する。
【解決手段】複数のノード２〜６は、データの複製であるレプリカを記憶する。このノード２は、クライアント７からレプリカＡ１〜Ａ４の更新を要求された場合は、自ストレージ装置を始端とし、複数のノードを接続する複数の経路を介して、各経路の終端となるノード５にデータの更新を要求するｕｐｄａｔｅ要求を送信する。ノード２は、ノード５が全ての経路を介してｕｐｄａｔｅ要求を受信した後に発行したｕｐｄａｔｅｄ要求を、いずれかの経路を介して受信した場合には、レプリカの更新が完了した旨をクライアント７に通知する。
【解決手段】複数のノード２〜６は、データの複製であるレプリカを記憶する。このノード２は、クライアント７からレプリカＡ１〜Ａ４の更新を要求された場合は、自ストレージ装置を始端とし、複数のノードを接続する複数の経路を介して、各経路の終端となるノード５にデータの更新を要求するｕｐｄａｔｅ要求を送信する。ノード２は、ノード５が全ての経路を介してｕｐｄａｔｅ要求を受信した後に発行したｕｐｄａｔｅｄ要求を、いずれかの経路を介して受信した場合には、レプリカの更新が完了した旨をクライアント７に通知する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ストレージ装置、ストレージシステム、データ更新方法およびデータ管理プログラムに関する。
【背景技術】
【０００２】
従来、分散ＫＶＳ（Key-Value Store）等のＮｏＳＱＬを初めとするストレージシステムにおいて、データの複製であるレプリカを複数のノードに配置する技術が知られている。このような技術が適用されたストレージシステムは、レプリカを複数のノードに配置することで、ディスク故障などによるデータの消失を防ぐとともに、各ノードに配置されたレプリカからデータの読出しを許可することで、アクセスの負荷分散を行う。
【０００３】
ここで、ストレージシステムは、各レプリカから読み出されるデータの同一性を保証するＳｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙが要求される場合がある。このようなＳｔｒｏ
ｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保つ手法の一例として、チェインレプリケーションの技術が知られている。このようなチェインレプリケーションが適用されたストレージシステムの一例について以下に説明する。
【０００４】
図２３は、チェインレプリケーションの一例について説明するための図である。なお、図２３に示す例では、チェインレプリケーションの一例としてＣＲＡＱ（Ｃｈａｉｎ Ｒｅｐｌｉｃａｔｉｏｎ ｗｉｔｈ Ａｐｐｏｒｔｉｏｎｅｄ Ｑｕｅｒｙ）が適用されたストレージシステムについて説明する。
【０００５】
図２３に示す例では、ストレージシステムは、同一のレプリカを有するＮ個のノードを有する。なお、図２３に示す例では、ストレージシステムは、Ｎ個のノードのうち、１ｓｔノード、２ｎｄノード、３ｒｄノード、Ｎｔｈノード以外のノードについては、図示を省略した。
【０００６】
このようなストレージシステムが有する各ノードは、クライアントからレプリカの更新を要求された場合には、各ノードを順に並べた経路に沿って、レプリカの更新を要求するｕｐｄａｔｅ要求を順次転送する。例えば、図２３中（Ａ）に示す例では、クライアントは、レプリカの更新要求を１ｓｔノードに発行する。このような場合には、１ｓｔノードは、レプリカの更新を準備するとともに、図２３中（Ｂ）に示すように、２ｎｄノードにｕｐｄａｔｅ要求を送信する。
【０００７】
次に、２ｎｄノードは、１ｓｔノードからｕｐｄａｔｅ要求を受信した場合には、レプリカの更新を準備するとともに、ｕｐｄａｔｅ要求を３ｒｄノードに転送する。その後、各ノードは、ｕｐｄａｔｅ要求を経路の終端となるＮｔｈノードまで順に転送する。また、図２３中（Ｃ）に示すように、経路の終端となるＮｔｈノードは、ｕｐｄａｔｅ要求を受信した場合には、レプリカを更新するとともに、ｕｐｄａｔｅ要求に対する応答であるｕｐｄａｔｅｄ要求を経路の１つ前のノードに送信する。
【０００８】
その後、各ノードは、ｕｐｄａｔｅｄ要求を受信した場合は、レプリカの更新を行うとともに、ｕｐｄａｔｅｄ要求を１次元の経路に沿って、始点となる１ｓｔノードまで順に転送する。そして、１ｓｔノードは、図２３中（Ｄ）に示すように、ｕｐｄａｔｅｄ要求を受信した場合には、レプリカを更新し、更新が終了した旨をクライアントに通知する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Object Storage on CRAQ, High-throughput chain replication for read-mostly workloads, Jeff Terrace and Michael J.Freedman Princeton University, USENIX annual Technical Conference.San Diego, CA, June 2009.
【非特許文献２】Chain Replication for Supporting High Throughput and Availability, Robbert van Renesse, Fred B.Schneider, USENIX Association OSDI’04:6th Symposium on Operation Systems Design and Implementation.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、上述したチェインレプリケーションの技術では、レプリカの更新を行う場合は、各ノードを順に接続する１つの経路に沿って、ｕｐｄａｔｅ要求を順に転送するので、ノードの数が増加するに従って、更新に要する時間が増加するという問題がある。
【００１１】
例えば、上述したチェインレプリケーションの技術では、ノードの数が倍になると、データの更新に要する時間も倍になってしまう。また、ノードの設置位置を分散させる分散環境の技術が適用されたストレージシステムにおいては、ノードを広域に設置し、ノード同士の距離が離れると、ネットワークの遅延が増加するので、レプリカの更新処理に要する時間がボトルネックとなってしまう。
【００１２】
本願は、上述した問題に鑑みてなされたものであり、１つの側面では、レプリカの更新に要する時間を短縮する。
【課題を解決するための手段】
【００１３】
１つの側面では、データの複製を記憶する複数のストレージ装置のうち、クライアントからデータの更新を要求されるストレージ装置である。このストレージ装置は、データの更新を要求された場合は、自ストレージ装置を始端とし、複数のストレージ装置を直列に接続する複数の経路を介して、各経路の終端となる１つまたは複数のストレージ装置にデータの更新を要求する更新要求を送信する。また、ストレージ装置は、各経路の終端となるストレージ装置が全ての経路を介して更新要求を受信した後に発行した応答を、更新通知を送信したいずれかの経路を介して受信した場合は、データの更新が完了した旨を前記クライアントに通知する。
【発明の効果】
【００１４】
１つの側面では、レプリカの更新に要する時間を短縮する。
【図面の簡単な説明】
【００１５】
【図１】図１は、実施例１に関わるストレージシステムの一例を説明するための図である。
【図２ａ】図２ａは、データＡのレプリカを記憶するノードを説明するための図である。
【図２ｂ】図２ｂは、データＢのレプリカを記憶するノードを説明するための図である。
【図２ｃ】図２ｃは、データＣのレプリカを記憶するノードを説明するための図である。
【図３】図３は、実施例１に関わる始端ノードの一例を説明するための図である。
【図４ａ】図４ａは、実施例１に関わるデータ記憶部が記憶する位置情報の一例を説明するための図である。
【図４ｂ】図４ｂは、実施例１に関わるデータ記憶部が記憶する各レプリカＡ１〜Ａ４を記憶するノードを示す情報の一例を説明するための図である。
【図５】図５は、実施例１に関わる始端ノードがｕｐｄａｔｅ要求を発行する処理の一例を説明するための図である。
【図６】図６は、実施例１に関わる始端ノードがｕｐｄａｔｅｄ要求を受信した際に実行する処理の一例を説明するための図である。
【図７】図７は、実施例１に関わる終端ノードの一例を説明するための図である。
【図８】図８は、実施例１に関わる終端ノードが実行する処理の一例を説明するための図である。
【図９ａ】図９ａは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。
【図９ｂ】図９ｂは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。
【図１０】図１０は、始端ノードが実行する処理の流れの一例を説明するためのフローチャートである。
【図１１】図１１は、中間ノードが実行する処理の流れの一例を説明するためのフローチャートである。
【図１２】図１２は、終端ノードが実行する処理の流れの一例を説明するためのフローチャートである。
【図１３】図１３は、実施例２に関わるストレージシステムの一例を説明するための図である。
【図１４】図１４は、実施例２に関わる始端ノードの一例を説明するための図である。
【図１５】図１５は、実施例２に関わる終端ノードの一例を説明するための図である。
【図１６】図１６は、実施例２に関わる終端ノードがＧｅｔ要求を受信した際に実行する処理の一例を説明するための図である。
【図１７】図１７は、実施例２に関わる終端ノードがｕｐｄａｔｅ要求を受信した際に実行する処理の一例を説明するための図である。
【図１８ａ】図１８ａは、実施例２に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。
【図１８ｂ】図１８ｂは、実施例２に関わる終端ノードがｒｅａｄｙＴｏＵｐｄａｔｅ要求を送受信する処理を説明するための図である。
【図１８ｃ】図１８ｃは、実施例２に関わるストレージシステムがｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。
【図１８ｄ】図１８ｄは、実施例２に関わるストレージシステムにおける動作を説明するための図である。
【図１９】図１９は、複数の経路の終端ノードが実行する処理の一例を説明するための図である。
【図２０】図２０は、実施例２に関わる終端ノードが実行する処理の流れを説明するためのフローチャートである。
【図２１】図２１は、Ｇｅｔ要求に対する処理の流れの一例を説明するためのフローチャートである。
【図２２】図２２は、データ管理プログラムを実行するコンピュータの一例を説明するための図である。
【図２３】図２３は、チェインレプリケーションの一例について説明するための図である。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して本願に係るストレージ装置、ストレージシステム、データ更新方法およびデータ管理プログラムについて説明する。
【実施例１】
【００１７】
以下の実施例１では、図１を用いて、ストレージシステムの一例を説明する。図１は、実施例１に関わるストレージシステムの一例を説明するための図である。なお、以下の説明において、ノードとは、例えば、データの複製であるレプリカを記憶する情報処理装置と、他のノードとの通信処理、データの更新処理、データの管理処理等を実行する演算処理装置とを有するストレージ装置やサーバ等が適用されるものとする。
【００１８】
図１に示すように、ストレージ装置１は、複数のデータセンター＃１〜＃３およびクライアント７をＩＰ（Internet Protocol）網８を介して接続したシステムである。また、データセンター＃１には、ノード２とノード３が設置されており、データセンター＃２には、ノード４、ノード５が設置されており、データセンター＃３には、ノード６が設置されている。
【００１９】
また、各ノード２〜６は、データの複製であるレプリカを記憶する。具体的には、各ノード２〜６は、データＡのレプリカであるレプリカＡ１〜Ａ４、データＢのレプリカであるレプリカＢ１〜Ｂ４、データＣのレプリカであるレプリカＣ１〜Ｃ４を分散させて記憶する。
【００２０】
例えば、図１に示す例では、ノード２は、レプリカＡ１とレプリカＣ４を記憶する。また、ノード３は、レプリカＡ２、レプリカＢ１を記憶する。また、ノード４は、レプリカＡ３、レプリカＣ１、レプリカＢ２を記憶する。また、ノード５は、レプリカＡ４、レプリカＣ２、レプリカＢ３を記憶する。また、ノード６は、レプリカＢ４とレプリカＣ３を記憶する。
【００２１】
ここで、図２ａ〜図２ｃを用いて、各データＡ〜Ｃのレプリカをどのノード２〜６が記憶しているかを説明する。なお、図２ａは、データＡのレプリカを記憶するノードを説明するための図である。また、図２ｂは、データＢのレプリカを記憶するノードを説明するための図である。また、図２ｃは、データＣのレプリカを記憶するノードを説明するための図である。なお、図２ａ〜図２ｃでは、各行に各レプリカを、各列に各ノード２〜６を対応付け、丸印が付けられたマスの行に対応付けたレプリカを、列に対応付けたノードが記憶することを示した。
【００２２】
例えば、図２ａに示すように、データＡのレプリカであるレプリカＡ１〜Ａ４は、ノード２〜５が記憶する。また、図２ｂに示すように、データＢのレプリカであるレプリカＢ１〜Ｂ４は、ノード３〜６が記憶する。また、図２ｃに示すように、データＣのレプリカであるレプリカＣ１〜Ｃ４は、ノード２及びノード４〜６が記憶する。
【００２３】
クライアント７は、各ノード２〜６が記憶する各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４を用いて、各データＡ〜Ｃの読出しや各データＡ〜Ｃの更新等を実行する。具体的には、クライアント７は、各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４がどのノードに記憶されているかを示す情報を記憶する。
【００２４】
そして、クライアント７は、ＩＰ網８を介して、レプリカの読出し要求を示すＧｅｔ要求を、ｕｐｄａｔｅ要求を転送する経路の終端ノードに発行する。例えば、クライアント７は、データＡの更新においてノード５が終端ノードとなる場合には、ノード５にＧｅｔ要求を発行する。
【００２５】
また、クライアント７は、ＩＰ網８を介して、レプリカの更新要求を示すＰｕｔ要求を発行する場合には、レプリカごとに定められた所定のノードに発行する。つまり、クライアント７は、各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４を更新する際にｕｐｄａｔｅ要求が送信される経路における始端ノードに対してＰｕｔ要求を発行する。例えば、クライアント７は、レプリカＡ１〜Ａ４の更新を行う場合には、レプリカＡ１を記憶するノード２に対してＰｕｔ要求を発行する。
【００２６】
また、クライアント７は、レプリカＢ１〜Ｂ４の更新を行う場合には、レプリカＢ１を記憶するノード３に対してＰｕｔ要求を発行する。また、クライアント７は、レプリカＣ１〜Ｃ４の更新を行う場合には、レプリカＣ１を記憶するノード４に対してＰｕｔ要求を発行する。
【００２７】
各ノード２〜６は、経路の終端ノードである際にＧｅｔ要求をクライアント７から取得した場合には、Ｇｅｔ要求の対象となるレプリカのデータをクライアント７へ送信する。また、ノード２〜４は、経路の始端ノードである際にＰｕｔ要求を取得した場合は、自ストレージ装置を始端とし、更新対象となるレプリカを記憶するノードを直列に接続する複数の経路に沿って、レプリカの更新を要求するｕｐｄａｔｅ要求を、各経路の終端となるノードに送信する。
【００２８】
例えば、ノード２は、クライアント７からレプリカＡに関わるＰｕｔ要求を取得した場合には、以下の処理を実行する。すなわち、ノード２は、更新に関わるレプリカＡを記憶する複数のノード３〜５を識別する。そして、ノード２は、ｕｐｄａｔｅ要求を送信する複数の経路を識別する。例えば、ノード２は、ｕｐｄａｔｅ要求を送信する経路として、ノード２、ノード３、ノード５を辿る経路と、ノード２、ノード４、ノード５を辿る経路を識別する。
【００２９】
そして、ノード２は、ヘッダにｕｐｄａｔｅ要求を転送する経路を示す経路情報を埋め込んだｕｐｄａｔｅ要求をノード３およびノード４に転送する。このような場合には、ノード３は、レプリカＡ２の更新準備を行うとともに、ｕｐｄａｔｅ要求のヘッダに埋め込まれた経路情報を参照し、ｕｐｄａｔｅ要求の転送先としてノード５を識別する。そして、ノード３は、ｕｐｄａｔｅ要求をノード５に転送する。
【００３０】
また、ノード４は、ｕｐｄａｔｅ要求を受信した場合には、レプリカＡ３の更新準備を行うとともに、ｕｐｄａｔｅ要求のヘッダに埋め込まれた経路情報を参照し、ｕｐｄａｔｅ要求の転送先としてノード５を識別する。そして、ノード４は、ｕｐｄａｔｅ要求をノード５に転送する。
【００３１】
また、ノード５は、ノード３またはノード４からｕｐｄａｔｅ要求を取得した場合には、経路情報を参照し、自身が複数の経路において終端となるノードであると判別する。このような場合には、ノード５は、ｕｐｄａｔｅ要求が転送される全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する。
【００３２】
そして、ノード５は、全ての経路を介してｕｐｄａｔｅ要求を受信した場合、すなわち、ノード３およびノード４からｕｐｄａｔｅ要求を受信した場合には、レプリカＡ４の更新を行うとともに、ｕｐｄａｔｅ要求に対する応答であるｕｐｄａｔｅｄ要求をノード３およびノード４に送信する。
【００３３】
また、ノード３およびノード４は、ノード５からｕｐｄａｔｅｄ要求を受信した場合には、レプリカＡ２およびレプリカＡ３の更新を行うとともに、ノード２へｕｐｄａｔｅｄ要求を転送する。また、ノード２は、ノード３またはノード４のいずれかからｕｐｄａｔｅｄ要求を取得した場合には、レプリカＡ１の更新を行うとともに、クライアント７に更新が終了した旨の通知を送信する。
【００３４】
このような処理を実行することで、ノード２〜５は、読み出されるデータの同一性が保証されるＳｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持することができる。また、ノード２〜５は、データＡのレプリカを記憶する全てのノードに対して、複数の経路を介してｕｐｄａｔｅ要求を行き渡らせるので、レプリカの更新に要する時間を短縮することができる。
【００３５】
なお、ノード２〜６は、レプリカＢ１〜Ｂ４およびレプリカＣ１〜Ｃ４についても同様の処理を実行する。このため、ストレージシステム１は、各レプリカの更新に要する時間を短縮することができる。
【００３６】
次に、各ノード２〜６について説明する。まず、図３を用いて、ノード２が複数の経路の始端となる始端ノード、および、ある経路においてｕｐｄａｔｅ要求を転送する中間ノードとして動作する例について説明する。なお、他のノード３〜６についても図２に示す各部を有するものとする。すなわち、各ノード２〜６は、記憶するレプリカや、ストレージシステム１の設定に応じて、クライアント７からＰｕｔ要求を受付ける始端ノードとして動作することができる。
【００３７】
図３は、実施例１に関わる始端ノードの一例を説明するための図である。図３に示す例では、始端ノードとして動作するノード２は、ネットワークインターフェース１０、要求送信元判断部１１、クライアント要求受信部１２、クライアント要求処理部１３、ノード間要求受信部１４、ノード間要求処理部１５を有する。また、ノード２は、データ記憶部１６、要求発行部１７、要求発行認証部１８、クライアント位置記憶部１９、トポロジー計算部２０、ノード間要求並列送信部２１、クライアント位置判断部２２、クライアント要求送信部２３を有する。
【００３８】
以下、ノード２が有する各部１０〜２３について説明する。まず、ノード２が有するデータ記憶部１６について説明する。データ記憶部１６は、レプリカのデータや、他のノードの設置位置等を記憶する記憶部である。例えば、データ記憶部１６は、ノード２がデータＡのレプリカＡ１〜Ａ４を更新する際に始端ノードとなる場合には、各レプリカＡ１〜Ａ４を記憶するノードを示す情報を記憶する。また、データ記憶部１６は、各ノード２〜６が設置された位置を示す位置情報を記憶する。
【００３９】
図４ａは、実施例１に関わるデータ記憶部が記憶する位置情報の一例を説明するための図である。図４ａに示す例では、データ記憶部１６は、ノード２がデータセンター＃１のラックＲ１に設置されている旨を示す位置情報と、ノード３がデータセンター＃１のラックＲ２に設置されている旨を示す位置情報とを記憶する。
【００４０】
また、データ記憶部１６は、ノード４がデータセンター＃２のラックＲ３に設置されている旨を示す位置情報と、ノード５がデータセンター＃２のラックＲ４に設置されている旨を示す位置情報とを記憶する。また、データ記憶部１６は、ノード６がデータセンター＃３のラックＲ５に設置されている旨を示す位置情報を記憶する。
【００４１】
図４ｂは、実施例１に関わるデータ記憶部が記憶する各レプリカＡ１〜Ａ４を記憶するノードを示す情報の一例を説明するための図である。図４ｂに示す例では、データ記憶部１６は、レプリカＡ１がノード２に、レプリカＡ２がノード３に、レプリカＡ３がノード４に、レプリカＡ４がノード５に記憶されている旨を示す情報を記憶する。
【００４２】
以下に示すように、ノード２は、始端ノードとして動作する場合には、データ記憶部１６が記憶する各情報を用いて、ｕｐｄａｔｅ要求を行き渡らせるノードと、ｕｐｄａｔｅ要求を転送する複数の経路とを識別する。そして、ノード２は、識別した複数の経路において自身と隣接するノードに対してｕｐｄａｔｅ要求を送信する。
【００４３】
図３に戻って、クライアント位置記憶部１９は、ノード２に対してＰｕｔ要求やＧｅｔ要求を発行したクライアントを示す情報を記憶する記憶部である。例えば、クライアント位置記憶部１９は、ノード２に対してＰｕｔ要求を発行したクライアント７のＩＰアドレス等を記憶する。
【００４４】
ネットワークインターフェース１０は、ＩＰ網８を介して、クライアント７が発行するＰｕｔ要求、および、他のノード３〜６が送信したｕｐｄａｔｅ要求やｕｐｄａｔｅｄ要求を受信する。このような場合には、ネットワークインターフェース１０は、受信したＰｕｔ要求、ｕｐｄａｔｅ要求、および、ｕｐｄａｔｅｄ要求を要求送信元判断部１１に出力する。
【００４５】
また、ネットワークインターフェース１０は、ノード間要求並列送信部２１からｕｐｄａｔｅ要求やｕｐｄａｔｅｄ要求を取得した場合には、取得したｕｐｄａｔｅ要求やｕｐｄａｔｅｄ要求を他のノード３〜６に送信する。また、ネットワークインターフェース１０は、クライアント要求送信部２３からレプリカのデータや更新処理が終了した旨の通知を取得した場合には、取得したデータや通知をクライアント７に送信する。
【００４６】
要求送信元判断部１１は、ネットワークインターフェース１０が取得した各要求を取得した場合には、取得した要求がＰｕｔ要求であるか否かを判別する。そして、要求送信元判断部１１は、取得した要求がＰｕｔ要求である場合には、取得したＰｕｔ要求をクライアント要求受信部１２に出力する。一方、要求送信元判断部１１は、取得した要求がＰｕｔ要求ではない場合には、すなわち、取得した要求がｕｐｄａｔｅ要求またはｕｐｄａｔｅｄ要求である場合には、取得した要求をノード間要求受信部１４に出力する。
【００４７】
クライアント要求受信部１２は、要求送信元判断部１１からＰｕｔ要求を取得した場合には、取得したＰｕｔ要求を発行したクライアント７を識別する。そして、クライアント要求受信部１２は、識別したクライアント７の位置情報をクライアント位置記憶部１９に格納する。また、クライアント要求受信部１２は、クライアント要求処理部１３に対して、取得したＰｕｔ要求を出力する。ここで、クライアント７の位置情報の例としては、クライアント７のＩＰアドレス等、クライアント７を一意に示す番号である。
【００４８】
クライアント要求処理部１３は、クライアント要求受信部１２から取得したＰｕｔ要求に対する処理を実行する。例えば、クライアント要求処理部１３は、クライアント要求受信部１２からＰｕｔ要求を取得した場合には、Ｐｕｔ要求の対象となるレプリカのデータをデータ記憶部１６から検索する。
【００４９】
そして、クライアント要求処理部１３は、検出したレプリカのデータをＰｕｔ要求に従って更新した更新後のデータを新たに生成し、更新後のデータを更新前のデータとは別にデータ記憶部１６に格納する。また、クライアント要求処理部１３は、ｕｐｄａｔｅ要求の発行を要求発行部１７に指示する。
【００５０】
ノード間要求受信部１４は、要求送信元判断部１１からｕｐｄａｔｅ要求を取得した場合には、ｕｐｄａｔｅ要求をノード間要求処理部１５に出力する。また、ノード間要求受信部１４は、要求送信元判断部１１からｕｐｄａｔｅｄ要求を取得した場合には、ｕｐｄａｔｅｄ要求をノード間要求処理部１５に出力する。
【００５１】
ノード間要求処理部１５は、ノード間要求受信部１４からｕｐｄａｔｅ要求を取得した場合には、以下の処理を実行する。まず、ノード間要求処理部１５は、更新対象となるレプリカをデータ記憶部１６から検索し、検索したレプリカのデータを更新した更新後のデータを生成する。そして、ノード間要求処理部１５は、更新後のデータを更新前のデータとともにデータ記憶部１６に格納する。また、ノード間要求処理部１５は、ノード間要求受信部１４が出力したｕｐｄａｔｅ要求を要求発行部１７に出力するとともに、ｕｐｄａｔｅ要求の転送処理の実行を指示する。
【００５２】
また、ノード間要求処理部１５は、ノード間要求受信部１４からｕｐｄａｔｅｄ要求を取得した場合には、以下の処理を実行する。まず、ノード間要求処理部１５は、クライアント要求処理部１３が更新前のレプリカのデータをデータ記憶部１６から削除する。次に、ノード間要求処理部１５は、ノード間要求受信部１４が受信したｕｐｄａｔｅｄ要求が、ノード２が発行したｕｐｄａｔｅ要求に対する応答として発行されたｕｐｄａｔｅｄ要求であるか否かを判別する。
【００５３】
そして、ノード間要求処理部１５は、ノード間要求受信部１４が取得したｕｐｄａｔｅｄ要求が、ノード２が始端ノードとして発行したｕｐｄａｔｅ要求に対する応答として発行されたｕｐｄａｔｅｄ要求であると判別した場合には、以下の処理を実行する。すなわち、ノード間要求処理部１５は、Ｐｕｔ要求が完了した旨を通知するＰｕｔ返答を発行するよう要求発行部１７に指示する。なお、ノード２が始端ノードである場合には、複数の経路を介して複数のｕｐｄａｔｅｄ要求を受信することとなるが、ノード間要求処理部１５は、最初にｕｐｄａｔｅｄ要求をノード２が受信した時点で、更新前のレプリカのデータを削除する。
【００５４】
一方、ノード間要求処理部１５は、ノード間要求受信部１４が取得したｕｐｄａｔｅｄ要求が、ノード２が始端ノードとして発行したｕｐｄａｔｅｄ要求に対応するｕｐｄａｔｅｄ要求ではないと判別した場合には、以下の処理を実行する。すなわち、ノード間要求処理部１５は、ノード間要求処理部１５が更新する前のレプリカのデータをデータ記憶部１６から削除する。そして、ノード間要求処理部１５は、ノード間要求受信部１４が出力したｕｐｄａｔｅｄ要求を要求発行部１７に出力するとともに、ｕｐｄａｔｅｄ要求の転送を行うよう指示する。
【００５５】
要求発行部１７は、クライアント要求処理部１３からｕｐｄａｔｅ要求の発行を指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、データ記憶部１６を参照し、ｕｐｄａｔｅ要求を送信するノード、すなわち、更新対象となるレプリカを記憶するノードを識別する。また、要求発行部１７は、判別したノードの位置情報をデータ記憶部１６から取得する。そして、要求発行部１７は、ｕｐｄａｔｅ要求を生成し、生成したｕｐｄａｔｅ要求を送信するようトポロジー計算部２０に指示する。この際、要求発行部１７は、取得したノードの位置情報をトポロジー計算部２０に送信する。
【００５６】
また、要求発行部１７は、ノード間要求処理部１５からｕｐｄａｔｅ要求の転送処理の実行を指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、ノード間要求処理部１５が出力したｕｐｄａｔｅ要求をトポロジー計算部２０に出力するとともに、ｕｐｄａｔｅ要求を転送するよう指示する。
【００５７】
また、要求発行部１７は、ノード間要求処理部１５からｕｐｄａｔｅｄ要求の転送処理の実行を指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、ノード間要求処理部１５が出力したｕｐｄａｔｅｄ要求をトポロジー計算部２０に出力するとともに、ｕｐｄａｔｅｄ要求を転送するように指示する。
【００５８】
また、要求発行部１７は、ノード間要求処理部１５からＰｕｔ返答を発行するよう指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、要求発行認証部１８にＰｕｔ返答を発行すべきか否かを判別するよう指示する。
【００５９】
そして、要求発行部１７は、要求発行認証部１８からＰｕｔ返答を発行すべきである旨の通知を受けた場合には、Ｐｕｔ返答を生成し、生成したＰｕｔ返答を発行するようクライアント位置判断部２２に指示する。一方、要求発行部１７は、要求発行認証部１８からＰｕｔ返答を発行すべきではない旨の通知を受けた場合には、処理を終了する。
【００６０】
要求発行認証部１８は、要求発行部１７からＰｕｔ返答を発行すべきか否かを判別するよう指示された場合には、以下の処理を実行する。すなわち、要求発行認証部１８は、要求発行部１７が同一のＰｕｔ返答を発行した旨を記憶しているか否かを判別する。
【００６１】
そして、要求発行認証部１８は、同一のＰｕｔ返答を発行した旨を記憶していない場合には、Ｐｕｔ返答を発行すべき旨を要求発行部１７に通知するとともに、このＰｕｔ返答を発行した旨を記憶する。一方、要求発行認証部１８は、同一のＰｕｔ返答を発行した旨を記憶している場合には、Ｐｕｔ返答を発行すべきでない旨を要求発行部１７に通知する。
【００６２】
トポロジー計算部２０は、ｕｐｄａｔｅ要求を送信するよう指示された場合には、以下の処理を実行する。まず、トポロジー計算部２０は、要求発行部１７からノードの位置情報を取得する。そして、トポロジー計算部２０は、取得したノードの位置情報を用いて、ｕｐｄａｔｅ要求を転送する複数の経路を識別する。
【００６３】
この際、トポロジー計算部２０は、相互に設置位置が近いノードを同じ経路とする複数の経路を識別する。また、トポロジー計算部２０は、各経路の終端ノードが同一のノードとなる複数の経路を識別する。そして、トポロジー計算部２０は、識別した複数の経路を示す経路情報をｕｐｄａｔｅ要求のヘッダに格納し、経路情報を格納したｕｐｄａｔｅ要求をノード間要求並列送信部２１に出力するとともに、ｕｐｄａｔｅ要求を送信するよう指示する。
【００６４】
例えば、ノード２がクライアント７からデータＡのレプリカＡ１〜Ａ４に関わるＰｕｔ要求を受付けた場合には、トポロジー計算部２０は、要求発行部１７からｕｄａｔｅ要求を取得するとともに、図４ａに例示する各ノード２〜５の位置情報を取得する。このような場合には、ノード２は、データセンター＃１にノード２、ノード３が設置され、データセンター＃２にノード４、ノード５が設置されていると判別する。
【００６５】
このように各ノード２〜５が設置されている際に、データセンターをまたぐ経路では、ｕｐｄａｔｅ要求を送信する際のレイテンシが増大してしまう。このため、トポロジー計算部２０は、可能な限りデータセンターをまたがない経路を識別する。また、トポロジー計算部２０は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙの保持を容易にするため、各経路の終端ノードを同一のノードとする。
【００６６】
すなわち、ｕｐｄｅｔｅ要求を転送する経路の終端ノードが複数存在する場合には、ｕｐｄａｔｅ要求を取得し、ｕｐｄａｔｅｄ要求を取得するまでの間にＧｅｔ要求を取得すると、問合せ先とする終端ノードを選択するアルゴリズムが複雑となってしまう。そこで、トポロジー計算部２０は、各経路の終端ノードを同一のノードとする。
【００６７】
例えば、図４ａに示すように、各ノード２〜６が設置され、各ノード２〜５がレプリカＡ１〜Ａ４を記憶している際に、クライアント７がデータＡに関わるＰｕｔ要求を発行した場合には、トポロジー計算部２０は、以下のような複数の経路を識別する。すなわち、トポロジー計算部２０は、ノード２を始端ノードとし、ノード３を経由してノード５を終端ノードとする経路、および、ノード２を始端ノードとし、ノード４を経由してノード５を終端ノードとする経路を識別する。
【００６８】
また、トポロジー計算部２０は、要求発行部１７からｕｐｄａｔｅ要求を取得するとともに、ｕｐｄａｔｅ要求を転送するよう指示された場合には、以下の処理を実行する。すなわち、トポロジー計算部２０は、ｕｐｄａｔｅ要求をノード間要求並列送信部２１に出力するとともに、ｕｐｄａｔｅ要求を転送するようノード間要求並列送信部２１に指示する。
【００６９】
また、トポロジー計算部２０は、要求発行部１７からｕｐｄａｔｅｄ要求を取得するとともに、ｕｐｄａｔｅｄ要求を転送するよう指示された場合には、以下の処理を実行する。すなわち、トポロジー計算部２０は、ｕｐｄａｔｅｄ要求をノード間要求並列送信部２１に出力するとともに、ｕｐｄａｔｅｄ要求を転送するようノード間要求並列送信部２１に指示する。
【００７０】
ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求をトポロジー計算部２０から取得するとともに、ｕｐｄａｔｅｄ要求を送信するよう指示された場合には、以下の処理を実行する。すなわち、ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求に格納された経路情報が示す複数の経路において、始端ノードであるノード２の次にｕｐｄａｔｅ要求が送信される複数のノードを識別する。そして、ノード間要求並列送信部２１は、ネットワークインターフェース１０およびＩＰ網８を介して、識別した複数のノードにｕｐｄａｔｅ要求を送信する。
【００７１】
例えば、ノード間要求並列送信部２１は、経路情報を解析し、ノード２を始端ノードとし、ノード３を経由してノード５を終端ノードとする経路を識別する。また、ノード間要求並列送信部２１は、ノード２を始端ノードとし、ノード４を経由してノード５を終端ノードとする経路を識別する。このような場合には、ノード間要求並列送信部２１は、ノード３およびノード４にｕｐｄａｔｅ要求を送信する。
【００７２】
また、ノード間要求並列送信部２１は、ｕｐａｄｔｅ要求を取得するとともにｕｐｄａｔｅ要求を転送する旨の指示を受付けた場合には、以下の処理を実行する。まず、ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求に格納された経路情報を解析し、ノード２の次にｕｐｄａｔｅ要求を転送すべきノードを識別する。そして、ノード間要求並列送信部２１は、ネットワークインターフェース１０を介して、識別したノードにｕｐｄａｔｅｄ要求を転送する。
【００７３】
また、ノード間要求並列送信部２１は、ｕｐａｄｔｅｄ要求を取得するとともにｕｐｄａｔｅｄ要求を転送する旨の指示を受付けた場合には、以下の処理を実行する。まず、後述するように、ｕｐｄａｔｅｄ要求を転送する経路を示す経路情報が格納されているので、ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求に格納された経路情報を解析し、ノード２の次にｕｐｄａｔｅｄ要求を転送すべきノードを識別する。そして、ノード間要求並列送信部２１は、ネットワークインターフェース１０を介して、識別したノードにｕｐｄａｔｅｄ要求を転送する。
【００７４】
クライアント位置判断部２２は、要求発行部１７からレプリカのデータを取得するとともに、クライアント７に送信するよう指示された場合には、以下の処理を実行する。すなわち、クライアント位置判断部２２は、クライアント位置記憶部１９からクライアント７の位置情報、例えば、クライアント７のＩＰアドレスを取得する。そして、クライアント位置判断部２２は、レプリカのデータとクライアント７の位置情報とをクライアント要求送信部２３に出力する。
【００７５】
また、クライアント位置判断部２２は、要求発行部１７からＰｕｔ返答を発行する旨を指示された場合には、以下の処理を実行する。すなわち、クライアント位置判断部２２は、クライアント位置記憶部１９からＰｕｔ返答の発行先となるクライアントの位置情報を取得する。そして、クライアント位置判断部２２は、クライアントの位置情報とＰｕｔ返答とをクライアント要求送信部２３に出力する。
【００７６】
また、クライアント要求送信部２３は、クライアント位置判断部からＰｕｔ返答とクライアントの位置情報とを取得した場合には、ネットワークインターフェース１０およびＩＰ網８を介して、Ｐｕｔ返答をクライアントに送信する。例えば、クライアント要求送信部２３は、クライアント７の位置情報とＰｕｔ返答とを取得した場合には、クライアント７にＰｕｔ応答を送信する。
【００７７】
次に、図５を用いて、クライアント７が発行したＰｕｔ要求を取得した際に始端ノードとなるノード２が実行する処理の一例について説明する。図５は、実施例１に関わる始端ノードがｕｐｄａｔｅ要求を発行する処理の一例を説明するための図である。なお、図５に示す例では、クライアント７は、データＡの複製であるレプリカＡ１〜Ａ４を更新対象とするＰｕｔ要求を発行したものとする。
【００７８】
例えば、図５に示す例では、ノード２は、図５中（１）に示すように、Ｐｕｔ要求を取得する。このような場合には、要求送信元判断部１１は、図５中（２）に示すように、Ｐｕｔ要求をクライアント要求受信部１２に出力する。クライアント要求受信部１２は、図５中（３）に示すように、クライアント７の位置情報をクライアント位置記憶部１９に格納するとともに、図５中（４）に示すように、クライアント要求処理部１３にＰｕｔ要求を出力する。
【００７９】
このような場合には、クライアント要求処理部１３は、データ記憶部１６に記憶されたレプリカＡ１の更新後のデータを生成するとともに、要求発行部１７にレプリカＡ１〜Ａ４の更新を要求するｕｐｄａｔｅ要求の発行を指示する。すると、要求発行部１７は、図５中（５）に示すように、データ記憶部１６からレプリカＡ１〜Ａ４を記憶する各ノード２〜５の位置情報を取得し、図５中（６）に示すように、トポロジー計算部２０にｕｐｄａｔｅ要求と各ノード２〜５の位置情報を送信する。
【００８０】
このような場合には、トポロジー計算部２０は、位置情報に基づいて、各ノード２〜５にｕｐｄａｔｅ要求を行き渡らせるための複数の経路を識別する。そして、トポロジー計算部２０は、図５中（７）に示すように、識別した複数の経路を示す経路情報を格納したｕｐａｔｅ要求をノード間要求並列送信部２１に出力する。すると、図５中（８）に示すように、ノード間要求並列送信部２１は、経路情報が示す次のノードにｕｐｄａｔｅ要求を送信する。
【００８１】
次に、図６を用いて、ｕｐｄａｔｅｄ要求を取得した際に始端ノードとなるノード２が実行する処理の一例について説明する。図６は、実施例１に関わる始端ノードがｕｐｄａｔｅｄ要求を受信した際に実行する処理の一例を説明するための図である。例えば、図６中（１）に示すように、ｕｐｄａｔｅｄ要求を取得した場合には、要求送信元判断部１１は、図６中（２）に示すように、ｕｐｄａｔｅｄ要求をノード間要求受信部１４に出力する。このような場合には、ノード間要求受信部１４は、図６中（３）に示すように、ｕｐｄａｔｅｄ要求をノード間要求処理部１５に出力する。
【００８２】
すると、ノード間要求処理部１５は、図６中（４）に示すように、更新前のレプリカＡ１をデータ記憶部１６から削除するとともに、要求発行部１７にＰｕｔ返答を出力する旨を指示する。このような場合には、図６中（５）に示すように、要求発行部１７は、Ｐｕｔ返答を出力すべきか否かを要求発行認証部１８に判別させる。そして、要求発行部１７は、Ｐｕｔ返答を出力すべき旨を取得した場合には、図６中（６）に示すように、Ｐｕｔ返答を出力するようクライアント位置判断部２２に指示する。
【００８３】
すると、クライアント位置判断部２２は、クライアント位置記憶部１９からＰｕｔ応答の送信先となるクライアント７の位置情報を取得し、図６中（７）に示すように、Ｐｕｔ応答と取得した位置情報とをクライアント要求送信部２３に出力する。このような場合には、クライアント要求送信部２３は、図６中（８）に示すように、ネットワークインターフェース１０およびＩＰ網８を介して、クライアント７にＰｕｔ返答を送信する。
【００８４】
次に、図７を用いて、終端ノードとして動作するノード５が実行する処理について説明する。図７は、実施例１に関わる終端ノードの一例を説明するための図である。なお、図３に示した各部１０〜２３と同様の機能を発揮するものについては、同一の符号を付し、以下の説明を省略する。また、他のノード２〜４、ノード６についても図７に示す各部を有するものとする。すなわち、各ノード２〜６は、記憶するレプリカや、ストレージシステム１の設定に応じて、終端ノードとして動作することができる。
【００８５】
なお、図７に示す例では、終端ノードとして動作するノード５は、ノード間要求受信部１４とノード間要求処理部１５ａとの間に要求収集部２４を有する。このため、ノード間要求受信部１４は、ノード５がノード３、４から受信するｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求をノード間要求処理部１５ａではなく要求収集部２４に出力することとなる。
【００８６】
ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、クライアント要求受信部１２ａ、クライアント要求処理部１３ａは、図３に示す各部１０〜１３と同様の機能を発揮する。また、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、クライアント要求受信部１２ａは、クライアント７からＧｅｔ要求を受信した場合には、受信したＧｅｔ要求をクライアント要求処理部１３ａに伝達する。
【００８７】
クライアント要求処理部１３ａは、Ｇｅｔ要求取得した場合にはデータ記憶部１６からＧｅｔ要求の対象となるレプリカのデータを検索する。そして、クライアント要求は、検索したレプリカのデータを要求発行部１７ａに出力するとともに、データをクライアントに送信するよう指示する。
【００８８】
このような場合には、要求処理部１３ａは、クライアント位置判断部２２を介して、クライアント要求送信部２３に、取得したデータをクライアント７に送信するよう指示する。その後、クライアント要求送信部２３は、クライアント７にデータを送信する。
【００８９】
要求収集部２４は、ノード間要求受信部１４からｕｐｄａｔｅ要求を取得した場合には、取得したｕｐｄａｔｅ要求に格納された経路情報を解析し、経路情報が示す経路においてノード５が終端ノードとなるか否かを判別する。そして、要求収集部２４は、経路情報が示す経路においてノード５が終端ノードとなる場合には、取得したｕｐｄａｔｅ要求を保持する。
【００９０】
また、要求収集部２４は、保持したｕｐｄａｔｅ要求の経路情報を解析し、同一のレプリカを更新対象とするｕｐｄａｔｅ要求を、経路情報が示す全ての経路の数だけ保持したか否かを判別する。すなわち、要求収集部２４は、全ての経路を介して転送されたｕｐｄａｔｅ要求をノード５が受信したか否かを判別する。
【００９１】
そして、要求収集部２４は、同一のレプリカを更新対象とするｕｐｄａｔｅ要求を、経路情報が示す全ての経路の数だけ保持したと判別した場合には、いずれか１つのｕｐｄａｔｅ要求をノード間要求処理部１５ａに出力する。また、要求収集部２４は、同一のレプリカを更新対象とするｕｐｄａｔｅ要求を、経路情報が示す全ての経路の数だけ保持していないと判別した場合には、残りのｕｐｄａｔｅ要求を取得するまで待機する。
【００９２】
また、要求収集部２４は、経路情報が示す経路においてノード５が終端ノードとはならない場合には、取得したｕｐｄａｔｅ要求うちの１つをノード間要求処理部１５ａに出力するとともに、ｕｐｄａｔｅｄ要求の発行を指示する。また、要求収集部２４は、ノード間要求受信部１４からｕｐｄａｔｅｄ要求を取得した場合には、取得したｕｐｄａｔｅｄ要求をノード間要求処理部１５ａに出力する。
【００９３】
ノード間要求処理部１５ａは、図３に示すノード間要求処理部１５と同様の処理を実行する。さらに、ノード間要求処理部１５ａは、要求収集部２４からｕｐｄａｔｅ要求を取得するとともに、ｕｐｄａｔｅｄ要求の発行を指示された場合には、以下の処理を実行する。
【００９４】
すなわち、ノード間要求処理部１５ａは、データ記憶部１６に格納されたｕｐｄａｔｅ要求の対象となるレプリカのデータを検索し、検索したデータを更新した更新後のレプリカのデータのみをデータ記憶部１６に格納する。また、ノード間要求処理部１５ａは、要求発行部１７ａに対して、ｕｐｄａｔｅｄ要求の発行を指示するとともに、ｕｐｄａｔｅ要求に格納されていた経路情報を出力する。
【００９５】
要求発行部１７ａは、図３に示す要求発行部１７と同様の機能を発揮するとともに、ノード間要求処理部１５ａからｕｐｄａｔｅｄ要求の発行を指示された場合には、ｕｐｄａｔｅｄ要求を生成する。そして、要求発行部１７ａは、トポロジー計算部２０ａに生成したｕｐｄａｔｅｄ要求と、ノード間要求処理部１５ａから取得した経路情報を出力する。
【００９６】
トポロジー計算部２０ａは、図３に示すトポロジー計算部２０と同様の機能を発揮するとともに、要求発行部１７ａからｕｐｄａｔｅｄ要求と経路情報とを取得した場合には、以下の処理を実行する。すなわち、トポロジー計算部２０ａは、取得した経路情報が示す複数の経路を逆に辿る新たな経路情報を生成する。そして、トポロジー計算部２０ａは、取得したｕｐｄａｔｅｄ要求のヘッダに新たな経路情報を格納し、ｕｐｄａｔｅｄ要求をノード間要求並列送信部２１に出力する。
【００９７】
このように、ノード２は、自身を始端ノードとする複数の経路を識別し、識別した経路において自身と隣接する複数のノードに対してｕｐｄａｔｅ要求を送信することで、ｕｐｄａｔｅ要求を各ノード２〜５に送信する。このため、ノード２は、複数の経路を介して、各経路上のノードにｕｐｄａｔｅ要求を並行して送信するので、レプリカの更新に要する時間を短縮することができる。
【００９８】
また、ノード５は、自身を終端ノードとするｕｐｄａｔｅ要求を、全ての経路から受信するのを待機する。そして、ノード５は、自身を終端ノードとするｕｐｄａｔｅ要求を全ての経路から受信した場合には、ｕｐｄａｔｅｄ要求を全ての経路を介して始端ノードに送信する。このため、ストレージシステム１は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持しつつ、レプリカの更新に要する時間を短縮することができる。
【００９９】
次に、図８を用いて、終端ノードであるノード５が実行する処理の一例を説明する。図８は、実施例１に関わる終端ノードが実行する処理の一例を説明するための図である。例えば、図８中（１）に示すように、ネットワークインターフェース１０ａは、他のノード２〜６からｕｐｄａｔｅ要求を受信した場合には、受信したｕｐｄａｔｅ要求を要求送信元判断部１１に出力する。
【０１００】
また、要求送信元判断部１１ａは、図８中（２）に示すように、ｕｐｄａｔｅ要求をノード間要求受信部１４に出力する。また、ノード間要求受信部１４は、図８中（３）に示すように、ｕｐｄａｔｅ要求を要求収集部２４に出力する。このような場合には、要求収集部２４は、ｕｐｄａｔｅ要求の経路情報が示す全ての経路を介して、同一のレプリカを対象とするｕｐｄａｔｅ要求を取得したか否かを判別する。そして、要求収集部２４は、全ての経路を介して、同一のレプリカを対象とするｕｐｄａｔｅ要求を取得したと判別した場合には、図８中（４）に示すように、ｕｐｄａｔｅ要求をノード間要求処置部１５ａに送信する。
【０１０１】
すると、ノード間要求処理部１５ａは、データ記憶部１６に記憶されたレプリカを更新するとともに、図８中（５）に示すように、要求発行部１７ａにｕｐｄａｔｅｄ要求を発行する旨を指示する。すると、要求発行部１７ａは、ｕｐｄａｔｅｄ要求を生成し、図８中（６）に示すように、ｕｐｄａｔｅｄ要求を送信するようトポロジー計算部２０ａに指示する。
【０１０２】
このような場合には、トポロジー計算部２０ａは、ｕｐｄａｔｅ要求に格納された経路情報が示す全ての経路を逆に辿る経路を示す新たな経路情報を識別し、新たな経路情報をｕｐｄａｔｅｄ要求のヘッダに格納する。そして、トポロジー計算部２０ａは、図８中（７）に示すように、ノード間要求並列送信部２１にｕｐｄａｔｅｄ要求の送信を指示する。このような場合には、ノード間要求並列送信部２１は、図８中（８）に示すように、ネットワークインターフェース１０ａを介して、ｕｐｄａｔｅｄ要求を送信する。
【０１０３】
次に、図９ａ、図９ｂを用いて、実施例１に関わるストレージシステム１が、複数の経路を介して、ｕｐｄａｔｅ要求を始端ノードから終端ノードにまで順次転送し、ｕｐｄａｔｅｄ要求を終端ノードから始端ノードまで順次転送する処理について説明する。
【０１０４】
図９ａは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。また、図９ｂは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。なお、図９ａ、図９ｂに示す例では、１ｓｔノードから７ｔｈノードまでの７個のノードが記憶するレプリカの更新を行う例について説明する。
【０１０５】
例えば、クライアント７は、図９ａ中（Ｄ）に示すように、Ｐｕｔ要求を１ｓｔノードに発行する。このような場合には、１ｓｔノードは、Ｐｕｔ要求の対象となるレプリカを記憶する全てのノード、すなわち、１ｓｔノードから７ｔｈノードを識別する。
【０１０６】
そして、図９ａに示す例では、１ｓｔノードは、自身を始端ノードとし、７ｔｈノードを終端とする３つの経路を識別する。詳細には、１ｓｔノードは、１ｓｔノード、２ｎｄノード、５ｔｈノード、７ｔｈノードを接続する経路、１ｓｔノード、３ｒｄノード、７ｔｈノードを接続する経路、１ｓｔノード、４ｔｈノード、６ｔｈノードを接続する経路を識別する。
【０１０７】
そして、１ｓｔノードは、図９ａ中（Ｅ）に示すように、ｕｐｄａｔｅ要求を２ｎｄノード、３ｒｄノード、４ｔｈノードに送信する。このような場合には、２ｎｄノードはｕｐｄａｔｅ要求を５ｔｈノードに転送し、５ｔｈノードはｕｐｄａｔｅ要求を７ｔｈノードに転送する。また、３ｒｄノードは、ｕｐｄａｔｅ要求を７ｔｈノードに転送する。また、４ｔｈノードは、ｕｐｄａｔｅ要求を６ｔｈノードに転送し、６ｔｈノードは、ｕｐｄａｔｅ要求を７ｔｈノードに転送する。
【０１０８】
ここで、７ｔｈノードは、図９ａに示す３つの全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機し、全ての経路を介してｕｐｄａｔｅ要求を受信したと判別した場合には、ｕｐｄａｔｅｄ要求を生成する。そして、図９ｂ中（Ｆ）に示すように、ｕｐｄａｔｅｄ要求を５ｔｈノード、３ｒｄノード、６ｔｈノードに送信する。このような場合には、２ｎｄノード〜６ｔｈノードは、各経路を逆に辿るようにｕｐｄａｔｅｄ要求を１ｓｔノードまで順次転送する。そして、１ｓｔノードは、いずれかの経路を介してｕｐｄａｔｅｄ要求を取得した場合には、図９ｂ中（Ｇ）に示すように、Ｐｕｔ応答をクライアント７に送信する。
【０１０９】
ここで、従来のストレージシステムは、１ｓｔノードから７ｔｈノードまで１つの経路を介して順次ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を順次転送するので、６回の転送を実行する。しかし、ストレージシステム１は、複数の経路を介してｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を順次転送するので、図９ａ、図９ｂに示す例では、最大で３回の転送でよい。このため、図９ａ、図９ｂに示す例では、ストレージシステム１は、従来の１／２の時間で更新処理を実行することができる。
【０１１０】
例えば、ネットワークインターフェース１０、１０ａ、要求送信元判断部１１、１１ａ、クライアント要求受信部１２、１２ａ、クライアント要求処理部１３、１３ａ、ノード間要求受信部１４、ノード間要求処理部１５、１５ａとは、電子回路である。また、要求発行部１７、１７ａ、要求発行認証部１８、クライアント位置記憶部１９、トポロジー計算部２０、２０ａ、ノード間要求並列送信部２１、クライアント位置判断部２２、クライアント要求送信部２３、要求収集部２４とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積回路、またはＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）などを適用する。
【０１１１】
また、データ記憶部１６とは、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（flash memory）などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。
【０１１２】
次に、図１０を用いて、始端ノードが実行する処理の流れの一例について説明する。図１０は、始端ノードが実行する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明ではノード２が始端ノードとして動作する際に実行する処理の一例について説明する。
【０１１３】
例えば、ノード２は、自身の状態に停止条件が発生しているか否かを判別する（ステップＳ１０１）。ここで、停止条件とは、例えば、Ｐｕｔ要求を受信してからＰｕｔ応答をまだ出力していない場合等に発生する条件である。そして、ノード２は、停止条件が発生していない場合は（ステップＳ１０１否定）、クライアント７からＰｕｔ要求を受信したか否かを判別する（ステップＳ１０２）。
【０１１４】
次に、ノード２は、クライアント７からＰｕｔ要求を受信した場合には（ステップＳ１０２肯定）、ｕｐｄａｔｅ要求を送信する複数の経路を識別するとともに、各経路における次のノードにｕｐｄａｔｅ要求を送信する（ステップＳ１０３）。なお、ノード２は、ｕｐｄａｔｅ要求を送信してからｕｐｄａｔｅｄ要求を受信するまでの間、ｕｐｄａｔｅｉｎｇ状態に移行する。
【０１１５】
次に、ノード２は、ｕｐｄａｔｅ要求を送信したいずれかのノードからｕｐｄａｔｅｄ要求を受信したか否かを判別し（ステップＳ１０４）、受信していない場合には（ステップＳ１０４否定）、ｕｐｄａｔｅｄ要求を受信するまで待機する（ステップＳ１０４）。そして、ノード２は、いずれかのノードからｕｐｄａｔｅｄ要求を受信した場合には（ステップＳ１０４肯定）、クライアントにＰｕｔ返答を送信し、ｕｐｄａｔｅｉｎｇ状態を解除する（ステップＳ１０５）。その後、ノード２は、停止条件が発生しているか否かを判別する（ステップＳ１０１）。
【０１１６】
また、ノード２は、クライアントからＰｕｔ要求を受信していない場合には（ステップＳ１０２否定）、再度停止条件が発生しているか否かを判別する（ステップＳ１０１）。また、ノード２は、停止条件が発生している場合には（ステップＳ１０１肯定）、停止条件が解消されるまで、処理を終了する。
【０１１７】
次に、図１１を用いて、各経路の中間ノードが実行する処理の流れの一例について説明する。図１１は、中間ノードが実行する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明では、ノード３が中間ノードとして動作する際に実行する処理の一例について説明する。
【０１１８】
例えば、ノード３は、停止条件が発生しているか否かを判別し（ステップＳ２０１）、発生していないと判別した場合には（ステップＳ２０１否定）、ｕｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ２０２）。そして、ノード３は、経路の前ノードからｕｐｄａｔｅ要求を受信した場合には（ステップＳ２０２肯定）、経路の次ノードにｕｐｄａｔｅ要求を転送し、ｕｐｄａｔｉｎｇ状態に遷移する（ステップＳ２０３）。
【０１１９】
次に、ノード３は、ｕｐｄａｔｅ要求を転送した次ノードからｕｐｄａｔｅｄ要求を受信するまで待機し（ステップＳ２０４否定）、ｕｐｄａｔｅｄ要求を受信した場合には（ステップＳ２０４肯定）、次の処理を実行する。すなわち、ノード３は、経路の前ノードにｕｐｄａｔｅｄ要求を転送し、ｕｐｄａｔｉｎｇ状態を解除する（ステップＳ２０５）。
【０１２０】
その後、ノード３は、再度停止条件が発生しているか否かを判別し（ステップＳ２０１）、停止条件が発生している場合には（ステップＳ２０１肯定）、停止条件が解消されるまで、処理を終了する。また、ノード３は、前ノードからｕｐｄａｔｅ要求を受信していない場合には（ステップＳ２０２否定）、再度停止条件が発生しているか否かを判別する（ステップＳ２０１）。
【０１２１】
次に、図１２を用いて、終端ノードが実行する処理の流れの一例について説明する。図１２は、終端ノードが実行する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明では、ノード５が終端ノードとして動作する際に実行する処理の一例について説明する。
【０１２２】
まず、ノード５は、停止条件が発生しているか否かを判別し（ステップＳ３０１）、発生していない場合には（ステップＳ３０１否定）、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ３０２）。そして、ノード５は、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信していない場合には（ステップＳ３０２否定）、全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する（ステップＳ３０２）。
【０１２３】
また、ノード５は、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信した場合には（ステップＳ３０２肯定）、レプリカを更新するとともに、各経路の前ノードにｕｐｄａｔｅｄ要求を送信する（ステップＳ３０３）。その後、ノード５は、再度、停止条件が発生しているか否かを判別し（ステップＳ３０１）、発生している場合には（ステップＳ３０１肯定）、停止条件が解消するまで処理を終了する。
【０１２４】
[ストレージシステム１の効果]
上述したように、ノード２は、クライアント７からレプリカＡ１〜Ａ４に対するＰｕｔ要求を受信した場合には、自身を始端とし、複数のノード２〜５を直列に接続する複数の経路を判別する。そして、ノード２は、識別した経路を介して、各経路の終端ノードであるノード５にｕｐｄａｔｅ要求を送信する。その後、ノード２は、いずれかの経路を介してｕｐｄａｔｅｄ要求を受信した場合には、クライアント７にＰｕｔ応答を送信する。
【０１２５】
このため、ノード２は、ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を複数の経路を介して各ノード２〜５に転送させるので、レプリカＡ１〜Ａ４の更新に要する時間を短縮することができる。
【０１２６】
また、ノード２は、各ノード２〜６の設置位置を記憶し、各ノード２〜６のうち、相互に設置位置が近い複数のストレージ装置を直列に接続する複数の経路を識別する。このため、ノード２は、各経路に含まれる複数のノードにｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を効率的に転送させることができる結果、各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４の更新に要する時間を短縮することができる。
【０１２７】
また、ノード２は、１つのノード５を終端ノードとする複数の経路を識別する。このため、ノード２は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを容易に保持することができる。
【０１２８】
また、ノード５は、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別し、全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する。そして、ノード５は、全ての経路を介してｕｐｄａｔｅ要求を受信した場合には、各経路を介して、ｕｐｄａｔｅｄ要求を始端ノードであるノード２に送信する。このため、ノード５は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保ちながら、複数の経路を介してｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を転送することができる。
【実施例２】
【０１２９】
次に、実施例２に関わるストレージシステムについて説明する。例えば、実施例１に関わるストレージシステム１は、１つのノードを終端ノードとする複数の経路を介して、ｕｐｄａｔｅ要求とｕｐｄａｔｅｄ要求とを順次転送した。しかし、実施例はこれに限定されるものではない。
【０１３０】
例えば、各経路における終端ノードを異なるノードとした際に、各経路においてｕｐｄａｔｅ要求とｕｐｄａｔｅｄ要求とを転送する回数を減少させられるのであれば、更新に要する時間をより短縮することができる。そこで、以下の説明においては、各経路における終端ノードを異なるノードとするストレージシステム１ａについて説明する。
【０１３１】
図１３は、実施例２に関わるストレージシステムの一例を説明するための図である。図１３に示す例では、ストレージシステム１ａは、ストレージシステム１と同様に各データセンター＃１〜＃３に複数のノード２ａ〜６ａを有する。なお、クライアント７およびＩＰ網８は、実施例１に関わるクライアント７およびＩＰ網８と同様の機能を発揮するものとして、説明を省略する。
【０１３２】
図１４は、実施例２に関わる始端ノードの一例を説明するための図である。なお、図１４に示す例では、始端ノードとして、ノード２ａの一例について説明する。また、他のノード３ａ〜６ａも、同様の機能を発揮できるものとする。また、図１４に示すノード２ａのうち、図３に示すノード２と同様の機能を発揮する部分については、同一の符号を付すものとし、以下の説明を省略する。
【０１３３】
トポロジー計算部２０ｂは、実施例１に関わるトポロジー計算部２０ａと同様の機能を発揮する。また、トポロジー計算部２０ｂは、各経路の終端ノードを異なるノードとした方が更新に要する時間をより短縮できる場合には、終端ノードをそれぞれ異なるノードとする複数の経路を識別する。
【０１３４】
そして、トポロジー計算部２０ｂは、識別した複数の経路を示す経路情報をｕｐｄａｔｅ要求に格納する。例えば、トポロジー計算部２０ｂは、ノード２ａを始端ノードとし、ノード３ａを終端ノードとする経路と、ノード２ａを始端ノードとし、ノード４ａを中間ノードとし、ノード５ａを終端ノードとする経路とを示す経路情報をｕｐｄａｔｅ要求に格納する。
【０１３５】
次に、図１５を用いて、実施例２に関わる終端ノードの一例を説明する。図１５は、実施例２に関わる終端ノードの一例を説明するための図である。なお、以下の説明においては、ノード３ａ、および、ノード５ａが終端ノードである例について説明する。また、他のノード２ａ、４ａ、６ａも、ノード３ａおよびノード５ａと同様の機能を発揮できるものとする。また、図１５に示すノード３ａおよび５ａのうち、図７に示すノード５と同様の機能を発揮する部分については、同一の符号を付すものとし、以下の説明を省略する。
【０１３６】
要求収集部２４ａは、要求収集部２４と同様の機能を有する。また、要求収集部２４ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信した場合は、ノード間要求処理部１５ｂにｕｐｄａｔｅ要求を出力せずに、以下の処理を実行する。
【０１３７】
すなわち、要求収集部２４ａは、ノード間要求処理部１５ｂに対して、ｕｐｄａｔｅ要求を受信した旨を通知するｒｅａｄｙＴｏＵｐｄａｔｅ要求を他の終端ノードに送信するよう指示する。この際、要求収集部２４ａは、ｕｐｄａｔｅ要求に格納されていた経路情報をノード間要求処理部１５ｂに通知する。
【０１３８】
また、要求収集部２４ａは、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、ノード間要求受信部１４を介して、他の終端ノードが発行したｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得する。そして、要求収集部２４ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したか否かを判別する。
【０１３９】
その後、要求収集部２４ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したと判別した場合には、取得したｕｐｄａｔｅ要求のうちの１つをノード間要求処理部１５ｂに出力する。一方、要求収集部２４ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得していないと判別した場合には、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得するまで待機する。
【０１４０】
つまり、要求収集部２４ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得した場合には、他の経路の終端ノードに対してｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。そして、要求収集部２４ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得し、かつ、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得した場合には、以下の処理を実行する。つまり、要求収集部２４ａは、自身を終端ノードとする全ての経路を介して、ｕｐｄａｔｅｄ要求を始端ノードに転送させる。
【０１４１】
ノード間要求処理部１５ｂは、図７に示すノード間要求処理部１５ａと同様の機能を発揮する。また、ノード間要求処理部１５ｂは、要求収集部２４ａから経路情報を取得するとともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示された場合には、以下の処理を実行する。すなわち、ノード間要求処理部１５ｂは、要求発行部１７ｂに経路情報を出力するとともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示する。
【０１４２】
また、ノード間要求処理部１５ｂは、データ記憶部１６に記憶された更新対象となるレプリカのデータを検索し、検索したデータを更新した更新後のデータを生成する。そして、ノード間要求処理部１５ｂは、更新前のレプリカのデータとともに、更新後のレプリカのデータをデータ記憶部１６に格納する。
【０１４３】
また、ノード間要求処理部１５ｂは、ｕｐｄａｔｅ要求を要求収集部２４ａから取得した場合には、データ記憶部１６に記憶された更新前のレプリカのデータを削除する。そして、ノード間要求処理部１５ｂは、要求発行部１７ｂに対して、ｕｐｄａｔｅｄ要求の発行を指示するとともに、ｕｐｄａｔｅ要求に格納されていた経路情報を出力する。
【０１４４】
他終端状態判断部２５は、クライアント要求受信部１２ａが出力したＧｅｔ要求を取得する。このような場合には、他終端状態判断部２５は、要求収集部２４ａが自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別する。そして、他終端状態判断部２５は、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信していないと判別した場合は、クライアント要求処理部１３ａに更新前のレプリカのデータをクライアント７に出力するよう指示する。
【０１４５】
また、他終端状態判断部２５は、要求収集部２４ａが自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信していた場合には、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信したか否かを判別する。そして、他終端状態判断部２５は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していると判別した場合には、クライアント要求処理部１３ａに更新後のレプリカのデータを出力するよう指示する。
【０１４６】
また、他終端状態判断部２５は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していないと判別した場合には、以下の処理を実行する。すなわち、他終端状態判断部２５は、ｕｐｄａｔｅｄ要求の発行を依頼したか否かを他の終端ノードに問合せるようクライアント要求処理部１３ａに指示する。
【０１４７】
そして、他終端状態判断部２５は、いずれかの終端ノードからｕｐｄａｔｅｄ要求の発行を依頼した旨の返答を受信した場合には、クライアント要求処理部１３ａに更新後のレプリカのデータをクライアント７に出力するよう指示する。一方、他終端状態判断部２５は、どの終端ノードからもｕｐｄａｔｅｄ要求の発行を依頼した旨の返答を受信しなかった場合には、クライアント要求処理部１３ａに更新前のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。
【０１４８】
つまり、他終端状態判断部２５は、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信し、かつ、自身を含むいずれかの終端ノードがｕｐｄａｔｅｄ要求の発行を依頼した場合は、Ｇｅｔ要求に対して更新後のレプリカのデータを出力させる。なお、他終端状態判断部２５は、他の終端ノードにｕｐｄａｔｅｄ要求を送信したか否かの問合せを行っている最中に、要求収集部２４ａが全ての終端ノードからｒｅａｄＴｏＵｐｄａｔｅ要求を取得した場合には、問合せを中止する。そして、他終点判断部２５は、更新後のレプリカのデータを出力するようにクライアント要求処理部１３ａに指示する。
【０１４９】
なお、要求収集部２４ａは、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、クライアント要求受信部１２ａを介して、他の終端ノードから送信された問合せを取得する。このような場合には、要求収集部２４ａは、自身がｕｐｄａｔｅｄ要求の発行を指示したか否かを問合せ元の終端ノードに返信するようノード間要求処理部１５ｂに指示する。このような場合には、返信が要求発行部１７ｂ、トポロジー計算部２０ｃ、ノード間要求並列送信部２１を介して、問合せ元の終端ノードに送信される。
【０１５０】
要求発行部１７ｂは、図７に例示した要求発行部１７ａと同様の機能を発揮する。また、要求発行部１７ｂは、経路情報を取得するとともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示された場合には、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を生成する。そして、要求発行部１７ｂは、取得した経路情報とともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求をトポロジー計算部２０ｃに出力する。
【０１５１】
トポロジー計算部２０ｃは、図７に示すトポロジー計算部２０ａと同様の機能を発揮する。また、トポロジー計算部２０ｃは、経路情報とともにｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得した場合には、取得した経路情報を解析し、自身以外の終端ノードを全て識別する。その後、トポロジー計算部２０ｃは、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を識別した全ての終端ノードに送信するようノード間要求並列送信部２１に指示する。
【０１５２】
このようなノード３ａおよびノード５ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信した場合には、他の終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。そして、ノード３ａおよびノード５ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信し、かつ、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信した場合には、ｕｐｄａｔｅｄ要求を送信することとなる。このため、ストレージシステム１ａは、ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を転送する複数の経路において、終端ノードが同一ではない場合にも、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持したまま、レプリカの更新に要する時間を短縮できる。
【０１５３】
また、ノード３ａおよびノード５ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信してから、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅを受信するまでの間にＧｅｔ要求を受信した場合には、以下の処理を実行する。すなわち、ノード３ａおよびノード５ａは、他の終端ノードにｕｐｄａｔｅｄ要求を発行したか否かを問い合わせることで、ｕｐｄａｔｅｄ要求を発行した終端ノードが存在するか否かを判別する。そして、ノード３ａおよびノード５ａは、いずれかの終端ノードがｕｐｄａｔｅｄ要求を発行した場合には、更新後のレプリカのデータを出力し、いずれの終端ノードもｕｐｄａｔｅｄ要求を発行していない場合には、更新前のレプリカのデータを出力する。
【０１５４】
このため、ストレージシステム１ａは、レプリカの更新中にＧｅｔ要求が発行された場合にも、各経路における更新状況に応じたデータをクライアントに送信することができる。この結果、ストレージシステム１ａは、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持したまま、レプリカの更新に要する時間を短縮できる。
【０１５５】
次に、図１６を用いて、終端ノードであるノード３ａ、ノード５ａがクライアント７からＧｅｔ要求を受信した際に実行する処理の一例について説明する。図１６は、実施例２に関わる終端ノードがＧｅｔ要求を受信した際に実行する処理の一例を説明するための図である。なお、図１６に示す例では、ノード３ａに対してクライアント７がデータＡに関わるレプリカＡ２のＧｅｔ要求を発行した例について説明する。
【０１５６】
まず、図１６中（１）に示すように、ネットワークインターフェース１０ａは、Ｇｅｔ要求を要求送信元判断部１１ａに出力する。このような場合には、要求送信元判断部１１ａは、図１６中（２）に示すように、クライアント要求受信部１２ａに出力する。次に
クライアント要求受信部１２ａは、図１６中（３）に示すように、クライアント７の位置情報をクライアント位置記憶部１９に格納する。また、クライアント要求受信部１２ａは、Ｇｅｔ要求を他終端状態判断部２５に出力する。
【０１５７】
次に、他終端状態判断部２５は、図１６中（４）に示すように、要求収集部２４ａがノード３ａを終端とする全ての経路を介してｕｐｄａｔｅ要求を取得したか否かを判別する。そして、他終端状態判断部２５は、要求収集部２４ａがノード３ａを終端とする全ての経路を介してｕｐｄａｔｅ要求を取得していない場合は、更新前のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。
【０１５８】
また、他終端状態判断部２５は、要求収集部２４ａがノード３ａを終端とする全ての経路を介してｕｐｄａｔｅ要求を取得している場合は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したか否かを判別する。そして、他終端状態判断部２５は、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得していない場合には、図１６中（５）に示すように、他の終端ノードに問合せるよう指示する。
【０１５９】
その後、他終端状態判断部２５は、ｕｐｄａｔｅｄ要求を送信した旨の返信をいずれかの終端ノードから取得した場合には、更新後のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。また、他終端状態判断部２５は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏｕｐｄａｔｅ要求を取得していた場合には、更新後のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。すると、クライアント要求処理部１３ａは、要求発行部１７ｂに更新後のレプリカのデータを出力するよう指示する。
【０１６０】
このような場合には、要求発行部１７ｂは、図１６中（６）に示すように、更新後のレプリカのデータを取得し、図１６中（７）に示すように取得したデータをクライアント位置判断部２２に出力する。すると、クライアント位置判断部２２は、クライアント位置記憶部１９からＧｅｔ要求の発行元であるクライアント７の位置情報を取得する。そして、クライアント位置判断部２２は、図１６中（８）に示すように、レプリカのデータとクライアント７の位置情報とをクライアント要求送信部２３に出力する。このような場合には、図１６中（９）に示すように、クライアント要求送信部２３は、ネットワークインターフェース１０ａを介して、クライアント７にレプリカのデータを送信する。
【０１６１】
次に、図１７を用いて、ノード３ａがｕｐｄａｔｅ要求を受信した際に実行する処理の一例について説明する。図１７は、実施例２に関わる終端ノードがｕｐｄａｔｅ要求を受信した際に実行する処理の一例を説明するための図である。例えば、図１７中（１）に示すように、ネットワークインターフェース１０ａは、受信したｕｐｄａｔｅ要求を要求送信元判断部１１ａに送信する。このような場合には、図１７中（２）に示すように、要求元判断部１１ａは、ｕｐｄａｔｅ要求をノード間要求受信部１４に出力し、図１７中（３）に示すように、ノード間要求受信部１４は、ｕｐｄａｔｅｄ要求を要求収集部２４ａに出力する。
【０１６２】
ここで、要求収集部２４ａは、要求収集部２４と同様に、ノード３ａを終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得するまで待機する。そして、要求収集部２４ａは、ノード３ａを終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得した場合には、図１７中（４）に示すように、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信するようノード間要求処理部１５ｂに指示する。
【０１６３】
このような場合には、ノード間要求処理部１５ｂは、図１７中（５）に示すように、更新後のレプリカのデータをデータ記憶部１６に格納する。また、ノード間要求処理部１５ｂは、図１７中（６）に示すように、要求発行部１７ｂにｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示する。このような場合には、要求発行部１７ｂ、トポロジー計算部２０ｃ、ノード間要求並列送信部２１は、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を他の終端ノードであるノード５ａに送信する。
【０１６４】
また、図１７中（７）に示すように、要求収集部２４ａは、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、ノード間要求受信部１４を介して、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得した場合には、以下の処理を実行する。すなわち、要求収集部２４ａは、ノード３ａ以外の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したか否かを判別する。
【０１６５】
そして、要求収集部２４ａは、ノード３ａ以外の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したと判別した場合には、図１７中（８）に示すように、ノード間要求処理部１５ｂに受信したｕｐｄａｔｅ要求のうちの１つを送信する。以降、ノード３ａは、実施例１に関わるノード５と同様の処理を実行し、ノード３ａを終端とする全ての経路を介して、ｕｐｄａｔｅｄ要求を始端ノードまで順次転送させる。
【０１６６】
次に、図１８ａ〜１８ｄを用いて、実施例２に関わるストレージシステム１ａがそれぞれ終端ノードが異なる複数の経路を介して、ｕｐｄａｔｅ要求とｕｐｄａｔｅｄ要求とを順次転送する処理について説明する。なお、図１８ａ〜１８ｄに示す例では、図９ａ、図９ｂに示すように、１ｓｔノードから７ｔｈノードまでの７個のノードが記憶するレプリカの更新を行う例について説明する。
【０１６７】
図１８ａは、実施例２に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。また、図１８ｂは、実施例２に関わる終端ノードがｒｅａｄｙＴｏＵｐｄａｔｅ要求を送受信する処理を説明するための図である。また、図１８ｃは、実施例２に関わるストレージシステムがｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。また、図１８ｄは、実施例２に関わるストレージシステムにおける動作を説明するための図である。
【０１６８】
まず図１８ａ中（Ｈ）に示すように、クライアント７は、始端ノードである１ｓｔノードにＰｕｔ要求を発行する。このような場合には、１ｓｔノードは、図１８ａに示すように、２ｎｄノード、４ｔｈノード、６ｔｈノードを接続する経路と、３ｒｄノード、５ｔｈノード、７ｔｈノードを接続する経路とを識別する。
【０１６９】
そして、図１８ａ中（Ｉ）に示すように、１ｓｔノードは、２ｎｄノードと３ｒｄノードとにｕｐｄａｔｅ要求を送信する。このような場合には、２ｎｄノードは４ｔｈノードにｕｐｄａｔｅ要求を転送し、４ｔｈノードは６ｔｈノードにｕｐｄａｔｅ要求を転送する。また、３ｒｄノードは５ｔｈノードにｕｐｄａｔｅ要求を転送し、５ｔｈノードは７ｔｈノードにｕｐｄａｔｅ要求を転送する。
【０１７０】
また、図１８ｂ中（Ｊ）に示すように、各経路の終端ノードである６ｔｈノードと７ｔｈノードは、ｕｐｄａｔｅ要求を受信した場合には、他の経路の終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。この処理によって、各経路の終端ノードである６ｔｈノードと７ｔｈノードとは、他の経路のノードにｕｐｄａｔｅ要求が行き渡ったか否かを識別することができる。
【０１７１】
そして、図１８ｃ中（Ｋ）に示すように、各経路の終端ノードである６ｔｈノードと７ｔｈノードは、自身以外の終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得した場合には、ｕｐｄａｔｅｄ要求を４ｔｈノードおよび５ｔｈノードに送信する。その後、図１８ｃ中（Ｌ）に示すように、１ｓｔノードは、いずれかの経路からｕｐａｄｔｅｄ要求を取得した場合には、Ｐｕｔ返答をクライアント７に送信する。
【０１７２】
すなわち、図１８ｄ中（Ｍ）に示すように、６ｔｈノードおよび７ｔｈノードは、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を相互に送受信することで、各経路の終端ノードとなる仮想終端ノードが存在するものとして動作する。このような処理を実行することで、ストレージシステム１ａは、各経路の終端ノードが異なるノードである場合にも、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持することができる。
【０１７３】
なお、各経路の終端ノードである６ｔｈノードおよび７ｔｈノードは、複数の経路の終端ノードとしても動作することができる。図１９は、複数の経路の終端ノードが実行する処理の一例を説明するための図である。図１９に示す例では、６ｔｈノードは、図１８ａ〜１８ｄに示した１ｓｔノード、２ｎｄノード、４ｔｈノード、６ｔｈノードを接続する経路に加えて、１ｓｔノード、８ｔｈノード、９ｔｈノード、６ｔｈノードを接続する経路の終端ノードとなる。
【０１７４】
このような場合には、６ｔｈノードは、図１９中（Ｎ）に示すように、自身を終端ノードとする２つの経路からｕｐｄａｔｅ要求を取得するまで待機する。そして、６ｔｈノードは、２つの経路からｕｐｄａｔｅ要求を取得した場合には、図１９中（Ｏ）に示すように、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を７ｔｈノードに送信する。このような処理を行うことで、ストレージシステム１ａは、任意のトポロジーを有する複数の経路を介して、ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を各ノードに送信することができる。
【０１７５】
例えば、ノード間要求処理部１５ｂ、要求発行部１７ｂ、トポロジー計算部２０ｃ、要求収集部２４ａ、他終端状態判断部２５とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積回路、またはＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）などを適用する。
【０１７６】
次に、図２０を用いて、終端ノードが実行する処理の流れの一例について説明する。図２０は、実施例２に関わる終端ノードが実行する処理の流れを説明するためのフローチャートである。なお、以下の説明では、ノード３ａが終端ノードとして動作する際に実行する処理の一例について説明する。
【０１７７】
例えば、ノード３ａは、自身の状態に停止条件が発生しているか否かを判別する（ステップＳ４０１）。そして、ノード３ａは、自身の状態に停止条件が発生していないと判別した場合には（ステップＳ４０１否定）、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ４０２）。そして、ノード３ａは、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信していないと判別した場合には（ステップＳ４０２否定）、全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する（ステップＳ４０２）。
【０１７８】
また、ノード３ａは、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信した場合には（ステップＳ４０２肯定）、各終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信し、ｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態に移行する（ステップＳ４０３）。ここで、ｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態とは、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信し、かつ、他の終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していない状態である。
【０１７９】
また、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ４０４）。そして、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していないと判別した場合には（ステップＳ４０４否定）、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信するまで待機する（ステップＳ４０４）。
【０１８０】
また、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信した場合には（ステップＳ４０４肯定）、レプリカを更新するとともに、自身を終端ノードとする全ての経路の前ノードにｕｐｄａｔｅｄ要求を送信する（ステップＳ４０５）。この際、ノード３ａは、ｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態を解除する。その後、ノード３ａは、再度停止条件が発生しているか否かを判別し（ステップＳ４０１）、発生している場合には（ステップＳ４０１肯定）、停止条件が解消するまで処理を終了する。
【０１８１】
次に、図２１を用いて、終端ノードがＧｅｔ要求を受信した際に実行する処理の流れの一例を説明する。図２１は、Ｇｅｔ要求に対する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明では、ノード３ａが終端ノードとして動作する際に実行する処理の流れの一例について説明する。
【０１８２】
まず、ノード３ａは、停止条件が発生しているかを判別し（ステップＳ５０１）、発生していない場合には（ステップＳ５０１否定）、クライアント７からＧｅｔ要求を受信したか否かを判別する（ステップＳ５０２）。そして、ノード３ａは、クライアント７からＧｅｔ要求を受信した場合には（ステップＳ５０２肯定）、自身がｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態であるか否かを判別する（ステップＳ５０３）。すなわち、ノード３ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信したか否かを判別する。
【０１８３】
そして、ノード３ａは、自身がｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態であると判別した場合には（ステップＳ５０３肯定）、他の終端ノードに問合せを行う（ステップＳ５０４）。そして、ノード３ａは、いずれかの終端ノードがｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態を解除してｕｐｄａｔｅｄ要求の発行を依頼したか否かを判別する（ステップＳ５０５）。
【０１８４】
その後、ノード３ａは、いずれの終端ノードもｕｐｄａｔｅｄ要求の発行を依頼していないと判別した場合には（ステップＳ５０５否定）、更新前のレプリカのデータをクライアント７に送信する（ステップＳ５０６）。また、ノード３ａは、いずれかの終端ノードがｕｐｄａｔｅｄ要求の発行を依頼したと判別した場合には（ステップＳ５０５肯定）、更新後のレプリカのデータをクライアント７に送信する（ステップＳ５０７）。その後、ノード３ａは、再度停止条件が発生しているか否かを判別し（ステップＳ５０１）、停止条件が発生している場合には（ステップＳ５０１肯定）、停止条件が解消するまで処理を終了する。
【０１８５】
また、ノード３ａは、Ｇｅｔ要求を受信した際に（ステップＳ５０２肯定）、自身がｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態ではないと判別した場合には（ステップＳ５０３否定）、保持しているレプリカのデータをクライアント７に送信する（ステップＳ５０８）。
【０１８６】
すなわち、ノード３ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信していない場合には、更新後のレプリカのデータを記憶していないので、更新前のレプリカのデータを送信することとなる。また、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信した場合には、更新後のレプリカのデータのみを記憶しているので、更新後のレプリカのデータを送信することとなる。
【０１８７】
また、ノード３ａは、Ｇｅｔ要求を受信していない場合には（ステップＳ５０２否定）、再度停止条件が発生しているか否かを判別する（ステップＳ５０１）。
【０１８８】
[ストレージシステム１ａの効果]
上述したように、終端ノードとして動作するノード３ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信した場合には、自身を終端ノードとする経路以外の経路における終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。そして、ノード３ａは、自身以外の全ての終端ノードからｒｅａｄｙＴｏＵｄａｔｅ要求を受信したか否かを判別する。その後、ノード３ａは、自身以外の全ての終端ノードからｒｅａｄｙＴｏＵｄａｔｅ要求を受信した場合には、ｕｐｄａｔｅｄ要求を、自身を終端ノードとする全ての経路を介して、始端ノードに送信する。
【０１８９】
このため、このようなノード３ａを有するストレージシステム１ａは、それぞれ異なるノードを終端ノードとする経路を介してｕｐｄａｔｅ要求を各ノードに送信することができる。この結果、ストレージシステム１ａは、レプリカの更新に要する時間をさらに短縮することができる。例えば、各ノード２ａ〜６ａの設置位置によっては、終端ノードを１つのノードとする複数の経路よりも、終端ノードを複数のノードとする複数の経路でｕｐｄａｔｅ要求を送信した方が更新に要する時間を短縮できる場合がある。このような場合にも、ストレージシステム１ａは、レプリカの更新に要する時間を短縮することができる。
【０１９０】
また、ノード３ａは、クライアント７からＧｅｔ要求を受信した場合には、自身がｒｅａｄｙＴｏＵｐｄａｔｅ状態か否かを判別し、ｒｅａｄｙＴｏＵｐｄａｔｅ状態である場合には、他の終端ノードがｕｐｄａｔｅｄ要求の発行を依頼したか否かを判別する。そして、ノード３ａは、いずれかの終端ノードがｕｐｄａｔｅｄ要求の発行を依頼していた場合には、更新後のレプリカのデータをクライアント７に送信する。また、ノード３ａは、いずれの終端ノードもｕｐｄａｔｅｄ要求の発行を依頼していない場合には、更新前のレプリカのデータをクライアント７に送信する。
【０１９１】
このようなノード３ａを有するストレージシステム１ａは、終端ノードが複数存在する場合にも、各終端ノードがＧｅｔ要求に対して送信するレプリカのデータをそろえることができる。この結果、ストレージシステム１ａは、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持しつつ、レプリカの更新に要する時間を短縮することができる。
【実施例３】
【０１９２】
これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例３として本発明に含まれる他の実施例を説明する。
【０１９３】
（１）経路の識別について
上述したストレージシステム１、１ａは、クライアント７がＰｕｔ要求を始端ノードに発行した場合には、更新対象となるレプリカを記憶するノードを識別し、識別したノードを接続する複数の経路を識別した。しかし、実施例はこれに限定されるものではない。すなわち、ストレージシステム１、１ａは、更新対象となるデータごとにあらかじめ設定された複数の経路を介して、ｕｐｄａｔｅ要求を各ノードに送信することとしてもよい。
【０１９４】
例えば、ストレージシステム１、１ａは、各ノード２〜５が記憶するレプリカＡ１〜Ａ４が他のノードに移る等の処理が発生しない場合など、ｕｐｄａｔｅ要求を送信する経路を固定してもよい場合には、ノード２〜５に予めｕｐｄａｔｅ要求を送信する経路を設定する。そして、ノード２〜５は、ノード２がＰｕｔ要求を受信した場合には、予め設定された複数の経路にそって、ｕｐｄａｔｅ要求を順に転送することとしてもよい。
【０１９５】
すなわち、ストレージシステム１、１ａは、複数の経路（マルチパス）でｕｐｄａｔｅ要求を各ノードに送信した場合には、１つの経路（シングルパス）でｕｐｄａｔｅ要求を各ノードに送信するよりも短時間でレプリカの更新を行うことができる。このため、ストレージシステム１、１ａは、複数の経路でｕｐｄａｔｅ要求を送信することができれば、経路が固定であっても、その都度複数の経路を識別する方法であってもよい。
【０１９６】
（２）ノードの数や各ノードが記憶するレプリカについて
上述した例では、ノード２〜６がレプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４を記憶する例について説明した。しかし、実施例はこれに限定されるものではなく、ノードの数や各ノードが記憶するレプリカの数および種類は任意の組合せを適用することができる。
【０１９７】
（３）経路情報について
上述した例では、ｕｐｄａｔｅ要求を送信する経路を示す経路情報をｕｐｄａｔｅ要求のヘッダに格納した。しかし、実施例はこれに限定されるものではない。例えば、ｕｐｄａｔｅ要求を送信する経路が固定である場合には、経路情報を格納する必要はなく、経路が固定でなくとも、経路情報をｕｐｄａｔｅ要求とは別に送ってもよい。すなわち、各ノードがｕｐｄａｔｅ要求を送信する経路を識別する処理については、任意の手法を適用することができる。
【０１９８】
（４）経路について
上述した例では、２つまたは３つの経路を識別したが、実施例はこれに限定されるものではなく、任意の数の複数の経路を識別することもできる。例えば、トポロジー計算部２０は、ｕｐｄａｔｅ要求を送信する複数の経路の組を複数識別し、各組において片道の最大遅延が最も小さい組を選択することとしてもよい。
【０１９９】
すなわち、ノード２〜６にレプリカＤ１〜Ｄ５が記憶されている際に、各レプリカ間の遅延がすべて１０ｍｓｅｃ（millisecond）だとする。このような場合に、トポロジー計算部２０は、ノード２、ノード３、ノード４、ノード６の経路とノード２、ノード５、ノード６の経路との第１の組を識別する。また、トポロジー計算部２０は、ノード２、ノード３、ノード６の経路と、ノード２、ノード４、ノード６の経路と、ノード２、ノード５、ノード６の経路との第２の組を識別する。このような場合には、第２の組の方が、片道の最大遅延が１０ｍｓｅｃ短いので、第２の組を識別することとなる。
【０２００】
（５）プログラム
ところで、実施例１、２に関わるノード２〜６、２ａ〜６ａは、ハードウェアを利用して各種の処理を実現する場合を説明した。しかし、実施例はこれに限定されるものではなく、あらかじめ用意されたプログラムをストレージ装置として動作するコンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図２２を用いて、実施例１に示したノード２〜６と同様の機能を有するデータ管理プログラムを実行するコンピュータの一例を説明する。図２２は、データ管理プログラムを実行するコンピュータの一例を説明するための図である。
【０２０１】
図２２に例示されたコンピュータ１００は、ＲＡＭ（Random Access Memory）１１０、ＨＤＤ（Hard Disk Drive）１２０、ＲＯＭ（Read Only Memory）１３０、ＣＰＵ（Central Processing Unit）１４０がバス１６０で接続される。また、コンピュータ１００は、ＲＡＭ（Random Access Memory）１４０、他のコンピュータと通信を行うためのＩ／Ｏ（Input Output）１５０がバス１６０で接続される。
【０２０２】
ＨＤＤ１２０には、レプリカが記憶されている。ＲＯＭ１３０には、データ更新プログラム１３１が記憶されており、ＣＰＵ１４０が読み出して実行することによって、図２２に示す例では、データ更新プロセス１４１として機能するようになる。なお、データ更新プロセス１４１は、図３に示す各部１１〜２３と同様の機能を発揮するが、図７に示す要求収集部２４および図１５に示す他終端状態判断部２５の機能を付加することもできる。
【０２０３】
なお、本実施例で説明したデータ管理プログラムは、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＭＯ（Magneto Optical Disc）、ＤＶＤ（Digital Versatile Disc）などのコンピュータで読取可能な記録媒体に記録される。また、このプログラムは、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【０２０４】
１、１ａ ストレージネットワーク
２〜６、２ａ〜６ａ ノード
７ クライアント
８ ＩＰ網
１０、１０ａ ネットワークインターフェース
１１、１１ａ 要求送信元判断部
１２、１２ａ クライアント要求受信部
１３、１３ａ クライアント要求処理部
１４ ノード間要求受信部
１５〜１５ｂ ノード間要求処理部
１６ データ記憶部
１７〜１７ｂ 要求発行部
１８ 要求発行認証部
１９ クライアント位置記憶部
２０〜２０ｃ トポロジー計算部
２１ ノード間要求並列送信部
２２ クライアント位置判断部
２３ クライアント要求送信部
２４、２４ａ 要求収集部
２５ 他終端状態判断部
【技術分野】
【０００１】
本発明は、ストレージ装置、ストレージシステム、データ更新方法およびデータ管理プログラムに関する。
【背景技術】
【０００２】
従来、分散ＫＶＳ（Key-Value Store）等のＮｏＳＱＬを初めとするストレージシステムにおいて、データの複製であるレプリカを複数のノードに配置する技術が知られている。このような技術が適用されたストレージシステムは、レプリカを複数のノードに配置することで、ディスク故障などによるデータの消失を防ぐとともに、各ノードに配置されたレプリカからデータの読出しを許可することで、アクセスの負荷分散を行う。
【０００３】
ここで、ストレージシステムは、各レプリカから読み出されるデータの同一性を保証するＳｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙが要求される場合がある。このようなＳｔｒｏ
ｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保つ手法の一例として、チェインレプリケーションの技術が知られている。このようなチェインレプリケーションが適用されたストレージシステムの一例について以下に説明する。
【０００４】
図２３は、チェインレプリケーションの一例について説明するための図である。なお、図２３に示す例では、チェインレプリケーションの一例としてＣＲＡＱ（Ｃｈａｉｎ Ｒｅｐｌｉｃａｔｉｏｎ ｗｉｔｈ Ａｐｐｏｒｔｉｏｎｅｄ Ｑｕｅｒｙ）が適用されたストレージシステムについて説明する。
【０００５】
図２３に示す例では、ストレージシステムは、同一のレプリカを有するＮ個のノードを有する。なお、図２３に示す例では、ストレージシステムは、Ｎ個のノードのうち、１ｓｔノード、２ｎｄノード、３ｒｄノード、Ｎｔｈノード以外のノードについては、図示を省略した。
【０００６】
このようなストレージシステムが有する各ノードは、クライアントからレプリカの更新を要求された場合には、各ノードを順に並べた経路に沿って、レプリカの更新を要求するｕｐｄａｔｅ要求を順次転送する。例えば、図２３中（Ａ）に示す例では、クライアントは、レプリカの更新要求を１ｓｔノードに発行する。このような場合には、１ｓｔノードは、レプリカの更新を準備するとともに、図２３中（Ｂ）に示すように、２ｎｄノードにｕｐｄａｔｅ要求を送信する。
【０００７】
次に、２ｎｄノードは、１ｓｔノードからｕｐｄａｔｅ要求を受信した場合には、レプリカの更新を準備するとともに、ｕｐｄａｔｅ要求を３ｒｄノードに転送する。その後、各ノードは、ｕｐｄａｔｅ要求を経路の終端となるＮｔｈノードまで順に転送する。また、図２３中（Ｃ）に示すように、経路の終端となるＮｔｈノードは、ｕｐｄａｔｅ要求を受信した場合には、レプリカを更新するとともに、ｕｐｄａｔｅ要求に対する応答であるｕｐｄａｔｅｄ要求を経路の１つ前のノードに送信する。
【０００８】
その後、各ノードは、ｕｐｄａｔｅｄ要求を受信した場合は、レプリカの更新を行うとともに、ｕｐｄａｔｅｄ要求を１次元の経路に沿って、始点となる１ｓｔノードまで順に転送する。そして、１ｓｔノードは、図２３中（Ｄ）に示すように、ｕｐｄａｔｅｄ要求を受信した場合には、レプリカを更新し、更新が終了した旨をクライアントに通知する。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Object Storage on CRAQ, High-throughput chain replication for read-mostly workloads, Jeff Terrace and Michael J.Freedman Princeton University, USENIX annual Technical Conference.San Diego, CA, June 2009.
【非特許文献２】Chain Replication for Supporting High Throughput and Availability, Robbert van Renesse, Fred B.Schneider, USENIX Association OSDI’04:6th Symposium on Operation Systems Design and Implementation.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかし、上述したチェインレプリケーションの技術では、レプリカの更新を行う場合は、各ノードを順に接続する１つの経路に沿って、ｕｐｄａｔｅ要求を順に転送するので、ノードの数が増加するに従って、更新に要する時間が増加するという問題がある。
【００１１】
例えば、上述したチェインレプリケーションの技術では、ノードの数が倍になると、データの更新に要する時間も倍になってしまう。また、ノードの設置位置を分散させる分散環境の技術が適用されたストレージシステムにおいては、ノードを広域に設置し、ノード同士の距離が離れると、ネットワークの遅延が増加するので、レプリカの更新処理に要する時間がボトルネックとなってしまう。
【００１２】
本願は、上述した問題に鑑みてなされたものであり、１つの側面では、レプリカの更新に要する時間を短縮する。
【課題を解決するための手段】
【００１３】
１つの側面では、データの複製を記憶する複数のストレージ装置のうち、クライアントからデータの更新を要求されるストレージ装置である。このストレージ装置は、データの更新を要求された場合は、自ストレージ装置を始端とし、複数のストレージ装置を直列に接続する複数の経路を介して、各経路の終端となる１つまたは複数のストレージ装置にデータの更新を要求する更新要求を送信する。また、ストレージ装置は、各経路の終端となるストレージ装置が全ての経路を介して更新要求を受信した後に発行した応答を、更新通知を送信したいずれかの経路を介して受信した場合は、データの更新が完了した旨を前記クライアントに通知する。
【発明の効果】
【００１４】
１つの側面では、レプリカの更新に要する時間を短縮する。
【図面の簡単な説明】
【００１５】
【図１】図１は、実施例１に関わるストレージシステムの一例を説明するための図である。
【図２ａ】図２ａは、データＡのレプリカを記憶するノードを説明するための図である。
【図２ｂ】図２ｂは、データＢのレプリカを記憶するノードを説明するための図である。
【図２ｃ】図２ｃは、データＣのレプリカを記憶するノードを説明するための図である。
【図３】図３は、実施例１に関わる始端ノードの一例を説明するための図である。
【図４ａ】図４ａは、実施例１に関わるデータ記憶部が記憶する位置情報の一例を説明するための図である。
【図４ｂ】図４ｂは、実施例１に関わるデータ記憶部が記憶する各レプリカＡ１〜Ａ４を記憶するノードを示す情報の一例を説明するための図である。
【図５】図５は、実施例１に関わる始端ノードがｕｐｄａｔｅ要求を発行する処理の一例を説明するための図である。
【図６】図６は、実施例１に関わる始端ノードがｕｐｄａｔｅｄ要求を受信した際に実行する処理の一例を説明するための図である。
【図７】図７は、実施例１に関わる終端ノードの一例を説明するための図である。
【図８】図８は、実施例１に関わる終端ノードが実行する処理の一例を説明するための図である。
【図９ａ】図９ａは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。
【図９ｂ】図９ｂは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。
【図１０】図１０は、始端ノードが実行する処理の流れの一例を説明するためのフローチャートである。
【図１１】図１１は、中間ノードが実行する処理の流れの一例を説明するためのフローチャートである。
【図１２】図１２は、終端ノードが実行する処理の流れの一例を説明するためのフローチャートである。
【図１３】図１３は、実施例２に関わるストレージシステムの一例を説明するための図である。
【図１４】図１４は、実施例２に関わる始端ノードの一例を説明するための図である。
【図１５】図１５は、実施例２に関わる終端ノードの一例を説明するための図である。
【図１６】図１６は、実施例２に関わる終端ノードがＧｅｔ要求を受信した際に実行する処理の一例を説明するための図である。
【図１７】図１７は、実施例２に関わる終端ノードがｕｐｄａｔｅ要求を受信した際に実行する処理の一例を説明するための図である。
【図１８ａ】図１８ａは、実施例２に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。
【図１８ｂ】図１８ｂは、実施例２に関わる終端ノードがｒｅａｄｙＴｏＵｐｄａｔｅ要求を送受信する処理を説明するための図である。
【図１８ｃ】図１８ｃは、実施例２に関わるストレージシステムがｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。
【図１８ｄ】図１８ｄは、実施例２に関わるストレージシステムにおける動作を説明するための図である。
【図１９】図１９は、複数の経路の終端ノードが実行する処理の一例を説明するための図である。
【図２０】図２０は、実施例２に関わる終端ノードが実行する処理の流れを説明するためのフローチャートである。
【図２１】図２１は、Ｇｅｔ要求に対する処理の流れの一例を説明するためのフローチャートである。
【図２２】図２２は、データ管理プログラムを実行するコンピュータの一例を説明するための図である。
【図２３】図２３は、チェインレプリケーションの一例について説明するための図である。
【発明を実施するための形態】
【００１６】
以下に添付図面を参照して本願に係るストレージ装置、ストレージシステム、データ更新方法およびデータ管理プログラムについて説明する。
【実施例１】
【００１７】
以下の実施例１では、図１を用いて、ストレージシステムの一例を説明する。図１は、実施例１に関わるストレージシステムの一例を説明するための図である。なお、以下の説明において、ノードとは、例えば、データの複製であるレプリカを記憶する情報処理装置と、他のノードとの通信処理、データの更新処理、データの管理処理等を実行する演算処理装置とを有するストレージ装置やサーバ等が適用されるものとする。
【００１８】
図１に示すように、ストレージ装置１は、複数のデータセンター＃１〜＃３およびクライアント７をＩＰ（Internet Protocol）網８を介して接続したシステムである。また、データセンター＃１には、ノード２とノード３が設置されており、データセンター＃２には、ノード４、ノード５が設置されており、データセンター＃３には、ノード６が設置されている。
【００１９】
また、各ノード２〜６は、データの複製であるレプリカを記憶する。具体的には、各ノード２〜６は、データＡのレプリカであるレプリカＡ１〜Ａ４、データＢのレプリカであるレプリカＢ１〜Ｂ４、データＣのレプリカであるレプリカＣ１〜Ｃ４を分散させて記憶する。
【００２０】
例えば、図１に示す例では、ノード２は、レプリカＡ１とレプリカＣ４を記憶する。また、ノード３は、レプリカＡ２、レプリカＢ１を記憶する。また、ノード４は、レプリカＡ３、レプリカＣ１、レプリカＢ２を記憶する。また、ノード５は、レプリカＡ４、レプリカＣ２、レプリカＢ３を記憶する。また、ノード６は、レプリカＢ４とレプリカＣ３を記憶する。
【００２１】
ここで、図２ａ〜図２ｃを用いて、各データＡ〜Ｃのレプリカをどのノード２〜６が記憶しているかを説明する。なお、図２ａは、データＡのレプリカを記憶するノードを説明するための図である。また、図２ｂは、データＢのレプリカを記憶するノードを説明するための図である。また、図２ｃは、データＣのレプリカを記憶するノードを説明するための図である。なお、図２ａ〜図２ｃでは、各行に各レプリカを、各列に各ノード２〜６を対応付け、丸印が付けられたマスの行に対応付けたレプリカを、列に対応付けたノードが記憶することを示した。
【００２２】
例えば、図２ａに示すように、データＡのレプリカであるレプリカＡ１〜Ａ４は、ノード２〜５が記憶する。また、図２ｂに示すように、データＢのレプリカであるレプリカＢ１〜Ｂ４は、ノード３〜６が記憶する。また、図２ｃに示すように、データＣのレプリカであるレプリカＣ１〜Ｃ４は、ノード２及びノード４〜６が記憶する。
【００２３】
クライアント７は、各ノード２〜６が記憶する各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４を用いて、各データＡ〜Ｃの読出しや各データＡ〜Ｃの更新等を実行する。具体的には、クライアント７は、各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４がどのノードに記憶されているかを示す情報を記憶する。
【００２４】
そして、クライアント７は、ＩＰ網８を介して、レプリカの読出し要求を示すＧｅｔ要求を、ｕｐｄａｔｅ要求を転送する経路の終端ノードに発行する。例えば、クライアント７は、データＡの更新においてノード５が終端ノードとなる場合には、ノード５にＧｅｔ要求を発行する。
【００２５】
また、クライアント７は、ＩＰ網８を介して、レプリカの更新要求を示すＰｕｔ要求を発行する場合には、レプリカごとに定められた所定のノードに発行する。つまり、クライアント７は、各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４を更新する際にｕｐｄａｔｅ要求が送信される経路における始端ノードに対してＰｕｔ要求を発行する。例えば、クライアント７は、レプリカＡ１〜Ａ４の更新を行う場合には、レプリカＡ１を記憶するノード２に対してＰｕｔ要求を発行する。
【００２６】
また、クライアント７は、レプリカＢ１〜Ｂ４の更新を行う場合には、レプリカＢ１を記憶するノード３に対してＰｕｔ要求を発行する。また、クライアント７は、レプリカＣ１〜Ｃ４の更新を行う場合には、レプリカＣ１を記憶するノード４に対してＰｕｔ要求を発行する。
【００２７】
各ノード２〜６は、経路の終端ノードである際にＧｅｔ要求をクライアント７から取得した場合には、Ｇｅｔ要求の対象となるレプリカのデータをクライアント７へ送信する。また、ノード２〜４は、経路の始端ノードである際にＰｕｔ要求を取得した場合は、自ストレージ装置を始端とし、更新対象となるレプリカを記憶するノードを直列に接続する複数の経路に沿って、レプリカの更新を要求するｕｐｄａｔｅ要求を、各経路の終端となるノードに送信する。
【００２８】
例えば、ノード２は、クライアント７からレプリカＡに関わるＰｕｔ要求を取得した場合には、以下の処理を実行する。すなわち、ノード２は、更新に関わるレプリカＡを記憶する複数のノード３〜５を識別する。そして、ノード２は、ｕｐｄａｔｅ要求を送信する複数の経路を識別する。例えば、ノード２は、ｕｐｄａｔｅ要求を送信する経路として、ノード２、ノード３、ノード５を辿る経路と、ノード２、ノード４、ノード５を辿る経路を識別する。
【００２９】
そして、ノード２は、ヘッダにｕｐｄａｔｅ要求を転送する経路を示す経路情報を埋め込んだｕｐｄａｔｅ要求をノード３およびノード４に転送する。このような場合には、ノード３は、レプリカＡ２の更新準備を行うとともに、ｕｐｄａｔｅ要求のヘッダに埋め込まれた経路情報を参照し、ｕｐｄａｔｅ要求の転送先としてノード５を識別する。そして、ノード３は、ｕｐｄａｔｅ要求をノード５に転送する。
【００３０】
また、ノード４は、ｕｐｄａｔｅ要求を受信した場合には、レプリカＡ３の更新準備を行うとともに、ｕｐｄａｔｅ要求のヘッダに埋め込まれた経路情報を参照し、ｕｐｄａｔｅ要求の転送先としてノード５を識別する。そして、ノード４は、ｕｐｄａｔｅ要求をノード５に転送する。
【００３１】
また、ノード５は、ノード３またはノード４からｕｐｄａｔｅ要求を取得した場合には、経路情報を参照し、自身が複数の経路において終端となるノードであると判別する。このような場合には、ノード５は、ｕｐｄａｔｅ要求が転送される全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する。
【００３２】
そして、ノード５は、全ての経路を介してｕｐｄａｔｅ要求を受信した場合、すなわち、ノード３およびノード４からｕｐｄａｔｅ要求を受信した場合には、レプリカＡ４の更新を行うとともに、ｕｐｄａｔｅ要求に対する応答であるｕｐｄａｔｅｄ要求をノード３およびノード４に送信する。
【００３３】
また、ノード３およびノード４は、ノード５からｕｐｄａｔｅｄ要求を受信した場合には、レプリカＡ２およびレプリカＡ３の更新を行うとともに、ノード２へｕｐｄａｔｅｄ要求を転送する。また、ノード２は、ノード３またはノード４のいずれかからｕｐｄａｔｅｄ要求を取得した場合には、レプリカＡ１の更新を行うとともに、クライアント７に更新が終了した旨の通知を送信する。
【００３４】
このような処理を実行することで、ノード２〜５は、読み出されるデータの同一性が保証されるＳｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持することができる。また、ノード２〜５は、データＡのレプリカを記憶する全てのノードに対して、複数の経路を介してｕｐｄａｔｅ要求を行き渡らせるので、レプリカの更新に要する時間を短縮することができる。
【００３５】
なお、ノード２〜６は、レプリカＢ１〜Ｂ４およびレプリカＣ１〜Ｃ４についても同様の処理を実行する。このため、ストレージシステム１は、各レプリカの更新に要する時間を短縮することができる。
【００３６】
次に、各ノード２〜６について説明する。まず、図３を用いて、ノード２が複数の経路の始端となる始端ノード、および、ある経路においてｕｐｄａｔｅ要求を転送する中間ノードとして動作する例について説明する。なお、他のノード３〜６についても図２に示す各部を有するものとする。すなわち、各ノード２〜６は、記憶するレプリカや、ストレージシステム１の設定に応じて、クライアント７からＰｕｔ要求を受付ける始端ノードとして動作することができる。
【００３７】
図３は、実施例１に関わる始端ノードの一例を説明するための図である。図３に示す例では、始端ノードとして動作するノード２は、ネットワークインターフェース１０、要求送信元判断部１１、クライアント要求受信部１２、クライアント要求処理部１３、ノード間要求受信部１４、ノード間要求処理部１５を有する。また、ノード２は、データ記憶部１６、要求発行部１７、要求発行認証部１８、クライアント位置記憶部１９、トポロジー計算部２０、ノード間要求並列送信部２１、クライアント位置判断部２２、クライアント要求送信部２３を有する。
【００３８】
以下、ノード２が有する各部１０〜２３について説明する。まず、ノード２が有するデータ記憶部１６について説明する。データ記憶部１６は、レプリカのデータや、他のノードの設置位置等を記憶する記憶部である。例えば、データ記憶部１６は、ノード２がデータＡのレプリカＡ１〜Ａ４を更新する際に始端ノードとなる場合には、各レプリカＡ１〜Ａ４を記憶するノードを示す情報を記憶する。また、データ記憶部１６は、各ノード２〜６が設置された位置を示す位置情報を記憶する。
【００３９】
図４ａは、実施例１に関わるデータ記憶部が記憶する位置情報の一例を説明するための図である。図４ａに示す例では、データ記憶部１６は、ノード２がデータセンター＃１のラックＲ１に設置されている旨を示す位置情報と、ノード３がデータセンター＃１のラックＲ２に設置されている旨を示す位置情報とを記憶する。
【００４０】
また、データ記憶部１６は、ノード４がデータセンター＃２のラックＲ３に設置されている旨を示す位置情報と、ノード５がデータセンター＃２のラックＲ４に設置されている旨を示す位置情報とを記憶する。また、データ記憶部１６は、ノード６がデータセンター＃３のラックＲ５に設置されている旨を示す位置情報を記憶する。
【００４１】
図４ｂは、実施例１に関わるデータ記憶部が記憶する各レプリカＡ１〜Ａ４を記憶するノードを示す情報の一例を説明するための図である。図４ｂに示す例では、データ記憶部１６は、レプリカＡ１がノード２に、レプリカＡ２がノード３に、レプリカＡ３がノード４に、レプリカＡ４がノード５に記憶されている旨を示す情報を記憶する。
【００４２】
以下に示すように、ノード２は、始端ノードとして動作する場合には、データ記憶部１６が記憶する各情報を用いて、ｕｐｄａｔｅ要求を行き渡らせるノードと、ｕｐｄａｔｅ要求を転送する複数の経路とを識別する。そして、ノード２は、識別した複数の経路において自身と隣接するノードに対してｕｐｄａｔｅ要求を送信する。
【００４３】
図３に戻って、クライアント位置記憶部１９は、ノード２に対してＰｕｔ要求やＧｅｔ要求を発行したクライアントを示す情報を記憶する記憶部である。例えば、クライアント位置記憶部１９は、ノード２に対してＰｕｔ要求を発行したクライアント７のＩＰアドレス等を記憶する。
【００４４】
ネットワークインターフェース１０は、ＩＰ網８を介して、クライアント７が発行するＰｕｔ要求、および、他のノード３〜６が送信したｕｐｄａｔｅ要求やｕｐｄａｔｅｄ要求を受信する。このような場合には、ネットワークインターフェース１０は、受信したＰｕｔ要求、ｕｐｄａｔｅ要求、および、ｕｐｄａｔｅｄ要求を要求送信元判断部１１に出力する。
【００４５】
また、ネットワークインターフェース１０は、ノード間要求並列送信部２１からｕｐｄａｔｅ要求やｕｐｄａｔｅｄ要求を取得した場合には、取得したｕｐｄａｔｅ要求やｕｐｄａｔｅｄ要求を他のノード３〜６に送信する。また、ネットワークインターフェース１０は、クライアント要求送信部２３からレプリカのデータや更新処理が終了した旨の通知を取得した場合には、取得したデータや通知をクライアント７に送信する。
【００４６】
要求送信元判断部１１は、ネットワークインターフェース１０が取得した各要求を取得した場合には、取得した要求がＰｕｔ要求であるか否かを判別する。そして、要求送信元判断部１１は、取得した要求がＰｕｔ要求である場合には、取得したＰｕｔ要求をクライアント要求受信部１２に出力する。一方、要求送信元判断部１１は、取得した要求がＰｕｔ要求ではない場合には、すなわち、取得した要求がｕｐｄａｔｅ要求またはｕｐｄａｔｅｄ要求である場合には、取得した要求をノード間要求受信部１４に出力する。
【００４７】
クライアント要求受信部１２は、要求送信元判断部１１からＰｕｔ要求を取得した場合には、取得したＰｕｔ要求を発行したクライアント７を識別する。そして、クライアント要求受信部１２は、識別したクライアント７の位置情報をクライアント位置記憶部１９に格納する。また、クライアント要求受信部１２は、クライアント要求処理部１３に対して、取得したＰｕｔ要求を出力する。ここで、クライアント７の位置情報の例としては、クライアント７のＩＰアドレス等、クライアント７を一意に示す番号である。
【００４８】
クライアント要求処理部１３は、クライアント要求受信部１２から取得したＰｕｔ要求に対する処理を実行する。例えば、クライアント要求処理部１３は、クライアント要求受信部１２からＰｕｔ要求を取得した場合には、Ｐｕｔ要求の対象となるレプリカのデータをデータ記憶部１６から検索する。
【００４９】
そして、クライアント要求処理部１３は、検出したレプリカのデータをＰｕｔ要求に従って更新した更新後のデータを新たに生成し、更新後のデータを更新前のデータとは別にデータ記憶部１６に格納する。また、クライアント要求処理部１３は、ｕｐｄａｔｅ要求の発行を要求発行部１７に指示する。
【００５０】
ノード間要求受信部１４は、要求送信元判断部１１からｕｐｄａｔｅ要求を取得した場合には、ｕｐｄａｔｅ要求をノード間要求処理部１５に出力する。また、ノード間要求受信部１４は、要求送信元判断部１１からｕｐｄａｔｅｄ要求を取得した場合には、ｕｐｄａｔｅｄ要求をノード間要求処理部１５に出力する。
【００５１】
ノード間要求処理部１５は、ノード間要求受信部１４からｕｐｄａｔｅ要求を取得した場合には、以下の処理を実行する。まず、ノード間要求処理部１５は、更新対象となるレプリカをデータ記憶部１６から検索し、検索したレプリカのデータを更新した更新後のデータを生成する。そして、ノード間要求処理部１５は、更新後のデータを更新前のデータとともにデータ記憶部１６に格納する。また、ノード間要求処理部１５は、ノード間要求受信部１４が出力したｕｐｄａｔｅ要求を要求発行部１７に出力するとともに、ｕｐｄａｔｅ要求の転送処理の実行を指示する。
【００５２】
また、ノード間要求処理部１５は、ノード間要求受信部１４からｕｐｄａｔｅｄ要求を取得した場合には、以下の処理を実行する。まず、ノード間要求処理部１５は、クライアント要求処理部１３が更新前のレプリカのデータをデータ記憶部１６から削除する。次に、ノード間要求処理部１５は、ノード間要求受信部１４が受信したｕｐｄａｔｅｄ要求が、ノード２が発行したｕｐｄａｔｅ要求に対する応答として発行されたｕｐｄａｔｅｄ要求であるか否かを判別する。
【００５３】
そして、ノード間要求処理部１５は、ノード間要求受信部１４が取得したｕｐｄａｔｅｄ要求が、ノード２が始端ノードとして発行したｕｐｄａｔｅ要求に対する応答として発行されたｕｐｄａｔｅｄ要求であると判別した場合には、以下の処理を実行する。すなわち、ノード間要求処理部１５は、Ｐｕｔ要求が完了した旨を通知するＰｕｔ返答を発行するよう要求発行部１７に指示する。なお、ノード２が始端ノードである場合には、複数の経路を介して複数のｕｐｄａｔｅｄ要求を受信することとなるが、ノード間要求処理部１５は、最初にｕｐｄａｔｅｄ要求をノード２が受信した時点で、更新前のレプリカのデータを削除する。
【００５４】
一方、ノード間要求処理部１５は、ノード間要求受信部１４が取得したｕｐｄａｔｅｄ要求が、ノード２が始端ノードとして発行したｕｐｄａｔｅｄ要求に対応するｕｐｄａｔｅｄ要求ではないと判別した場合には、以下の処理を実行する。すなわち、ノード間要求処理部１５は、ノード間要求処理部１５が更新する前のレプリカのデータをデータ記憶部１６から削除する。そして、ノード間要求処理部１５は、ノード間要求受信部１４が出力したｕｐｄａｔｅｄ要求を要求発行部１７に出力するとともに、ｕｐｄａｔｅｄ要求の転送を行うよう指示する。
【００５５】
要求発行部１７は、クライアント要求処理部１３からｕｐｄａｔｅ要求の発行を指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、データ記憶部１６を参照し、ｕｐｄａｔｅ要求を送信するノード、すなわち、更新対象となるレプリカを記憶するノードを識別する。また、要求発行部１７は、判別したノードの位置情報をデータ記憶部１６から取得する。そして、要求発行部１７は、ｕｐｄａｔｅ要求を生成し、生成したｕｐｄａｔｅ要求を送信するようトポロジー計算部２０に指示する。この際、要求発行部１７は、取得したノードの位置情報をトポロジー計算部２０に送信する。
【００５６】
また、要求発行部１７は、ノード間要求処理部１５からｕｐｄａｔｅ要求の転送処理の実行を指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、ノード間要求処理部１５が出力したｕｐｄａｔｅ要求をトポロジー計算部２０に出力するとともに、ｕｐｄａｔｅ要求を転送するよう指示する。
【００５７】
また、要求発行部１７は、ノード間要求処理部１５からｕｐｄａｔｅｄ要求の転送処理の実行を指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、ノード間要求処理部１５が出力したｕｐｄａｔｅｄ要求をトポロジー計算部２０に出力するとともに、ｕｐｄａｔｅｄ要求を転送するように指示する。
【００５８】
また、要求発行部１７は、ノード間要求処理部１５からＰｕｔ返答を発行するよう指示された場合には、以下の処理を実行する。すなわち、要求発行部１７は、要求発行認証部１８にＰｕｔ返答を発行すべきか否かを判別するよう指示する。
【００５９】
そして、要求発行部１７は、要求発行認証部１８からＰｕｔ返答を発行すべきである旨の通知を受けた場合には、Ｐｕｔ返答を生成し、生成したＰｕｔ返答を発行するようクライアント位置判断部２２に指示する。一方、要求発行部１７は、要求発行認証部１８からＰｕｔ返答を発行すべきではない旨の通知を受けた場合には、処理を終了する。
【００６０】
要求発行認証部１８は、要求発行部１７からＰｕｔ返答を発行すべきか否かを判別するよう指示された場合には、以下の処理を実行する。すなわち、要求発行認証部１８は、要求発行部１７が同一のＰｕｔ返答を発行した旨を記憶しているか否かを判別する。
【００６１】
そして、要求発行認証部１８は、同一のＰｕｔ返答を発行した旨を記憶していない場合には、Ｐｕｔ返答を発行すべき旨を要求発行部１７に通知するとともに、このＰｕｔ返答を発行した旨を記憶する。一方、要求発行認証部１８は、同一のＰｕｔ返答を発行した旨を記憶している場合には、Ｐｕｔ返答を発行すべきでない旨を要求発行部１７に通知する。
【００６２】
トポロジー計算部２０は、ｕｐｄａｔｅ要求を送信するよう指示された場合には、以下の処理を実行する。まず、トポロジー計算部２０は、要求発行部１７からノードの位置情報を取得する。そして、トポロジー計算部２０は、取得したノードの位置情報を用いて、ｕｐｄａｔｅ要求を転送する複数の経路を識別する。
【００６３】
この際、トポロジー計算部２０は、相互に設置位置が近いノードを同じ経路とする複数の経路を識別する。また、トポロジー計算部２０は、各経路の終端ノードが同一のノードとなる複数の経路を識別する。そして、トポロジー計算部２０は、識別した複数の経路を示す経路情報をｕｐｄａｔｅ要求のヘッダに格納し、経路情報を格納したｕｐｄａｔｅ要求をノード間要求並列送信部２１に出力するとともに、ｕｐｄａｔｅ要求を送信するよう指示する。
【００６４】
例えば、ノード２がクライアント７からデータＡのレプリカＡ１〜Ａ４に関わるＰｕｔ要求を受付けた場合には、トポロジー計算部２０は、要求発行部１７からｕｄａｔｅ要求を取得するとともに、図４ａに例示する各ノード２〜５の位置情報を取得する。このような場合には、ノード２は、データセンター＃１にノード２、ノード３が設置され、データセンター＃２にノード４、ノード５が設置されていると判別する。
【００６５】
このように各ノード２〜５が設置されている際に、データセンターをまたぐ経路では、ｕｐｄａｔｅ要求を送信する際のレイテンシが増大してしまう。このため、トポロジー計算部２０は、可能な限りデータセンターをまたがない経路を識別する。また、トポロジー計算部２０は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙの保持を容易にするため、各経路の終端ノードを同一のノードとする。
【００６６】
すなわち、ｕｐｄｅｔｅ要求を転送する経路の終端ノードが複数存在する場合には、ｕｐｄａｔｅ要求を取得し、ｕｐｄａｔｅｄ要求を取得するまでの間にＧｅｔ要求を取得すると、問合せ先とする終端ノードを選択するアルゴリズムが複雑となってしまう。そこで、トポロジー計算部２０は、各経路の終端ノードを同一のノードとする。
【００６７】
例えば、図４ａに示すように、各ノード２〜６が設置され、各ノード２〜５がレプリカＡ１〜Ａ４を記憶している際に、クライアント７がデータＡに関わるＰｕｔ要求を発行した場合には、トポロジー計算部２０は、以下のような複数の経路を識別する。すなわち、トポロジー計算部２０は、ノード２を始端ノードとし、ノード３を経由してノード５を終端ノードとする経路、および、ノード２を始端ノードとし、ノード４を経由してノード５を終端ノードとする経路を識別する。
【００６８】
また、トポロジー計算部２０は、要求発行部１７からｕｐｄａｔｅ要求を取得するとともに、ｕｐｄａｔｅ要求を転送するよう指示された場合には、以下の処理を実行する。すなわち、トポロジー計算部２０は、ｕｐｄａｔｅ要求をノード間要求並列送信部２１に出力するとともに、ｕｐｄａｔｅ要求を転送するようノード間要求並列送信部２１に指示する。
【００６９】
また、トポロジー計算部２０は、要求発行部１７からｕｐｄａｔｅｄ要求を取得するとともに、ｕｐｄａｔｅｄ要求を転送するよう指示された場合には、以下の処理を実行する。すなわち、トポロジー計算部２０は、ｕｐｄａｔｅｄ要求をノード間要求並列送信部２１に出力するとともに、ｕｐｄａｔｅｄ要求を転送するようノード間要求並列送信部２１に指示する。
【００７０】
ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求をトポロジー計算部２０から取得するとともに、ｕｐｄａｔｅｄ要求を送信するよう指示された場合には、以下の処理を実行する。すなわち、ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求に格納された経路情報が示す複数の経路において、始端ノードであるノード２の次にｕｐｄａｔｅ要求が送信される複数のノードを識別する。そして、ノード間要求並列送信部２１は、ネットワークインターフェース１０およびＩＰ網８を介して、識別した複数のノードにｕｐｄａｔｅ要求を送信する。
【００７１】
例えば、ノード間要求並列送信部２１は、経路情報を解析し、ノード２を始端ノードとし、ノード３を経由してノード５を終端ノードとする経路を識別する。また、ノード間要求並列送信部２１は、ノード２を始端ノードとし、ノード４を経由してノード５を終端ノードとする経路を識別する。このような場合には、ノード間要求並列送信部２１は、ノード３およびノード４にｕｐｄａｔｅ要求を送信する。
【００７２】
また、ノード間要求並列送信部２１は、ｕｐａｄｔｅ要求を取得するとともにｕｐｄａｔｅ要求を転送する旨の指示を受付けた場合には、以下の処理を実行する。まず、ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求に格納された経路情報を解析し、ノード２の次にｕｐｄａｔｅ要求を転送すべきノードを識別する。そして、ノード間要求並列送信部２１は、ネットワークインターフェース１０を介して、識別したノードにｕｐｄａｔｅｄ要求を転送する。
【００７３】
また、ノード間要求並列送信部２１は、ｕｐａｄｔｅｄ要求を取得するとともにｕｐｄａｔｅｄ要求を転送する旨の指示を受付けた場合には、以下の処理を実行する。まず、後述するように、ｕｐｄａｔｅｄ要求を転送する経路を示す経路情報が格納されているので、ノード間要求並列送信部２１は、ｕｐｄａｔｅ要求に格納された経路情報を解析し、ノード２の次にｕｐｄａｔｅｄ要求を転送すべきノードを識別する。そして、ノード間要求並列送信部２１は、ネットワークインターフェース１０を介して、識別したノードにｕｐｄａｔｅｄ要求を転送する。
【００７４】
クライアント位置判断部２２は、要求発行部１７からレプリカのデータを取得するとともに、クライアント７に送信するよう指示された場合には、以下の処理を実行する。すなわち、クライアント位置判断部２２は、クライアント位置記憶部１９からクライアント７の位置情報、例えば、クライアント７のＩＰアドレスを取得する。そして、クライアント位置判断部２２は、レプリカのデータとクライアント７の位置情報とをクライアント要求送信部２３に出力する。
【００７５】
また、クライアント位置判断部２２は、要求発行部１７からＰｕｔ返答を発行する旨を指示された場合には、以下の処理を実行する。すなわち、クライアント位置判断部２２は、クライアント位置記憶部１９からＰｕｔ返答の発行先となるクライアントの位置情報を取得する。そして、クライアント位置判断部２２は、クライアントの位置情報とＰｕｔ返答とをクライアント要求送信部２３に出力する。
【００７６】
また、クライアント要求送信部２３は、クライアント位置判断部からＰｕｔ返答とクライアントの位置情報とを取得した場合には、ネットワークインターフェース１０およびＩＰ網８を介して、Ｐｕｔ返答をクライアントに送信する。例えば、クライアント要求送信部２３は、クライアント７の位置情報とＰｕｔ返答とを取得した場合には、クライアント７にＰｕｔ応答を送信する。
【００７７】
次に、図５を用いて、クライアント７が発行したＰｕｔ要求を取得した際に始端ノードとなるノード２が実行する処理の一例について説明する。図５は、実施例１に関わる始端ノードがｕｐｄａｔｅ要求を発行する処理の一例を説明するための図である。なお、図５に示す例では、クライアント７は、データＡの複製であるレプリカＡ１〜Ａ４を更新対象とするＰｕｔ要求を発行したものとする。
【００７８】
例えば、図５に示す例では、ノード２は、図５中（１）に示すように、Ｐｕｔ要求を取得する。このような場合には、要求送信元判断部１１は、図５中（２）に示すように、Ｐｕｔ要求をクライアント要求受信部１２に出力する。クライアント要求受信部１２は、図５中（３）に示すように、クライアント７の位置情報をクライアント位置記憶部１９に格納するとともに、図５中（４）に示すように、クライアント要求処理部１３にＰｕｔ要求を出力する。
【００７９】
このような場合には、クライアント要求処理部１３は、データ記憶部１６に記憶されたレプリカＡ１の更新後のデータを生成するとともに、要求発行部１７にレプリカＡ１〜Ａ４の更新を要求するｕｐｄａｔｅ要求の発行を指示する。すると、要求発行部１７は、図５中（５）に示すように、データ記憶部１６からレプリカＡ１〜Ａ４を記憶する各ノード２〜５の位置情報を取得し、図５中（６）に示すように、トポロジー計算部２０にｕｐｄａｔｅ要求と各ノード２〜５の位置情報を送信する。
【００８０】
このような場合には、トポロジー計算部２０は、位置情報に基づいて、各ノード２〜５にｕｐｄａｔｅ要求を行き渡らせるための複数の経路を識別する。そして、トポロジー計算部２０は、図５中（７）に示すように、識別した複数の経路を示す経路情報を格納したｕｐａｔｅ要求をノード間要求並列送信部２１に出力する。すると、図５中（８）に示すように、ノード間要求並列送信部２１は、経路情報が示す次のノードにｕｐｄａｔｅ要求を送信する。
【００８１】
次に、図６を用いて、ｕｐｄａｔｅｄ要求を取得した際に始端ノードとなるノード２が実行する処理の一例について説明する。図６は、実施例１に関わる始端ノードがｕｐｄａｔｅｄ要求を受信した際に実行する処理の一例を説明するための図である。例えば、図６中（１）に示すように、ｕｐｄａｔｅｄ要求を取得した場合には、要求送信元判断部１１は、図６中（２）に示すように、ｕｐｄａｔｅｄ要求をノード間要求受信部１４に出力する。このような場合には、ノード間要求受信部１４は、図６中（３）に示すように、ｕｐｄａｔｅｄ要求をノード間要求処理部１５に出力する。
【００８２】
すると、ノード間要求処理部１５は、図６中（４）に示すように、更新前のレプリカＡ１をデータ記憶部１６から削除するとともに、要求発行部１７にＰｕｔ返答を出力する旨を指示する。このような場合には、図６中（５）に示すように、要求発行部１７は、Ｐｕｔ返答を出力すべきか否かを要求発行認証部１８に判別させる。そして、要求発行部１７は、Ｐｕｔ返答を出力すべき旨を取得した場合には、図６中（６）に示すように、Ｐｕｔ返答を出力するようクライアント位置判断部２２に指示する。
【００８３】
すると、クライアント位置判断部２２は、クライアント位置記憶部１９からＰｕｔ応答の送信先となるクライアント７の位置情報を取得し、図６中（７）に示すように、Ｐｕｔ応答と取得した位置情報とをクライアント要求送信部２３に出力する。このような場合には、クライアント要求送信部２３は、図６中（８）に示すように、ネットワークインターフェース１０およびＩＰ網８を介して、クライアント７にＰｕｔ返答を送信する。
【００８４】
次に、図７を用いて、終端ノードとして動作するノード５が実行する処理について説明する。図７は、実施例１に関わる終端ノードの一例を説明するための図である。なお、図３に示した各部１０〜２３と同様の機能を発揮するものについては、同一の符号を付し、以下の説明を省略する。また、他のノード２〜４、ノード６についても図７に示す各部を有するものとする。すなわち、各ノード２〜６は、記憶するレプリカや、ストレージシステム１の設定に応じて、終端ノードとして動作することができる。
【００８５】
なお、図７に示す例では、終端ノードとして動作するノード５は、ノード間要求受信部１４とノード間要求処理部１５ａとの間に要求収集部２４を有する。このため、ノード間要求受信部１４は、ノード５がノード３、４から受信するｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求をノード間要求処理部１５ａではなく要求収集部２４に出力することとなる。
【００８６】
ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、クライアント要求受信部１２ａ、クライアント要求処理部１３ａは、図３に示す各部１０〜１３と同様の機能を発揮する。また、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、クライアント要求受信部１２ａは、クライアント７からＧｅｔ要求を受信した場合には、受信したＧｅｔ要求をクライアント要求処理部１３ａに伝達する。
【００８７】
クライアント要求処理部１３ａは、Ｇｅｔ要求取得した場合にはデータ記憶部１６からＧｅｔ要求の対象となるレプリカのデータを検索する。そして、クライアント要求は、検索したレプリカのデータを要求発行部１７ａに出力するとともに、データをクライアントに送信するよう指示する。
【００８８】
このような場合には、要求処理部１３ａは、クライアント位置判断部２２を介して、クライアント要求送信部２３に、取得したデータをクライアント７に送信するよう指示する。その後、クライアント要求送信部２３は、クライアント７にデータを送信する。
【００８９】
要求収集部２４は、ノード間要求受信部１４からｕｐｄａｔｅ要求を取得した場合には、取得したｕｐｄａｔｅ要求に格納された経路情報を解析し、経路情報が示す経路においてノード５が終端ノードとなるか否かを判別する。そして、要求収集部２４は、経路情報が示す経路においてノード５が終端ノードとなる場合には、取得したｕｐｄａｔｅ要求を保持する。
【００９０】
また、要求収集部２４は、保持したｕｐｄａｔｅ要求の経路情報を解析し、同一のレプリカを更新対象とするｕｐｄａｔｅ要求を、経路情報が示す全ての経路の数だけ保持したか否かを判別する。すなわち、要求収集部２４は、全ての経路を介して転送されたｕｐｄａｔｅ要求をノード５が受信したか否かを判別する。
【００９１】
そして、要求収集部２４は、同一のレプリカを更新対象とするｕｐｄａｔｅ要求を、経路情報が示す全ての経路の数だけ保持したと判別した場合には、いずれか１つのｕｐｄａｔｅ要求をノード間要求処理部１５ａに出力する。また、要求収集部２４は、同一のレプリカを更新対象とするｕｐｄａｔｅ要求を、経路情報が示す全ての経路の数だけ保持していないと判別した場合には、残りのｕｐｄａｔｅ要求を取得するまで待機する。
【００９２】
また、要求収集部２４は、経路情報が示す経路においてノード５が終端ノードとはならない場合には、取得したｕｐｄａｔｅ要求うちの１つをノード間要求処理部１５ａに出力するとともに、ｕｐｄａｔｅｄ要求の発行を指示する。また、要求収集部２４は、ノード間要求受信部１４からｕｐｄａｔｅｄ要求を取得した場合には、取得したｕｐｄａｔｅｄ要求をノード間要求処理部１５ａに出力する。
【００９３】
ノード間要求処理部１５ａは、図３に示すノード間要求処理部１５と同様の処理を実行する。さらに、ノード間要求処理部１５ａは、要求収集部２４からｕｐｄａｔｅ要求を取得するとともに、ｕｐｄａｔｅｄ要求の発行を指示された場合には、以下の処理を実行する。
【００９４】
すなわち、ノード間要求処理部１５ａは、データ記憶部１６に格納されたｕｐｄａｔｅ要求の対象となるレプリカのデータを検索し、検索したデータを更新した更新後のレプリカのデータのみをデータ記憶部１６に格納する。また、ノード間要求処理部１５ａは、要求発行部１７ａに対して、ｕｐｄａｔｅｄ要求の発行を指示するとともに、ｕｐｄａｔｅ要求に格納されていた経路情報を出力する。
【００９５】
要求発行部１７ａは、図３に示す要求発行部１７と同様の機能を発揮するとともに、ノード間要求処理部１５ａからｕｐｄａｔｅｄ要求の発行を指示された場合には、ｕｐｄａｔｅｄ要求を生成する。そして、要求発行部１７ａは、トポロジー計算部２０ａに生成したｕｐｄａｔｅｄ要求と、ノード間要求処理部１５ａから取得した経路情報を出力する。
【００９６】
トポロジー計算部２０ａは、図３に示すトポロジー計算部２０と同様の機能を発揮するとともに、要求発行部１７ａからｕｐｄａｔｅｄ要求と経路情報とを取得した場合には、以下の処理を実行する。すなわち、トポロジー計算部２０ａは、取得した経路情報が示す複数の経路を逆に辿る新たな経路情報を生成する。そして、トポロジー計算部２０ａは、取得したｕｐｄａｔｅｄ要求のヘッダに新たな経路情報を格納し、ｕｐｄａｔｅｄ要求をノード間要求並列送信部２１に出力する。
【００９７】
このように、ノード２は、自身を始端ノードとする複数の経路を識別し、識別した経路において自身と隣接する複数のノードに対してｕｐｄａｔｅ要求を送信することで、ｕｐｄａｔｅ要求を各ノード２〜５に送信する。このため、ノード２は、複数の経路を介して、各経路上のノードにｕｐｄａｔｅ要求を並行して送信するので、レプリカの更新に要する時間を短縮することができる。
【００９８】
また、ノード５は、自身を終端ノードとするｕｐｄａｔｅ要求を、全ての経路から受信するのを待機する。そして、ノード５は、自身を終端ノードとするｕｐｄａｔｅ要求を全ての経路から受信した場合には、ｕｐｄａｔｅｄ要求を全ての経路を介して始端ノードに送信する。このため、ストレージシステム１は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持しつつ、レプリカの更新に要する時間を短縮することができる。
【００９９】
次に、図８を用いて、終端ノードであるノード５が実行する処理の一例を説明する。図８は、実施例１に関わる終端ノードが実行する処理の一例を説明するための図である。例えば、図８中（１）に示すように、ネットワークインターフェース１０ａは、他のノード２〜６からｕｐｄａｔｅ要求を受信した場合には、受信したｕｐｄａｔｅ要求を要求送信元判断部１１に出力する。
【０１００】
また、要求送信元判断部１１ａは、図８中（２）に示すように、ｕｐｄａｔｅ要求をノード間要求受信部１４に出力する。また、ノード間要求受信部１４は、図８中（３）に示すように、ｕｐｄａｔｅ要求を要求収集部２４に出力する。このような場合には、要求収集部２４は、ｕｐｄａｔｅ要求の経路情報が示す全ての経路を介して、同一のレプリカを対象とするｕｐｄａｔｅ要求を取得したか否かを判別する。そして、要求収集部２４は、全ての経路を介して、同一のレプリカを対象とするｕｐｄａｔｅ要求を取得したと判別した場合には、図８中（４）に示すように、ｕｐｄａｔｅ要求をノード間要求処置部１５ａに送信する。
【０１０１】
すると、ノード間要求処理部１５ａは、データ記憶部１６に記憶されたレプリカを更新するとともに、図８中（５）に示すように、要求発行部１７ａにｕｐｄａｔｅｄ要求を発行する旨を指示する。すると、要求発行部１７ａは、ｕｐｄａｔｅｄ要求を生成し、図８中（６）に示すように、ｕｐｄａｔｅｄ要求を送信するようトポロジー計算部２０ａに指示する。
【０１０２】
このような場合には、トポロジー計算部２０ａは、ｕｐｄａｔｅ要求に格納された経路情報が示す全ての経路を逆に辿る経路を示す新たな経路情報を識別し、新たな経路情報をｕｐｄａｔｅｄ要求のヘッダに格納する。そして、トポロジー計算部２０ａは、図８中（７）に示すように、ノード間要求並列送信部２１にｕｐｄａｔｅｄ要求の送信を指示する。このような場合には、ノード間要求並列送信部２１は、図８中（８）に示すように、ネットワークインターフェース１０ａを介して、ｕｐｄａｔｅｄ要求を送信する。
【０１０３】
次に、図９ａ、図９ｂを用いて、実施例１に関わるストレージシステム１が、複数の経路を介して、ｕｐｄａｔｅ要求を始端ノードから終端ノードにまで順次転送し、ｕｐｄａｔｅｄ要求を終端ノードから始端ノードまで順次転送する処理について説明する。
【０１０４】
図９ａは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。また、図９ｂは、実施例１に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。なお、図９ａ、図９ｂに示す例では、１ｓｔノードから７ｔｈノードまでの７個のノードが記憶するレプリカの更新を行う例について説明する。
【０１０５】
例えば、クライアント７は、図９ａ中（Ｄ）に示すように、Ｐｕｔ要求を１ｓｔノードに発行する。このような場合には、１ｓｔノードは、Ｐｕｔ要求の対象となるレプリカを記憶する全てのノード、すなわち、１ｓｔノードから７ｔｈノードを識別する。
【０１０６】
そして、図９ａに示す例では、１ｓｔノードは、自身を始端ノードとし、７ｔｈノードを終端とする３つの経路を識別する。詳細には、１ｓｔノードは、１ｓｔノード、２ｎｄノード、５ｔｈノード、７ｔｈノードを接続する経路、１ｓｔノード、３ｒｄノード、７ｔｈノードを接続する経路、１ｓｔノード、４ｔｈノード、６ｔｈノードを接続する経路を識別する。
【０１０７】
そして、１ｓｔノードは、図９ａ中（Ｅ）に示すように、ｕｐｄａｔｅ要求を２ｎｄノード、３ｒｄノード、４ｔｈノードに送信する。このような場合には、２ｎｄノードはｕｐｄａｔｅ要求を５ｔｈノードに転送し、５ｔｈノードはｕｐｄａｔｅ要求を７ｔｈノードに転送する。また、３ｒｄノードは、ｕｐｄａｔｅ要求を７ｔｈノードに転送する。また、４ｔｈノードは、ｕｐｄａｔｅ要求を６ｔｈノードに転送し、６ｔｈノードは、ｕｐｄａｔｅ要求を７ｔｈノードに転送する。
【０１０８】
ここで、７ｔｈノードは、図９ａに示す３つの全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機し、全ての経路を介してｕｐｄａｔｅ要求を受信したと判別した場合には、ｕｐｄａｔｅｄ要求を生成する。そして、図９ｂ中（Ｆ）に示すように、ｕｐｄａｔｅｄ要求を５ｔｈノード、３ｒｄノード、６ｔｈノードに送信する。このような場合には、２ｎｄノード〜６ｔｈノードは、各経路を逆に辿るようにｕｐｄａｔｅｄ要求を１ｓｔノードまで順次転送する。そして、１ｓｔノードは、いずれかの経路を介してｕｐｄａｔｅｄ要求を取得した場合には、図９ｂ中（Ｇ）に示すように、Ｐｕｔ応答をクライアント７に送信する。
【０１０９】
ここで、従来のストレージシステムは、１ｓｔノードから７ｔｈノードまで１つの経路を介して順次ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を順次転送するので、６回の転送を実行する。しかし、ストレージシステム１は、複数の経路を介してｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を順次転送するので、図９ａ、図９ｂに示す例では、最大で３回の転送でよい。このため、図９ａ、図９ｂに示す例では、ストレージシステム１は、従来の１／２の時間で更新処理を実行することができる。
【０１１０】
例えば、ネットワークインターフェース１０、１０ａ、要求送信元判断部１１、１１ａ、クライアント要求受信部１２、１２ａ、クライアント要求処理部１３、１３ａ、ノード間要求受信部１４、ノード間要求処理部１５、１５ａとは、電子回路である。また、要求発行部１７、１７ａ、要求発行認証部１８、クライアント位置記憶部１９、トポロジー計算部２０、２０ａ、ノード間要求並列送信部２１、クライアント位置判断部２２、クライアント要求送信部２３、要求収集部２４とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積回路、またはＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）などを適用する。
【０１１１】
また、データ記憶部１６とは、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、フラッシュメモリ（flash memory）などの半導体メモリ素子、または、ハードディスク、光ディスクなどの記憶装置である。
【０１１２】
次に、図１０を用いて、始端ノードが実行する処理の流れの一例について説明する。図１０は、始端ノードが実行する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明ではノード２が始端ノードとして動作する際に実行する処理の一例について説明する。
【０１１３】
例えば、ノード２は、自身の状態に停止条件が発生しているか否かを判別する（ステップＳ１０１）。ここで、停止条件とは、例えば、Ｐｕｔ要求を受信してからＰｕｔ応答をまだ出力していない場合等に発生する条件である。そして、ノード２は、停止条件が発生していない場合は（ステップＳ１０１否定）、クライアント７からＰｕｔ要求を受信したか否かを判別する（ステップＳ１０２）。
【０１１４】
次に、ノード２は、クライアント７からＰｕｔ要求を受信した場合には（ステップＳ１０２肯定）、ｕｐｄａｔｅ要求を送信する複数の経路を識別するとともに、各経路における次のノードにｕｐｄａｔｅ要求を送信する（ステップＳ１０３）。なお、ノード２は、ｕｐｄａｔｅ要求を送信してからｕｐｄａｔｅｄ要求を受信するまでの間、ｕｐｄａｔｅｉｎｇ状態に移行する。
【０１１５】
次に、ノード２は、ｕｐｄａｔｅ要求を送信したいずれかのノードからｕｐｄａｔｅｄ要求を受信したか否かを判別し（ステップＳ１０４）、受信していない場合には（ステップＳ１０４否定）、ｕｐｄａｔｅｄ要求を受信するまで待機する（ステップＳ１０４）。そして、ノード２は、いずれかのノードからｕｐｄａｔｅｄ要求を受信した場合には（ステップＳ１０４肯定）、クライアントにＰｕｔ返答を送信し、ｕｐｄａｔｅｉｎｇ状態を解除する（ステップＳ１０５）。その後、ノード２は、停止条件が発生しているか否かを判別する（ステップＳ１０１）。
【０１１６】
また、ノード２は、クライアントからＰｕｔ要求を受信していない場合には（ステップＳ１０２否定）、再度停止条件が発生しているか否かを判別する（ステップＳ１０１）。また、ノード２は、停止条件が発生している場合には（ステップＳ１０１肯定）、停止条件が解消されるまで、処理を終了する。
【０１１７】
次に、図１１を用いて、各経路の中間ノードが実行する処理の流れの一例について説明する。図１１は、中間ノードが実行する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明では、ノード３が中間ノードとして動作する際に実行する処理の一例について説明する。
【０１１８】
例えば、ノード３は、停止条件が発生しているか否かを判別し（ステップＳ２０１）、発生していないと判別した場合には（ステップＳ２０１否定）、ｕｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ２０２）。そして、ノード３は、経路の前ノードからｕｐｄａｔｅ要求を受信した場合には（ステップＳ２０２肯定）、経路の次ノードにｕｐｄａｔｅ要求を転送し、ｕｐｄａｔｉｎｇ状態に遷移する（ステップＳ２０３）。
【０１１９】
次に、ノード３は、ｕｐｄａｔｅ要求を転送した次ノードからｕｐｄａｔｅｄ要求を受信するまで待機し（ステップＳ２０４否定）、ｕｐｄａｔｅｄ要求を受信した場合には（ステップＳ２０４肯定）、次の処理を実行する。すなわち、ノード３は、経路の前ノードにｕｐｄａｔｅｄ要求を転送し、ｕｐｄａｔｉｎｇ状態を解除する（ステップＳ２０５）。
【０１２０】
その後、ノード３は、再度停止条件が発生しているか否かを判別し（ステップＳ２０１）、停止条件が発生している場合には（ステップＳ２０１肯定）、停止条件が解消されるまで、処理を終了する。また、ノード３は、前ノードからｕｐｄａｔｅ要求を受信していない場合には（ステップＳ２０２否定）、再度停止条件が発生しているか否かを判別する（ステップＳ２０１）。
【０１２１】
次に、図１２を用いて、終端ノードが実行する処理の流れの一例について説明する。図１２は、終端ノードが実行する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明では、ノード５が終端ノードとして動作する際に実行する処理の一例について説明する。
【０１２２】
まず、ノード５は、停止条件が発生しているか否かを判別し（ステップＳ３０１）、発生していない場合には（ステップＳ３０１否定）、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ３０２）。そして、ノード５は、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信していない場合には（ステップＳ３０２否定）、全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する（ステップＳ３０２）。
【０１２３】
また、ノード５は、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信した場合には（ステップＳ３０２肯定）、レプリカを更新するとともに、各経路の前ノードにｕｐｄａｔｅｄ要求を送信する（ステップＳ３０３）。その後、ノード５は、再度、停止条件が発生しているか否かを判別し（ステップＳ３０１）、発生している場合には（ステップＳ３０１肯定）、停止条件が解消するまで処理を終了する。
【０１２４】
[ストレージシステム１の効果]
上述したように、ノード２は、クライアント７からレプリカＡ１〜Ａ４に対するＰｕｔ要求を受信した場合には、自身を始端とし、複数のノード２〜５を直列に接続する複数の経路を判別する。そして、ノード２は、識別した経路を介して、各経路の終端ノードであるノード５にｕｐｄａｔｅ要求を送信する。その後、ノード２は、いずれかの経路を介してｕｐｄａｔｅｄ要求を受信した場合には、クライアント７にＰｕｔ応答を送信する。
【０１２５】
このため、ノード２は、ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を複数の経路を介して各ノード２〜５に転送させるので、レプリカＡ１〜Ａ４の更新に要する時間を短縮することができる。
【０１２６】
また、ノード２は、各ノード２〜６の設置位置を記憶し、各ノード２〜６のうち、相互に設置位置が近い複数のストレージ装置を直列に接続する複数の経路を識別する。このため、ノード２は、各経路に含まれる複数のノードにｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を効率的に転送させることができる結果、各レプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４の更新に要する時間を短縮することができる。
【０１２７】
また、ノード２は、１つのノード５を終端ノードとする複数の経路を識別する。このため、ノード２は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを容易に保持することができる。
【０１２８】
また、ノード５は、自身を終端とする全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別し、全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する。そして、ノード５は、全ての経路を介してｕｐｄａｔｅ要求を受信した場合には、各経路を介して、ｕｐｄａｔｅｄ要求を始端ノードであるノード２に送信する。このため、ノード５は、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保ちながら、複数の経路を介してｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を転送することができる。
【実施例２】
【０１２９】
次に、実施例２に関わるストレージシステムについて説明する。例えば、実施例１に関わるストレージシステム１は、１つのノードを終端ノードとする複数の経路を介して、ｕｐｄａｔｅ要求とｕｐｄａｔｅｄ要求とを順次転送した。しかし、実施例はこれに限定されるものではない。
【０１３０】
例えば、各経路における終端ノードを異なるノードとした際に、各経路においてｕｐｄａｔｅ要求とｕｐｄａｔｅｄ要求とを転送する回数を減少させられるのであれば、更新に要する時間をより短縮することができる。そこで、以下の説明においては、各経路における終端ノードを異なるノードとするストレージシステム１ａについて説明する。
【０１３１】
図１３は、実施例２に関わるストレージシステムの一例を説明するための図である。図１３に示す例では、ストレージシステム１ａは、ストレージシステム１と同様に各データセンター＃１〜＃３に複数のノード２ａ〜６ａを有する。なお、クライアント７およびＩＰ網８は、実施例１に関わるクライアント７およびＩＰ網８と同様の機能を発揮するものとして、説明を省略する。
【０１３２】
図１４は、実施例２に関わる始端ノードの一例を説明するための図である。なお、図１４に示す例では、始端ノードとして、ノード２ａの一例について説明する。また、他のノード３ａ〜６ａも、同様の機能を発揮できるものとする。また、図１４に示すノード２ａのうち、図３に示すノード２と同様の機能を発揮する部分については、同一の符号を付すものとし、以下の説明を省略する。
【０１３３】
トポロジー計算部２０ｂは、実施例１に関わるトポロジー計算部２０ａと同様の機能を発揮する。また、トポロジー計算部２０ｂは、各経路の終端ノードを異なるノードとした方が更新に要する時間をより短縮できる場合には、終端ノードをそれぞれ異なるノードとする複数の経路を識別する。
【０１３４】
そして、トポロジー計算部２０ｂは、識別した複数の経路を示す経路情報をｕｐｄａｔｅ要求に格納する。例えば、トポロジー計算部２０ｂは、ノード２ａを始端ノードとし、ノード３ａを終端ノードとする経路と、ノード２ａを始端ノードとし、ノード４ａを中間ノードとし、ノード５ａを終端ノードとする経路とを示す経路情報をｕｐｄａｔｅ要求に格納する。
【０１３５】
次に、図１５を用いて、実施例２に関わる終端ノードの一例を説明する。図１５は、実施例２に関わる終端ノードの一例を説明するための図である。なお、以下の説明においては、ノード３ａ、および、ノード５ａが終端ノードである例について説明する。また、他のノード２ａ、４ａ、６ａも、ノード３ａおよびノード５ａと同様の機能を発揮できるものとする。また、図１５に示すノード３ａおよび５ａのうち、図７に示すノード５と同様の機能を発揮する部分については、同一の符号を付すものとし、以下の説明を省略する。
【０１３６】
要求収集部２４ａは、要求収集部２４と同様の機能を有する。また、要求収集部２４ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信した場合は、ノード間要求処理部１５ｂにｕｐｄａｔｅ要求を出力せずに、以下の処理を実行する。
【０１３７】
すなわち、要求収集部２４ａは、ノード間要求処理部１５ｂに対して、ｕｐｄａｔｅ要求を受信した旨を通知するｒｅａｄｙＴｏＵｐｄａｔｅ要求を他の終端ノードに送信するよう指示する。この際、要求収集部２４ａは、ｕｐｄａｔｅ要求に格納されていた経路情報をノード間要求処理部１５ｂに通知する。
【０１３８】
また、要求収集部２４ａは、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、ノード間要求受信部１４を介して、他の終端ノードが発行したｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得する。そして、要求収集部２４ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したか否かを判別する。
【０１３９】
その後、要求収集部２４ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したと判別した場合には、取得したｕｐｄａｔｅ要求のうちの１つをノード間要求処理部１５ｂに出力する。一方、要求収集部２４ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得していないと判別した場合には、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得するまで待機する。
【０１４０】
つまり、要求収集部２４ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得した場合には、他の経路の終端ノードに対してｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。そして、要求収集部２４ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得し、かつ、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得した場合には、以下の処理を実行する。つまり、要求収集部２４ａは、自身を終端ノードとする全ての経路を介して、ｕｐｄａｔｅｄ要求を始端ノードに転送させる。
【０１４１】
ノード間要求処理部１５ｂは、図７に示すノード間要求処理部１５ａと同様の機能を発揮する。また、ノード間要求処理部１５ｂは、要求収集部２４ａから経路情報を取得するとともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示された場合には、以下の処理を実行する。すなわち、ノード間要求処理部１５ｂは、要求発行部１７ｂに経路情報を出力するとともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示する。
【０１４２】
また、ノード間要求処理部１５ｂは、データ記憶部１６に記憶された更新対象となるレプリカのデータを検索し、検索したデータを更新した更新後のデータを生成する。そして、ノード間要求処理部１５ｂは、更新前のレプリカのデータとともに、更新後のレプリカのデータをデータ記憶部１６に格納する。
【０１４３】
また、ノード間要求処理部１５ｂは、ｕｐｄａｔｅ要求を要求収集部２４ａから取得した場合には、データ記憶部１６に記憶された更新前のレプリカのデータを削除する。そして、ノード間要求処理部１５ｂは、要求発行部１７ｂに対して、ｕｐｄａｔｅｄ要求の発行を指示するとともに、ｕｐｄａｔｅ要求に格納されていた経路情報を出力する。
【０１４４】
他終端状態判断部２５は、クライアント要求受信部１２ａが出力したＧｅｔ要求を取得する。このような場合には、他終端状態判断部２５は、要求収集部２４ａが自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別する。そして、他終端状態判断部２５は、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信していないと判別した場合は、クライアント要求処理部１３ａに更新前のレプリカのデータをクライアント７に出力するよう指示する。
【０１４５】
また、他終端状態判断部２５は、要求収集部２４ａが自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信していた場合には、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信したか否かを判別する。そして、他終端状態判断部２５は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していると判別した場合には、クライアント要求処理部１３ａに更新後のレプリカのデータを出力するよう指示する。
【０１４６】
また、他終端状態判断部２５は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していないと判別した場合には、以下の処理を実行する。すなわち、他終端状態判断部２５は、ｕｐｄａｔｅｄ要求の発行を依頼したか否かを他の終端ノードに問合せるようクライアント要求処理部１３ａに指示する。
【０１４７】
そして、他終端状態判断部２５は、いずれかの終端ノードからｕｐｄａｔｅｄ要求の発行を依頼した旨の返答を受信した場合には、クライアント要求処理部１３ａに更新後のレプリカのデータをクライアント７に出力するよう指示する。一方、他終端状態判断部２５は、どの終端ノードからもｕｐｄａｔｅｄ要求の発行を依頼した旨の返答を受信しなかった場合には、クライアント要求処理部１３ａに更新前のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。
【０１４８】
つまり、他終端状態判断部２５は、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信し、かつ、自身を含むいずれかの終端ノードがｕｐｄａｔｅｄ要求の発行を依頼した場合は、Ｇｅｔ要求に対して更新後のレプリカのデータを出力させる。なお、他終端状態判断部２５は、他の終端ノードにｕｐｄａｔｅｄ要求を送信したか否かの問合せを行っている最中に、要求収集部２４ａが全ての終端ノードからｒｅａｄＴｏＵｐｄａｔｅ要求を取得した場合には、問合せを中止する。そして、他終点判断部２５は、更新後のレプリカのデータを出力するようにクライアント要求処理部１３ａに指示する。
【０１４９】
なお、要求収集部２４ａは、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、クライアント要求受信部１２ａを介して、他の終端ノードから送信された問合せを取得する。このような場合には、要求収集部２４ａは、自身がｕｐｄａｔｅｄ要求の発行を指示したか否かを問合せ元の終端ノードに返信するようノード間要求処理部１５ｂに指示する。このような場合には、返信が要求発行部１７ｂ、トポロジー計算部２０ｃ、ノード間要求並列送信部２１を介して、問合せ元の終端ノードに送信される。
【０１５０】
要求発行部１７ｂは、図７に例示した要求発行部１７ａと同様の機能を発揮する。また、要求発行部１７ｂは、経路情報を取得するとともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示された場合には、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を生成する。そして、要求発行部１７ｂは、取得した経路情報とともに、ｒｅａｄｙＴｏＵｐｄａｔｅ要求をトポロジー計算部２０ｃに出力する。
【０１５１】
トポロジー計算部２０ｃは、図７に示すトポロジー計算部２０ａと同様の機能を発揮する。また、トポロジー計算部２０ｃは、経路情報とともにｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得した場合には、取得した経路情報を解析し、自身以外の終端ノードを全て識別する。その後、トポロジー計算部２０ｃは、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を識別した全ての終端ノードに送信するようノード間要求並列送信部２１に指示する。
【０１５２】
このようなノード３ａおよびノード５ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信した場合には、他の終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。そして、ノード３ａおよびノード５ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信し、かつ、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信した場合には、ｕｐｄａｔｅｄ要求を送信することとなる。このため、ストレージシステム１ａは、ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を転送する複数の経路において、終端ノードが同一ではない場合にも、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持したまま、レプリカの更新に要する時間を短縮できる。
【０１５３】
また、ノード３ａおよびノード５ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信してから、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅを受信するまでの間にＧｅｔ要求を受信した場合には、以下の処理を実行する。すなわち、ノード３ａおよびノード５ａは、他の終端ノードにｕｐｄａｔｅｄ要求を発行したか否かを問い合わせることで、ｕｐｄａｔｅｄ要求を発行した終端ノードが存在するか否かを判別する。そして、ノード３ａおよびノード５ａは、いずれかの終端ノードがｕｐｄａｔｅｄ要求を発行した場合には、更新後のレプリカのデータを出力し、いずれの終端ノードもｕｐｄａｔｅｄ要求を発行していない場合には、更新前のレプリカのデータを出力する。
【０１５４】
このため、ストレージシステム１ａは、レプリカの更新中にＧｅｔ要求が発行された場合にも、各経路における更新状況に応じたデータをクライアントに送信することができる。この結果、ストレージシステム１ａは、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持したまま、レプリカの更新に要する時間を短縮できる。
【０１５５】
次に、図１６を用いて、終端ノードであるノード３ａ、ノード５ａがクライアント７からＧｅｔ要求を受信した際に実行する処理の一例について説明する。図１６は、実施例２に関わる終端ノードがＧｅｔ要求を受信した際に実行する処理の一例を説明するための図である。なお、図１６に示す例では、ノード３ａに対してクライアント７がデータＡに関わるレプリカＡ２のＧｅｔ要求を発行した例について説明する。
【０１５６】
まず、図１６中（１）に示すように、ネットワークインターフェース１０ａは、Ｇｅｔ要求を要求送信元判断部１１ａに出力する。このような場合には、要求送信元判断部１１ａは、図１６中（２）に示すように、クライアント要求受信部１２ａに出力する。次に
クライアント要求受信部１２ａは、図１６中（３）に示すように、クライアント７の位置情報をクライアント位置記憶部１９に格納する。また、クライアント要求受信部１２ａは、Ｇｅｔ要求を他終端状態判断部２５に出力する。
【０１５７】
次に、他終端状態判断部２５は、図１６中（４）に示すように、要求収集部２４ａがノード３ａを終端とする全ての経路を介してｕｐｄａｔｅ要求を取得したか否かを判別する。そして、他終端状態判断部２５は、要求収集部２４ａがノード３ａを終端とする全ての経路を介してｕｐｄａｔｅ要求を取得していない場合は、更新前のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。
【０１５８】
また、他終端状態判断部２５は、要求収集部２４ａがノード３ａを終端とする全ての経路を介してｕｐｄａｔｅ要求を取得している場合は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したか否かを判別する。そして、他終端状態判断部２５は、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得していない場合には、図１６中（５）に示すように、他の終端ノードに問合せるよう指示する。
【０１５９】
その後、他終端状態判断部２５は、ｕｐｄａｔｅｄ要求を送信した旨の返信をいずれかの終端ノードから取得した場合には、更新後のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。また、他終端状態判断部２５は、要求収集部２４ａが全ての終端ノードからｒｅａｄｙＴｏｕｐｄａｔｅ要求を取得していた場合には、更新後のレプリカのデータを出力するようクライアント要求処理部１３ａに指示する。すると、クライアント要求処理部１３ａは、要求発行部１７ｂに更新後のレプリカのデータを出力するよう指示する。
【０１６０】
このような場合には、要求発行部１７ｂは、図１６中（６）に示すように、更新後のレプリカのデータを取得し、図１６中（７）に示すように取得したデータをクライアント位置判断部２２に出力する。すると、クライアント位置判断部２２は、クライアント位置記憶部１９からＧｅｔ要求の発行元であるクライアント７の位置情報を取得する。そして、クライアント位置判断部２２は、図１６中（８）に示すように、レプリカのデータとクライアント７の位置情報とをクライアント要求送信部２３に出力する。このような場合には、図１６中（９）に示すように、クライアント要求送信部２３は、ネットワークインターフェース１０ａを介して、クライアント７にレプリカのデータを送信する。
【０１６１】
次に、図１７を用いて、ノード３ａがｕｐｄａｔｅ要求を受信した際に実行する処理の一例について説明する。図１７は、実施例２に関わる終端ノードがｕｐｄａｔｅ要求を受信した際に実行する処理の一例を説明するための図である。例えば、図１７中（１）に示すように、ネットワークインターフェース１０ａは、受信したｕｐｄａｔｅ要求を要求送信元判断部１１ａに送信する。このような場合には、図１７中（２）に示すように、要求元判断部１１ａは、ｕｐｄａｔｅ要求をノード間要求受信部１４に出力し、図１７中（３）に示すように、ノード間要求受信部１４は、ｕｐｄａｔｅｄ要求を要求収集部２４ａに出力する。
【０１６２】
ここで、要求収集部２４ａは、要求収集部２４と同様に、ノード３ａを終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得するまで待機する。そして、要求収集部２４ａは、ノード３ａを終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を取得した場合には、図１７中（４）に示すように、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信するようノード間要求処理部１５ｂに指示する。
【０１６３】
このような場合には、ノード間要求処理部１５ｂは、図１７中（５）に示すように、更新後のレプリカのデータをデータ記憶部１６に格納する。また、ノード間要求処理部１５ｂは、図１７中（６）に示すように、要求発行部１７ｂにｒｅａｄｙＴｏＵｐｄａｔｅ要求の発行を指示する。このような場合には、要求発行部１７ｂ、トポロジー計算部２０ｃ、ノード間要求並列送信部２１は、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を他の終端ノードであるノード５ａに送信する。
【０１６４】
また、図１７中（７）に示すように、要求収集部２４ａは、ネットワークインターフェース１０ａ、要求送信元判断部１１ａ、ノード間要求受信部１４を介して、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得した場合には、以下の処理を実行する。すなわち、要求収集部２４ａは、ノード３ａ以外の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したか否かを判別する。
【０１６５】
そして、要求収集部２４ａは、ノード３ａ以外の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得したと判別した場合には、図１７中（８）に示すように、ノード間要求処理部１５ｂに受信したｕｐｄａｔｅ要求のうちの１つを送信する。以降、ノード３ａは、実施例１に関わるノード５と同様の処理を実行し、ノード３ａを終端とする全ての経路を介して、ｕｐｄａｔｅｄ要求を始端ノードまで順次転送させる。
【０１６６】
次に、図１８ａ〜１８ｄを用いて、実施例２に関わるストレージシステム１ａがそれぞれ終端ノードが異なる複数の経路を介して、ｕｐｄａｔｅ要求とｕｐｄａｔｅｄ要求とを順次転送する処理について説明する。なお、図１８ａ〜１８ｄに示す例では、図９ａ、図９ｂに示すように、１ｓｔノードから７ｔｈノードまでの７個のノードが記憶するレプリカの更新を行う例について説明する。
【０１６７】
図１８ａは、実施例２に関わるストレージシステムが複数の経路を介してｕｐｄａｔｅ要求を送信する処理を説明するための図である。また、図１８ｂは、実施例２に関わる終端ノードがｒｅａｄｙＴｏＵｐｄａｔｅ要求を送受信する処理を説明するための図である。また、図１８ｃは、実施例２に関わるストレージシステムがｕｐｄａｔｅｄ要求を送信する処理を説明するための図である。また、図１８ｄは、実施例２に関わるストレージシステムにおける動作を説明するための図である。
【０１６８】
まず図１８ａ中（Ｈ）に示すように、クライアント７は、始端ノードである１ｓｔノードにＰｕｔ要求を発行する。このような場合には、１ｓｔノードは、図１８ａに示すように、２ｎｄノード、４ｔｈノード、６ｔｈノードを接続する経路と、３ｒｄノード、５ｔｈノード、７ｔｈノードを接続する経路とを識別する。
【０１６９】
そして、図１８ａ中（Ｉ）に示すように、１ｓｔノードは、２ｎｄノードと３ｒｄノードとにｕｐｄａｔｅ要求を送信する。このような場合には、２ｎｄノードは４ｔｈノードにｕｐｄａｔｅ要求を転送し、４ｔｈノードは６ｔｈノードにｕｐｄａｔｅ要求を転送する。また、３ｒｄノードは５ｔｈノードにｕｐｄａｔｅ要求を転送し、５ｔｈノードは７ｔｈノードにｕｐｄａｔｅ要求を転送する。
【０１７０】
また、図１８ｂ中（Ｊ）に示すように、各経路の終端ノードである６ｔｈノードと７ｔｈノードは、ｕｐｄａｔｅ要求を受信した場合には、他の経路の終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。この処理によって、各経路の終端ノードである６ｔｈノードと７ｔｈノードとは、他の経路のノードにｕｐｄａｔｅ要求が行き渡ったか否かを識別することができる。
【０１７１】
そして、図１８ｃ中（Ｋ）に示すように、各経路の終端ノードである６ｔｈノードと７ｔｈノードは、自身以外の終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を取得した場合には、ｕｐｄａｔｅｄ要求を４ｔｈノードおよび５ｔｈノードに送信する。その後、図１８ｃ中（Ｌ）に示すように、１ｓｔノードは、いずれかの経路からｕｐａｄｔｅｄ要求を取得した場合には、Ｐｕｔ返答をクライアント７に送信する。
【０１７２】
すなわち、図１８ｄ中（Ｍ）に示すように、６ｔｈノードおよび７ｔｈノードは、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を相互に送受信することで、各経路の終端ノードとなる仮想終端ノードが存在するものとして動作する。このような処理を実行することで、ストレージシステム１ａは、各経路の終端ノードが異なるノードである場合にも、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持することができる。
【０１７３】
なお、各経路の終端ノードである６ｔｈノードおよび７ｔｈノードは、複数の経路の終端ノードとしても動作することができる。図１９は、複数の経路の終端ノードが実行する処理の一例を説明するための図である。図１９に示す例では、６ｔｈノードは、図１８ａ〜１８ｄに示した１ｓｔノード、２ｎｄノード、４ｔｈノード、６ｔｈノードを接続する経路に加えて、１ｓｔノード、８ｔｈノード、９ｔｈノード、６ｔｈノードを接続する経路の終端ノードとなる。
【０１７４】
このような場合には、６ｔｈノードは、図１９中（Ｎ）に示すように、自身を終端ノードとする２つの経路からｕｐｄａｔｅ要求を取得するまで待機する。そして、６ｔｈノードは、２つの経路からｕｐｄａｔｅ要求を取得した場合には、図１９中（Ｏ）に示すように、ｒｅａｄｙＴｏＵｐｄａｔｅ要求を７ｔｈノードに送信する。このような処理を行うことで、ストレージシステム１ａは、任意のトポロジーを有する複数の経路を介して、ｕｐｄａｔｅ要求およびｕｐｄａｔｅｄ要求を各ノードに送信することができる。
【０１７５】
例えば、ノード間要求処理部１５ｂ、要求発行部１７ｂ、トポロジー計算部２０ｃ、要求収集部２４ａ、他終端状態判断部２５とは、電子回路である。ここで、電子回路の例として、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの集積回路、またはＣＰＵ（Central Processing Unit）やＭＰＵ（Micro Processing Unit）などを適用する。
【０１７６】
次に、図２０を用いて、終端ノードが実行する処理の流れの一例について説明する。図２０は、実施例２に関わる終端ノードが実行する処理の流れを説明するためのフローチャートである。なお、以下の説明では、ノード３ａが終端ノードとして動作する際に実行する処理の一例について説明する。
【０１７７】
例えば、ノード３ａは、自身の状態に停止条件が発生しているか否かを判別する（ステップＳ４０１）。そして、ノード３ａは、自身の状態に停止条件が発生していないと判別した場合には（ステップＳ４０１否定）、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ４０２）。そして、ノード３ａは、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信していないと判別した場合には（ステップＳ４０２否定）、全ての経路を介してｕｐｄａｔｅ要求を受信するまで待機する（ステップＳ４０２）。
【０１７８】
また、ノード３ａは、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信した場合には（ステップＳ４０２肯定）、各終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信し、ｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態に移行する（ステップＳ４０３）。ここで、ｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態とは、自身が終端ノードとなる全ての経路を介してｕｐｄａｔｅ要求を受信し、かつ、他の終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していない状態である。
【０１７９】
また、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信したか否かを判別する（ステップＳ４０４）。そして、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信していないと判別した場合には（ステップＳ４０４否定）、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信するまで待機する（ステップＳ４０４）。
【０１８０】
また、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信した場合には（ステップＳ４０４肯定）、レプリカを更新するとともに、自身を終端ノードとする全ての経路の前ノードにｕｐｄａｔｅｄ要求を送信する（ステップＳ４０５）。この際、ノード３ａは、ｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態を解除する。その後、ノード３ａは、再度停止条件が発生しているか否かを判別し（ステップＳ４０１）、発生している場合には（ステップＳ４０１肯定）、停止条件が解消するまで処理を終了する。
【０１８１】
次に、図２１を用いて、終端ノードがＧｅｔ要求を受信した際に実行する処理の流れの一例を説明する。図２１は、Ｇｅｔ要求に対する処理の流れの一例を説明するためのフローチャートである。なお、以下の説明では、ノード３ａが終端ノードとして動作する際に実行する処理の流れの一例について説明する。
【０１８２】
まず、ノード３ａは、停止条件が発生しているかを判別し（ステップＳ５０１）、発生していない場合には（ステップＳ５０１否定）、クライアント７からＧｅｔ要求を受信したか否かを判別する（ステップＳ５０２）。そして、ノード３ａは、クライアント７からＧｅｔ要求を受信した場合には（ステップＳ５０２肯定）、自身がｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態であるか否かを判別する（ステップＳ５０３）。すなわち、ノード３ａは、他の全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信したか否かを判別する。
【０１８３】
そして、ノード３ａは、自身がｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態であると判別した場合には（ステップＳ５０３肯定）、他の終端ノードに問合せを行う（ステップＳ５０４）。そして、ノード３ａは、いずれかの終端ノードがｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態を解除してｕｐｄａｔｅｄ要求の発行を依頼したか否かを判別する（ステップＳ５０５）。
【０１８４】
その後、ノード３ａは、いずれの終端ノードもｕｐｄａｔｅｄ要求の発行を依頼していないと判別した場合には（ステップＳ５０５否定）、更新前のレプリカのデータをクライアント７に送信する（ステップＳ５０６）。また、ノード３ａは、いずれかの終端ノードがｕｐｄａｔｅｄ要求の発行を依頼したと判別した場合には（ステップＳ５０５肯定）、更新後のレプリカのデータをクライアント７に送信する（ステップＳ５０７）。その後、ノード３ａは、再度停止条件が発生しているか否かを判別し（ステップＳ５０１）、停止条件が発生している場合には（ステップＳ５０１肯定）、停止条件が解消するまで処理を終了する。
【０１８５】
また、ノード３ａは、Ｇｅｔ要求を受信した際に（ステップＳ５０２肯定）、自身がｒｅａｄｙＴｏＵｐｄａｔｅ待ち状態ではないと判別した場合には（ステップＳ５０３否定）、保持しているレプリカのデータをクライアント７に送信する（ステップＳ５０８）。
【０１８６】
すなわち、ノード３ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信していない場合には、更新後のレプリカのデータを記憶していないので、更新前のレプリカのデータを送信することとなる。また、ノード３ａは、全ての終端ノードからｒｅａｄｙＴｏＵｐｄａｔｅ要求を受信した場合には、更新後のレプリカのデータのみを記憶しているので、更新後のレプリカのデータを送信することとなる。
【０１８７】
また、ノード３ａは、Ｇｅｔ要求を受信していない場合には（ステップＳ５０２否定）、再度停止条件が発生しているか否かを判別する（ステップＳ５０１）。
【０１８８】
[ストレージシステム１ａの効果]
上述したように、終端ノードとして動作するノード３ａは、自身を終端ノードとする全ての経路を介してｕｐｄａｔｅ要求を受信した場合には、自身を終端ノードとする経路以外の経路における終端ノードにｒｅａｄｙＴｏＵｐｄａｔｅ要求を送信する。そして、ノード３ａは、自身以外の全ての終端ノードからｒｅａｄｙＴｏＵｄａｔｅ要求を受信したか否かを判別する。その後、ノード３ａは、自身以外の全ての終端ノードからｒｅａｄｙＴｏＵｄａｔｅ要求を受信した場合には、ｕｐｄａｔｅｄ要求を、自身を終端ノードとする全ての経路を介して、始端ノードに送信する。
【０１８９】
このため、このようなノード３ａを有するストレージシステム１ａは、それぞれ異なるノードを終端ノードとする経路を介してｕｐｄａｔｅ要求を各ノードに送信することができる。この結果、ストレージシステム１ａは、レプリカの更新に要する時間をさらに短縮することができる。例えば、各ノード２ａ〜６ａの設置位置によっては、終端ノードを１つのノードとする複数の経路よりも、終端ノードを複数のノードとする複数の経路でｕｐｄａｔｅ要求を送信した方が更新に要する時間を短縮できる場合がある。このような場合にも、ストレージシステム１ａは、レプリカの更新に要する時間を短縮することができる。
【０１９０】
また、ノード３ａは、クライアント７からＧｅｔ要求を受信した場合には、自身がｒｅａｄｙＴｏＵｐｄａｔｅ状態か否かを判別し、ｒｅａｄｙＴｏＵｐｄａｔｅ状態である場合には、他の終端ノードがｕｐｄａｔｅｄ要求の発行を依頼したか否かを判別する。そして、ノード３ａは、いずれかの終端ノードがｕｐｄａｔｅｄ要求の発行を依頼していた場合には、更新後のレプリカのデータをクライアント７に送信する。また、ノード３ａは、いずれの終端ノードもｕｐｄａｔｅｄ要求の発行を依頼していない場合には、更新前のレプリカのデータをクライアント７に送信する。
【０１９１】
このようなノード３ａを有するストレージシステム１ａは、終端ノードが複数存在する場合にも、各終端ノードがＧｅｔ要求に対して送信するレプリカのデータをそろえることができる。この結果、ストレージシステム１ａは、Ｓｔｒｏｎｇ Ｃｏｎｓｉｓｔｅｎｃｙを保持しつつ、レプリカの更新に要する時間を短縮することができる。
【実施例３】
【０１９２】
これまで本発明の実施例について説明したが実施例は、上述した実施例以外にも様々な異なる形態にて実施されてよいものである。そこで、以下では実施例３として本発明に含まれる他の実施例を説明する。
【０１９３】
（１）経路の識別について
上述したストレージシステム１、１ａは、クライアント７がＰｕｔ要求を始端ノードに発行した場合には、更新対象となるレプリカを記憶するノードを識別し、識別したノードを接続する複数の経路を識別した。しかし、実施例はこれに限定されるものではない。すなわち、ストレージシステム１、１ａは、更新対象となるデータごとにあらかじめ設定された複数の経路を介して、ｕｐｄａｔｅ要求を各ノードに送信することとしてもよい。
【０１９４】
例えば、ストレージシステム１、１ａは、各ノード２〜５が記憶するレプリカＡ１〜Ａ４が他のノードに移る等の処理が発生しない場合など、ｕｐｄａｔｅ要求を送信する経路を固定してもよい場合には、ノード２〜５に予めｕｐｄａｔｅ要求を送信する経路を設定する。そして、ノード２〜５は、ノード２がＰｕｔ要求を受信した場合には、予め設定された複数の経路にそって、ｕｐｄａｔｅ要求を順に転送することとしてもよい。
【０１９５】
すなわち、ストレージシステム１、１ａは、複数の経路（マルチパス）でｕｐｄａｔｅ要求を各ノードに送信した場合には、１つの経路（シングルパス）でｕｐｄａｔｅ要求を各ノードに送信するよりも短時間でレプリカの更新を行うことができる。このため、ストレージシステム１、１ａは、複数の経路でｕｐｄａｔｅ要求を送信することができれば、経路が固定であっても、その都度複数の経路を識別する方法であってもよい。
【０１９６】
（２）ノードの数や各ノードが記憶するレプリカについて
上述した例では、ノード２〜６がレプリカＡ１〜Ａ４、Ｂ１〜Ｂ４、Ｃ１〜Ｃ４を記憶する例について説明した。しかし、実施例はこれに限定されるものではなく、ノードの数や各ノードが記憶するレプリカの数および種類は任意の組合せを適用することができる。
【０１９７】
（３）経路情報について
上述した例では、ｕｐｄａｔｅ要求を送信する経路を示す経路情報をｕｐｄａｔｅ要求のヘッダに格納した。しかし、実施例はこれに限定されるものではない。例えば、ｕｐｄａｔｅ要求を送信する経路が固定である場合には、経路情報を格納する必要はなく、経路が固定でなくとも、経路情報をｕｐｄａｔｅ要求とは別に送ってもよい。すなわち、各ノードがｕｐｄａｔｅ要求を送信する経路を識別する処理については、任意の手法を適用することができる。
【０１９８】
（４）経路について
上述した例では、２つまたは３つの経路を識別したが、実施例はこれに限定されるものではなく、任意の数の複数の経路を識別することもできる。例えば、トポロジー計算部２０は、ｕｐｄａｔｅ要求を送信する複数の経路の組を複数識別し、各組において片道の最大遅延が最も小さい組を選択することとしてもよい。
【０１９９】
すなわち、ノード２〜６にレプリカＤ１〜Ｄ５が記憶されている際に、各レプリカ間の遅延がすべて１０ｍｓｅｃ（millisecond）だとする。このような場合に、トポロジー計算部２０は、ノード２、ノード３、ノード４、ノード６の経路とノード２、ノード５、ノード６の経路との第１の組を識別する。また、トポロジー計算部２０は、ノード２、ノード３、ノード６の経路と、ノード２、ノード４、ノード６の経路と、ノード２、ノード５、ノード６の経路との第２の組を識別する。このような場合には、第２の組の方が、片道の最大遅延が１０ｍｓｅｃ短いので、第２の組を識別することとなる。
【０２００】
（５）プログラム
ところで、実施例１、２に関わるノード２〜６、２ａ〜６ａは、ハードウェアを利用して各種の処理を実現する場合を説明した。しかし、実施例はこれに限定されるものではなく、あらかじめ用意されたプログラムをストレージ装置として動作するコンピュータで実行することによって実現するようにしてもよい。そこで、以下では、図２２を用いて、実施例１に示したノード２〜６と同様の機能を有するデータ管理プログラムを実行するコンピュータの一例を説明する。図２２は、データ管理プログラムを実行するコンピュータの一例を説明するための図である。
【０２０１】
図２２に例示されたコンピュータ１００は、ＲＡＭ（Random Access Memory）１１０、ＨＤＤ（Hard Disk Drive）１２０、ＲＯＭ（Read Only Memory）１３０、ＣＰＵ（Central Processing Unit）１４０がバス１６０で接続される。また、コンピュータ１００は、ＲＡＭ（Random Access Memory）１４０、他のコンピュータと通信を行うためのＩ／Ｏ（Input Output）１５０がバス１６０で接続される。
【０２０２】
ＨＤＤ１２０には、レプリカが記憶されている。ＲＯＭ１３０には、データ更新プログラム１３１が記憶されており、ＣＰＵ１４０が読み出して実行することによって、図２２に示す例では、データ更新プロセス１４１として機能するようになる。なお、データ更新プロセス１４１は、図３に示す各部１１〜２３と同様の機能を発揮するが、図７に示す要求収集部２４および図１５に示す他終端状態判断部２５の機能を付加することもできる。
【０２０３】
なお、本実施例で説明したデータ管理プログラムは、あらかじめ用意されたプログラムをパーソナルコンピュータやワークステーションなどのコンピュータで実行することによって実現することができる。このプログラムは、インターネットなどのネットワークを介して配布することができる。また、このプログラムは、ハードディスク、フレキシブルディスク（ＦＤ）、ＣＤ−ＲＯＭ（Compact Disc Read Only Memory）、ＭＯ（Magneto Optical Disc）、ＤＶＤ（Digital Versatile Disc）などのコンピュータで読取可能な記録媒体に記録される。また、このプログラムは、コンピュータによって記録媒体から読み出されることによって実行することもできる。
【符号の説明】
【０２０４】
１、１ａ ストレージネットワーク
２〜６、２ａ〜６ａ ノード
７ クライアント
８ ＩＰ網
１０、１０ａ ネットワークインターフェース
１１、１１ａ 要求送信元判断部
１２、１２ａ クライアント要求受信部
１３、１３ａ クライアント要求処理部
１４ ノード間要求受信部
１５〜１５ｂ ノード間要求処理部
１６ データ記憶部
１７〜１７ｂ 要求発行部
１８ 要求発行認証部
１９ クライアント位置記憶部
２０〜２０ｃ トポロジー計算部
２１ ノード間要求並列送信部
２２ クライアント位置判断部
２３ クライアント要求送信部
２４、２４ａ 要求収集部
２５ 他終端状態判断部
【特許請求の範囲】
【請求項１】
データの複製を記憶する複数のストレージ装置のうち、クライアントからデータの更新を要求されるストレージ装置において、
前記データの更新を要求された場合は、自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となる１つまたは複数のストレージ装置に前記データの更新を要求する更新要求を送信する送信部と、
各経路の終端となる前記１つまたは複数のストレージ装置が前記複数の経路の全ての経路を介して前記更新要求の受信に応じて発行した応答を、前記送信部が前記更新要求を送信したいずれかの経路を介して受信した場合には、前記データの更新が完了した旨を前記クライアントに通知する通知部と
を有することを特徴とするストレージ装置。
【請求項２】
各ストレージ装置の設置位置を記憶する記憶部と、
前記記憶部が記憶する各ストレージ装置の設置位置に基づいて、自ストレージ装置を始端とし、相互に設置位置が近い複数のストレージ装置を接続する複数の経路を識別する識別部と、
をさらに有し、
前記送信部は、前記識別部が識別した複数の経路を介して、各経路の終端となるストレージ装置に前記更新要求を送信することを特徴とする請求項１に記載のストレージ装置。
【請求項３】
前記送信部は、同一のストレージ装置を終端とする複数の経路を介して、前記更新要求を送信することを特徴とする請求項１または２に記載のストレージ装置。
【請求項４】
データの複製を記憶する複数のストレージ装置のうち、データの更新を要求する更新要求を他のストレージ装置から受付けるストレージ装置において、
自ストレージ装置を終端とし、複数のストレージ装置を接続する複数の経路を介して前記更新要求を受信する受信部と、
前記受信部が、前記自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したか否かを判別する判別部と、
前記判別部が、前記自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したと判別した場合は、前記更新要求に対する応答を、前記自ストレージ装置を終端とする全ての経路を介して、各経路の始端となるストレージ装置へ送信する送信部と
を有することを特徴とするストレージ装置。
【請求項５】
データの複製を記憶する複数のストレージ装置のうち、他のストレージ装置からデータの更新を要求する更新要求を受付けるストレージ装置において、
自ストレージ装置を終端とし、複数のストレージ装置を接続する１つまたは複数の経路を介して前記更新要求を受信する受信部と、
前記受信部が、自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信した場合には、自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置に更新要求を受信した旨を通知する通知部と、
前記受信部が、自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信し、かつ、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から更新要求を受信した旨の通知を受付けたか否かを判別する判別部と、
前記判別部が、自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信し、かつ、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から更新要求を受信した旨の通知を受付けたと判別した場合には、前記更新要求に対する応答を前記自ストレージ装置を終端とする経路を介して、前記経路の始端となるストレージ装置へ送信する送信部と
を有することを特徴とするストレージ装置。
【請求項６】
更新の対象となる前記データの読出し要求を取得した際に、前記通知部が前記更新要求を受信した旨を通知した後であり、かつ、前記送信部が前記応答を送信していない場合には、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置に対して、前記応答を送信したか否かを問い合わせる問合せ部と、
前記問合せ部の問合せに対する応答として、いずれかのストレージ装置から前記応答を送信した旨の通知を取得した場合には、更新後の前記データを出力し、前記問合せ部の問合せに対する応答として、いずれのストレージ装置からも前記応答を送信した旨の通知を取得しなかった場合には、更新前の前記データを出力する出力部と
をさらに有することを特徴とする請求項５に記載のストレージ装置。
【請求項７】
データの複製を記憶する複数のストレージ装置を有するストレージシステムにおいて、
クライアントからデータの更新を要求された場合には、自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となる１つまたは複数のストレージ装置に前記データの更新を要求する更新要求を送信する第１のストレージ装置と、
自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したか否かを判別し、前記全ての経路を介して前記更新要求を受信したと判別した場合には、前記更新要求に対する応答を、前記全ての経路を介して、前記第１のストレージ装置へ送信する第２のストレージ装置と
を有することを特徴とするストレージシステム。
【請求項８】
データの複製を記憶する複数のストレージ装置を有するストレージシステムが実行するデータ更新方法において、
クライアントからデータの更新を要求される第１のストレージ装置が、
自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となるストレージ装置に前記データの更新を要求する更新要求を送信する処理を実行し、
前記各経路の終端となる第２のストレージ装置が、
自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したか否かを判別し、前記全ての経路を介して前記更新要求を受信したと判別した場合には、前記更新要求に対する応答を、前記全ての経路を介して、前記第１のストレージ装置へ送信する処理を実行する
ことを特徴とするデータ更新方法。
【請求項９】
データの複製を記憶する複数のストレージ装置のうち、クライアントからデータの更新を要求されるストレージ装置が実行するデータ管理プログラムにおいて、
前記データの更新を要求された場合は、自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となる前記１つまたは複数のストレージ装置に前記データの更新を要求する更新要求を送信し、
各経路の終端となるストレージ装置が全ての経路を介して前記更新要求を受信した後に前記更新要求に対して発行した応答を、前記更新通知を送信したいずれかの経路を介して受信した場合には、前記データの更新が完了した旨を前記クライアントに通知する
処理を実行させることを特徴とするデータ管理プログラム。
【請求項１０】
データの複製を記憶する複数のストレージ装置のうち、他のストレージ装置からデータの更新を要求する更新要求を受付けるストレージ装置が実行するデータ管理プログラムにおいて、
自ストレージ装置を終端とし、複数のストレージ装置を接続する全ての経路を介して前記更新要求を受信したか否かを判別し、
自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したと判別した場合は、前記更新要求に対する応答を、前記自ストレージ装置を終端とする全ての経路を介して、各経路の始端となるストレージ装置へ送信する
処理を実行させることを特徴とするデータ管理プログラム。
【請求項１１】
データの複製を記憶する複数のストレージ装置のうち、他のストレージ装置からデータの更新を要求する更新要求を受付けるデータ管理プログラムにおいて、
自ストレージ装置を終端とし、複数のストレージ装置を接続する経路を介して前記更新要求を受信した場合は、自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置に更新要求を受信した旨を通知し、
自ストレージ装置を終端とする経路を介して前記更新要求を受信し、かつ、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から前記更新要求を受信した旨の通知を受付けたか否かを判別し、
自ストレージ装置を終端とする経路を介して前記更新要求を受信し、かつ、自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から前記更新要求を受信した旨の通知を受付けたと判別した場合には、前記更新要求に対する応答を前記自ストレージ装置を終端とする経路を介して、前記経路の始端となるストレージ装置へ送信する
処理を実行させることを特徴とするデータ管理プログラム。
【請求項１】
データの複製を記憶する複数のストレージ装置のうち、クライアントからデータの更新を要求されるストレージ装置において、
前記データの更新を要求された場合は、自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となる１つまたは複数のストレージ装置に前記データの更新を要求する更新要求を送信する送信部と、
各経路の終端となる前記１つまたは複数のストレージ装置が前記複数の経路の全ての経路を介して前記更新要求の受信に応じて発行した応答を、前記送信部が前記更新要求を送信したいずれかの経路を介して受信した場合には、前記データの更新が完了した旨を前記クライアントに通知する通知部と
を有することを特徴とするストレージ装置。
【請求項２】
各ストレージ装置の設置位置を記憶する記憶部と、
前記記憶部が記憶する各ストレージ装置の設置位置に基づいて、自ストレージ装置を始端とし、相互に設置位置が近い複数のストレージ装置を接続する複数の経路を識別する識別部と、
をさらに有し、
前記送信部は、前記識別部が識別した複数の経路を介して、各経路の終端となるストレージ装置に前記更新要求を送信することを特徴とする請求項１に記載のストレージ装置。
【請求項３】
前記送信部は、同一のストレージ装置を終端とする複数の経路を介して、前記更新要求を送信することを特徴とする請求項１または２に記載のストレージ装置。
【請求項４】
データの複製を記憶する複数のストレージ装置のうち、データの更新を要求する更新要求を他のストレージ装置から受付けるストレージ装置において、
自ストレージ装置を終端とし、複数のストレージ装置を接続する複数の経路を介して前記更新要求を受信する受信部と、
前記受信部が、前記自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したか否かを判別する判別部と、
前記判別部が、前記自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したと判別した場合は、前記更新要求に対する応答を、前記自ストレージ装置を終端とする全ての経路を介して、各経路の始端となるストレージ装置へ送信する送信部と
を有することを特徴とするストレージ装置。
【請求項５】
データの複製を記憶する複数のストレージ装置のうち、他のストレージ装置からデータの更新を要求する更新要求を受付けるストレージ装置において、
自ストレージ装置を終端とし、複数のストレージ装置を接続する１つまたは複数の経路を介して前記更新要求を受信する受信部と、
前記受信部が、自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信した場合には、自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置に更新要求を受信した旨を通知する通知部と、
前記受信部が、自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信し、かつ、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から更新要求を受信した旨の通知を受付けたか否かを判別する判別部と、
前記判別部が、自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信し、かつ、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から更新要求を受信した旨の通知を受付けたと判別した場合には、前記更新要求に対する応答を前記自ストレージ装置を終端とする経路を介して、前記経路の始端となるストレージ装置へ送信する送信部と
を有することを特徴とするストレージ装置。
【請求項６】
更新の対象となる前記データの読出し要求を取得した際に、前記通知部が前記更新要求を受信した旨を通知した後であり、かつ、前記送信部が前記応答を送信していない場合には、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置に対して、前記応答を送信したか否かを問い合わせる問合せ部と、
前記問合せ部の問合せに対する応答として、いずれかのストレージ装置から前記応答を送信した旨の通知を取得した場合には、更新後の前記データを出力し、前記問合せ部の問合せに対する応答として、いずれのストレージ装置からも前記応答を送信した旨の通知を取得しなかった場合には、更新前の前記データを出力する出力部と
をさらに有することを特徴とする請求項５に記載のストレージ装置。
【請求項７】
データの複製を記憶する複数のストレージ装置を有するストレージシステムにおいて、
クライアントからデータの更新を要求された場合には、自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となる１つまたは複数のストレージ装置に前記データの更新を要求する更新要求を送信する第１のストレージ装置と、
自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したか否かを判別し、前記全ての経路を介して前記更新要求を受信したと判別した場合には、前記更新要求に対する応答を、前記全ての経路を介して、前記第１のストレージ装置へ送信する第２のストレージ装置と
を有することを特徴とするストレージシステム。
【請求項８】
データの複製を記憶する複数のストレージ装置を有するストレージシステムが実行するデータ更新方法において、
クライアントからデータの更新を要求される第１のストレージ装置が、
自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となるストレージ装置に前記データの更新を要求する更新要求を送信する処理を実行し、
前記各経路の終端となる第２のストレージ装置が、
自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したか否かを判別し、前記全ての経路を介して前記更新要求を受信したと判別した場合には、前記更新要求に対する応答を、前記全ての経路を介して、前記第１のストレージ装置へ送信する処理を実行する
ことを特徴とするデータ更新方法。
【請求項９】
データの複製を記憶する複数のストレージ装置のうち、クライアントからデータの更新を要求されるストレージ装置が実行するデータ管理プログラムにおいて、
前記データの更新を要求された場合は、自ストレージ装置を始端とし、複数のストレージ装置を接続する複数の経路を介して、各経路の終端となる前記１つまたは複数のストレージ装置に前記データの更新を要求する更新要求を送信し、
各経路の終端となるストレージ装置が全ての経路を介して前記更新要求を受信した後に前記更新要求に対して発行した応答を、前記更新通知を送信したいずれかの経路を介して受信した場合には、前記データの更新が完了した旨を前記クライアントに通知する
処理を実行させることを特徴とするデータ管理プログラム。
【請求項１０】
データの複製を記憶する複数のストレージ装置のうち、他のストレージ装置からデータの更新を要求する更新要求を受付けるストレージ装置が実行するデータ管理プログラムにおいて、
自ストレージ装置を終端とし、複数のストレージ装置を接続する全ての経路を介して前記更新要求を受信したか否かを判別し、
自ストレージ装置を終端とする全ての経路を介して前記更新要求を受信したと判別した場合は、前記更新要求に対する応答を、前記自ストレージ装置を終端とする全ての経路を介して、各経路の始端となるストレージ装置へ送信する
処理を実行させることを特徴とするデータ管理プログラム。
【請求項１１】
データの複製を記憶する複数のストレージ装置のうち、他のストレージ装置からデータの更新を要求する更新要求を受付けるデータ管理プログラムにおいて、
自ストレージ装置を終端とし、複数のストレージ装置を接続する経路を介して前記更新要求を受信した場合は、自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置に更新要求を受信した旨を通知し、
自ストレージ装置を終端とする経路を介して前記更新要求を受信し、かつ、前記自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から前記更新要求を受信した旨の通知を受付けたか否かを判別し、
自ストレージ装置を終端とする経路を介して前記更新要求を受信し、かつ、自ストレージ装置を終端とする経路以外の経路において終端となる全てのストレージ装置から前記更新要求を受信した旨の通知を受付けたと判別した場合には、前記更新要求に対する応答を前記自ストレージ装置を終端とする経路を介して、前記経路の始端となるストレージ装置へ送信する
処理を実行させることを特徴とするデータ管理プログラム。
【図１】
【図２ａ】
【図２ｂ】
【図２ｃ】
【図３】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８ａ】
【図１８ｂ】
【図１８ｃ】
【図１８ｄ】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２ａ】
【図２ｂ】
【図２ｃ】
【図３】
【図４ａ】
【図４ｂ】
【図５】
【図６】
【図７】
【図８】
【図９ａ】
【図９ｂ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８ａ】
【図１８ｂ】
【図１８ｃ】
【図１８ｄ】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【公開番号】特開２０１３−１０９６００（Ｐ２０１３−１０９６００Ａ）
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願番号】特願２０１１−２５４４６９（Ｐ２０１１−２５４４６９）
【出願日】平成２３年１１月２１日（２０１１．１１．２１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
【公開日】平成２５年６月６日（２０１３．６．６）
【国際特許分類】
【出願日】平成２３年１１月２１日（２０１１．１１．２１）
【出願人】（０００００５２２３）富士通株式会社 (25,993)
【Ｆターム（参考）】
[ Back to top ]