JP5387757B2 - 並列データ処理システム、並列データ処理方法及びプログラム - Google Patents

Description

［関連出願についての記載］
本発明は、日本国特許出願：特願２０１０−０４９４７３号（２０１０年０３月０５日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、並列データ処理システム、並列データ処理方法及びプログラムに関し、特に、グラフ構造で表現されたデータ集合に含まれるデータを複数の計算機に分散させて記憶した場合に、並列にデータを処理するための並列データ処理システム、並列データ処理方法及びプログラムに関する。

データをグラフ構造で表現する技術が知られている。例えば、非特許文献１に、オブジェクトとオブジェクト間のリンクでデータセットを表現したオブジェクト指向データベース技術が記載されている。また、非特許文献２に、データとデータ間の関係をリンクで表現した知識ベース技術が記載されている。さらに、特許文献１に、ＸＭＬ文書により、グラフの一種である木構造のデータとして格納データを表現して利用するデータベース技術が記載されている。また、非特許文献３に、データとデータ間の「３つ組」構造の関係によりデータを表現するＲＤＦ（Ｒｅｓｏｕｒｃｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｆｒａｍｅｗｏｒｋ）形式により、データを格納及び利用するデータベース技術が記載されている。

一方、多数の計算機をネットワーク接続し、これらのＨＤＤ（Ｈａｒｄ Ｄｉｓｋ Ｄｒｉｖｅ）やメモリを用いて、データを格納及び利用するシステムを実現する技術が知られている。例えば、非特許文献４に、データアイテムあるいはオブジェクトと呼ぶデータ単位をコンシステントハッシング（Ｃｏｎｓｉｓｔｅｎｔ Ｈａｓｈｉｎｇ）と呼ばれる技術により、システムを構成する複数の計算機に複製して分散格納し、ユーザにデータを提供する技術が記載されている。また、非特許文献５に、行（Ｒｏｗ）と呼ばれる複数の列データから構成されるデータ単位に基づいて、複数の計算機全体に対してＢｉｇＴａｂｌｅと呼ばれるデータ構造を構築して、管理及び提供する技術が記載されている。

複数の主体に対して一貫したデータを提供するには、トランザクション制御が必要とされる。例えば、非特許文献６に、強さの異なる複数の種類のロックを、複数の粒度のデータに対して取得することで、データの一貫性が破壊されることを防ぎつつ、ロック取得時間を削減する技術が記載されている。また、特許文献２に、分散された複数のデータベースについて、統合した検索を可能とするため、関連保持用の内部データベースを別途保持する技術が記載されている。

特表２００４−５１５８３６号公報 特開２００５−２３４６１２号公報

大本、高松、田中、「オブジェクトデータベースの経路存在制約とその応用」、 電子情報通信学会技術研究報告 Ｄ．Ｅ． ９５（１４７）、 電子情報通信学会、 ｐｐ．１１３−１２０、１９９５． Ｖ．Ｋ． Ｃｈａｕｄｈｒｉ， "ＴＲＡＮＳＡＣＴＩＯＮ ＳＹＮＣＨＲＯＮＩＺＡＴＩＯＮ ＩＮ ＫＮＯＷＬＥＤＧＥ ＢＡＳＥＳ： Ｃｏｎｃｅｐｔｓ， Ｒｅａｌｉｚａｔｉｏｎ ａｎｄ Ｑｕａｎｔｉｔａｔｉｖｅ Ｅｖａｌｕａｔｉｏｎ，" Ｐｈ．Ｄ． ｔｈｅｓｉｓ， Ｕｎｉｖ． Ｔｒｏｎｔｏ， １９９５． 的野、パレビ、小島、「Ｐ２Ｐ環境における三次元ハッシュ索引を用いた分散ＲＤＦデータベース問合せ処理」、 情報処理学会論文誌． データベース ４７巻（ＳＩＧ＿８（ＴＯＤ＿３０））、ｐｐ．１２１−１３３、 ２００６ Ｇ． ＤｅＣａｎｄｉａ， ｅｔ ａｌ．， "Ｄｙｎａｍｏ： Ａｍａｚｏｎ’ｓ Ｈｉｇｈｌｙ Ａｖａｉｌａｂｌｅ Ｋｅｙ−ｖａｌｕｅ Ｓｔｏｒｅ，" ｉｎ Ｐｒｏｃｅｅｄｉｎｇｓ ｏｎ ２１ｓｔ ＡＣＭ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ Ｐｒｉｎｃｉｐｌｅｓ（ＳＯＳＰ ２００７）， ｐｐ．２０５−２２０， ２００７． Ｆａｙ Ｃｈａｎｇ ｅｔ ａｌ．， "Ｂｉｇｔａｂｌｅ： Ａ Ｄｉｓｔｒｉｂｕｔｅｄ Ｓｔｏｒａｇｅ Ｓｙｓｔｅｍ ｆｏｒ Ｓｔｒｕｃｔｕｒｅｄ Ｄａｔａ，" ＯＳＤＩ ’０６： Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ ７ｔｈ ＵＳＥＮＩＸ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｏｐｅｒａｔｉｎｇ Ｓｙｓｔｅｍｓ Ｄｅｓｉｇｎ ａｎｄ Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ， ｐｐ．２０５−２１８， ２００６． ジム・グレイ、 アンドレアス・ロイター、 「トランザクション処理 概念と技法（上／下）」、 日経ＢＰ社、 ２００１． Ａｌａｎ Ｆｅｋｅｔｅ ｅｔ ａｌ．， "Ｍａｋｉｎｇ Ｓｎａｐｓｈｏｔ Ｉｓｏｌａｔｉｏｎ Ｓｅｒｉａｌｉｚａｂｌｅ，" ＡＣＭ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｄａｔａｂａｓｅ Ｓｙｓｔｅｍｓ （ＴＯＤＳ）， Ｖｏｌ．３０， Ｎｏ．２， ｐｐ．４９２−５２８， ２００５．

上記特許文献１〜２及び非特許文献１〜７の全開示内容はその引用をもって本書に繰込み記載する。
以下の分析は、本発明者によってなされたものである。

多数の計算機によって構成されたデータ格納システムにおいて、グラフ構造で表現されたデータセットに対する更新・読み出し要求の処理における一貫性制御について考える。

従来の一貫性制御手法に基づくシステムは、スケーラビリティを欠く。データセット全体に対するトランザクション性の保持が要求されているため、データセット全体を統括する一貫性保持機構がボトルネックとなるからである。

一方、スケーラビリティを追求する従来のデータ格納システムは、単一オブジェクトごとの一貫性保持機能のみを提供している。非特許文献４又は非特許文献５に記載された技術によると、オブジェクト又は行単位での一貫性保持機能が提供されるに過ぎない。すなわち、単一トランザクションからの複数のオブジェクト（例えば、オブジェクトＡ及びオブジェクトＢ）への更新は個別に処理され、ある時点における読み出しにおいて、新オブジェクトＡと旧オブジェクトＢを同一のトランザクションが読み出すことができる。単一オブジェクトごとの一貫性保持によると、スケーラビリティは向上するものの、より強い一貫性を必要とするアプリケーションには対応することができない。

非特許文献１に記載されているように、グラフ構造のデータベースでは、必ずしもデータセット全体で一貫性を表現しなくてもよい。すなわち、グラフ構造の枝で結合された節点集合（以下「オブジェクトクラスタ」という）内で一貫性が保持されていれば十分であるようなアプリケーションが存在する。

オブジェクトクラスタ内の一貫性を保持する簡単な方法として、予め定められたオブジェクトクラスタごとに異なるシステムで管理する方法が考えられる。しかし、グラフ構造で表現されたデータ集合において、グラフ構造の枝情報が更新される場合がある。グラフ構造の枝情報が更新されることにより、複数のオブジェクトクラスタが結合されて単一のオブジェクトクラスタとなるような場合には、オブジェクトクラスタごとに異なるシステムで管理する方法は、適用することができない。

また、特許文献２に記載された方法によると、異なる一対のオブジェクトクラスタごとに関連保持用の内部データベースが必要とされるため、システムはスケーラビリティを有しない。さらに、特許文献２に記載された方法においては、更新に対するトランザクション性も考慮されていない。

そこで、並列データ処理システムにおいて、複数の処理単位がグラフ構造で表現されたデータ（ないしオブジェクト）を格納、提供及び更新する場合に、オブジェクトクラスタごとの一貫性を保持するとともに、スケーラビリティを確保することが課題となる。本発明の目的は、かかる課題を解決する並列データ処理システム、並列データ処理方法及びプログラムを提供することにある。

本発明の第１の視点に係る並列データ処理システムは、
オブジェクト間の関連を表すオブジェクト関連情報とオブジェクトとを保持するオブジェクト格納部と、
前記オブジェクト格納部に対してオブジェクト又はオブジェクト関連情報の生成、読み出し又は更新を行う処理単位と、
オブジェクト関連情報で関連付けられたオブジェクトの集合であるオブジェクトクラスタごとに設けられ、各オブジェクトクラスタ内のオブジェクトに対する一貫した値を前記処理単位に返す複数の一貫性制御部と、
オブジェクトの識別子を受けて、該オブジェクトを含むオブジェクトクラスタの識別子、又は、前記複数の一貫性制御部のうちの該オブジェクトクラスタに対する一貫性制御部の識別子を返すオブジェクト対クラスタ対応判定部と、を備え、
前記処理単位は、オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を、前記オブジェクト対クラスタ対応判定部から取得し、前記オブジェクト格納部にアクセスしている間は、該一貫性制御部に基づいて一貫性制御を行う。

本発明の第２の視点に係る並列データ処理方法は、
オブジェクト間の関連を表すオブジェクト関連情報とオブジェクトとを保持するオブジェクト格納部と、
前記オブジェクト格納部に対するオブジェクト又はオブジェクト関連情報の生成、読み出し又は更新を行う処理単位と、
オブジェクト関連情報で関連付けられたオブジェクトの集合であるオブジェクトクラスタごとに設けられ、各オブジェクトクラスタ内のオブジェクトに対する一貫した値を前記処理単位に返す複数の一貫性制御部と、
オブジェクトの識別子を受けて、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を返すオブジェクト対クラスタ対応判定部と、を備えた並列データ処理システムにおいて、
前記処理単位が、オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を、前記オブジェクト対クラスタ対応判定部から取得する工程と、
前記オブジェクト格納部にアクセスしている間は、前記複数の一貫性制御部のうちの取得した識別子に相当する一貫性制御部に基づいて一貫性制御を行う工程と、を含む。

本発明の第３の視点に係るプログラムは、
オブジェクト間の関連を表すオブジェクト関連情報とオブジェクトとを保持するオブジェクト格納部と、
前記オブジェクト格納部に対するオブジェクト又はオブジェクト関連情報の生成、読み出し又は更新を行う処理単位と、
オブジェクト関連情報で関連付けられたオブジェクトの集合であるオブジェクトクラスタごとに設けられ、各オブジェクトクラスタ内のオブジェクトに対する一貫した値を前記処理単位に返す複数の一貫性制御部と、
オブジェクトの識別子を受けて、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を返すオブジェクト対クラスタ対応判定部と、を備えた並列データ処理システムにおいて、
オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を、前記オブジェクト対クラスタ対応判定部から取得する処理と、
前記オブジェクト格納部にアクセスしている間は、前記複数の一貫性制御部のうちの取得した識別子に相当する一貫性制御部に基づいて一貫性制御を行う処理と、をコンピュータに実行させる。

本発明に係る並列データ処理システム、並列データ処理方法及びプログラムによると、複数の処理単位がグラフ構造で表現されたデータを格納、提供及び更新する場合に、オブジェクトクラスタごとの一貫性を保持するとともに、スケーラビリティを確保することができる。

第１の実施形態に係る並列データ処理システムの構成を示すブロック図である。 第１の実施形態に係る並列データ処理システムの構成を示すブロック図である。 オブジェクトクラスタについて説明するための図である。 第１の実施形態に係る並列データ処理システムにおける処理単位対クラスタ対応判定部による処理を一例として示す図である。 第１の実施形態に係る並列データ処理システムにおけるオブジェクト対クラスタ対応判定部におけるオブジェクトとオブジェクトクラスタとの対応関係を一例として示す図である。 第１の実施形態に係る並列データ処理システムによるオブジェクトクラスタ間をまたがない処理を一例として示すシーケンス図である。 第１の実施形態に係る並列データ処理システムによるオブジェクトクラスタ間をまたぐものの、オブジェクトクラスタ間の結合が起こらなかったときの処理を一例として示すシーケンス図である。 第１の実施形態に係る並列データ処理システムによる、オブジェクトクラスタ間をまたぐ関連ができた場合における処理を一例として示すシーケンス図である。 第２の実施形態に係る並列データ処理システムの構成を示すブロック図である。 第２の実施形態に係る並列データ処理システムのオブジェクト対クラスタ判定部に格納された情報を一例として示す図である。 第３の実施形態に係る並列データ処理システムの構成を示すブロック図である。

第１の展開形態によると、上記第１の視点に係る並列データ処理システムが提供される。

第２の展開形態によると、
前記オブジェクト対クラスタ対応判定部は、非同期に更新された、オブジェクトの識別子と該オブジェクトを含むオブジェクトクラスタの識別子との関連付けを保持する非同期オブジェクト対クラスタ対応情報と、
オブジェクトクラスタが他のオブジェクトクラスタに統合された場合に、統合により消滅したオブジェクトクラスタの識別子と統合先のオブジェクトクラスタの識別子とを関連付けて保持するクラスタ結合情報と、
オブジェクトの識別子を受けて、該オブジェクトの識別子と前記非同期オブジェクト対クラスタ対応情報とから、該オブジェクトが過去に属していたオブジェクトクラスタの識別子を取得し、該オブジェクトクラスタの識別子と前記クラスタ結合情報とから、該オブジェクトが現在属するオブジェクトクラスタの識別子、又は、前記複数の一貫性制御部のうちの該オブジェクトクラスタに対応する一貫性制御部の識別子を取得して返す対応クラスタ決定部と、をさらに備えている、並列データ処理システムが提供される。

第３の展開形態によると、
処理単位の識別子と該処理単位がアクセス中のオブジェクトを含むオブジェクトクラスタの識別子とを関連付けて保持する処理単位対クラスタ対応判定部をさらに備え、
前記処理単位は、オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、関連するオブジェクトクラスタの識別子と前記複数の一貫性制御部のうちの該オブジェクトクラスタに対する一貫性制御部の識別子とを、前記オブジェクト対クラスタ対応判定部から取得し、該オブジェクトクラスタにアクセスする前に、自身を表す識別子と該オブジェクトクラスタの識別子とを前記処理単位対クラスタ対応判定部に登録する、並列データ処理システムが提供される。

第４の展開形態によると、
処理単位により複数のオブジェクトクラスタを結合する操作が発生した場合には、該複数のオブジェクトクラスタに含まれるオブジェクトに対する処理を行っている処理単位のうちのコミットされていない未コミット処理単位を、前記処理単位対クラスタ対応判定部から取得し、該未コミット処理単位の処理を中止する命令を発行するクラスタ結合制御部をさらに備えている、並列データ処理システムが提供される。

第５の展開形態によると、
前記複数の一貫性制御部は、それぞれ、複数のオブジェトのバージョンを利用したＭＶＣＣ（Ｍｕｌｔｉｖｅｒｓｉｏｎ Ｃｏｎｃｕｒｒｅｎｃｙ Ｃｏｎｔｒｏｌ）制御による一貫性制御を行い、
前記クラスタ結合制御部は、前記未コミット処理単位のうちの読み出しのみを行っている処理単位には、オブジェクトクラスタ結合以前のバージョンを提供する、並列データ処理システムが提供される。

第６の展開形態によると、前記オブジェクトは、ファイルシステムのファイル、ファイルと関連するメタデータの集合、関係データベースのタプル、オブジェクトデータベースのデータ、Ｋｅｙ−ＶａｌｕｅストアのＫｅｙ−ｖａｌｕｅ、ＸＭＬ文書のタグで囲まれた内容、ＲＤＦ（Ｒｅｓｏｕｒｃｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｆｒａｍｅｗｏｒｋ）文書のリソースのいずれかである、並列データ処理システムが提供される。

第７の展開形態によると、前記オブジェクトクラスタは、オブジェクト関連情報で結ばれたオブジェクトの集合である、並列データ処理システムが提供される。

第８の展開形態によると、前記オブジェクト関連情報は、オブジェクト間の双方向又は片方向の関連を含む、並列データ処理システムが提供される。

第９の展開形態によると、上記第２の視点に係る並列データ処理方法が提供される。

第１０の展開形態によると、上記第３の視点に係るプログラムが提供される。

第１１の展開形態によると、上記プログラムが記録されたコンピュータ読み取り可能な記録媒体が提供される。

本発明に係る並列データ処理システム、並列データ処理方法及びプログラムによると、オブジェクトクラスタごとに一貫性制御を行うことで、従来のオブジェクト単位の一貫性制御では実現できないアプリケーションを実装することができる。また、オブジェクトクラスタを結合する処理以外は、個々の一貫性制御部で処理が完結するため、システムが多数の計算機で構成されていたとしても、オブジェクトクラスタの個数に比例したスケーラビリティを実現することができる。さらに、システム動作中におけるオブジェクトの結合も処理することができる。

（実施形態１）
第１の実施形態に係る並列データ処理システムについて、図面を参照して説明する。図１は、本実施形態に係る並列データ処理システム１００の構成を示すブロック図である。

図１を参照すると、並列データ処理システム１００は、オブジェクト格納部３０、処理単位４０、処理単位対クラスタ対応判定部２１、オブジェクト対クラスタ対応判定部２２及び一貫性制御部２３を有する。

オブジェクト格納部３０は、オブジェクト間の関連を表すオブジェクト関連情報とオブジェクトとを保持する。

処理単位４０はオブジェクト格納部３０に対して、オブジェクト又はオブジェクト関連情報の生成、読み出し又は更新を行う。

一貫性制御部２３は、各オブジェクトクラスタ内のオブジェクトに対する一貫した値を処理単位４０に返す。

オブジェクト対クラスタ対応判定部２２は、オブジェクトの識別子を受けて、当該オブジェクトを含むオブジェクトクラスタの識別子又は当該オブジェクトクラスタに対する一貫性制御部２３の識別子を返す。

処理単位対クラスタ対応判定部２１は、処理単位の識別子と当該処理単位がアクセス中のオブジェクトを含むオブジェクトクラスタの識別子とを関連付けて保持する。

処理単位４０は、オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、当該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部２３の識別子を、オブジェクト対クラスタ対応判定部２２から取得し、オブジェクト格納部３０にアクセスしている間は、取得した一貫性制御部に基づいて一貫性制御を行う。

図２は、本実施形態に係る並列データ処理システムを、複数のデータ処理装置によって実現した場合の構成を示すブロック図である。

図２を参照すると、並列データ処理システムは、データ処理装置１０ａ〜１０ｃが、ネットワーク６０を介して接続されている。ここでは、データ処理装置の台数を、一例として３台としたが、データ処理装置の台数はこれに限られない。また、並列データ処理システム１００を利用するユーザに提供されたユーザ計算機７０も、ネットワーク６０に接続されている。

図２を参照すると、データ処理装置１０ａ〜１０ｃは、それぞれ、ＣＰＵ１１ａ〜１１ｃ、データ記憶部１２ａ〜１２ｃ及びデータ転送部１３ａ〜１３ｃを有する。ＣＰＵ１１ａ〜１１ｃは、本実施形態に係る並列データ処理システム１００の各部の機能を実現する。

データ記憶部１２ａ〜１２ｃは、例えば、ハードディスクドライブ（ＨＤＤ）、フラッシュメモリ、ＤＲＡＭ（Ｄｙｎａｍｉｃ Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）、ＭＲＡＭ（Ｍａｇｎｅｔｏｒｅｓｉｓｔｉｖｅ ＲＡＭ）、ＦｅＲＡＭ（Ｆｅｒｒｏｅｌｅｃｔｒｉｃ ＲＡＭ）、ＰＲＡＭ（Ｐｈａｓｅ ｃｈａｎｇｅ ＲＡＭ）、ＲＡＩＤコントローラに結合された記憶装置、磁気テープのようにデータを記録可能な物理媒体、又は、ストレージノードの外部に設置された媒体にデータを記録する制御装置である。

ネットワーク６０及びデータ転送部１３ａ〜１３ｃは、例えば、Ｅｔｈｅｒｎｅｔ（登録商標）、Ｆｉｂｒｅ ＣｈａｎｎｅｌやＦＣｏＥ（Ｆｉｂｒｅ Ｃｈａｎｎｅｌ ｏｖｅｒ Ｅｔｈｅｒｎｅｔ（登録商標））、ＩｎｆｉｎｉＢａｎｄ、ＱｓＮｅｔ、 Ｍｙｒｉｎｅｔ、 Ｅｔｈｅｒｎｅｔ、あるいはこれらを利用するＴＣＰ／ＩＰやＲＤＭＡのような上位プロトコルによって実現しうる。ただし、ネットワーク６０の実現方法は、これらに限られない。

処理単位４０は、格納されたオブジェクトに対する１つ又は複数の処理を発行するプログラムである。処理単位４０は、例えば、ＣＰＵ１１ａ〜１１ｃのいずれかで動作するプログラムにより実施される。他の例として、処理単位４０は、ネットワーク６０を通じてデータのやり取りができる計算機（非図示）上のプログラムである。例えば、トランザクション処理システムにおける１つのトランザクションを、１つの処理単位とみなすことができる。

データ処理装置１０ａ〜１０ｃにより、オブジェクト格納部３０が実現される。ユーザデータであるオブジェクトとオブジェクト間の関係は、それぞれ、オブジェクト３１とオブジェクト関連情報３２として、データ記憶部１２ａ〜１２ｃに格納される。

ここで、オブジェクトとは、識別子によって識別しうる１つ以上のデータの集合である。オブジェクトは、例えば、ユーザから意味的に分断された最小単位のデータを表す。オブジェクトとして、例えば、ファイルシステムのファイル、ファイルと関連するメタデータの集合、関係データベースのタプル、オブジェクトデータベースのデータ、Ｋｅｙ−ＶａｌｕｅストアのＫｅｙ−ｖａｌｕｅ、ＸＭＬ文書のタグで囲まれた内容、ＲＤＦ文書のリソース、Ｇｏｏｇｌｅ Ａｐｐ Ｅｎｇｉｎｅのデータエンティティ、Ｍｉｃｒｏｓｏｆｔ Ｗｉｎｄｏｗｓ Ａｚｕｒｅキューのメッセージ等が挙げられる。なお、オブジェクトは、これらに限られない。

また、データ記憶部１２ａ〜１２ｃには、２つ以上のオブジェクトの関係を示す情報がオブジェクト関連情報３２として格納されている。オブジェクト関連情報３２とは、２つ以上のオブジェクトが関連していることを表すために、データを扱うユーザ又はシステムが付与する情報である。オブジェクト関連情報として、例えば、オブジェクトがメタデータとして別のオブジェクトへの参照を有する場合が挙げられる。また、ファイルシステムのディレクトリは格納ファイル情報を有する。この格納ファイル情報も、オブジェクト関連情報とみなすことができる。さらに、ＸＭＬ文書におけるＸＭＬ構造を木構造として捉えた場合には、親と子との間のオブジェクト関連情報とみなすことができる。なお、オブジェクト関連情報は、これらに限られない。

オブジェクトクラスタは、オブジェクト関連情報で結ばれたオブジェクトの集合である。すなわち、オブジェクトＯ_ＸとオブジェクトＯ_Ｙとの間の関連情報がオブジェクト関連情報３２に存在する場合には、オブジェクトＯ_Ｘ及びオブジェクトＯ_Ｙは、同一のオブジェクトクラスタ（例えば、オブジェクトクラスタＣ_Ａ）に属するものとする。

図３は、オブジェクトとオブジェクト間の関連情報により構成されるオブジェクトクラスタを一例として示す図である。図３を参照すると、オブジェクトクラスタＣ_ＡはオブジェクトＯ_１〜Ｏ_３を含み、オブジェクトクラスタＣ_ＢはオブジェクトＯ_４〜Ｏ_９を含み、オブジェクトクラスタＣ_ＣはオブジェクトＯ_１０〜Ｏ_１２を含む。

図３の状態において、例えば、新しい処理単位４０がオブジェクトＯ_３とオブジェクトＯ_４との間にオブジェクト関連情報を生成した場合、当該処理がコミットされ、オブジェクト格納部３０に格納された後は、オブジェクトクラスタＣ_ＡとオブジェクトクラスタＣ_Ｂに含まれるすべてのオブジェクトは同一のオブジェクトクラスタに属するものとみなされる。

オブジェクトは、複数のデータ処理装置１０ａ〜１０ｃに分散して格納される。これは、例えば、コンシステントハッシュ、メタサーバによる分散配置等によって実現しうる。一方、オブジェクト関連情報３２は、一箇所に格納されていてもよいし、オブジェクトごとに付与されて分散して格納されていてもよい。また、オブジェクト関連情報３２には方向があってもよい。すなわち、オブジェクトＯ_１からオブジェクトＯ_２への関連はあるものの、オブジェクトＯ_２からオブジェクトＯ_１への関連はないものとするオブジェクト関連情報が存在してもよい。なお、本実施形態においては、かかる場合にはオブジェクトＯ_１とオブジェクトＯ_２とは関連があるものとみなす。

並列データ処理システムを複数のデータ処理装置によって実現した場合、処理単位対クラスタ対応判定部、オブジェクト対クラスタ対応判定部、一貫性制御部は、例えば、ＣＰＵ１１ａ〜１１ｃ上で動作するプログラムがネットワーク６０によってお互いに協調動作することによって実現される。また、他の例として、処理単位対クラスタ対応判定部、オブジェクト対クラスタ対応判定部、一貫性制御部の機能を有する個別のハードウェアあるいは専用ＣＰＵを各データ処理装置が備えていてもよい。

ユーザ計算機７０又はデータ処理装置１０ａ〜１０ｃ上で動作する処理単位（ないしトランザクション）４０は、オブジェクト格納部３０上のオブジェクト又はオブジェクト関連情報に対する１つ以上の作成、読み出し、書き込み又は削除により構成される。処理単位４０は、並列データ処理システム１００が提供する一貫性の範囲内でデータを利用することができ、これが実現できないときには、並列データ処理システム１００によりロールバック処理又はアボート処理が行われる。すなわち、本実施形態の並列データ処理システム１００では、オブジェクトクラスタ内の一貫性を満たす範囲でデータを作成、読み出し、書き込み又は削除ができない場合には、ロールバック処理又はアボート処理が行われる。かかる場合として、例えば、他の処理単位４０による更新との間で不整合が生じる場合が挙げられる。

一貫性制御は、例えば、非特許文献６に記載された階層ロッキングにより、Ｓロック、Ｘロック、ＩＳロック、ＩＸロックという強さが異なるロックを、オブジェクトクラスタ全体、オブジェクト、オブジェクト内のメタデータ等の粒度が異なるデータに対して付与し、各処理単位の排他制御を行うことによって実現することができる。また、一貫性制御は、非特許文献７に記載されたＳＩ（Ｓｎａｐｓｈｏｔ Ｉｓｏｌａｔｉｏｎ）手法により、オブジェクトの複数のバージョンを格納し、処理単位ごとにいずれのバージョンを提供するかを制御することによって実現することもできる。なお、本実施形態における一貫性制御は、これらの手法に限定されない。

次に、データ処理装置１０ａ〜１０ｃで実現される、処理単位対クラスタ対応判定部２１、オブジェクト対クラスタ対応判定部２２、及び一貫性制御部２３のそれぞれの動作によって実現されるオブジェクトの一貫性制御について説明する。

処理単位対クラスタ対応判定部２１は、どの処理単位４０が現在までにどのオブジェクトクラスタに属するオブジェクトに関わったかを保持する。また、処理単位対クラスタ対応判定部２１は、オブジェクトクラスタを識別する識別子を入力とし、そのオブジェクトに関わっている処理単位の識別子のリストを出力する。さらに、処理単位対クラスタ対応判定部２１は、複数のオブジェクトクラスタのそれぞれを識別する識別子を入力とし、これらの２つ以上に関わっており、かつ、未コミット状態である処理単位の識別子のリストを出力する。

図４は、処理単位対クラスタ対応判定部による処理を一例として示す図である。図４の表は、処理単位の識別子とオブジェクトクラスタの識別子とを関連付けて保持している。図４の表に示すように、処理単位とオブジェクトクラスタとが関連付けられている場合には、処理単位対クラスタ対応判定部２１は、処理単位３の識別子を入力としたときには、オブジェクトクラスタＣ_Ｅ、Ｃ_Ｈの識別子を出力する。一方、オブジェクトクラスタＣ_Ｈの識別子を入力としたときには、処理単位３〜６の識別子を出力する。

オブジェクト対クラスタ対応判定部２２は、どのオブジェクトが現在どのオブジェクトクラスタに属しているかを保持する。また、オブジェクト対クラスタ対応判定部２２は、オブジェクトを識別する識別子を入力とし、そのオブジェクトが現在属しているオブジェクトクラスタを識別する識別子、又は、当該オブジェクトクラスタに関する一貫性制御を行う一貫性制御部２３の識別子を返す。

図５は、オブジェクト対クラスタ対応判定部２２におけるオブジェクトとオブジェクトクラスタとの対応関係を一例として示す図である。図５を参照すると、オブジェクトＯ_１、Ｏ_２はオブジェクトクラスタＣ_Ｄに含まれ、オブジェクトＯ_３はオブジェクトクラスタＣ_Ｅに含まれ、オブジェクトＯ_４〜Ｏ_６はオブジェクトクラスタＣ_Ｈに含まる。

図６、図７、図８を参照して、処理単位によるオブジェクト参照又は更新の動作について説明する。

処理単位４０は、オブジェクトを参照又は更新する際、まず、当該オブジェクトが属するオブジェクトクラスタを識別する識別子をオブジェクト対クラスタ対応判定部２２から取得する。次に、処理単位４０は、当該オブジェクトにアクセスする前に、処理単位対クラスタ対応判定部２１に、自身を表す識別子と当該オブジェクトクラスタを表す識別子とを登録する。なお、処理単位４０が、当該クラスタ内のオブジェクト又はオブジェクト関連情報を利用してすでに登録済みであることを判別できる場合には、処理単位対クラスタ対応判定部２１への登録を省略することができる。

次に、処理単位４０は、データへのアクセスを行う。ここで、処理単位４０のアクセス中に、複数のオブジェクトクラスタにまたがるオブジェクト関連情報の作成が含まれない場合には、上述の従来手法によって、個々のオブジェクトクラスタごとに、処理単位４０のアクセスに対する一貫性管理が行われる。図６は、オブジェクトクラスタ間をまたがない処理を一例として示すシーケンス図である。

処理単位４０は、データへのアクセスが終了した場合には、コミット命令を各一貫性制御部２３に発行する。ここで、複数のオブジェクトクラスタ間にまたがるオブジェクト関連情報３２の作成が含まれない場合には、それぞれの一貫性制御部２３でコミットの成否が判断される。コミットの成否は、当該処理単位によるデータへの変更が他の処理単位による読み書きに影響するか否かに基づいて判断される。

ここで、他の処理単位との影響の度合いは、ユーザ又はシステムが事前に設定した条件によって決まる。各判定や条件は、既存技術により行われる。例えば、トランザクションの分離レベルが直列化（Ｓｅｒｉａｌｉｚａｂｌｅ）である場合には、全ての処理単位が時間的にオーバーラップせず、直列に実行された場合とデータの状態が同一であれば成功とみなされる。一部のコミットが失敗したとしても、その他のコミットは成功する。図７は、オブジェクトクラスタ間をまたぐものの、オブジェクトクラスタ間の結合が起こらなかったときの処理を一例として示すシーケンス図である。

ここで、ある処理単位４０により、複数のオブジェクトクラスタ間にまたがるオブジェクト関連情報３２が作成されたとする。図８は、オブジェクトクラスタ間をまたぐ関連ができた場合の処理を一例として示すシーケンス図である。この場合には、まず、処理単位４０は、処理単位対クラスタ対応判定部２１によって、関連するオブジェクトクラスタの２つ以上にまたがる処理単位を特定する。次に、当該処理をアボートさせる。さらに、オブジェクト対クラスタ対応判定部２２に対し、当該オブジェクトクラスタの結合を指示する。オブジェクト対クラスタ対応判定部２２は、当該オブジェクトクラスタ内のすべてのオブジェクトが単一のオブジェクトクラスタに相当するように情報を書き換える。最後に、各オブジェクトクラスタに対応する一貫性制御部２３に同時にコミットを発行する。

ここでは、例えば、２相コミット（２ＰＣ：Ｔｗｏ Ｐｈａｓｅ Ｃｏｍｍｉｔ）を用いることができる。すなわち、まず、２ＰＣ−プリペア（コミット準備）メッセージをすべての一貫性制御部２３に発行する。一貫性制御部２３は、当該コミットが成功するか否かを判定する。一貫性制御部２３は、コミットが失敗する予定であれば失敗と返す。一方、一貫性制御部２３は、コミットが成功するのであれば、当該コミットを妨げるすべてのリソースをロックし、成功を返す。次に、処理単位は、２ＰＣ−コミット（コミット実行）メッセージを送出し、すべての一貫性制御部２３は、データの更新を反映させ、必要に応じてロックを開放する。

以上のように、オブジェクトクラスタごとに一貫性制御を行うことで、従来のオブジェクト単位の一貫性制御によると実現することのできないアプリケーションを実装することができる。また、オブジェクトクラスタを結合する処理以外は、個々の一貫性制御部２３で処理が完結する。したがって、並列データ処理システム１００が複数のデータ処理装置１０ａ〜１０ｃを含む場合においても、オブジェクトクラスタの個数に比例したスケーラビリティを実現することができる。

（実施形態２）
第２の実施形態に係る並列データ処理システムについて、図面を参照して説明する。本実施形態では、第１の実施形態におけるオブジェクト対クラスタ対応判定部２２内の処理を２段階とし、オブジェクト対クラスタ対応判定部２２が情報を更新する処理の性能を向上させる。

図９は、本実施形態に係る並列データ処理システム２００の構成を示すブロック図である。図９を参照すると、本実施形態におけるオブジェクト対クラスタ対応判定部５２は、さらに、対応クラスタ決定部５３、クラスタ結合情報５５及び非同期オブジェクト対クラスタ対応情報５６を有する。

オブジェクト対クラスタ対応判定部５２は、どのオブジェクトが現在どのオブジェクトクラスタに属しているかを保持する。また、オブジェクト対クラスタ対応判定部５２は、オブジェクトを識別する識別子を入力とし、そのオブジェクトが現在属しているオブジェクトクラスタを識別する識別子、又は、当該オブジェクトクラスタに関する一貫性制御を行う一貫性制御部２３の識別子を返す。

クラスタ結合情報５５は、以前存在したオブジェクトクラスタが他のクラスタに結合された際に、当該結合を表す情報を蓄積する。図１０は、クラスタ結合情報５５を一例として示す。クラスタ結合情報５５に基づいて、各オブジェクトクラスタが、現在どのオブジェクトクラスタに結合されているかを判別することができる。

図１０を参照すると、例えば、オブジェクトクラスタＣ_Ａは、現在、オブジェクトクラスタＣ_Ｂに結合されている。一方、オブジェクトクラスタＣ_Ｂは、オブジェクトクラスタＣ_Ｄに結合されている。さらに、オブジェクトクラスタＣ_Ｄは、オブジェクトクラスタＣ_Ｅに結合されている。したがって、図１０に示したクラスタ結合情報５５によると、オブジェクトクラスタＣ_Ａは、現在、オブジェクトクラスタＣ_Ｅに結合されていることが分かる。

非同期オブジェクト対クラスタ対応情報５６は、各オブジェクトがいずれのオブジェクトクラスタに所属しているかを示す情報を非同期に更新したものである。図１０は、非同期オブジェクト対クラスタ対応情報５６を一例として示す。非同期オブジェクト対クラスタ対応情報５６に基づいて、オブジェクトに対するオブジェクトクラスタを取得することができる。ここで、非同期に更新するとは、オブジェクトの結合が起こったとしても、非同期オブジェクト対クラスタ対応情報５６を、直ちに更新する必要がないか、又は、全く更新する必要がないことを意味する。

対応クラスタ決定部５３は、オブジェクトの識別子を受けて、当該オブジェクトが所属するオブジェクトクラスタの識別子を返す。まず、対応クラスタ決定部５３は、アクセス対象のオブジェクト識別子と非同期オブジェクト対クラスタ対応情報５６とを用いて、当該オブジェクトが過去に所属していたオブジェクトクラスタの識別子を取得する。次に、対応クラスタ決定部５３は、取得したオブジェクトクラスタの識別子とクラスタ結合情報５５と用いて、当該オブジェクトが現在いずれのオブジェクトクラスタに存在し、いずれの一貫性制御部２３で管理されているかを示す識別子を返す。

本実施形態の並列データ処理システム２００によると、２つのオブジェクトクラスタが結合した場合に、クラスタ結合情報５５を一行更新するだけでよい。一方、第１の実施形態の並列データ処理システム１００によると、オブジェクトの個数だけ所属クラスタの情報が更新される。したがって、本実施形態によると、第１の実施形態と比較して、オブジェクト対クラスタ対応判定部５２による更新処理を高速化することができる。

（実施形態３）
第３の実施形態に係る並列データ処理システムについて、図面を参照して説明する。図１１は、本実施形態に係る並列データ処理システム３００の構成を示すブロック図である。

図１１を参照すると、本実施形態の並列データ処理システムは、上記第１の実施形態に係る並列データ処理システム１００（図１）において、さらに、クラスタ結合制御部２５を有している。

クラスタ結合制御部２５は、処理単位４０から複数のオブジェクトクラスタを結合する操作が発生し、コミットした際に、対象となる複数のオブジェクトクラスタにまたがって処理を行っている処理単位であってコミットしていない未コミット処理単位を、処理単位クラスタ対応判定部２１から取得し、当該未コミット処理単位の処理を中止する命令を発行する。

また、一貫性制御部２３は、複数のオブジェトのバージョンを利用したＭＶＣＣ（Ｍｕｌｔｉｖｅｒｓｉｏｎ Ｃｏｎｃｕｒｒｅｎｃｙ Ｃｏｎｔｒｏｌ）制御による一貫性制御を行うようにしてもよい。このとき、クラスタ結合制御部２５は、上記の未コミット処理単位のうちの読み出しのみを行っている処理単位には、オブジェクトクラスタ結合以前のバージョンを提供することが好ましい。

本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。

本発明に係る並列データ処理システム、並列データ処理方法及びプログラムは、並列データベース、分散ストレージ、並列ファイルシステム、分散データベース、データグリッド、クラスタコンピュータに適用することができる。

１０ａ〜１０ｃ データ処理装置
１１ａ〜１１ｃ ＣＰＵ
１２ａ〜１２ｃ データ記憶部
１３ａ〜１３ｃ データ転送部
２１ 処理単位対クラスタ対応判定部
２２、５２ オブジェクト対クラスタ対応判定部
２３ 一貫性制御部
２５ クラスタ結合制御部
３０ オブジェクト格納部
３１、Ｏ_１〜Ｏ_１２、Ｏ_Ｘ、Ｏ_Ｙ オブジェクト
３２ オブジェクト関連情報
４０ 処理単位
５３ 対応クラスタ決定部
５５ クラスタ結合情報
５６ 非同期オブジェクト対クラスタ対応情報
６０ ネットワーク
７０ ユーザ計算機
１００、２００、３００ 並列データ処理システム
Ｃ_Ａ〜Ｃ_Ｈ オブジェクトクラスタ

Claims (9)

1. オブジェクト間の関連を表すオブジェクト関連情報とオブジェクトとを保持するオブジェクト格納部と、
   前記オブジェクト格納部に対してオブジェクト又はオブジェクト関連情報の生成、読み出し又は更新を行う処理単位と、
   オブジェクト関連情報で関連付けられたオブジェクトの集合であるオブジェクトクラスタごとに設けられ、各オブジェクトクラスタ内のオブジェクトに対する一貫した値を前記処理単位に返す複数の一貫性制御部と、
   オブジェクトの識別子を受けて、該オブジェクトを含むオブジェクトクラスタの識別子、又は、前記複数の一貫性制御部のうちの該オブジェクトクラスタに対する一貫性制御部の識別子を返すオブジェクト対クラスタ対応判定部と、を備え、
   前記処理単位は、オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を、前記オブジェクト対クラスタ対応判定部から取得し、前記オブジェクト格納部にアクセスしている間は、該一貫性制御部に基づいて一貫性制御を行うことを特徴とする並列データ処理システム。
2. 前記オブジェクト対クラスタ対応判定部は、非同期に更新された、オブジェクトの識別子と該オブジェクトを含むオブジェクトクラスタの識別子との関連付けを保持する非同期オブジェクト対クラスタ対応情報と、
   オブジェクトクラスタが他のオブジェクトクラスタに統合された場合に、統合により消滅したオブジェクトクラスタの識別子と統合先のオブジェクトクラスタの識別子とを関連付けて保持するクラスタ結合情報と、
   オブジェクトの識別子を受けて、該オブジェクトの識別子と前記非同期オブジェクト対クラスタ対応情報とから、該オブジェクトが過去に属していたオブジェクトクラスタの識別子を取得し、該オブジェクトクラスタの識別子と前記クラスタ結合情報とから、該オブジェクトが現在属するオブジェクトクラスタの識別子、又は、前記複数の一貫性制御部のうちの該オブジェクトクラスタに対応する一貫性制御部の識別子を取得して返す対応クラスタ決定部と、をさらに備えていることを特徴とする、請求項１に記載の並列データ処理システム。
3. 処理単位の識別子と該処理単位がアクセス中のオブジェクトを含むオブジェクトクラスタの識別子とを関連付けて保持する処理単位対クラスタ対応判定部をさらに備え、
   前記処理単位は、オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、関連するオブジェクトクラスタの識別子と前記複数の一貫性制御部のうちの該オブジェクトクラスタに対する一貫性制御部の識別子とを、前記オブジェクト対クラスタ対応判定部から取得し、該オブジェクトクラスタにアクセスする前に、自身を表す識別子と該オブジェクトクラスタの識別子とを前記処理単位対クラスタ対応判定部に登録することを特徴とする、請求項１又は２に記載の並列データ処理システム。
4. 処理単位により複数のオブジェクトクラスタを結合する操作が発生した場合には、該複数のオブジェクトクラスタに含まれるオブジェクトに対する処理を行っている処理単位のうちのコミットされていない未コミット処理単位を、前記処理単位対クラスタ対応判定部から取得し、該未コミット処理単位の処理を中止する命令を発行するクラスタ結合制御部をさらに備えていることを特徴とする、請求項３に記載の並列データ処理システム。
5. 前記複数の一貫性制御部は、それぞれ、複数のオブジェトのバージョンを利用したＭＶＣＣ（Ｍｕｌｔｉｖｅｒｓｉｏｎ Ｃｏｎｃｕｒｒｅｎｃｙ Ｃｏｎｔｒｏｌ）制御による一貫性制御を行い、
   前記クラスタ結合制御部は、前記未コミット処理単位のうちの読み出しのみを行っている処理単位には、オブジェクトクラスタ結合以前のバージョンを提供することを特徴とする、請求項４に記載の並列データ処理システム。
6. 前記オブジェクトは、ファイルシステムのファイル、ファイルと関連するメタデータの集合、関係データベースのタプル、オブジェクトデータベースのデータ、Ｋｅｙ−ＶａｌｕｅストアのＫｅｙ−ｖａｌｕｅ、ＸＭＬ文書のタグで囲まれた内容、ＲＤＦ（Ｒｅｓｏｕｒｃｅ Ｄｅｓｃｒｉｐｔｉｏｎ Ｆｒａｍｅｗｏｒｋ）文書のリソースのいずれかであることを特徴とする、請求項１乃至５のいずれか１項に記載の並列データ処理システム。
   
7. 前記オブジェクト関連情報は、オブジェクト間の双方向又は片方向の関連を含むことを特徴とする、請求項１乃至６のいずれか１項に記載の並列データ処理システム。
8. オブジェクト間の関連を表すオブジェクト関連情報とオブジェクトとを保持するオブジェクト格納部と、
   前記オブジェクト格納部に対するオブジェクト又はオブジェクト関連情報の生成、読み出し又は更新を行う処理単位と、
   オブジェクト関連情報で関連付けられたオブジェクトの集合であるオブジェクトクラスタごとに設けられ、各オブジェクトクラスタ内のオブジェクトに対する一貫した値を前記処理単位に返す複数の一貫性制御部と、
   オブジェクトの識別子を受けて、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を返すオブジェクト対クラスタ対応判定部と、を備えた並列データ処理システムにおいて、
   前記処理単位が、オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を、前記オブジェクト対クラスタ対応判定部から取得する工程と、
   前記オブジェクト格納部にアクセスしている間は、前記複数の一貫性制御部のうちの取得した識別子に相当する一貫性制御部に基づいて一貫性制御を行う工程と、を含むことを特徴とする並列データ処理方法。
9. オブジェクト間の関連を表すオブジェクト関連情報とオブジェクトとを保持するオブジェクト格納部と、
   前記オブジェクト格納部に対するオブジェクト又はオブジェクト関連情報の生成、読み出し又は更新を行う処理単位と、
   オブジェクト関連情報で関連付けられたオブジェクトの集合であるオブジェクトクラスタごとに設けられ、各オブジェクトクラスタ内のオブジェクトに対する一貫した値を前記処理単位に返す複数の一貫性制御部と、
   オブジェクトの識別子を受けて、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を返すオブジェクト対クラスタ対応判定部と、を備えた並列データ処理システムにおいて、
   オブジェクト又はオブジェクト関連情報の作成、読み出し又は更新を行う際、前記複数の一貫性制御部のうちの該オブジェクトを含むオブジェクトクラスタに対する一貫性制御部の識別子を、前記オブジェクト対クラスタ対応判定部から取得する処理と、
   前記オブジェクト格納部にアクセスしている間は、前記複数の一貫性制御部のうちの取得した識別子に相当する一貫性制御部に基づいて一貫性制御を行う処理と、をコンピュータに実行させることを特徴とするプログラム。

Images