(57)【特許請求の範囲】
【請求項１】
ネットワークを介して複数の計算機が接続され、前記複数の計算機の各々が有する記憶領域から構成されたデータベースを用いて業務を実行する計算機システムであって、
前記データベースに格納されるデータは、前記データの識別情報、前記データの値、及び前記データベースにおけるイベントの実行順番であるシーケンス番号を含み、
前記複数の計算機の各々には、前記データの識別情報に対して分散配置アルゴリズムを適用して決定された管理範囲毎に当該データが分散して配置され、
前記複数の計算機の各々は、
配置されたデータを管理するデータ管理部と、
配置されたデータに対する操作の前記シーケンス番号を決定するデータ制御部と、
新たに追加された計算機に、所定の管理範囲に含まれるデータの複製データを送信する復旧制御部と、を有し、
前記複数の計算機は、復旧要求を送信する第１の計算機、及び前記復旧要求を受信する第２の計算機を含み、
前記第２の計算機は、
前記第１の計算機から復旧要求を受信し、前記第２の計算機の状態を復旧状態に遷移させ、前記シーケンス番号に基づいて前記データベースからデータを一つ以上読み出し、第１の複製データとして前記第１の計算機に送信する複製処理と、
前記復旧状態において前記データの更新命令を受信した場合、前記更新命令の前記シーケンス番号を決定し、前記更新命令に基づいて所定のデータを更新し、第２の複製データとして送信する更新処理と、を実行し、
前記第１の計算機又は前記第２の計算機の少なくともいずれか一方が、前記第１の計算機における前記第１の複製データ及び前記第２の複製データの書き込み順番を制御し、
前記第１の計算機は、前記書き込み順番に基づいて、前記第１の複製データ及び前記第２の複製データを前記データベースを構成する記憶領域に書き込む書込処理を実行することを特徴とする計算機システム。
【請求項２】
請求項１に記載の計算機システムであって、
前記複数の計算機の各々は、前記シーケンス番号、及び前記データベースにおけるイベントの内容が対応づけられた履歴情報を保持し、
前記復旧要求は、処理対象の前記管理範囲を示す情報を含み、
前記複製処理では、
前記第２の計算機の復旧制御部が、
前記復旧要求を受信した場合、前記履歴情報に基づいて、最新のシーケンス番号を複製シーケンス番号として保持し、
前記処理対象の管理範囲の排他ロックを取得し、
前記処理対象の管理範囲に含まれるデータの中から、未送信のデータ、かつ、前記複製シーケンス番号より古い前記シーケンス番号を含むデータを一つ以上読み出して、前記第１の複製データとして前記第１の計算機の復旧制御部に送信し、
前記取得された排他ロックを解放し、
前記更新処理では、
前記第２の計算機のデータ管理部が、
前記処理対象の管理範囲の前記排他ロックを取得し、
前記更新命令に基づいて前記所定のデータを更新し、前記第１の複製データの送信指示を前記第２の計算機の復旧制御部に出力し、
前記取得された排他ロックを解放し、
前記第２の計算機の復旧制御部が、前記送信指示に基づいて前記第１の複製データを前記第１の計算機の復旧制御部に送信し、
前記書込処理では、前記第１の計算機の復旧制御部が、受信した順番にしたがって、前記第１の複製データ及び前記第２の複製データを前記データベースを構成する記憶領域に書き込むことを特徴とする計算機システム。
【請求項３】
請求項１に記載の計算機システムであって、
前記複数の計算機の各々は、
前記シーケンス番号、及び前記データベースにおけるイベントの内容が対応づけられた履歴情報を保持し、
前記第１の複製データ及び前記第２の複製データを一時的に格納する作業記憶領域を有し、
前記復旧要求は、処理対象の前記管理範囲を示す情報を含み、
前記複製処理では、
前記第２の計算機の復旧制御部が、
前記復旧要求を受信した場合、前記履歴情報に基づいて、最新のシーケンス番号を複製シーケンス番号として保持し、
前記処理対象の管理範囲に含まれるデータの中から、未送信のデータ、かつ、前記複製シーケンス番号より古い前記シーケンス番号を含むデータを一つ以上読み出して、前記第１の複製データとして前記第１の計算機の復旧制御部に送信し、
前記更新処理では、
前記第２の計算機のデータ管理部が、前記更新命令に基づいて前記所定のデータを更新し、前記第１の複製データの送信指示を前記第２の計算機の復旧制御部に出力し、
前記第２の計算機の復旧制御部が、前記送信指示に基づいて前記第１の複製データを前記第１の計算機の復旧制御部に送信し、
前記書込処理では、
前記第１の計算機の復旧制御部が、
前記受信した第１の複製データ及び前記受信した第２の複製データを前記作業記憶領域に格納し、
前記データベース及び前記作業記憶領域の中から、同一の前記データの識別情報を含む、前記第１の複製データ及び前記第２の複製データを検索し、
前記検索された第１の複製データに含まれる前記シーケンス番号、及び前記検索された第２の複製データに含まれる前記シーケンス番号を参照して、最新の前記シーケンス番号を含む複製データを選択し、
前記選択された複製データを前記データベースを構成する記憶領域に書き込むことを特徴とする計算機システム。
【請求項４】
請求項３に記載の計算機システムであって、
前記データベースに格納されるデータは、さらに、削除対象のデータであるか否かを示す削除フラグを含み、
前記更新処理では、前記第２の計算機のデータ管理部が、前記更新命令がデータの削除命令である場合に、前記削除フラグが付与された削除対象のデータを前記第１の複製データとして前記第１の計算機の復旧制御部に送信し、
前記書込処理では、前記第１の計算機のデータ管理部が、前記データベースに書き込まれたデータのうち、前記削除フラグが付与されたデータを、前記データベースを構成する記憶領域から削除すること特徴とする計算機システム。
【請求項５】
請求項２又は請求項３のいずれか一項に記載の計算機システムであって、
前記複数の計算機の各々は、前記複数の計算機の各々がマスタとして管理する前記管理範囲、及びスレーブとして管理する前記管理範囲を示す構成情報を保持し、
前記複製処理では、
前記第２の計算機の復旧制御部が、前記複製シーケンス番号を含む前記第１の複製データが送信された後、前記複数の計算機に前記第１の計算機を追加するための合流イベントの前記シーケンス番号である合流シーケンス番号の決定を前記第２の計算機のデータ制御部に指示し、
前記第２の計算機のデータ制御部が、
分散合意アルゴリズムに基づいて、前記複数の計算機の各々の前記データ制御部と通信することによって前記合流シーケンス番号を決定し、
前記決定された合流シーケンス番号、及び、前記合流イベントの内容が対応づけられた前記履歴情報を保持し、
前記決定された合流シーケンス番号を前記第２の計算機の復旧制御部に出力し、
前記更新処理では、
前記第２の計算機のデータ管理部が、
前記第１の複製データが送信された後に、当該第１の複製データに含まれる前記シーケンス番号と、前記合流シーケンス番号とを比較して、前記合流イベントが発生するか否かを判定し、
前記合流イベントが発生すると判定された場合、前記第１の計算機の復旧制御部に、前記合流シーケンス番号を送信し、
前記合流イベントでは、前記第１の計算機が前記処理対象の管理範囲のマスタとなるように前記構成情報が更新されることを特徴とする計算機システム。
【請求項６】
請求項５に記載の計算機システムであって、
前記第１の計算機は、
前記処理対象の管理範囲をマスタとして管理する計算機、又は、前記処理対象の管理範囲をスレーブとして管理する計算機の少なくともいずれか一方の計算機を前記第２の計算機として選択し、
前記選択された第２の計算機に前記復旧要求を送信することを特徴とする計算機システム。
【請求項７】
ネットワークを介して複数の計算機が接続され、前記複数の計算機の各々が有する記憶領域から構成されたデータベースを用いて業務を実行する計算機システムにおける計算機システム管理方法であって、
前記複数の計算機の各々は、プロセッサと、前記プロセッサに接続されるメモリと、前記プロセッサと接続され、前記ネットワークを介して他の前記計算機と通信するためのネットワークインタフェースとを有し、
前記データベースに格納されるデータは、前記データの識別情報、前記データの値、及び前記データベースにおけるイベントの実行順番であるシーケンス番号を含み、
前記複数の計算機の各々には、前記データの識別情報に対して分散配置アルゴリズムを適用することによって決定された管理範囲毎に当該データが分散して配置され、
前記複数の計算機の各々は、
配置されたデータを管理するデータ管理部と、
配置されたデータに対する操作の前記シーケンス番号を決定するデータ制御部と、
新たに追加された計算機に、所定の管理範囲に含まれるデータの複製データを送信する復旧制御部と、を有し、
前記複数の計算機は、復旧要求を送信する第１の計算機、及び前記復旧要求を受信する第２の計算機を含み、
前記方法は、
前記第２の計算機が、前記第１の計算機から復旧要求を受信し、前記第２の計算機の状態を復旧状態に遷移させ、前記シーケンス番号に基づいて前記データベースからデータを一つ以上読み出し、第１の複製データとして前記第１の計算機に送信する複製処理を実行するステップと、
前記第２の計算機が、前記復旧状態において前記データの更新命令を受信した場合、前記更新命令の前記シーケンス番号を決定し、前記更新命令に基づいて所定のデータを更新し、第２の複製データとして送信する更新処理を実行するステップと、
前記第１の計算機又は前記第２の計算機の少なくともいずれか一方が、前記第１の計算機における前記第１の複製データ及び前記第２の複製データの書き込み順番を制御するステップと、
前記第１の計算機が、前記書き込み順番に基づいて、前記第１の複製データ及び前記第２の複製データを前記データベースを構成する記憶領域に書き込む書込処理を実行するステップと、を含むことを特徴とする計算機システム管理方法。
【請求項８】
請求項７に記載の計算機システム管理方法であって、
前記複数の計算機の各々は、前記シーケンス番号、及び前記データベースにおけるイベントの内容が対応づけられた履歴情報を保持し、
前記復旧要求は、処理対象の前記管理範囲を示す情報を含み、
前記複製処理は、
前記第２の計算機の復旧制御部が、
前記復旧要求を受信した場合、前記履歴情報に基づいて、最新のシーケンス番号を複製シーケンス番号として保持するステップと、
前記処理対象の管理範囲の排他ロックを取得するステップと、
前記処理対象の管理範囲に含まれるデータの中から、未送信のデータ、かつ、前記複製シーケンス番号より古い前記シーケンス番号を含むデータを一つ以上読み出して、前記第１の複製データとして前記第１の計算機の復旧制御部に送信するステップと、
前記取得された排他ロックを解放するステップと、を含み、
前記更新処理は、
前記第２の計算機のデータ管理部が、
前記処理対象の管理範囲の前記排他ロックを取得するステップと、
前記更新命令に基づいて前記所定のデータを更新し、前記第１の複製データの送信指示を前記第２の計算機の復旧制御部に出力するステップと、
前記取得された排他ロックを解放するステップと、
前記第２の計算機の復旧制御部が、前記送信指示に基づいて前記第１の複製データを前記第１の計算機の復旧制御部に送信するステップと、を含み、
前記書込処理では、前記第１の計算機の復旧制御部が、受信した順番にしたがって、前記第１の複製データ及び前記第２の複製データを前記データベースを構成する記憶領域に書き込むことを特徴とする計算機システム管理方法。
【請求項９】
請求項７に記載の計算機システム管理方法であって、
前記複数の計算機の各々は、
前記シーケンス番号、及び前記データベースにおけるイベントの内容が対応づけられた履歴情報を保持し、
前記第１の複製データ及び前記第２の複製データを一時的に格納する作業記憶領域を有し、
前記復旧要求は、処理対象の前記管理範囲を示す情報を含み、
前記複製処理は、
前記第２の計算機の復旧制御部が、
前記復旧要求を受信した場合、前記履歴情報に基づいて、最新のシーケンス番号を複製シーケンス番号として保持するステップと、
前記処理対象の管理範囲に含まれるデータの中から、未送信のデータ、かつ、前記複製シーケンス番号より古い前記シーケンス番号を含むデータを一つ以上読み出して、前記第１の複製データとして前記第１の計算機の復旧制御部に送信するステップと、を含み、
前記更新処理は、
前記第２の計算機のデータ管理部が、前記更新命令に基づいて前記所定のデータを更新し、前記第１の複製データの送信指示を前記第２の計算機の復旧制御部に出力するステップと、
前記第２の計算機の復旧制御部が、前記送信指示に基づいて前記第１の複製データを前記第１の計算機の復旧制御部に送信するステップと、を含み、
前記書込処理は、
前記第１の計算機の復旧制御部が、
前記受信した第１の複製データ及び前記受信した第２の複製データを前記作業記憶領域に格納するステップと、
前記データベース及び前記作業記憶領域の中から、同一の前記データの識別情報を含む、前記第１の複製データ及び前記第２の複製データを検索するステップと、
前記検索された第１の複製データに含まれる前記シーケンス番号、及び前記検索された第２の複製データに含まれる前記シーケンス番号を参照して、最新の前記シーケンス番号を含む複製データを選択するステップと、
前記選択された複製データを前記データベースを構成する記憶領域に書き込むステップと、を含むことを特徴とする計算機システム管理方法。
【請求項１０】
請求項９に記載の計算機システム管理方法であって、
前記データベースに格納されるデータは、さらに、削除対象のデータであるか否かを示す削除フラグを含み、
前記更新処理は、前記第２の計算機のデータ管理部が、前記更新命令がデータの削除命令である場合に、前記削除フラグが付与された削除対象のデータを前記第１の複製データとして前記第１の計算機の復旧制御部に送信するステップを含み、
前記書込処理は、前記第１の計算機のデータ管理部が、前記データベースに書き込まれたデータのうち、前記削除フラグが付与されたデータを、前記データベースを構成する記憶領域から削除するステップを含むこと特徴とする計算機システム管理方法。
【請求項１１】
請求項８又は請求項９のいずれか一項に記載の計算機システム管理方法であって、
前記複数の計算機の各々は、前記複数の計算機の各々がマスタとして管理する前記管理範囲、及びスレーブとして管理する前記管理範囲を示す構成情報を保持し、
前記複製処理は、
前記第２の計算機の復旧制御部が、前記複製シーケンス番号を含む前記第１の複製データが送信された後、前記複数の計算機に前記第１の計算機を追加するための合流イベントの前記シーケンス番号である合流シーケンス番号の決定を前記第２の計算機のデータ制御部に指示するステップと、
前記第２の計算機のデータ制御部が、
分散合意アルゴリズムに基づいて、前記複数の計算機の各々の前記データ制御部と通信することによって前記合流シーケンス番号を決定するステップと、
前記決定された合流シーケンス番号、及び、前記合流イベントの内容が対応づけられた前記履歴情報を保持するステップと、
前記決定された合流シーケンス番号を前記第２の計算機の復旧制御部に出力するステップと、を含み、
前記更新処理は、
前記第２の計算機のデータ管理部が、
前記第１の複製データが送信された後に、当該第１の複製データに含まれる前記シーケンス番号と、前記合流シーケンス番号とを比較して、前記合流イベントが発生するか否かを判定するステップと、
前記合流イベントが発生すると判定された場合、前記第１の計算機の復旧制御部に、前記合流シーケンス番号を送信するステップと、を含み、
前記合流イベントでは、前記第１の計算機が前記処理対象の管理範囲のマスタとなるように前記構成情報が更新されることを特徴とする計算機システム管理方法。
【請求項１２】
請求項１１に記載の計算機システム管理方法であって、
前記方法は、
前記第１の計算機が、
前記処理対象の管理範囲をマスタとして管理する計算機、又は、前記処理対象の管理範囲をスレーブとして管理する計算機の少なくともいずれか一方の計算機を前記第２の計算機として選択するステップと、
前記選択された第２の計算機に前記復旧要求を送信するステップと、を含むことを特徴とする計算機システム管理方法。
【請求項１３】
ネットワークを介して複数の計算機が接続され、前記複数の計算機の各々が有する記憶領域から構成されたデータベースを用いて業務を実行する計算機システムに含まれる前記計算機が実行するプログラムであって、
前記複数の計算機の各々は、プロセッサと、前記プロセッサに接続されるメモリと、前記プロセッサと接続され、前記ネットワークを介して他の前記計算機と通信するためのネットワークインタフェースとを有し、
前記データベースに格納されるデータは、前記データの識別情報、前記データの値、及び前記データベースにおけるイベントの実行順番であるシーケンス番号を含み、
前記複数の計算機の各々には、前記データの識別情報に対して分散配置アルゴリズムを適用することによって決定された管理範囲毎に当該データが分散して配置され、
前記複数の計算機の各々は、
配置されたデータを管理するデータ管理部と、
配置されたデータに対する操作の前記シーケンス番号を決定するデータ制御部と、
新たに追加された計算機に、所定の管理範囲に含まれるデータの複製データを送信する復旧制御部と、を有し、
前記プログラムは、
他の前記計算機から復旧要求を受信し、前記計算機の状態を復旧状態に遷移し、前記シーケンス番号に基づいて前記データベースに格納される前記データを一つ以上読み出し、第１の複製データとして前記他の計算機に送信する複製処理を実行する手順と、
前記復旧状態において前記データの更新命令を受信した場合、前記更新命令の前記シーケンス番号を決定し、前記更新命令に基づいて所定のデータを更新し、第２の複製データとして送信する更新処理を実行する手順と、
前記他の計算機における前記第１の複製データ及び前記第２の複製データの書き込み順番を制御する手順と、を前記計算機に実行させることを特徴とするプログラム。
【請求項１４】
請求項１３に記載のプログラムであって、
前記複数の計算機の各々は、前記シーケンス番号、及び前記データベースにおけるイベントの内容が対応づけられた履歴情報を保持し、
前記復旧要求は、処理対象の前記管理範囲を示す情報を含み、
前記複製処理は、
前記計算機の復旧制御部が、
前記復旧要求を受信した場合、前記履歴情報に基づいて、最新のシーケンス番号を複製シーケンス番号として保持する手順と、
前記処理対象の管理範囲の排他ロックを取得する手順と、
前記処理対象の管理範囲に含まれるデータの中から、未送信のデータ、かつ、前記複製シーケンス番号より古い前記シーケンス番号を含むデータを一つ以上読み出して、前記第１の複製データとして前記他の計算機の復旧制御部に送信する手順と、
前記取得された排他ロックを解放する手順と、を含み、
前記更新処理は、
前記計算機のデータ管理部が、
前記処理対象の管理範囲の前記排他ロックを取得する手順と、
前記更新命令に基づいて前記所定のデータを更新し、前記第１の複製データの送信指示を前記計算機の復旧制御部に出力する手順と、
前記取得された排他ロックを解放する手順と、
前記計算機の復旧制御部が、前記送信指示に基づいて前記第１の複製データを前記他の計算機の復旧制御部に送信する手順と、を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の計算機から構成される分散データベースに関する。
【背景技術】
【０００２】
近年、Ｗｅｂを用いたアプリケーションを実行する計算システムにおいてデータ量が爆発的に増大しており、複数のサーバにデータを分散させることによって、データへのアクセス性能を向上させるシステムが様々知られている。例えば、ＲＤＢＭＳ（Ｒｅｌａｔｉｏｎａｌ  ＤａｔａＢａｓｅ  Ｍａｎａｇｅｍｅｎｔ  Ｓｙｓｔｅｍ）では、データを所定の範囲毎に分割し、分割されたデータを複数のサーバに配置することによって、システム全体のアクセス性能を向上させる方法が知られている。【０００３】
また、キャッシュサーバ等に用いられるシステムとして、ＫＶＳ（Ｋｅｙ  Ｖａｌｕｅ  Ｓｔｏｒｅ）等のＮｏＳＱＬ（Ｎｏｔ  ｏｎｌｙ  ＳＱＬ）データベースが知られている。【０００４】
ＫＶＳでは、データに高速にアクセス可能な揮発性の記憶媒体、例えばメモリに、データを格納する構成（メモリストア）、データ格納の永続性に優れる不揮発性の記録媒体、例えば、ＳＳＤ（Ｓｏｌｉｄ  Ｓｔａｔｅ  Ｄｉｓｋ）やＨＤＤ等に、データを格納する構成（ディスクストア）、又は、前述したものを併用する構成等の種々の構成がとられている。【０００５】
メモリストア及びディスクストアには、データ（バリュー）と、データの識別子（キー）とがペアとなったレコードが複数格納される。【０００６】
インメモリ型分散ＫＶＳでは、複数のサーバからクラスタを構成して、そのクラスタに含まれるサーバのメモリ上に構成されるＫＶＳである。これによって、データアクセスの高速化、及びシステムの可用性が実現される。【０００７】
分散ＫＶＳを構成する各サーバは、所定の管理範囲（例えば、キーレンジ）のデータを格納する。また、分散ＫＶＳではデータの信頼性を確保するために、各サーバは他のサーバが管理する管理範囲に含まれるデータの複製データを格納する。【０００８】
各サーバは、管理範囲に含まれるデータのマスタサーバとして処理を実行する。すなわち、所定のキーを含む読み出し要求に対して、そのキーに対応するデータが含まれる管理範囲を管理するサーバが、キーに対応するデータを読み出すこととなる。また、各サーバは、他のサーバが管理する管理範囲の複製データのスレーブサーバとして稼働する。【０００９】
以下の説明では、マスタサーバとして管理するデータをマスタデータと記載し、スレーブサーバとして管理するデータをスレーブデータとも記載する。【００１０】
したがって、分散ＫＶＳでは、一つのサーバに障害が発生した場合であっても、当該サーバのマスタデータの複製データを保持する他のサーバが、新たなマスタサーバとして処理を継続することができる。【００１１】
前述したように分散ＫＶＳを構成するサーバには、管理サーバのような特別なサーバが存在しないため単一点障害が存在しない。すなわち、任意のサーバに障害が発生した場合であっても他のサーバが処理を継続できるため、計算機システムが停止することがない。したがって、分散ＫＶＳは耐障害性も確保される。【００１２】
なお、スレーブサーバの数、すなわち、複製データの格納先となるサーバの数は、計算機システムによって任意に設定することができる。以下、一つの管理範囲に対するスレーブサーバの数を多重度とも記載する。【００１３】
分散ＫＶＳを構成する一つのサーバが停止した場合、分散ＫＶＳの多重度は一つ減少した状態となる。分散ＫＶＳにおける多重度以上のサーバが停止すると、分散ＫＶＳを用いた業務を継続できなくなる。そのため、速やかに分散ＫＶＳの多重度を回復する必要がある。以下の説明では、分散ＫＶＳの多重度を回復させることを「復旧」と記載する。【００１４】
分散ＫＶＳの復旧では、以下のような処理が実行される。【００１５】
第一に、障害が発生したサーバの代わりとなる新規サーバの起動処理が実行される。【００１６】
第二に、障害が発生したサーバが保持するデータを新規サーバに書き込むための複製処理が実行される。具体的には、障害が発生したサーバが保持するデータの複製データを保持するサーバが、新規サーバに当該複製データを送信する。このとき、複製元のサーバ及び複製先のサーバは、同一のデータを保持する必要がある。したがって、複製元のサーバが保持するデータが更新された場合、当該更新されたデータを複製先のサーバに書き込む必要がある。【００１７】
第三に、新規サーバをクラスタに追加するための処理が実行される。【００１８】
分散ＫＶＳを利用するアプリケーションは、銀行口座及びインターネットショッピング等のオンラインシステム上の商取引を行うものが想定される。そのため、アプリケーションが処理を継続できるように、分散ＫＶＳを停止させることなく復旧する必要がある。【００１９】
前述したような、分散ＫＶＳの復旧処理については、特許文献１に記載された技術が知られている。【００２０】
特許文献１には、「（１）稼働中のコピー元計算機のある時点でのメモリの全データのスナップショットを取得し、コピー先計算機へ転送し、該コピー先計算機のメモリへと書込み、（２）（１）の実施中から継続的にコピー元計算機のメモリに対するデータ更新を監視し、検出した更新に関する差分データをコピー先計算機へ転送し、コピー先計算機のメモリへと書込むことを繰り返し、（３）差分データのサイズが１つの送信メッセージに格納できるサイズ以下となると、最後に１回差分データの転送、コピー先計算機のメモリへの書込みを行い、コピー先計算機の処理を該コピー元計算機と同期をとって再開する」ことが記載されている。
【先行技術文献】
【特許文献】
【００２１】
【特許文献１】特開２００９−１９９１９７号公報
【特許文献２】米国特許第５２６１０８５号明細書
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかし、特許文献１に記載の技術では、複製元計算機がスナップショットを取得する必要があり、メモリ使用量が増大する。そのため、分散ＫＶＳに割り当てるメモリが不足し、システム全体の性能が低下する可能性がある。【００２３】
また、スナップショットの送信に伴う通信帯域の使用量（通信量）が増大し、システム全体の通信性能が低下する可能性がある。また、スナップショットを取得した後に、データの更新が発生した場合、複製元計算機は複製先計算機に差分データを送信するため、送信する必要のないデータが送信される問題が発生する。例えば、スナップショットの送信時に、更新処理によって一部のデータが削除されている場合、送信する必要のない差分データを送信するという問題が発生する。【００２４】
また、複製元計算機と複製先計算機との間で同期を取る場合、ユーザプログラム（アプリケーション）を停止させる必要がある。【００２５】
本発明は、メモリ使用量及び通信帯域の使用量を抑え、アプリケーションを停止させることなく分散ＫＶＳを構成するシステムを復旧させることを目的とする。
【課題を解決するための手段】
【００２６】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、ネットワークを介して複数の計算機が接続され、前記複数の計算機の各々が有する記憶領域から構成されたデータベースを用いて業務を実行する計算機システムであって、前記データベースに格納されるデータは、前記データの識別情報、前記データの値、及び前記データベースにおけるイベントの実行順番であるシーケンス番号を含み、前記複数の計算機の各々には、前記データの識別情報に対して分散配置アルゴリズムを適用して決定された管理範囲毎に当該データが分散して配置される。前記複数の計算機の各々は、配置されたデータを管理するデータ管理部と、配置されたデータに対する操作の前記シーケンス番号を決定するデータ制御部と、新たに追加された計算機に、所定の管理範囲に含まれるデータの複製データを送信する復旧制御部と、を有する。前記複数の計算機は、復旧要求を送信する第１の計算機、及び前記復旧要求を受信する第２の計算機を含む。前記第２の計算機は、前記第１の計算機から復旧要求を受信し、前記第２の計算機の状態を復旧状態に遷移させ、前記シーケンス番号に基づいて前記データベースからデータを一つ以上読み出し、第１の複製データとして前記第１の計算機に送信する複製処理を実行する。前記第２の計算機は、前記復旧状態において前記データの更新命令を受信した場合、前記更新命令の前記シーケンス番号を決定し、前記更新命令に基づいて所定のデータを更新し、第２の複製データとして送信する更新処理を実行する。前記第１の計算機又は前記第２の計算機の少なくともいずれか一方が、前記第１の計算機における前記第１の複製データ及び前記第２の複製データの書き込み順番を制御し、前記第１の計算機は、前記書き込み順番に基づいて、前記第１の複製データ及び前記第２の複製データを前記データベースを構成する記憶領域に書き込む書込処理を実行する。
【発明の効果】
【００２７】
本発明によれば、メモリ使用量及び通信帯域の使用量を抑えた計算機システムの復旧が可能となる。また、業務（アプリケーション）を停止させることなくシステムを復旧することができる。【００２８】
前述した以外の課題、構成及び効果は、以下の実施形態の説明によって明らかにされる。
【図面の簡単な説明】
【００２９】
【図１】本発明の概要を説明するシーケンス図である。
【図２】本発明の実施例１における計算機システムの構成を示すブロック図である。
【図３】本発明の実施例１におけるデータストアに格納されるデータの形式を示す説明図である。
【図４】本発明の実施例１における構成情報の一例を示す説明図である。
【図５】本発明の実施例１における分散合意履歴情報の一例を示す説明図である。
【図６】本発明の実施例１における復旧情報の一例を示す説明図である。
【図７】本発明の概要を説明するシーケンス図である。
【図８】本発明の実施例１における複製元のサーバが実行する復旧処理を説明するフローチャートである。
【図９】本発明の実施例１における複製元のサーバが実行するデータ複製処理を説明するフローチャートである。
【図１０】本発明の実施例１における複製元のサーバが実行する更新処理を説明するフローチャートである。
【図１１】本発明の実施例１における復旧時のデータ更新処理を説明するフローチャートである。
【図１２】本発明の実施例１における判定処理を説明するフローチャートである。
【図１３】本発明の実施例１における複製先のサーバが実行する復旧処理を説明するフローチャートである。
【図１４】本発明の実施例１におけるデータストアに格納されるデータの形式を示す説明図である。
【図１５】本発明の実施例２における複製元のサーバが実行するデータ複製処理を説明するフローチャートである。
【図１６】本発明の実施例２における復旧時のデータ更新処理を説明するフローチャートである。
【図１７】本発明の実施例２における複製先のサーバが実行する復旧処理を説明するフローチャートである。
【発明を実施するための形態】
【００３０】
まず、本発明の概要について説明する。
【００３１】
図１は、本発明の概要を説明するシーケンス図である。
【００３２】
図１に示す計算機システムは、三つのサーバ１００と、一つのクライアント装置２００から構成される。三つのサーバ１００はクラスタを構成し、当該サーバ１００が有する記憶領域上に分散データベースが構築される。本実施例では、分散データベースとして分散ＫＶＳを用いるものとする。本実施例の分散ＫＶＳには、キー、バリュー、及びシーケンス番号が対応づけられたデータが複数格納される。以下の説明では、分散ＫＶＳを構成するサーバ１００のクラスタを、単にクラスタと記載する。
【００３３】
ここで、シーケンス番号は、分散ＫＶＳのイベントの実行順番を示す値である。本実施例では、「１」から順に各イベントにシーケンス番号が付与される。分散ＫＶＳのイベントは、データに対する操作（更新処理）、及び計算機システムの構成変更のことを示す。
【００３４】
また、クラスタに含まれる各サーバ１００には、分散配置アルゴリズムに基づいて決定されたキーレンジ毎にデータが配置される。各サーバ１００は、キー、バリュー、及びシーケンス番号が対応づけられたデータをデータ管理情報３００としてデータストア１６０（図２参照）に格納する。
【００３５】
ここで、キーレンジは、各データのキーから算出されたハッシュ値の範囲を表す。なお、分散配置アルゴリズムとしては、Ｃｏｎｓｉｓｔｅｎｔ  Ｈａｓｈｉｎｇ法、Ｒａｎｇｅ法及びＬｉｓｔ法等の種々の方法が用いられる。
【００３６】
各サーバ１００は所定のキーレンジに含まれるデータ（マスタデータ）を管理するマスタサーバとして稼動する。また、各サーバ１００は、他のサーバ１００が管理するキーレンジに含まれるデータの複製データ（スレーブデータ）を保持し、スレーブサーバとして稼動する。
【００３７】
図１では、分散ＫＶＳの復旧処理を示す。以下の説明では、障害発生したサーバ１００がマスタとして管理するキーレンジを対象キーレンジとも記載する。
【００３８】
サーバ１００−１は、現在の対象キーレンジのマスタサーバである。サーバ１００−３は、対象キーレンジの新たなマスタサーバとして追加されるサーバである。
【００３９】
サーバ１００−１は、データ管理情報３００−１に示すような対象キーレンジのマスタデータを格納する。なお、サーバ１００−２にも、同一のスレーブデータが格納される。
【００４０】
サーバ１００−３は、サーバ１００−１に復旧要求を送信する（ステップＳ１０１）。サーバ１００−１は、当該復旧要求を受信すると、復旧状態に遷移する。
【００４１】
このとき、サーバ１００−１は、送信対象のデータの範囲を特定する情報として、マスタデータに含まれるシーケンス番号のうち最も大きいシーケンス番号を記憶する。すなわち、サーバ１００−１は、最新のシーケンス番号を記憶する。その後、サーバ１００−１は、データ複製処理を開始する。以下の説明では、複製元のサーバ１００が、データ複製処理の開始時に記憶するシーケンス番号を複製シーケンス番号とも記載する。
【００４２】
サーバ１００−１は、サーバ１００−３に、キーが「Ａ」のデータの複製データを送信する（ステップＳ１０２）。サーバ１００−３は、受信した複製データをデータストア１６０（図２参照）に格納する。このとき、サーバ１００−３が保持するマスタデータはデータ管理情報３００−２に示すようになる。
【００４３】
サーバ１００−１は、復旧状態時に、クライアント装置２００からキー「Ｃ」のバリューを「ＤＤＤ」に更新するための更新命令を受信した場合（ステップＳ１０３）、分散合意アルゴリズムに基づいて、サーバ１００−２との間で当該更新命令のシーケンス番号を決定する（ステップＳ１０４）。このとき、データ複製処理は一時的に停止される。
【００４４】
以下の説明では、複数のサーバ１００が分散合意アルゴリズムに基づいて、分散ＫＶＳに対する操作の実行順番を決定することを分散合意を行うとも記載する。なお、本実施例では、分散合意アルゴリズムとしてＰａｘｏｓアルゴリズムを用いる。
【００４５】
サーバ１００−１は、サーバ１００−２に更新命令の複製を送信し、当該更新命令について分散合意を行う。図１に示す例では、シーケンス番号が「５」まで決定されているため、受信した更新命令のシーケンス番号は「６」に決定される。これによって、サーバ１００−２も同様のデータ更新処理を実行する。
【００４６】
サーバ１００−１は、更新命令にしたがって、マスタデータを更新する（ステップＳ１０５）。具体的には、サーバ１００−１は、キー「Ｃ」に対応するデータのバリューに「ＤＤＤ」を格納し、シーケンス番号に「６」を格納する。このとき、マスタデータはデータ管理情報３００−３に示すようになる。なお、サーバ１００-２は、分散合意を実行することによって生成された分散状態マシンイベント情報５００（図５参照）に基づいて、同様にデータを更新する。
【００４７】
サーバ１００−１は、サーバ１００−３に、更新されたデータの複製データを送信する（ステップＳ１０６）。サーバ１００−３は、受信した複製データをデータストア１６０（図２参照）に格納する。このとき、サーバ１００−３が保持するマスタデータはデータ管理情報３００−４に示すようになる。
【００４８】
サーバ１００−１は、データの更新処理が完了した後、データ複製処理を再開する。
【００４９】
サーバ１００−１は、サーバ１００−３に、キーが「Ｂ」のデータの複製データを送信する（ステップＳ１０７）。サーバ１００−３は、受信した複製データをデータストア１６０（図２参照）に格納する。このとき、サーバ１００−３が保持するマスタデータはデータ管理情報３００−５に示すようになる。なお、データ管理情報３００−５のデータの順番は、サーバ１００−３におけるデータの書き込み順を示す。したがって、サーバ１００−３は、データ管理情報３００−３と同一形式のマスタデータを保持する。
【００５０】
ここで、複製シーケンス番号以下のシーケンス番号を含むデータが全て送信されたため、サーバ１００−１は、データ複製処理を終了する。
【００５１】
本発明では、複製元のサーバ１００−１がスナップショットを取得することなく、複製先のサーバ１００−３に全てのデータを送信することができる。小さいデータサイズのデータが送信され、また、最新のデータが送信されるため、復旧処理における通信帯域の使用量を抑制できる。また、データの整合性を保つためにシステムを停止させる必要がなく、また、サーバ１００−１とサーバ１００−３との間で同期をとる必要がない。
【００５２】
したがって、復旧処理時におけるネットワーク負荷を低減し、サービスの継続が可能なシステムの復旧が可能となる。
【実施例１】
【００５３】
図２は、本発明の実施例１における計算機システムの構成を示すブロック図である。【００５４】
計算機システムは、複数のサーバ１００、及びクライアント装置２００から構成される。各サーバ１００間又はサーバ１００とクライアント装置２００との間は、ネットワーク２５０を介して互いに接続される。【００５５】
ネットワーク２５０は、ＬＡＮ、ＷＡＮ及びＳＡＮ等の有線及び無線の種々の構成が考えられる。本発明は、サーバ１００及びクライアント装置２００が通信できるものであればどのようなネットワークであってもよい。なお、ネットワーク２５０には、複数のネットワーク装置（図示省略）が含まれる。ネットワーク装置は、例えば、スイッチ及びゲートウェイなどが含まれる。【００５６】
サーバ１００は、プロセッサ１１０、主記憶装置１２０、補助記憶装置１３０、及びネットワークインタフェース１４０を備え、分散ＫＶＳを構成するサーバである。サーバ１００は、クライアント装置２００から送信される要求にしたがって各種処理を実行する。各サーバ１００の構成は同一であるものとする。【００５７】
なお、サーバ１００は、キーボード、マウス、タッチパネル等の入力装置、及び、ディスプレイ等の出力装置を備えていてもよい。【００５８】
プロセッサ１１０は、主記憶装置１２０に格納されるプログラムを実行する。プロセッサ１１０がプログラムを実行することによって、サーバ１００が備える機能を実現することができる。以下、プログラムを主語に処理を説明する場合には、プロセッサ１１０によって、プログラムが実行されていることを示す。【００５９】
主記憶装置１２０は、プロセッサ１１０が実行するプログラム及び当該プログラムの実行に必要な情報を格納する。主記憶装置１２０は、例えば、メモリ等が考えられる。【００６０】
本実施例の主記憶装置１２０上には、データ管理部１５１、分散状態マシン制御部１５２、及び復旧制御部１５３を実現するためのプログラムが格納される。また、主記憶装置１２０上には、必要な情報として、構成情報１７０、及び分散合意履歴情報１８０が格納される。【００６１】
さらに、主記憶装置１２０上には、分散ＫＶＳを構成するデータベースであるデータストア１６０が格納される。本実施例のデータストア１６０には、キー、バリュー、及びシーケンス番号を一組としたデータが格納される。なお、各サーバ１００のデータストア１６０には、マスタデータ及びスレーブデータが格納される。【００６２】
補助記憶装置１３０は、各種情報を格納する。補助記憶装置１３０は、例えば、ＨＤＤ又はＳＳＤ等が考えられる。なお、補助記憶装置１３０上に分散ＫＶＳを構築するディスクストア（図示省略）が構築されてもよい。【００６３】
ネットワークインタフェース１４０は、ネットワーク２５０を介して他の装置と接続するためのインタフェースである。【００６４】
ここで、主記憶装置１２０に格納されるプログラム及び情報について説明する。【００６５】
データ管理部１５１は、サーバ１００が管理するデータに対する各種処理を制御する。データ管理部１５１は、クライアント装置２００から送信された命令を受け付け、当該命令に基づいて、データの読出処理及び書込処理等を制御する。また、データ管理部１５１は、他のサーバ１００へのデータの問い合わせ、クライアント装置２００への処理結果の送信等の処理も実行する。【００６６】
分散状態マシン制御部１５２は、各サーバ１００における分散ＫＶＳのデータの整合性を制御する。具体的には、分散状態マシン制御部１５２は、他のサーバ１００の分散状態マシン制御部１５２と通信することによって、分散ＫＶＳに対して入力されたイベントの実行順番であるシーケンス番号を決定する。【００６７】
ここで、状態マシンとは、「状態」及び「イベント」を用いて対象の振る舞いが表現されるシステムである。状態マシンは、内部に現在の状態を保持し、外部からイベントが入力された場合、予め決定されたルールにしたがって状態を遷移させる。【００６８】
分散状態マシンは、分散システムにおいて、複数のサーバ上に存在する一つ以上の状態マシンに同一の振る舞いを実行させるための仕組みである（例えば、特許文献２参照）。複数の状態マシンが同一の振る舞いを行うためには、各状態マシンに同一イベントを同一の入力順に入力する必要がある。そこで、イベントを入力する順番を決定するために分散合意アルゴリズムが用いられる。【００６９】
ＫＶＳは、キーに対する更新命令等の操作をイベント、当該操作に対するデータの更新を状態の遷移と仮定した場合、キー毎の状態マシンの集合として扱うことができる。したがって、分散ＫＶＳでは、クラスタに含まれる各サーバが同一のデータを保持するための構成として、分散状態マシンを用いることができる。【００７０】
ただし、キー毎に状態マシンを運用する場合、状態マシンの数が膨大となるため現実的ではない。例えば、全てのキーのデータ量が４バイトである場合、必要となる状態マシンの数は４０億個になる。【００７１】
したがって、一定のキーの集合毎に一つの状態マシンを運用する方が望ましい。すなわち、キーレンジに対して一つの状態マシンを存在するようにすればよい。なお、本実施例では、説明の簡単のために、一つのサーバ１００に一つの状態マシンが存在するものとする。この場合、各サーバ１００には一つの分散状態マシン制御部１５２が含まれる。【００７２】
復旧制御部１５３は、復旧処理を制御する。複製先のサーバ１００の復旧制御部１５３は、複製元のサーバ１００に復旧要求を送信し、複製元から送信されたデータをデータストア１６０に格納する。複製元のサーバ１００の復旧制御部１５３は、複製先のサーバ１００にデータを送信する。【００７３】
復旧制御部１５３は、復旧処理に用いる復旧情報１５４を保持する。復旧情報１５４の詳細については、図６を用いて後述する。【００７４】
構成情報１７０は、データの格納先を示す情報を格納する。すなわち、各キーレンジのマスタサーバ及びスレーブサーバを示す情報が格納される。なお、構成情報１７０の詳細については、図４を用いて後述する。分散合意履歴情報１８０は、イベントの合意内容に関する情報を格納する。分散合意履歴情報の詳細については、図５を用いて後述する。【００７５】
次に、クライアント装置２００について説明する。クライアント装置２００は、プロセッサ２１０、主記憶装置２２０、補助記憶装置２３０、及びネットワークインタフェース２４０を備え、サーバ１００に対して各種処理の実行を要求する更新命令を送信する。【００７６】
プロセッサ２１０は、主記憶装置２２０に格納されるプログラムを実行する。プロセッサ２１０がプログラムを実行することによって、クライアント装置２００が備える機能を実現することができる。以下、プログラムを主語に処理を説明する場合には、プロセッサ２１０によって、プログラムが実行されていることを示す。【００７７】
主記憶装置２２０は、プロセッサ２１０が実行するプログラム及び当該プログラムの実行に必要な情報を格納する。主記憶装置２２０は、例えば、メモリ等が考えられる。【００７８】
本実施例の主記憶装置２２０上には、アプリケーション２５１、及び構成情報管理部２５２を実現するためのプログラムが格納される。また、主記憶装置２２０上には、必要な情報として構成情報２６０が格納される。【００７９】
補助記憶装置２３０は、各種情報を格納する。補助記憶装置１３０は、例えば、ＨＤＤ又はＳＳＤ等が考えられる。【００８０】
ネットワークインタフェース２４０は、ネットワーク２５０を介して他の装置と接続するためのインタフェースである。【００８１】
ここで、主記憶装置２２０に格納されるプログラム及び情報について説明する。【００８２】
アプリケーション２５１は、サーバ１００に対して更新命令を送信する。また、アプリケーション２５１は、サーバ１００から送信されるアクセス要求に対する処理の結果を受信する。【００８３】
更新命令は、データに対する操作、すなわちデータに対する更新処理の実行を要求するための命令である。本実施例の更新処理には、データの書き込み、データの上書き、及びデータの削除が含まれる。【００８４】
構成情報管理部２５２は、データの格納先を管理する構成情報２６０を管理する。【００８５】
構成情報２６０は、データの格納先を示す情報を格納する。構成情報２６０は、構成情報１７０と同一のものである。【００８６】
なお、本実施例では、サーバ１００及びクライアント装置２００が備える機能を、ソフトウェアを用いて実現しているが、専用のハードウェアを用いて同一の機能を実現してもよい。【００８７】
図３は、本発明の実施例１におけるデータストア１６０に格納されるデータの形式を示す説明図である。【００８８】
本実施形態では、データストア１６０は、データ管理情報３００を格納する。データ管理情報３００には、キー、バリュー、及びシーケンス番号から構成されるデータが複数含まれる。以下、キー、バリュー、及びシーケンス番号から構成されるデータをキーバリュー型データとも記載する。【００８９】
データ管理情報３００は、Ｋｅｙ３０１、Ｖａｌｕｅ３０２、及びシーケンス番号３０３を含む。【００９０】
Ｋｅｙ３０１は、データを識別するための識別子（キー）を格納する。Ｖａｌｕｅ３０２は、実際のデータ（バリュー）を格納する。シーケンス番号３０３は、Ｋｅｙ３０１に対する更新処理（イベント）の実行順番を示す値を格納する。【００９１】
クライアント装置２００を操作するユーザは、Ｋｅｙ３０１を指定して分散ＫＶＳにデータを保存し、また、Ｋｅｙ３０１を指定して分散ＫＶＳから所望のデータを取得することができる。【００９２】
各サーバ１００は、所定のＫｅｙ３０１の範囲（キーレンジ）毎にキーバリュー型データを管理する。すなわち、キーレンジ毎にキーバリュー型データが各サーバ１００に分散して配置される。サーバ１００は、指定された管理範囲４００のデータのマスタサーバとして処理を実行することとなる。これによって、大量のデータを並列的かつ高速に処理できる。【００９３】
なお、データストア１６０に格納されるデータの形式は、図３に示すものに限定されず、例えば、キーのハッシュ値、バリュー、及びシーケンス番号を対応づけた形式のデータであってもよい。【００９４】
図４は、本発明の実施例１における構成情報１７０の一例を示す説明図である。【００９５】
構成情報１７０は、各サーバ１００の配置されるデータのキーレンジに関する情報を格納する。具体的には、構成情報１７０は、サーバＩＤ４０１及びキーレンジ４０２を含む。【００９６】
サーバＩＤ４０１は、サーバ１００を一意に識別するための識別子を格納する。サーバＩＤ４０１には、例えば、サーバ１００の識別子、ＩＰアドレス、及びＭＡＣアドレス等が格納される。【００９７】
キーレンジ４０２は、キーレンジを特定するためのハッシュ値の範囲を格納する。キーレンジ４０２は、マスタ４０３及びスレーブ４０４を含む。マスタ４０３は、マスタデータのキーレンジを特定するハッシュ値を格納する。スレーブ４０４は、各サーバ１００のスレーブデータのキーレンジを特定するハッシュ値を格納する。【００９８】
なお、スレーブ４０４のカラムは、多重度の数だけ存在する。図４に示す例では、多重度が１の分散ＫＶＳであることを示す。【００９９】
図５は、本発明の実施例１における分散合意履歴情報１８０の一例を示す説明図である。【０１００】
分散合意履歴情報１８０は、複数の分散状態マシンイベント情報５００を含む。分散状態マシンイベント情報５００は、分散ＫＶＳにおけるイベントの情報を格納する。具体的には、分散状態マシンイベント情報５００は、シーケンス番号５０１、提案内容５０２を含む。【０１０１】
シーケンス番号５０１は、イベントの実行順番を示す値を格納する。提案内容５０２は、イベントの具体的な内容を格納する。図５に示す提案内容５０２には、Ｋｅｙ５０４、Ｖａｌｕｅ５０５を含むＰｕｔ命令５０３が格納される。【０１０２】
本実施例では、キーレンジ毎に分散合意履歴情報１８０が存在するものとする。【０１０３】
図６は、本発明の実施例１における復旧情報１５４の一例を示す説明図である。【０１０４】
復旧情報１５４は、複製シーケンス番号６０１、対象キーレンジ６０２、宛先情報６０３、及び合流シーケンス番号６０４を含む。【０１０５】
複製シーケンス番号６０１は、複製シーケンス番号を格納する。対象キーレンジ６０２は、対象キーレンジを特定するハッシュ値を格納する。宛先情報６０３は、複製先のサーバ１００を特定するための情報を格納する。宛先情報６０３には、例えば、サーバ１００のＩＰアドレス、及びポート番号等が格納される。【０１０６】
合流シーケンス番号６０４は、クラスタに新たなサーバ１００を追加するためのイベントの実行順番を示すシーケンス番号を格納する。以下の説明では、クラスタに新たなサーバ１００を追加するためのイベントを、メンバ合流イベントとも記載する。【０１０７】
図７は、本発明の概要を説明するシーケンス図である。図７は、図１のステップＳ１０７の後に実行される処理を示す。【０１０８】
サーバ１００−１は、サーバ１００−３に、複製対象の全てのデータを送信した後（ステップＳ１０７）、サーバ１００−２との間でメンバ合流イベントの分散合意を行う（ステップＳ１０８）。これによって、メンバ合流イベントのシーケンス番号が決定される。以下の説明では、メンバ合流イベントのシーケンス番号を合流シーケンス番号とも記載する。【０１０９】
サーバ１００−１は、復旧情報１５４に、決定された合流シーケンス番号を格納する。メンバ合流イベントが実行されるまでは、サーバ１００−１が対象キーレンジのマスタサーバとして処理を行う。すなわち、合流シーケンス番号より小さいシーケンス番号が付与された更新命令は、サーバ１００−１によって処理される。【０１１０】
図７に示す例では、合流シーケンス番号は「１５」に決定されたものとする。【０１１１】
サーバ１００−１及びサーバ１００−２は、メンバ合流イベントの分散合意が行われた後、当該メンバ合流イベントの実行を開始する。しかし、この時点では、シーケンス番号が「１５」でないため、一定期間待ち状態となる。一定期間経過した後、シーケンス番号が合流シーケンス番号より小さい場合、サーバ１００−１及びサーバ１００−２は、ＮＯＯＰ命令の分散合意を行って、シーケンス番号の値を加算する。【０１１２】
クライアント装置２００は、キー「Ａ」のデータを削除するための更新命令をサーバ１００−１に送信する（ステップＳ１０９）。この時点では、サーバ１００−３はクラスタに追加されていないため、更新命令はサーバ１００−１に送信される。【０１１３】
サーバ１００−１は、更新命令を受信すると、サーバ１００−２との間で分散合意を行う（ステップＳ１１０）。図７に示す例では、受信した更新命令のシーケンス番号は「７」に決定される。【０１１４】
サーバ１００−１は、更新命令にしたがって、マスタデータを更新する（ステップＳ１１１）。具体的には、サーバ１００−１は、キー「Ａ」のデータを削除する。このとき、マスタデータはデータ管理情報３００−６に示すようになる。なお、サーバ１００−２は、分散合意を実行することによって生成された分散状態マシンイベント情報５００に基づいて、同様にデータを更新する。【０１１５】
サーバ１００−１は、サーバ１００−３に、データの削除を指示するデータを送信する（ステップＳ１１２）。サーバ１００−３は、データを削除する。このとき、サーバ１００−３が保持するマスタデータはデータ管理情報３００−７に示すようになる。【０１１６】
サーバ１００−１は、シーケンス番号が「１５」になるまでステップＳ１１０からステップＳ１１２までの処理を実行する。【０１１７】
所定のイベントのシーケンス番号が「１４」である場合、次にメンバ合流イベントが発生する。ここで、サーバ１００−１は、サーバ１００−３に、合流シーケンス番号を含む復旧完了データを送信し（ステップＳ１１３）、その後、復旧状態を解除する。【０１１８】
また、サーバ１００−１及びサーバ１００−２は、メンバ合流イベントを実行する（ステップＳ１１４）。【０１１９】
なお、この時点ではサーバ１００-３が新たなマスタサーバとなるように構成情報１７０が更新されている。具体的には、サーバ１００−１は、構成情報１７０にサーバ１００−３のエントリを追加し、サーバ１００−３をマスタサーバとして設定する。サーバ１００−２及びサーバ１００−３も同様の処理を実行する。さらに、サーバ１００−１は、サーバ１００−３及びクライアント装置２００に更新された構成情報１７０を送信する。【０１２０】
当該処理によって、クラスタにサーバ１００−３が追加され、また、サーバ１００−３が対象キーレンジに含まれるデータに対する更新命令を処理する。【０１２１】
その後、クライアント装置２００は、キーが「Ｄ」、バリューが「ＥＥＥ」であるデータを追加するための更新命令をサーバ１００−３に送信する（ステップＳ１１５）。【０１２２】
サーバ１００−３は、サーバ１００−１及びサーバ１００−２との間で分散合意を行い（ステップＳ１１６）、受信した更新命令のシーケンス番号を「１６」に決定する。【０１２３】
サーバ１００−３は、更新命令にしたがって、マスタデータを更新する（ステップＳ１１７）。具体的には、サーバ１００−３は、キーが「Ｄ」、バリューが「ＥＥＥ」、シーケンス番号が「１６」であるデータを格納する。サーバ１００−１及びサーバ１００−２は、それぞれ、分散合意の実行時に送信された分散状態マシンイベント情報５００に基づいて、同様にデータを更新する。このとき、マスタデータはデータ管理情報３００−８に示すようになる。【０１２４】
図８は、本発明の実施例１における複製元のサーバ１００が実行する復旧処理を説明するフローチャートである。【０１２５】
サーバ１００は、他のサーバ１００から復旧要求を受信する（ステップＳ２０１）。具体的には、復旧制御部１５３が、復旧要求を受信する。復旧要求には、対象キーレンジを特定するためのハッシュ値、及び複製先のサーバ１００の宛先情報が含まれる。【０１２６】
サーバ１００は、受信した復旧要求に基づいて、復旧情報１５４を生成する（ステップＳ２０２）。具体的には、以下のような処理が実行される。【０１２７】
復旧制御部１５３は、復旧要求に含まれる対象キーレンジのハッシュ値、及び宛先情報を取得する。復旧制御部１５３は、分散状態マシン制御部１５２に、複製シーケンス番号の取得要求を出力する。なお、取得要求には、対象キーレンジのハッシュ値が含まれる。【０１２８】
分散状態マシン制御部１５２は、取得要求に含まれる対象キーレンジのハッシュ値に基づいて、対象キーレンジに対応する分散状態マシンイベント情報５００を検索する。さらに、分散状態マシン制御部１５２は、検索された分散状態マシンイベント情報５００のシーケンス番号５０１を参照し、最も大きいシーケンス番号を取得する。すなわち、最新のシーケンス番号が取得される。【０１２９】
分散状態マシン制御部１５２は、取得されたシーケンス番号を複製シーケンス番号として復旧制御部１５３に出力する。【０１３０】
復旧制御部１５３は、キーレンジのハッシュ値、宛先情報、及び複製シーケンス番号に基づいて、復旧情報１５４を生成する。その後、復旧制御部１５３は、復旧状態に遷移する。【０１３１】
なお、この時点では、復旧情報１５４には合流シーケンス番号６０４が含まれていない。【０１３２】
以上が、ステップＳ２０２の処理の説明である。【０１３３】
次に、サーバ１００は、データ複製処理を実行する（ステップＳ２０３）。データ複製処理の詳細については、図９を用いて後述する。【０１３４】
複製対象の全てのデータが送信されたと判定された場合、サーバ１００は、分散合意アルゴリズムに基づいて、メンバ合流イベントのシーケンス番号、すなわち、合流シーケンス番号を決定する（ステップＳ２０４）。具体的には、復旧制御部１５３が、分散状態マシン制御部１５２に、メンバ合流イベントの分散合意を指示する。具体的な処理については、図９を用いて後述する。【０１３５】
次に、サーバ１００は、決定された合流シーケンス番号を復旧情報１５４に格納し（ステップＳ２０５）、処理を終了する。【０１３６】
なお、合流シーケンス番号と複製シーケンス番号との間の差が大きい場合、頻繁に更新が行われないシステムでは、合流シーケンス番号が付与されたイベントの発生まで、複製先のサーバ１００をクラスタに追加することができない。この場合、分散状態マシン制御部１５２は、ステップＳ２０５の処理が実行された後、一定期間、メンバ合流イベントの発生を待つ。一定期間経過後のシーケンス番号が合流シーケンス番号より小さい場合、分散状態マシン制御部１５２は、所定の回数、ＮＯＯＰ命令の分散合意を行う。【０１３７】
図９は、本発明の実施例１における複製元のサーバ１００が実行するデータ複製処理を説明するフローチャートである。データ複製処理は、復旧制御部１５３が主体となって実行される。【０１３８】
復旧制御部１５３は、対象キーレンジに含まれるデータの排他ロックを取得する（ステップＳ３０１）。これによって、対象キーレンジに対するデータ更新処理が実行されない。そのため、データ複製処理、及びデータ更新処理が同時に発生することを避けることができる。【０１３９】
なお、データ更新処理によって、対象キーレンジの排他ロックが取得されている場合、復旧制御部１５３は、排他ロックが解放されるまで待ち続ける。【０１４０】
復旧制御部１５３は、対象キーレンジに含まれるデータの中から複製対象のデータを検索する（ステップＳ３０２）。【０１４１】
具体的には、復旧制御部１５３は、データストア１６０のデータ管理情報３００、及び復旧情報１５４を参照し、対象キーレンジに含まれるデータの中から、複製シーケンス番号より古いシーケンス番号を含み、かつ、未送信のデータを検索する。本実施例では、復旧制御部１５３は、送信済みのデータのシーケンス番号より大きく、かつ、複製シーケンス番号以下のシーケンス番号を含むデータを検索する。【０１４２】
復旧制御部１５３は、検索結果に基づいて、複製対象のデータが存在するか否かを判定する（ステップＳ３０３）。すなわち、複製対象の全てのデータを送信したか否かが判定される。【０１４３】
複製対象のデータが存在すると判定された場合、復旧制御部１５３は、検索されたデータを読み出し、読み出されたデータを複製データとして複製先のサーバ１００に送信する（ステップＳ３０４）。具体的には、以下のような処理が実行される。【０１４４】
復旧制御部１５３は、検索されたデータの中から送信するデータを選択する。選択方法としては、シーケンス番号が小さい順にデータを選択する方法、又は、キーの辞書の登録順にデータを選択する方法が考えられる。また、選択されるデータの数は、一つ、又は、二つ以上のいずれであってもよい。本実施例では、選択されるデータの数は一つであるものとする。【０１４５】
なお、データの選択方法、及び選択されるデータの数に関する情報は、復旧制御部１５３に予め設定されていてもよいし、復旧要求に含まれてもよい。【０１４６】
復旧制御部１５３は、選択されたデータをデータストア１６０から読み出し、複製先のサーバ１００の復旧制御部１５３に読み出されたデータを複製データとして送信する。【０１４７】
以上がステップＳ３０４の処理の説明である。【０１４８】
次に、復旧制御部１５３は、対象キーレンジの排他ロックを解放し（ステップＳ３０５）、ステップＳ３０１に戻る。【０１４９】
ステップＳ３０３において、複製対象のデータが存在しないと判定された場合、復旧制御部１５３は、対象キーレンジの排他ロックを解放する（ステップＳ３０６）。その後、復旧制御部１５３は、分散状態マシン制御部１５２に、メンバ合流イベントの分散合意の実行を指示し（ステップＳ３０７）、処理を終了する。このとき、分散状態マシン制御部１５２は、以下のような処理を実行する。【０１５０】
分散状態マシン制御部１５２は、当該指示を受け付けると、分散合意アルゴリズムにしたがって、他のサーバ１００の分散状態マシン制御部１５２と通信を行い、メンバ合流イベントの処理内容を配信し、合流シーケンス番号を決定する。【０１５１】
各サーバ１００の分散状態マシン制御部１５２は、メンバ合流イベントの提案内容５０２を含む分散状態マシンイベント情報５００を分散合意履歴情報１８０に格納する。【０１５２】
提案内容５０２には、メンバ合流イベントの処理内容として、構成情報１７０を更新するための情報、及び合流シーケンス番号を算出するための情報が含まれる。構成情報１７０を更新するための情報には、対象キーレンジ６０２及び宛先情報６０３に対応する情報が含まれる。また、合流シーケンス番号を算出するための情報には、条件式が含まれる。【０１５３】
例えば、メンバ合流イベントに対応する分散状態マシンイベント情報５００に付与されるシーケンス番号５０１に所定の値を加算し、算出された値を合流シーケンス番号として算出する条件式が考えられる。また、当該シーケンス番号５０１に所定の値を乗算し、算出された値を合流シーケンス番号として算出する条件式が考えられる。なお、本発明は、合流シーケンス番号を算出する条件式に限定されない。【０１５４】
各サーバ１００の分散状態マシン制御部１５２は、メンバ合流イベントの分散合意が行われた後、メンバ合流イベントの提案内容５０２に基づいて、合流シーケンス番号を算出する。また、各サーバ１００の分散状態マシン制御部１５２は、復旧制御部１５３に、算出された合流シーケンス番号を出力する。復旧制御部１５３は、入力された合流シーケンス番号を保持する。【０１５５】
各サーバ１００の分散状態マシン制御部１５２は、一定期間待ち状態となる。各サーバ１００の分散状態マシン制御部１５２は、シーケンス番号が合流シーケンス番号に一致した場合、待ち状態であったメンバ合流イベントを実行する。このとき、分散状態マシン制御部１５２は、データ管理部１５１に、構成情報１７０の更新を指示する。当該指示には、対象キーレンジ６０２及び宛先情報６０３に対応する情報が含まれる。【０１５６】
データ管理部１５１は、構成情報１７０を参照して、複製元のサーバ１００のエントリを検索する。【０１５７】
データ管理部１５１は、検索されたエントリのマスタ４０３から対象キーレンジ６０２が除かれるようにハッシュ値を更新する。また、データ管理部１５１は、検索されたエントリのスレーブ４０４に対象キーレンジ６０２が含まれるようにハッシュ値を更新する。【０１５８】
また、データ管理部１５１は、構成情報１７０に新たなエントリを追加し、宛先情報６０３に基づいて、サーバＩＤ４０１に複製先のサーバ１００の識別子を格納する。また、データ管理部１５１は、当該エントリのマスタ４０３に対象キーレンジ６０２のハッシュ値を格納する。さらに、データ管理部１５１は、当該エントリのスレーブ４０４に所定のハッシュ値を格納する。【０１５９】
スレーブ４０４のハッシュ値の決定方法は様々考えられる。例えば、少なくとも一つのサーバ１００が、障害が発生したサーバのマスタ４０３、スレーブ４０４のハッシュ値を履歴情報として保持しておき、当該履歴情報に基づいてスレーブ４０４のハッシュ値を決定する方法が考えられる。また、他のサーバ１００のエントリのスレーブ４０４を参照し、分散ＫＶＳにおける多重度を満たすようにスレーブ４０４のハッシュ値を決定する方法が考えられる。なお、本発明は、スレーブ４０４に格納するハッシュ値の決定方法に限定されない。【０１６０】
以上が、ステップＳ３０７の処理の説明である。【０１６１】
図１０は、本発明の実施例１における複製元のサーバ１００が実行するデータ更新処理を説明するフローチャートである。データ更新処理は、データ管理部１５１が主体となって実行される。【０１６２】
データ管理部１５１は、クライアント装置２００から更新命令を受信する（ステップＳ４０１）。【０１６３】
データ管理部１５１は、更新命令のシーケンス番号を決定する（ステップＳ４０２）。具体的には、以下のような処理が実行される。【０１６４】
データ管理部１５１は、分散状態マシン制御部１５２に、更新命令の処理内容とともに、当該更新命令の分散合意を行うように依頼する。【０１６５】
分散状態マシン制御部１５２は、分散合意アルゴリズムにしたがって、他のサーバ１００の分散状態マシン制御部１５２と通信を行い、更新命令の複製を配信し、当該更新命令のシーケンス番号を決定する。分散状態マシン制御部１５２は、データ管理部１５１に、決定されたシーケンス番号を出力する。【０１６６】
以上が、ステップＳ４０２の処理の説明である。【０１６７】
次に、データ管理部１５１は、復旧状態であるか否かを判定する（ステップＳ４０３）。具体的には、以下のような処理が実行される。【０１６８】
データ管理部１５１は、復旧制御部１５３に復旧情報１５４の取得要求を送信する。【０１６９】
復旧情報１５４が存在する場合、復旧制御部１５３は、当該復旧情報１５４をデータ管理部１５１に出力する。復旧情報１５４が存在しない場合、復旧制御部１５３は、エラー通知を出力する。【０１７０】
復旧情報１５４を取得した場合、データ管理部１５１は、復旧状態であると判定する。一方、エラー通知を取得した場合、データ管理部１５１は、復旧状態でないと判定する。【０１７１】
以上が、ステップＳ４０３の処理の説明である。【０１７２】
復旧状態でないと判定された場合、データ管理部１５１は、ステップＳ４０８に進む。【０１７３】
復旧状態であると判定された場合、データ管理部１５１は、更新命令における処理対象のデータが対象キーレンジに含まれるか否かを判定する（ステップＳ４０４）。【０１７４】
具体的には、データ管理部１５１は、更新命令に含まれるキーのハッシュ値を算出する。データ管理部１５１は、算出されたキーのハッシュ値、及び取得された復旧情報１５４に含まれる対象キーレンジ６０２に基づいて、算出されたキーのハッシュ値が対象キーレンジに含まれるか否かを判定する。算出されたキーのハッシュ値が対象キーレンジに含まれていると判定された場合、操作対象のデータが対象キーレンジに含まれると判定する。【０１７５】
更新対象のデータが対象キーレンジに含まれないと判定された場合、データ管理部１５１は、ステップＳ４０８に進む。【０１７６】
更新対象のデータが対象キーレンジに含まれると判定された場合、データ管理部１５１は、復旧状態におけるデータ更新処理を実行し（ステップＳ４０５）、その後、判定処理を実行する（ステップＳ４０６）。ここで、判定処理は、復旧処理が完了したか否かを判定するための処理である。【０１７７】
復旧状態におけるデータ更新処理の詳細については、図１１を用いて後述する。判定処理の詳細については、図１２を用いて後述する。【０１７８】
データ管理部１５１は、処理結果をクライアント装置２００に通知し（ステップＳ４０７）、処理を終了する。なお、他のサーバ１００（スレーブサーバ）も同様にステップＳ４０３からステップＳ４０８の処理を実行する。当該処理は、マスタサーバの処理とは独立した処理である。【０１７９】
ステップＳ４０８では、データ管理部１５１は、通常のデータ更新処理を実行し、ステップＳ４０７に進む。【０１８０】
通常のデータ更新処理では、データを追加する場合、データ管理部１５１は、排他ロックを取得し、データ管理情報３００にキー、バリュー、及びシーケンス番号を対応づけたデータを格納する。なお、通常のデータ更新処理は、公知の技術であるため詳細な説明を省略する。【０１８１】
図１１は、本発明の実施例１における復旧状態におけるデータ更新処理を説明するフローチャートである。復旧状態におけるデータ更新処理は、データ管理部１５１が主体となって実行される。【０１８２】
データ管理部１５１は、対象キーレンジに含まれるデータの排他ロックを取得する（ステップＳ５０１）。これによって、対象キーレンジに対するデータ複製処理が実行されない。そのため、データ複製処理、及びデータ更新処理が同時に発生することを避けることができる。【０１８３】
なお、データ複製処理によって、対象キーレンジの排他ロックが取得されている場合、データ管理部１５１は、排他ロックが解放されるまで待ち続ける。【０１８４】
データ管理部１５１は、更新命令に基づいて、データを更新する（ステップＳ５０２）。例えば、更新命令がデータの上書き処理に対応する命令である場合、データ管理部１５１は、更新対象のデータを検索し、検索されたデータのバリュー、及びシーケンス番号に所定の値を上書きする。なお、データの更新方法は公知の技術であるため詳細な説明を省略する。【０１８５】
データ管理部１５１は、復旧制御部１５３に、複製データの送信を指示する（ステップＳ５０３）。当該指示には、更新されたデータが含まれる。復旧制御部１５３は、当該指示を受け付けると、復旧情報１５４を参照し、複製先のサーバ１００の復旧制御部１５３に更新されたデータを複製データとして送信する。【０１８６】
なお、データ管理部１５１が、複製先のサーバ１００の復旧制御部１５３に、更新されたデータを複製データとして送信してもよい。この場合、データ管理部１５１は、復旧制御部１５３から宛先情報を取得する。【０１８７】
データ管理部１５１は、排他ロックを解放し（ステップＳ５０４）、処理を終了する。このとき、データ管理部１５１は、復旧制御部１５３に判定処理の実行を指示する。【０１８８】
なお、更新命令に含まれるコマンドによっては、データが更新されない場合も存在する。この場合、データ管理部１５１は、ステップＳ５０２及びステップＳ５０３の処理を省略してもよい。【０１８９】
ここで、排他ロック制御について説明する。【０１９０】
データ複製処理、及び、復旧状態におけるデータ更新処理では、それぞれ、排他ロックが取得される。これは、並列に実行される二つの処理によって送信される複製データの順番を制御するためである。すなわち、複製元のサーバ１００は、排他ロックを取得することによって、二つの処理が直列的に実行されるように制御する。これによって、分散ＫＶＳにおけるデータの整合性を保つことができる。【０１９１】
一方、排他ロックが取得されない場合、通信の遅延等によって、複製元のサーバ１００が、データの不整合が発生する順番で複製データを受信する可能性がある。例えば、データの上書き、データの削除の順に処理が実行された場合、通信の遅延によって、複製先のサーバ１００がデータの削除、データの上書きの順に複製データを受信する可能性がある。この場合、データの不整合が生じる。【０１９２】
そのため、実施例１では、複製元のサーバ１００が、前述したようなデータの不整合を回避するために、排他ロックを用いて二つの処理を直列的に実行することによって、複製データの送信順番を制御する。【０１９３】
なお、本実施例では、排他ロックを用いて二つの処理の実行順番を制御したが、本発明はこれに限定されない。キューイング等、二つの処理を直列的に実行する方法であればどのような方法を用いてもよい。【０１９４】
図１２は、本発明の実施例１における判定処理を説明するフローチャートである。判定処理は、復旧制御部１５３が主体になって実行される。【０１９５】
復旧制御部１５３は、データ管理部１５１から判定処理の実行指示を受け付けると処理を開始する。まず、復旧制御部１５３は、復旧情報１５４に合流シーケンス番号が格納されているか否かを判定する（ステップＳ６０１）。【０１９６】
復旧情報１５４に合流シーケンス番号が格納されていないと判定された場合、復旧制御部１５３は、処理を終了する。【０１９７】
復旧情報１５４に合流シーケンス番号が格納されていると判定された場合、復旧制御部１５３は、メンバ合流イベントが発生するか否かを判定する（ステップＳ６０２）。具体的には、以下のような処理が実行される。【０１９８】
復旧制御部１５３は、復旧情報１５４から合流シーケンス番号６０４を取得する。復旧制御部１５３は、合流シーケンス番号６０４から、判定処理の前に実行されたデータ更新処理（ステップＳ４０５）における更新命令に付与されたシーケンス番号５０１を減算する。なお、当該シーケンス番号５０１は、復旧状態におけるデータ更新処理において実行された更新命令に対応する提案内容５０２を含む分散状態マシンイベント情報５００に付与されたものである。【０１９９】
復旧制御部１５３は、算出された値が「１」であるか否かを判定する。算出された値が「１」である場合、復旧制御部１５３はメンバ合流イベントが発生すると判定する。【０２００】
以上が、ステップＳ６０２の処理の説明である。【０２０１】
メンバ合流イベントが発生しないと判定された場合、復旧制御部１５３は、処理を終了する。【０２０２】
メンバ合流イベントが発生すると判定された場合、復旧制御部１５３は、複製先のサーバ１００の復旧制御部１５３に復旧完了データを送信する（ステップＳ６０３）。復旧完了データには、合流シーケンス番号が含まれる。【０２０３】
復旧制御部１５３は、復旧情報１５４を初期化し（ステップＳ６０４）、処理を終了する。具体的には、復旧制御部１５３は、復旧情報１５４に含まれる全ての情報を削除する。これによって、復旧状態が解除される。【０２０４】
図１３は、本発明の実施例１における複製先のサーバ１００が実行する復旧処理を説明するフローチャートである。【０２０５】
サーバ１００は、復旧処理に必要な情報を設定し（ステップＳ７０１）、設定された情報に基づいてサーバ１００に復旧要求を送信する（ステップＳ７０２）。具体的には、復旧制御部１５３が、ユーザから設定された情報に基づいて、サーバ１００に復旧要求を送信する。【０２０６】
本実施例では、複製元のサーバ１００及び複製先のサーバを特定するための情報が設定される。【０２０７】
例えば、ユーザは複製先のサーバ１００の宛先情報及び対象キーレンジを設定する。この場合、設定された宛先情報に基づいて、複製元のサーバ１００に復旧要求が送信される。【０２０８】
また、ユーザは対象キーレンジを設定する。この場合、複製先のサーバ１００は、他のサーバ１００から構成情報１７０を取得し、取得された構成情報１７０を参照し、対象キーレンジのマスタサーバを検索する。複製先のサーバ１００は、検索されたマスタサーバに対応するサーバ１００に、復旧要求を送信する。【０２０９】
サーバ１００は、他のサーバ１００からデータを受信すると（ステップＳ７０３）、受信したデータが複製データであるか否かを判定する（ステップＳ７０４）。具体的には、復旧制御部１５３が、受信したデータが複製データであるか否かを判定する。【０２１０】
受信したデータが複製データであると判定された場合、サーバ１００は、受信したデータをデータストア１６０に書き込み（ステップＳ７０５）、ステップＳ７０３に戻る。具体的には、復旧制御部１５３がデータストア１６０に受信したデータを書き込む。なお、復旧制御部１５３はデータ管理部１５１にデータストア１６０へのデータの書き込みを依頼してもよい。【０２１１】
ステップＳ７０４において、受信したデータが複製データでない、すなわち、復旧完了データであると判定された場合、サーバ１００は、合流シーケンス番号を登録し（ステップＳ７０６）、処理を終了する。具体的には、以下のような処理が実行される。【０２１２】
復旧制御部１５３が、復旧完了データに含まれる合流シーケンス番号を取得し、分散状態マシン制御部１５２に、取得された合流シーケンス番号を含む登録要求を出力する。【０２１３】
分散状態マシン制御部１５２は、一時的に合流シーケンス番号を保持する。なお、分散状態マシン制御部１５２は、メンバ合流イベントが発生した後、当該合流シーケンス番号を削除してもよい。【０２１４】
なお、サーバ１００は、複製元のサーバ１００から更新された構成情報１７０を取得する。本発明は、更新された構成情報１７０の取得方法に限定されない、例えば、以下のような取得方法が考えられる。一つの取得方法としては、複製元のサーバ１００が、複製先のサーバ１００に、一つの複製データとして更新された構成情報１７０を送信する。他の取得方法としては、複製元のサーバ１００が、更新された構成情報１７０が含まれる復旧完了データを送信する。【０２１５】
本実施例では、復旧要求には対象キーレンジのハッシュ値が含まれるが、必ずしも必要ではない。例えば、クラスタに含まれる全てのサーバ１００が同一のデータを保持する場合、ステップＳ７０１において、ユーザは対象キーレンジを指定する必要はない。この場合、サーバ１００に格納される全データが複製処理の対象となる。【０２１６】
実施例１によれば、データ更新処理及びデータ複製処理が並列に実行されている場合において、複製元のサーバ及び複製先のサーバのデータの整合性を保った復旧が可能となる。【０２１７】
また、復旧処理においてスナップショットを取得する必要がないため複製元のサーバのメモリ使用量を低減することができる。また、復旧処理では、一つ又は複数の複製データが送信されることによってネットワーク通信量を低減することができる。また、更新されたデータが優先的に送信されるため、同一キーのデータを複数回送信する必要がない。そのため、復旧処理におけるネットワーク通信量を低減することができる。【０２１８】
また、クライアント装置２００のアプリケーション２５１を停止させることなく復旧することができる。【０２１９】
（実施例１の変形例）
ステップＳ７０１では、データ複製処理を実行するサーバ１００を選択することもできる。具体的には、以下のような処理が実行される。【０２２０】
複製先のサーバ１００は、ユーザから対象キーレンジを受け付けると、クラスタに含まれるサーバ１００から構成情報１７０を取得する。【０２２１】
複製先のサーバ１００は、構成情報１７０を参照し、対象キーレンジのマスタサーバ及びスレーブサーバの情報をユーザに対して表示する。ユーザは、表示された情報に基づいて、データ複製処理を実行するサーバ１００を選択する。【０２２２】
マスタサーバがデータ複製処理を実行するサーバ１００として選択された場合、実施例１と同一の処理となる。【０２２３】
スレーブサーバがデータ複製処理を実行するサーバ１００として選択された場合、復旧制御部１５３は、スレーブサーバの識別情報及びデータ複製処理の実行指示を復旧要求に含める。さらに、復旧制御部１５３は、当該復旧要求をスレーブサーバに送信する。【０２２４】
スレーブサーバは、図８から図１２に示す処理を実行する。【０２２５】
これによって、マスタサーバの処理負荷を低減することができる。
【実施例２】
【０２２６】
実施例１では、複製元のサーバ１００は、データ複製処理及びデータ更新処理の開始時に排他ロックを取得することによって、複製先のサーバ１００の複製データの受信順番を制御していた。これによって、前述したようなデータの不整合が回避される。【０２２７】
実施例２では、排他ロック制御を用いる代わりに、複製先のサーバ１００が二つの処理の実行順番を考慮して複製データをデータストア１６０に書き込む。【０２２８】
以下、実施例１との差異を中心に実施例２について説明する。【０２２９】
実施例２のシステム構成では、サーバ１００が一時的にデータを蓄積するためのバッファを有する。その他の構成は実施例１と同一であるため説明を省略する。また、実施例２では、データストア１６０に格納される情報が異なる。その他の情報は実施例１と同一である。【０２３０】
図１４は、本発明の実施例１におけるデータストア１６０に格納されるデータの形式を示す説明図である。【０２３１】
実施例２のデータ管理情報３００は、新たに削除フラグ３０４を含む。【０２３２】
削除フラグ３０４は、データの削除を示す更新処理であるか否かを示す情報を格納する。本実施例では、データの削除を示す更新処理の場合「Ｔｒｕｅ」が格納され、データの削除以外の更新処理の場合「Ｆａｌｓｅ」が格納される。【０２３３】
図１５は、本発明の実施例２における複製元のサーバ１００が実行するデータ複製処理を説明するフローチャートである。【０２３４】
実施例２では、ステップＳ３０１、ステップＳ３０５及びステップＳ３０６の処理が省略される。その他の処理は実施例１と同一の処理である。【０２３５】
図１６は、本発明の実施例２における復旧状態におけるデータ更新処理を説明するフローチャートである。【０２３６】
実施例２では、ステップＳ５０１及びステップＳ５０４の処理が省略される。【０２３７】
更新命令がデータの削除を指示する命令の場合、ステップＳ５０２及びステップＳ５０３の処理が異なる。データの追加、及びデータの上書きを指示する更新命令の場合の処理は実施例１の処理と同一である。【０２３８】
ステップＳ５０２では、更新命令がデータの削除を指示する命令であった場合、データ管理部１５１は、更新命令に基づいて、削除対象のデータを検索する。データ管理部１５１は、検索されたデータの削除フラグ３０４を「Ｔｒｕｅ」に変更する。【０２３９】
ステップＳ５０３では、データ管理部１５１は、復旧制御部１５３に、複製先のサーバ１００への複製データの送信を指示する。当該送信には、削除フラグ３０４が「Ｔｒｕｅ」である複製データが含まれる。その後、データ管理部１５１は、削除フラグ３０４が「Ｔｒｕｅ」のデータを削除する。【０２４０】
復旧制御部１５３は、当該指示を受け付けると、復旧情報１５４を参照し、複製先のサーバ１００の復旧制御部１５３に複製データを送信する。【０２４１】
図１７は、本発明の実施例２における複製先のサーバ１００が実行する復旧処理を説明するフローチャートである。【０２４２】
ステップＳ７０１からステップＳ７０４の処理は、実施例１と同一の処理である。【０２４３】
ステップＳ７０４において、受信したデータが複製データであると判定された場合、サーバ１００は、受信した複製データをバッファに一時的に蓄積する（ステップＳ８０１）。具体的には、復旧制御部１５３が、バッファに受信した複製データを格納する。【０２４４】
サーバ１００は、バッファに蓄積されたデータをデータストア１６０に書き込むか否かを判定する（ステップＳ８０２）。【０２４５】
例えば、バッファに蓄積されたデータの容量が所定のしきい値以上である場合に、復旧制御部１５３は、当該データをデータストア１６０に書き込む。また、復旧制御部１５３は、タイマを備え、一定時間経過した場合に、当該データをデータストア１６０に書き込む。【０２４６】
バッファに蓄積された複製データをデータストア１６０に書き込まれないと判定された場合、サーバ１００は、ステップＳ７０３に戻る。【０２４７】
バッファに蓄積された複製データをデータストア１６０に書き込むと判定された場合、サーバ１００は、バッファに蓄積された複製データをデータストア１６０に書き込み（ステップＳ８０３）、その後、ステップＳ７０３に戻る。具体的には、以下のような処理が実行される。【０２４８】
復旧制御部１５３は、バッファに蓄積された複製データに含まれるシーケンス番号を参照し、最も小さいシーケンス番号を含む複製データを選択する。復旧制御部１５３は、選択された複製データのキーを参照し、バッファ及びデータストア１６０の中から当該キーと同一のキーを含む複製データを検索する。【０２４９】
復旧制御部１５３は、検索された複製データの中から最も大きいシーケンス番号を含む複製データを選択し、選択された複製データをデータストア１６０に書き込む。また、復旧制御部１５３は、バッファから検索された複製データを削除する。【０２５０】
なお、削除フラグ３０４が「Ｔｒｕｅ」の複製データも一時的にデータストア１６０に格納される。【０２５１】
復旧制御部１５３は、バッファにデータが蓄積されているか否かを判定する。バッファにデータが蓄積されていない場合、復旧制御部１５３は処理を終了する。一方、バッファにデータが蓄積されている場合、復旧制御部１５３は、同様の処理を繰り返し実行する。【０２５２】
なお、前述した処理では、シーケンス番号の順番に基づいて処理が実行されていたが、キーの辞書の登録順に処理が実行されてもよい。【０２５３】
以上がステップＳ８０３の処理の説明である。【０２５４】
ステップＳ７０４において、受信したデータが復旧完了データであると判定された場合、サーバ１００は、バッファに一時的に蓄積されたデータをデータストア１６０に書き込み、その後、削除フラグ３０４に基づいてデータストア１６０からデータを削除する（ステップＳ８０４）。具体的には、以下のような処理が実行される。【０２５５】
まず、復旧制御部１５３は、バッファに蓄積されたデータをデータストア１６０に書き込む。データの書込方法は、ステップＳ８０３と同一の方法を用いる。その後、復旧制御部１５３は、データ管理情報３００の削除フラグ３０４を参照し、削除フラグ３０４に「Ｔｒｕｅ」が格納されるデータを検索する。復旧制御部１５３は、検索されたデータをデータ管理情報３００から削除する。【０２５６】
以上がステップＳ８０４の処理の説明である。【０２５７】
ステップＳ７０６の処理は、実施例１の処理と同一であるため説明を省略する。【０２５８】
実施例２によれば、複製元のサーバ１００は排他ロックを取得する必要がないため、排他ロック制御に伴う処理のオーバーヘッドを削減することができる。【０２５９】
以上説明したように、本発明によれば、一つ又は所定数の複製データが送信されるため計算機システムのネットワークの通信量を低減することができる。また、複製元のサーバ１００は、復旧処理時にスナップショットを取得する必要がないためメモリの使用量を低減することができる。また、更新されたデータが優先的に送信することによって同一キーのデータの送信を抑制できるため、ネットワークの通信量を低減することができる。【０２６０】
また、複製データの書き込み順を制御することによって、データの整合性を保つことができる。更新処理を停止することなく、複製先のサーバ１００にデータを書き込むため、システムを停止させる必要がない。合流シーケンス番号に基づいて複製先のサーバ１００がクラスタに追加されるため、システム全体の整合性を保ち、かつ、明示的にシステムの構成を変更することができる。【０２６１】
なお、本実施例で例示した種々のソフトウェアは、電磁的、電子的及び光学式等の種々の記録媒体（例えば、非一時的な記憶媒体）に格納可能であり、インターネット等の通信網を通じて、コンピュータにダウンロード可能である。【０２６２】
さらに、本実施例では、ソフトウェアによる制御を用いた例について説明したが、その一部をハードウェアによって実現することも可能である。【０２６３】
以上、本発明を添付の図面を参照して詳細に説明したが、本発明はこのような具体的構成に限定されるものではなく、添付した請求の範囲の趣旨内における様々な変更及び同等の構成を含むものである。
【図１】
0005952960.tif 000002
【図２】
0005952960.tif 000003
【図３】
0005952960.tif 000004
【図４】
0005952960.tif 000005
【図５】
0005952960.tif 000006
【図６】
0005952960.tif 000007
【図７】
0005952960.tif 000008
【図８】
0005952960.tif 000009
【図９】
0005952960.tif 000010
【図１０】
0005952960.tif 000011
【図１１】
0005952960.tif 000012
【図１２】
0005952960.tif 000013
【図１３】
0005952960.tif 000014
【図１４】
0005952960.tif 000015
【図１５】
0005952960.tif 000016
【図１６】
0005952960.tif 000017
【図１７】
0005952960.tif 000018