(57)【特許請求の範囲】
【請求項１】
複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための方法であって、
前記分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶するステップであって、前記データアイテムが、順序付け規則によって全順序的であり、前記プロセスの少なくとも一部が、異なる処理モジュール上でランされている、前記記憶するステップと、
前記複数のプロセスのうちの２以上を使用して各プロセスの自身に割り当てられたトランザクションを処理するステップであって、前記複数のプロセスのうちの前記２以上のうちの１つを使用してトランザクションを処理することが、
前記データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、前記要求が第１の順序である、前記受信すること、
前記データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、前記ロックを前記第１の順序で順番に取得すること、
前記ロックのいずれかが前記第１の時間間隔以内に取得されない場合に、前記ロックのうちの少なくとも２つに関して前記順序付け規則に合致する第２の順序を決定すること、及び
データアイテムに対するロックを前記第２の順序で順番に取得することを含む、処理されている前記トランザクションを再始動することを含む、前記処理するステップとを含む、前記方法。
【請求項２】
処理されているトランザクションを再始動することが、前記トランザクションをロールバックし、データアイテムに対する前記トランザクションを処理するために取得したすべての既存のロックを解放することを含む請求項１に記載の方法。
【請求項３】
第２の順序が、少なくとも、ロックが第１の時間間隔以内に取得されたデータアイテムに関して順序付け規則に合致する請求項１又は２に記載の方法。
【請求項４】
処理するステップが、順序付け規則に基づく第１の時間遅延以内にロックが取得されたデータアイテムの位置を特定する情報を記憶することをさらに含み、第２の順序を決定することが、前記第１の時間遅延以内にロックが取得された前記データアイテムの前記位置を特定する記憶された情報に少なくとも部分的に基づいて前記第２の順序を決定することを含む請求項１〜３のいずれかに記載の方法。
【請求項５】
第２の順序を決定することが、前記トランザクションが処理する前記データアイテムに前記順序付け規則に従って割り振られた番号に基づいて、ロックを取得するための動作順のリストをソートすることを含む請求項１〜４のいずれかに記載の方法。
【請求項６】
処理するステップが、第１の順序が順序付け規則に合致するか否かを決定し、前記第１の順序が前記順序付け規則に合致する場合に、ロックが第１の時間間隔以内に取得されなかったすべてのデータアイテムに対するロックを前記第１の時間間隔よりも長く待つことをさらに含む請求項１〜５のいずれかに記載の方法。
【請求項７】
処理するステップが、１組の要求を受信したプロセスをロールバックするかどうか決定するために、複数のプロセスのうちの２以上のうちのその他のプロセスの優先度に対する、前記１組の要求を受信したプロセスの優先度を決定することをさらに含む、請求項１〜６のいずれかに記載の方法。
【請求項８】
処理されているトランザクションを再始動することが、優先度を決定した後に実施される請求項７に記載の方法。
【請求項９】
処理されているトランザクションを再始動することが、１組の要求によってアクセスが要求された少なくとも１つのデータアイテムに対するロックの状態が解放された状態であると決定した後に実施される請求項１〜８のいずれかに記載の方法。
【請求項１０】
処理するステップが、第１の順序が順序付け規則に合致するか否かを決定することをさらに含み、処理されているトランザクションを再始動することが、第１の順序が前記順序付け規則に合致しないと決定してから第２の時間間隔の後に実施される請求項１〜５のいずれかに記載の方法。
【請求項１１】
第２の時間間隔が、第１の時間間隔よりも長い請求項１０に記載の方法。
【請求項１２】
第１の時間間隔が、１秒未満である請求項１〜１１のいずれかに記載の方法。
【請求項１３】
処理するステップが、処理されているトランザクションがコミットされるか、中止されるか、又は再始動されるまでデータアイテムに対して取得されたすべてのロックを保持することと、処理されている前記トランザクションがコミットされるか、中止されるか、又は再始動されるときに前記データアイテムに対する前記ロックを解放することとをさらに含む請求項１〜１２のいずれかに記載の方法。
【請求項１４】
データアイテムに対するロックが、単一のロック解除状態及び１又は２以上のロック状態を含む少なくとも２つの状態を含む請求項１〜１３のいずれかに記載の方法。
【請求項１５】
データアイテムに対するロックを取得することが、前記データアイテムに関連するロックの状態をロック状態のうちの１つに変更することを含む請求項１４に記載の方法。
【請求項１６】
データアイテムに対するロックを解放することが、前記データアイテムに関連するロックの状態をロック状態のうちの１つからロック解除状態に変更することを含む請求項１４又は１５に記載の方法。
【請求項１７】
データアイテムに対するロックが、ロックされたデータアイテムへの完全なアクセスを単一のプロセスにのみ許可する少なくとも１つの排他的ロック状態を含む請求項１４〜１６のいずれかに記載の方法。
【請求項１８】
データアイテムに対するロックが、ロックされたデータアイテムへの読み取りのみのアクセスを複数のプロセスに許可する少なくとも１つの共有ロック状態を含む請求項１４〜１７のいずれかに記載の方法。
【請求項１９】
複数のプロセスの少なくとも一部が、互いに非同期にランされている請求項１〜１８のいずれかに記載の方法。
【請求項２０】
トランザクションが、データベーストランザクションを含み、データアイテムが、データベースのレコードである請求項１〜１９のいずれかに記載の方法。
【請求項２１】
データベースが、インメモリデータベースである請求項２０に記載の方法。
【請求項２２】
データストレージシステムが、データベースの複数のノードに分散される請求項２０又は２１に記載の方法。
【請求項２３】
複数のプロセスのうちの２以上の少なくとも一部が、処理モジュールのうちの異なる処理モジュール上でランされている請求項１〜２２のいずれかに記載の方法。
【請求項２４】
１又は２以上のコンピュータによって実行されるときに、複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための動作を１又は２以上のコンピュータに実施させる命令を記憶するコンピュータ可読ストレージ媒体であって、前記動作が、
前記分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶する動作であって、前記データアイテムが、順序付け規則によって全順序的であり、前記プロセスの少なくとも一部が、異なる処理モジュール上でランされている、前記記憶する動作と、
前記複数のプロセスのうちの２以上を使用して各プロセスの自身に割り当てられたトランザクションを処理する動作であって、前記複数のプロセスのうちの前記２以上のうちの１つを使用してトランザクションを処理することが、
前記データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、前記要求が第１の順序である、前記受信すること、
前記データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、前記ロックを前記第１の順序で順番に取得すること、
前記ロックのいずれかが前記第１の時間間隔以内に取得されない場合に、前記ロックのうちの少なくとも２つに関して前記順序付け規則に合致する第２の順序を決定すること、及び
データアイテムに対するロックを前記第２の順序で順番に取得することを含む、処理されている前記トランザクションを再始動することを含む、前記処理する動作とを含む、前記コンピュータ可読ストレージ媒体。
【請求項２５】
トランザクションを処理するための分散型コンピューティングシステムであって、
複数の処理モジュールと、
前記分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能であり、データアイテムを記憶するように構成されたデータストレージシステムであって、前記データアイテムが、順序付け規則によって全順序的であり、前記プロセスの少なくとも一部が、異なる処理モジュール上でランされている、前記データストレージシステムとを含み、
前記複数のプロセスのうちの２以上が、各プロセスの自身に割り当てられたトランザクションを処理するように構成され、前記複数のプロセスのうちの前記２以上のうちの１つを使用してトランザクションを処理することが、
前記データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、前記要求が第１の順序である、前記受信すること、
前記データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、前記ロックを前記第１の順序で順番に取得すること、
前記ロックのいずれかが前記第１の時間間隔以内に取得されない場合に、前記ロックのうちの少なくとも２つに関して前記順序付け規則に合致する第２の順序を決定すること、及び
データアイテムに対するロックを前記第２の順序で順番に取得することを含む、処理されている前記トランザクションを再始動することを含む、前記分散型コンピューティングシステム。
【請求項２６】
複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための方法であって、
前記分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶するステップであって、前記データアイテムが、順序付け規則によって全順序的であり、前記プロセスの少なくとも一部が、異なる処理モジュール上でランされている、前記記憶するステップと、
前記複数のプロセスのうちの２以上を使用して各プロセスの自身に割り当てられたトランザクションを処理するステップであって、前記複数のプロセスのうちの前記２以上のうちの１つを使用してトランザクションを処理することが、
前記データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、前記要求が第１の順序である、前記受信すること、
前記データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、前記ロックを前記第１の順序で順番に取得すること、
前記ロックのいずれかが前記第１の時間間隔以内に取得されない場合に、前記第１の順序が前記順序付け規則に合致するか否かを決定すること、及び
前記第１の順序が前記順序付け規則に合致しない場合に、処理されている前記トランザクションを再始動することを含む、前記処理するステップとを含む、前記方法。
【請求項２７】
処理されているトランザクションを再始動することが、前記トランザクションをロールバックし、データアイテムに対する前記トランザクションを処理するために取得したすべての既存のロックを解放し、第１の順序とは異なる第２の順序で順番にデータアイテムに対するロックを取得することを含む請求項２６に記載の方法。
【請求項２８】
第２の順序が、少なくとも、ロックが第１の時間間隔以内に取得されたデータアイテムに関して順序付け規則に合致する請求項２７に記載の方法。
【請求項２９】
処理するステップが、順序付け規則に基づく第１の時間遅延以内にロックが取得されたデータアイテムの位置を特定する情報を記憶することをさらに含み、第２の順序を決定することが、前記第１の時間遅延以内にロックが取得された前記データアイテムの前記位置を特定する記憶された情報に少なくとも部分的に基づいて前記第２の順序を決定することを含む、請求項２７〜２８のいずれかに記載の方法。
【請求項３０】
第２の順序が、前記トランザクションが処理する前記データアイテムに前記順序付け規則に従って割り振られた番号に基づいて、ロックを取得するための動作順のリストをソートすることに基づいて決定される請求項２７〜２９のいずれかに記載の方法。
【請求項３１】
処理するステップが、第１の順序が順序付け規則に合致する場合に、ロックが第１の時間間隔以内に取得されなかったすべてのデータアイテムに対するロックを前記第１の時間間隔よりも長く待つことをさらに含む請求項２６〜３０のいずれかに記載の方法。
【請求項３２】
処理するステップが、１組の要求を受信したプロセスをロールバックするかどうか決定するために、複数のプロセスのうちの２以上のうちのその他のプロセスの優先度に対する、前記１組の要求を受信したプロセスの優先度を決定することをさらに含む、請求項２６〜３１のいずれかに記載の方法。
【請求項３３】
第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することが、優先度を決定した後に実施される請求項３２に記載の方法。
【請求項３４】
第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することが、１組の要求によってアクセスが要求された少なくとも１つのデータアイテムに対するロックの状態が解放された状態であると決定した後に実施される請求項２６〜３３のいずれかに記載の方法。
【請求項３５】
第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することが、前記第１の順序が前記順序付け規則に合致しないと決定してから第２の時間間隔の後に実施される請求項２６〜３３のいずれかに記載の方法。
【請求項３６】
第２の時間間隔が、第１の時間間隔よりも長い請求項３５に記載の方法。
【請求項３７】
第１の時間間隔が、１秒未満である請求項２６〜３６のいずれかに記載の方法。
【請求項３８】
処理するステップが、処理されているトランザクションがコミットされるか、中止されるか、又は再始動されるまでデータアイテムに対して取得されたすべてのロックを保持することと、処理されている前記トランザクションがコミットされるか、中止されるか、又は再始動されるときに前記データアイテムに対する前記ロックを解放することとをさらに含む請求項２６〜３７のいずれかに記載の方法。
【請求項３９】
データアイテムに対するロックが、単一のロック解除状態及び１又は２以上のロック状態を含む少なくとも２つの状態を含む請求項２６〜３８のいずれかに記載の方法。
【請求項４０】
データアイテムに対するロックを取得することが、前記データアイテムに関連するロックの状態をロック状態のうちの１つに変更することを含む請求項３９に記載の方法。
【請求項４１】
データアイテムに対するロックを解放することが、前記データアイテムに関連するロックの状態をロック状態のうちの１つからロック解除状態に変更することを含む請求項３９又は４０に記載の方法。
【請求項４２】
データアイテムに対するロックが、ロックされたデータアイテムへの完全なアクセスを単一のプロセスにのみ許可する少なくとも１つの排他的ロック状態を含む請求項３９〜４１のいずれかに記載の方法。
【請求項４３】
データアイテムに対するロックが、ロックされたデータアイテムへの読み取りのみのアクセスを複数のプロセスに許可する少なくとも１つの共有ロック状態を含む請求項３９〜４２のいずれかに記載の方法。
【請求項４４】
複数のプロセスの少なくとも一部が、互いに非同期にランされている請求項２６〜４３のいずれかに記載の方法。
【請求項４５】
トランザクションが、データベーストランザクションを含み、データアイテムが、データベースのレコードである請求項２６〜４４のいずれかに記載の方法。
【請求項４６】
データベースが、インメモリデータベースである請求項４５に記載の方法。
【請求項４７】
データストレージシステムが、データベースの複数のノードに分散される請求項４５又は４６に記載の方法。
【請求項４８】
複数のプロセスのうちの２以上の少なくとも一部が、処理モジュールのうちの異なる処理モジュール上で施行されている請求項２６〜４７のいずれかに記載の方法。
【請求項４９】
１又は２以上のコンピュータによって実行されるときに、複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための動作を１又は２以上のコンピュータに実施させる命令を記憶するコンピュータ可読ストレージ媒体であって、前記動作が、
前記分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶する動作であって、前記データアイテムが、順序付け規則によって全順序的であり、前記プロセスの少なくとも一部が、異なる処理モジュール上でランされている、前記記憶する動作と、
前記複数のプロセスのうちの２以上を使用して各プロセスの自身に割り当てられたトランザクションを処理する動作であって、前記複数のプロセスのうちの前記２以上のうちの１つを使用してトランザクションを処理することが、
前記データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、前記要求が第１の順序である、前記受信すること、
前記データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、前記ロックを前記第１の順序で順番に取得すること、
前記ロックのいずれかが前記第１の時間間隔以内に取得されない場合に、前記第１の順序が前記順序付け規則に合致するか否かを決定すること、及び
前記第１の順序が前記順序付け規則に合致しない場合に、処理されている前記トランザクションを再始動することを含む、前記処理する動作とを含む、前記コンピュータ可読ストレージ媒体。
【請求項５０】
トランザクションを処理するための分散型コンピューティングシステムであって、
複数の処理モジュールと、
前記分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能であり、データアイテムを記憶するように構成されたデータストレージシステムであって、前記データアイテムが、順序付け規則によって全順序的であり、前記プロセスの少なくとも一部が、異なる処理モジュール上でランされている、前記データストレージシステムとを含み、
前記複数のプロセスのうちの２以上が、各プロセスの自身に割り当てられたトランザクションを処理するように構成され、前記複数のプロセスのうちの前記２以上のうちの１つを使用してトランザクションを処理することが、
前記データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、前記要求が第１の順序である、前記受信すること、
前記データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、前記ロックを前記第１の順序で順番に取得すること、
前記ロックのいずれかが前記第１の時間間隔以内に取得されない場合に、前記第１の順序が前記順序付け規則に合致するか否かを決定すること、及び
前記第１の順序が前記順序付け規則に合致しない場合に、処理されている前記トランザクションを再始動することを含む、前記分散型コンピューティングシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、２０１５年４月１日に出願した米国特許出願第６２／１４１，３８８号明細書の優先権を主張するものである。
【０００２】
本出願は、分散型コンピューティングシステムにおいてトランザクションを処理することに関する。特に、本出願は、複数のデータ処理モジュールと、例えば、いくつかのデータベースノードに分散される可能性があるデータベースとの分散型ネットワークにおいてデータベーストランザクションを処理するように特に適合される分散型コンピューティングシステム、コンピュータによって履行される方法(computer-implemented methods)、及びコンピュータ可読ストレージ媒体にも関する。
【背景技術】
【０００３】
データベースは、ソフトウェアプログラムを使用して管理され、問い合わせられ得る永続的なデータの構造化された組である。トランザクション型（transactional）データベース管理システムは、データベース「トランザクション」を使用してデータベース内のデータに働きかける（例えば、記憶する及び操作する）リレーショナルデータベースシステムを含み得る。概して、データベーストランザクションは、データベースに対してデータベース管理システムによって実施される（１又は２以上の動作を含む）単一の作業単位を象徴する。データベーストランザクションが確実に処理されることを保証するために、データベーストランザクションは、原子性がなければ(atomic)ならず（つまり、その１若しくは２以上の動作のすべてを含むトランザクションがすべて完了するか若しくは何らの影響も与えないかのどちらかでなければならず）、一貫性がなければ(consistent)ならず（つまり、トランザクションがデータベースをある有効な状態から別の有効な状態へと移さなければならず）、独立性がなければ(isolated)ならず（つまり、同時に実施されるトランザクションがデータベース内で、それらのトランザクションが逐次的に実行されたとした場合に至るのと同じ状態に至り）、永続性がなければ(durable)ならない（つまり、コミットされたトランザクションがシステムのクラッシュ、エラー、及びその他の問題に関係なくコミットされたままである）。データベーストランザクションのこの１組の特性は、「ＡＣＩＤ」と呼ばれることがある。データベーストランザクションは、１若しくは２以上のサーバコンピュータにおいてクライアントコンピュータからの要求に応答するために使用され得るオンライントランザクション処理（ＯＬＴＰ）システムなどの産業用システムにおいて使用される可能性があり、又はデータウェアハウスシステムを含むオンライン分析処理（ＯＬＡＰ）システムなどのその他のシステムが構築される基礎として使用される可能性がある。例えば、研究、健康管理、又は情報サービスに関連する産業を含むさまざまな種類の産業が、そのようなシステムを使用する可能性がある。
【０００４】
場合によっては、特に、ＡＣＩＤ特性を厳守することが困難であるシステム（例えば、分散型システム）において、ＡＣＩＤ特性のうちの１又は２以上が、特定の条件の下で緩められる可能性がある。その他の状況においては、たとえデータベースがいくつかのデータベースノードに分散されるときでも、トランザクションがＡＣＩＤ特性を維持することが重要である。分散型データベースなどの分散型システムにおいては、いずれかのＡＣＩＤ特性をサポートするために使用されるいずれの分散型アルゴリズムも、下でより詳細に説明されるように、ノード間のデッドロックを避けるようにして実施される必要がある。しかし、実際のデッドロックの状況を検出する能力を提供するか、又は常に厳密なデッドロックの回避を保証する特定の分散型アルゴリズム（例えば、原子性のある(atomic)コミットのための２相コミットプロトコル、又は同時実行制御（concurrency control）のための２相ロックプロトコル）は、システムの性能に影響を与える。
【０００５】
通常の集中的なトランザクション型データベースにおいては、上述のデッドロックなどのデッドロックの検出、防止、及び／又は回避のための方法がよく知られている。しかし、複数の同時に実行されるトランザクションの場合、デッドロックの起こる見込みがより高いので、分散型データベースにおいては、デッドロックを検出し、回避するための解決策を見つけることがますます難しくなる。いくつかの分散型データベースの動作は、特に耐障害アルゴリズムによって解決することが難しい分散型コンピューティングにおける問題に対応する。いくつかの種類の障害に関しては、分散型コンピューティングにおける一部の問題が、耐障害分散型アルゴリズムによって解決することが不可能であることが分かってさえいる。
【発明の概要】
【課題を解決するための手段】
【０００６】
一態様においては、概して、複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための方法が、分散型コンピューティングシステムにおいてラン(running)される複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶するステップであって、データアイテムが、順序付け規則によって全順序的（totally ordered）であり、プロセスの少なくとも一部が、異なる処理モジュール上でランされている、ステップと、複数のプロセスのうちの２以上（plurality）を使用してトランザクションを処理するステップとを含む。複数のプロセスのうちの２以上のうちの１つを使用してトランザクションを処理することは、データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、要求が第１の順序である、受信すること、データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、ロックを第１の順序で順番に取得すること、ロックのいずれかが第１の時間間隔以内に取得されない場合に、ロックのうちの少なくとも２つに関して順序付け規則に合致する第２の順序を決定すること、及びデータアイテムに対するロックを第２の順序で順番に取得することを含む、処理されているトランザクションを再始動することを含む。
【０００７】
態様は、以下の特徴のうちの１又は２以上を含み得る。
【０００８】
処理されているトランザクションを再始動することは、トランザクションをロールバックし、データアイテムに対するすべての既存のロックを解放することを含む。
【０００９】
第２の順序は、少なくとも、ロックが第１の時間間隔以内に取得されたデータアイテムに関して順序付け規則に合致する。
【００１０】
処理するステップは、ロックが第１の時間間隔以内に取得されたデータアイテムの順序付け規則に基づく位置を特定する情報を記憶することをさらに含み、第２の順序を決定することは、位置を特定する記憶された情報に少なくとも部分的に基づいて第２の順序を決定することを含む。
【００１１】
第２の順序を決定することは順序付け規則に従って、ロックを取得するための動作のリストをソートすることを含む。
【００１２】
処理するステップは、第１の順序が順序付け規則に合致するか否かを決定し、第１の順序が順序付け規則に合致する場合に、ロックが第１の時間間隔以内に取得されなかったすべてのデータアイテムに対するロックを第１の時間間隔よりも長く待つことをさらに含む。
【００１３】
処理するステップは、複数のプロセスのうちの２以上のうちのその他のプロセスに対する、１組の要求を受信したプロセスの優先度を決定することをさらに含む。
【００１４】
処理されているトランザクションを再始動することは、優先度を決定した後に実施される(performed)。
【００１５】
処理されているトランザクションを再始動することは、１組の要求によってアクセスが要求された少なくとも１つのデータアイテムに対するロックの状態が変わったと決定した後に実施される。
【００１６】
処理するステップは、第１の順序が順序付け規則に合致するか否かを決定することをさらに含み、処理されているトランザクションを再始動することは、第１の順序が順序付け規則に合致しないと決定してから第２の時間間隔の後に実施される。
【００１７】
第２の時間間隔は、第１の時間間隔よりも長い。
【００１８】
第１の時間間隔は、１秒未満である。
【００１９】
処理するステップは、処理されているトランザクションがコミットされるか、中止されるか、又は再始動されるまでデータアイテムに対して取得されたすべてのロックを保持することと、処理されているトランザクションがコミットされるか、中止されるか、又は再始動されるときにデータアイテムに対するロックを解放することとをさらに含む。
【００２０】
データアイテムに対するロックは、単一のロック解除状態及び１又は２以上のロック状態を含む少なくとも２つの状態を含む。
【００２１】
データアイテムに対するロックを取得することは、データアイテムに関連するロックの状態をロック状態のうちの１つに変更することを含む。
【００２２】
データアイテムに対するロックを解放することは、データアイテムに関連するロックの状態をロック状態のうちの１つからロック解除状態に変更することを含む。
【００２３】
データアイテムに対するロックは、ロックされたデータアイテムへの完全なアクセスを単一のプロセスにのみ許可する少なくとも１つの排他的ロック状態を含む。
【００２４】
データアイテムに対するロックは、ロックされたデータアイテムへの読み取りのみのアクセスを複数のプロセスに許可する少なくとも１つの共有ロック状態を含む。
【００２５】
複数のプロセスの少なくとも一部は、互いに非同期にランされている。
【００２６】
トランザクションは、データベーストランザクションを含み、データアイテムは、データベースのレコードである。
【００２７】
データベースは、インメモリデータベースである。
【００２８】
データストレージシステムは、データベースの複数のノードに分散される。
【００２９】
複数のプロセスのうちの２以上の少なくとも一部は、処理モジュールのうちの異なる処理モジュール上でランされている。
【００３０】
別の態様においては、概して、１又は２以上のコンピュータによって実行されるときに、複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための動作を１又は２以上のコンピュータに実施させる命令を記憶するコンピュータ可読ストレージ媒体であって、動作が、分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶する動作であって、データアイテムが、順序付け規則によって全順序的であり、プロセスの少なくとも一部が、異なる処理モジュール上でランされている、記憶する動作と、複数のプロセスのうちの２以上を使用してトランザクションを処理する動作であって、複数のプロセスのうちの２以上のうちの１つを使用してトランザクションを処理することが、データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、要求が第１の順序である、受信すること、データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、ロックを第１の順序で順番に取得すること、ロックのいずれかが第１の時間間隔以内に取得されない場合に、ロックのうちの少なくとも２つに関して順序付け規則に合致する第２の順序を決定すること、及びデータアイテムに対するロックを第２の順序で順番に取得することを含む、処理されているトランザクションを再始動することを含む、処理する動作を含む、コンピュータ可読ストレージ媒体。
【００３１】
別の態様においては、概して、トランザクションを処理するための分散型コンピューティングシステムが、複数の処理モジュールと、分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能であり、データアイテムを記憶するデータストレージシステムであって、データアイテムが、順序付け規則によって全順序的であり、プロセスの少なくとも一部が、異なる処理モジュール上でランされている、データストレージシステムとを含む。複数のプロセスのうちの２以上が、トランザクションを処理する。複数のプロセスのうちの２以上のうちの１つを使用してトランザクションを処理することは、データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、要求が第１の順序である、受信すること、データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、ロックを第１の順序で順番に取得すること、ロックのいずれかが第１の時間間隔以内に取得されない場合に、ロックのうちの少なくとも２つに関して順序付け規則に合致する第２の順序を決定すること、及びデータアイテムに対するロックを第２の順序で順番に取得することを含む、処理されているトランザクションを再始動することを含む。
【００３２】
別の態様においては、概して、複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための方法が、分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶するステップであって、データアイテムが、順序付け規則によって全順序的であり、プロセスの少なくとも一部が、異なる処理モジュール上でランされている、記憶するステップと、複数のプロセスのうちの２以上を使用してトランザクションを処理するステップとを含む。複数のプロセスのうちの２以上のうちの１つを使用してトランザクションを処理することは、データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、要求が第１の順序である、受信すること、データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、ロックを第１の順序で順番に取得すること、ロックのいずれかが第１の時間間隔以内に取得されない場合に、第１の順序が順序付け規則に合致するか否かを決定すること、及び第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することを含む。
【００３３】
態様は、以下の特徴のうちの１又は２以上を含み得る。
【００３４】
処理されているトランザクションを再始動することは、トランザクションをロールバックし、データアイテムに対するすべての既存のロックを解放し、第１の順序とは異なる第２の順序で順番にデータアイテムに対するロックを取得することを含む。
【００３５】
第２の順序は、少なくとも、ロックが第１の時間間隔以内に取得されたデータアイテムに関して順序付け規則に合致する。
【００３６】
処理するステップは、ロックが第１の時間間隔以内に取得されたデータアイテムの順序付け規則に基づく位置を特定する情報を記憶し、位置を特定する記憶された情報に少なくとも部分的に基づいて第２の順序を決定することをさらに含む。
【００３７】
第２の順序は、順序付け規則に従って、ロックを取得するための動作のリストをソートすることに基づいて決定される。
【００３８】
処理するステップは、第１の順序が順序付け規則に合致する場合に、ロックが第１の時間間隔以内に取得されなかったすべてのデータアイテムに対するロックを第１の時間間隔よりも長く待つことをさらに含む。
【００３９】
処理するステップは、複数のプロセスのうちの２以上のうちのその他のプロセスに対する、１組の要求を受信したプロセスの優先度を決定することをさらに含む。
【００４０】
第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することは、優先度を決定した後に実施される。
【００４１】
第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することは、１組の要求によってアクセスが要求された少なくとも１つのデータアイテムに対するロックの状態が変わったと決定した後に実施される。
【００４２】
第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することは、第１の順序が順序付け規則に合致しないと決定してから第２の時間間隔の後に実施される。
【００４３】
第２の時間間隔は、第１の時間間隔よりも長い。
【００４４】
第１の時間間隔は、１秒未満である。
【００４５】
処理するステップは、処理されているトランザクションがコミットされるか、中止されるか、又は再始動されるまでデータアイテムに対して取得されたすべてのロックを保持することと、処理されているトランザクションがコミットされるか、中止されるか、又は再始動されるときにデータアイテムに対するロックを解放することとをさらに含む。
【００４６】
データアイテムに対するロックは、単一のロック解除状態及び１又は２以上のロック状態を含む少なくとも２つの状態を含む。
【００４７】
データアイテムに対するロックを取得することは、データアイテムに関連するロックの状態をロック状態のうちの１つに変更することを含む。
【００４８】
データアイテムに対するロックを解放することは、データアイテムに関連するロックの状態をロック状態のうちの１つからロック解除状態に変更することを含む。
【００４９】
データアイテムに対するロックは、ロックされたデータアイテムへの完全なアクセスを単一のプロセスにのみ許可する少なくとも１つの排他的ロック状態を含む。
【００５０】
データアイテムに対するロックは、ロックされたデータアイテムへの読み取りのみのアクセスを複数のプロセスに許可する少なくとも１つの共有ロック状態を含む。
【００５１】
複数のプロセスの少なくとも一部は、互いに非同期にランされている。
【００５２】
トランザクションは、データベーストランザクションを含み、データアイテムは、データベースのレコードである。
【００５３】
データベースは、インメモリデータベースである。
【００５４】
データストレージシステムは、データベースの複数のノードに分散される。
【００５５】
複数のプロセスのうちの２以上の少なくとも一部は、処理モジュールのうちの異なる処理モジュール上でランされている。
【００５６】
別の態様においては、概して、１又は２以上のコンピュータによって実行されるときに、複数の処理モジュールを含む分散型コンピューティングシステムにおいてトランザクションを処理するための動作を１又は２以上のコンピュータに実施させる命令を記憶するコンピュータ可読ストレージ媒体であって、動作が、分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能なデータストレージシステムにデータアイテムを記憶する動作であって、データアイテムが、順序付け規則によって全順序的であり、プロセスの少なくとも一部が、異なる処理モジュール上でランされている、記憶する動作と、複数のプロセスのうちの２以上を使用してトランザクションを処理する動作であって、複数のプロセスのうちの２以上のうちの１つを使用してトランザクションを処理することが、データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、要求が第１の順序である、受信すること、データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、ロックを第１の順序で順番に取得すること、ロックのいずれかが第１の時間間隔以内に取得されない場合に、第１の順序が順序付け規則に合致するか否かを決定すること、及び第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することを含む、処理する動作とを含む、コンピュータ可読ストレージ媒体。
【００５７】
別の態様においては、概して、トランザクションを処理するための分散型コンピューティングシステムが、複数の処理モジュールと、分散型コンピューティングシステムにおいてランされる複数のプロセスがアクセス可能であり、データアイテムを記憶するデータストレージシステムであって、データアイテムが、順序付け規則によって全順序的であり、プロセスの少なくとも一部が、異なる処理モジュール上でランされている、データストレージシステムとを含む。複数のプロセスのうちの２以上が、トランザクションを処理する。複数のプロセスのうちの２以上のうちの１つを使用してトランザクションを処理することは、データストレージシステムに記憶されたデータアイテムにアクセスするための１組の要求を受信することであって、要求が第１の順序である、受信すること、データアイテムに対するロックの各々が第１の時間間隔以内に取得される場合に、ロックを第１の順序で順番に取得すること、ロックのいずれかが第１の時間間隔以内に取得されない場合に、第１の順序が順序付け規則に合致するか否かを決定すること、及び第１の順序が順序付け規則に合致しない場合に、処理されているトランザクションを再始動することを含む。
【００５８】
態様は、以下の利点のうちの１又は２以上を含む可能性がある。
【００５９】
その他の利点の中でもとりわけ、態様は、システムの性能(system performance)を維持しながら、分散型データベースにおいてデッドロックを防止する。
【００６０】
態様は、ロールバックされ続けることによってトランザクションが欠乏に苦しむことがないことを保証する。
【００６１】
態様は、分散型データベースにおける効率的なトランザクション型データ処理に依拠する物流又は産業プロセスがデッドロックの回数の削減又はより速いトランザクション型データ処理の恩恵を直接受けることができることを可能にする。
【００６２】
態様は、トランザクションによって指定された順序に従ってデータアイテムに対するロックを取得し、成功しない場合、知られているデッドロックのないロック順序に戻ることを可能にする。
【００６３】
本発明のその他の特徴及び利点は、以下の説明及び請求項から明らかになるであろう。
【図面の簡単な説明】
【００６４】
【図１】分散型データベースシステムを含むデータ処理システムのブロック図である。
【図２】２つのデータベーストランザクションの間のデッドロックを示す図である。
【図３】予防的デッドロック回避（pre-emptive deadlock avoidance）アルゴリズムの流れ図である。
【図４】第１の潜在的なデッドロック状況への図３のアルゴリズムの適用を示す図である。
【図５】第２の潜在的なデッドロック状況への図３のアルゴリズムの適用を示す図である。
【発明を実施するための形態】
【００６５】
１  概要
図１は、デッドロック回避技術が使用され得るデータ処理システム１００の例を示す。システム１００は、通信ネットワーク１０６（例えば、ＷＡＮ、ＬＡＮ、又はマルチプロセッサシステム内若しくはチップ上のネットワーク）を介してＭ個のデータベースクライアント１０４と通信する分散型データベースシステム１０２を含む。
【００６６】
分散型データベースシステム１０２は、データベースＤのフラグメント（fragment）Ｄｎが割り当てられるＮ個のノード１０８を含む。各ノード１０８は、データベースＤのフラグメントが記憶されるデータストレージデバイス１１２と、データストレージデバイス１１２上のデータベースのフラグメントを管理する（例えば、サーバコンピュータ、プロセッサ、又はプロセッサコアによって制御される）処理モジュールであるデータベースマネージャ１１０とを含む。所与のノード１０８のためのデータベースマネージャ１１０は、データストレージデバイス１１２上のデータベースのフラグメントとクライアント１０４及びその他のノード１０８などのノード１０８の外部のエンティティ（entity）との間のインターフェースとしても働く。図１に明示的に示されていないが、一部の例において、各データベースマネージャ１１０は、データベースマネージャ１１０によって管理されるデータストレージデバイス１１２上に記憶されるデータベースのフラグメントの管理に責任を負うデータプロセッサと、２つ以上のノード１０８上のデータベースフラグメントへのアクセスを必要とする要求を処理するためのアプリケーションプロセッサと、クライアント１０４及びその他のノード１０８と通信するための通信ソフトウェアとを含む。
【００６７】
動作中、クライアント１０４は、データベースＤに対して実行するための１又は２以上のデータベーストランザクションを指定する。クライアント１０４によって指定されたトランザクションは、ノード１０８のデータベースマネージャ１１０のうちの１又は２以上に通信ネットワーク１０６を介して送信される。トランザクションがＮ個のノード１０８の第ｎのデータベースマネージャ１１０に到着するとき、第ｎのデータベースマネージャ１１０は、トランザクションを評価し、第ｎのデータベースマネージャ１１０によって管理される第ｎのデータストレージデバイス１１２上に記憶されるデータベースのフラグメントに対してトランザクションを実行するためのアクセス計画（access plan）（例えば、問い合わせ計画（query plan））を生じさせる。
【００６８】
一部の例においては、トランザクションが複数のノード１０８に記憶されるデータベースの複数のフラグメントにアクセスするとき、第ｎのデータベースマネージャ１１０が、複数のノード１０８のデータベースマネージャ１１０にトランザクション及び／又はアクセス計画を転送する。その他の例においては、トランザクションが生じたクライアント１０４が、トランザクションを完了するために必要とされる適切なノード１０８にトランザクションを送信する。さらにその他の例においては、トランザクションが生じたクライアント１０４が、リーダーノードとして指定されるノード１０８のうちの１つにトランザクションを送信し、リーダーノードが、トランザクションを完了するために必要とされる適切なノード１０８に適切なアクセス計画を送信する。
【００６９】
１又は２以上のデータベーストランザクションに関するアクセス計画が適切なノード１０８に適切に置かれるようにして、１又は２以上のトランザクションが実行され、データベースにアクセスし得る。通常の集中的なトランザクション型データベースと同様に、１又は２以上のトランザクションが互いに衝突し、一部のトランザクションが成功裏に完了し、その他のトランザクションが失敗する結果を生じる可能性があり、その時点で、それらのトランザクションは、強制的にそれらのトランザクションの変更を元に戻され、再始動される。
【００７０】
２  デッドロック
トランザクションの間で生じる１つの潜在的な衝突が、デッドロックである。非常に広く言えば、デッドロックは、２又は３以上の同時に実行されるトランザクションがそれぞれ他のトランザクションが排他的にアクセスすることができるリソースを必要とし、完了する前にその他のトランザクションがリソースを解放するのを待たなければならない状況である。調べられず放置されると、２又は３以上の同時に実行されるトランザクションはそれらのトランザクションの必要とされるリソースにアクセスすることができないので、それらの２又は３以上の同時に実行されるトランザクションのいずれも完了しない。
【００７１】
図２を参照すると、デッドロックが発生する状況の従来の例が示される。例においては、２つのトランザクションＴ１及びＴ２が、トランザクションデータベースに記憶されたデータ要素ｘ及びｙに同時に働きかける。Ｔ１は、データ要素ｙの値を読み取り、データ要素ｘに値を書き込むための動作を含む。Ｔ２は、データ要素ｘの値を読み取り、データ要素ｙに値を書き込むための動作を含む。本明細書において使用されるとき、「ロック」は、特定のデータ要素に対するロックを獲得するエンティティ以外のいずれのエンティティによるその特定のデータ要素への同時アクセスも防止するための任意のメカニズムである。実施されている／防止されているアクセスの種類に応じた複数の種類のロックが、存在する可能性がある。例えば、「読み取りロック」は、いずれのその他のエンティティがデータ要素を読み取ることも防止するロックであり、「書き込みロック」は、いずれのその他のエンティティがデータ要素を書き込むことも防止するロックである。
【００７２】
第１の時間ステップ（１）において、Ｔ１が、データ要素ｙに対する読み取りロックＲＴ１１１３を取得するためのread_lock(y)コマンドを発する。第２の時間ステップ（２）において、Ｔ１が、ｙの値を読み取るためのread(y)コマンドを発する。第３の時間ステップ（３）において、Ｔ２が、データ要素ｘに対する読み取りロックＲＴ２１１５を取得するためのread_lock(x)コマンドを発する。第４の時間ステップ（４）において、Ｔ２が、ｘの値を読み取るためのread(x)コマンドを発する。
【００７３】
第５の時間ステップ（５）において、Ｔ１が、データ要素ｘに対する書き込みロックＷＴ１１１７を取得しようと試みるためのwrite_lock(x)コマンドを発する。しかし、Ｔ２が、データ要素ｘに対する読み取りロックを既に有しており、したがって、Ｔ１は、そのＴ１がそのＴ１の書き込みロックＷＴ１１１７を取得することが可能になる前に、Ｔ２がデータ要素ｘに対するそのＴ２の読み取りロックを解放し終わるまで待たなければならない。同様に、第６の時間ステップ（６）において、Ｔ２は、データ要素ｙに対する書き込みロックＷＴ２１１９を取得しようと試みるためのwrite_lock(y)コマンドを発する。しかし、Ｔ１が、データ要素ｙに対する読み取りロックを既に有しており、したがって、Ｔ２は、そのＴ２がそのＴ２の書き込みロックＷＴ２１１９を取得することが可能になる前に、Ｔ１がデータ要素ｙに対するそのＴ１の読み取りロックを解放し終わるまで待たなければならない。
【００７４】
この時点で、Ｔ１もＴ２もそのトランザクションを完了し終わるまでその読み取りロックを解放しないが、どちらかのトランザクションが先に進むためには、他方のトランザクションがその他方のトランザクションを解放しなければならないので、デッドロックが発生している。図２に示されるデッドロックなどのデッドロックが発生すると、先に進むための唯一の方法は、トランザクションのうちの一方をロールバックし、他方が完了することを可能にすることによってデッドロックを解くことである。
【００７５】
３  デッドロックの回避
上述のように、通常の集中的なトランザクション型データベースにおいては、上述のデッドロックなどのデッドロックの検出、防止、及び／又は回避のための方法がよく知られている。しかし、分散型データベースシステム１０２の複数の異なるノード１０８によって記憶されるデータにそれぞれが働きかける複数の同時に実行されるトランザクションの場合、デッドロックの起こる見込みがより高いので、分散型データベースにおいては、デッドロックを検出し、回避するための解決策を見つけることがますます難しくなる。いくつかの分散型データベースの動作は、特に耐障害アルゴリズムによって解決することが難しい分散型コンピューティングにおける問題に対応する。いくつかの種類の障害に関しては、分散型コンピューティングにおける一部の問題が、耐障害分散型アルゴリズムによって解決することが不可能であることが分かってさえいる。
【００７６】
図３を参照すると、一部の例において、分散型データベースシステム１０２は、たとえデッドロックがまだ実際に起こっていないとしても、トランザクションがデッドロックさせられるか又はデッドロックする可能性がある場合にトランザクションを元に戻す（又はロールバックする）「予防的デッドロック回避」アルゴリズム３１４を使用してデッドロックを回避する。さらに、アルゴリズム３１４は、下でより詳細に説明されるように、順序付け規則との合致を求める必要を、ロックが迅速に取得されない特定の状況のみに制限することによって、他の方法であれば、順序付けられたロック方式において強いられることになるであろうオーバーヘッドの一部を削減することができる。このようにして、分散型データベースにおける効率的なトランザクション型データ処理に依拠する物流又は産業プロセスは、デッドロックの回数の削減又はより速いトランザクション型データ処理の恩恵を直接受けることができる。
【００７７】
予防的デッドロック回避アルゴリズム３１４の前提条件は、分散型データベースに記憶されたデータアイテムが順序付け規則によって全順序的であることである。アイテムの「全順序」（又は「線形順序（linearly ordered）」）集合は、集合内のアイテムの対のあらゆるアイテムが、順序付け規則（「比較可能性（comparability）」又は「全順序律（totality）」とも呼ばれる）によって対の他方のアイテムに対して定義された順序を有する集合である。「半順序（partially ordered）」集合においては、対照的に、アイテムのあらゆる対が、互いに対して定義された順序を有するとは限らない。全順序集合は、半順序集合にも当てはまるその他の特性（例えば、反対称性（antisymmetry）及び推移性（transitivity））も有する。
【００７８】
全順序的であるそのような順序付け規則の１つの簡単な例は、データベース内の各データアイテムに一連の番号のうちの異なる番号を割り振ることである。例えば、データベース内の第１のデータ要素が、番号１を割り振られ、データベース内の第２のデータ要素が、番号２を割り振られ、以下同様である。もちろん、その他のより複雑な順序付け規則が、使用される可能性がある。例えば、ノード１０８の各々が、任意の所与のノードにおける番号がそれぞれのデータベースフラグメントの中で一意であるようにそのノード１０８のデータアイテムに番号を独立して割り振る可能性があり、そのときは、異なるノードの間の重複のチェックが、実施される。いずれかの重複が見つかった場合、ノードのすべてにわたって異なるデータアイテムに異なる番号（又は全順序的文字列）が割り振られることを保証するために、番号の一部又はすべてを変更するための同点決勝（tie breaker）規則が使用される。重複が見つかる場合に使用され得る同点決勝規則の例は、「ｉ」がデータアイテムに割り振られた元のローカルの番号であり、「ｊ」がノードの番号（１からＮまで）である場合にＮ個のノードの各々におけるすべての番号を再割り振りするための次の規則、すなわち、(i+j) mod Nである。
【００７９】
全順序的なデータアイテムを有するデータベースの１つの特性は、データアイテムに対するロックがデータアイテムの順序付け規則に合致する順序でしか獲得されない場合に、デッドロックが起こり得ないことである。つまり、トランザクションが番号１のデータアイテムに対するロックを獲得し、それから、番号２のデータアイテムに対するロックを獲得する場合、（すべてのその他のトランザクションが順序付け規則に合致する順序でロックを獲得していると仮定すれば）デッドロックは起こり得ない。しかし、トランザクションが番号２のデータアイテムに対するロックを獲得し、それから、データアイテム１に対するロックを獲得する場合、トランザクションの相対的なタイミングによっては、デッドロックが（必ずではないが）起こり得る。
【００８０】
非常に広く言えば、予防的デッドロック回避アルゴリズム３１４は、まず、トランザクションが任意の順序でデータアイテムに対するロックを取得しようと試みることを可能にし、トランザクションが順序付け規則に合致する順序でロックを取得しようと試みることを強制しない。トランザクションが取得しようと試みるロックのいずれかが予め定義された時間間隔又は時間遅延以内に取得されない場合、デッドロックが起こったか又は起こる可能性があるので、トランザクションがロールバックされる。一部の例において、時間間隔又は時間遅延は、順序付け規則に合致する順序でロックを獲得している任意の２つのトランザクションが時間間隔又は時間遅延以内にそれらのトランザクションのロックを取得する見込みが高くなる（例えば、見込みが５０％を超えているか、７５％を超えているか、又は９０％を超えている）ように十分に長い。
【００８１】
ロールバックされるいずれのトランザクションに関しても、トランザクションのロック動作は、順序付け規則に合致するように第２の順序でソートされる。それから、トランザクションが、再始動され（例えば、再び試みられるか又は再び処理され）、ロック動作が、ソートされた第２の順序で実施される。再始動されたトランザクションは、順序付け規則に合致する順序でそのトランザクションのロックを獲得し、初めて試みているトランザクションよりも高い優先度を有するので、少なくともロックを獲得することに関してはデッドロックなく進行する。つまり、下で説明される例示的なアルゴリズム３１４は、再始動されたトランザクションが初めて試みているトランザクションよりも高い優先度を有するので、初めて試みているすべてのトランザクションをロールバックする。結果として、再始動されたトランザクションは、以前ロールバックされロックの順序に合致する順序でそれらのトランザクションのロックの少なくとも一部を獲得しているトランザクションとだけ、ロックを求めて競合する。アルゴリズムのその他の例においては、時間間隔の後の順序決定が引き続き使用されるが、トランザクションの間の相対的な優先度は必ずしも使用されず、したがって、デッドロック(deadline)が引き続き阻止されるが、進行するための要件は必ずしも厳しくない。
【００８２】
より詳細には、アルゴリズム３１４の第１のステップ３１６において、ループがトランザクションＴによって実行されるロック動作のリストに沿って順番に進むときに、実施されるべき次のロック動作が存在するかどうかを知るためにループ条件が調べられ（つまり、リストによって示される順番で１度に１つのロック動作）、各ロック動作に関して、アルゴリズム３１４は、そのロック動作によって特定されたデータアイテムに対するロックＬを取得しようと試み始める。第２のステップ３１８において、ロック動作が、Ｌ．ｏｗｎｅｒ（つまり、もしあれば、どのトランザクションがロックＬを既に所有するかを表すロックＬのプロパティ）を調べて、その値がＮＵＬＬに等しいかどうかを決定する。ＮＵＬＬに等しい場合、どのトランザクションもロックＬを現在所有しておらず、アルゴリズムは第３のステップ３２０に進み、第３のステップ３２０において、トランザクションＴがロックＬを入手する。第３のステップ３２０においては、Ｌ．ｏｗｎｅｒがＴに設定され、ループがステップ３１６に戻る。
【００８３】
Ｌ．ｏｗｎｅｒがＮＵＬＬに等しくない場合、別のトランザクションがロックＬを既に所有しており、アルゴリズムは第４のステップ３２２に進み、第４のステップ３２２において、Ｔ．ｐｒｉｏｒｉｔｙ（つまり、トランザクションＴの処理の優先度を表すプロパティ）がＬ．ｏｗｎｅｒの優先度（つまり、ロックＬを現在所有しているトランザクションの処理の優先度を表すプロパティ）と比較される。Ｔ．ｐｒｉｏｒｉｔｙがＬ．ｏｗｎｅｒ．ｐｒｉｏｒｉｔｙよりも高い場合、アルゴリズム３１４は、第５のステップ３２４に進み、第５のステップ３２４において、ロックＬを現在所有しているトランザクション（つまり、Ｌ．ｏｗｎｅｒ）が、ロールバックされる。そして、トランザクションＴがロックＬを入手し、そのとき、Ｌ．ｏｗｎｅｒがＴに設定され、ループがステップ３１６に戻る。Ｔ．ｐｒｉｏｒｉｔｙがＬ．ｏｗｎｅｒ．ｐｒｉｏｒｉｔｙ以下である場合、アルゴリズム３１４は、第６のステップ３２６に進み、第６のステップ３２６において、トランザクションがロックＬを取得しようと試みるための時間の間隔（又は「時間間隔」若しくは「時間遅延」）ｔｗを与えられる。
【００８４】
ロックＬが時間の間隔ｔｗ以内に解放され、Ｌ．ｏｗｎｅｒをＮＵＬＬに等しくする場合、アルゴリズム３１４は第７のステップ３３０に進み、第７のステップ３３０において、トランザクションＴがロックＬを入手し、ループがステップ３１６に戻る。第７のステップ３３０において、Ｌ．ｏｗｎｅｒがＴに設定される。代替的に、時間間隔又は時間遅延ｔｗの間に別のトランザクションがロックＬを解放しない場合、アルゴリズムは、第８のステップ３３２に進む。第８のステップ３３２において、アルゴリズム３１４が、トランザクションＴによって発せられたすべての動作をロールバックする。第８のステップ３３２は、Ｔによって実行されるロック動作のリストをデータアイテムの順序付け規則に合致するように第２の順序でソートし、Ｔ．ｐｒｉｏｒｉｔｙをインクリメントする(increment)。そして、アルゴリズム３１４は、ループ条件がソートされたロック動作のリストの初めに再び初期化されるようにしてステップ３１６に戻ることによってトランザクションＴを再始動し、したがって、ロック動作のロックは、今やソートされた（第２の）順序で順番に取得される。
【００８５】
例示的なアルゴリズム３１４とは異なる解決策を適用するが、アルゴリズム３１４と同様にオーバーヘッドを減らすようにしてやはりデッドロックを回避する予防的デッドロック回避アルゴリズムのさまざまなその他の例が、代替的に使用され得る。例えば、特定の時間間隔又は時間遅延の後にあらゆるトランザクションに関して（ステップ３３２において）ロック動作をロールバックし、第２の順序でソートする代わりに、アルゴリズムは、すべての最初のロックが取得された順序が順序付け規則に合致しているか否かをまず決定する可能性がある。最初のロックが順序付け規則に合致する順序で取得された場合、遅延は、デッドロックが原因ではなく、トランザクションは、トランザクションをロールバックする前により長い時間間隔又は時間遅延の間、ロックを待ち続ける可能性がある。しかし、最初のロックが順序付け規則に合致する順序で取得されなかった場合、トランザクションは、デッドロックが発生した可能性があるのでロールバックされ、例えば、ソートされたリストを用いて再始動される（例えば、再び試みられるか又は再び処理される）。したがって、一部のアルゴリズムは、第１の順序が順序付け規則に合致するか否かを決定するためのステップを含み、（アルゴリズム３１４などの）その他のアルゴリズムは、そのようなステップを含まない。
【００８６】
３．１  例
図４を参照すると、予防的デッドロック回避アルゴリズム３１４の例示的な応用において、２つのトランザクションＴ１及びＴ２は、分散型データベースの（データアイテムｘ及びｙを含む）データアイテムに同時に働きかけている。データアイテムは、順序付け規則に従った順序で番号を振られ、ｘが、番号１を割り振られ、ｙが、番号２を割り振られる。以下の検討を簡潔にするために、データアイテムは、ｘ１及びｙ２と呼ばれる。
【００８７】
最初の時間ステップ（０）においては、いかなるトランザクションもｘ１又はｙ２に対するロックを所有しない。第１の時間ステップ（１）において、Ｔ１が、read_lock(y2)コマンドを発することによってｙ２に対するロックを取得しようと試みる。そのようにするために、Ｔ１は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｙ２に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第１の時間ステップ（１）においてｙ２に対する書き込みロックを所有しないので、Ｔ１は、アルゴリズム３１４の第３のステップ３２０に進み、ｙ２に対する読み取りロック
【００８８】
【数１】
0006724039.tif 000002
【００８９】
４３４を成功裏に取得する。ｙ２に対する読み取りロック
【００９０】
【数２】
0006724039.tif 000003
【００９１】
４３４を取得すると、ｙ２に関するＬ．ｏｗｎｅｒがＴ１に設定される。
【００９２】
第２の時間ステップ（２）において、Ｔ１は、read(y2)コマンドを発することによってｙ２の値を読み取ろうと試みる。Ｔ１は、ｙ２に対する読み取りロックを所有するので、ｙ２の値を成功裏に読み取る。
【００９３】
第３の時間ステップ（３）において、Ｔ２が、read_lock(x1)コマンドを発することによってｘ１に対するロックを取得しようと試みる。そのようにするために、Ｔ２は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｘ１に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第３の時間ステップ（３）においてｘ１に対する書き込みロックを所有しないので、Ｔ２は、アルゴリズム３１４の第３のステップ３２０に進み、ｘ１に対する読み取りロック
【００９４】
【数３】
0006724039.tif 000004
【００９５】
４３６を成功裏に取得する。ｘ１に対する読み取りロック
【００９６】
【数４】
0006724039.tif 000005
【００９７】
４３６を取得すると、ｘ１に関するＬ．ｏｗｎｅｒがＴ２に設定される。
【００９８】
第４の時間ステップ（４）において、Ｔ２は、read(x1)コマンドを発することによってｘ１の値を読み取ろうと試みる。Ｔ２は、ｘ１に対する読み取りロックを所有するので、ｘ１の値を成功裏に読み取る。
【００９９】
第５の時間ステップ（５）において、Ｔ１が、write_lock(x1)コマンドを発することによってｘ１に対する書き込みロックを取得しようと試みる。そのようにするために、Ｔ１は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｘ１に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。Ｔ２がｘ１に対する読み取りロックをまだ所有する（つまり、ｘ１に関するＬ．ｏｗｎｅｒがＴ２に等しい）ので、Ｔ１は、アルゴリズム３１４の第４のステップ３２２に進み、Ｔ１がＴ２よりも高い優先度を有するかどうかを決定する。第５の時間ステップ（５）において、Ｔ１．ｐｒｉｏｒｉｔｙとＴ２．ｐｒｉｏｒｉｔｙとの両方はゼロに等しく、したがって、Ｔ１は、アルゴリズム３１４の第６のステップ３２６に進み、時間間隔又は時間遅延ｔｗの間、ｘ１に対する書き込みロックを取得しようと試みる。
【０１００】
第６の時間ステップ（６）において、Ｔ１がｘ１に対する書き込みロックを取得するのをまだ待っている間に、Ｔ２はwrite_lock(y2)コマンドを発することによってｙ２に対する書き込みロックを取得しようと試みる。そのようにするために、トランザクションＴ２は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｙ２に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。Ｔ１がｙ２に対する読み取りロックをまだ所有する（つまり、ｙ２に関するＬ．ｏｗｎｅｒがＴ１に等しい）ので、Ｔ２は、アルゴリズム３１４の第４のステップ３２２に進み、Ｔ２がＴ１よりも高い優先度を有するかどうかを決定する。第５の時間ステップ（５）において、Ｔ１．ｐｒｉｏｒｉｔｙとＴ２．ｐｒｉｏｒｉｔｙとの両方はゼロに等しく、したがって、Ｔ２は、アルゴリズム３１４の第６のステップ３２６に進み、時間間隔又は時間遅延ｔｗの間、ｙ２に対する書き込みロックを取得しようと試みる。
【０１０１】
第７の時間ステップ（７）において、トランザクションＴ１がｘ１に対する書き込みロックを取得しようと試みるための時間間隔ｔｗが、（読み取りロック
【０１０２】
【数５】
0006724039.tif 000006
【０１０３】
４３６が時間間隔ｔｗの間に解放されなかったので）Ｔ１がｘ１に対する書き込みロックを未だ取得することなく経過する。アルゴリズム３１４は、第８のステップ３３２に進み、第７の時間ステップ（７）においてｘ１に対する書き込みロックを取得しようとするトランザクションの試みを中止することと、第８の時間ステップ（８）においてｙ２に対するトランザクションの読み取りロックを解放することとを含め、トランザクションＴ１をロールバックする。Ｔ１をロールバックすることによって、Ｔ１とＴ２との間のデッドロックが回避される。Ｔ１がロールバックされたので、Ｔ１．ｐｒｉｏｒｉｔｙは、アルゴリズム３１４の第８のステップ３３２によってゼロから１にインクリメントされる（図５参照）。Ｔ１の優先度を上げることによって、アルゴリズム３１４は、繰り返しロールバックされることによってＴ１が欠乏に苦しむことがないことを保証する。最後に、アルゴリズム３１４の第８のステップ３３２は、Ｔ１がロールバックされる前に発したロック動作を調べ、データアイテムの順序付け規則に合致するようにそれらのロック動作をソートする。Ｔ１に関して、ロック動作は、以下のようにソートされる。
（１）write_lock(x1)
（２）read_lock(y2)
【０１０４】
ｙ２に対するＴ１の読み取りロックが解放されると、トランザクションＴ２は、ｙ２に対する書き込みロック
【０１０５】
【数６】
0006724039.tif 000007
【０１０６】
４４０を成功裏に取得することができる。第９の時間ステップ（９）において、トランザクションＴ２が、write(y2)コマンドを発し、ｙ２を新しい値ｙ２’によって上書きする。第１０の時間ステップ（１０）において、トランザクションＴ２は、commit(T2)コマンドを発して、そのトランザクションの変更をデータベースにコミットする。Ｔ２の変更がコミットされた後、ｘ１に対する読み取りロック
【０１０７】
【数７】
0006724039.tif 000008
【０１０８】
４３６及びｙ２’に対する書き込みロック
【０１０９】
【数８】
0006724039.tif 000009
【０１１０】
４４０が解放され、トランザクションＴ２が完了する。
【０１１１】
第１１の時間ステップ（１１）において、Ｔ１が、第２の試みを始める。第２の試みにおいて、Ｔ１は、Ｔ１の第１の試みにおいてＴ１が発したロック動作を、トランザクションの冒頭に、ソートされた順序で（つまり、データアイテムの順序付け規則に合致する順序で）再び発する。つまり、第１１の時間ステップ（１１）において、Ｔ１が、write_lock(x1)コマンドを発することによってｘ１に対する書き込みロックを取得しようと試みる。そのようにするために、Ｔ１は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｘ１に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第１１の時間ステップ（１１）においてｘ１に対する書き込みロックを所有しないので、Ｔ１は、アルゴリズム３１４の第３のステップ３２０に進み、ｘ１に対する書き込みロック
【０１１２】
【数９】
0006724039.tif 000010
【０１１３】
４４２を成功裏に取得する。ｘ１に対する書き込みロック
【０１１４】
【数１０】
0006724039.tif 000011
【０１１５】
４４２を取得すると、ｘ１に関するＬ．ｏｗｎｅｒがＴ１に設定される。
【０１１６】
第１２の時間ステップ（１２）において、Ｔ１が、read_lock(y2')コマンドを発することによってｙ２’に対する読み取りロックを取得しようと試みる。そのようにするために、第１のトランザクションＴ１は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｙ２’に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第１２の時間ステップ（１２）においてｙ２’に対する書き込みロックを所有しないので、Ｔ１は、アルゴリズム３１４の第３のステップ３２０に進み、ｙ２’に対する読み取りロック
【０１１７】
【数１１】
0006724039.tif 000012
【０１１８】
４４４を成功裏に取得する。ｙ２’に対する読み取りロック
【０１１９】
【数１２】
0006724039.tif 000013
【０１２０】
４４４を取得すると、ｙ２’に関するＬ．ｏｗｎｅｒがＴ１に設定される。
【０１２１】
第１３の時間ステップ（１３）において、トランザクションＴ１が、write(x1)コマンドを発し、ｘ１を新しい値ｘ１’によって上書きする。第１４の時間ステップ（１４）において、トランザクションＴ１は、commit(T1)コマンドを発して、そのトランザクションの変更をデータベースにコミットする。Ｔ１の変更がコミットされた後、ｙ２に対する読み取りロック
【０１２２】
【数１３】
0006724039.tif 000014
【０１２３】
４４４、及び書き込みロック
【０１２４】
【数１４】
0006724039.tif 000015
【０１２５】
４４２が解放され、トランザクションＴ１が完了する。
【０１２６】
図５を参照すると、予防的デッドロック回避アルゴリズム３１４の別の例示的な応用において、２つのトランザクションＴ１及びＴ２は、分散型データベースの（データアイテムｘ１及びｙ２を含む）データアイテムに同時に働きかけている。この例において、第１のトランザクションＴ１は、以前ロールバックされたことがあり、Ｔ１．ｐｒｉｏｒｉｔｙは１に等しい。
【０１２７】
最初の時間ステップ（０）においては、いかなるトランザクションもｘ１又はｙ２に対するロックを所有しない。第１の時間ステップ（１）において、Ｔ１が、read_lock(y2)コマンドを発することによってｙ２に対するロックを取得しようと試みる。そのようにするために、Ｔ１は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｙ２に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第１の時間ステップ（１）においてｙ２に対する書き込みロックを所有しないので、Ｔ１は、アルゴリズム３１４の第３のステップ３２０に進み、ｙ２に対する読み取りロック
【０１２８】
【数１５】
0006724039.tif 000016
【０１２９】
６４６を成功裏に取得する。ｙ２に対する読み取りロック
【０１３０】
【数１６】
0006724039.tif 000017
【０１３１】
６４６を取得すると、ｙ２に関するＬ．ｏｗｎｅｒがＴ１に設定される。
【０１３２】
第２の時間ステップ（２）において、Ｔ１は、read(y2)コマンドを発することによってｙ２の値を読み取ろうと試みる。Ｔ１は、ｙ２に対する読み取りロックを所有するので、ｙ２の値を成功裏に読み取る。
【０１３３】
第３の時間ステップ（３）において、Ｔ２が、read_lock(x1)コマンドを発することによってｘ１に対するロックを取得しようと試みる。そのようにするために、Ｔ２は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｘ１に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第３の時間ステップ（３）においてｘ１に対する書き込みロックを所有しないので、Ｔ２は、アルゴリズム３１４の第３のステップ３２０に進み、ｘ１に対する読み取りロック
【０１３４】
【数１７】
0006724039.tif 000018
【０１３５】
６４８を成功裏に取得する。ｘ１に対する読み取りロック
【０１３６】
【数１８】
0006724039.tif 000019
【０１３７】
６４８を取得すると、ｘ１に関するＬ．ｏｗｎｅｒがＴ２に設定される。
【０１３８】
第４の時間ステップ（４）において、Ｔ２は、read(x1)コマンドを発することによってｘ１の値を読み取ろうと試みる。Ｔ２は、ｘ１に対する読み取りロックを所有するので、ｘ１の値を成功裏に読み取る。
【０１３９】
第５の時間ステップ（５）において、Ｔ１が、write_lock(x1)コマンドを発することによってｘ１に対する書き込みロックを取得しようと試みる。そのようにするために、Ｔ１は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｘ１に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。Ｔ２がｘ１に対する読み取りロックをまだ所有する（つまり、ｘ１に関するＬ．ｏｗｎｅｒがＴ２に等しい）ので、Ｔ１は、アルゴリズム３１４の第４のステップ３２２に進み、Ｔ１がＴ２よりも高い優先度を有するかどうかを決定する。第５の時間ステップ（５）において、Ｔ１．ｐｒｉｏｒｉｔｙは１に等しく、Ｔ２．ｐｒｉｏｒｉｔｙは０に等しい。したがって、Ｔ１は、アルゴリズム３１４の第５のステップ３２４に進み、第６の時間ステップ（６）においてｘ１に対するＴ２の読み取りロック
【０１４０】
【数１９】
0006724039.tif 000020
【０１４１】
６４６を解放するためのunlock(x1)コマンドを発することを含め、Ｔ２をロールバックする。Ｔ２がロールバックされたので、Ｔ２．ｐｒｉｏｒｉｔｙは、アルゴリズム３１４の第５のステップ３２４によってゼロから１にインクリメントされる。
【０１４２】
ｘ１に対するＴ２の読み取りロック
【０１４３】
【数２０】
0006724039.tif 000021
【０１４４】
６４８が解放されると、Ｔ１は、ｘ１に対する書き込みロック
【０１４５】
【数２１】
0006724039.tif 000022
【０１４６】
６５０を成功裏に取得することができる。第７の時間ステップ（７）において、Ｔ１が、write(x1)コマンドを発し、ｘ１を新しい値ｘ１’によって上書きする。第８の時間ステップ（８）において、Ｔ１は、commit(T1)コマンドを発して、そのトランザクションの変更をデータベースにコミットする。Ｔ１の変更がコミットされた後、ｙ２に対する読み取りロック
【０１４７】
【数２２】
0006724039.tif 000023
【０１４８】
６４６及びｘ１’に対する書き込みロック
【０１４９】
【数２３】
0006724039.tif 000024
【０１５０】
６５０が解放され、トランザクションＴ１が完了する。
【０１５１】
第９の時間ステップ（９）において、Ｔ２が、第２の試みを始める。第２の試みにおいて、Ｔ２が、read_lock(x1)コマンドを発することによってｘ１’に対する読み取りロックを取得しようと試みる。そのようにするために、Ｔ２は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｘ１に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第９の時間ステップ（９）においてｘ１’に対する書き込みロックを所有しないので、Ｔ２は、アルゴリズム３１４の第３のステップ３２０に進み、ｘ１’に対する読み取りロック
【０１５２】
【数２４】
0006724039.tif 000025
【０１５３】
６５２を成功裏に取得する。ｘ１’に対する読み取りロック
【０１５４】
【数２５】
0006724039.tif 000026
【０１５５】
６５２を取得すると、ｘ１’に関するＬ．ｏｗｎｅｒがＴ２に設定される。
【０１５６】
第１０の時間ステップ（１０）において、Ｔ２が、write_lock(y2)コマンドを発することによってｙ２に対する書き込みロックを取得しようと試みる。そのようにするために、第２のトランザクションＴ２は、予防的デッドロック回避アルゴリズム３１４の第２のステップ３１８を適用し、ｙ２に関するＬ．ｏｗｎｅｒがＮＵＬＬに等しいかどうかを決定する。その他のトランザクションが第１０の時間ステップ（１０）においてｙ２に対する書き込みロックを所有しないので、Ｔ２は、アルゴリズム３１４の第３のステップ３２０に進み、ｙ２に対する書き込みロック
【０１５７】
【数２６】
0006724039.tif 000027
【０１５８】
６５４を成功裏に取得する。ｙ２に対する書き込みロック
【０１５９】
【数２７】
0006724039.tif 000028
【０１６０】
６５４を取得すると、ｙ２に関するＬ．ｏｗｎｅｒがＴ２に設定される。
【０１６１】
第１１の時間ステップ（１１）において、Ｔ２が、ｘ１’の値を読み取るためのread(x1')コマンドを発する。第１２の時間ステップ（１２）において、Ｔ２が、write(y2)コマンドを発し、ｙ２を新しい値ｙ２’によって上書きする。第１３の時間ステップ（１３）において、Ｔ２は、commit(T2)コマンドを発して、そのトランザクションの変更をデータベースにコミットする。Ｔ２の変更がコミットされた後、ｘ１に対する読み取りロック
【０１６２】
【数２８】
0006724039.tif 000029
【０１６３】
６５２及びｘ１’に対する書き込みロック
【０１６４】
【数２９】
0006724039.tif 000030
【０１６５】
６５４が解放され、トランザクションＴ２が完了する。
【０１６６】
４  代替形態
一部の例においては、ロック動作がトランザクションの第１の試みにおいてデータアイテムに対して実施されるときに、順序付け規則に基づくデータアイテムの位置が、ロック動作をソートする際に後で使用するために記憶される。例えば、第１の時間遅延以内にロックが取得されたデータアイテムの位置が、記憶される可能性がある。トランザクション内のすべてのロックがソートされることを必要とする代わりに、第１の時間遅延以内に最初に取得されたロックのみを単純にソートすれば、進展を保証するのに十分である可能性があり、そのようなソートは、多数のロック動作を伴うトランザクションのためにそれほど多くの作業を必要としない可能性がある。
【０１６７】
一部の例において、ロック動作が完了するのを待つための時間間隔又は時間遅延は、ロック動作が順序付け規則に合致する場合より長い。
【０１６８】
一部の例において、トランザクションは、第２の時間間隔又は第２の時間遅延の後にのみ再始動される。一部の例において、第２の時間間隔又は時間遅延は、ロック動作がロックを取得しようと試みることを可能にされる時間間隔又は時間遅延よりも長い。
【０１６９】
一部の例において、ロック動作がロックを取得しようと試みることを可能にされる時間間隔又は時間遅延は、１秒未満（例えば、１００ｍｓ、１ｍｓ、１００マイクロ秒、１マイクロ秒、又は０．１マイクロ秒）である。一部の例において、ロック動作がロックを取得しようと試みることを可能にされる時間間隔は、約ゼロ秒である。
【０１７０】
一部の例において、所与のデータアイテムに関するロックは、単一のロック解除状態及び１又は２以上のロック状態を含む複数の状態を有する可能性がある。一部の例において、１又は２以上のロック状態は、排他的書き込みロック状態及び非排他的複数読み取りロック状態を含む。
【０１７１】
一部の例において、分散型データベースシステム上で実行されているトランザクションは、非同期に実行されるトランザクションである。一部の例において、データベースは、インメモリデータベースである。
【０１７２】
上の発明の概要の節において説明された特徴を含む本明細書において説明されたさまざまな特徴を含むさまざまなその他の代替的な技術が、使用され得る。
【０１７３】
５  実施形態
上述のデッドロック回避手法は、例えば、好適なソフトウェア命令を実行するプログラミング可能なコンピューティングシステムを用いて実装される(implemented)可能性があり、又はフィールドプログラマブルゲートアレイ（ＦＰＧＡ，field-programmable gate array）などの好適なハードウェアで、若しくは何らかの混成の形態で実装される可能性がある。例えば、プログラミングされる手法において、ソフトウェアは、それぞれが少なくとも１つのプロセッサ、（揮発性及び／又は不揮発性メモリ及び／又はストレージ要素を含む）少なくとも１つのデータストレージシステム、（少なくとも１つの入力デバイス又はポートを用いて入力を受け取るため、及び少なくとも１つの出力デバイス又はポートを用いて出力を与えるための）少なくとも１つのユーザインターフェースを含む（分散、クライアント／サーバ、又はグリッドなどのさまざまなアーキテクチャである可能性がある）１又は２以上のプログラミングされた又はプログラミング可能なコンピューティングシステム上で実行される１又は２以上のコンピュータプログラムのプロシージャを含み得る。ソフトウェアは、例えば、データフローグラフの設計、構成、及び実行に関連するサービスを提供するより大きなプログラムの１又は２以上のモジュールを含む可能性がある。プログラムのモジュール（例えば、データフローグラフの要素）は、データリポジトリに記憶されたデータモデルに準拠するデータ構造又はその他の編成されたデータとして実装され得る。
【０１７４】
ソフトウェアは、ある期間（例えば、ダイナミックＲＡＭなどのダイナミックメモリデバイスのリフレッシュ周期の間の時間）媒体の物理特性（例えば、表面ピット及びランド、磁区、又は電荷）を使用して、揮発性若しくは不揮発性ストレージ媒体又は任意のその他の非一時的媒体に具現化されるなど、非一時的形態で記憶され得る。命令をロードするのに備えて、ソフトウェアは、ＣＤ−ＲＯＭ又は（例えば、多目的若しくは専用のコンピューティングシステム若しくはデバイスによって読み取り可能な）その他のコンピュータ可読媒体などの有形の非一時的媒体上に提供される可能性があり、或いはそのソフトウェアが実行されるコンピューティングシステムの有形の非一時的媒体にネットワークの通信媒体を介して配信される（例えば、伝搬信号に符号化される）可能性がある。処理の一部又はすべては、専用のコンピュータ上で、又はコプロセッサ若しくはフィールドプログラマブルゲートアレイ（ＦＰＧＡ，field-programmable gate array）若しくは専用の特定用途向け集積回路（ＡＳＩＣ，application-specific integrated circuit）などの専用のハードウェアを使用して実施される可能性がある。処理は、ソフトウェアによって規定された計算の異なる部分が異なるコンピューティング要素によって実施される分散された方法で履行される(implemented)可能性がある。それぞれのそのようなコンピュータプログラムは、本明細書において説明された処理を実施するためにストレージデバイスの媒体がコンピュータによって読み取られるときにコンピュータを構成し、動作させるために、多目的又は専用のプログラミング可能なコンピュータによってアクセスされ得るストレージデバイスのコンピュータ可読ストレージ媒体（例えば、ソリッドステートメモリ若しくは媒体、又は磁気式若しくは光学式媒体）に記憶されるか又はダウンロードされることが好ましい。本発明のシステムは、コンピュータプログラムで構成された有形の非一時的媒体として実装されると考えられる可能性もあり、そのように構成された媒体は、本明細書において説明された処理ステップのうちの１又は２以上を実施するために特定の予め定義された方法でコンピュータを動作させる。
【０１７５】
本発明のいくつかの実施形態が、説明された。しかしながら、上述の説明は、添付の請求項の範囲によって画定される本発明の範囲を例示するように意図されており、限定するように意図されていないことを理解されたい。したがって、その他の実施形態も、添付の請求項の範囲内にある。例えば、本発明の範囲を逸脱することなくさまざまな修正がなされ得る。さらに、上述のステップの一部は、順序に依存しない可能性があり、したがって、説明された順序とは異なる順序で実施される可能性がある。
【図１】
0006724039.tif 000031
【図２】
0006724039.tif 000032
【図３】
0006724039.tif 000033
【図４】
0006724039.tif 000034
【図５】
0006724039.tif 000035