JP2018142129A - 情報処理システム、情報処理方法、及び情報処理装置 - Google Patents

Abstract

【課題】データの整合性を保つまでの時間を短くできる情報処理システムを提供する。【解決手段】情報処理システムは、複数のノードでデータを同期する情報処理システムであって、前記複数のノードの各々は、いずれも共通の分散アルゴリズムに基づいて、前記複数のノードの中から前記データの配信に責任を負ういずれかのノードを決定し、決定した前記いずれかのノードを特定する情報を前記いずれかのノード以外の残りのノードに配信する、処理を実行する処理部を有する。【選択図】図３

Description

本件は、情報処理システム、情報処理方法、及び情報処理装置に関する。

無線によって互いに通信可能な複数の通信端末（以下、ノードという）間でデータを共有するシステムが知られている。このようなシステムの一種として、サーバを使用せずに、個々のノードで分散的にデータを共有するシステムが知られている（以上、特許文献１参照）。

また、このようなシステムにおいて、サーバを使用せずに、複数のノードの中から、データの配信に責任を負う代表のノードを選任するElection algorithm（以下、選任アルゴリズムと記載）も知られている。例えば、このような選任アルゴリズムとして、Bully algorithm（ブリーアルゴリズム）やRing algorithm（リングアルゴリズム）などが知られている。

国際公開第２０１４／１２８８０７号

しかしながら、上述した選任アルゴリズムは個々のノードと合意を得てから代表のノードを選任する。より詳細には、選任アルゴリズムはどのノードがデータの配信に責任を負うのかシステムに参加する全ノードの合意を得てから代表のノードを選任する。このため、代表のノードを選任するまでに大量の通信が発生する。また、無線通信環境下ではノードは自由に移動することができるため、ノード間の通信状態は刻々と変化し、安定した通信状態が維持されにくい。このような安定した通信状態が維持されにくい状況下で、ノードのシステムへの新規加入やノードのシステムからの離脱が頻繁に発生すると、代表のノードの選任に多大な時間を要する可能性もある。代表のノードの選任が遅れるとデータの配信が遅れ、データが複数のノード間で整合するまでに時間がかかるという問題がある。

そこで、１つの側面では、データの整合性を保つまでの時間を短くできる情報処理システム、情報処理方法、及び情報処理装置を提供することを目的とする。

１つの実施態様では、情報処理システムは、複数のノードでデータを同期する情報処理システムであって、前記複数のノードの各々は、いずれも共通の分散アルゴリズムに基づいて、前記複数のノードの中から前記データの配信に責任を負ういずれかのノードを決定し、決定した前記いずれかのノードを特定する情報を前記いずれかのノード以外の残りのノードに配信する、処理を実行する処理部を有する。

データの整合性を保つまでの時間を短くすることができる。

図１は情報処理システムの一例を説明するための図である。 図２はノードのハードウェア構成の一例である。 図３はノードのブロック図の一例である。 図４はデータ記憶部の一例である。 図５は配信者情報記憶部の一例である。 図６は引継情報記憶部の一例である。 図７はデータ更新時の処理の一例を示すフローチャートである。 図８はデータ受信時の処理の一例を示すフローチャートである。 図９は引継情報受信時の処理の一例を示すフローチャート（その１）である。 図１０は引継情報受信時の処理の一例を示すフローチャート（その２）である。 図１１は離脱検出時の処理の一例を示すフローチャートである。 図１２は引継依頼受信時の処理の一例を示すフローチャートである。 図１３は加入検出時の処理の一例を示すフローチャートである。

以下、本件を実施するための形態について図面を参照して説明する。

図１は情報処理システムＳの一例を説明するための図である。情報処理システムＳはEventual Consistency（結果整合性）を実現するコンピュータシステムである。情報処理システムＳはそれぞれ情報処理装置としての複数のノード１００，２００，３００，４００を含んでいる。特に、ノード４００は表示装置４１０と表示装置４１０を制御する制御装置４２０を含んでいる。

ノード１００，２００，３００，４００は無線基地局（例えばアクセスポイント）ＡＰを含む通信ネットワークＮＷを介して互いに接続されている。図１に示すように、通信ネットワークＮＷは有線ネットワークＮＷ１及び無線ネットワークＮＷ２を含んでいる。このため、ノード１００，２００，３００，４００は互いに無線や有線を利用して通信することができる。したがって、情報処理システムＳは、例えばノード１００，２００，３００，４００のそれぞれに表示されたドキュメントや設計図を操作によりどのノード１００，２００，３００，４００からでも共同編集することができる。尚、ノード１００，２００，３００間では無線基地局ＡＰを介さないアドホックネットワークが利用されていてもよい。

ここで、ノード１００，２００，３００，４００としては例えば端末装置やスマートデバイスなどがある。端末装置としては、例えば携帯型（モバイルタイプ）のPersonal Computer（ＰＣ）や据置型（デスクトップタイプ）のＰＣなどがある。スマートデバイスとしては、例えばスマートフォン、スマートウォッチ、タブレット端末、ウェアラブルコンピュータなどがある。尚、ノード１００，２００，３００，４００は端末装置やスマートデバイスに限定されず、表示機能及び通信機能を備えていれば、例えばスマートテレビ、電子レンジ、ヘルスケア用品といった家庭用の電気機器のほか、デジタルカメラや携帯ゲーム機などであってもよい。ノード１００，２００，３００，４００はキー（Ｋｅｙ）と呼ばれる同じ識別情報を含むデータを互いに送信し合うことによってデータを共有する。

次に、図２を参照して、ノード１００のハードウェア構成について説明する。尚、上述したノード２００，３００，４００については基本的にノード１００と同様のハードウェア構成であるため説明を省略する。

図２はノード１００のハードウェア構成の一例である。図２に示すように、ノード１００は、少なくともCentral Processing Unit（ＣＰＵ）１００Ａ、Random Access Memory（ＲＡＭ）１００Ｂ、Read Only Memory（ＲＯＭ）１００Ｃ、ネットワークＩ／Ｆ（インタフェース）１００Ｄ、及び通信回路１００Ｋを含んでいる。通信回路１００Ｋにはアンテナ１００Ｋ´が接続されている。通信回路１００Ｋに代えて通信機能を実現するＣＰＵが利用されてもよい。ノード１００は、通信回路１００Ｋ及びアンテナ１００Ｋ´を介してノード２００，３００と接続される。

また、ノード１００は、入力部１００Ｆ及び表示部１００Ｇも含んでいる。入力部１００Ｆとしては、例えばキーボード、ポインティングデバイス、タッチパネルなどがある。表示部１００Ｇとしては、例えば液晶ディスプレイがある。さらに、ノード１００は、必要に応じて、Hard Disk Drive（ＨＤＤ）１００Ｅ、入出力Ｉ／Ｆ１００Ｈ、ドライブ装置１００Ｉの少なくとも１つを含んでいてもよい。ＣＰＵ１００Ａからドライブ装置１００Ｉ及び通信回路１００Ｋは、内部バス１００Ｊによって互いに接続されている。少なくともＣＰＵ１００ＡとＲＡＭ１００Ｂとが協働することによってコンピュータが実現される。

入出力Ｉ／Ｆ１００Ｈには、半導体メモリ７３０が接続される。半導体メモリ７３０としては、例えばUniversal Serial Bus（ＵＳＢ）メモリやフラッシュメモリなどがある。入出力Ｉ／Ｆ１００Ｈは、半導体メモリ７３０に記憶されたプログラムやデータを読み取る。入出力Ｉ／Ｆ１００Ｈは、例えばＵＳＢポートを備えている。

ドライブ装置１００Ｉには、可搬型記録媒体７４０が挿入される。可搬型記録媒体７４０としては、例えばCompact Disc（ＣＤ）−ＲＯＭ、Digital Versatile Disc（ＤＶＤ）といったリムーバブルディスクがある。ドライブ装置１００Ｉは、可搬型記録媒体７４０に記録されたプログラムやデータを読み込む。
ネットワークＩ／Ｆ１００Ｄは、例えばLocal Area Network（ＬＡＮ）ポートを備えている。

上述したＲＡＭ１００Ｂには、ＨＤＤ１００Ｅに記憶されたプログラムがＣＰＵ１００Ａによって格納される。ＲＡＭ１００Ｂには、可搬型記録媒体７４０に記録されたプログラムがＣＰＵ１００Ａによって格納される。格納されたプログラムをＣＰＵ１００Ａが実行することにより、後述する各種の機能が実現され、また、後述する各種の動作が実行される。尚、プログラムは後述するフローチャートに応じたものとすればよい。

次に、図３を参照して、ノード１００の機能構成について説明する。尚、上述したノード２００，３００，４００については基本的にノード１００と同様のハ機能構成であるため説明を省略する。

図３はノード１００のブロック図の一例である。図４はデータ記憶部１３２の一例である。図５は配信者情報記憶部１３５の一例である。図６は引継情報記憶部１３７の一例である。図３に示すように、ノード１００はアプリ１１０、通信部１２０、及びミドルウェア１３０を備えている。

アプリ１１０は、ノード１００で動作する分散アプリケーションである。分散アプリケーションは例えばHyper Text Transfer Protocol（ＨＴＭＬ）といった特定のマークアップ言語で記述されており、種々のデータを操作する。分散アプリケーションとしては例えば画面共有アプリなどがある。
通信部１２０は、ノード１００とノード２００，３００，４００との通信を制御する。例えば、通信部１２０はノード２００，３００，４００の少なくとも１つを指定してアプリ１１０で操作されたデータを送信する。例えば、通信部１２０は情報処理システムＳに加入する新たなノード（不図示）や情報処理システムＳから離脱するノード（例えばノード３００）をミドルウェア１３０に通知する。

ミドルウェア１３０は、アプリ１１０によりデータが操作されると、その操作をノード２００，３００，４００が備えるミドルウェア（不図示）と通知しあう。また、ミドルウェア１３０は、通信状態が安定していない場合や、ノード数が増加した場合に、通知するデータ操作の通信量が通信能力を超えると判断すると、その操作の通知を停止する。その他、ミドルウェア１３０は、種々の処理を実行する。

より詳しく説明すると、ミドルウェア１３０は、図３に示すように、入出力部１３１、データ記憶部１３２、データ配信管理部１３３、及びデータ送受信部１３４を含んでいる。特に、データ送受信部１３４はデータ配信部１３４Ａとデータ受信部１３４Ｂを含んでいる。また、ミドルウェア１３０は、配信者情報記憶部１３５、責任ノード決定部１３６、引継情報記憶部１３７、及びノード検出部１３８を含んでいる。さらに、ミドルウェア１３０は、配信責任管理部１３９、情報送受信部１４０、不整合解消部１４１を含んでいる。特に、情報送受信部１４０は引継情報配信部１４０Ａと引継情報受信部１４０Ｂを含んでいる。

入出力部１３１はアプリ１１０とミドルウェア１３０とのインタフェースである。入出力部１３１はアプリ１１０によりデータの操作が行われると、データ記憶部１３２を更新する。例えば、入出力部１３１はアプリ１１０によりデータを書き込む操作が行われると、アプリ１１０からのデータを受け付けて、データ記憶部１３２に同じキーのデータが存在しなければ、受け付けたデータをデータ記憶部１３２に書き込む。これにより、データ記憶部１３２は、ノード１００の通信先であるノード２００，３００，４００と共有するデータを記憶する。また、入出力部１３１はアプリ１１０によるデータの操作をデータ配信管理部１３３に出力する。さらに、入出力部１３１はデータ記憶部１３２を監視し、データ記憶部１３２がノード２００，３００，４００から受信したデータに基づいて更新されると、アプリ１１０に更新を通知する。

ここで、図４に示すように、データ記憶部１３２は入出力部１３１が書き込んだデータをデータテーブルＴ１により管理する。各データはそれぞれKey（キー）とValue（バリュー：値）とバージョンを構成要素として含んでいる。キーはデータを識別する識別情報である。バージョンは例えばLamport clock（ランポートクロック）といった論理クロック（又は論理時刻）である。論理クロックとしてベクタークロックやOperating System（ＯＳ）のシステムクロックが利用されてもよい。尚、図４においてデータはキー・バリュー型で示されているが、必ずしもキー・バリュー型に限定されない。

データ配信管理部１３３は入出力部１３１から出力されたデータ操作を受け付けると、データ操作を受け付けた旨を配信責任管理部１３９に通知する。また、データ配信管理部１３３はデータ操作を受け付けると、データ記憶部１３２からデータを取得し、取得したデータをデータ送受信部１３４に出力する。より詳しくは、データ配信管理部１３３は取得したデータをデータ配信部１３４Ａに出力する。さらに、データ配信管理部１３３はデータ送受信部１３４から出力されたデータを受信すると、データ記憶部１３２を更新する。例えば、データ配信管理部１３３はデータ受信部１３４Ｂから出力されたデータを受信すると、データ記憶部１３２に同じキーのデータが存在しなければ、受け付けたデータをデータ記憶部１３２に書き込む。

データ配信部１３４Ａはデータ配信管理部１３３から出力されたデータを、通信部１２０を介してノード２００，３００，４００に配信する。一方、データ受信部１３４Ｂは、ノード２００，３００，４００からそれぞれ配信されたデータを、通信部１２０を介して受信する。

配信者情報記憶部１３５は配信者情報を記憶する。より詳しくは、図５に示すように、配信者情報記憶部１３５は配信者情報を配信者情報テーブルＴ２により管理する。各配信者情報はそれぞれキーと配信責任ノードＩＤを構成要素として含んでいる。配信責任ノードＩＤはデータの配信責任を負うノード１００，２００，３００，４００の識別情報である。例えば、キー「Ｘ」のデータはノードＩＤ「Ｎ１」が割り当てられたノード（例えばノード２００）が配信責任を負うことを示している。このように、配信責任ノードＩＤはキーと関連付けられている。配信責任管理部１３９は、配信者情報を確認することによりデータの配信責任をノード１００，２００，３００，４００のいずれが負うのかを把握することができる。

責任ノード決定部１３６は配信責任管理部１３９が引継情報記憶部１３７を更新すると、特定の分散アルゴリズムに基づいて、ノード１００，２００，３００，４００の中からデータの配信に責任を負うノード１００，２００，３００，４００のいずれかを配信責任ノードとして決定する。特定の分散アルゴリズムとしては、コンシステントハッシュ法などが利用される。尚、ノード２００，３００，４００が備える責任ノード決定部（不図示）も責任ノード決定部１３６が利用する特定の分散アルゴリズムと共通の（又は同一の若しくは特徴が同じ）分散アルゴリズムを使用して配信責任ノードを決定する。

引継情報記憶部１３７はノード２００，３００，４００のいずれかが情報処理システムＳから離脱し、離脱したノード（例えばノード３００）が配信責任ノードである場合、離脱したノードの配信責任を他のノード（例えばノード１００，２００，４００）に引き継ぐための引継情報を記憶する。より詳しくは、図６に示すように、引継情報記憶部１３７は引継情報を引継情報テーブルＴ３により管理する。各引継情報はそれぞれ引継情報ＩＤ、引継ノードＩＤ、キー及びバージョンを構成要素として含んでいる。引継情報ＩＤは引継情報を識別する識別情報である。引継ノードＩＤは配信責任を引き継ぐ先のノードを識別する識別情報である。このように、たとえノード３００が情報処理システムＳから離脱しても、引継情報により配信責任は情報処理システムＳに残存するノード１００，２００，４００のいずれかに引き継がれる。

ノード検出部１３８は通信部１２０からの通知に基づいて、新たなノード（不図示）の情報処理システムＳへの加入を検出する。また、ノード検出部１３８は通信部１２０からの通知に基づいて、ノード（例えばノード２００，３００，４００の少なくともいずれか）の情報処理システムＳからの離脱を検出する。ノード検出部１３８はノードの加入及び離脱を検出すると、ノードの加入及び離脱を配信責任管理部１３９に通知する。

配信責任管理部１３９はデータ配信管理部１３３からデータの操作が通知されると、責任ノード決定部１３６、情報送受信部１４０、不整合解消部１４１の動作を制御する。例えば、配信責任管理部１３９はデータ配信管理部１３３からデータの操作が通知されると、配信者情報記憶部１３５を更新する。その他、配信責任管理部１３９は種々の情報処理を実行する。

引継情報配信部１４０Ａは通信部１２０を介して、ノード２００，３００，４００に引継情報を配信する。引継情報受信部１４０Ｂは通信部１２０を介して、ノード２００，３００，４００から配信された引継情報を受信する。引継情報受信部１４０Ｂは引継情報を受信すると、配信責任管理部１３９に出力する。

不整合解消部１４１は引継情報記憶部１３７を更新することによりノード１００，２００，３００，４００の合意に関する不整合を解消する。例えば、不整合解消部１４１は配信責任管理部１３９がデータ配信管理部１３３からアプリ１１０によるデータの操作が通知されると、引継情報を削除することにより不整合を解消する。例えば、不整合解消部１４１は配信責任管理部１３９が引継情報受信部１４０Ｂから出力された引継情報を受け付けると、必要に応じて引継情報を削除することにより不整合を解消する。

続いて、図７から図１３を参照して、ノード１００の動作について説明する。尚、ノード２００，３００，４００もノード１００の動作と同様であるため、説明を省略する。

図７はデータ更新時の処理の一例を示すフローチャートである。より詳しくは、図７はアプリ１１０がデータを操作した際に実行される処理を表している。

まず、アプリ１１０がデータを操作すると、入出力部１３１はアプリ１１０からのデータを受け付ける（ステップＳ１０１）。ステップＳ１０１の処理が完了すると、次いで、入出力部１３１はデータを更新する（ステップＳ１０２）。より詳しくは、入出力部１３１はデータ記憶部１３２にアクセスし、データ記憶部１３２に受け付けたデータのキーと同じキーのデータが存在しなければ、データ記憶部１３２に受け付けたデータを書き込む。逆に、データ記憶部１３２に受け付けたデータのキーと同じキーのデータが存在すれば、入出力部１３１はバージョンを確認し、バージョンが古ければ、受け付けたデータを上書きする。尚、入出力部１３１はデータの書き込み時及び上書き時にデータにバージョンを付与する。

ステップＳ１０２の処理が完了すると、次いで、配信責任管理部１３９は該当キーを自ノードが引き継いでいるか否かを判断する（ステップＳ１０３）。より詳しくは、配信責任管理部１３９はデータ配信管理部１３３からデータの操作が通知されると、引継情報記憶部１３７にアクセスし、操作されたデータのキーの引継ノードＩＤが自ノードに割り当てられたノードＩＤであるか否かを判断する。該当キーを自ノードが引き継いでいる場合（ステップＳ１０３：ＹＥＳ）、不整合解消部１４１は該当キーの引継情報を削除する（ステップＳ１０４）。すなわち、アプリ１１０で操作されたデータの配信責任は自ノード（すなわち、ノード１００）が負うため、該当キーの引継情報を保持する必要がない。したがって、不整合解消部１４１は該当キーの引継情報を削除する。

ステップＳ１０４の処理が完了すると、引継情報配信部１４０Ａは残存する引継情報を配信する（ステップＳ１０５）。より詳しくは、配信責任管理部１３９は該当キーの引継情報を削除した後に引継情報記憶部１３７に残存する引継情報を取得して引継情報配信部１４０Ａに出力し、引継情報配信部１４０Ａは配信責任管理部１３９から出力された引継情報を配信する。これにより、配信された引継情報を受信したノード２００，３００，４００は自身が保持する引継情報を更新する。したがって、ノード１００，２００，３００，４００がそれぞれ保持する引継情報が同期する。尚、引継情報配信部１４０Ａは引継情報を削除した旨を表す情報を配信してもよい。

ステップＳ１０５の処理が完了した場合、又は、配信責任管理部１３９が該当キーの引継情報を保持していないと判断した場合（ステップＳ１０３：ＮＯ）、次いで、配信責任管理部１３９は該当キーの配信者情報を自ノードに更新する（ステップＳ１０６）。したがって、アプリ１１０がデータの操作を行うと、その該当キーのデータの配信責任はアプリ１１０を含むノード（例えばノード１００）が負うことが特定される。

ステップＳ１０６の処理が完了すると、データ配信部１３４Ａはデータを配信し（ステップＳ１０７）、処理を終了する。より詳しくは、データ配信管理部１３３はデータ記憶部１３２からデータを取得してデータ配信部１３４Ａに出力し、データ配信部１３４Ａはデータ配信管理部１３３から出力されたデータを配信して、処理を終了する。これにより、ノード２００，３００，４００はノード１００から配信されたデータを受信することができる。

図８はデータ受信時の処理の一例を示すフローチャートである。より詳しくは、図８はデータ受信部１３４Ｂがデータを受信した際に実行される処理を表している。

まず、データ受信部１３４Ｂはデータを受信する（ステップＳ２０１）。例えば、データ受信部１３４Ｂはノード１００以外のノード（例えばノード２００）が配信したデータを受信する。ステップＳ２０１の処理が完了すると、データ配信管理部１３３はデータを更新する（ステップＳ２０２）。より詳しくは、データ受信部１３４Ｂがデータを受信すると、データ受信部１３４Ｂはデータをデータ配信管理部１３３に出力する。したがって、データ配信管理部１３３はデータ受信部１３４Ｂから出力されたデータを受け付けて、データ記憶部１３２にデータを書き込んだり、キーとバージョンとに基づいてデータ記憶部１３２に記憶されたデータを上書きしたりする。

ステップＳ２０２の処理が完了すると、次いで、入出力部１３１はアプリ１１０に更新を通知する（ステップＳ２０３）。より詳しくは、入出力部１３１はデータ記憶部１３２を監視し、データ記憶部１３２が更新されると、入出力部１３１はアプリ１１０に更新を通知する。

ステップＳ２０３の処理が完了すると、次いで、配信責任管理部１３９は自ノードが配信責任を負うか否かを判断する（ステップＳ２０４）。より詳しくは、配信責任管理部１３９はデータ配信管理部１３３からの通知に基づいて配信者情報記憶部１３５にアクセスし、受信したデータのキーに応じて自ノードが配信責任を負っているか否かを判断する。ここで、自ノードが配信責任を負っている場合（ステップＳ２０４：ＹＥＳ）、配信責任管理部１３９は配信責任を停止する（ステップＳ２０５）。例えば、配信責任管理部１３９は、該当の配信者情報を削除することにより、配信責任を停止する。すなわち、ノード２００が備えるアプリ（不図示）によるデータの操作に基づいてノード２００からデータが配信された場合、ノード２００が配信責任を負い、ノード１００は配信責任を負わない。したがって、自ノード（例えばノード１００）が配信責任を負っている場合、配信責任管理部１３９は配信責任を停止する。

一方、自ノードが配信責任を負っていない場合（ステップＳ２０４：ＮＯ）、次いで、配信責任管理部１３９は該当キーを自ノードが引き継いでいるか否かを判断する（ステップＳ２０６）。より詳しくは、配信責任管理部１３９はデータ配信管理部１３３からデータの受信が通知されると、引継情報記憶部１３７にアクセスし、受信したデータのキーの引継ノードＩＤが自ノードに割り当てられたノードＩＤであるか否かを判断する。該当キーを自ノードが引き継いでいる場合（ステップＳ２０６：ＹＥＳ）、不整合解消部１４１は該当キーの引継情報を削除する（ステップＳ２０７）。すなわち、ノード２００のアプリ（不図示）で操作されたデータの配信責任はノード２００が負うため、該当キーの引継情報を保持する必要がない。したがって、不整合解消部１４１は該当キーの引継情報を削除する。

ステップＳ２０７の処理が完了すると、引継情報配信部１４０Ａは残存する引継情報を配信する（ステップＳ２０８）。より詳しくは、配信責任管理部１３９は該当キーの引継情報を削除した後に引継情報記憶部１３７に残存する引継情報を取得して引継情報配信部１４０Ａに出力し、引継情報配信部１４０Ａは配信責任管理部１３９から出力された引継情報を配信する。これにより、配信された引継情報を受信したノード２００，３００，４００は自身の引継情報を更新する。したがって、ノード１００，２００，３００，４００がそれぞれ保持する引継情報が同期する。尚、該当キーを自ノードが引き継いでいない場合（ステップＳ２０６：ＮＯ）、不整合解消部１４１はステップＳ２０７の処理をスキップし、引継情報配信部１４０ＡはステップＳ２０８の処理をスキップして、処理を終了する。

図９は引継情報受信時の処理の一例を示すフローチャート（その１）である。図１０は引継情報受信時の処理の一例を示すフローチャート（その２）である。より詳しくは、図９及び図１０は引継情報受信部１４０Ｂが引継情報を受信した際に実行される処理を表している。

まず、引継情報受信部１４０Ｂは引継情報を受信する（ステップＳ３０１）。例えば、引継情報受信部１４０Ｂはノード１００以外のノード（例えばノード２００）が配信した引継情報を受信する。ステップＳ３０１の処理が完了すると、配信責任管理部１３９は引継情報を更新する（ステップＳ３０２）。より詳しくは、引継情報受信部１４０Ｂが引継情報を受信すると、引継情報受信部１４０Ｂは引継情報を配信責任管理部１３９に出力する。したがって、配信責任管理部１３９は引継情報受信部１４０Ｂから出力された引継情報を受け付けて、引継情報記憶部１３７に引継情報を書き込んだり、キーとバージョンとに基づいてデータ記憶部１３２に記憶されたデータを上書きしたりする。これにより、ノード１００，２００，３００，４００間の引継情報が同期する。

ステップＳ３０２の処理が完了すると、次いで、配信責任管理部１３９は該当キーを自ノードが引き継いでいるか否かを判断する（ステップＳ３０３）。より詳しくは、配信責任管理部１３９は引継情報受信部１４０Ｂから出力された引継情報を受け付けると、引継情報記憶部１３７にアクセスし、引継情報に含まれるキーの引継ノードＩＤが自ノードに割り当てられたＩＤであるか否かを判断する。該当キーを自ノードが引き継いでいる場合（ステップＳ３０３：ＹＥＳ）、責任ノード決定部１３６は配信責任ノードを決定する（ステップＳ３０４）。すなわち、責任ノード決定部１３６は自ノード（例えばノード１００）が配信責任を負うか他ノード（例えばノード２００，３００，４００）が配信責任を負うかを判断する。

責任ノード決定部１３６が決定した配信責任ノードが自ノードである場合（ステップＳ３０５：ＹＥＳ）、配信責任管理部１３９は自ノードが保持するデータの該当キーのバージョンを確認する（ステップＳ３０６）。より詳しくは、責任ノード決定部１３６が配信責任ノードを決定すると、配信責任管理部１３９はデータ配信管理部１３３を介して該当キーのバージョンを確認する。

ステップＳ３０６の処理が完了すると、次いで、配信責任管理部１３９はデータが古いか否かを判断する（ステップＳ３０７）。より詳しくは、配信責任管理部１３９は該当キーの引継情報のバージョンと自ノードが保持するデータの該当キーのバージョンとを比較して、データが古いか否かを判断する。比較した結果、自ノードが保持するデータの該当キーのバージョンが引継情報のバージョンより小さければ、データが古いため（ステップＳ３０７：ＹＥＳ）、配信責任管理部１３９は最新データの配信を該当ノードに依頼し（ステップＳ３０８）、処理を終了する。すなわち、配信責任管理部１３９は最新データの配信を配信責任ノードに依頼し、処理を終了する。これにより、複数のノード１００，２００，３００，４００間でデータが同期していないという不整合が解消する。一方、比較した結果、自ノードが保持するデータの該当キーのバージョンが引継情報のバージョンより大きければ、データが新しいため（ステップＳ３０７：ＮＯ）、配信責任管理部１３９はステップＳ３０８の処理をスキップする。

一方、ステップＳ３０５の処理において、責任ノード決定部１３６が決定した配信責任ノードが自ノードでない場合（ステップＳ３０５：ＮＯ）、図１０に示すように、配信責任管理部１３９は他ノードが該当キーを引き継ぐ引継情報が存在するか否かを判断する（ステップＳ３０９）。より詳しくは、責任ノード決定部１３６が決定した配信責任ノードが他ノードである場合、配信責任管理部１３９は引継情報記憶部１３７を確認し、他ノードが該当キーを引き継ぐ引継情報が存在するか否かを判断する。

他ノードが該当キーを引き継ぐ引継情報が存在する場合（ステップＳ３０９：ＹＥＳ）、不整合解消部１４１は該当キーの引継情報を削除する（ステップＳ３１０）。すなわち、他ノード（例えばノード２００）が配信責任を負うため、該当キーの引継情報を保持する必要がない。したがって、不整合解消部１４１は該当キーの引継情報を削除する。

ステップＳ３１０の処理が完了すると、引継情報配信部１４０Ａは残存する引継情報を配信する（ステップＳ３１１）。より詳しくは、配信責任管理部１３９は該当キーの引継情報を削除した後に引継情報記憶部１３７に残存する引継情報を取得して引継情報配信部１４０Ａに出力し、引継情報配信部１４０Ａは配信責任管理部１３９から出力された引継情報を配信する。これにより、配信された引継情報を受信したノード２００，３００，４００は自身の引継情報を更新する。したがって、ノード１００，２００，３００，４００がそれぞれ保持する引継情報が同期する。尚、他ノードが該当キーを引き継ぐ引継情報が存在しない場合（ステップＳ３０９：ＮＯ）、又は、ステップＳ３０３の処理において、該当キーを自ノードが引き継いでいない場合（ステップＳ３０３：ＮＯ）、不整合解消部１４１はステップＳ３１０の処理をスキップし、引継情報配信部１４０ＡはステップＳ３１１の処理をスキップする。

ステップＳ３１１の処理が完了した場合、又は、ステップＳ３１０，Ｓ３１１の処理がスキップされた場合、配信責任管理部１３９は自ノードが保持するデータの該当キーのバージョンを確認する（ステップＳ３１２）。より詳しくは、責任ノード決定部１３６が配信責任ノードを決定すると、配信責任管理部１３９はデータ配信管理部１３３を介して該当キーのバージョンを確認する。

ステップＳ３１２の処理が完了すると、次いで、配信責任管理部１３９はデータが新しいか否かを判断する（ステップＳ３１３）。より詳しくは、配信責任管理部１３９は該当キーの引継情報のバージョンと自ノードが保持するデータの該当キーのバージョンとを比較して、データが新しいか否かを判断する。比較した結果、自ノードが保持するデータの該当キーのバージョンが引継情報のバージョンより大きければ、データが新しいため（ステップＳ３１３：ＹＥＳ）、配信責任管理部１３９は最新のデータを該当ノードに配信する（ステップＳ３１４）。すなわち、配信責任管理部１３９はデータ配信部１３４Ａを通じて、最新のデータをノード２００，３００，４００に配信する。これにより、データが同期していないという不整合が解消する。一方、比較した結果、自ノードが保持するデータの該当キーのバージョンが引継情報のバージョンより小さければ、データが古いため（ステップＳ３１３：ＮＯ）、図９に示すように、配信責任管理部１３９は処理を終える。

図１１は離脱検出時の処理の一例を示すフローチャートである。より詳しくは、図１１はノード検出部１３８がノード（例えばノード３００）の離脱を検出した際に実行される処理を表している。

例えばノード３００が情報処理システムＳから離脱すると、ノード検出部１３８はノード３００の離脱を検出する（ステップＳ４０１）。より詳しくは、ノード３００は離脱を通知し、通信部１２０は当該通知を受け付けると、ノード検出部１３８にノード３００の離脱を通知する。これにより、ノード検出部１３８はノード３００の離脱を検出する。

ステップＳ４０１の処理が完了すると、次いで、配信責任管理部１３９は離脱したノードが配信していたキーを把握する（ステップＳ４０２）。例えば、ノード検出部１３８がノード３００の離脱を検出すると、配信責任管理部１３９は配信者情報記憶部１３５及び引継情報記憶部１３７にアクセスし、配信者情報及び引継情報に基づいて、離脱したノード３００が配信していたデータのキーを把握する。

ステップＳ４０２の処理が完了すると、次いで、配信責任管理部１３９は後続の処理が未済のキーを選択し（ステップＳ４０３）、後続の処理が未済のキーがなくなるまでループ処理を行う。ステップＳ４０３の処理において、配信責任管理部１３９がいずれかのキーを選択すると、責任ノード決定部１３６は配信責任ノードを決定する（ステップＳ４０４）。より詳しくは、責任ノード決定部１３６は配信責任管理部１３９が選択したキーの配信責任ノードを決定する。

ここで、責任ノード決定部１３６が決定した配信責任ノードが自ノードである場合（ステップＳ４０５：ＹＥＳ）、配信責任管理部１３９は選択したキーを自ノードが引き継ぐことを引継情報に書込み（ステップＳ４０６）、引継情報を配信する（ステップＳ４０７）。言い換えれば、選択したキーの配信責任者が自ノードであることが引継情報に書き込まれ、その引継情報が配信される。ステップＳ４０７の処理が完了すると、ステップＳ４０３に戻って、配信責任管理部１３９は後続の処理が未済の別のキーを選択し、ステップＳ４０４からＳ４０７までの処理を繰り返す。これにより、自ノード（例えばノード１００）が配信責任を負う全てキーが特定され、特定されたキーを自ノードが引き継いだことが引継情報により他ノード（例えばノード２００，４００）に配信される。ステップＳ４０７の処理が完了すると、データ配信部１３４Ａはデータの配信を開始し（ステップＳ４０８）、処理を終了する。

一方、責任ノード決定部１３６が決定した配信責任ノードが自ノードでない場合（ステップＳ４０５：ＮＯ）、配信責任管理部１３９は引継依頼を送信する（ステップＳ４０９）。より詳しくは、決定した配信責任ノードによる引継情報の配信を所定の時間にわたり引継情報受信部１４０Ｂが受信しない場合に、配信責任管理部１３９は選択したキーとともに、責任ノード決定部１３６が決定した他ノード（例えばノード２００又はノード４００）に引継情報配信部１４０Ａを通じて引継依頼を送信する。尚、引継依頼は配信責任の引き継ぎを依頼する情報である。

ステップＳ４０９の処理が完了すると、配信責任管理部１３９は引継依頼と引継情報の内容を確認し（ステップＳ４１０）、引継依頼と引継情報の内容が一致するか否かを判断する（ステップＳ４１１）。配信責任管理部１３９は引継情報の共有により、他ノード（例えばノード２００又はノード４００）が引継依頼を受け入れたか否かを把握することができる。引継依頼と引継情報の内容が一致しない場合（ステップＳ４１１：ＮＯ）、配信責任管理部１３９はステップＳ４０９及びＳ４１０の処理を繰り返す。言い換えれば、引継依頼と引継情報の内容が一致するまで配信責任管理部１３９はステップＳ４０９及びＳ４１０の処理を繰り返す。一方、引継依頼と引継情報の内容が一致した場合（ステップＳ４１１：ＹＥＳ）、配信責任管理部１３９は処理を終了する。このように、配布責任ノードが一意に定まらない期間もデータの配信を継続して、ノード間（例えばノード１００，２００，４００間）のデータの整合性を保つことができる。

図１２は引継依頼受信時の処理の一例を示すフローチャートである。より詳しくは、図１２は配信責任管理部１３９が引継依頼を受信した際に実行される処理を表している。

配信責任管理部１３９は引継情報受信部１４０Ｂを介して引継依頼を受信すると（ステップＳ５０１）、責任ノード決定部１３６は配信責任ノードを決定する（ステップＳ５０２）。より詳しくは、責任ノード決定部１３６は配信責任管理部１３９が引継依頼とともに送信されたキーの配信責任ノードを決定する。

ここで、責任ノード決定部１３６が決定した配信責任ノードが自ノードでない場合（ステップＳ５０３：ＮＯ）、配信責任管理部１３９は引継情報が登録済であるか否かを判断する（ステップＳ５０４）。より詳しくは、配信責任管理部１３９は該当キーの引継情報が登録済であるか否かを判断する。引継情報が登録済である場合（ステップＳ５０４：ＹＥＳ）、又は、責任ノード決定部１３６が決定した配信責任ノードが自ノードである場合（ステップＳ５０３：ＹＥＳ）、データの配信を開始し（ステップＳ５０５）、処理を終了する。一方、引継情報が登録済でない場合（ステップＳ５０４：ＮＯ）、配信責任管理部１３９はステップＳ５０５の処理をスキップして処理を終了する。

図１３は加入検出時の処理の一例を示すフローチャートである。より詳しくは、図１３はノード検出部１３８がノード（不図示）の加入を検出した際に実行される処理を表している。

例えば新たなノード（不図示）が情報処理システムＳに加入すると、ノード検出部１３８はそのノードの加入を検出する（ステップＳ６０１）。より詳しくは、新たなノードがデータの配信を要求すると、通信部１２０は当該要求を受け付け、ノード検出部１３８に当該要求を通知する。これにより、ノード検出部１３８は新たなノードの加入を検出する。

ステップＳ６０１の処理が完了すると、次いで、配信責任管理部１３９は自ノードが該当キーの配信責任ノードであるか否かを判断する（ステップＳ６０２）。より詳しくは、配信責任管理部１３９は配信者情報記憶部１３５を確認して、自ノードが該当キーの配信責任ノードであるか否かを判断する。自ノードが該当キーの配信責任ノードでない場合（ステップＳ６０２：ＮＯ）、さらに、配信責任管理部１３９は自ノードが該当キーの引き継ぎを申告しているか否かを判断する（ステップＳ６０３）。より詳しくは、配信責任管理部１３９は引継情報記憶部１３７を確認して、自ノードが該当キーの配信責任を引き継ぎか否かを判断する。自ノードが該当キーの引き継ぎを申告している場合（ステップＳ６０３：ＹＥＳ）、又は、自ノードが該当キーの配信責任ノードである場合（ステップＳ６０２：ＹＥＳ）、データ配信部１３４Ａは新たに加入したノードに対して該当キーのデータを配信し（ステップＳ６０４）、処理を終了する。尚、自ノードが該当キーの引き継ぎを申告していない場合（ステップＳ６０３：ＮＯ）、配信責任管理部１３９はステップＳ６０４をスキップして処理を終了する。

以上、本実施形態に係る情報処理システムＳは複数のノード１００，２００，３００，４００でデータを同期する。複数のノード１００，２００，３００，４００の各々はいずれも同様のミドルウェアを備えており、例えばノード１００のミドルウェア１３０はノード２００，３００，４００と共通の分散アルゴリズムに基づいて、複数のノード１００，２００，３００，４００の中からデータの配信に責任を負う配信責任ノードを決定する。そして、当該ミドルウェア１３０は決定した配信決定ノードを特定する情報を配信決定ノード以外の残りのノードに配信する。これにより、配信責任ノードの選任が即時に決定されるため、データの配信が遅延せず、複数のノード１００，２００，３００，４００間でデータの整合性を保つまでの時間を短くすることができる。

以上、本発明の好ましい実施形態について詳述したが、本発明に係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。

なお、以上の説明に関して更に以下の付記を開示する。
（付記１）複数のノードでデータを同期する情報処理システムであって、前記複数のノードの各々は、いずれも共通の分散アルゴリズムに基づいて、前記複数のノードの中から前記データの配信に責任を負ういずれかのノードを決定し、決定した前記いずれかのノードを特定する情報を前記いずれかのノード以外の残りのノードに配信する、処理を実行する処理部を有する情報処理システム。
（付記２）前記処理部は、前記情報に基づき、前記複数のノードの中で前記責任を負うノードが重複する場合、前記分散アルゴリズムに基づいて、重複するノードの中からいずれか１つのノードを除いた残りのノードが負う前記責任を停止する、ことを特徴とする付記１に記載の情報処理システム。
（付記３）前記処理部は、決定した前記いずれかのノードが自ノード以外の他ノードである場合、前記他ノードに前記責任の引き継ぎを依頼する、ことを特徴とする付記１又は２に記載の情報処理システム。
（付記４）前記処理部は、決定した前記いずれかのノードによる前記情報の配信を所定の時間受信しない場合に、前記他ノードに前記引き継ぎを依頼する、ことを特徴とする付記３に記載の情報処理システム。
（付記５）前記処理部は、自ノードが保持するデータのバージョンが、配信した前記情報に含まれる前記データのバージョンより古い場合、前記情報を配信したノードにデータの送信を依頼し、自ノードが保持するデータのバージョンが、配信した前記情報に含まれる前記データのバージョンより新しい場合、前記情報を配信したノードにデータを送信する、ことを特徴とする付記１から４のいずれか１項に記載の情報処理システム。
（付記６）前記処理部は、前記複数のノードのいずれかの離脱を検出した場合、離脱したノードが配信するデータと離脱したノードが保持する前記情報に対して引き継ぎ先のノードを判定する、ことを特徴とする付記１から５のいずれか１項に記載の情報処理システム。
（付記７）複数のノードでデータを同期する情報処理方法であって、前記複数のノードの各コンピュータは、いずれも共通の分散アルゴリズムに基づいて、前記複数のノードの中から前記データの配信に責任を負ういずれかのノードを決定し、決定した前記いずれかのノードを特定する情報を前記いずれかのノード以外の残りのノードに配信する、処理を実行する情報処理方法。
（付記８）前記処理は、前記情報に基づき、前記複数のノードの中で前記責任を負うノードが重複する場合、前記分散アルゴリズムに基づいて、重複するノードの中からいずれか１つのノードを除いた残りのノードが負う前記責任を停止する、ことを特徴とする付記７に記載の情報処理方法。
（付記９）前記処理は、決定した前記いずれかのノードが自ノード以外の他ノードである場合、前記他ノードに前記責任の引き継ぎを依頼する、ことを特徴とする付記７又は８に記載の情報処理方法。
（付記１０）前記処理は、決定した前記いずれかのノードによる前記情報の配信を所定の時間受信しない場合に、前記他ノードに前記引き継ぎを依頼する、ことを特徴とする付記９に記載の情報処理方法。
（付記１１）前記処理は、自ノードが保持するデータのバージョンが、配信した前記情報に含まれる前記データのバージョンより古い場合、前記情報を配信したノードにデータの送信を依頼し、自ノードが保持するデータのバージョンが、配信した前記情報に含まれる前記データのバージョンより新しい場合、前記情報を配信したノードにデータを送信する、ことを特徴とする付記７から１０のいずれか１項に記載の情報処理方法。
（付記１２）前記処理は、前記複数のノードのいずれかの離脱を検出した場合、離脱したノードが配信するデータと離脱したノードが保持する前記情報に対して引き継ぎ先のノードを判定する、ことを特徴とする付記７から１１のいずれか１項に記載の情報処理方法。
（付記１３）互いにデータを同期する複数の情報処理装置の中のいずれかの情報処理装置であって、いずれも共通の分散アルゴリズムに基づいて、前記データの配信に責任を負ういずれかの情報処理装置を決定し、決定した前記いずれかの情報処理装置を特定する情報を前記いずれかの情報処理装置以外の残りの情報処理装置に配信する、処理を実行する処理部を有する情報処理装置。

Ｓ 情報処理システム
１００，２００，３００，４００ ノード
１３０ ミドルウェア
１３５ 配信者情報記憶部
１３６ 責任ノード決定部
１３７ 引継情報記憶部
１３８ ノード検出部
１３９ 配信責任管理部
１４０ 情報送受信部
１４１ 不整合解消部

Claims (8)

1. 複数のノードでデータを同期する情報処理システムであって、
   前記複数のノードの各々は、
   いずれも共通の分散アルゴリズムに基づいて、前記複数のノードの中から前記データの配信に責任を負ういずれかのノードを決定し、
   決定した前記いずれかのノードを特定する情報を前記いずれかのノード以外の残りのノードに配信する、
   処理を実行する処理部を有する情報処理システム。
2. 前記処理部は、前記情報に基づき、前記複数のノードの中で前記責任を負うノードが重複する場合、前記分散アルゴリズムに基づいて、重複するノードの中からいずれか１つのノードを除いた残りのノードが負う前記責任を停止する、
   ことを特徴とする請求項１に記載の情報処理システム。
3. 前記処理部は、決定した前記いずれかのノードが自ノード以外の他ノードである場合、前記他ノードに前記責任の引き継ぎを依頼する、
   ことを特徴とする請求項１又は２に記載の情報処理システム。
4. 前記処理部は、決定した前記いずれかのノードによる前記情報の配信を所定の時間受信しない場合に、前記他ノードに前記引き継ぎを依頼する、
   ことを特徴とする請求項３に記載の情報処理システム。
5. 前記処理部は、自ノードが保持するデータのバージョンが、配信した前記情報に含まれる前記データのバージョンより古い場合、前記情報を配信したノードにデータの送信を依頼し、自ノードが保持するデータのバージョンが、配信した前記情報に含まれる前記データのバージョンより新しい場合、前記情報を配信したノードにデータを送信する、
   ことを特徴とする請求項１から４のいずれか１項に記載の情報処理システム。
6. 前記処理部は、前記複数のノードのいずれかの離脱を検出した場合、離脱したノードが配信するデータと離脱したノードが保持する前記情報に対して引き継ぎ先のノードを判定する、
   ことを特徴とする請求項１から５のいずれか１項に記載の情報処理システム。
7. 複数のノードでデータを同期する情報処理方法であって、
   前記複数のノードの各コンピュータは、
   いずれも共通の分散アルゴリズムに基づいて、前記複数のノードの中から前記データの配信に責任を負ういずれかのノードを決定し、
   決定した前記いずれかのノードを特定する情報を前記いずれかのノード以外の残りのノードに配信する、
   処理を実行する情報処理方法。
8. 互いにデータを同期する複数の情報処理装置の中のいずれかの情報処理装置であって、
   いずれも共通の分散アルゴリズムに基づいて、前記データの配信に責任を負ういずれかの情報処理装置を決定し、
   決定した前記いずれかの情報処理装置を特定する情報を前記いずれかの情報処理装置以外の残りの情報処理装置に配信する、
   処理を実行する処理部を有する情報処理装置。

Images