データベースの管理方法
【課題】リソースの効率的な活用が可能なマルチマスタノード形式のデータベース管理技術を実現する。
【解決手段】下位マスタノードのセッションにおいて、データベースのシャドウコピーとメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして上位マスタノードに対して送信するステップと、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書込セットをアボートし、更新がない場合は前記シャドウコピーを用いて自身のデータベースを更新するステップと、トランザクション最小値がクラスタ最小値より小さい場合はアボートするステップと該最小値を有するトランザクションを廃棄するステップとを有する管理方法。
【解決手段】下位マスタノードのセッションにおいて、データベースのシャドウコピーとメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして上位マスタノードに対して送信するステップと、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書込セットをアボートし、更新がない場合は前記シャドウコピーを用いて自身のデータベースを更新するステップと、トランザクション最小値がクラスタ最小値より小さい場合はアボートするステップと該最小値を有するトランザクションを廃棄するステップとを有する管理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データベースの管理方法、特に複数のマスタノードがネットワークにより階層的に接続されているデータベースの管理方法に関する。
【背景技術】
【０００２】
PostgreSQLのような追記型のデータベースといえども、リソースを有効活用するためには、タプルを削除した後に一定時間経過したら当該タプルを完全消去(vacuum)することが望ましい。
【０００３】
しかし、トランザクションは実行開始から終了までを単一のスナップショットで管理するため、あるトランザクションによって特定のタプルが削除されたとしても、そのことによって即座に全てのトランザクションから当該タプルが参照されなくなるとは限らない。そのため、当該タプルを参照する一連のトランザクションが全てコミットされない限りそのタプルは完全消去されないことが原則である。もしそのタプルが削除されたとしても、その時点で実行中の他のスナップショット上では当該タプルが参照できるようにしておかなければならないのである。
【０００４】
そのため、PostgreSQLでは、トランザクション毎に付与されているトランザクションIDを利用して、各トランザクションのスナップショットからみてすでにコミットされているトランザクションIDを参照しながらどこまで完全消去すればよいかを判断する仕組みを採用していた。すなわち、各トランザクションのスナップショットで実行中とみなされているトランザクションIDのうち最小の値を計算し、その最小値のＩＤに合わせて完全消去する運用をしていたわけである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−２９３９１０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以上述べた運用はシングルノード構成のデータベースでの運用であるが、これをマルチマスタノードに適用した場合にはシングルノードシステムでは予期すらできない以下のような課題が発生することが本発明者によって見出された。
【０００７】
すなわち、マルチマスタノードシステムは、階層的に構築された膨大な数のノードで構成され、かつそのノード上で並列に同時実行される膨大なトランザクションを有している。そのため、ノード間の処理能力にばらつきがあった場合、一つのノードの処理遅延が全体の処理能力に影響を与えてしまうことになる。
【０００８】
そのため、マルチマスタノード構成のデータベースの場合、いつまでたっても完全消去できる最小値ＩＤの値が大きくならず、そのためにノード全体の完全消去処理の実効性が確保できなかった。
【０００９】
このため、強制的に最小値ＩＤをある程度の大きさの値に設定して完全消去処理を行ってしまう方法が考えられる。
ところで、この種のマルチマスタノード形式のデータベースにおいて、本発明者はその更新を効率的に矛盾無く行うために、下位のマスタノードのデータベースのシャドウコピ
ーと自身のメモリ上に展開されたヒープタプルマップとを書き込みセットとして上位マスタノードに送信してノード全体のデータベースの更新処理を統一する技術を提案している（特願２０１０−２３９７１３）。
【００１０】
ところで、この下位ノードで書き込みセットを生成して上位ノードに向けて送信している間に、書き込みセットの更新対象になっているタプルに対する完全消去命令が上位ノードから下位ノードに対して送信された場合、その後に前記書き込みセットを受信した上位ノードでは、既に完全消去されたはずのタプルを書き込みセットの内容に基づいて更新してしまう可能性があった。
【００１１】
そのため、マルチマスタノード形式のデータベースにおいても、データベース全体の整合性を崩すことなく、トランザクションの廃棄処理を行う必要があった。
【課題を解決するための手段】
【００１２】
前記課題を解決するために、本発明では以下の手段を採用した。
【００１３】
本発明の第１形態は、レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、上位マスタノードに対して、当該下位のマスタノードのデータベースのシャドウコピーと、自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書き込みセットとして送信するステップと、前記上位マスタノードにおいて、前記下位マスタノードから受信した書き込みセット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するとともに、この更新記録をトランザクションログとして生成するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信するステップと、前記下位マスタノードにおいて、前記で受信したトランザクションログに基づいて自身のデータベースを更新するステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該クラスタ最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなるマスタノードを階層的に有する追記型データベースの管理方法である。
【００１４】
また、本発明の第２形態は、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として上位マスタノードに通知し、前記上位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する前記第１形態記載の追記型データベースの管理方法である。
【００１５】
また、本発明の第３形態は、前記上位マスタノードと前記下位マスタノードとの間の階層に中位マスタノードを有しており、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として中位マスタノードに通知し、前記中位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とを比較して最も小さい値を当該中位マ
スタノードのツリー最小値として上位マスタノードに通知し、上位マスタノードは、自身のノード最小値と、前記１または２以上の中位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する第１形態記載の追記型データベースの管理方法である。
【００１６】
また、本発明の第４形態は、前記中位マスタノードはさらに２階層以上のツリー構造を有している第３形態記載の追記型データベースの管理方法である。
【００１７】
また、本発明の第５形態、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログの下位マスタノードへの通知とは非同期で行われる第１形態記載の追記型データベースの管理方法である。
【００１８】
この方法によれば、レプリケーション管理プロセスと非同期にクラスタ最小値を下位マスタノードに通知することにより、効率的なトランザクションＩＤの廃棄処理ができる。
【００１９】
また、本発明の第６形態は、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログに当該クラスタ最小値を含めて行われる第１形態記載の追記型データベースの管理方法である。
【００２０】
この方法によれば、レプリケーション管理プロセスの中にクラスタ最小値を含めることによって、通知順を強制することができるため、矛盾のないトランザクションＩＤの廃棄が可能になる。
【００２１】
また、本発明の第７形態は、前記書込セットは、下位マスタノードの代わりに中位マスタノードで生成され、少なくとも当該中位マスタノードで実行中のトランザクションが参照するスナップショットのトランザクション最小値が書き込まれている第３形態または第４形態記載の追記型データベースの管理方法である。
【００２２】
本発明の第８形態は、ノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、当該下位マスタノードのデータベースのシャドウコピーと、下位マスタノードのメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして上位マスタノードに対して送信させるステップと、前記で受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなる下位マスタノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法である。
【００２３】
本発明の第９形態は、レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースにおける下位マスタノードのデータベース管理方法であって、いずれかの下位マスタノードでデータベースへの更新命令が生じたときに、当該下位マスタノードのデータベース処理部が上位マスタノードに対して、自身のメモリ上に展開されたデータベースのシャドウコピーと、ヒープタプルマップと、実行中のトランザクションが参
照するスナップショットのトランザクション最小値とを書込セットとして生成する際に、それを受信する前記上位マスタノードに対して、前記下位マスタノードから受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きいときに前記シャドウコピーを用いて上位マスタノードのデータベースを更新させ、この更新記録をトランザクションログとして生成させ、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信させるために、前記書込セットを上位マスタノードに送信するステップと、前記下位マスタノードのトランザクションログ処理部は、前記トランザクションログを受信したときに、当該トランザクションログに基づいて自身のデータベースを更新するステップと、下位マスタノードにおいて、前記上位マスタノードが保持するクラスタ最小値を受信して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄するステップと、からなる下位マスタノードのデータベースの管理方法である。
【００２４】
本発明の第１０形態は、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として上位マスタノードに通知し、前記上位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する第８形態または第９形態記載の追記型データベースの管理方法である。
【００２５】
本発明の第１１形態は、前記上位マスタノードと前記下位マスタノードとの間の階層に中位マスタノードを有しており、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として中位マスタノードに通知し、前記中位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とを比較して最も小さい値を当該中位マスタノードのツリー最小値として上位マスタノードに通知し、上位マスタノードは、自身のノード最小値と、前記１または２以上の中位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する第８形態または第９形態記載の追記型データベースの管理方法である。
【００２６】
本発明の第１２形態は、前記中位マスタノードはさらに２階層以上のツリー構造を有している第１１形態記載の追記型データベースの管理方法である。
【００２７】
本発明の第１３形態は、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログの下位マスタノードへの通知とは非同期で行われる第８形態記載の追記型データベースの管理方法である。
【００２８】
本発明の第１４形態は、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログに当該クラスタ最小値を含めて行われる第８形態記載の追記型データベースの管理方法である。
【００２９】
本発明の第１５形態は、前記書込セットは、下位マスタノードの代わりに中位マスタノードで生成され、少なくとも当該中位マスタノードで実行中のトランザクションが参照するスナップショットのトランザクション最小値が書き込まれている第１１形態または第１２形態記載の追記型データベースの管理方法である。
【００３０】
本発明の第１６形態は、更新が可能な上位と１または２以上の下位のマスタノードを階層的に有する追記型データベースの管理方法であって、前記各下位マスタノードにおいて
、実行中のトランザクションが参照するスナップショットのトランザクション最小値同士を比較して最も小さい値であるノード最小値を前記上位マスタノードに送信するステップと、前記各下位マスタノードからのノード最小値を受信した上位マスタノードが、自身のノード最小値を読み出して前記で受信したノード最小値と比較して、これらの各ノード最小値の範囲内で上位マスタノードが保持するクラスタ最小値を決定・更新するステップと、前記上位マスタノードで更新されたクラスタ最小値を各下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなるマスタノードを階層的に有する追記型データベースの管理方法である。
【００３１】
本発明の第１７形態は、前記上位マスタノードと下位マスタノードとの２階層である第１６形態記載のマスタノードを階層的に有する追記型データベースの管理方法である。
【００３２】
本発明の第１８形態は、前記上位マスタノードと、１階層以上の中位マスタノードと、下位マスタノードとからなる少なくとも３階層以上であり、前記中位マスタノードも自身のノード最小値を前記上位マスタノードに送信するステップを実行するとともに、上位マスタノードは、前記各下位マスタノードと中位マスタノードからのノード最小値を受信して、自身のノード最小値を読み出して前記で受信したノード最小値と比較して、これらの各ノード最小値の範囲内で上位マスタノードが保持するクラスタ最小値を決定・更新するステップを実行する第１６形態記載のマスタノードを階層的に有する追記型データベースの管理方法である。
【００３３】
本発明の第１９形態は、レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、上位マスタノードに対して、当該下位のマスタノードのデータベースのシャドウコピーと、自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値と、ノード内のトランザクション最小値同士を比較して、最も小さい値であるノード最小値とを書き込みセットとして送信するステップと、前記上位マスタノードおいて、前記各書込セットから読み出したノード最小値と、自身が保持するノード最小値と比較して、これらの各ノード最小値の範囲内の値で上位マスタノードが保持するクラスタ最小値を決定・更新するステップと、前記上位マスタノードにおいて、前記下位マスタノードから受信した書き込みセット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するとともに、この更新記録をトランザクションログとして生成するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信するステップと、前記下位マスタノードにおいて、前記で受信したトランザクションログに基づいて自身のデータベースを更新するステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなるマスタノードを階層的に有する追記型データベースの管理方法である。
【００３４】
本発明の第２０形態は前記上位マスタノードと下位マスタノードとの間に、１階層以上の中位マスタノードを有しており、いずれかの中位マスタノードのセッションにおいて、上位マスタノードに対して、当該中位マスタノードのデータベースのシャドウコピーと、
自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値と、ノード内のトランザクション最小値同士を比較して、最も小さい値であるノード最小値を書き込みセットとして送信するステップとをさらに含む第１９形態記載のマスタノードを階層的に有する追記型データベースの管理方法である。
【００３５】
本発明の第２１形態は、更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、実行中のトランザクションが参照するスナップショットのトランザクション最小値を含む下位データベース更新情報を上位マスタノードに送信するステップと、前記下位データベース更新情報を受信した上位マスタノードにおいて、前記トランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、前記下位データベース更新情報に基づいて上位マスタノードのデータベースを更新するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該下位データベース更新情報をアボートするステップと、前記上位マスタノードの更新記録をトランザクションログとして生成するステップと、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信するステップと、前記下位マスタノードにおいて、前記で受信したトランザクションログに基づいて自身のデータベースを更新するステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなる下位マスタノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法である。
【００３６】
本発明の第２２形態は、前記下位データベース更新情報は、下位マスタノードのデータベースのシャドウコピーと、自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とからなる書込セットであり、上位マスタノードが前記書込セットを受信すると、トランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書込セットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、からなる第２１形態記載の追記型データベースの管理方法である。
【００３７】
本発明の第２３形態は、上記に加えて、上位と下位のマスタノードの間に１階層以上の中位マスタノードを有しており、いずれかの中位マスタノードのセッションにおいて、上位マスタノードに対して、当該中位マスタノードのデータベースの更新対象となったトランザクション最小値を含む中位データベース更新情報を上位マスタノードに送信するステップと、前記中位データベース更新情報を受信した上位マスタノードにおいて、前記トランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、前記中位データベース更新情報に基づいて上位マスタノードのデータベースを更新するステップと、を含む第２１形態または第２２形態記載の追記型データベースの管理方法である。
【発明の効果】
【００３８】
本発明によれば、マルチマスタノード形式のデータベースにおいても、データベース全体の整合性を崩すことなく、より大きな最小値ＩＤレベルでツリー全体の完全消去を実現することができる。
【図面の簡単な説明】
【００３９】
【図１】本願発明のマルチノード形式のデータベース構造を示す説明図
【図２】データベース制御部の構成を示すブロック図
【図３】書込みセットの内容を示す図
【図４】上位マスタノードにおける書込みセットの処理を示す説明図
【図５】トランザクションログデータの構成を示す説明図
【図６】マルチノード形式のデータベースツリー構造とトランザクション最小値とツリー最小値とノード最小値との関係を示す図
【図７】クラスタ最小値の更新と、そのクラスタ最小値を用いたトランザクションの廃棄処理の説明図
【図８】スナップショットの内容を示す図
【図９】書込セットの変形例を示す図
【発明を実施するための形態】
【００４０】
以下、本発明の実施の形態を図面を参照して説明する。
【実施例】
【００４１】
図１は、本実施形態の階層的マスタノードの構造を示している。同図に示すように、上位マスタノード（ＭＳ１０１）の下に階層的に中位マスタノード（ＭＳ２０１，ＭＳ２０２・・・ＭＳ２０ｎ）や、下位マスタノード（ＭＳ３０１，ＭＳ３０２・・・ＭＳ３０ｎ）を有するノード構成となっている。各ノード（情報処理装置）にはデータベースを有している。また上位マスタノード（ＭＳ１０１）にはスレーブを有しているが、他の下位マスタノードにもスレーブを有していてもよい。このようなマスタ・スレーブ構成の場合には両者間のデータベースの更新には本出願人によるＰＣＴ／ＪＰ２０１０／０５４３１１（本出願人による未公開先行出願）に記載された更新管理技術を適用することができる。
【００４２】
図２は、下位マスタノード（ＭＳ２０１）の機能ブロック図であるが、上位マスタノード（ＭＳ１０１）も同様の機能を有している。
同図に示すように、クライアント（ＣＬ）からデータベースの更新命令が入力されるとデータベース処理部（１１ｂ）は、メモリ（ＭＭ）上に構築されたバックエンドメモリ（ＢＥＭ）上に下位データベース更新情報を示す書込セットを生成する。この書込セットは図４に示すようにヒープタプルマップ（ＨＴＭ）とシャドウコピー（ＳＣ）とトランザクション最小値（Ｘｍｉｎ）とで構成される。ここでは、マスタデータベース（１０１ａ）の行番号４を削除（ＤＥＬＥＴＥ）し、行番号５を新たな値（ｓｃ１）に書き換える（ＵＰＤＡＴＥ）する更新命令が入力されたものと仮定する。
【００４３】
このとき、データベース処理部１１ｂは、マスタデータベース（１１ａ）を参照しながら当該マスタデータベース（１１ａ）に直接書き込むことは行わずに、バックエンドメモリ（ＢＥＭ）で生成された書込セットを通信モジュール（１１ｄ）より上位マスタに送信する。
このような処理は上位マスタノード（ＭＳ１０１）においても、下位マスタノード（ＭＳ２０１，ＭＳ２０２・・・ＭＳ２０ｎや、ＭＳ３０１，ＭＳ３０２・・・ＭＳ３０ｎ）においても同様である。
【００４４】
図８は、各ノード（上位ノード、中位ノードまたは下位ノード）におけるトランザクションとそのスナップショットとの関係を示している。各ノードでは複数のトランザクションが並行して実行されており、複数のそれぞれの時点での時系列にトランザクションの実行状態を示すスナップショットが複数保持されている。
【００４５】
同図においてこのノードでは、トランザクションＩＤ＝２，４，５，６および９が実行中である。また、トランザクションＩＤ＝１，３，７，８および１０はコミットされている。また、トランザクションＩＤ＝１１は未実行状態である。この時点でのスナップショットには、実行中またはコミットされたトランザクションの最大値をトランザクション最大値（ここではＸｍａｘ＝１０）として、実行中のトランザクションの最小値をトランザクション最小値（ここではＸｍｉｎ＝２）として記録されている。
【００４６】
このようなスナップショットは、前述のバックエンドメモリ（ＢＥＭ）に記録されるようになっている。
これらのスナップショット間の複数のトランザクション最小値の中で、最も小さい値がノード最小値となる。同図では、スナップショット７０１のトランザクション最小値が２（Ｘｍｉｎ＝２）であり、スナップショット７０２のトランザクション最小値が４（Ｘｍｉｎ＝４）であるので、ノード最小値は２（Ｎｍｉｎ＝２）となる。なお、下位マスタノードにさらに下位のノードが無い場合には、当該ノード最小値（Ｎｍｉｎ＝２）がツリー最小値（Ｔｍｉｎ＝２）となる。
【００４７】
下位マスタノード（たとえばＭＳ３０１）で生成されたノード最小値（Ｎｍｉｎ）、すなわちツリー最小値（Ｔｍｉｎ）は、後述する書込セットとは非同期で随時中位ノード（たとえばＭＳ２０１）に通知される。この中位マスタノード（ＭＳ２０１）ではそれぞれの下位マスタノード（ＭＳ３０１−ＭＳ３０ｎ）から受信したツリー最小値（Ｔｍｉｎ）と自身のスナップショット中のノード最小値（Ｎｍｉｎ）とを比較して、より小さい値を自身のツリー最小値（Ｔｍｉｎ）として更新する。
【００４８】
次に、それぞれの中位マスタノード（ＭＳ２０１−ＭＳ２０ｎ）のツリー最小値（Ｔｍｉｎ）は上位マスタノード（ＭＳ１０１）に通知される。
上位マスタノード（ＭＳ１０１）では、それぞれの中位マスタノード（ＭＳ２０１−ＭＳ２０ｎ）から受信したツリー最小値（Ｔｍｉｎ）を受信すると、自身のスナップショット中のノード最小値（Ｎｍｉｎ）とを比較して、いずれかの最小値またはその最小値間の値を採用して自身のツリー最小値（Ｔｍｉｎ）を更新する。そして、このツリー最小値（Ｔｍｉｎ）とその時点でのクラスタ最小値（Ｃｍｉｎ）を比較して、その間の値をとって新たなクラスタ最小値（Ｃｍｉｎ）を決定・更新する。
【００４９】
次に、図６を用いて下位マスタノードＥ，Ｆのノード最小値（Ｎｍｉｎ）すなわちツリー最小値（Ｔｍｉｎ）、中位マスタノードＢ，Ｃ，Ｄ，Ｅのツリー最小値（Ｔｍｉｎ）および上位マスタノードＡのツリー最小値（Ｔｍｉｎ）とクラスタ最小値（Ｃｍｉｎ）とが更新される状態を説明する。
【００５０】
ここで、下位マスタノードＦのトランザクション最小値（Ｘｍｉｎ）同士を比較した結果、ノード最小値（Ｎｍｉｎ）が３、下位マスタノードＧの最小値（Ｎｍｉｎ）が４の場合、これらの下位マスタノードＦ，Ｇにはさらに下の階層が無いので、これらのノード最小値（Ｎｍｉｎ）がそれぞれのツリー最小値（Ｔｍｉｎ）となる。
【００５１】
これらのツリー最小値（Ｔｍｉｎ＝３，Ｔｍｉｎ＝４）がそれぞれ中位マスタノードＤに通知される。
中位マスタノードＤでは、ノード最小値として４を有しており、これらが比較されて最も低い値（ここでは３）が中位ノードＤのツリー最小値として設定される（Ｔｍｉｎ＝３）。
【００５２】
一方、中位マスタノードＥでは、ノード最小値（Ｎｍｉｎ）が５であり、このノードは下位マスタノードを有していないため、当該ノード最小値（Ｎｍｉｎ＝５）がツリー最小
値（Ｔｍｉｎ＝５）として設定される。
【００５３】
中位マスタノードＣでは、中位マスタノードＤからのツリー最小値（Ｔｍｉｎ＝３）と中位マスタノードＥからのツリー最小値（Ｔｍｉｎ＝５）とを受信する。一方、中位マスタノードＣでは自身のノード最小値（Ｎｍｉｎ）として４を有しており、これらを比較して最も小さい値である３を自身のツリー最小値（Ｔｍｉｎ＝３）として更新する。そしてこのツリー最小値は上位マスタノードＡに通知される。
【００５４】
一方、同図では、前記中位マスタノードＣと並列な中位マスタノードＢが存在しているが、この中位マスタノードＢには下の階層のマスタノードが無いため、自身のノード最小値（Ｎｍｉｎ＝６）がそのままツリー最小値（Ｔｍｉｎ＝６）として上位マスタノードＡに通知される。
【００５５】
上位マスタノードＡでは、中位マスタノードＢからのツリー最小値（Ｔｍｉｎ＝６）と、中位マスタノードＣからのツリー最小値（Ｔｍｉｎ＝３）とを受信して、自身のノード最小値（Ｎｍｉｎ＝７）と比較して、これらの中で最も小さい値を上位マスタノードＡにおけるツリー最小値（Ｔｍｉｎ＝３）として更新する。
【００５６】
そしてマスタノードＡでは、自身のノード最小値（Ｎｍｉｎ＝７）と、更新されたツリー最小値（Ｔｍｉｎ＝３）との間の数値をクラスタ最小値（Ｃｍｉｎ）として設定する。
このときのクラスタ最小値（Ｃｍｉｎ）の決定基準としては、クラスタ最小値をより小さい値（たとえばＣｍｉｎ＝３）とすれば、全てのノードのスナップショット上のトランザクション最小値が３以上になるので、下位・中位マスタノードで生成される書込セットが上位マスタノードに到達したときにアボートされる確率は低くなり、無駄になる書込セットが少なくなり各ノードでの負荷は低減される。一方、完全消去の基準が小さい値となってしまうために、ノード全体の完全消去による効率的運用は図りにくくなる。
【００５７】
それとは逆に、クラスタ最小値（Ｃｍｉｎ）をより大きな値（たとえばＣｍｉｎ＝７）とすれば、完全消去の効率は良くなるが、中位・下位マスタノードで生成された書込セットが上位マスタノードに到着したときにアボートされる確率が高くなり、中位・下位マスタノードにおける書込セットの負荷は大きくなる。
【００５８】
このようなクラスタ最小値（Ｃｍｉｎ）の設定方法は、あらかじめノード最小値（Ｎｍｉｎ）とツリー最小値（Ｔｍｉｎ）との規定差分値を定めておき、この規定差分値を越えた場合には強制的に規定差分内となるような基準値に制御してもよい。
【００５９】
このようにクラスタ最小値（Ｃｍｉｎ）が設定されると、このクラスタ最小値（Ｃｍｉｎ）に基づいてタプルの完全消去が行われる。つまり、上位マスタノードにおいて、このクラスタ最小値（Ｃｍｉｎ）より小さいトランザクションＩＤを持つトランザクションによって削除されたタプルを完全消去することができる。そして上位マスタノードで完全消去されたタプルは、以下で説明するトランザクションの廃棄と書き込みセットのアボート処理とによって、中位・下位マスタノードでも安全に完全消去できることになる。
【００６０】
なお、以上の説明では、中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇがノード最小値（Ｎｍｉｎ）同士を比較してツリー最小値を更新しながら上位マスタノードＡに通知される例で説明したが、これに限定されることなく、各中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇがそれぞれ自身のノード最小値（Ｎｍｉｎ）を直接上位マスタノードＡに通知するようにしてもよい。上位マスタノードＡはこのようにして通知されたノード最小値（Ｎｍｉｎ）を自身が保持するノード最小値（Ｎｍｉｎ）と比較して、これらの範囲内で新たな値を決定してそれをクラスタ最小値（Ｃｍｉｎ）として更新すること
ができる。
【００６１】
このように各中位・下位マスタノードＢ−Ｇがそれぞれのノード最小値（Ｎｍｉｎ）を直接上位マスタノードＡに通知することにより、各階層でツリー最小値（Ｔｍｉｎ）を更新しながら上位マスタノードＡに通知する方式よりも複雑な処理が必要なく通知システムを簡略化できる。
さらに、中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇのそれぞれで書込セットを生成するときにヒープタプルマップ（ＨＴＭ）、シャドウコピー（ＳＣ）、トランザクション最小値（Ｘｍｉｎ）とともにノード最小値（Ｎｍｉｎ）を登録させるようにしてもよい（図９参照）。このように書込セット中にノード最小値（Ｎｍｉｎ）を登録して上位マスタノードＡに通知させることによって、上位マスタノードＡに対して書込セット以外の別の通知システムが不要となりシステムを簡略化できる。
【００６２】
この場合、上位マスタノードＡは、各中位マスタノードＢ−Ｅおよび下位マスタノードＦ，Ｇから直接送信されたそれぞれの書込セットからノード最小値（Ｎｍｉｎ）を読み出して、自身が保持するノード最小値（Ｎｍｉｎ）と比較して、これらの範囲内で新たな値を決定してそれをクラスタ最小値（Ｃｍｉｎ）として更新してもよい。
【００６３】
上位マスタノードＡにおいて、以上のようにクラスタ最小値（Ｃｍｉｎ）を更新した後は、前述と同じ処理が行われる。すなわち、前記上位マスタノードＡにおいて、前記中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇから受信した書き込みセット中のトランザクション最小値（Ｘｍｉｎ）と上位マスタノードＡが保持するクラスタ最小値（Ｃｍｉｎ）とを比較して、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップ（ＨＴＭ）と自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピー（ＳＣ）を用いて自身のデータベースを更新するとともに、この更新記録をトランザクションログとして生成する。一方、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）よりも小さい場合には、当該書き込みセットをアボートする。
【００６４】
上位マスタノードＡで設定・更新されたクラスタ最小値（たとえばＣｍｉｎ＝６）は、図７に示すように、中位マスタノードＢ，Ｃ，Ｄ，Ｅおよび下位マスタノードＦ，Ｇに通知される。このクラスタ最小値（Ｃｍｉｎ＝６）を受信した各ノードでは、この値（Ｃｍｉｎ＝６）よりも小さいトランザクション最小値を持つスナップショットを参照しているトランザクションを全て廃棄する。これによって、各ノードでのトランザクション最小値（Ｘｍｉｎ）、ノード最小値（Ｎｍｉｎ）、それらに基づくツリー最小値（Ｔｍｉｎ）は必ず６よりも大きな値をとる。したがって、クラスタ最小値（Ｃｍｉｎ）の通知後は完全消去されたタプルを参照するトランザクションは存在しなくなる。
【００６５】
なお、図６および図７では、上位マスタノードＡ、２階層の中位マスタノードＢ，Ｃ，Ｄ，Ｅ、下位マスタノードＥ，Ｆからなる４階層のツリー構造を有するマルチマスタノードで説明したが、上位マスタノードと下位マスタノードの２階層構造、または中位マスタノードが３階層以上すなわち全体で５階層以上のツリー構造を有していてもよい。
【００６６】
次に、図３を用いて書込セットの生成およびそれを用いた更新について説明する。
同図は、下位マスタノード（一例としてＭ３０１）におけるマスタデータベース（１１ａ）と、書込セットとの関係を示している。マスタデータベース（１１ａ）は行番号と、命令内容と、ポインタとによって構成されており、新たな命令がクライアント端末（ＣＬ）からなされる毎に行番号が追加されていく追記型のデータベースである。同図の場合、
前記で説明したように、行番号４を削除（ＤＥＬＥＴＥ）し、行番号５を新たな命令内容に書き換える（ｓｃ１にＵＰＤＡＴＥ）する場合を示している。
【００６７】
下位マスタノード（ＭＳ３０１）においてクライアント端末（ＣＬ）からの命令によりマスタデータベースに対してこのような更新命令がなされると、前述のように、バックエンドメモリ（ＢＥＭ）上でヒープタプルマップ（ＨＴＭ、ヒープファイル）とシャドウコピー（ＳＣ）とトランザクション最小値（Ｘｍｉｎ）からなる書込セットが生成される。
【００６８】
ヒープタプルマップ（ＨＴＭ）には、元の行番号（ｃｔｉｄ）と、新しい行の行番号（ｓｃｔｉｄ）が関係付けられて登録されるようになっている。このようにヒープタプルマップ（ＨＴＭ）はデータベースの更新毎に追加生成されていく。なお、行番号５の命令内容（ｓｃ１）が書き込まれる行番号はこの段階ではまだ不明であるため、ｓｃｔｉｄには新しい命令（ｓｃ１）を書き込んでおく。
【００６９】
一方、シャドウコピー（ＳＣ）には、マスタデータベース（１１ａ）を参照して書き換えられるべき行番号のシャドウコピーを生成する。このとき、新たに追加される行番号はこの段階では不明であるので、行番号には新たな命令（ｓｃ１）を書き込んでおく。
【００７０】
なお、この段階で下位マスタノード（ＭＳ３０１）のデータベース処理部（１１ｂ）は、ヒープタプルマップ（ＨＴＭ）の生成によりＤＥＬＥＴＥ命令が適用される行番号４と、ＵＰＤＡＴＥ命令が適用される旧行番号５は削除されることが既にわかるため、シャドウコピー（ＳＣ）としては新たな命令（ｓｃ１）だけを書き込んでおいてもよい。
【００７１】
さらに、書込セットに付加されるトランザクション最小値（Ｘｍｉｎ）は、前記で説明したように実行中のトランザクションが参照しているスナップショット上に記録されているトランザクション最小値（Ｘｍｉｎ）をそのまま書き込む。
【００７２】
このようにして生成された書込セットは、当該下位マスタノード（ＭＳ３０１）から中位マスタノード（たとえばＭＳ２０１）、さらに上位マスタノード（ＭＳ１０１）に送信される。
【００７３】
上位マスタノード（ＭＳ１０１）において、データベース処理部１１ｂ（中央処理装置（ＣＰＵ））は、前記で受信した書込セットからトランザクション最小値（Ｘｍｉｎ）を読み出す。そして、このトランザクション最小値（Ｘｍｉｎ）と上位マスタノード（ＭＳ１０１）のバックエンドメモリ（ＢＥＭ）に保持されたクラスタ最小値（Ｃｍｉｎ）と比較する。このとき、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）と等しいか大きいときには、トランザクションログ処理部（１１ｃ）を起動してトランザクションログデータの生成を開始した後に、以下の処理を行う。
【００７４】
まず、ヒープタプルマップ（ＨＴＭ）を読み出して、自身のマスタデータベース１１ａと比較する。ここで、ターゲットとなっているタプル（ここでは行番号４，５および７）の内容がデータベース（１１ａ）上で更新されているか否かを検証する。図４では、行番号４−６については未更新であるため、行番号４に削除ポインタを付与し、書き換えられる旧番号５にも削除ポインタを付与する。そして、新たな行番号７に新しい命令（ｓｃ１）が書き込まれる。
【００７５】
下位マスタノード（Ｍ３０１）からの書込セット中のヒープタプルマップ（ＨＴＭ）と自身のデータベースを比較して、上位マスタノード（Ｍ１０１）において既に別の書込セットによって当該行が更新されているときには、当該書込セットによる処理はアボート（中断）される。
【００７６】
一方、書込セット内のトランザクション最小値（Ｘｍｉｎ）とクラスタ最小値（Ｃｍｉｎ）と比較して、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）よりも小さいときには、当該書込セットをアボートする。
【００７７】
このように書込セットをアボート処理する理由を以下に説明する。
書込セットの中にはクラスタ最小値（Ｃｍｉｎ）よりも小さいトランザクションＩＤを持つトランザクションが削除したタプルが更新対象となっている可能性がある。このようなタプルは上位マスタノードのクラスタ最小値（Ｃｍｉｎ）の設定に基づいて、既に廃棄されている可能性が高い。その場合、ヒープタプルマップを用いてこのタプルに対する整合性検出ができないので、上位マスタノードに矛盾を生じてしまう。そのため、クラスタ最小値（Ｃｍｉｎ）よりも小さいトランザクション最小値（Ｘｍｉｎ）を有する書込セットをアボートして係る矛盾の発生を防止しているわけである。
【００７８】
クラスタ最小値（Ｃｍｉｎ）の通知によるトランザクションの廃棄が中位・下位マスタノードで完了すれば、このような書込セットは生成されない。しかし、クラスタ最小値（Ｃｍｉｎ）を上位マスタノードから下位マスタノードに通知している間に中位・下位マスタノードで生成された書込セットは、クラスタ最小値（Ｃｍｉｎ）より小さいトランザクション最小値を持つ可能性があるので、書込セットを上位マスタノードで適用する際にチェックする必要がある。そこで前述のように、書込セットに登録されたトランザクション最小値（Ｘｍｉｎ）とクラスタ最小値（Ｃｍｉｎ）とを比較して、トランザクション最小値（Ｘｍｉｎ）が小さい場合には書込セットをアボートするようにして解決しているわけである。
【００７９】
このように、クラスタ最小値（Ｃｍｉｎ）の通知により、完全消去されたタプルを参照するトランザクションを全て廃棄することができ、前記通知（Ｃｍｉｎ）の通知と入れ違いに作成された書き込みセットもクラスタ最小値（Ｃｍｉｎ）を基準にアボートできる。したがって、中位・下位ノードでもデータベースの整合性を損なわずにタプルを完全消去することができる。
【００８０】
図５は、上位マスタノード（ＭＳ１０１）のマスタデータベース（１１ａ）が上記により更新されたときにトランザクションログ処理部（１１ｃ）で生成されるトランザクションログデータの一例である。このトランザクションログは、少なくとも命令とトランザクション内容（行番号とそれに対する実行処理内容）が時系列で連続的に記録されたファイルである。
【００８１】
同図によればトランザクションの開始命令（ＸＢ１）に続いて、命令番号と行番号とが対になったログが順次生成されている。たとえば、最初にＤＥＬＥＴＥ命令（Ｄ１）として行番号４を削除し（Ｄ１４）、次にＵＰＤＡＴＥ命令（Ｕ１）として行番号５を削除し行番号７を追加し（Ｕ１５７）次にこれらのコミット命令（ＸＣ１）を発行する。なお、このトランザクションログデータには、クラスタ最小値（Ｃｍｉｎ＝６）を追加してもよい。このようにクラスタ最小値（Ｃｍｉｎ＝６）を含めることによって、中位マスタノードＢ，Ｃ，Ｄ，Ｅまたは下位マスタノードＦ，Ｇにおけるトランザクションの廃棄順を制御することが可能となる。
【００８２】
なお、前述したようにこのトランザクションログデータとは非同期にクラスタ最小値（Ｃｍｉｎ＝６）を中位マスタノードＢ，Ｃ，Ｄ，Ｅおよび下位マスタノードＦ，Ｇに通知する場合には、前述のトランザクションログデータの生成・送信を待つことなく効率的なトランザクションの廃棄処理が可能となる。
【００８３】
このトランザクションログデータは、通信モジュール（１１ｄ）より中位マスタノード（ＭＳ２０１）をはじめ、すべての下位マスタノード（ＭＳ３０２・・・ＭＳ３０ｎ）に対して配信される。
【００８４】
前記トランザクションログデータを受信した中位・下位マスタノードでは、当該トランザクションログデータを自身のデータベースに複製（レプリケーション）する。
具体的には、下位マスタノード（たとえばＭ３０２）が図５に示したトランザクションログデータを通信モジュール１１ｄで受信すると、トランザクションログ処理部１１ｃを起動してこのトランザクションログデータを自身のマスタデータベース１１ａにレプリケーションする。この結果、行番号４と５に削除ポインタが付与され、新たな行番号７が追加される。そして、このトランザクションログデータにクラスタ最小値（Ｃｍｉｎ＝６）が追記されている場合には、各マスタノードにおいて、このクラスタ最小値（Ｃｍｉｎ＝６）よりも小さいトランザクション最小値（Ｘｍｉｎ）を持つスナップショットを参照するトランザクションが全て廃棄される。
【００８５】
このように、中位・下位マスタノードでは上位マスタノードから送信されるトランザクションログデータのレプリケーションによって統一的にデータベースが管理されることになる。
【００８６】
以上、本発明を実施形態に基づいて説明したが、本発明はこれに限定されるものではない。以下、その変形例について説明する。
（上位マスタノードＭＳ１０１でデータベースの更新が行われる場合）
下位マスタノード（たとえばＭＳ３０１）でマスタデータベースの更新命令が発生した場合の処理については、図２で説明したように、バックエンドメモリ（ＢＥＭ）上でヒープタプルマップ（ＨＴＭ、ヒープファイル）とシャドウコピー（ＳＣ）とからなる書込セットが生成されるが、上位マスタノード（ＭＳ１０１）でマスタデータベースの更新命令が発生した場合には、上位ノードに通知する必要がないため、書込セットは生成されない。すなわち、このような場合、上位ノード（ＭＳ１０１）では、図４の左図に示すようにマスタデータベース（１１ａ）に対して直接更新データの書込が行われるとともに、図５に示すトランザクションログデータが生成される。このトランザクションログデータは下位マスタノードに配信され、前記トランザクションログデータを受信した下位マスタノードでは、当該トランザクションログデータを自身のマスタデータベースにレプリケーションする。
【００８７】
（下位マスタノードで書込セットを生成している段階で検索処理が実行されたとき）
下位マスタノード（たとえばＭＳ１０１）において、図３に示すような書込セットを生成している段階で、当該下位マスタノードのマスタデータベースに対して検索が実行されたとき、書込セットの生成された行番号以外の行番号を対象とした検索であれば問題はないが、該当行（ここでは行番号４および行番号５）に対する検索である場合、これらの行番号に対しては既に実質的な更新処理が行われているため、マスタデータベースの該当行を検索したとしても正確な検索結果は得られない。
【００８８】
このような場合、データベース処理部（１１ｂ）は、まずヒープタプルマップ（ＨＴＭ）を参照して、検索該当行番号がエントリされているか否かをチェックする。たとえば図３に示す例で、検索対象が行番号３である場合、データベース処理部（１１ｂ）は、メモリ（ＭＭ）上に構築されたバックエンドメモリ（ＢＥＭ）上の書込セット内のヒープタプルマップ（ＨＴＭ）を参照して、該当行（行番号３）がエントリされているか否かを判定する。図３の例では、該当行はエントリされていない。その場合には、マスタデータベース１１ａに直接アクセスして該当行（行番号３）を検索する。
【００８９】
一方、図３に示す例で、検索対象が行番号４である場合、データベース処理部（１１ｂ）は書込セット内のヒープタプルマップ（ＨＴＭ）を参照したときに、該当行（行番号４）がエントリされていることを検出することになる。この場合、マスタデータベース１１ａにアクセスしても、残存する該当行は既に削除する更新命令が実行されているため、検索対象としても意味がない。この場合、データベース処理部（１１ｂ）は、ヒープタプルマップ（ＨＴＭ）を参照して該当行（行番号４）が削除されていることを検出する。このように、検索対象行が削除されているため、データベース処理部（１１ｂ）は該当行を検索対象とはしない。
【００９０】
一方、図３に示す例で、検索対象が行番号５である場合、上記と同様に、ヒープタプルマップ（ＨＴＭ）を参照して該当行（行番号５）に対応するシャドウコピー（ＳＣ１）が作成されていることを検出する。
【００９１】
このとき、データベース処理部（１１ｂ）は、シャドウコピー（ＳＣ１）を参照して、行番号５を書き換えた内容を検索対象とすればよい。
以上の説明では、１行毎にヒープタプルマップ（ＨＴＭ）を参照する場合で説明したが、このような処理方法に限らず、検索を行う際にデータベース処理部（１１ｂ）は、まず一括的にヒープタプルマップ（ＨＴＭ）を参照して、ここにエントリされている行番号の全てを削除されたものとしてこれらを除外してマスタデータベース（１１ａ）を検索しその後、再度ヒープタプルマップ（ＨＴＭ）を参照してそのエントリに基づいて該当行を検索対象から除外したり（行番号４の場合）、シャドウコピー（ＳＣ１）を検索対象としてもよい。
【００９２】
（下位マスタノードで上位マスタノードからのトランザクションログデータによる更新が行われているときの競合が生じた場合）
上位マスタノードから配信されたトランザクションログデータによって下位マスタノードのデータベースにレプリケーションが行われているときに、該当行に対して下位マスタノードのデータベースの更新命令が実行されている場合、競合が発生することになる。
【００９３】
具体的には、下位マスタノードへの更新命令に基づいて行番号４と５とを更新しているときに、上位マスタノードから行番号５に関するトランザクションログデータが配信されてきたときがこれに該当する。
【００９４】
このような場合には、下位マスタノードで作成された書込セットが上位マスタノードに送信されたとしても、上位マスタノードでは既に該当行に関するトランザクションログデータが配信されているため、前記書込セットは上位マスタノードで競合が検出されてアボートされることになる。したがって、当該下位マスタノードにおける競合は無視して差し支えない。この方法によれば、上位マスタノードにおいて本来アボートされるのがわかっているような書込セットでも上位マスタノードに送信しなければならず、上位マスタノードおよび下位マスタノードでのそれぞれの負担は増加するものの、上位マスタノードからのトランザクションログデータを下位マスタノードでレプリケーションする段階で一々競合のチェックを行わなくてよいため、処理が高速化できるという利点がある。
【００９５】
一方、このような下位マスタノードでの競合を解決する別の方法としては、下位マスタノードにおいてヒープタプルマップ（ＨＴＭ）を生成したときに、これを当該下位マスタノード内のメモリに登録し、このメモリを共有メモリとして、他の下位マスタノードからアクセス可能な状態としておく。このような他の下位ノードマスタ間のアクセスは、それぞれの下位マスタノードのデータベース処理部１１ｂが行う。この方法によれば、ヒープタプルマップ（ＨＴＭ）の生成時に競合をチェックするため、トランザクションログデータによるレプリケーションが遅延する可能性はあるものの、競合の問題を下位マスタノー
ド間だけで解決できるので、上位マスタノードに負担をかけない。
【００９６】
以上、本発明を実施形態に基づいて説明したがこれらに限定されるものではない。
たとえば、書込セットは下位マスタノード（ＭＳ３０１）で生成する場合で説明したがこれに限らず中位マスタノード（ＭＳ２０１）で生成してもよいことは勿論である。
【産業上の利用可能性】
【００９７】
本発明は、階層構造を備えたマルチマスタノード構造のデータベース管理システムに利用できる。
【符号の説明】
【００９８】
ＭＳ１０１ 上位マスタノード
ＳＬ スレーブ
ＭＳ２０１，ＭＳ２０２・・・ＭＳ２０ｎ 中位マスタノード
ＭＳ３０１，ＭＳ３０２・・・ＭＳ３０ｎ 下位マスタノード
ＣＬ クライアント端末
１１ａ マスタデータベース
１１ｂ データベース処理部
１１ｃ トランザクションログ処理部
１１ｄ 通信モジュール
ＢＥＭ バックエンドメモリ
ＨＴＭ ヒープタプルマップ
ＳＣ シャドウコピー
Ｃｍｉｎ クラスタ最小値
Ｘｍｉｎ トランザクション最小値
【技術分野】
【０００１】
本発明は、データベースの管理方法、特に複数のマスタノードがネットワークにより階層的に接続されているデータベースの管理方法に関する。
【背景技術】
【０００２】
PostgreSQLのような追記型のデータベースといえども、リソースを有効活用するためには、タプルを削除した後に一定時間経過したら当該タプルを完全消去(vacuum)することが望ましい。
【０００３】
しかし、トランザクションは実行開始から終了までを単一のスナップショットで管理するため、あるトランザクションによって特定のタプルが削除されたとしても、そのことによって即座に全てのトランザクションから当該タプルが参照されなくなるとは限らない。そのため、当該タプルを参照する一連のトランザクションが全てコミットされない限りそのタプルは完全消去されないことが原則である。もしそのタプルが削除されたとしても、その時点で実行中の他のスナップショット上では当該タプルが参照できるようにしておかなければならないのである。
【０００４】
そのため、PostgreSQLでは、トランザクション毎に付与されているトランザクションIDを利用して、各トランザクションのスナップショットからみてすでにコミットされているトランザクションIDを参照しながらどこまで完全消去すればよいかを判断する仕組みを採用していた。すなわち、各トランザクションのスナップショットで実行中とみなされているトランザクションIDのうち最小の値を計算し、その最小値のＩＤに合わせて完全消去する運用をしていたわけである。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００６−２９３９１０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
以上述べた運用はシングルノード構成のデータベースでの運用であるが、これをマルチマスタノードに適用した場合にはシングルノードシステムでは予期すらできない以下のような課題が発生することが本発明者によって見出された。
【０００７】
すなわち、マルチマスタノードシステムは、階層的に構築された膨大な数のノードで構成され、かつそのノード上で並列に同時実行される膨大なトランザクションを有している。そのため、ノード間の処理能力にばらつきがあった場合、一つのノードの処理遅延が全体の処理能力に影響を与えてしまうことになる。
【０００８】
そのため、マルチマスタノード構成のデータベースの場合、いつまでたっても完全消去できる最小値ＩＤの値が大きくならず、そのためにノード全体の完全消去処理の実効性が確保できなかった。
【０００９】
このため、強制的に最小値ＩＤをある程度の大きさの値に設定して完全消去処理を行ってしまう方法が考えられる。
ところで、この種のマルチマスタノード形式のデータベースにおいて、本発明者はその更新を効率的に矛盾無く行うために、下位のマスタノードのデータベースのシャドウコピ
ーと自身のメモリ上に展開されたヒープタプルマップとを書き込みセットとして上位マスタノードに送信してノード全体のデータベースの更新処理を統一する技術を提案している（特願２０１０−２３９７１３）。
【００１０】
ところで、この下位ノードで書き込みセットを生成して上位ノードに向けて送信している間に、書き込みセットの更新対象になっているタプルに対する完全消去命令が上位ノードから下位ノードに対して送信された場合、その後に前記書き込みセットを受信した上位ノードでは、既に完全消去されたはずのタプルを書き込みセットの内容に基づいて更新してしまう可能性があった。
【００１１】
そのため、マルチマスタノード形式のデータベースにおいても、データベース全体の整合性を崩すことなく、トランザクションの廃棄処理を行う必要があった。
【課題を解決するための手段】
【００１２】
前記課題を解決するために、本発明では以下の手段を採用した。
【００１３】
本発明の第１形態は、レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、上位マスタノードに対して、当該下位のマスタノードのデータベースのシャドウコピーと、自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書き込みセットとして送信するステップと、前記上位マスタノードにおいて、前記下位マスタノードから受信した書き込みセット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するとともに、この更新記録をトランザクションログとして生成するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信するステップと、前記下位マスタノードにおいて、前記で受信したトランザクションログに基づいて自身のデータベースを更新するステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該クラスタ最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなるマスタノードを階層的に有する追記型データベースの管理方法である。
【００１４】
また、本発明の第２形態は、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として上位マスタノードに通知し、前記上位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する前記第１形態記載の追記型データベースの管理方法である。
【００１５】
また、本発明の第３形態は、前記上位マスタノードと前記下位マスタノードとの間の階層に中位マスタノードを有しており、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として中位マスタノードに通知し、前記中位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とを比較して最も小さい値を当該中位マ
スタノードのツリー最小値として上位マスタノードに通知し、上位マスタノードは、自身のノード最小値と、前記１または２以上の中位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する第１形態記載の追記型データベースの管理方法である。
【００１６】
また、本発明の第４形態は、前記中位マスタノードはさらに２階層以上のツリー構造を有している第３形態記載の追記型データベースの管理方法である。
【００１７】
また、本発明の第５形態、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログの下位マスタノードへの通知とは非同期で行われる第１形態記載の追記型データベースの管理方法である。
【００１８】
この方法によれば、レプリケーション管理プロセスと非同期にクラスタ最小値を下位マスタノードに通知することにより、効率的なトランザクションＩＤの廃棄処理ができる。
【００１９】
また、本発明の第６形態は、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログに当該クラスタ最小値を含めて行われる第１形態記載の追記型データベースの管理方法である。
【００２０】
この方法によれば、レプリケーション管理プロセスの中にクラスタ最小値を含めることによって、通知順を強制することができるため、矛盾のないトランザクションＩＤの廃棄が可能になる。
【００２１】
また、本発明の第７形態は、前記書込セットは、下位マスタノードの代わりに中位マスタノードで生成され、少なくとも当該中位マスタノードで実行中のトランザクションが参照するスナップショットのトランザクション最小値が書き込まれている第３形態または第４形態記載の追記型データベースの管理方法である。
【００２２】
本発明の第８形態は、ノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、当該下位マスタノードのデータベースのシャドウコピーと、下位マスタノードのメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして上位マスタノードに対して送信させるステップと、前記で受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなる下位マスタノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法である。
【００２３】
本発明の第９形態は、レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースにおける下位マスタノードのデータベース管理方法であって、いずれかの下位マスタノードでデータベースへの更新命令が生じたときに、当該下位マスタノードのデータベース処理部が上位マスタノードに対して、自身のメモリ上に展開されたデータベースのシャドウコピーと、ヒープタプルマップと、実行中のトランザクションが参
照するスナップショットのトランザクション最小値とを書込セットとして生成する際に、それを受信する前記上位マスタノードに対して、前記下位マスタノードから受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きいときに前記シャドウコピーを用いて上位マスタノードのデータベースを更新させ、この更新記録をトランザクションログとして生成させ、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信させるために、前記書込セットを上位マスタノードに送信するステップと、前記下位マスタノードのトランザクションログ処理部は、前記トランザクションログを受信したときに、当該トランザクションログに基づいて自身のデータベースを更新するステップと、下位マスタノードにおいて、前記上位マスタノードが保持するクラスタ最小値を受信して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄するステップと、からなる下位マスタノードのデータベースの管理方法である。
【００２４】
本発明の第１０形態は、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として上位マスタノードに通知し、前記上位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する第８形態または第９形態記載の追記型データベースの管理方法である。
【００２５】
本発明の第１１形態は、前記上位マスタノードと前記下位マスタノードとの間の階層に中位マスタノードを有しており、前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として中位マスタノードに通知し、前記中位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とを比較して最も小さい値を当該中位マスタノードのツリー最小値として上位マスタノードに通知し、上位マスタノードは、自身のノード最小値と、前記１または２以上の中位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する第８形態または第９形態記載の追記型データベースの管理方法である。
【００２６】
本発明の第１２形態は、前記中位マスタノードはさらに２階層以上のツリー構造を有している第１１形態記載の追記型データベースの管理方法である。
【００２７】
本発明の第１３形態は、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログの下位マスタノードへの通知とは非同期で行われる第８形態記載の追記型データベースの管理方法である。
【００２８】
本発明の第１４形態は、前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログに当該クラスタ最小値を含めて行われる第８形態記載の追記型データベースの管理方法である。
【００２９】
本発明の第１５形態は、前記書込セットは、下位マスタノードの代わりに中位マスタノードで生成され、少なくとも当該中位マスタノードで実行中のトランザクションが参照するスナップショットのトランザクション最小値が書き込まれている第１１形態または第１２形態記載の追記型データベースの管理方法である。
【００３０】
本発明の第１６形態は、更新が可能な上位と１または２以上の下位のマスタノードを階層的に有する追記型データベースの管理方法であって、前記各下位マスタノードにおいて
、実行中のトランザクションが参照するスナップショットのトランザクション最小値同士を比較して最も小さい値であるノード最小値を前記上位マスタノードに送信するステップと、前記各下位マスタノードからのノード最小値を受信した上位マスタノードが、自身のノード最小値を読み出して前記で受信したノード最小値と比較して、これらの各ノード最小値の範囲内で上位マスタノードが保持するクラスタ最小値を決定・更新するステップと、前記上位マスタノードで更新されたクラスタ最小値を各下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなるマスタノードを階層的に有する追記型データベースの管理方法である。
【００３１】
本発明の第１７形態は、前記上位マスタノードと下位マスタノードとの２階層である第１６形態記載のマスタノードを階層的に有する追記型データベースの管理方法である。
【００３２】
本発明の第１８形態は、前記上位マスタノードと、１階層以上の中位マスタノードと、下位マスタノードとからなる少なくとも３階層以上であり、前記中位マスタノードも自身のノード最小値を前記上位マスタノードに送信するステップを実行するとともに、上位マスタノードは、前記各下位マスタノードと中位マスタノードからのノード最小値を受信して、自身のノード最小値を読み出して前記で受信したノード最小値と比較して、これらの各ノード最小値の範囲内で上位マスタノードが保持するクラスタ最小値を決定・更新するステップを実行する第１６形態記載のマスタノードを階層的に有する追記型データベースの管理方法である。
【００３３】
本発明の第１９形態は、レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、上位マスタノードに対して、当該下位のマスタノードのデータベースのシャドウコピーと、自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値と、ノード内のトランザクション最小値同士を比較して、最も小さい値であるノード最小値とを書き込みセットとして送信するステップと、前記上位マスタノードおいて、前記各書込セットから読み出したノード最小値と、自身が保持するノード最小値と比較して、これらの各ノード最小値の範囲内の値で上位マスタノードが保持するクラスタ最小値を決定・更新するステップと、前記上位マスタノードにおいて、前記下位マスタノードから受信した書き込みセット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するとともに、この更新記録をトランザクションログとして生成するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信するステップと、前記下位マスタノードにおいて、前記で受信したトランザクションログに基づいて自身のデータベースを更新するステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなるマスタノードを階層的に有する追記型データベースの管理方法である。
【００３４】
本発明の第２０形態は前記上位マスタノードと下位マスタノードとの間に、１階層以上の中位マスタノードを有しており、いずれかの中位マスタノードのセッションにおいて、上位マスタノードに対して、当該中位マスタノードのデータベースのシャドウコピーと、
自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値と、ノード内のトランザクション最小値同士を比較して、最も小さい値であるノード最小値を書き込みセットとして送信するステップとをさらに含む第１９形態記載のマスタノードを階層的に有する追記型データベースの管理方法である。
【００３５】
本発明の第２１形態は、更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースの管理方法であって、いずれかの下位マスタノードのセッションにおいて、実行中のトランザクションが参照するスナップショットのトランザクション最小値を含む下位データベース更新情報を上位マスタノードに送信するステップと、前記下位データベース更新情報を受信した上位マスタノードにおいて、前記トランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、前記下位データベース更新情報に基づいて上位マスタノードのデータベースを更新するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該下位データベース更新情報をアボートするステップと、前記上位マスタノードの更新記録をトランザクションログとして生成するステップと、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信するステップと、前記下位マスタノードにおいて、前記で受信したトランザクションログに基づいて自身のデータベースを更新するステップと、前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、からなる下位マスタノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法である。
【００３６】
本発明の第２２形態は、前記下位データベース更新情報は、下位マスタノードのデータベースのシャドウコピーと、自身のメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とからなる書込セットであり、上位マスタノードが前記書込セットを受信すると、トランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書込セットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するステップと、前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、からなる第２１形態記載の追記型データベースの管理方法である。
【００３７】
本発明の第２３形態は、上記に加えて、上位と下位のマスタノードの間に１階層以上の中位マスタノードを有しており、いずれかの中位マスタノードのセッションにおいて、上位マスタノードに対して、当該中位マスタノードのデータベースの更新対象となったトランザクション最小値を含む中位データベース更新情報を上位マスタノードに送信するステップと、前記中位データベース更新情報を受信した上位マスタノードにおいて、前記トランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、前記中位データベース更新情報に基づいて上位マスタノードのデータベースを更新するステップと、を含む第２１形態または第２２形態記載の追記型データベースの管理方法である。
【発明の効果】
【００３８】
本発明によれば、マルチマスタノード形式のデータベースにおいても、データベース全体の整合性を崩すことなく、より大きな最小値ＩＤレベルでツリー全体の完全消去を実現することができる。
【図面の簡単な説明】
【００３９】
【図１】本願発明のマルチノード形式のデータベース構造を示す説明図
【図２】データベース制御部の構成を示すブロック図
【図３】書込みセットの内容を示す図
【図４】上位マスタノードにおける書込みセットの処理を示す説明図
【図５】トランザクションログデータの構成を示す説明図
【図６】マルチノード形式のデータベースツリー構造とトランザクション最小値とツリー最小値とノード最小値との関係を示す図
【図７】クラスタ最小値の更新と、そのクラスタ最小値を用いたトランザクションの廃棄処理の説明図
【図８】スナップショットの内容を示す図
【図９】書込セットの変形例を示す図
【発明を実施するための形態】
【００４０】
以下、本発明の実施の形態を図面を参照して説明する。
【実施例】
【００４１】
図１は、本実施形態の階層的マスタノードの構造を示している。同図に示すように、上位マスタノード（ＭＳ１０１）の下に階層的に中位マスタノード（ＭＳ２０１，ＭＳ２０２・・・ＭＳ２０ｎ）や、下位マスタノード（ＭＳ３０１，ＭＳ３０２・・・ＭＳ３０ｎ）を有するノード構成となっている。各ノード（情報処理装置）にはデータベースを有している。また上位マスタノード（ＭＳ１０１）にはスレーブを有しているが、他の下位マスタノードにもスレーブを有していてもよい。このようなマスタ・スレーブ構成の場合には両者間のデータベースの更新には本出願人によるＰＣＴ／ＪＰ２０１０／０５４３１１（本出願人による未公開先行出願）に記載された更新管理技術を適用することができる。
【００４２】
図２は、下位マスタノード（ＭＳ２０１）の機能ブロック図であるが、上位マスタノード（ＭＳ１０１）も同様の機能を有している。
同図に示すように、クライアント（ＣＬ）からデータベースの更新命令が入力されるとデータベース処理部（１１ｂ）は、メモリ（ＭＭ）上に構築されたバックエンドメモリ（ＢＥＭ）上に下位データベース更新情報を示す書込セットを生成する。この書込セットは図４に示すようにヒープタプルマップ（ＨＴＭ）とシャドウコピー（ＳＣ）とトランザクション最小値（Ｘｍｉｎ）とで構成される。ここでは、マスタデータベース（１０１ａ）の行番号４を削除（ＤＥＬＥＴＥ）し、行番号５を新たな値（ｓｃ１）に書き換える（ＵＰＤＡＴＥ）する更新命令が入力されたものと仮定する。
【００４３】
このとき、データベース処理部１１ｂは、マスタデータベース（１１ａ）を参照しながら当該マスタデータベース（１１ａ）に直接書き込むことは行わずに、バックエンドメモリ（ＢＥＭ）で生成された書込セットを通信モジュール（１１ｄ）より上位マスタに送信する。
このような処理は上位マスタノード（ＭＳ１０１）においても、下位マスタノード（ＭＳ２０１，ＭＳ２０２・・・ＭＳ２０ｎや、ＭＳ３０１，ＭＳ３０２・・・ＭＳ３０ｎ）においても同様である。
【００４４】
図８は、各ノード（上位ノード、中位ノードまたは下位ノード）におけるトランザクションとそのスナップショットとの関係を示している。各ノードでは複数のトランザクションが並行して実行されており、複数のそれぞれの時点での時系列にトランザクションの実行状態を示すスナップショットが複数保持されている。
【００４５】
同図においてこのノードでは、トランザクションＩＤ＝２，４，５，６および９が実行中である。また、トランザクションＩＤ＝１，３，７，８および１０はコミットされている。また、トランザクションＩＤ＝１１は未実行状態である。この時点でのスナップショットには、実行中またはコミットされたトランザクションの最大値をトランザクション最大値（ここではＸｍａｘ＝１０）として、実行中のトランザクションの最小値をトランザクション最小値（ここではＸｍｉｎ＝２）として記録されている。
【００４６】
このようなスナップショットは、前述のバックエンドメモリ（ＢＥＭ）に記録されるようになっている。
これらのスナップショット間の複数のトランザクション最小値の中で、最も小さい値がノード最小値となる。同図では、スナップショット７０１のトランザクション最小値が２（Ｘｍｉｎ＝２）であり、スナップショット７０２のトランザクション最小値が４（Ｘｍｉｎ＝４）であるので、ノード最小値は２（Ｎｍｉｎ＝２）となる。なお、下位マスタノードにさらに下位のノードが無い場合には、当該ノード最小値（Ｎｍｉｎ＝２）がツリー最小値（Ｔｍｉｎ＝２）となる。
【００４７】
下位マスタノード（たとえばＭＳ３０１）で生成されたノード最小値（Ｎｍｉｎ）、すなわちツリー最小値（Ｔｍｉｎ）は、後述する書込セットとは非同期で随時中位ノード（たとえばＭＳ２０１）に通知される。この中位マスタノード（ＭＳ２０１）ではそれぞれの下位マスタノード（ＭＳ３０１−ＭＳ３０ｎ）から受信したツリー最小値（Ｔｍｉｎ）と自身のスナップショット中のノード最小値（Ｎｍｉｎ）とを比較して、より小さい値を自身のツリー最小値（Ｔｍｉｎ）として更新する。
【００４８】
次に、それぞれの中位マスタノード（ＭＳ２０１−ＭＳ２０ｎ）のツリー最小値（Ｔｍｉｎ）は上位マスタノード（ＭＳ１０１）に通知される。
上位マスタノード（ＭＳ１０１）では、それぞれの中位マスタノード（ＭＳ２０１−ＭＳ２０ｎ）から受信したツリー最小値（Ｔｍｉｎ）を受信すると、自身のスナップショット中のノード最小値（Ｎｍｉｎ）とを比較して、いずれかの最小値またはその最小値間の値を採用して自身のツリー最小値（Ｔｍｉｎ）を更新する。そして、このツリー最小値（Ｔｍｉｎ）とその時点でのクラスタ最小値（Ｃｍｉｎ）を比較して、その間の値をとって新たなクラスタ最小値（Ｃｍｉｎ）を決定・更新する。
【００４９】
次に、図６を用いて下位マスタノードＥ，Ｆのノード最小値（Ｎｍｉｎ）すなわちツリー最小値（Ｔｍｉｎ）、中位マスタノードＢ，Ｃ，Ｄ，Ｅのツリー最小値（Ｔｍｉｎ）および上位マスタノードＡのツリー最小値（Ｔｍｉｎ）とクラスタ最小値（Ｃｍｉｎ）とが更新される状態を説明する。
【００５０】
ここで、下位マスタノードＦのトランザクション最小値（Ｘｍｉｎ）同士を比較した結果、ノード最小値（Ｎｍｉｎ）が３、下位マスタノードＧの最小値（Ｎｍｉｎ）が４の場合、これらの下位マスタノードＦ，Ｇにはさらに下の階層が無いので、これらのノード最小値（Ｎｍｉｎ）がそれぞれのツリー最小値（Ｔｍｉｎ）となる。
【００５１】
これらのツリー最小値（Ｔｍｉｎ＝３，Ｔｍｉｎ＝４）がそれぞれ中位マスタノードＤに通知される。
中位マスタノードＤでは、ノード最小値として４を有しており、これらが比較されて最も低い値（ここでは３）が中位ノードＤのツリー最小値として設定される（Ｔｍｉｎ＝３）。
【００５２】
一方、中位マスタノードＥでは、ノード最小値（Ｎｍｉｎ）が５であり、このノードは下位マスタノードを有していないため、当該ノード最小値（Ｎｍｉｎ＝５）がツリー最小
値（Ｔｍｉｎ＝５）として設定される。
【００５３】
中位マスタノードＣでは、中位マスタノードＤからのツリー最小値（Ｔｍｉｎ＝３）と中位マスタノードＥからのツリー最小値（Ｔｍｉｎ＝５）とを受信する。一方、中位マスタノードＣでは自身のノード最小値（Ｎｍｉｎ）として４を有しており、これらを比較して最も小さい値である３を自身のツリー最小値（Ｔｍｉｎ＝３）として更新する。そしてこのツリー最小値は上位マスタノードＡに通知される。
【００５４】
一方、同図では、前記中位マスタノードＣと並列な中位マスタノードＢが存在しているが、この中位マスタノードＢには下の階層のマスタノードが無いため、自身のノード最小値（Ｎｍｉｎ＝６）がそのままツリー最小値（Ｔｍｉｎ＝６）として上位マスタノードＡに通知される。
【００５５】
上位マスタノードＡでは、中位マスタノードＢからのツリー最小値（Ｔｍｉｎ＝６）と、中位マスタノードＣからのツリー最小値（Ｔｍｉｎ＝３）とを受信して、自身のノード最小値（Ｎｍｉｎ＝７）と比較して、これらの中で最も小さい値を上位マスタノードＡにおけるツリー最小値（Ｔｍｉｎ＝３）として更新する。
【００５６】
そしてマスタノードＡでは、自身のノード最小値（Ｎｍｉｎ＝７）と、更新されたツリー最小値（Ｔｍｉｎ＝３）との間の数値をクラスタ最小値（Ｃｍｉｎ）として設定する。
このときのクラスタ最小値（Ｃｍｉｎ）の決定基準としては、クラスタ最小値をより小さい値（たとえばＣｍｉｎ＝３）とすれば、全てのノードのスナップショット上のトランザクション最小値が３以上になるので、下位・中位マスタノードで生成される書込セットが上位マスタノードに到達したときにアボートされる確率は低くなり、無駄になる書込セットが少なくなり各ノードでの負荷は低減される。一方、完全消去の基準が小さい値となってしまうために、ノード全体の完全消去による効率的運用は図りにくくなる。
【００５７】
それとは逆に、クラスタ最小値（Ｃｍｉｎ）をより大きな値（たとえばＣｍｉｎ＝７）とすれば、完全消去の効率は良くなるが、中位・下位マスタノードで生成された書込セットが上位マスタノードに到着したときにアボートされる確率が高くなり、中位・下位マスタノードにおける書込セットの負荷は大きくなる。
【００５８】
このようなクラスタ最小値（Ｃｍｉｎ）の設定方法は、あらかじめノード最小値（Ｎｍｉｎ）とツリー最小値（Ｔｍｉｎ）との規定差分値を定めておき、この規定差分値を越えた場合には強制的に規定差分内となるような基準値に制御してもよい。
【００５９】
このようにクラスタ最小値（Ｃｍｉｎ）が設定されると、このクラスタ最小値（Ｃｍｉｎ）に基づいてタプルの完全消去が行われる。つまり、上位マスタノードにおいて、このクラスタ最小値（Ｃｍｉｎ）より小さいトランザクションＩＤを持つトランザクションによって削除されたタプルを完全消去することができる。そして上位マスタノードで完全消去されたタプルは、以下で説明するトランザクションの廃棄と書き込みセットのアボート処理とによって、中位・下位マスタノードでも安全に完全消去できることになる。
【００６０】
なお、以上の説明では、中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇがノード最小値（Ｎｍｉｎ）同士を比較してツリー最小値を更新しながら上位マスタノードＡに通知される例で説明したが、これに限定されることなく、各中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇがそれぞれ自身のノード最小値（Ｎｍｉｎ）を直接上位マスタノードＡに通知するようにしてもよい。上位マスタノードＡはこのようにして通知されたノード最小値（Ｎｍｉｎ）を自身が保持するノード最小値（Ｎｍｉｎ）と比較して、これらの範囲内で新たな値を決定してそれをクラスタ最小値（Ｃｍｉｎ）として更新すること
ができる。
【００６１】
このように各中位・下位マスタノードＢ−Ｇがそれぞれのノード最小値（Ｎｍｉｎ）を直接上位マスタノードＡに通知することにより、各階層でツリー最小値（Ｔｍｉｎ）を更新しながら上位マスタノードＡに通知する方式よりも複雑な処理が必要なく通知システムを簡略化できる。
さらに、中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇのそれぞれで書込セットを生成するときにヒープタプルマップ（ＨＴＭ）、シャドウコピー（ＳＣ）、トランザクション最小値（Ｘｍｉｎ）とともにノード最小値（Ｎｍｉｎ）を登録させるようにしてもよい（図９参照）。このように書込セット中にノード最小値（Ｎｍｉｎ）を登録して上位マスタノードＡに通知させることによって、上位マスタノードＡに対して書込セット以外の別の通知システムが不要となりシステムを簡略化できる。
【００６２】
この場合、上位マスタノードＡは、各中位マスタノードＢ−Ｅおよび下位マスタノードＦ，Ｇから直接送信されたそれぞれの書込セットからノード最小値（Ｎｍｉｎ）を読み出して、自身が保持するノード最小値（Ｎｍｉｎ）と比較して、これらの範囲内で新たな値を決定してそれをクラスタ最小値（Ｃｍｉｎ）として更新してもよい。
【００６３】
上位マスタノードＡにおいて、以上のようにクラスタ最小値（Ｃｍｉｎ）を更新した後は、前述と同じ処理が行われる。すなわち、前記上位マスタノードＡにおいて、前記中位マスタノードＢ−Ｅまたは下位マスタノードＦ，Ｇから受信した書き込みセット中のトランザクション最小値（Ｘｍｉｎ）と上位マスタノードＡが保持するクラスタ最小値（Ｃｍｉｎ）とを比較して、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップ（ＨＴＭ）と自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピー（ＳＣ）を用いて自身のデータベースを更新するとともに、この更新記録をトランザクションログとして生成する。一方、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）よりも小さい場合には、当該書き込みセットをアボートする。
【００６４】
上位マスタノードＡで設定・更新されたクラスタ最小値（たとえばＣｍｉｎ＝６）は、図７に示すように、中位マスタノードＢ，Ｃ，Ｄ，Ｅおよび下位マスタノードＦ，Ｇに通知される。このクラスタ最小値（Ｃｍｉｎ＝６）を受信した各ノードでは、この値（Ｃｍｉｎ＝６）よりも小さいトランザクション最小値を持つスナップショットを参照しているトランザクションを全て廃棄する。これによって、各ノードでのトランザクション最小値（Ｘｍｉｎ）、ノード最小値（Ｎｍｉｎ）、それらに基づくツリー最小値（Ｔｍｉｎ）は必ず６よりも大きな値をとる。したがって、クラスタ最小値（Ｃｍｉｎ）の通知後は完全消去されたタプルを参照するトランザクションは存在しなくなる。
【００６５】
なお、図６および図７では、上位マスタノードＡ、２階層の中位マスタノードＢ，Ｃ，Ｄ，Ｅ、下位マスタノードＥ，Ｆからなる４階層のツリー構造を有するマルチマスタノードで説明したが、上位マスタノードと下位マスタノードの２階層構造、または中位マスタノードが３階層以上すなわち全体で５階層以上のツリー構造を有していてもよい。
【００６６】
次に、図３を用いて書込セットの生成およびそれを用いた更新について説明する。
同図は、下位マスタノード（一例としてＭ３０１）におけるマスタデータベース（１１ａ）と、書込セットとの関係を示している。マスタデータベース（１１ａ）は行番号と、命令内容と、ポインタとによって構成されており、新たな命令がクライアント端末（ＣＬ）からなされる毎に行番号が追加されていく追記型のデータベースである。同図の場合、
前記で説明したように、行番号４を削除（ＤＥＬＥＴＥ）し、行番号５を新たな命令内容に書き換える（ｓｃ１にＵＰＤＡＴＥ）する場合を示している。
【００６７】
下位マスタノード（ＭＳ３０１）においてクライアント端末（ＣＬ）からの命令によりマスタデータベースに対してこのような更新命令がなされると、前述のように、バックエンドメモリ（ＢＥＭ）上でヒープタプルマップ（ＨＴＭ、ヒープファイル）とシャドウコピー（ＳＣ）とトランザクション最小値（Ｘｍｉｎ）からなる書込セットが生成される。
【００６８】
ヒープタプルマップ（ＨＴＭ）には、元の行番号（ｃｔｉｄ）と、新しい行の行番号（ｓｃｔｉｄ）が関係付けられて登録されるようになっている。このようにヒープタプルマップ（ＨＴＭ）はデータベースの更新毎に追加生成されていく。なお、行番号５の命令内容（ｓｃ１）が書き込まれる行番号はこの段階ではまだ不明であるため、ｓｃｔｉｄには新しい命令（ｓｃ１）を書き込んでおく。
【００６９】
一方、シャドウコピー（ＳＣ）には、マスタデータベース（１１ａ）を参照して書き換えられるべき行番号のシャドウコピーを生成する。このとき、新たに追加される行番号はこの段階では不明であるので、行番号には新たな命令（ｓｃ１）を書き込んでおく。
【００７０】
なお、この段階で下位マスタノード（ＭＳ３０１）のデータベース処理部（１１ｂ）は、ヒープタプルマップ（ＨＴＭ）の生成によりＤＥＬＥＴＥ命令が適用される行番号４と、ＵＰＤＡＴＥ命令が適用される旧行番号５は削除されることが既にわかるため、シャドウコピー（ＳＣ）としては新たな命令（ｓｃ１）だけを書き込んでおいてもよい。
【００７１】
さらに、書込セットに付加されるトランザクション最小値（Ｘｍｉｎ）は、前記で説明したように実行中のトランザクションが参照しているスナップショット上に記録されているトランザクション最小値（Ｘｍｉｎ）をそのまま書き込む。
【００７２】
このようにして生成された書込セットは、当該下位マスタノード（ＭＳ３０１）から中位マスタノード（たとえばＭＳ２０１）、さらに上位マスタノード（ＭＳ１０１）に送信される。
【００７３】
上位マスタノード（ＭＳ１０１）において、データベース処理部１１ｂ（中央処理装置（ＣＰＵ））は、前記で受信した書込セットからトランザクション最小値（Ｘｍｉｎ）を読み出す。そして、このトランザクション最小値（Ｘｍｉｎ）と上位マスタノード（ＭＳ１０１）のバックエンドメモリ（ＢＥＭ）に保持されたクラスタ最小値（Ｃｍｉｎ）と比較する。このとき、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）と等しいか大きいときには、トランザクションログ処理部（１１ｃ）を起動してトランザクションログデータの生成を開始した後に、以下の処理を行う。
【００７４】
まず、ヒープタプルマップ（ＨＴＭ）を読み出して、自身のマスタデータベース１１ａと比較する。ここで、ターゲットとなっているタプル（ここでは行番号４，５および７）の内容がデータベース（１１ａ）上で更新されているか否かを検証する。図４では、行番号４−６については未更新であるため、行番号４に削除ポインタを付与し、書き換えられる旧番号５にも削除ポインタを付与する。そして、新たな行番号７に新しい命令（ｓｃ１）が書き込まれる。
【００７５】
下位マスタノード（Ｍ３０１）からの書込セット中のヒープタプルマップ（ＨＴＭ）と自身のデータベースを比較して、上位マスタノード（Ｍ１０１）において既に別の書込セットによって当該行が更新されているときには、当該書込セットによる処理はアボート（中断）される。
【００７６】
一方、書込セット内のトランザクション最小値（Ｘｍｉｎ）とクラスタ最小値（Ｃｍｉｎ）と比較して、トランザクション最小値（Ｘｍｉｎ）がクラスタ最小値（Ｃｍｉｎ）よりも小さいときには、当該書込セットをアボートする。
【００７７】
このように書込セットをアボート処理する理由を以下に説明する。
書込セットの中にはクラスタ最小値（Ｃｍｉｎ）よりも小さいトランザクションＩＤを持つトランザクションが削除したタプルが更新対象となっている可能性がある。このようなタプルは上位マスタノードのクラスタ最小値（Ｃｍｉｎ）の設定に基づいて、既に廃棄されている可能性が高い。その場合、ヒープタプルマップを用いてこのタプルに対する整合性検出ができないので、上位マスタノードに矛盾を生じてしまう。そのため、クラスタ最小値（Ｃｍｉｎ）よりも小さいトランザクション最小値（Ｘｍｉｎ）を有する書込セットをアボートして係る矛盾の発生を防止しているわけである。
【００７８】
クラスタ最小値（Ｃｍｉｎ）の通知によるトランザクションの廃棄が中位・下位マスタノードで完了すれば、このような書込セットは生成されない。しかし、クラスタ最小値（Ｃｍｉｎ）を上位マスタノードから下位マスタノードに通知している間に中位・下位マスタノードで生成された書込セットは、クラスタ最小値（Ｃｍｉｎ）より小さいトランザクション最小値を持つ可能性があるので、書込セットを上位マスタノードで適用する際にチェックする必要がある。そこで前述のように、書込セットに登録されたトランザクション最小値（Ｘｍｉｎ）とクラスタ最小値（Ｃｍｉｎ）とを比較して、トランザクション最小値（Ｘｍｉｎ）が小さい場合には書込セットをアボートするようにして解決しているわけである。
【００７９】
このように、クラスタ最小値（Ｃｍｉｎ）の通知により、完全消去されたタプルを参照するトランザクションを全て廃棄することができ、前記通知（Ｃｍｉｎ）の通知と入れ違いに作成された書き込みセットもクラスタ最小値（Ｃｍｉｎ）を基準にアボートできる。したがって、中位・下位ノードでもデータベースの整合性を損なわずにタプルを完全消去することができる。
【００８０】
図５は、上位マスタノード（ＭＳ１０１）のマスタデータベース（１１ａ）が上記により更新されたときにトランザクションログ処理部（１１ｃ）で生成されるトランザクションログデータの一例である。このトランザクションログは、少なくとも命令とトランザクション内容（行番号とそれに対する実行処理内容）が時系列で連続的に記録されたファイルである。
【００８１】
同図によればトランザクションの開始命令（ＸＢ１）に続いて、命令番号と行番号とが対になったログが順次生成されている。たとえば、最初にＤＥＬＥＴＥ命令（Ｄ１）として行番号４を削除し（Ｄ１４）、次にＵＰＤＡＴＥ命令（Ｕ１）として行番号５を削除し行番号７を追加し（Ｕ１５７）次にこれらのコミット命令（ＸＣ１）を発行する。なお、このトランザクションログデータには、クラスタ最小値（Ｃｍｉｎ＝６）を追加してもよい。このようにクラスタ最小値（Ｃｍｉｎ＝６）を含めることによって、中位マスタノードＢ，Ｃ，Ｄ，Ｅまたは下位マスタノードＦ，Ｇにおけるトランザクションの廃棄順を制御することが可能となる。
【００８２】
なお、前述したようにこのトランザクションログデータとは非同期にクラスタ最小値（Ｃｍｉｎ＝６）を中位マスタノードＢ，Ｃ，Ｄ，Ｅおよび下位マスタノードＦ，Ｇに通知する場合には、前述のトランザクションログデータの生成・送信を待つことなく効率的なトランザクションの廃棄処理が可能となる。
【００８３】
このトランザクションログデータは、通信モジュール（１１ｄ）より中位マスタノード（ＭＳ２０１）をはじめ、すべての下位マスタノード（ＭＳ３０２・・・ＭＳ３０ｎ）に対して配信される。
【００８４】
前記トランザクションログデータを受信した中位・下位マスタノードでは、当該トランザクションログデータを自身のデータベースに複製（レプリケーション）する。
具体的には、下位マスタノード（たとえばＭ３０２）が図５に示したトランザクションログデータを通信モジュール１１ｄで受信すると、トランザクションログ処理部１１ｃを起動してこのトランザクションログデータを自身のマスタデータベース１１ａにレプリケーションする。この結果、行番号４と５に削除ポインタが付与され、新たな行番号７が追加される。そして、このトランザクションログデータにクラスタ最小値（Ｃｍｉｎ＝６）が追記されている場合には、各マスタノードにおいて、このクラスタ最小値（Ｃｍｉｎ＝６）よりも小さいトランザクション最小値（Ｘｍｉｎ）を持つスナップショットを参照するトランザクションが全て廃棄される。
【００８５】
このように、中位・下位マスタノードでは上位マスタノードから送信されるトランザクションログデータのレプリケーションによって統一的にデータベースが管理されることになる。
【００８６】
以上、本発明を実施形態に基づいて説明したが、本発明はこれに限定されるものではない。以下、その変形例について説明する。
（上位マスタノードＭＳ１０１でデータベースの更新が行われる場合）
下位マスタノード（たとえばＭＳ３０１）でマスタデータベースの更新命令が発生した場合の処理については、図２で説明したように、バックエンドメモリ（ＢＥＭ）上でヒープタプルマップ（ＨＴＭ、ヒープファイル）とシャドウコピー（ＳＣ）とからなる書込セットが生成されるが、上位マスタノード（ＭＳ１０１）でマスタデータベースの更新命令が発生した場合には、上位ノードに通知する必要がないため、書込セットは生成されない。すなわち、このような場合、上位ノード（ＭＳ１０１）では、図４の左図に示すようにマスタデータベース（１１ａ）に対して直接更新データの書込が行われるとともに、図５に示すトランザクションログデータが生成される。このトランザクションログデータは下位マスタノードに配信され、前記トランザクションログデータを受信した下位マスタノードでは、当該トランザクションログデータを自身のマスタデータベースにレプリケーションする。
【００８７】
（下位マスタノードで書込セットを生成している段階で検索処理が実行されたとき）
下位マスタノード（たとえばＭＳ１０１）において、図３に示すような書込セットを生成している段階で、当該下位マスタノードのマスタデータベースに対して検索が実行されたとき、書込セットの生成された行番号以外の行番号を対象とした検索であれば問題はないが、該当行（ここでは行番号４および行番号５）に対する検索である場合、これらの行番号に対しては既に実質的な更新処理が行われているため、マスタデータベースの該当行を検索したとしても正確な検索結果は得られない。
【００８８】
このような場合、データベース処理部（１１ｂ）は、まずヒープタプルマップ（ＨＴＭ）を参照して、検索該当行番号がエントリされているか否かをチェックする。たとえば図３に示す例で、検索対象が行番号３である場合、データベース処理部（１１ｂ）は、メモリ（ＭＭ）上に構築されたバックエンドメモリ（ＢＥＭ）上の書込セット内のヒープタプルマップ（ＨＴＭ）を参照して、該当行（行番号３）がエントリされているか否かを判定する。図３の例では、該当行はエントリされていない。その場合には、マスタデータベース１１ａに直接アクセスして該当行（行番号３）を検索する。
【００８９】
一方、図３に示す例で、検索対象が行番号４である場合、データベース処理部（１１ｂ）は書込セット内のヒープタプルマップ（ＨＴＭ）を参照したときに、該当行（行番号４）がエントリされていることを検出することになる。この場合、マスタデータベース１１ａにアクセスしても、残存する該当行は既に削除する更新命令が実行されているため、検索対象としても意味がない。この場合、データベース処理部（１１ｂ）は、ヒープタプルマップ（ＨＴＭ）を参照して該当行（行番号４）が削除されていることを検出する。このように、検索対象行が削除されているため、データベース処理部（１１ｂ）は該当行を検索対象とはしない。
【００９０】
一方、図３に示す例で、検索対象が行番号５である場合、上記と同様に、ヒープタプルマップ（ＨＴＭ）を参照して該当行（行番号５）に対応するシャドウコピー（ＳＣ１）が作成されていることを検出する。
【００９１】
このとき、データベース処理部（１１ｂ）は、シャドウコピー（ＳＣ１）を参照して、行番号５を書き換えた内容を検索対象とすればよい。
以上の説明では、１行毎にヒープタプルマップ（ＨＴＭ）を参照する場合で説明したが、このような処理方法に限らず、検索を行う際にデータベース処理部（１１ｂ）は、まず一括的にヒープタプルマップ（ＨＴＭ）を参照して、ここにエントリされている行番号の全てを削除されたものとしてこれらを除外してマスタデータベース（１１ａ）を検索しその後、再度ヒープタプルマップ（ＨＴＭ）を参照してそのエントリに基づいて該当行を検索対象から除外したり（行番号４の場合）、シャドウコピー（ＳＣ１）を検索対象としてもよい。
【００９２】
（下位マスタノードで上位マスタノードからのトランザクションログデータによる更新が行われているときの競合が生じた場合）
上位マスタノードから配信されたトランザクションログデータによって下位マスタノードのデータベースにレプリケーションが行われているときに、該当行に対して下位マスタノードのデータベースの更新命令が実行されている場合、競合が発生することになる。
【００９３】
具体的には、下位マスタノードへの更新命令に基づいて行番号４と５とを更新しているときに、上位マスタノードから行番号５に関するトランザクションログデータが配信されてきたときがこれに該当する。
【００９４】
このような場合には、下位マスタノードで作成された書込セットが上位マスタノードに送信されたとしても、上位マスタノードでは既に該当行に関するトランザクションログデータが配信されているため、前記書込セットは上位マスタノードで競合が検出されてアボートされることになる。したがって、当該下位マスタノードにおける競合は無視して差し支えない。この方法によれば、上位マスタノードにおいて本来アボートされるのがわかっているような書込セットでも上位マスタノードに送信しなければならず、上位マスタノードおよび下位マスタノードでのそれぞれの負担は増加するものの、上位マスタノードからのトランザクションログデータを下位マスタノードでレプリケーションする段階で一々競合のチェックを行わなくてよいため、処理が高速化できるという利点がある。
【００９５】
一方、このような下位マスタノードでの競合を解決する別の方法としては、下位マスタノードにおいてヒープタプルマップ（ＨＴＭ）を生成したときに、これを当該下位マスタノード内のメモリに登録し、このメモリを共有メモリとして、他の下位マスタノードからアクセス可能な状態としておく。このような他の下位ノードマスタ間のアクセスは、それぞれの下位マスタノードのデータベース処理部１１ｂが行う。この方法によれば、ヒープタプルマップ（ＨＴＭ）の生成時に競合をチェックするため、トランザクションログデータによるレプリケーションが遅延する可能性はあるものの、競合の問題を下位マスタノー
ド間だけで解決できるので、上位マスタノードに負担をかけない。
【００９６】
以上、本発明を実施形態に基づいて説明したがこれらに限定されるものではない。
たとえば、書込セットは下位マスタノード（ＭＳ３０１）で生成する場合で説明したがこれに限らず中位マスタノード（ＭＳ２０１）で生成してもよいことは勿論である。
【産業上の利用可能性】
【００９７】
本発明は、階層構造を備えたマルチマスタノード構造のデータベース管理システムに利用できる。
【符号の説明】
【００９８】
ＭＳ１０１ 上位マスタノード
ＳＬ スレーブ
ＭＳ２０１，ＭＳ２０２・・・ＭＳ２０ｎ 中位マスタノード
ＭＳ３０１，ＭＳ３０２・・・ＭＳ３０ｎ 下位マスタノード
ＣＬ クライアント端末
１１ａ マスタデータベース
１１ｂ データベース処理部
１１ｃ トランザクションログ処理部
１１ｄ 通信モジュール
ＢＥＭ バックエンドメモリ
ＨＴＭ ヒープタプルマップ
ＳＣ シャドウコピー
Ｃｍｉｎ クラスタ最小値
Ｘｍｉｎ トランザクション最小値
【特許請求の範囲】
【請求項１】
ノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法であって、
いずれかの下位マスタノードのセッションにおいて、当該下位マスタノードのデータベースのシャドウコピーと、下位マスタノードのメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして上位マスタノードに対して送信させるステップと、
前記で受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するステップと、
前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、
前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、
からなる下位マスタノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法。
【請求項２】
レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースにおける下位マスタノードのデータベース管理方法であって、
いずれかの下位マスタノードでデータベースへの更新命令が生じたときに、当該下位マスタノードのデータベース処理部が上位マスタノードに対して、自身のメモリ上に展開されたデータベースのシャドウコピーと、ヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして生成する際に、
それを受信する前記上位マスタノードに対して、前記下位マスタノードから受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きいときに前記シャドウコピーを用いて上位マスタノードのデータベースを更新させ、この更新記録をトランザクションログとして生成させ、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信させるために、前記書込セットを上位マスタノードに送信するステップと、
前記下位マスタノードのトランザクションログ処理部は、前記トランザクションログを受信したときに、当該トランザクションログに基づいて自身のデータベースを更新するステップと、
下位マスタノードにおいて、前記上位マスタノードが保持するクラスタ最小値を受信して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄するステップと、
からなる下位マスタノードのデータベースの管理方法。
【請求項３】
前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として上位マスタノードに通知し、
前記上位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する請求項１または２記載の追記型データベースの管理方法。
【請求項４】
前記上位マスタノードと前記下位マスタノードとの間の階層に中位マスタノードを有しており、
前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として中位マスタノードに通知し、
前記中位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とを比較して最も小さい値を当該中位マスタノードのツリー最小値として上位マスタノードに通知し、
上位マスタノードは、自身のノード最小値と、前記１または２以上の中位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する請求項１または２記載の追記型データベースの管理方法。
【請求項５】
前記中位マスタノードはさらに２階層以上のツリー構造を有している請求項４記載の追記型データベースの管理方法。
【請求項６】
前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログの下位マスタノードへの通知とは非同期で行われる請求項１記載の追記型データベースの管理方法。
【請求項７】
前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログに当該クラスタ最小値を含めて行われる請求項１記載の追記型データベースの管理方法。
【請求項８】
前記書込セットは、下位マスタノードの代わりに中位マスタノードで生成され、少なくとも当該中位マスタノードで実行中のトランザクションが参照するスナップショットのトランザクション最小値が書き込まれている請求項４または５記載の追記型データベースの管理方法。
【請求項１】
ノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法であって、
いずれかの下位マスタノードのセッションにおいて、当該下位マスタノードのデータベースのシャドウコピーと、下位マスタノードのメモリ上に展開されたヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして上位マスタノードに対して送信させるステップと、
前記で受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きい場合には、当該書き込みセット中のヒープタプルマップと自身のデータベースとを比較して、ターゲットとして登録されているタプルのデータベースにおける更新の有無を検証し、更新がなされているときには当該書き込みセットをアボートし、更新がなされていないときには前記シャドウコピーを用いて自身のデータベースを更新するステップと、
前記でトランザクション最小値がクラスタ最小値よりも小さい場合には、当該書き込みセットをアボートするステップと、
前記上位マスタノードが保持するクラスタ最小値を下位マスタノードに通知して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄させるステップと、
からなる下位マスタノードを階層的に有する上位マスタノードにおける追記型データベースの管理方法。
【請求項２】
レコード更新が可能な上位と下位のマスタノードを階層的に有する追記型データベースにおける下位マスタノードのデータベース管理方法であって、
いずれかの下位マスタノードでデータベースへの更新命令が生じたときに、当該下位マスタノードのデータベース処理部が上位マスタノードに対して、自身のメモリ上に展開されたデータベースのシャドウコピーと、ヒープタプルマップと、実行中のトランザクションが参照するスナップショットのトランザクション最小値とを書込セットとして生成する際に、
それを受信する前記上位マスタノードに対して、前記下位マスタノードから受信した書込セット中のトランザクション最小値と上位マスタノードが保持するクラスタ最小値とを比較して、トランザクション最小値がクラスタ最小値と等しいか大きいときに前記シャドウコピーを用いて上位マスタノードのデータベースを更新させ、この更新記録をトランザクションログとして生成させ、前記トランザクションログを前記送信元の下位マスタノードを含む下位マスタノードに配信させるために、前記書込セットを上位マスタノードに送信するステップと、
前記下位マスタノードのトランザクションログ処理部は、前記トランザクションログを受信したときに、当該トランザクションログに基づいて自身のデータベースを更新するステップと、
下位マスタノードにおいて、前記上位マスタノードが保持するクラスタ最小値を受信して、該最小値よりも小さいトランザクション最小値を有するトランザクションを廃棄するステップと、
からなる下位マスタノードのデータベースの管理方法。
【請求項３】
前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として上位マスタノードに通知し、
前記上位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する請求項１または２記載の追記型データベースの管理方法。
【請求項４】
前記上位マスタノードと前記下位マスタノードとの間の階層に中位マスタノードを有しており、
前記下位マスタノードは、実行中のトランザクションを時系列に記録した複数のスナップショット間のトランザクション最小値同士を比較して最も小さい値をノード最小値とし、このノード最小値をツリー最小値として中位マスタノードに通知し、
前記中位マスタノードは、自身のノード最小値と、前記１または２以上の下位マスタノードから通知されたツリー最小値とを比較して最も小さい値を当該中位マスタノードのツリー最小値として上位マスタノードに通知し、
上位マスタノードは、自身のノード最小値と、前記１または２以上の中位マスタノードから通知されたツリー最小値とから選択的にクラスタ最小値を決定・保持する請求項１または２記載の追記型データベースの管理方法。
【請求項５】
前記中位マスタノードはさらに２階層以上のツリー構造を有している請求項４記載の追記型データベースの管理方法。
【請求項６】
前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログの下位マスタノードへの通知とは非同期で行われる請求項１記載の追記型データベースの管理方法。
【請求項７】
前記上位マスタノードが保持するクラスタ最小値の下位マスタノードへの通知は、前記トランザクションログに当該クラスタ最小値を含めて行われる請求項１記載の追記型データベースの管理方法。
【請求項８】
前記書込セットは、下位マスタノードの代わりに中位マスタノードで生成され、少なくとも当該中位マスタノードで実行中のトランザクションが参照するスナップショットのトランザクション最小値が書き込まれている請求項４または５記載の追記型データベースの管理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１３−３３４３９（Ｐ２０１３−３３４３９Ａ）
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願番号】特願２０１２−１３８３７（Ｐ２０１２−１３８３７）
【出願日】平成２４年１月２６日（２０１２．１．２６）
【分割の表示】特願２０１２−１０４３４（Ｐ２０１２−１０４３４）の分割
【原出願日】平成２４年１月２０日（２０１２．１．２０）
【出願人】（３０１０１４２６９）株式会社Ｍｕｒａｋｕｍｏ (23)
【公開日】平成２５年２月１４日（２０１３．２．１４）
【国際特許分類】
【出願日】平成２４年１月２６日（２０１２．１．２６）
【分割の表示】特願２０１２−１０４３４（Ｐ２０１２−１０４３４）の分割
【原出願日】平成２４年１月２０日（２０１２．１．２０）
【出願人】（３０１０１４２６９）株式会社Ｍｕｒａｋｕｍｏ (23)
[ Back to top ]