JP5292350B2 - メッセージキュー管理システム及びロックサーバ及びメッセージキュー管理方法及びメッセージキュー管理プログラム - Google Patents

Description

本発明は、メッセージキュー管理システム及びロックサーバ及びメッセージキュー管理方法及びメッセージキュー管理プログラムに係り、特に、安価なハードウェアを用いた信頼性の低いネットワーク・コンピュータ・クラスタ環境において、ネットワーク故障及びサーバ故障耐性を備えたメッセージキュー管理システム及びロックサーバ及びメッセージキュー管理方法及びメッセージキュー管理プログラムに関する。

第１の従来技術として、安価なハードウェアを用いた信頼性の低いネットワーク・コンピュータ・クラスタ環境において、長時間トランザクションをサポートする技術がある。この技術は、マスタ交代に備えてデータを複製（レプリケーション）することによりサーバ故障への耐障害性、トランザクションによるクライアント端末の故障に対する耐障害性を実現するものである（例えば、非特許文献１参照）
また、第２の従来技術として、長時間トランザクションをサポートするためのメッセージキュー技術がある。この技術は、ディスク共有及びバックアップによりサーバ故障への耐障害性を実現するものである（例えば、特許文献１参照）。

また、第３の従来技術として、ネットワーク故障、サーバ故障のいずれにも対応したロックサービスがある。この技術は、ファイルにロックをかけるオペレーションを行うことでネットワーク故障、サーバ故障、クライアント故障のいずれに対しても対応が可能な技術である（例えば、非特許文献２，３参照）。

特開2004-086543号公報

http://www.ibm.com/software/jp/websphere/integration/wmq/ Mike Burrows, "The Chubby lock service for loosely-coupled distributed systems", 7th USENIX Symposium on Operating Systems Design and Implementation (OSDI), 2006. November 8.(http://research.google.com/archive/chubby-osdi06.pdf) Tushar Chandra et al., "Paxos Made Live - An Engineering Perspective," PODC'07, 2007.(http://labs.google.com/papers/paxos_made_live.html)

しかしながら、上記の第１の従来技術（非特許文献１）は、ネットワークが分断された場合には、マスタが複数存在するマルチマスタ状態が発生する可能性がある。また、トランザクションはロールバックされるため、タスクキューの実施例ではタスク処理に長時間を要するという問題がある。また、長時間トランザクションにより、キュー内の要素が失われないことは保証できるが、Paxos（信頼性が低いプロセッサのネットワークにおいて、単一の結果について合意を得る問題を解決するためのプロトコルの集合）を用いていないため、データの一貫性が保障できないケースがある。

また、第２の従来技術（特許文献１）は、サーバの冗長化に殆どの場合成功するが、クライアント故障によりデータが失われる可能性がある。

また、第３の従来技術（非特許文献２、３）は、ネットワーク故障、サーバ故障にも対応できるロックサービスであり、ロック・ファイル処理等のオペレーションが可能であるが、サーバ上のファイル操作とそれに対応する分散ロックをプリミティブな操作とした場合、その組み合わせだけでは、サーバが故障しフェイルオーバした場合にキュー内の情報の無矛盾性を保障することができない。例えば、ファイルにロックをかけた上でキュー情報を操作するのでは、一つのキュー操作（プッシュ・ポップ等）に対して、ファイルのロックと読み込み・書き込みの複数の操作を行わなければならず、十分な性能が期待できない。

本発明は、上記の点に鑑みなされたもので、同期している複数サーバ間でネットワークが分散した場合(Split Brain状態)にマルチマスタ状態を回避すると共に、マスタキューを保持しているサーバが故障し、フェイルオーバした場合に、キュー内の情報が矛盾することを防止することが可能なメッセージキュー管理システム及びロックサーバ及びメッセージキュー管理方法及びメッセージキュー管理プログラムを提供することを目的とする。

さらに、クラスタ内の一部のサーバが故障した場合でも、キューのトランザクション状態が導入されているシステムにおいて、当該状態を保持することが可能なメッセージキュー管理システム及びロックサーバ及びメッセージキュー管理方法及びメッセージキュー管理プログラムを提供することを目的とする。

図１は、本発明の原理構成図である。

本発明（請求項１）は、安価なハードウェアを用いた信頼性の低いネットワーク・コンピュータ・クラスタ環境での、複数のクライアント端末、複数のワーカ、プライマリサーバ、バックアップサーバ、マスタまたはレプリカの動作モードを有する複数のロックサーバを含む大規模分散処理システムにおいて、該クライアント端末、該ワーカ、該プライマリサーバ、該バックアップサーバをクライアント１とし、該クライアントと該複数のロックサーバ３００からなるメッセージキューシステムであって、
クライアント１は、
全てのマスタ候補に対して接続要求を送信し、該マスタ候補からセッションＩＤを取得し、該セッションＩＤに対するキュー操作要求を行う手段と、
セッションＩＤの送信元の該マスタ候補から所定の時間内にメッセージを受信できない場合には、全てのマスタ候補に該セッションＩＤを送信することにより再接続要求を送信する手段と、を有し、
ロックサーバ３００は、
キュー及び該キューの情報を格納したデータベース３０９と、
セッション情報を格納したセッション情報記憶手段と、
削除待ちのセッション情報を格納した削除待ちセッション記憶手段と、
マスタは常に一台であることを保証する多数決プロトコルであるPaxosを用いて自装置がマスタか否かを判定するマスタ調整手段３０１と、
マスタ調整手段３０１の結果、マスタが交代した場合には、データベース３０９内に予め複製されていたキューの情報及びクライアント１からの再接続要求によって有効なセッションの確認を行い、キューに対する操作の途中状態を復元し、自装置がマスタになれば非マスタにデータ複製を要求し、自装置がマスタでなければマスタからのデータ復元要求に応じて、自装置内にデータを複製するレプリケーション手段３０７と、を有し、
レプリケーション手段３０７は、
自装置が以前マスタではなかった場合は、セッション情報記憶手段からマスタ交代前のセッション情報を読み込んで、削除待ちセッション記憶手段に格納し、該セッション情報記憶手段のセッション情報を削除し、所定の時間が経過後、該削除待ちセッション記憶手段にセッションがある場合には、該削除待ちセッション記憶手段からセッションＩＤを取得し、データベース３０９の該セッションＩＤに該当するクライアントが保持していたキューの途中状態を無効化する第１のセッション制御手段と、
クライアント１からの接続要求に対しては、セッションＩＤを発行し、セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する接続要求処理手段と、該クライアント１からの再接続要求に対しては、削除待ちセッション情報記憶手段から該再接続要求に該当するセッションＩＤを削除し、該セッションＩＤを該セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する再接続要求処理手段と、該クライアントからの要求が該接続要求及び該再接続要求以外であれば、要求内容に応じてデータベース３０９内のキューに対する処理を行い、レプリカとして動作するロックサーバに送信する要求処理手段と、を含む第２のセッション制御手段と、を含む。

また、本発明（請求項２）は、第２のセッション制御手段の要求処理手段において、
クライアント１からの要求がキューのプッシュ操作要求である場合は、取得したキューＩＤ、キー、及びキー値を用いてデータベースのキューに対してプッシュ操作を行うプッシュ手段と、
クライアント１からの要求がキューのポップ操作要求である場合は、取得したキューＩＤに基づいてデータベース３０９のキューについてポップ操作を行うポップ手段と、
クライアント１からの要求が削除要求である場合は、取得したキューＩＤ、キーを用いてデータベース３０９のキューについて削除操作を行う削除手段と、
クライアント１からの要求が、キューに対する操作の途中状態の復元のための要求であるマーク要求である場合は、キューＩＤとセッションＩＤを取得し、データベース３０９から該キューＩＤに該当するキューの先頭レコードを取得し、該レコードにセッションＩＤが設定されていなければ、取得した該セッションＩＤを設定するマーク手段と、
クライアント１からの要求が、キューに対する操作の途中状態を復元しない要求であるアンマーク要求である場合は、キューＩＤとキーを取得し、データベース３０９から該キューＩＤに該当するレコード一覧から該キーに対応するレコードを取得して、該レコードのセッションＩＤを削除するアンマーク手段と、を含む。

本発明（請求項３）は、安価なハードウェアを用いた信頼性の低いネットワーク・コンピュータ・クラスタ環境での、複数のクライアント端末、複数のワーカ、プライマリサーバ、バックアップサーバ、マスタまたはレプリカの動作モードを有する複数のロックサーバを含む大規模分散処理システムにおいて、該クライアント端末、該ワーカ、該プライマリサーバ、該バックアップサーバをクライアントとするシステムにおけるロックサーバであって、
キュー及び該キューの情報を格納したデータベースと、
セッション情報を格納したセッション情報記憶手段と、
削除待ちのセッション情報を格納した削除待ちセッション記憶手段と、
マスタは常に一台であることを保証する多数決プロトコルであるPaxosを用いて自装置がマスタか否かを判定するマスタ調整手段と、
マスタ調整手段の結果、マスタが交代した場合には、データベース内に予め複製されていたキューの情報及びクライアントからの再接続要求によって有効なセッションの確認を行い、キューに対する操作の途中状態を復元し、自装置がマスタになれば非マスタにデータ複製を要求し、自装置がマスタでなければマスタからのデータ復元要求に応じて、自装置内にデータを複製するレプリケーション手段と、を有し、
レプリケーション手段は、
自装置が以前マスタではなかった場合は、セッション情報記憶手段からマスタ交代前のセッション情報を読み込んで、削除待ちセッション記憶手段に格納し、該セッション情報記憶手段のセッション情報を削除し、所定の時間が経過後、該削除待ちセッション記憶手段にセッションがある場合には、該削除待ちセッション記憶手段からセッションＩＤを取得し、データベースの該セッションＩＤに該当するクライアントが保持していたキューの途中状態を無効化する第１のセッション制御手段と、
クライアントからの接続要求に対しては、セッションＩＤを発行し、セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する接続要求処理手段と、該クライアントからの再接続要求に対しては、削除待ちセッション情報記憶手段から該再接続要求に該当するセッションＩＤを削除し、該セッションＩＤを該セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する再接続要求処理手段と、該クライアントからの要求が該接続要求及び該再接続要求以外であれば、要求内容に応じてデータベース内のキューに対する処理を行い、他のロックサーバに送信する要求処理手段と、を含む第２のセッション制御手段と、を含む。

また、本発明（請求項４）は、第２のセッション制御手段の要求処理手段において、
クライアントからの要求がキューのプッシュ操作要求である場合は、取得したキューＩＤ、キー、及びキー値を用いてデータベースのキューに対してプッシュ操作を行うプッシュ手段と、
クライアントからの要求がキューのポップ操作要求である場合は、取得したキューＩＤに基づいてデータベースのキューについてポップ操作を行うポップ手段と、
クライアントからの要求が削除要求である場合は、取得したキューＩＤ、キーを用いてデータベースのキューについて削除操作を行う削除手段と、
クライアントからの要求が、キューに対する操作の途中状態の復元のための要求であるマーク要求である場合は、キューＩＤとセッションＩＤを取得し、データベースから該キューＩＤに該当するキューの先頭レコードを取得し、該レコードにセッションＩＤが設定されていなければ、取得した該セッションＩＤを設定するマーク手段と、
クライアントからの要求が、キューに対する途中状態を復元しない要求であるアンマーク要求である場合は、キューＩＤとキーを取得し、データベースから該キューＩＤに該当するレコード一覧から該キーに対応するレコードを取得して、該レコードのセッションＩＤを削除するアンマーク手段と、を含む。

本発明（請求項５）は、安価なハードウェアを用いた信頼性の低いネットワーク・コンピュータ・クラスタ環境での、複数のクライアント端末、複数のワーカ、プライマリサーバ、バックアップサーバ、マスタまたはレプリカの動作モードを有する複数のロックサーバを含む大規模分散処理システムにおいて、該クライアント端末、該ワーカ、該プライマリサーバ、該バックアップサーバをクライアントとし、該複数のロックサーバのうちのいずれかをマスタとするメッセージキュー管理方法であって、
クライアントは、
全てのマスタ候補となるロックサーバに対して接続要求を送信し、該マスタ候補からセッションＩＤを取得し、該セッションＩＤに対するキュー操作要求を行うステップと、
セッションＩＤの送信元の該マスタ候補から所定の時間内にメッセージを受信できない場合には、全てのマスタ候補に該セッションＩＤを送信することにより再接続要求を送信するステップと、を行い、
ロックサーバは、
マスタは常に一台であることを保証する多数決プロトコルであるPaxosを用いて自装置がマスタか否かを判定するマスタ調整ステップと、
マスタ調整ステップの結果、マスタが交代した場合には、データベース内に予め複製されていたキューの情報及びクライアントからの再接続要求によって有効なセッションの確認を行い、キューに対する操作の途中状態を復元し、自装置がマスタになれば非マスタにデータ複製を要求し、自装置がマスタでなければマスタからのデータ復元要求に応じて、自装置内にデータを複製するレプリケーションステップと、を行い、
レプリケーションステップにおいて、
自装置が以前マスタではなかった場合は、
セッション情報を格納したセッション情報記憶手段からマスタ交代前のセッション情報を読み込んで、削除待ちのセッション情報を格納した削除待ちセッション記憶手段に格納し、該セッション情報記憶手段のセッション情報を削除し、所定の時間が経過後、該削除待ちセッション記憶手段にセッションがある場合には、該削除待ちセッション記憶手段からセッションＩＤを取得し、データベースの該セッションＩＤに該当するクライントが保持していたキューの途中状態を無効化する第１のセッション制御ステップと、
クライアントからの接続要求に対しては、セッションＩＤを発行し、セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信し、
該クライアントからの再接続要求に対しては、削除待ちセッション情報記憶手段から該再接続要求に該当するセッションＩＤを削除し、該セッションＩＤを該セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信し、
該クライアントからの要求が該接続要求及び該再接続要求以外であれば、要求内容に応じてデータベース内のキューに対する処理を行い、他のロックサーバに送信する第２のセッション制御ステップと、を含む。

また、本発明（請求項６）は、第２のセッション制御ステップにおいて、
クライアントからの要求がキューのプッシュ操作要求である場合は、取得したキューＩＤ、キー、及びキー値を用いてデータベースのキューに対してプッシュ操作を行い、
クライアントからの要求がキューのポップ操作要求である場合は、取得したキューＩＤに基づいてデータベースのキューについてポップ操作を行い、
クライアントからの要求が削除要求である場合は、取得したキューＩＤ、キーを用いてデータベースのキューについて削除操作を行い、
クライアントからの要求が、キューに対する操作の途中状態の復元のための要求であるマーク要求である場合は、キューＩＤとセッションＩＤを取得し、データベースから該キューＩＤに該当するキューの先頭レコードを取得し、該レコードにセッションＩＤが設定されていなければ、取得した該セッションＩＤを設定するマーク操作を行い、
クライアントからの要求が、キューに対する途中状態を復元しない要求であるアンマーク要求である場合は、キューＩＤとキーを取得し、データベースから該キューＩＤに該当するレコード一覧から該キーに対応するレコードを取得して、該レコードのセッションＩＤを削除するアンマーク操作を行う。

本発明（請求項７）は、請求項３または４に記載のロックサーバを構成する各手段としてコンピュータを機能させるためのメッセージキュー管理プログラムである。

上記のように本発明によれば、安価なハードウェアを用いた信頼性の低いネットワーク・コンピュータ・クラスタ環境において、予め決められた候補の中から多数決によって一意なマスタを選出することにより、マルチマスタ状態となることを回避する。

また、レプリケーションとフェイルオーバによりマスタが故障しても新しいマスタに役割を引き継ぐのみで動作を継続するため、クラスタ内の一部のサーバが故障した場合であっても、キューのトランザクション状態が導入されているシステムにおいて、キュー内の情報が矛盾する問題を防止する。

また、クラスタ内の一部のサーバが故障した場合であっても、キューのトランザクション状態が導入されているシステムにおいて、当該状態を保持できる。即ち、タスクキューに適用した場合、タスクの再実行を防ぐことにより、システムの処理効率が向上する。

本発明の原理構成図である。 本発明を適用するシステム構成図である。 本発明の一実施の形態における要部のシステム構成図である。 本発明の一実施の形態におけるセッション一覧記憶部のテーブルの例である。 本発明の一実施の形態における削除待ちセッション一覧記憶部のテーブルの例である。 本発明の一実施の形態におけるＤＢのテーブルの例である。 本発明の一実施の形態におけるクライアントの動作のフローチャートである。 本発明の一実施の形態におけるロックサーバのフローチャートである。 本発明の一実施の形態におけるクライアントとのセッション復元処理（Ｓ１０６０）のフローチャートである。 本発明の一実施の形態におけるクライアントからの要求受付開始処理（Ｓ１０７０）のフローチャートである。 本発明の一実施の形態におけるキュー制御部のプッシュ操作のフローチャートである。 本発明の一実施の形態におけるキュー制御部のポップ操作のフローチャートである。 本発明の一実施の形態におけるキュー制御部のデリート操作のフローチャートである。 本発明の一実施の形態におけるキュー制御部のマーク操作のフローチャートである。 本発明の一実施の形態におけるアンマーク操作のフローチャートである。 本発明の一実施の形態におけるクライアントからの要求受付閉塞処理（Ｓ１１００，Ｓ２１３０）のフローチャートである。

以下、図面と共に本発明の実施の形態を説明する。

図３は、本発明を適用するシステム構成を示す。

本発明は、図２に示すように、分散ファイルシステムのデータ管理と制御を行うプライマリサーバ１００、バックアップサーバ２００、分散システムの可用性とシステムとしての一貫性を高めるための基本機能を提供するマスタまたはレプリカとしての動作モードを有するロックサーバ３００、分散システムの分散ファイルシステムを利用するアプリケーションにリンクされるクライアント端末ライブラリを有する複数のクライアント端末１０、物理的にデータを保持する複数のワーカ２０から構成される、大規模分散処理システムに適用される技術である。

プライマリサーバ１００は、クライアント端末１０からのファイルのメタ情報取得・更新要求を取得して、更新されたメタ情報を複製してバックアップサーバ２００に送信し、メタ情報に基づいてワーカ２０に対するデータ管理及び制御を行う。また、分散ファイルマスタの状態をロックサーバマスタ３００に保存する。

クライアント端末１０は、ロックサーバ３００からプライマリサーバ１００の位置情報を取得し、プライマリサーバ１００からファイルのメタ情報を取得し、プライマリサーバ１００から渡された、データを管理しているワーカ２０のメタ情報に基づいてデータの読み出しを行う、または、データの書き込みを行う。

ワーカ２０は、クライアント端末１０からアクセスされることにより、データの登録、提供を行う。

ロックサーバ（マスタ）３００は、分散ファイルマスタ状態と分散マスタの位置情報を管理し、プライマリサーバ１００、バックアップサーバ２００からのロック獲得要求を受け、サーバ間の排他制御を行うと共に、死活状態の監視を行い、例えば、プライマリサーバ１００に障害が発生した場合には、当該プライマリサーバ１００の死活監視ファイルを削除する。ロックサーバ（レプリカ）３００は、マスタとなっているロックサーバ３００の複製された情報を保持する。

図３は、本発明の一実施の形態における要部のシステム構成を示す。同図では、本実施の形態における要部としてロックサーバ３００の構成を示す。
同図に示す「クライアント」とは、ロックサーバ３００から見た通信相手を指し、図２に示すクライアント端末１０のみならず、分散ファイルマスタのプライマリサーバ１００、バックアップサーバ２００、ワーカ２０のいずれかを指すものとする。

同図に示すロックサーバ３００は、マスタ調停部３０１、マスタ管理部３０２、セッション管理部３０３、セッション一覧記憶部３０４、削除待ちセッション一覧記憶部３０５、要求処理部３０６、レプリケーション管理部３０７、データベース（ＤＢ）３０９、トランザクション管理部３１０を有する。

上記のセッション一覧記憶部３０４、削除待ちセッション一覧記憶部３０５は、メモリまたはハードディスク等の記憶媒体である。

セッション一覧記憶部３０４及び削除待ちセッション一覧記憶部３０５は、セッション管理部３０３から参照、更新されるテーブルであり、図４、図５にそれぞれ示すように、セッションＩＤ、ＩＰアドレスなどのクライアント情報、及びマークしているキューのエントリからなるテーブルを格納している。なお、削除待ちセッション一覧記憶部３０５のテーブルはマスタ交代直後のみ保持される。

ＤＢ３０９は、図６に示すように、キュー一覧（同図（Ａ））とキューＩＤ毎のレコード一覧（同図（Ｂ））のテーブルを有する。

最初に、クライアント１の動作について説明する。

図７は、本発明の一実施の形態におけるクライアントの動作のフローチャートである。

ステップ１０１） クライアント１は、全てのマスタ候補（ロックサーバ３００）に対して接続要求を送信する。

ステップ１０２） マスタとして動作しているロックサーバ３００からセッションＩＤを受信する。

ステップ１０３） セッションＩＤ送信元のマスタに対して受信確認を送信する。

ステップ１０４） 死活監視タイマをセットする。

ステップ１０５） 死活監視タイマがタイムアウトする前に上記のマスタ候補のロックサーバ３００から応答を受信したかを判定し、受信した場合はステップ１０３に移行し、受信していない場合は、ステップ１０６に移行する。

ステップ１０６） 再接続タイマをセットする。

ステップ１０７） 全てのマスタ候補のロックサーバ３００へセッションＩＤを含む再接続要求を送信する。

ステップ１０８） 再接続タイマがタイムアウトする前にマスタとして動作しているロックサーバ３００から返信が得られたかを判定し、得られた場合はステップ１０３に移行し、得られない場合は当該処理を終了する。

図８は、本発明の一実施の形態におけるロックサーバのフローチャートである。

同図に示す処理は、Paxosによるマスタの選出処理、レプリケーション及びフェイルオーバによるデータの冗長化、紛失防止キューのための処理が含まれる。

ステップ１０１０） オペレータがシステムを起動すると、マスタ調停部３０１は、Paxosによるマスタ選定処理を行う。当該処理は、例えば、文献１『Leslie Lamport, "Paxos Made Simpke, "ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001) 51-58』、文献２『Cary G. Gray and Davide R. Cheriton, "Leases: An Efficient Fault-Tolerant Mechanism for Distributed File Cache Coherency," Procs of 12th ACM SOSP '89, 202-210,1989』、及び前述の非特許文献２に開示されている方法を採用する。

当該方法は、システム上の予め決められたマスタ候補のロックサーバ３００中から多数決によって一意なマスタを選出する。具体的には、マスタと同期できないサーバは停止する。これによりマルチマスタ状態とはなならい。これは、Paxosにより、一つの議題について、多数決の結論（＝新しいマスタ）は必ず一つの値に収束するためである。

ステップ１０２０） マスタ管理部３０２は、自サーバ３００が上記のステップ１０１０の処理によりマスタとして選出されたかを判定し、選出された場合はステップ１０３０に移行し、選出されない場合にはステップ１１１０に移行する。

ステップ１０３０） マスタリースタイマをセットする。ここで、「マスタリース」とは、マスタの状態を継続する期限を指す。

ステップ１０４０） 次回マスタを選出するためのタイマをセットする。

ステップ１０５０） マスタ管理部３０２は、自装置が以前もマスタであり、かつ、以前のマスタリースタイマがタイムアウトしていない場合はステップ１０７０に移行し、以前はマスタコンピュータではない、または、以前のマスタリースタイマがタイムアウトしている場合、つまり、マスタが交代した場合はステップ１０６０に移行する。

ステップ１０６０） セッション管理部３０３は、クライアント１とのセッションを復元し、ステップ１０７０に移行する。当該動作は、マスタが交代した際の処理であり、当該ロックサーバ３００がマスタでない状態からマスタとなった契機において、マスタとして動作を開始するために必要な処理である。この詳細動作を図９に示す。

図９は、本発明の一実施の形態におけるクライアント端末とのセッション復元処理のフローチャートである。

ステップ５０１０） クライアント１とのセッションを復元する際に、セッション管理部３０３は、図４に示すセッション情報記憶部３０４からマスタ交代前のセッション情報を読み込み、全情報を図５に示す削除待ちセッション一覧記憶部３０５に書き込む。

ステップ５０２０） セッション管理部３０３は、図４のセッション一覧記憶部３０４のテーブル内の前情報を削除する。

ステップ５０３０） セッション管理部３０３は、セッション削除タイマをセットする。

ステップ５０４０） セッション管理部３０３は、セッション削除タイマがタイムアウトしたならステップ５０５０に移行する。

ステップ５０５０） セッション管理部３０３は、削除待ちセッション一覧記憶部３０５のテーブルが空であれば当該処理を終了し、空でなければ、ステップ５０６０に移行する。

ステップ５０６０） セッション管理部３０３は、削除待ちセッション一覧記憶部３０５の任意の１セッションを選択する。

ステップ５０７０） セッション管理部３０３は、選択された当該セッションの削除処理を行う。具体的には、セッション一覧記憶部３０４からセッションＩＤに関連するクライアントが保持していたキューを全て取得して削除する。

ステップ１０７０） 要求処理部３０６は、上記のステプ５０１０〜５０７０の処理が終了すると、クライアント１からの要求の受付を開始する。

以下に当該クライアント１からの要求受付処理を図１０に基づいて詳細に説明する。図１０は、本発明の一実施の形態におけるクライアントからの要求受付開始処理のフローチャートである。

ステップ２０２０） 要求処理部３０６は、クライアント１から要求があった場合はステップ２０３０に移行し、ない場合は待機する。

ステップ２０３０） 要求処理部３０６は、クライアント１からの要求を取得すると、当該要求が（最初の）接続要求か否かを判断し、接続要求である場合はステップ２０４０に移行し、それ以外の場合はステップ２０７０に移行する。

ステップ２０４０） セッション管理部３０３は、セッションＩＤを発行し、セッション一覧記憶部３０４に追加格納する。

ステップ２０５０） 要求処理部３０６は、セッション管理部３０３において発行されたセッションＩＤをクライアント１に通知する。

ステップ２０６０） クライアント監視プロセスを起動し、ステップ２０２０に移行する。

ステップ２０７０） ステップ２０３０において、取得した要求が再接続要求である場合は、ステップ２０８０に移行し、それ以外の場合はステップ２１００に移行する。

ステップ２０８０） セッション管理部３０３は、受信した要求が再接続要求である場合は、削除待ちセッション一覧記憶部３０５から、当該要求に該当するセッションＩＤを削除する。

ステップ２０９０） セッション管理部３０３は、セッションＩＤをセッション一覧記憶部３０４に追加格納し、ステップ２０５０に移行する。

ステップ２１００） ステップ２０７０において、要求処理部３０６によりクライアント１からの要求が再接続要求以外の要求であると判断された場合は、レプリケーション管理部３０７のキュー制御部３０８は、要求の内容に応じて、図６に示すＤＢ３０９内のキューに対する処理を実行する。当該キューに対する各種の処理について、図１１〜図１５に基づいて説明する。

＜プッシュ操作＞
キュー制御部３０８のキューに対するプッシュ操作を図１１に示す。

ステップ１１０１０） キュー制御部３０７は、クライアント１からプッシュ操作要求としてキューＩＤ、キー（Ｋ）、値（Ｖ）が入力されると、キューＩＤに基づいてＤＢ３０９内のキュー一覧（図６（Ａ））からキューの最後のレコード(Last)を取得する。

ステップ１１０２０） 以下に示す入力された入力キー（Ｋ）、入力値（Ｖ）を用いてレコードを作成し、キューＩＤに対応付けてレコード一覧（図６（Ｂ））に挿入する。また、キュー一覧（図６（Ａ））の最後尾キーの次のキーを入力キーとして最後尾レコードを更新する。

ステップ１１０３０） ＤＢ３０９内のキュー一覧表（図６（Ａ））の当該キューの最後尾キーを入力キー（Ｋ）で更新する。

＜ポップ操作＞
次に、キュー制御部３０７のポップ操作を図１２に示す。

ステップ１２０１０） キュー制御部３０８は、クライアント１からポップ操作要求としてキューＩＤが入力されると、キューＩＤを用いてＤＢ３０９内のキュー一覧（図６（Ａ））から当該キューの先頭レコード（Front）を取得する。

ステップ１２０２０） 当該先頭レコード(Front)をＤＢ３０９のキュー一覧（図６（Ａ））から削除する。

ステップ１２０３０） キュー一覧（図６（Ａ））上の当該キューＩＤに対応するキューの先頭キーを先頭キーの次のキー『Front.次キー』にて更新する。

＜デリート操作＞
次に、キュー制御部３０８のデリート操作を図１３に示す。

ステップ１３０１０） キュー制御部３０８は、クライアント１からデリート操作要求としてキューＩＤとキー（Ｋ）が入力されると、ＤＢ３０９のレコード一覧（図６（Ｂ））から当該キューＩＤに対応する当該キーのレコードＣを取得する。

ステップ１３０２０） レコードＣの前キー「Prev」及び次キー「Next」を基に、レコードＢ、レコードＡを取得する。

ステップ１３０３０） レコードＢの次キーをレコードＡのキーで、レコードＡの次キーをレコードＢのキーで更新し、レコードＣを削除する。

＜マーク操作＞
次に、キュー制御部３０８のマーク操作を図１４に示す。ここで「マーク操作」とは、キューに対する途中状態の復元を指す。

ステップ１４０１０） キュー制御部３０８は、クライアント１からマーク操作要求としてセッションＩＤ，キューＩＤが入力されると、キューの先頭レコードをＤＢ３０９のキュー一覧（図６（Ａ））から取得し、現在レコードとする。

ステップ１４０２０） 取得した現在レコードのセッションＩＤが空欄ならばステップ１４０４０へ移行し、セッションＩＤが空欄でなかった場合はステップ１４０３０に移行する。

ステップ１４０３０） 現在のレコードの次キーをもとに、次のレコードをキューのレコード一覧（図６（Ｂ）)より取得し、現在レコードとし、ステップ１４０２０に移行する。次キーが空欄だった場合には失敗とし、当該処理を終了する。

ステップ１４０４０） 現在レコードのセッションＩＤを、入力されたセッションＩＤにより更新する。

＜アンマーク操作＞
次に、キュー制御部３０８のアンマーク操作を図１５に示す。ここで、「アンマーク操作」とは、キューに対する途中状態の復元を行わず、クライアント１が故障した際に、キュー内のエントリが永久に残留する問題を解決するものである。

ステップ１５０１０） キュー制御部３０８は、クライアント１からアンマーク操作要求としてキー、キューＩＤが入力されると、キューＩＤに該当するレコード一覧（図６（Ｂ））から入力キーに該当するレコードを取得する。

ステップ１５０２０） 当該レコードのセッションＩＤを空欄に更新する。

ステップ２１１０） レプリケーション管理部３０７は、上記のプッシュ操作、ポップ操作、デリート操作、マーク操作、アンマーク操作のいずれかの処理結果をレプリカ３０に送信する。

ステップ２１２０） レプリカ３０から返信が得られた場合はステップ２０２０に移行し、得られない場合はステップ２１３０に移行する。

ステップ２１３０） 要求処理部３０６は、クライアント１からの要求の受付を閉塞する。当該ステップの詳細は図１６にて詳述する。

ステップ１０８０） 次回マスタ選出タイマがタイムアウトしたかを判定し、タイムアウトした場合は、ステップ１０９０に移行し、タイムアウトしていなければ当該処理を繰り返す。

ステップ１０９０） マスタリースはタイムアウトしたかを判定し、タイムアウトした場合には、ステップ１１００に移行し、タイムアウトしていなければ当該処理を繰り返す。

ステップ１１００） 要求処理部３０６は、クライアント１からの要求受付を閉塞する。当該処理を図１６を用いて説明する。

ステップ３０１０） クライアント１からの要求受付プロセスを停止する。

ステップ３０２０） 全てのクライアント端末監視プロセスを停止する。

ステップ３０３０） 全てのセッション情報をセッション一覧記憶部３０５から削除する。

ステップ１１１０） 次に、上記のステップ１０２０において、自身がマスタとして選出されなかった場合は、マスタリースタイマをセットする。

ステップ１１２０） マスタからのレプリケーション要求受付を開始する。当該処理は、文献３『Jim Gray et al., "The Recovery Manager of the System R Database Manager", Computing Surveys, Vol. 13, No.2, 1981.』及び文献４『David K. Gifford, "Weighted Voting for Replicated Data", Proc of SIGOPS, pp. 150-162, 1979.』に示される処理を行うものとする。

ステップ１１３０） マスタリースタイマがタイムアウトした場合はステップ１１４０に移行する。

ステップ１１４０） マスタからのレプリケーション要求の受付を閉塞し、ステップ１０１０に移行する。当該処理は上記の文献３,４と同様の処理を行うものとする。

次に、図８のステップ１１００，図１０の２１３０におけるクライアントからの要求受付の閉塞処理について説明する。

図１６は、本発明の一実施の形態におけるクライアントからの要求受付閉塞処理（Ｓ１１００，Ｓ２１３０）のフローチャートである。

ステップ３０１０） 要求処理部３０６は、クライアントからの要求受付プロセスを停止する。

ステップ３０２０） 全てのクライアントの監視プロセスを停止する。

ステップ３０３０） 全てのセッション情報を削除する。

上記の一連のフローチャートにおいて、図８のステップ１０１０〜１１００では、多数決プロトコルPaxosによるマスタ選出を行うことにより、マスタは常に１台であることが保証される。これにより、ネットワーク故障によるネットワーク分断状態（Split Brain状態）になっても、システムが管理しているキューのデータ構造が複数のマスタによって更新されることなないため、キューのデータ構造の整合性を維持することができる。

また、マスタ故障によってマスタが存在しなくなった場合にも、このマスタに代わる次のマスタを選出する機能が含まれているため、新しいマスタが動作を引き継ぐことができる。

マスタが動作を引き継ぐ場合は、図８のステップ１０７０及び図１０のフローチャートに示す処理を行う。ここでは、サーバがマスタでない状態からマスタとなった契機において、マスタとして動作を開始するために必要な処理を行っている。

新しくマスタとなったロックサーバ３００は、図１０のステップ２１００〜ステップ２１２０によって予め復元されていた図４、図５、図６及び図７に示すクライアントから再接続処理（ステップ１０７）によって、有効なセッションの確認を行う。これにより、キュー内のデータの仕掛かり中（図６（Ｂ）マーク済）状態が正当であること（＝マークされているが、マークしているセッションが存在しない状態となっているキュー内のレコード）を確認し、サーバ故障状態及びネットワーク故障状態からの復帰を行う。

このとき、前述の非特許文献１のように、データ変更が仕掛り中であることを示すためにトランザクションを用いるのでは、トランザクションの途中の状態を復元（レプリケーション）しなければならない。しかし、トランザクションの途中状態（各種データに対する全てのロック状態）を汎用的に復元していたのでは性能向上は難しい。そこで、本発明では、図６（Ｂ），図１４、図１５にあるように、トランザクションの途中状態を「マーク状態」として、キュー内の一つにエントリに限るものとして限定することにより、途中状態の復元を容易にした。これによって、キュー内に対する操作の途中状態を復元することが可能となる。図６（Ｂ）、図１４、図１５の詳細については上記のフローチャートのステップ１４０１０〜１４０４０、ステップ１５１０，１５２０に示すとおりである。

また、マスタ交代に備えてデータを復元（レプリケーション）する処理は、上記のフローチャートの図１０のステップ２０７０〜２０８０に示す。ここでの論理的な処理は図１１から図１５に示すとおりである。図１１〜図１５の処理の背後で、文献３と同様のアルゴリズムを用いてデータを永続化し、文献４と同様のアルゴリズムを用いてデータを復元している。これにより、サーバ故障及びネットワーク故障に由来するマスタ交代への対故障性を担保している。

クライアント１は、セッションが正常な状態にあるときのみ（図７に示すステップ１０３〜１０５）、プッシュ・ポップ・デリート・マーク・アンマークのいずれかのキュー操作要求をマスタに送信し、マスタはクライアント１の操作要求に基づいて、図１０に示すステップ２１００〜２１２０のキュー操作を行う。図６（Ｂ）のデータ構造及び図１１〜図１５によってキューの操作を定義する。

このように、キューに対してこれらのKey-Value形式の１レコードをキューの１エントリに対応させることにより、キューの論理的なデータ構造を実現する
なお、上記のロックサーバ３００の処理をプログラムとして構築し、これらのコンピュータにインストールして実行させる、または、ネットワークを介して流通させることも可能である。

また、構築されたプログラムをハードディスクや、フレキシブルディスク・ＣＤ−ＲＯＭ等の可搬記憶媒体に格納し、コンピュータにインストールする、または、配布することが可能である。

なお、本発明は、上記の実施の形態に限定されることなく、特許請求の範囲内において種々変更・応用が可能である。

１ クライアント
１０ クライアント端末
２０ ワーカ
１００ プライマリサーバ
２００ バックアップサーバ
３００ ロックサーバ
３０１ マスタ調整手段
３０２ マスタ管理部
３０３ セッション管理部
３０４ セッション一覧記憶部
３０５ 削除待ちセッション一覧記憶部
３０６ 要求処理部
３０７ レプリケーション手段、レプリケーション部
３０９ データベース

Claims (7)

1. ネットワーク・コンピュータ・クラスタ環境での、複数のクライアント端末、複数のワーカ、プライマリサーバ、バックアップサーバ、マスタまたはレプリカの動作モードを有する複数のロックサーバを含む大規模分散処理システムにおいて、該クライアント端末、該ワーカ、該プライマリサーバ、該バックアップサーバをクライアントとし、該クライアントと該複数のロックサーバからなるメッセージキューシステムであって、
   前記クライアントは、
   全てのマスタ候補に対して接続要求を送信し、該マスタ候補からセッションＩＤを取得し、該セッションＩＤに対するキュー操作要求を行う手段と、
   前記セッションＩＤの送信元の該マスタ候補から所定の時間内にメッセージを受信できない場合には、全てのマスタ候補に該セッションＩＤを送信することにより再接続要求を送信する手段と、を有し、
   前記ロックサーバは、
   キュー及び該キューの情報を格納したデータベースと、
   セッション情報を格納したセッション情報記憶手段と、
   削除待ちのセッション情報を格納した削除待ちセッション記憶手段と、
   マスタは常に一台であることを保証する多数決プロトコルであるPaxosを用いて自装置がマスタか否かを判定するマスタ調整手段と、
   前記マスタ調整手段の結果、マスタが交代した場合には、前記データベース内に予め複製されていたキューの情報及び前記クライアントからの再接続要求によって有効なセッションの確認を行い、キューに対する操作の途中状態を復元し、自装置がマスタになれば非マスタにデータ複製を要求し、自装置がマスタでなければマスタからのデータ復元要求に応じて、自装置内にデータを複製するレプリケーション手段と、
   を有し、
   前記レプリケーション手段は、
   前記自装置が以前マスタではなかった場合は、前記セッション情報記憶手段からマスタ交代前のセッション情報を読み込んで、前記削除待ちセッション記憶手段に格納し、該セッション情報記憶手段のセッション情報を削除し、所定の時間が経過後、該削除待ちセッション記憶手段にセッションがある場合には、該削除待ちセッション記憶手段からセッションＩＤを取得し、前記データベースの該セッションＩＤに該当するクライアントが保持していたキューの途中状態を無効化する第１のセッション制御手段と、
   前記クライアントからの接続要求に対しては、セッションＩＤを発行し、前記セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する接続要求処理手段と、該クライアントからの再接続要求に対しては、前記削除待ちセッション情報記憶手段から該再接続要求に該当するセッションＩＤを削除し、該セッションＩＤを該セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する再接続要求処理手段と、該クライアントからの要求が該接続要求及び該再接続要求以外であれば、要求内容に応じて前記データベース内のキューに対する処理を行い、レプリカとして動作するロックサーバに送信する要求処理手段と、を含む第２のセッション制御手段と、
   を含むことを特徴とするメッセージキューシステム。
2. 前記第２のセッション制御手段の前記要求処理手段は、
   前記クライアントからの要求がキューのプッシュ操作要求である場合は、取得したキューＩＤ、キー、及びキー値を用いて前記データベースのキューに対してプッシュ操作を行うプッシュ手段と、
   前記クライアントからの要求がキューのポップ操作要求である場合は、取得したキューＩＤに基づいて前記データベースのキューについてポップ操作を行うポップ手段と、
   前記クライアントからの要求が削除要求である場合は、取得したキューＩＤ、キーを用いて前記データベースのキューについて削除操作を行う削除手段と、
   前記クライアントからの要求が、キューに対する操作の途中状態の復元のための要求であるマーク要求である場合は、キューＩＤとセッションＩＤを取得し、前記データベースから該キューＩＤに該当するキューの先頭レコードを取得し、該レコードにセッションＩＤが設定されていなければ、取得した該セッションＩＤを設定するマーク手段と、
   前記クライアントからの要求が、キューに対する操作の途中状態を復元しない要求であるアンマーク要求である場合は、キューＩＤとキーを取得し、前記データベースから該キューＩＤに該当するレコード一覧から該キーに対応するレコードを取得して、該レコードのセッションＩＤを削除するアンマーク手段と、
   を含む請求項１記載のメッセージキューシステム。
3. ネットワーク・コンピュータ・クラスタ環境での、複数のクライアント端末、複数のワーカ、プライマリサーバ、バックアップサーバ、マスタまたはレプリカの動作モードを有する複数のロックサーバを含む大規模分散処理システムにおいて、該クライアント端末、該ワーカ、該プライマリサーバ、該バックアップサーバをクライアントとするシステムにおけるロックサーバであって、
   キュー及び該キューの情報を格納したデータベースと、
   セッション情報を格納したセッション情報記憶手段と、
   削除待ちのセッション情報を格納した削除待ちセッション記憶手段と、
   マスタは常に一台であることを保証する多数決プロトコルであるPaxosを用いて自装置がマスタか否かを判定するマスタ調整手段と、
   前記マスタ調整手段の結果、マスタが交代した場合には、前記データベース内に予め複製されていたキューの情報及び前記クライアントからの再接続要求によって有効なセッションの確認を行い、キューに対する操作の途中状態を復元し、自装置がマスタになれば非マスタにデータ複製を要求し、自装置がマスタでなければマスタからのデータ復元要求に応じて、自装置内にデータを複製するレプリケーション手段と、
   を有し、
   前記レプリケーション手段は、
   前記自装置が以前マスタではなかった場合は、前記セッション情報記憶手段からマスタ交代前のセッション情報を読み込んで、前記削除待ちセッション記憶手段に格納し、該セッション情報記憶手段のセッション情報を削除し、所定の時間が経過後、該削除待ちセッション記憶手段にセッションがある場合には、該削除待ちセッション記憶手段からセッションＩＤを取得し、前記データベースの該セッションＩＤに該当するクライアントが保持していたキューの途中状態を無効化する第１のセッション制御手段と、
   前記クライアントからの接続要求に対しては、セッションＩＤを発行し、前記セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する接続要求処理手段と、該クライアントからの再接続要求に対しては、前記削除待ちセッション情報記憶手段から該再接続要求に該当するセッションＩＤを削除し、該セッションＩＤを該セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信する再接続要求処理手段と、該クライアントからの要求が該接続要求及び該再接続要求以外であれば、要求内容に応じて前記データベース内のキューに対する処理を行い、他のロックサーバに送信する要求処理手段と、を含む第２のセッション制御手段と、
   を含むことを特徴とするロックサーバ。
4. 前記第２のセッション制御手段の前記要求処理手段は、
   前記クライアントからの要求がキューのプッシュ操作要求である場合は、取得したキューＩＤ、キー、及びキー値を用いて前記データベースのキューに対してプッシュ操作を行うプッシュ手段と、
   前記クライアントからの要求がキューのポップ操作要求である場合は、取得したキューＩＤに基づいて前記データベースのキューについてポップ操作を行うポップ手段と、
   前記クライアントからの要求が削除要求である場合は、取得したキューＩＤ、キーを用いて前記データベースのキューについて削除操作を行う削除手段と、
   前記クライアントからの要求が、キューに対する操作の途中状態の復元のための要求であるマーク要求である場合は、キューＩＤとセッションＩＤを取得し、前記データベースから該キューＩＤに該当するキューの先頭レコードを取得し、該レコードにセッションＩＤが設定されていなければ、取得した該セッションＩＤを設定するマーク手段と、
   前記クライアントからの要求が、キューに対する途中状態を復元しない要求であるアンマーク要求である場合は、キューＩＤとキーを取得し、前記データベースから該キューＩＤに該当するレコード一覧から該キーに対応するレコードを取得して、該レコードのセッションＩＤを削除するアンマーク手段と、
   を含む請求項３記載のロックサーバ。
5. ネットワーク・コンピュータ・クラスタ環境での、複数のクライアント端末、複数のワーカ、プライマリサーバ、バックアップサーバ、マスタまたはレプリカの動作モードを有する複数のロックサーバを含む大規模分散処理システムにおいて、該クライアント端末、該ワーカ、該プライマリサーバ、該バックアップサーバをクライアントとし、該複数のロックサーバのうちのいずれかをマスタとするメッセージキュー管理方法であって、
   前記クライアントは、
   全てのマスタ候補となる前記ロックサーバに対して接続要求を送信し、該マスタ候補からセッションＩＤを取得し、該セッションＩＤに対するキュー操作要求を行うステップと、
   前記セッションＩＤの送信元の該マスタ候補から所定の時間内にメッセージを受信できない場合には、全てのマスタ候補に該セッションＩＤを送信することにより再接続要求を送信するステップと、を行い、
   前記ロックサーバは、
   マスタは常に一台であることを保証する多数決プロトコルであるPaxosを用いて自装置がマスタか否かを判定するマスタ調整ステップと、
   前記マスタ調整ステップの結果、マスタが交代した場合には、前記データベース内に予め複製されていたキューの情報及び前記クライアントからの再接続要求によって有効なセッションの確認を行い、キューに対する操作の途中状態を復元し、自装置がマスタになれば非マスタにデータ複製を要求し、自装置がマスタでなければマスタからのデータ復元要求に応じて、自装置内にデータを複製するレプリケーションステップと、
   を行い、
   前記レプリケーションステップにおいて、
   前記自装置が以前マスタではなかった場合は、
   セッション情報を格納したセッション情報記憶手段からマスタ交代前のセッション情報を読み込んで、削除待ちのセッション情報を格納した削除待ちセッション記憶手段に格納し、該セッション情報記憶手段のセッション情報を削除し、所定の時間が経過後、該削除待ちセッション記憶手段にセッションがある場合には、該削除待ちセッション記憶手段からセッションＩＤを取得し、前記データベースの該セッションＩＤに該当するクライントが保持していたキューの途中状態を無効化する第１のセッション制御ステップと、
   前記クライアントからの接続要求に対しては、セッションＩＤを発行し、前記セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信し、
   該クライアントからの再接続要求に対しては、前記削除待ちセッション情報記憶手段から該再接続要求に該当するセッションＩＤを削除し、該セッションＩＤを該セッション情報記憶手段に追加し、該セッションＩＤを該クライアントに送信し、
   該クライアントからの要求が該接続要求及び該再接続要求以外であれば、要求内容に応じて前記データベース内のキューに対する処理を行い、他の前記ロックサーバに送信する第２のセッション制御ステップと、
   を含むことを特徴とするメッセージキュー管理方法。
6. 前記第２のセッション制御ステップにおいて、
   前記クライアントからの要求がキューのプッシュ操作要求である場合は、取得したキューＩＤ、キー、及びキー値を用いて前記データベースのキューに対してプッシュ操作を行い、
   前記クライアントからの要求がキューのポップ操作要求である場合は、取得したキューＩＤに基づいて前記データベースのキューについてポップ操作を行い、
   前記クライアントからの要求が削除要求である場合は、取得したキューＩＤ、キーを用いて前記データベースのキューについて削除操作を行い、
   前記クライアントからの要求が、キューに対する操作の途中状態の復元のための要求であるマーク要求である場合は、キューＩＤとセッションＩＤを取得し、前記データベースから該キューＩＤに該当するキューの先頭レコードを取得し、該レコードにセッションＩＤが設定されていなければ、取得した該セッションＩＤを設定するマーク操作を行い、
   前記クライアントからの要求が、キューに対する途中状態を復元しない要求であるアンマーク要求である場合は、キューＩＤとキーを取得し、前記データベースから該キューＩＤに該当するレコード一覧から該キーに対応するレコードを取得して、該レコードのセッションＩＤを削除するアンマーク操作を行う、
   請求項５記載のメッセージキュー管理方法。
7. 請求項３または４に記載のロックサーバを構成する各手段としてコンピュータを機能させるためのメッセージキュー管理プログラム。

Images