JP6056453B2 - プログラム、データ管理方法および情報処理装置 - Google Patents

Description

本発明はプログラム、データ管理方法および情報処理装置に関する。

現在、ネットワークに接続された複数のノードにデータを分散して格納する分散ストレージシステムが利用されることがある。分散ストレージシステムの一例として、各ノードがデータレコードとしてキーと値（バリュー）の組を記憶する分散キーバリューストアが挙げられる。分散キーバリューストアでは、例えば、キーのハッシュ値に基づいて、複数のノードの中からキーとバリューの組を記憶すべきノードが決定される。

分散ストレージシステムでは、所定数以下のノードの故障に耐えられるよう、データをコピーして複数のノードに記憶しておくことがある。例えば、同じデータを３台のノードに記憶しておけば、２台までのノードの同時故障に耐えることができる。データを冗長化した場合、同じデータを記憶する複数のノードのうち、１つのノードのみが当該データの読み出しや書き込みなどの命令を受け付けて処理し、他のノードは当該データを専らバックアップデータとして管理することが考えられる。前者はマスタ処理と呼ぶことがあり、後者はスレーブ処理と呼ぶことがある。複数のノードのリソースを活用するため、マスタ処理専用・スレーブ処理専用のノードを設けるのではなく、各ノードがあるデータについてはマスタ処理を担当し別のデータについてはスレーブ処理を担当することもある。

なお、複数のノードそれぞれがマスタプロセッサとスレーブプロセッサと共有メモリを備え、マスタプロセッサは複数のノードを接続するバスを介して直接監視され、スレーブプロセッサは共有メモリを介して間接的に監視されるシステムが提案されている。また、それぞれ担当する加入者のメッセージを処理する２つのホームロケーションレジスタ（ＨＬＲ）を備え、一方のＨＬＲが故障すると、メッセージをコピーすることで故障したＨＬＲの処理を他方のＨＬＲが引き継ぐシステムが提案されている。また、複数のリソース管理装置それぞれがリソース要求情報を記憶する予約データベースを備え、リソース管理装置の間で予約データベースが共有された状態にするシステムが提案されている。

特開平７−９３２７０号公報 特開平１０−５１２１２２号公報 特開２０１１−２０３８４８号公報

データを冗長化した分散ストレージシステムでは、あるデータについてマスタ処理を担当するノードが書き込み命令を実行すると、スレーブ処理を担当するノードに書き込みを反映させることになる。しかし、データの管理には、ランダムアクセスが比較的低速なＨＤＤ（Hard Disk Drive）などの不揮発性の記憶装置が利用されることが多い。そのため、書き込み命令が実行される毎にスレーブ処理を担当するノードがこのような不揮発性の記憶装置にアクセスすることは、同じノードで実行される他のデータについてのマスタ処理の性能を低下させるおそれがあるという問題がある。マスタ処理の性能が低下すると、外部から見た分散ストレージシステム全体のスループットが低下してしまう。

１つの側面では、本発明は、データの冗長性の管理が他の処理の性能に与える影響を軽減するプログラム、データ管理方法および情報処理装置を提供することを目的とする。

１つの態様では、第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムにおいて、第２のノードとして用いられるコンピュータに以下の処理を実行させるプログラムが提供される。第１のデータ集合に属するデータに対して実行された命令を示すログを第１のノードから受信し、受信したログをコンピュータが備えるメモリに格納する。所定の条件が満たされたタイミングで、メモリに蓄積された複数の命令分のログをコンピュータが備えるメモリと異なる記憶装置に書き込む。

また、１つの態様では、第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムが実行するデータ管理方法が提供される。データ管理方法では、第１のデータ集合に属するデータに対して実行された命令を示すログを第１のノードから第２のノードに送信する。送信されたログを第２のノードが備えるメモリに格納する。所定の条件が満たされたタイミングで、メモリに蓄積された複数の命令分のログを第２のノードが備えるメモリと異なる記憶装置に書き込む。

また、１つの態様では、第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムにおいて、第２のノードとして用いられる情報処理装置が提供される。情報処理装置は、メモリと、メモリと異なる記憶装置と、第１のデータ集合に属するデータに対して実行された命令を示すログを第１のノードから受信する受信部と、受信したログをメモリに格納し、所定の条件が満たされたタイミングで、メモリに蓄積された複数の命令分のログを記憶装置に書き込む制御部と、を有する。

１つの側面では、データの冗長性の管理が他の処理の性能に与える影響を軽減できる。

第１の実施の形態の情報処理システムの例を示す図である。 第２の実施の形態の情報処理システムの例を示す図である。 データ配置例を示す図である。 ノード障害時のデータ配置の変化例を示す図である。 各ノードのハードウェア例を示すブロック図である。 各ノードの機能例を示すブロック図である。 ノード管理テーブルの例を示す図である。 マスタ処理の手順例を示すフローチャートである。 スレーブ処理の手順例を示すフローチャートである。 冗長回復の手順例を示すフローチャートである。 ノード間の第１の通信例を示す図である。 ノード間の第２の通信例を示す図である。 ノード間の第３の通信例を示す図である。 他のデータ配置例を示す図である。 ノード間の第４の通信例を示す図である。 ノード間の第５の通信例を示す図である。

以下、本実施の形態を図面を参照して説明する。
［第１の実施の形態］
図１は、第１の実施の形態の情報処理システムの例を示す図である。第１の実施の形態の情報処理システムは、ノード１０，２０を含む複数のノードを備える。これら複数のノードは、ＬＡＮ（Local Area Network）などのネットワークに接続されており、ＨＤＤなどの不揮発性の記憶装置を用いて分散してデータを管理する。

ノード１０には第１のデータ集合が割り当てられ、ノード２０には第１のデータ集合と重複しない第２のデータ集合が割り当てられている。各データ集合は、例えば、キーと値（バリュー）の組であるキーバリュー形式のデータレコードを１つ以上含む。例えば、第１のデータ集合は、キーのハッシュ値が所定の第１の範囲に属するようなデータレコードの集合であり、第２のデータ集合は、キーのハッシュ値が第１の範囲と重複しない所定の第２の範囲に属するようなデータレコードの集合である。

第１のデータ集合が割り当てられたノード１０は、第１のデータ集合に属するデータを指定した命令を受け付け、受け付けた命令を実行する。命令の種類として、例えば、書き込み（ライト）命令や読み出し（リード）命令が挙げられる。あるデータを指定した書き込み命令を受け付けると、ノード１０は、指定されたデータをノード１０が備える不揮発性の記憶装置に書き込む。また、あるデータを指定した読み出し命令を受け付けると、ノード１０は、指定されたデータをノード１０が備える不揮発性の記憶装置から読み出す。同様に、第２のデータ集合が割り当てられたノード２０は、第２のデータ集合に属するデータを指定した命令を受け付け、受け付けた命令を実行する。

また、ノード２０は、第１のデータ集合のバックアップコピーを管理する。ノード２０は、ノード１０と異なり、第１のデータ集合に属するデータを指定した命令を直接には受け付けて実行することはしない。すなわち、第１のデータ集合に属するデータの読み出しは、ノード２０ではなくノード１０から行われる。また、第１のデータ集合に属するデータの保存は、ノード２０ではなくノード１０に対して要求される。

なお、命令を受け付けて実行することをマスタ処理、バックアップコピーを管理することをスレーブ処理と言うことができる。ノード１０は第１のデータ集合のマスタ処理を担当し、ノード２０は第１のデータ集合のスレーブ処理と第２のデータ集合のマスタ処理とを担当している。また、あるデータ集合にとって、マスタ処理を担当するノードをマスタノード、スレーブ処理を担当するノードをスレーブノードと言うこともできる。第１のデータ集合にとっては、ノード１０がマスタノードでありノード２０がスレーブノードである。また、第２のデータ集合にとっては、ノード２０がマスタノードである。

ここで、第１のデータ集合について、マスタノードであるノード１０で書き込み命令が実行されると、データの冗長性を維持するために、書き込み結果をスレーブノードであるノード２０に反映させることになる。そこで、ノード１０からノード２０に、実行された命令を示すログを送信する。ログとして通知する命令は、読み出し命令を含む全ての種類の命令としてもよいし、書き込み命令などの所定の種類の命令に絞ってもよい。

情報処理装置としてのノード２０は、メモリ２１、記憶装置２２、受信部２３および制御部２４を有する。メモリ２１は、例えば、ＲＡＭ（Random Access Memory）などの揮発性の記憶装置である。記憶装置２２は、例えば、メモリ２１よりランダムアクセスが低速なＨＤＤなどの不揮発性の記憶装置である。受信部２３は、例えば、有線または無線でネットワークに接続する通信インタフェースである。制御部２４は、例えば、プロセッサを含む。「プロセッサ」は、ＣＰＵ（Central Processing Unit）やＤＳＰ（Digital Signal Processor）でもよいし、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）などの特定用途の電子回路でもよい。また、「プロセッサ」は、複数のプロセッサの集合（マルチプロセッサ）であってもよい。プロセッサは、例えば、ＲＡＭなどの揮発性メモリに記憶されたプログラムを実行する。

受信部２３は、第１のデータ集合に属するデータについてノード１０で実行された命令（好ましくは、書き込み命令）を示すログを、ネットワークを介してノード１０から受信する。ログは、例えば、所定の種類の命令が実行される毎に逐次受信される。

制御部２４は、ログが受信される毎に、受信されたログをメモリ２１上のバッファ領域に追加する。例えば、キー＝ａ，値＝１０を指定した書き込み命令のログが受信されると、このログをメモリ２１のバッファ領域に追加する。その後、キー＝ｂ，値＝２０を指定した書き込み命令のログが受信されると、このログをメモリ２１のバッファ領域に更に追加する。このようにして、メモリ２１には、複数の命令分のログが蓄積される。

そして、制御部２４は、所定の条件が満たされたタイミングで、メモリ２１に蓄積された複数の命令分のログを記憶装置２２に書き込む。これら複数の命令分のログは、記憶装置２２の連続する記憶領域にシーケンシャルに書き込むことが可能である。記憶装置２２に保存したログは、メモリ２１から消去してもよい。例えば、制御部２４は、別々に受信されたキー＝ａ，値＝１０を指定した書き込み命令のログと、キー＝ｂ，値＝２０を指定した書き込み命令のログとを、纏めてメモリ２１から記憶装置２２に移動させる。

所定の条件としては、例えば、ノード２０の負荷の大きさの条件が用いられる。この場合、制御部２４は、ノード２０の負荷を監視し、負荷が閾値未満になったタイミングでログを記憶装置２２に書き込む。監視する負荷としては、ＣＰＵ使用率やマスタ処理による不揮発性の記憶装置（例えば、記憶装置２２）へのアクセス頻度を用いてもよい。また、所定の条件としては、例えば、メモリ２１のバッファ領域に格納されたログの量の条件が用いられる。この場合、制御部２４は、バッファ領域を監視し、ログの量が閾値に達したタイミングでバッファ領域のログを記憶装置２２に書き込む。

なお、記憶装置２２に書き込まれたログは、ノード１０に障害が発生したときに第１のデータ集合を復元するために使用できる。例えば、ノード２０は、ノード２０が保持する古い第１のデータ集合のバックアップコピーに対して命令を再実行することで、最新の第１のデータ集合を復元する。これにより、ノード２０がノード１０に代わってマスタノードになることができる。また、記憶装置２２に書き込まれたログは、ノード１０に障害が発生したときに第１のデータ集合の冗長性を回復するために使用できる。例えば、ノード２０は、ノード１０，２０以外の他のノードにログを送信することで、当該他のノードを第１のデータ集合の新たなスレーブノードに指定する。ただし、ノード２０は、ノード１０に障害が発生する前に、ノード２０の負荷が低いときに命令を再実行してもよい。

第１の実施の形態の情報処理システムによれば、第１のデータ集合に属するデータを指定した命令はノード１０が実行し、第２のデータ集合に属するデータを指定した命令はノード２０が実行するため、ノード１０，２０間でデータ処理の負荷が分散される。また、ノード１０に割り当てられた第１のデータ集合のバックアップコピーをノード２０が管理してデータを冗長化するため、ノード１０，２０の一方が故障しても他方が第１のデータ集合の処理を継続することができ、耐故障性が向上する。

また、ノード１０で第１のデータ集合に属するデータの書き込み命令が実行されたときに、すぐにノード２０でも同じ書き込み命令が実行されるのではなくノード２０にログが蓄積される。そして、ノード１０に障害が発生したとき（または、ノード２０の負荷が低いとき）、ログに従ってノード２０で書き込み命令が再実行される。このため、ノード２０で第１のデータ集合のバックアップコピーを管理する負荷が軽減される。

更に、ログはノード１０からノード２０に送信される毎に記憶装置２２に書き込まれるのではなくメモリ２１に蓄積され、所定の条件が満たされたときに蓄積されたログが纏めて記憶装置２２に書き込まれる。このため、バックアップコピーの管理に関する記憶装置２２へのアクセスを減らすことができ、記憶装置２２がランダムアクセアスの低速な記憶装置であっても、他の処理に関する記憶装置２２へのアクセスが待ち状態になる可能性を減らすことができる。よって、ノード２０における第２のデータ集合に属するデータの処理性能が低下する可能性を減らし、スループットを向上させることができる。

［第２の実施の形態］
図２は、第２の実施の形態の情報処理システムの例を示す図である。第２の実施の形態の情報処理システムは、データを複数のノードに分散して管理する。この情報処理システムは、クライアント装置３１およびノード１００，１００−１〜１００−６を備える。クライアント装置３１と各ノードは、ネットワーク３０に接続されている。

クライアント装置３１は、ユーザが操作する端末装置としてのコンピュータである。クライアント装置３１は、データの読み出し（リード）やデータの書き込み（ライト）を行うとき、ノード１００，１００−１〜１００−６の何れかにアクセスする。アクセス先のノードとしては、データの内容にかかわらず任意のノードを選択してよい。すなわち、この情報処理システムはボトルネックとなり得る集中管理ノードをもたず、全てのノードはクライアント装置３１からのアクセスを受け付けることができる。また、クライアント装置３１は、所望のデータが何れのノードに記憶されているか知らなくてよい。

ノード１００，１００−１〜１００−６は、データを不揮発性の記憶装置に格納して管理するサーバコンピュータである。ノード１００，１００−１〜１００−６は、例えば、データをキーと値（バリュー）の組であるキーバリュー形式で記憶する。この場合、ノード１００，１００−１〜１００−６の集合を分散キーバリューストアと呼んでもよい。

第２の実施の形態の情報処理システムでは、耐故障性を高めるためデータが冗長化され、同じデータが複数（例えば２つ）のノードに重複して記憶される。同じデータを記憶する複数のノードのうち、１つのノードがそのデータについてのクライアント装置３１からのアクセスを処理し、他のノードはそのデータを専らバックアップコピーとして管理する。前者の処理はマスタ処理、後者の処理はスレーブ処理と呼ぶことがある。また、あるデータにとって、マスタ処理を担当するノードをマスタノード、スレーブ処理を担当するノードをスレーブノードと呼ぶことがある。各ノードではマスタ処理とスレーブ処理を混在させることがあり、その際、各ノードは何れかのデータにとってのマスタノードである（マスタ処理を担当する）と共に、他の何れかのデータにとってのスレーブノードになる（スレーブ処理を担当する）。なお、バックアップコピーは、クライアント装置３１が読み出し命令を発行したときの読み出し対象としては使用されない。ただし、クライアント装置３１が書き込み命令を発行してマスタノードのデータ（バックアップコピーに対応するオリジナルのデータ）が更新された場合には、データの一貫性を維持するために、オリジナルのデータに対応するバックアップコピーは更新され得る。

各ノードには、キーのハッシュ値に基づいて、マスタ処理を担当すべきデータとスレーブ処理を担当すべきデータとが割り当てられる。クライアント装置３１からアクセスを受け付けたノードは、クライアント装置３１から指定されたキーのハッシュ値を算出し、そのキーが示すデータのマスタ処理を担当するマスタノードを判定する。判定されたマスタノードが他ノードであるときは、アクセスが当該他ノードに転送される。

図３は、データ配置例を示す図である。データをノード１００，１００−１〜１００−６に配置するにあたって、図３に示すように、キーのハッシュ値の値域を円状に繋げたハッシュ空間を定義する。例えば、ハッシュ値がＬビットで表されるとき、２^L−１（ハッシュ値の最大）の次のハッシュ値が０に戻るような循環するハッシュ空間が定義される。

ハッシュ空間上には、各ノードに対応する点（ハッシュ値）を設定する。ノードに対応するハッシュ値は、例えば、そのノードのＩＰ（Internet Protocol）アドレスなどのアドレスのハッシュ値とする。図３の例では、ノード１００，１００−１〜１００−６に対応するハッシュ値ｈ０〜ｈ６が、ハッシュ空間上に設定される。そして、隣接する２つのノードのハッシュ値によって挟まれる区間毎に、マスタノードとスレーブノードが割り当てられる。例えば、各ノードは、ハッシュ空間上で１つ前のノードとの間の区間に属するデータのマスタ処理を担当する。また、例えば、あるデータのマスタ処理を担当するノードの１つ後ろに位置するノードが、当該データのスレーブ処理を担当する。

一例として、ｈ（）をハッシュ関数としｈ６とｈ０の間に“０”があるとすると、区間ｈ６＜ｈ（ｋｅｙ）≦２^L−１または０≦ｈ（ｋｅｙ）≦ｈ０に属するデータＡのマスタ処理はノード１００が担当し、データＡのスレーブ処理はノード１００−１が担当する。また、区間ｈ０＜ｈ（ｋｅｙ）≦ｈ１に属するデータＢのマスタ処理はノード１００−１が担当し、データＢのスレーブ処理はノード１００−２が担当する。また、区間ｈ１＜ｈ（ｋｅｙ）≦ｈ２に属するデータＣのマスタ処理はノード１００−２が担当し、データＣのスレーブ処理はノード１００−３が担当する。

図４は、ノード障害時のデータ配置の変化例を示す図である。あるノードで障害が発生すると、ハッシュ空間上で障害が発生したノードの１つ後ろに位置するノードが、障害が発生したノードのマスタ処理とスレーブ処理を引き継ぐ。これに伴い、ノードへのデータ配置が変化する。ただし、障害の影響を受けるノードは、情報処理システムが備えるノードの全部ではなく一部である。例えば、同じデータがＮ個のノードに記憶されている（冗長度がＮである）場合、障害が発生したノードより後ろのＮ個ノードが影響を受ける。

一例として、ノード１００−１に障害が発生すると、ノード１００−２がデータＢのマスタ処理とデータＡのスレーブ処理を引き継ぐ。ノード１００−２は、データＢのスレーブノードであったため、他のノードからデータＢを取得しなくてよい。一方、ノード１００−２は、データＡの新たなスレーブノードになるため、ノード１００−１が抜けた後の１つ前のノード１００からデータＡを取得することになる。また、ノード１００−３は、ノード１００−２がデータＢのマスタノードになったことに伴い、データＢのスレーブ処理を引き継ぐ。ノード１００−３は、新たにデータＢのスレーブノードになるため、１つ前のノード１００−２からデータＢを取得することになる。

ところで、クライアント装置３１からの要求に従ってあるマスタノードでデータの書き込みが行われると、データの冗長性を維持するために、スレーブノードにその書き込みの結果を反映させることになる。そこで、第２の実施の形態の情報処理システムでは、マスタノードからスレーブノードに、データの書き込みが行われる毎にログを送信する。

図５は、各ノードのハードウェア例を示すブロック図である。ノード１００は、ＣＰＵ１０１、ＲＡＭ１０２、ＨＤＤ１０３、画像信号処理部１０４、入力信号処理部１０５、読み取り装置１０６および通信インタフェース１０７を有する。

ＣＰＵ１０１は、プログラムの命令を実行するプロセッサである。ＣＰＵ１０１は、ＨＤＤ１０３に記憶されているプログラムやデータの少なくとも一部をＲＡＭ１０２にロードし、プログラムを実行する。なお、ＣＰＵ１０１は複数のプロセッサコアを備えてもよく、ノード１００は複数のプロセッサを備えてもよく、以下で説明する処理を複数のプロセッサまたはプロセッサコアを用いて並列実行してもよい。また、複数のプロセッサの集合（マルチプロセッサ）を「プロセッサ」と呼んでもよい。

ＲＡＭ１０２は、ＣＰＵ１０１が実行するプログラムや情報処理に用いられるデータを一時的に記憶する揮発性メモリである。なお、ノード１００は、ＲＡＭ以外の種類のメモリを備えてもよく、複数の種類のメモリを備えてもよい。

ＨＤＤ１０３は、ＯＳ（Operating System）やミドルウェアやアプリケーションソフトウェアなどのソフトウェアのプログラム、および、データを記憶する不揮発性の記憶装置である。なお、ノード１００は、ＳＳＤ（Solid State Drive）などの他の種類の不揮発性の記憶装置を備えてもよく、複数の種類の不揮発性の記憶装置を備えてもよい。

画像信号処理部１０４は、ＣＰＵ１０１からの命令に従って、ノード１００に接続されたディスプレイ４１に画像を出力する。ディスプレイ４１としては、ＣＲＴ（Cathode Ray Tube）ディスプレイ、液晶ディスプレイ（ＬＣＤ：Liquid Crystal Display）、プラズマディスプレイ（ＰＤＰ：Plasma Display Panel）、有機ＥＬ（ＯＥＬＤ：Organic Electro-Luminescence）ディスプレイなど各種のディスプレイを用いることができる。

入力信号処理部１０５は、ノード１００に接続された入力デバイス４２から入力信号を取得し、ＣＰＵ１０１に通知する。入力デバイス４２としては、マウスやタッチパネルやタッチパッドやトラックボールなどのポインティングデバイス、キーボード、リモートコントローラ、ボタンスイッチなど各種の入力デバイスを用いることができる。また、ノード１００には複数の種類の入力デバイスが接続されてもよい。

読み取り装置１０６は、記録媒体４３に記録されたプログラムやデータを読み取るメディアインタフェースである。記録媒体４３として、例えば、フレキシブルディスク（ＦＤ：Flexible Disk）やＨＤＤなどの磁気ディスク、ＣＤ（Compact Disc）やＤＶＤ（Digital Versatile Disc）などの光ディスク、光磁気ディスク（ＭＯ：Magneto-Optical disk）を使用できる。また、記録媒体４３として、例えば、フラッシュメモリカードなどの不揮発性の半導体メモリを使用することもできる。読み取り装置１０６は、例えば、ＣＰＵ１０１からの命令に従って、記録媒体４３から読み取ったプログラムやデータをＲＡＭ１０２またはＨＤＤ１０３に格納する。

通信インタフェース１０７は、ネットワーク３０を介してクライアント装置３１や他のノードと通信を行う。通信インタフェース１０７は、ケーブルが接続される有線通信インタフェースでもよいし、電波や光などの伝送媒体を用いてワイヤレスで通信を行う無線通信インタフェースであってもよい。

ただし、ノード１００は読み取り装置１０６を備えなくてもよく、ノード１００に対するユーザ操作がクライアント装置３１などの他の装置から行える場合には画像信号処理部１０４や入力信号処理部１０５を備えなくてもよい。また、ディスプレイ４１や入力デバイス４２は、ノード１００の筐体と一体に形成されていてもよいし、ワイヤレスで接続されていてもよい。クライアント装置３１やノード１００−１〜１００−６も、上記と同様のハードウェアによって実現できる。

なお、ＣＰＵ１０１は第１の実施の形態の制御部２４の一例、ＲＡＭ１０２は第１の実施の形態のメモリ２１の一例、ＨＤＤ１０３は第１の実施の形態の記憶装置２２の一例、通信インタフェース１０７は第１の実施の形態の受信部２３の一例である。

図６は、各ノードの機能例を示すブロック図である。ノード１００は、データ記憶部１１０、ログ記憶部１２０、ログバッファ１３０、ノード情報記憶部１４０、アクセス処理部１５１、命令実行部１５２、ログ生成部１５３、ログ管理部１５４、ノード監視部１５５および冗長回復部１６０を有する。冗長回復部１６０は、マスタ回復部１６１、スレーブ回復部１６２およびデータ追加部１６３を有する。

データ記憶部１１０は、ＨＤＤ１０３に確保される不揮発性の記憶領域である。データ記憶部１１０は、キーと値（バリュー）の組であるキーバリュー形式のデータレコードを記憶する。データ記憶部１１０は、キーに応じて複数の記憶領域に分割されている。例えば、キーが近いデータレコード同士が、近い位置に記憶される。

ログ記憶部１２０は、ＨＤＤ１０３に確保される不揮発性の記憶領域である。ログ記憶部１２０は、他のノードから受信されデータ記憶部１１０に未反映である書き込み命令のログを記憶する。ログ記憶部１２０は、データ記憶部１１０の記憶領域に対応して複数の記憶領域に分割されている。例えば、データ記憶部１１０上で近い位置に書き込まれるデータレコードについての書き込み命令のログ（例えば、キーが近いデータレコードの書き込み命令のログ）が、ログ記憶部１２０の同じ記憶領域に纏めて記憶される。

ログバッファ１３０は、ＲＡＭ１０２に確保される揮発性の記憶領域である。ログバッファ１３０は、他のノードから受信されログ記憶部１２０に保存していないログを一時的に蓄積する。ログバッファ１３０は、ログ記憶部１２０の記憶領域に対応して複数のバッファ領域に分割されている。例えば、データ記憶部１１０上で近い位置に書き込まれるデータレコードについての書き込み命令のログ（例えば、キーが近いデータレコードの書き込み命令のログ）が、ログバッファ１３０の同じバッファ領域に纏めて蓄積される。

ノード情報記憶部１４０は、ＲＡＭ１０２またはＨＤＤ１０３に確保される記憶領域である。ノード情報記憶部１４０は、ノード１００，１００−１〜１００−６に対するデータの割り当てを示すノード情報を記憶する。例えば、ノード情報は、キーのハッシュ値の区間とマスタノードとの対応関係を示す。図３で説明した方法によってスレーブノードが決定される場合、あるデータのマスタノードとハッシュ空間上でのノードの順序から、当該データのスレーブノードを求めることができる。よって、ノード情報は、キーのハッシュ値の区間とスレーブノードとの対応関係を示す情報を含まなくてもよい。

アクセス処理部１５１は、クライアント装置３１からのアクセスとしてのデータ操作命令を、クライアント装置３１または他のノードからネットワーク３０を介して受信する。データ操作命令の種類には、キーを指定した読み出し命令（リード命令）や、キーと値を指定した書き込み命令（ライト命令）が含まれる。アクセス処理部１５１は、データ操作命令で指定されたキーからハッシュ値を算出し、ノード情報記憶部１４０に記憶されたノード情報を参照して、そのデータ操作命令を実行すべきマスタノードを検索する。検索されたマスタノードがノード１００である場合、アクセス処理部１５１は、データ操作命令を命令実行部１５２に出力する。一方、検索されたマスタノードが他ノードである場合、アクセス処理部１５１は、データ操作命令を検索されたマスタノードに転送する。

命令実行部１５２は、アクセス処理部１５１から取得したデータ操作命令を実行し、実行結果を示す応答メッセージをクライアント装置３１に送信する。すなわち、データ操作命令が読み出し命令である場合、命令実行部１５２は、指定されたキーが示すデータをデータ記憶部１１０から読み出し、読み出したデータをクライアント装置３１に送信する。データ操作命令が書き込み命令である場合、命令実行部１５２は、指定されたキーに応じてデータ記憶部１１０の記憶領域を選択し、選択した記憶領域にキーと対応付けて値を書き込む。このとき、命令実行部１５２は、データ記憶部１１０のデータ構造によって、値と共にキーを書き込むこともあるし書き込まないこともある。

ログ生成部１５３は、命令実行部１５２が書き込み命令を実行したとき、実行された書き込み命令を示すログ（例えば、キーと値の組を示すログ）を生成する。また、ログ生成部１５３は、ノード情報記憶部１４０に記憶されたノード情報を参照して、書き込まれたデータに関するスレーブノードを検索する。そして、ログ生成部１５３は、生成したログを、ネットワーク３０を介してスレーブノードに送信する。

なお、以上の説明ではログとして書き込み命令を示すログを送信することとしたが、書き込み命令を示すログに加えて読み出し命令などの他の命令を示すログも送信するようにしてもよい。また、ログ生成部１５３がログを送信するタイミングは、命令実行部１５２がデータ操作命令の実行結果を示す応答メッセージをクライアント装置３１に送信する前でもよいし送信した後でもよい。また、ログ生成部１５３は、書き込み命令を示すログのコピーを、ノード１００に記憶しておくようにしてもよい。

ログ管理部１５４は、他ノードが送信した書き込み命令のログを受信する。ログ管理部１５４は、書き込み命令で指定されたキーに応じてログバッファ１３０のバッファ領域を選択し、選択したバッファ領域にログを追記する。すなわち、ログ管理部１５４は、受信されたログをすぐにＨＤＤ１０３に書き込まずにＲＡＭ１０２に一時的に蓄積する。

また、ログ管理部１５４は、所定の条件が満たされたとき、ログバッファ１３０の何れかのバッファ領域に蓄積されたログを、当該バッファ領域に対応するログ記憶部１２０の記憶領域に纏めて書き込む。ログ記憶部１２０に書き込んだログは、ログバッファ１３０から削除してよい。１回のログ記憶部１２０への書き込みでは、複数回に分けて受信された複数の書き込み命令分のログを、纏めてシーケンシャルに書き込むことが可能である。所定の条件には、何れかのバッファ領域に蓄積されたログの量が閾値に達したことが含まれる。また、所定の条件には、ノード１００の負荷（例えば、ＣＰＵ使用率やＨＤＤ１０３のＩＯ（Input/Output）頻度）が閾値未満になったことが含まれる。

なお、ノード１００がマスタ処理を担当するデータに関して、マスタノードにもログを保存する場合、ログ生成部１５３がログバッファ１３０またはログ記憶部１２０にログを書き込んでもよい。その場合、ログ生成部１５３は、ログバッファ１３０またはログ記憶部１２０から当該ログを読み出してスレーブノードに転送してもよい。また、ノード１００がスレーブ処理を担当するデータに関して、ログバッファ１３０またはログ記憶部１２０に格納されたログをログ管理部１５４が更に他のノードに転送することもできる。

アクセス処理部１５１、命令実行部１５２およびログ生成部１５３の処理は、マスタ処理に相当する。また、ログ管理部１５４の処理は、スレーブ処理に相当する。好ましくは、ノード１００におけるマスタ処理の優先度を高くし、スレーブ処理の優先度を低くする。また、マスタ処理のＣＰＵ使用率やマスタ処理のＩＯ頻度が低いタイミングで、ログ記憶部１２０へのログの書き込みが行われることが好ましい。

ノード監視部１５５は、分散データ管理に参加する他のノード（ノード１００−１〜１００−６）が正常に稼働しているか監視する。例えば、ノード監視部１５５は、定期的に他のノードにメッセージを送信し、メッセージの送信から一定時間内に応答を得られないノードを障害が発生したノードと判定する。障害が発生したノードが検出されると、ノード監視部１５５は、図４で説明したような方法に従ってデータ配置を計算し、ノード情報記憶部１４０に記憶されたノード情報を更新する。

また、ノード監視部１５５は、障害の発生したノードが、ノード１００がマスタ処理を担当しているデータのスレーブノードまたはノード１００がスレーブ処理を担当しているデータのマスタノードであるとき、冗長回復部１６０に冗長性の回復を依頼する。

冗長回復部１６０は、ノード監視部１５５または他のノードからの依頼に応じて、障害が発生したノードに割り当てられていたデータの冗長性を回復する。
マスタ回復部１６１は、ノード１００がスレーブ処理を担当しているデータのマスタノードに障害が発生したとき、故障したノードに代わってノード１００がマスタノードになるよう制御する。また、マスタ回復部１６１は、正常な他の１つのノードが、ノード１００に代わって新たなスレーブノードになるよう制御する。新たなスレーブノードは、例えば、図３，４で説明したような方法に従って決定することができる。

ノード１００がマスタノードになるにあたり、マスタ回復部１６１は、ログ記憶部１２０からログを読み出し、ログが示す書き込み命令を再実行することでデータ記憶部１１０にデータを書き込む。複数の書き込み命令分のログは、データ記憶部１１０の記憶領域に対応するように分類されている。このため、ログ記憶部１２０の記憶領域単位でログを読み出して再実行すれば、データ記憶部１１０のできる限り近い位置へのデータの書き込みを連続して行うことができ、ＨＤＤ１０３へのアクセスを効率化できる。

また、新たなスレーブノードを設定するにあたり、マスタ回復部１６１は、ログ適用前のデータ記憶部１１０に記憶された関係するデータとログ記憶部１２０に記憶されたログを、新たなスレーブノードに送信する。ただし、マスタ回復部１６１は、ログ適用前のデータとログに代えて、ログ適用後のデータを新たなスレーブノードに送信してもよい。

なお、マスタ回復部１６１は、複数の書き込み命令を再実行する前に、それらの書き込み命令を最適化してもよい。例えば、同じキーを指定した２以上の書き込み命令がログに含まれている場合、それら２以上の書き込み命令のうち最後に実行された１つのみを残して他の書き込み命令を消去してもよい。書き込み命令の最適化は、ログ管理部１５４がログバッファ１３０からログ記憶部１２０にログを移動するときに行ってもよい。また、マスタ回復部１６１は、マスタノードが故障する前であっても、ノード１００の負荷が低いときに、ログ記憶部１２０に記憶されたログをデータ記憶部１１０に反映させてもよい。

スレーブ回復部１６２は、ノード１００がマスタ処理を担当しているデータのスレーブノードに障害が発生したとき、故障したノードに代わって正常な他の１つのノードが新たなスレーブノードになるよう制御する。新たなスレーブノードは、例えば、図３，４で説明したような方法に従って決定することができる。スレーブ回復部１６２は、データ記憶部１１０に記憶された関係するデータを新たなスレーブノードに送信する。

データ追加部１６３は、他のノードからの依頼に応じて、ノード１００が新たなスレーブノードになるよう制御する。データ追加部１６３は、新たなマスタノード（旧スレーブノード）から古いデータと書き込み命令のログを受信すると、古いデータをデータ記憶部１１０に書き込み、書き込み命令のログをログ記憶部１２０（またはログバッファ１３０）に書き込む。そして、データ追加部１６３は、ログが示す書き込み命令を再実行してデータ記憶部１１０上に最新のデータを再現する。また、データ追加部１６３は、マスタノードから最新のデータを受信すると、最新のデータをデータ記憶部１１０に書き込む。

なお、アクセス処理部１５１、命令実行部１５２、ログ生成部１５３、ログ管理部１５４、ノード監視部１５５および冗長回復部１６０は、ＣＰＵ１０１に実行させるプログラムのモジュールとして実現することができる。ただし、これらモジュールの機能の一部または全部を、特定用途の集積回路を用いて実現してもよい。また、ノード１００−１〜１００−６も、ノード１００と同様のモジュールを有する。

図７は、ノード管理テーブルの例を示す図である。ノード管理テーブル１４１は、ノード情報記憶部１４０に記憶されている。ノード管理テーブル１４１は、ハッシュ値とノードＩＤ（Identification）の項目を含む。ハッシュ値の項目には、ハッシュ空間上でのハッシュ値の区間が登録される。ノードＩＤの項目には、キーのハッシュ値が当該区間に属するようなデータのマスタ処理を担当するノード（マスタノード）の識別情報が登録される。ノードの識別情報として、ＩＰアドレスなどの通信アドレスを用いてもよい。

データ操作命令で指定されるキーに対して所定のハッシュ関数を適用してハッシュ値を算出すると、ノード管理テーブル１４１から、当該データ操作命令を実行するべきマスタノードを検索することができる。また、図３で説明したような方法に従ってスレーブノードが決定されている場合、ノード管理テーブル１４１を参照して、検索されたマスタノードの１つ後ろのノードをスレーブノードとして特定することができる。

図８は、マスタ処理の手順例を示すフローチャートである。ここでは、ノード１００がマスタ処理を実行する場合を考えてマスタ処理の手順を説明する。ノード１００は、アクセスを受信する毎に図８に示すマスタ処理を実行する。ノード１００−１〜１００−６においてもノード１００と同様のマスタ処理が実行される。

（Ｓ１１）アクセス処理部１５１は、クライアント装置３１からのアクセスとしてのデータ操作命令を、クライアント装置３１または他のノードから受信する。
（Ｓ１２）アクセス処理部１５１は、データ操作命令で指定されたキーのハッシュ値を算出し、ノード情報記憶部１４０に記憶されたノード管理テーブル１４１からハッシュ値に対応するマスタノードを検索する。そして、アクセス処理部１５１は、検索されたマスタノードが自ノード（ノード１００）であるか判断する。マスタノードが自ノードである場合は処理をＳ１３に進め、自ノードでない場合は処理をＳ１７に進める。

（Ｓ１３）命令実行部１５２は、データ操作命令を実行する。データ操作命令が読み出し命令である場合、命令実行部１５２は、読み出し命令で指定されたキーをもつデータをデータ記憶部１１０から読み出す。データ操作命令が書き込み命令である場合、命令実行部１５２は、キーに応じたデータ記憶部１１０の記憶領域を選択し、選択した記憶領域に書き込み命令で指定されたキーと値の組を書き込む。

（Ｓ１４）命令実行部１５２は、データ操作命令の実行結果を示す応答メッセージを、クライアント装置３１に送信する。読み出し命令を実行した場合、命令実行部１５２は、読み出したデータを応答メッセージに含めて送信する。書き込み命令を実行した場合、命令実行部１５２は、書き込みの成否を示す情報を応答メッセージに含めて送信する。

（Ｓ１５）ログ生成部１５３は、命令実行部１５２が実行したデータ操作命令が書き込み命令であるか判断する。書き込み命令である場合は処理をＳ１６に進め、書き込み命令でない場合（例えば、読み出し命令である場合）はマスタ処理を終了する。なお、書き込みが失敗したときは、処理をＳ１６に進めずにマスタ処理を終了してよい。

（Ｓ１６）ログ生成部１５３は、命令実行部１５２が実行した書き込み命令を示すログを生成する。また、ログ生成部１５３は、ノード管理テーブル１４１を参照して、キーのハッシュ値に対応するスレーブノードを検索する。そして、ログ生成部１５３は、検索されたスレーブノードに生成したログを送信する。その後、マスタ処理を終了する。

（Ｓ１７）アクセス処理部１５１は、検索されたマスタノードにアクセスとしてのデータ操作命令を転送する。そして、マスタ処理を終了する。
なお、前述のように、ログの生成および送信（Ｓ１５，Ｓ１６）は、クライアント装置３１への応答メッセージの送信（Ｓ１４）よりも前に実行してもよい。また、前述のように、ログに記録するデータ操作命令を書き込み命令に限定せず、読み出し命令などの他の種類のデータ操作命令をログに記録してもよい。その場合、ログを受信したスレーブノードがログから書き込み命令のみを抽出するようにしてもよい。

図９は、スレーブ処理の手順例を示すフローチャートである。ここでは、ノード１００がスレーブ処理を実行する場合を考えてスレーブ処理の手順を説明する。ノード１００は、図９に示すスレーブ処理を繰り返し実行する。ノード１００−１〜１００−６においてもノード１００と同様のスレーブ処理が実行される。

（Ｓ２１）ログ管理部１５４は、他ノードからログを受信したか判断する。ログを受信した場合は処理をＳ２２に進め、ログを受信していない場合は処理をＳ２４に進める。
（Ｓ２２）ログ管理部１５４は、ログバッファ１３０に含まれる複数のバッファ領域の中から、ログで指定されているキーに対応するバッファ領域を選択する。

（Ｓ２３）ログ管理部１５４は、選択したバッファ領域に受信したログを追加する。
（Ｓ２４）ログ管理部１５４は、ログバッファ１３０に含まれる各バッファ領域について、当該バッファ領域に蓄積されているログの量（例えば、ログサイズまたはデータ操作命令の数）を確認する。そして、ログ管理部１５４は、ログ量が所定の閾値以上のバッファ領域が使用されているか判断する。条件を満たすバッファ領域が使用されている場合は処理をＳ２６に進め、条件を満たすバッファ領域が使用されていない場合は処理をＳ２５に進める。

（Ｓ２５）ログ管理部１５４は、ノード１００の負荷を測定し、負荷が所定の閾値未満であるか判断する。ノード１００の負荷の指標値としては、例えば、ＣＰＵ使用率やＨＤＤ１０３へのアクセス頻度などを用いることができる。ログ管理部１５４は、マスタ処理に伴う負荷を測定してもよい。ノード１００の負荷が閾値未満の場合は処理をＳ２６に進め、負荷が閾値以上である場合はスレーブ処理を終了する。

（Ｓ２６）ログ管理部１５４は、ログバッファ１３０のバッファ領域を１つ選択する。ログ量が閾値以上のバッファ領域がある場合は、ログ量が閾値以上のバッファ領域を選択する。ログ量が閾値以上のバッファ領域がない場合は、任意のバッファ領域を選択してもよいし、ログ量が最も多いバッファ領域を選択するようにしてもよい。

（Ｓ２７）ログ管理部１５４は、選択したバッファ領域に蓄積されているログをログ記憶部１２０に書き込む。このとき、複数のデータ操作命令分のログを纏めてシーケンシャルにログ記憶部１２０に書き込むことが可能である。ログ記憶部１２０に書き込んだログはログバッファ１３０から削除してよい。そして、スレーブ処理を終了する。

このように、ログ管理部１５４は、マスタノードからログを受信すると、受信したログをすぐにＨＤＤ１０３に書き込まずにＲＡＭ１０２に蓄積する。そして、ログ管理部１５４は、ＲＡＭ１０２に蓄積されたログが多くなるかノード１００の負荷が低くなるのを待って、複数のデータ操作命令分のログを纏めてＨＤＤ１０３に移動させる。

図１０は、冗長回復の手順例を示すフローチャートである。ここでは、ノード１００が他のノードの障害を検出した場合を考えて冗長回復の手順を説明する。ノード１００−１〜１００−６においてもノード１００と同様の冗長回復が行われる。

（Ｓ３１）ノード監視部１５５は、他ノードの障害を検出する。
（Ｓ３２）ノード監視部１５５は、ノード情報記憶部１４０に記憶されたノード管理テーブル１４１を参照して、故障したノードが、ノード１００がスレーブ処理を担当するデータについてのマスタノードであるか判断する。故障したノードがマスタノードである場合は処理をＳ３３に進め、マスタノードでない場合は処理をＳ３６に進める。

（Ｓ３３）マスタ回復部１６１は、故障したマスタノードに代わってノード１００がマスタノードになることを決定する。また、マスタ回復部１６１は、正常なノードの中から新たなスレーブノードを決定する。新たなスレーブノードは、例えば、図４で説明したように、ハッシュ空間上でノード１００の１つ後ろに配置されたノード１００−１とする。

（Ｓ３４）マスタ回復部１６１は、データ記憶部１１０に記憶されている関係するデータとログ記憶部１２０に記憶されているログを、新たなスレーブノードに送信する。新たなスレーブノードでは、ログが適用される前の古いデータに対してログが示す書き込み命令を再実行することで最新のデータが再現される。

（Ｓ３５）マスタ回復部１６１は、ログ記憶部１２０に記憶されたログが示す書き込み命令を再実行することで、故障したマスタノードに記憶されていた最新のデータをデータ記憶部１１０上に再現する。このとき、マスタ回復部１６１は、ログ記憶部１２０の記憶領域単位でログを再実行することで、データ記憶部１１０上の近い位置へのデータの書き込みを連続的に行うことができる。そして、処理をＳ３９に進める。

なお、前述のように、まずデータ記憶部１１０に対してログを適用し（Ｓ３５）、再現された最新のデータを新たなスレーブノードに送信するようにしてもよい。その場合、新たなスレーブノードではログを適用する処理を行わなくてよい。

（Ｓ３６）ノード監視部１５５は、ノード管理テーブル１４１を参照して、故障したノードが、ノード１００がマスタ処理を担当するデータについてのスレーブノードであるか判断する。故障したノードがスレーブノードである場合は処理をＳ３７に進め、スレーブノードでない場合は処理をＳ３９に進める。

（Ｓ３７）スレーブ回復部１６２は、正常なノードの中から、故障したスレーブノードに代わる新たなスレーブノードを決定する。新たなスレーブノードは、例えば、ハッシュ空間上で故障したスレーブノードの１つ後ろに配置されたノードとする。

（Ｓ３８）スレーブ回復部１６２は、データ記憶部１１０に記憶されている関係するデータを新たなスレーブノードに送信する。ノード１００はマスタノードであることから、着目するデータについてデータ記憶部１１０には最新のデータが記憶されている。新たなスレーブノードでは、ノード１００から送信された最新のデータが保存される。

（Ｓ３９）ノード監視部１５５は、故障したノードを除外した後のデータ配置を計算してノード管理テーブル１４１を更新する。例えば、図４で説明したように、故障したノードのマスタ処理とスレーブ処理を、ハッシュ空間上で故障したノードの１つ後ろに位置するノードが引き継ぐ。また、例えば、故障したノードの１つ後ろのノードが担当していたスレーブ処理を、故障したノードの２つ後ろに位置するノードが引き継ぐ。

図１１は、ノード間の第１の通信例を示す図である。ここでは、ノード１００がキー＝Ａ，Ａ１，Ａ２のデータのマスタノードであり、ノード１００−１がキー＝Ａ，Ａ１，Ａ２のデータのスレーブノードであるとする。また、データの冗長度は２であり、ノード１００−２はキー＝Ａ，Ａ１，Ａ２のデータについてマスタ処理もスレーブ処理も担当していないとする。なお、図１１では、ノード１００が行う他のデータのスレーブ処理やノード１００−１が行う他のデータのマスタ処理については説明を省略している。

ノード１００は、キー＝Ａ，Ａ１，Ａ２を指定したデータ操作命令を受け付ける。例えば、ノード１００は、キー＝Ａ１のデータに対する値＝６０の書き込み命令、キー＝Ａ２のデータに対する値＝７０の書き込み命令、キー＝Ａ１のデータに対する読み出し命令、キー＝Ａのデータに対する値＝１００の書き込み命令を順に受け付ける。すると、ノード１００は、これらのデータ操作命令を順次実行する。これにより、ノード１００のＨＤＤ１０３には、キーバリュー形式のデータとして、キー＝Ａに対応する値＝１００、キー＝Ａ１に対応する値＝６０、キー＝Ａ２に対応する値＝７０が記憶される。

また、ノード１００は、実行された書き込み命令を示すログをノード１００−１に順次送信する。例えば、ノード１００は、キー＝Ａ１のデータに対する値＝６０の書き込み命令を示すログ、キー＝Ａ２のデータに対する値＝７０の書き込み命令を示すログ、キー＝Ａのデータに対する値＝１００の書き込み命令を示すログを、ノード１００−１に順次送信する。キー＝Ａ１の読み出し命令を示すログは、ノード１００−１に送信してもよいし送信しなくてもよい。

ノード１００−１は、ノード１００から受信したログをノード１００−１のＨＤＤ１０３−１にはすぐに書き込まずに、ノード１００−１のＲＡＭ１０２−１に一時的に蓄積する。そして、ＲＡＭ１０２−１に蓄積されたログの量が閾値に達するか、または、ノード１００−１の負荷が低くなったタイミングで、ノード１００−１は、蓄積されたログを纏めてＨＤＤ１０３−１に移動する。例えば、ノード１００−１は、キー＝Ａ１のデータに対する値＝６０の書き込み命令を示すログ、キー＝Ａ２のデータに対する値＝７０の書き込み命令を示すログ、キー＝Ａのデータに対する値＝１００の書き込み命令を示すログをＨＤＤ１０３−１に書き込む。

ここで、ノード１００−１は、ＨＤＤ１０３−１に保存したログを、ノード１００が保持しているデータに対応するバックアップコピーにすぐには反映させない。ノード１００がマスタ処理を担当しておりノード１００に保存されている最新のデータと、ノード１００−１がスレーブ処理を担当しておりノード１００のデータに対応してノード１００−１に保存されているデータであるバックアップコピーとが、一時的に同一でなくなる。すなわち、ノード１００がもつキー＝Ａ，Ａ１，Ａ２のデータは最新である一方、ノード１００−１がもつバックアップコピーは最新でない。ただし、ノード１００−１は、ＨＤＤ１０３−１に記憶されたログをバックアップコピーに適用することで、後で（例えば、ノード１００に障害が発生したときに）最新のデータを復元することが可能である。

図１２は、ノード間の第２の通信例を示す図である。ここでは、図１１の状態でノード１００に障害が発生した場合を考える。ノード１００−１は、キー＝Ａ，Ａ１，Ａ２のデータのスレーブノードであることから、キー＝Ａ，Ａ１，Ａ２のデータのマスタノードであるノード１００の故障を検出すると、これらデータの冗長性の回復を制御する。

ノード１００−１は、ノード１００に代わって自ノードがキー＝Ａ，Ａ１，Ａ２のデータのマスタノードになると決定する。すると、ノード１００−１は、ノード１００−１に代わってスレーブノードになるべきノード１００−２に、キー＝Ａ，Ａ１，Ａ２のバックアップコピー（ログ適用前）とログを送信する。そして、ノード１００−１は、古いバックアップコピーに対してログを適用し、ノード１００がもっていた最新のデータを復元する。これにより、例えば、ＨＤＤ１０３−１には、キー＝Ａに対応する値＝１００、キー＝Ａ１に対応する値＝６０、キー＝Ａ２に対応する値＝７０という最新のデータが復元される。

ノード１００−２は、ノード１００−１から古いバックアップコピーとログを受信すると、バックアップコピーに対してログを適用して最新のデータを復元する。これにより、例えば、ノード１００−２のＨＤＤ１０３−２には、キー＝Ａに対応する値＝１００、キー＝Ａ１に対応する値＝６０、キー＝Ａ２に対応する値＝７０という最新のデータが復元される。以降、ノード１００−２は、キー＝Ａ，Ａ１，Ａ２のデータのスレーブノードになる。ノード１００−２のデータの復元は、ノード１００−１のデータの復元と並列に行うことが可能である。

ただし、ノード１００−１からノード１００−２には、ノード１００−１でログを適用した後の最新のデータを送信するようにしてもよい。また、上記の説明では、新たなスレーブノードであるノード１００−２が最新のデータを復元するとしたが、最新のデータを復元せずに古いバックアップコピーとログを保持してもよい。その場合、例えば、ノード１００−１が故障したときに最新のデータを復元すればよい。

図１３は、ノード間の第３の通信例を示す図である。ここでは、図１１の状態でノード１００−１に障害が発生した場合を考える。ノード１００は、キー＝Ａ，Ａ１，Ａ２のデータのマスタノードであることから、キー＝Ａ，Ａ１，Ａ２のデータのスレーブノードであるノード１００−１の故障を検出すると、これらデータの冗長性の回復を制御する。

ノード１００は、ノード１００−１に代わってスレーブノードになるべきノード１００−２に、キー＝Ａ，Ａ１，Ａ２の最新のデータを送信する。ノード１００−２は、ノード１００から受信した最新のデータを、ノード１００−２のＨＤＤ１０３−２に記憶する。例えば、ノード１００−２のＨＤＤ１０３−２に、キー＝Ａに対応する値＝１００、キー＝Ａ１に対応する値＝６０、キー＝Ａ２に対応する値＝７０という最新のデータが格納される。以降、ノード１００−２は、キー＝Ａ，Ａ１，Ａ２のデータのスレーブノードになる。

以上、データの冗長度が２である（同じデータが２つのノードに記憶される）場合を例に、データの配置の変化を説明した。ただし、データの冗長度を３以上にすることも可能である。その場合、同じデータが記憶される３つ以上のノードのうち、何れか１つがマスタノードになり、残りの２つ以上のノードがスレーブノードになる。２つ以上のスレーブノードは、好ましくは、第１スレーブノード，第２スレーブノード，・・・のように順位付けされる。第１スレーブノードは、１つ上位のノード（当初のマスタノード）が故障したときに新たなマスタノードになる。第２スレーブノード以下のノードは、それより上位のノードの１つが故障したときに１つ上位のスレーブノードに繰り上がる。その際、最下位のスレーブノードが新たに割り当てられる。

図１４は、他のデータ配置例を示す図である。ここでは、データの冗長度が３に設定されており、同じデータが３つのノードに重複して記憶される場合を考える。
各ノードは、図３の例と同様に、ハッシュ空間上で１つ前のノードとの間の区間に属するデータのマスタノードになる。そして、あるデータのマスタノードの１つ後ろに位置するノードが当該データの第１スレーブノードになり、あるデータのマスタノードの２つ後ろに位置するノードが当該データの第２スレーブノードになる。

例えば、ｈ（）をハッシュ関数とすると、区間ｈ６＜ｈ（ｋｅｙ）≦２^L−１または０≦ｈ（ｋｅｙ）≦ｈ０に属するデータＡのマスタノードはノード１００になり、データＡの第１スレーブノードはノード１００−１になり、データＡの第２スレーブノードはノード１００−２になる。また、区間ｈ０＜ｈ（ｋｅｙ）≦ｈ１に属するデータＢのマスタノードはノード１００−１になり、データＢの第１スレーブノードはノード１００−２になり、データＢの第２スレーブノードはノード１００−３になる。また、区間ｈ１＜ｈ（ｋｅｙ）≦ｈ２に属するデータＣのマスタノードはノード１００−２になり、データＣの第１スレーブノードはノード１００−３になり、データＣの第２スレーブノードはノード１００−４という具合になる。

図１５は、ノード間の第４の通信例を示す図である。ここでは、ノード１００がキー＝Ａ，Ａ１，Ａ２のデータのマスタノードであり、ノード１００−１がキー＝Ａ，Ａ１，Ａ２のデータの第１スレーブノードであり、ノード１００−２がキー＝Ａ，Ａ１，Ａ２のデータの第２スレーブノードである。また、データの冗長度は３であり、ノード１００−３はキー＝Ａ，Ａ１，Ａ２のデータについてマスタ処理もスレーブ処理も担当していない。

ノード１００は、冗長度が２の場合（図１１に示した例）と同様に、キー＝Ａ，Ａ１，Ａ２のデータを指定したデータ操作命令を受け付け、これらのデータ操作命令を順次実行する。また、ノード１００は、実行された書き込み命令を示すログを第１スレーブノードであるノード１００−１に順次送信する。例えば、ノード１００は、キー＝Ａ１のデータに対する値＝６０の書き込み命令を示すログ、キー＝Ａ２のデータに対する値＝７０の書き込み命令を示すログ、キー＝Ａのデータに対する値＝１００の書き込み命令を示すログを、ノード１００−１に順次送信する。

ノード１００−１は、冗長度が２の場合（図１１に示した例）と同様に、ノード１００から受信したログをノード１００−１のＨＤＤ１０３−１にはすぐに書き込まずに、ノード１００−１のＲＡＭ１０２−１に一時的に蓄積する。そして、ＲＡＭ１０２−１に蓄積されたログの量が閾値に達するか、または、ノード１００−１の負荷が低くなったタイミングで、ノード１００−１は、蓄積されたログを纏めてＨＤＤ１０３−１に移動する。

また、ノード１００−１は、ノード１００から受信したログをコピーして、第２スレーブノードであるノード１００−２に転送する。ただし、ノード１００−１がノード１００−２にログを転送する代わりに、ノード１００がログをコピーしてノード１００−１，１００−２にそれぞれ送信するようにしてもよい。ノード１００−２は、受信したログをノード１００−２のＨＤＤ１０３−２にすぐには書き込まずに、ノード１００−２のＲＡＭ１０２−２に一時的に蓄積する。そして、ＲＡＭ１０２−２に蓄積されたログの量が閾値に達するか、または、ノード１００−２の負荷が低くなったタイミングで、ノード１００−２は、蓄積されたログを纏めてＨＤＤ１０３−２に移動する。

図１６は、ノード間の第５の通信例を示す図である。ここでは、図１５の状態でノード１００に障害が発生した場合を考える。ノード１００−１，１００−２は、キー＝Ａ，Ａ１，Ａ２のデータのスレーブノードであることから、キー＝Ａ，Ａ１，Ａ２のデータのマスタノードであるノード１００の故障を検出するとデータの冗長性の回復を制御する。

ノード１００−１は、ノード１００に代わって自ノードがキー＝Ａ，Ａ１，Ａ２のデータのマスタノードになると決定する。すると、ノード１００−１は、古いバックアップコピーに対してログを適用し、ノード１００がもっていた最新のデータを復元する。これにより、例えば、ノード１００−１のＨＤＤ１０３−１には、キー＝Ａに対応する値＝１００、キー＝Ａ１に対応する値＝６０、キー＝Ａ２に対応する値＝７０という最新のデータが復元される。

ノード１００−２は、ノード１００−１に代わって自ノードがキー＝Ａ，Ａ１，Ａ２のデータの第１スレーブノードになると決定する。すると、ノード１００−２は、ノード１００−２に代わって第２スレーブノードになるべきノード１００−３に、キー＝Ａ，Ａ１，Ａ２のバックアップコピー（ログ適用前）とログを送信する。このとき、ノード１００−２は第２スレーブノードであったため、キー＝Ａ，Ａ１，Ａ２のデータのバックアップコピーやログをノード１００−１から受信しなくてよい。そして、ノード１００−２は、ノード１００−１と同様、古いバックアップコピーに対してログを適用して最新のデータを復元することができる。これにより、例えば、ノード１００−２のＨＤＤ１０３−２には、キー＝Ａに対応する値＝１００、キー＝Ａ１に対応する値＝６０、キー＝Ａ２に対応する値＝７０という最新のデータが復元される。

ノード１００−３は、ノード１００−２から古いバックアップコピーとログを受信すると、バックアップコピーに対してログを適用して最新のデータを復元することができる。これにより、例えば、ノード１００−３のＨＤＤ１０３−３には、キー＝Ａに対応する値＝１００、キー＝Ａ１に対応する値＝６０、キー＝Ａ２に対応する値＝７０という最新のデータが復元される。ノード１００−１〜１００−３のデータ復元は、互いに並列に行うことができる。

ただし、第２スレーブノードであったノード１００−２からノード１００−３にバックアップコピーやログを送信する代わりに、第１スレーブノードであったノード１００−１からノード１００−３にバックアップコピーやログを送信してもよい。また、ノード１００−２（または、ノード１００−１）が最新のデータを復元してから、ノード１００−３に最新のデータのコピーを送信してもよい。また、上記の説明では、第２スレーブノードから第１スレーブノードに変わったノード１００−２が最新のデータを復元することとしたが、最新のデータを復元せずに古いバックアップコピーとログを保持してもよい。その場合、例えば、ノード１００−１が故障したときに最新のデータを復元すればよい。同様に、ノード１００−３が最新のデータを復元しないようにしてもよい。

第２の実施の形態の情報処理システムによれば、ノード１００，１００−１〜１００−６がマスタ処理を分担するため、クライアント装置３１からのアクセスの負荷が分散される。また、マスタ処理を行うノードと異なるノードがデータのバックアップコピーを管理してデータを冗長化しておくため、耐故障性が向上する。また、各ノードがマスタ処理とスレーブ処理を兼ねるため、コンピュータの処理能力を効率的に利用できる。

また、マスタノードで書き込み命令が実行されたとき、すぐにスレーブノードがもつバックアップコピーに書き込みを反映させるのではなく、スレーブノードにログが保存される。このため、スレーブ処理によるＨＤＤへのランダムアクセスを減らし、マスタ処理の性能への影響を軽減することができる。更に、ログはマスタノードからスレーブノードに送信される毎にＨＤＤに書き込まれるのではなくＲＡＭに一時的に蓄積され、後で複数の書き込み命令分のログがシーケンシャルにＨＤＤに書き込まれる。このため、スレーブ処理によるＨＤＤへのランダムアクセスを更に減らすことができる。このように、ランダムアクセスが低速なＨＤＤを用いてデータを管理していても、スレーブ処理の影響でマスタ処理の性能が低下することを抑制し、スループットを向上させることができる。

なお、前述のように、第１の実施の形態の情報処理は、ノード１０，２０にプログラムを実行させることで実現できる。また、第２の実施の形態の情報処理は、クライアント装置３１やノード１００，１００−１〜１００−６にプログラムを実行させることで実現できる。プログラムは、コンピュータ読み取り可能な記録媒体（例えば、記録媒体４３）に記録しておくことができる。記録媒体としては、例えば、磁気ディスク、光ディスク、光磁気ディスク、半導体メモリなどを使用できる。磁気ディスクには、ＦＤおよびＨＤＤが含まれる。光ディスクには、ＣＤ、ＣＤ−Ｒ（Recordable）／ＲＷ（Rewritable）、ＤＶＤおよびＤＶＤ−Ｒ／ＲＷが含まれる。プログラムは、可搬型の記録媒体に記録されて配布されることがある。その場合、可搬型の記録媒体からＨＤＤなどの他の記録媒体（例えば、ＨＤＤ１０３）にプログラムを複製して（インストールして）実行してもよい。

１０，２０ ノード
２１ メモリ
２２ 記憶装置
２３ 受信部
２４ 制御部

Claims (6)

1. 第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に前記第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムにおいて、前記第２のノードとして用いられるコンピュータに、
   前記第１のデータ集合に属するデータに対して実行された命令を示すログを前記第１のノードから受信し、受信したログを前記コンピュータが備えるメモリに格納し、
   前記コンピュータの負荷が閾値未満であるときに、前記メモリに蓄積された複数の命令分のログを前記コンピュータが備える前記メモリと異なる記憶装置に書き込む、
   処理を実行させるプログラム。
2. 第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に前記第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムにおいて、前記第２のノードとして用いられるコンピュータに、
   前記第１のデータ集合に属するデータに対して実行された命令を示すログを前記第１のノードから受信し、受信したログを前記コンピュータが備えるメモリに格納し、
   前記メモリに蓄積されたログの量が閾値以上になったときに、前記メモリに蓄積された複数の命令分のログを前記コンピュータが備える前記メモリと異なる記憶装置に書き込む、
   処理を実行させるプログラム。
3. 第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に前記第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムにおいて、前記第２のノードとして用いられるコンピュータに、
   前記第１のデータ集合に属するデータに対して実行された命令を示すログを前記第１のノードから受信し、受信したログが示す命令によって指定されたデータのキーに応じて、当該受信したログを前記コンピュータが備えるメモリに設けられた複数のバッファ領域の何れか１つに格納し、
   所定の条件が満たされたタイミングで、バッファ領域単位で、前記メモリに蓄積された複数の命令分のログを前記コンピュータが備える前記メモリと異なる記憶装置に書き込む、
   処理を実行させるプログラム。
4. 第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に前記第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムにおいて、前記第２のノードとして用いられるコンピュータに、
   前記第１のデータ集合に属するデータに対して実行された命令を示すログを前記第１のノードから受信し、受信したログを前記コンピュータが備えるメモリに格納し、
   所定の条件が満たされたタイミングで、前記メモリに蓄積された複数の命令分のログを前記コンピュータが備える前記メモリと異なる記憶装置に書き込み、
   前記第１のノードの障害を検出し、
   前記障害が検出されると、前記記憶装置に書き込まれたログまたは当該ログに基づいて復元された前記第１のデータ集合を第３のノードに送信することで、前記第３のノードに前記第１のデータ集合のバックアップコピーを管理させる、
   処理を実行させるプログラム。
5. 第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に前記第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムが実行するデータ管理方法であって、
   前記第１のデータ集合に属するデータに対して実行された命令を示すログを前記第１のノードから前記第２のノードに送信し、
   送信されたログを前記第２のノードが備えるメモリに格納し、
   前記第２のノードの負荷が閾値未満であるときに、前記メモリに蓄積された複数の命令分のログを前記第２のノードが備える前記メモリと異なる記憶装置に書き込む、
   データ管理方法。
6. 第１のデータ集合が割り当てられた第１のノードと、第２のデータ集合が割り当てられると共に前記第１のデータ集合のバックアップコピーを管理する第２のノードとを備えるシステムにおいて、前記第２のノードとして用いられる情報処理装置であって、
   メモリと、
   前記メモリと異なる記憶装置と、
   前記第１のデータ集合に属するデータに対して実行された命令を示すログを前記第１のノードから受信する受信部と、
   受信したログを前記メモリに格納し、前記情報処理装置の負荷が閾値未満であるときに、前記メモリに蓄積された複数の命令分のログを前記記憶装置に書き込む制御部と、
   を有する情報処理装置。
   

Images