(57)【要約】【課題】単一版同時実行制御アルゴリズムが持つ、高い実装効率と処理性能とを損なうことなく、書込み競合時の性能低下を解決する。【解決手段】制御処理装置１０は、トランザクションの書込み命令を受けた場合に、トランザクションの書込みを、書込みロックを用いて実行するか書込みロック用いないで実行するかを判定する判定部１３１と、判定部１３１が書込みロックを用いて実行すると判定した場合に、トランザクションに対する書込みロックを獲得してトランザクションの書込みを実行する書込み部１３３と、判定部１３１が書込みロック用いないで実行すると判定した場合に、トランザクションの書込み命令を破棄する最適化部１３２と、書込み部１３３による書込み後、または、最適化部１３２による書込み命令破棄後、トランザクションの書込みが成功した旨を命令元に返却する返却部１３４と、を有する。【選択図】図１
2019185492.tif 000002
【特許請求の範囲】
【請求項１】
トランザクションの書込み処理を制御する制御処理装置であって、
前記トランザクションの書込み命令を受けた場合に、前記トランザクションの書込みを、書込みロックを用いて実行するか前記書込みロックを用いないで実行するかを判定する判定部と、
前記判定部が、前記トランザクションの書込みを、前記書込みロックを用いて実行すると判定した場合に、前記トランザクションに対する前記書込みロックを獲得して前記トランザクションの書込みを実行する書込み部と、
前記判定部が、前記トランザクションの書込みを、前記書込みロックを用いないで実行すると判定した場合に、前記トランザクションの書込み命令を破棄する最適化部と、
前記書込み部による書込み後、または、前記最適化部による書込み命令破棄後、前記トランザクションの書込みが成功した旨を命令元に返却する返却部と、
を有することを特徴とする制御処理装置。
【請求項２】
前記トランザクションの書込みに関する情報の記録がアトミックに実行されるログを記憶する記憶部をさらに有し、
前記判定部は、前記ログを参照し、前記ログに既に記録された内容の読込みを伴わない書込み命令を判定対象とし、該判定対象の書込み命令の分離性が保証できないと判定した場合には前記書込み部に前記トランザクションの書込みを実行させることを特徴とする請求項１に記載の制御処理装置。
【請求項３】
前記判定部は、前記ログを参照し、複数の書込み命令の依存関係の有無に応じて、前記判定対象の書込み命令の分離性を検証し、
前記最適化部は、アトミックな命令にしたがって前記トランザクションの書込み命令の破棄を実行し、前記ログのロックを獲得して前記書込み命令を破棄した旨を前記ログに記録することを特徴とする請求項２に記載の制御処理装置。
【請求項４】
前記ログは、ブルームフィルタであり、
前記最適化部は、ＣＡＳ命令を実装することを特徴とする請求項２または３に記載の制御処理装置。
【請求項５】
トランザクションの書込み処理を制御する制御処理装置が実行する制御処理方法であって、
前記トランザクションの書込み命令を受けた場合に、前記トランザクションの書込みを、書込みロックを用いて実行するか前記書込みロック用いないで実行するかを判定する判定工程と、
前記判定工程において、前記トランザクションの書込みを、前記書込みロックを用いて実行すると判定された場合に、前記トランザクションに対する前記書込みロックを獲得して前記トランザクションの書込みを実行する書込み工程と、
前記判定工程において、前記トランザクションの書込みを、前記書込みロックを用いないで実行すると判定された場合に、前記トランザクションの書込み命令を破棄する最適化工程と、
前記書込み工程における書込み後、または、前記最適化工程における書込み命令破棄後、前記トランザクションの書込みが成功した旨を命令元に返却する返却工程と、
を含んだことを特徴とする制御処理方法。
【請求項６】
コンピュータを、請求項１〜４のいずれか一つに記載の制御処理装置として機能さ
せるための制御処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、制御処理装置、制御処理方法および制御処理プログラムに関する。
【背景技術】
【０００２】
コンピュータにて行う不可分な一連のデータ処理群をトランザクションと呼ぶ。トランザクションの処理には、ＡＣＩＤ（Atomicity  Consistency  Isolation  Durability）すなわち原子性、一貫性、分離性、永続性を必要とする。
【０００３】
トランザクション処理では、マルチコア環境で並列処理を行った際に、シングルコアで直列実行した際の処理結果と等価な処理結果を生成する。この特性が分離性であり、分離性を実現するためのアルゴリズムを同時実行制御アルゴリズム（Concurrency  Control）と呼ぶ。
【０００４】
このとき用いられる等価性には、いくつかに分類される。そして、異なる等価性を用いることによって、許容される処理結果の組み合わせが変化する。このうち、Multiversion  Serializability（ＭＶＳＲ）（例えば、非特許文献１参照）を等価性に用いる同時実行制御アルゴリズムが、最も多くの処理結果を直列実行と等価であるとみなすことができる。
【０００５】
ここで、ＭＶＳＲを等価性に用いるアルゴリズムは、計算量を多く必要とする多版同時実行制御（Multiversion  Concurrency  Control）でのみ実現可能とされており、実用に耐えうる性能が得られなかった。
【０００６】
このため、ＭＶＳＲよりも許容する処理結果の少ないConflict  Serializability（ＣＳＲ）を等価性の検証に用い、計算量の少ない単一版同時実行制御（1Version  Concurrency  Control）のアルゴリズムが提案されてきた。
【先行技術文献】
【非特許文献】
【０００７】
【非特許文献１】Gerhard  Weikum  and  Gottfried  Vossen,  2001.  Transactional  Information  Systems:  Theory,  Algorithms,  and  the  Practice  of  Concurrency  Control  and  Recovery,  Morgan  Kaufmann  Publishers  Inc.,  San  Francisco,  CA,  USA.
【非特許文献２】Robert  H.  Thomas  (1979),  “A  majority  consensus  approach  to  concurrency  control  for  multiple  copy  databases”,  ACM  Transactions  on  Database  Systems,  4  (2):  180−209,  doi:10.1145/320071.320076.
【非特許文献３】Xiangyao  Yu,  George  Bezerra,  Andrew  Pavlo,  Srinivas  Devadas,  and  Michael  Stonebraker,  2014,  “Staring  into  the  abyss:  an  evaluation  of  concurrency  control  with  one  thousand  cores”,  Proc.  VLDB  Endow.  8,  3  (November  2014),  209−220.
【発明の概要】
【発明が解決しようとする課題】
【０００８】
ここで、ＣＳＲを等価性に用いる単一版同時実行制御アルゴリズムは、全ての書込み処理を反映させなければならない。これに対し、ＭＶＳＲを等価性に用いる場合はこの限りではなく（非特許文献２参照）、一部の書込み処理を破棄することが可能である。この一部の書込み処理の破棄は、ＣＳＲでは実行できない。このため、既存の全てのトランザクション処理装置ならびに同時実行制御アルゴリズムにおいて、書込み競合時の性能は大きく低下することが報告されている（非特許文献３参照）。
【０００９】
本発明は、上記に鑑みてなされたものであって、単一版同時実行制御アルゴリズムが持つ、高い実装効率と処理性能とを損なうことなく、書込み競合時の性能低下を解決する制御処理装置、制御処理方法および制御処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明の制御処理装置は、トランザクションの書込み処理を制御する制御処理装置であって、トランザクションの書込み命令を受けた場合に、トランザクションの書込みを、書込みロックを用いて実行するか書込みロック用いないで実行するかを判定する判定部と、判定部が書込みロックを用いて実行すると判定した場合に、トランザクションに対する書込みロックを獲得してトランザクションの書込みを実行する書込み部と、判定部が書込みロックを用いないで実行すると判定した場合に、トランザクションの書込み命令を破棄する最適化部と、書込み部による書込み後、または、最適化部による書込み命令破棄後、トランザクションの書込みが成功した旨を命令元に返却する返却部と、を有することを特徴とする。
【発明の効果】
【００１１】
本発明によれば、単一版同時実行制御アルゴリズムが持つ、高い実装効率と処理性能とを損なうことなく、書込み競合時の性能低下を解決することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、実施の形態に係る制御処理装置の構成の一例を示すブロック図である。
【図２】図２は、図１に示す制御処理装置の処理の流れを説明する図である。
【図３】図３は、図１に示す判定部及び最適化部が実行する処理内容のアルゴリズムを示す図である。
【図４】図４は、図１に示す判定部による判定処理について説明する図である。
【図５】図５は、図１に示す最適化部が実装するＣＡＳ（Compare-And-Swap）命令を説明する図である。
【図６】図６は、実施の形態に係る制御処理装置の全体の処理のアルゴリズムを示す図である。
【図７】図７は、図１に示す制御処理装置による書込み制御処理の処理手順のフローチャートである。
【図８】図８は、プログラムが実行されることにより、制御処理装置が実現されるコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１３】
以下に、本願に係る制御処理装置、制御処理方法および制御処理プログラムの実施形態を図面に基づいて詳細に説明する。また、本発明は、以下に説明する実施形態により限定されるものではない。
【００１４】
［主な記号の定義］
実施の形態で用いる主な記号を下表に示す。以下の各説明において、同一の記号を用いる。
【００１５】
【表１】
2019185492.tif 000003
【００１６】
［従来の数理的背景］
まず、以降の説明において必要となる背景知識を説明する。トランザクション（transaction：Ｔ）とは、不可分な一連の命令列のことを指す。命令列に含まれる命令数ｉは、０＜ｉである。トランザクション処理を構成する命令は、読込み（ｒ）と書込み（ｗ）である。命令列には終端記号としてコミット（ｃ）かアボート（ａ）のどちらかがアルゴリズムにより与えられる。
【００１７】
同時実行制御アルゴリズムの目的は、直列実行した際の処理結果と等価な処理結果を高速に生成することである。例えば、トランザクション数Ｎに対して、Ｎ！の直列実行順序が存在するため、このうちいずれかの直列実行順序Ｍ＿（ｅ．ｇ．Ｔｉ→Ｔｊ→Ｔｋ・・・・）と等価な命令実行順序Ｈを得られればよい。
【００１８】
マルチコア環境においてトランザクションを並列実行すると、各トランザクション処理に含まれる命令ｏｐ（ｏｐ∈ｒ，ｗ）について、（１）式に示す命令集合が存在する。
【００１９】
【数１】
2019185492.tif 000004
【００２０】
このとき、Ｓの実行順序は｜Ｓ｜！存在する。同時実行制御アルゴリズムは、ロック等の同期機構を用いて、この｜Ｓ｜！の実行順序を制限し、直列実行順序と等価な命令実行順序Ｈを生成する。
【００２１】
等価性については分類があり、用いる等価性によっては、いかなる直列実行順序とも等価とはみなすことができず、Ｈを棄却する場合がある。このため、｜Ｓ｜！の実行順序のうちより多くの命令実行順序Ｈを直列実行順序と等価であるとみなすことができる等価性を用いることが望ましい。
【００２２】
既存手法の殆どが等価性にＣＳＲを用いている。このＣＳＲは、書込み処理と読込み処理との両方でロック、すなわち、排他制御を行うことによって、容易に実装できる。このため、ＣＳＲを等価性に用いる単一版同時実行制御のアルゴリズムが多く提案されている。
【００２３】
ＣＳＲを等価性に用いるとき、すべてのトランザクションの書込み処理が必ずロック等を用いて直列化される必要がある。この制約により、ＣＳＲの同時実行制御アルゴリズムが生成する命令実行順序Ｈについて、以下（（２）式）が保証される。
【００２４】
【数２】
2019185492.tif 000005
【００２５】
ＣＳＲを等価性に用いた際、直列実行順序Ｍと同時実行制御アルゴリズムが生成する命令実行順序Ｈの書込み順序（ｗｉ→ｗｊ）、ならびに、書込みに対する読込み順序（ｗｉ→ｒｊ）は、必ず一致しなければならない。
【００２６】
同時実行制御アルゴリズムは、この制約を満たすために、書込み処理の際にロックを獲得し、他のトランザクションとの順序を決定する。これは、言い換えれば、ＣＳＲにおいて、書込みロックの獲得順序がＭにおけるトランザクションの順序を決定するということである。書込みにおいて，ロックを獲得することがＮ！の順序集合からＭを決定することを意味するため、ロックを獲得することなしに自身のＨにおける順序を確定することはできない。この制約から、ＣＳＲを等価性に用いる単一版同時実行制御アルゴリズムは、特定のタプルに書込みが競合した場合にも必ずロックを獲得する必要があり、マルチコア環境を有効に使うことができず、性能が低下することを避けられなかった。
【００２７】
［実施の形態］
そこで、本実施の形態に係る制御処理装置では、単一版同時実行制御アルゴリズムをベースラインとして、書込みロックを用いずに直列実行順序Ｍを決定する最適化を行う。具体的には、本実施の形態に係る制御処理装置では、ＣＳＲを等価性に用いる単一版同時実行制御アルゴリズムに、アトミック操作可能なブルームフィルタ（Bloom  Filter）を追加することによって、ＭＶＳＲを等価性に用いるアルゴリズムに拡張する。これによって、本実施の形態に係る制御処理装置では、書込み競合時においても、一部の書込みを破棄することが可能となり、処理を高速化できる。
【００２８】
図１は、実施の形態に係る制御処理装置の構成の一例を示すブロック図である。図１に示すように、本実施の形態に係る制御処理装置１０は、トランザクションの書込み処理を制御する制御処理装置であって、入力部１１、記憶部１２、制御部１３及び出力部１４を有する。
【００２９】
入力部１１は、制御処理装置１０の操作者からの各種操作を受け付ける入力インタフェースである。例えば、キーボードやマウス等の入力デバイスによって構成される。
【００３０】
記憶部１２は、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、または、ハードディスク、光ディスク等の記憶装置によって実現され、制御処理装置１０を動作させる処理プログラムや、処理プログラムの実行中に使用されるデータなどが記憶される。記憶部１２は、ブルームフィルタ１２１を有する。
【００３１】
ブルームフィルタ１２１は、トランザクションの書込みに関する情報が記録されるログであって、アトミックに記録が実行される。ブルームフィルタ１２１は、制御処理装置１０における全てのトランザクションの書込み命令が記録される。なお、ブルームフィルタ１２１は、計算機科学におけるあるデータ構造の名称であり、他のデータ構造に比べて非常に高速に、データが存在するか否かという判定を行うことができる。例えば、ブルームフィルタ１２１は、トランザクションの識別情報と該トランザクションにおける書込み命令とを、書込み時間に対応させて、ビット列で表現したデータ構造である。
【００３２】
制御部１３は、制御処理装置１０全体を制御する。制御部１３は、例えば、ＣＰＵ（Central  Processing  Unit）、ＭＰＵ（Micro  Processing  Unit）等の電子回路や、ＡＳＩＣ（Application  Specific  Integrated  Circuit）、ＦＰＧＡ（Field  Programmable  Gate  Array）等の集積回路である。また、制御部１３は、各種の処理手順を規定したプログラムや制御データを格納するための内部メモリを有し、内部メモリを用いて各処理を実行する。また、制御部１３は、各種のプログラムが動作することにより各種の処理部として機能する。制御部１３は、判定部１３１、最適化部１３２、書込み部１３３及び返却部１３４を有する。
【００３３】
判定部１３１は、トランザクションの書込み命令を受けた場合に、トランザクションの書込みを、書込みロックを用いて実行するか書込みロックを用いないで実行するかを判定する。判定部１３１は、ブルームフィルタ１２１を参照し、ブルームフィルタ１２１に既に記録された内容の読込み処理を伴わない書込み命令を判定対象とする。そして、判定部１３１は、判定対象の書込み命令の分離性（Isolation）が保証できない場合には、書込み部１３３に、書込みロックを獲得してのトランザクションの書込みを実行させる。判定部１３１は、ブルームフィルタ１２１を参照し、複数の書込み命令の依存関係の有無に応じて、判定対象の書込み処理の分離性を検証する。
【００３４】
最適化部１３２は、判定部１３１が、トランザクションの書込みを、書込みロックを用いないで実行すると判定した場合に、トランザクションの書込み命令を破棄する。最適化部１３２は、アトミック命令にしたがって書込みの破棄を実行し、他のトランザクションに対して排他的に書込み命令を破棄した旨をブルームフィルタ１２１に記録する。最適化部１３２は、例えば、ＣＡＳ命令を実装する。
【００３５】
書込み部１３３は、単一版制御を行う同時実行制御部である。書込み部１３３は、ＣＳＲを等価性に用いる同時実行制御アルゴリズムを適用してトランザクションの書込みを実行する。書込み部１３３は、判定部１３１が、トランザクションの書込みを、書込みロックを用いて実行すると判定した場合に、トランザクションに対する書込みロックを獲得して、トランザクションの書込みを実行する。
【００３６】
返却部１３４は、書込み部１３３による書込み後、または、最適化部１３２による書込み命令破棄後、トランザクションの書込みが成功した旨を、命令元に返却する。
【００３７】
出力部１４は、例えば、液晶ディスプレイやプリンタ等であって、各種情報を出力する。また、出力部１４は、外部装置との間で、各種データの入出力を司るインタフェースであってもよく、外部装置に各種情報を出力してもよい。
【００３８】
［処理の流れ］
次に、制御処理装置１０の処理の流れを説明する。図２は、図１に示す制御処理装置１０の処理の流れを説明する図である。
【００３９】
図２に示すように、制御処理装置１０は、トランザクションの書込み命令を受けた場合、判定部１３１が、トランザクションの書込みを、書込みロックを用いて実行するか書込みロック用いないで実行するかを判定する（図２の（１）参照）。
【００４０】
判定部１３１が、トランザクションの書込みを、書込みロックを用いないで実行すると判定した場合、最適化部１３２は、ＣＡＳ命令を実行して、トランザクションの書込み命令を破棄する最適化処理を行う（図２の（２）参照）。
【００４１】
判定部１３１が、トランザクションの書込みを、書込みロックを用いて実行すると判定した場合は、書込み部１３３は、トランザクションに対する書込みロックを獲得してトランザクションの書込みを実行する。具体的には、書込み部１３３は、書込みロックを獲得して（図２の（３）参照）、ログ（ＷＡＬ（Write  Ahead  Log））先行書込みを行い（図２の（４）参照）、データを更新した後に（図２の（５）参照）、ロックを解放する（図２の（６）参照）一連の処理を行う。
【００４２】
そして、返却部１３４は、書込み部１３３による書込み後、または、最適化部１３２による書込み命令破棄後、トランザクションの書込みが成功した旨を命令元に返却して（図２の（７）参照）、処理を終了する。
【００４３】
［本実施の形態の数理的背景］
次に、本実施の形態の数理的背景について説明する。制御処理装置１０では、単一版同時実行制御アルゴリズムをベースラインとして、書込みロックを用いずにトランザクションの順序を決定する最適化を行う。すなわち、Ｈに含まれる書込み処理ｗｉ，ｗｊの順序を変更した場合で、かつ、ｊ＜Ｍｉとなるような新たな直列実行順序Ｍが存在し、このＭが、ＨとＭＶＳＲにおいて等価であるとき、ｗｊを破棄することが可能である。
【００４４】
この最適化は、ＣＡＳと呼ばれるＣＰＵ命令か、他のＣＰＵ命令やロックを用いたＣＡＳと同等の処理によって実装する。すなわち、最適化部１３２は、ＣＡＳ命令を実装する。そして、制御処理装置１０は、最適化が適用された場合、すなわち、判定部１３１において書込みロックを用いないと判定された場合、トランザクションの書込み処理、すなわちロック、ログ（ＷＡＬ）先行書込み及びデータ更新を実際に行わず、命令元に、書込みが成功した旨を返却する。これによって、制御処理装置１０は、書込み競合が起こった場合においても、高速に処理を行うことが可能となる。
【００４５】
［アルゴリズム１］
制御処理装置１０の判定部１３１が実行する判定と、最適化部１３２が実行するＣＡＳ命令実行との手順について説明する。図３は、図１に示す判定部１３１及び最適化部１３２が実行する処理内容のアルゴリズムを示す図である。
【００４６】
まず、単一版同時実行制御において、書込み処理は、その書込み内容が一度も読込みされることなく上書きされた場合、今後もまた読込みされることは無いことから、書込み処理自体を破棄していたとしても分離性に影響がないことがＭＶＳＲによって証明されている（詳細は、非特許文献１参照）。
【００４７】
本実施の形態では、この書込み処理の破棄を積極的に行うものである。本実施の形態では、判定部１３１は、既に存在する読込み処理を伴わない書込み処理「Blind  Write」を対象とし、Blind  Writeを行ったトランザクションよりもＭにおいて自分が過去に起こったとみなして、書込みを破棄できるかを検証する。
【００４８】
最適化部１３２が最適化（書込み命令の破棄）を行った場合、このトランザクションＴｊと、過去に実行されたBlind  Writeを行ったトランザクションＴｉとのＭにおける順序は、ｊ＜ｉとなる。ここで、判定部１３１は、図３のアルゴリズム中の（ａ）では、命令実行順序Ｈについて、以下の（３）式に示す関係が存在するか否かをブルームフィルタを用いて検証する。
【００４９】
【数３】
2019185492.tif 000006
【００５０】
この（３）式に対応する読込み処理がＴｊに存在する場合、Ｔｉの書込み処理内容をＴｊが読込みしていることから、ｉ＜ｊの順序がＭに要求される。この順序は、書込みを破棄した際のｊ＜ｉの順序と矛盾する。
【００５１】
すなわち、この（３）式に示す関係が存在する場合、ＣＳＲにおいてもＭＶＳＲにおいても、Ｎ！の直列実行順序の中でＨと等価なＭは存在しないことを意味し、書込み命令の分離性が保証されない。このため、アルゴリズム中の（ａ）に示す検証に失敗した場合、書込み命令は破棄せず、判定部１３１は、単一版制御を選択し、書込み部１３３に、書込みロックを用いたトランザクションの書込みを実行させることによって、分離性を保持する。
【００５２】
そして、（３）式に示す関係が存在する場合、すなわち、判定部１３１が、アルゴリズム中の（ａ）に示す検証に成功した場合、最適化部１３２は、書込み命令を破棄する。
【００５３】
図４は、図１に示す判定部１３１による判定処理について説明する図である。例えば、図４では、判定部１３１が、実行中のトランザクションＴ４に対する最適化の可否を判定する例について説明する。この際、判定部１３１は、ブルームフィルタ１２１を参照する。そして、実行を終了したトランザクションＴ１，Ｔ２，Ｔ３のＷＳを重ねたブルームフィルタ２１と、トランザクションＴ４のＲＳ２２とについて、ビットマスクで衝突判定を行う（図４の（１）参照）。
【００５４】
判定部１３１は、ブルームフィルタ２１とＲＳ２２とで衝突がない、すなわち、ｗ（トランザクションＴ１，Ｔ２，Ｔ３のＷＳ）とｒ（トランザクションＴ４のＲＳ）との依存関係が無いと判定した場合には、最適化が可能であるとして、最適化部１３２に最適化を実行させる（図４の（２）参照）。
【００５５】
この際、最適化部１３２は、このタプルを操作した全てのトランザクションのＷＳをブルームフィルタに書き加えていく処理（後述の図６のアルゴリズム中の（Ｃ）参照）を、ＣＡＳ１命令で行う。このＣＡＳ命令について、図５を参照して説明する。
【００５６】
図５は、図１に示す最適化部１３２が実装するＣＡＳ命令を説明する図である。ブルームフィルタは、ＣＡＳ命令によってアトミックに更新されていくため、複数のトランザクションの最適化が衝突しても調停が行われる。図５を参照し、ロックを獲得して書込みが終了したトランザクションＴ１の後に、トランザクションＴ２の書込み命令、トランザクションＴ３の書込み命令に対する最適化を行う場合について説明する。
【００５７】
この場合、先に受けたトランザクションＴ２の書込み命令は、読込み処理を伴わずトランザクションＴ１との依存もないため、破棄されるものである。最適化部１３２は、このトランザクションＴ２についてＣＡＳ命令を実行する（図５の（１）参照）。
【００５８】
このトランザクションＴ２についてのＣＡＳ命令の成功によって、先行するトランザクションＴ１のBlind  Writeの前に、自身のトランザクションＴ２の書込みが実行されたとみなすことができる。したがって、最適化部１３２は、このＣＡＳ１命令のみで、トランザクションＴ２の書込み処理を破棄できる。なお、この例では、後に受けたトランザクションＴ３についてはＣＡＳ命令が失敗するものの（図５の（２）参照）、最適化部１３２は、再度、ブルームフィルタ１２１を読み出し、改めてＣＡＳ命令を実行する。この結果、例えば、トランザクションＴ２のBlind  Writeの前に、自身のトランザクションＴ３の書込みが実行された際の直列実行順序Ｍ（Ｔ３→Ｔ２→Ｔ１）と等価であることを判定できる。このように、最適化部１３２は、ブルームフィルタ１２１への書込みが競合しないように、調停を行う。
【００５９】
［アルゴリズム２］
図６は、実施の形態に係る制御処理装置１０の全体の処理のアルゴリズムを示す図である。
【００６０】
制御処理装置１０は、一般的なトランザクションの制御処理装置と同様に、ユーザからの入力として、トランザクション開始（Begin）、読込み（Read）、書込み（Write）、トランザクション終了（Commit）を受け付ける。
【００６１】
一般的な単一版同時実行制御アルゴリズムに対して、本実施の形態を適用した際の差分としては、図６に示す（Ａ），（Ｃ）が存在する。（Ａ）は、Algorithm1（図３対象）の適用可否の判断である。これが成功した場合には、処理中のトランザクションＴｊは全ての書込み対象タプルについて、書込みを破棄できることを意味する。この際、最適化部１３２は、ブルームフィルタ１２１をクリアした後に、トランザクションＴｊを破棄した旨をブルームフィルタ１２１に記録する。
【００６２】
図６に示す（Ｃ）は、本実施の形態の最適化が適用できなかった際、すなわち、ＣＳＲを等価性に用いる単一版同時実行制御アルゴリズムの処理について、本実施の形態によって追加される処理である。書込み部１３３が、ロックを獲得し、実際に書込み処理を行い、かつ、その書込み処理がBlind  Writeであった場合、その書込み処理は、これ以後のトランザクションが本発明を適用する際の対象となる。このため、書込み部１３３は、ブルームフィルタ１２１をクリアした後に、このトランザクションのＷＳをブルームフィルタ１２１に記録する。
【００６３】
これによって、制御処理装置１０は、最適化部１３２によるＣＡＳ命令による最適化（書込み命令の破棄）を連続して実行することができる。さらに、制御処理装置１０は、ブルームフィルタ１２１のビット列が飽和した場合があっても、定期的にブルームフィルタ１２１上のビット列をクリアして、偽陽性の悪化を防止している。
【００６４】
なお、図６の（Ｂ）は、ＣＳＲを等価性に用いる同時実行制御アルゴリズムにおいて必ず用いられる処理である。前述したように、単一版同時実行制御においては、書込み順序とコミット順序とを一致させている。これによって、データ依存性（Data  Dependency）と出力依存性（Write  Dependency）とを統一させることができるものの、反依存（Anti-dependency）については一致しない可能性がある。これによる分離性違反を効率的に検出するための手法は数多く提案されている。本実施の形態は、出力依存に関する最適化であり、反依存の検出方法については本実施の形態とは独立して組み合わせることが可能であるため、先行手法のどれを使用することも可能である。
【００６５】
［書込み制御処理の処理手順］
次に、制御処理装置１０のトランザクションの書込み制御処理の処理手順を説明する。図７は、図１に示す制御処理装置１０による書込み制御処理の処理手順のフローチャートである。
【００６６】
図７に示すように、制御処理装置１０は、トランザクションの書込み命令を受けた場合（ステップＳ１）、判定部１３１が、最適化の可否を判定する。具体的には、判定部１３１は、トランザクションの書込みを、書込みロックを用いて実行するか書込みロックを用いないで実行するかを判定する（ステップＳ２）。
【００６７】
判定部１３１が、トランザクションの書込みを、書込みロックを用いないで実行すると判定した場合は（ステップＳ２：Ｙｅｓ）、最適化部１３２は、トランザクションの書込み命令を破棄する最適化処理を行う（ステップＳ３）。これに対し、判定部１３１が、トランザクションの書込みを、書込みロックを用いて実行すると判定した場合は（ステップＳ２：Ｎｏ）、書込み部１３３は、書込みロックを用いた書込み処理を行う。具体的には、書込み部１３３は、書込みロックを獲得し（ステップＳ４）、ログ先行書込みを行い（ステップＳ５）、データを更新してから（ステップＳ６）、ロックを開放する（ステップＳ７）。
【００６８】
そして、返却部１３４は、ステップＳ３終了後、または、ステップＳ７終了後、トランザクションの書込みが成功した旨を命令元に返却して（ステップＳ８）、処理を終了する。
【００６９】
［実施の形態の効果］
このように、実施の形態に係る制御処理装置１０は、トランザクションの書込み命令を受けた場合に、トランザクションの書込みを、書込みロックを用いて実行するか書込みロックを用いないで実行するかを判定する。そして、制御処理装置１０は、トランザクションの書込みを、書込みロックを用いて実行すると判定した場合にはトランザクションに対する書込みロックを獲得してトランザクションの書込みを実行する。また、制御処理装置１０は、トランザクションの書込みを、書込みロックを用いないで実行すると判定した場合には、トランザクションの書込み命令を破棄する。そして、制御処理装置１０は、書込み後または書込み命令破棄後、トランザクションの書込みが成功した旨を命令元に返却する。
【００７０】
したがって、制御処理装置１０によれば、書込みロックを用いないと判定した場合には、実際の書込みを行わず書き込み命令を破棄するため、時間計算量と空間計算量とを大幅に削減でき、処理全体の高速化を可能にする。すなわち、制御処理装置１０によれば、書込みが競合した場合であっても、性能低下を防止することができる。また、制御処理装置１０によれば、書込みロックを用いて書込みを行うと判定した場合には、トランザクションに対する書込みロックを獲得してトランザクションの書込みを実行する、すなわち、単一版同時実行制御アルゴリズムを適用する。このため、制御処理装置１０によれば、単一版同時実行制御アルゴリズムが有する高い実装効率と処理性能とを損なうこともない。
【００７１】
そして、制御処理装置１０では、アトミックに操作可能なブルームフィルタ１２１を追加している。これによって、判定部１３１は、ブルームフィルタ１２１に既に記録された内容の読込みを伴わない書込み命令について、判定対象の書込み命令の分離性の保証を検証することができる。この際、判定部１３１は、ブルームフィルタ１２１を参照し、複数の書込み命令の依存関係の有無に応じて、判定対象の書込み命令の分離性を検証する。そして、最適化部１３２は、アトミックなＣＡＳ命令にしたがってトランザクションの書込み命令の破棄を実行するとともに、書込み命令を破棄した旨をブルームフィルタ１２１に記録する。
【００７２】
したがって、本実施の形態では、読込みを伴わない書込み処理、すなわちBlind  Writeについて、これが存在せずともＭＶＳＲに影響を与えない場合には、実際に書込み処理を行わず破棄することによって、処理全体を高速化している。
【００７３】
また、制御処理装置１０は、既存の単一版同時実行制御アルゴリズムに、ブルームフィルタ１２１を追加することのみで実装が可能であるため、非常に汎用的である。
【００７４】
このように、制御処理装置１０では、ＣＳＲを等価性に用いる単一版同時実行制御アルゴリズムに、アトミック操作可能なブルームフィルタ１２１を追加して、ＭＶＳＲを等価性に用いるアルゴリズムに拡張するとともに、書込み競合時でも一部のトランザクションの書込みを破棄するため、処理を高速化できる。
【００７５】
［実施形態のシステム構成について］
図１に示した制御処理装置１０の各構成要素は機能概念的なものであり、必ずしも物理的に図示のように構成されていることを要しない。すなわち、制御処理装置１０の機能の分散および統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散または統合して構成することができる。
【００７６】
また、制御処理装置１０においておこなわれる各処理は、全部または任意の一部が、ＣＰＵおよびＣＰＵにより解析実行されるプログラムにて実現されてもよい。また、制御処理装置１０においておこなわれる各処理は、ワイヤードロジックによるハードウェアとして実現されてもよい。
【００７７】
また、実施の形態において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行うこともできる。もしくは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的に行うこともできる。この他、上述および図示の処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて適宜変更することができる。
【００７８】
［プログラム］
図８は、プログラムが実行されることにより、制御処理装置１０が実現されるコンピュータの一例を示す図である。コンピュータ１０００は、例えば、メモリ１０１０、ＣＰＵ１０２０を有する。また、コンピュータ１０００は、ハードディスクドライブインタフェース１０３０、ディスクドライブインタフェース１０４０、シリアルポートインタフェース１０５０、ビデオアダプタ１０６０、ネットワークインタフェース１０７０を有する。これらの各部は、バス１０８０によって接続される。
【００７９】
メモリ１０１０は、ＲＯＭ１０１１およびＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１１００に挿入される。シリアルポートインタフェース１０５０は、例えばマウス１１１０、キーボード１１２０に接続される。ビデオアダプタ１０６０は、例えばディスプレイ１１３０に接続される。
【００８０】
ハードディスクドライブ１０９０は、例えば、ＯＳ（Operating  System）１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、制御処理装置１０の各処理を規定するプログラムは、コンピュータ１０００により実行可能なコードが記述されたプログラムモジュール１０９３として実装される。プログラムモジュール１０９３は、例えばハードディスクドライブ１０９０に記憶される。例えば、制御処理装置１０における機能構成と同様の処理を実行するためのプログラムモジュール１０９３が、ハードディスクドライブ１０９０に記憶される。なお、ハードディスクドライブ１０９０は、ＳＳＤ（Solid  State  Drive）により代替されてもよい。
【００８１】
また、上述した実施の形態の処理で用いられる設定データは、プログラムデータ１０９４として、例えばメモリ１０１０やハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して実行する。
【００８２】
なお、プログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限らず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、プログラムモジュール１０９３およびプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶されてもよい。そして、プログラムモジュール１０９３およびプログラムデータ１０９４は、他のコンピュータから、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【００８３】
以上、本発明者によってなされた発明を適用した実施の形態について説明したが、本実施の形態による本発明の開示の一部をなす記述および図面により本発明は限定されることはない。すなわち、本実施の形態に基づいて当業者等によりなされる他の実施の形態、実施例および運用技術等はすべて本発明の範疇に含まれる。
【符号の説明】
【００８４】
１０  制御処理装置
１１  入力部
１２  記憶部
１３  制御部
１４  出力部
１２１  ブルームフィルタ
１３１  判定部
１３２  最適化部
１３３  書込み部
１３４  返却部
【図１】
2019185492.tif 000007
【図２】
2019185492.tif 000008
【図３】
2019185492.tif 000009
【図４】
2019185492.tif 000010
【図５】
2019185492.tif 000011
【図６】
2019185492.tif 000012
【図７】
2019185492.tif 000013
【図８】
2019185492.tif 000014