(57)【要約】  非共有データベースシステムの性能を改善するためのさまざまな技術を記載する。非共有データベースシステムにおいて、この非共有データベースシステムを稼動する少なくとも２つのノードは、ディスクへの共有アクセスを有する。具体的には、永続的な記憶上のデータの位置を変えることなく、非共有データベース内のデータの所有権を変更するための技術を提供する。データの所有権を転送する間に、そのデータに対する永続的な記憶の位置が変更されないため、データを物理的に再配置することによって生じる場合に比べ、より自由に、かつ、性能の不利益がより少ない状態で、所有権が転送され得る。高速かつ実行時における所有権の再割当を行なうためのさまざまな技術も記載する。実行時に再割当てが実行され得るため、非共有システムは、再割当を実行するためにオフラインにされる必要がない。さらに、これらの技術は、ノードのうちの１つのノード上のいくつかのデータ項目の所有権を単に再割当するためだけに全ノードにわたって大量のデータを大容量で再割当する必要性をなくしつつ、相対的により細かい粒度で再割当がどのように行なわれ得るかを示す。
2007501457.tif 000002
【特許請求の範囲】
【請求項１】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが、前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、特定のノードが前記特定のデータ項目についての演算を実行するように、特定のノードに演算を転送し、前記方法はさらに、
第１のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から特定のデータ項目を移動することなく特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、
前記再割当の後に、いずれかのノードが、前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが特定のデータ項目についての演算を実行するように、前記他のノードに演算を転送する、方法。
【請求項２】
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、前記複数のノード間で共有される所有権のマップを更新するステップを含む、請求項１に記載の方法。
【請求項３】
前記複数のノードは、マルチノードデータベースシステムのノードである、請求項１に記載の方法。
【請求項４】
前記マルチノードデータベースシステムは、前記永続的な記憶へのアクセスを有さないノードを含む、請求項３に記載の方法。
【請求項５】
前記永続的な記憶は、前記マルチノードデータベースシステムにより使用される複数の永続的な記憶の第１の永続的な記憶であり、
前記方法はさらに、前記第１の永続的な記憶へのアクセスを有する第１のノードから、第２の永続的な記憶へのアクセスを有するものの前記第１の永続的な記憶へのアクセスを有さない第２のノードに第２のデータ項目の所有権を再割当するステップを含み、
前記第２のデータ項目の所有権を再割当する前記ステップは、前記第１の永続的な記憶から前記第２の永続的な記憶に前記第２のデータ項目を移動するステップを含む、請求項３に記載の方法。
【請求項６】
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、前記他のノードを前記マルチノードデータベースシステムに追加することに応じて実行される、請求項３に記載の方法。
【請求項７】
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、前記特定のノードが前記マルチノードデータベースシステムから除去されることを見越して実行され、
前記方法はさらに、前記特定のノードが前記マルチノードデータベースシステムから除去されることを見越して、前記永続的な記憶から別の永続的な記憶に、前記特定のノードから前記永続的な記憶へのアクセスを有さない前記マルチノードデータベースシステムの
ノードに再割当された第２のデータ項目を物理的に移動するステップを含む、請求項３に記載の方法。
【請求項８】
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、前記特定のノードから１つ以上の他のノードへの所有権の段階的な転送の一部として実行される、請求項３に記載の方法。
【請求項９】
前記段階的な転送は、前記特定のノードが前記マルチノードデータベースシステム内の１つ以上の他のノードに比べて酷使されていると検出されることに応じて開始される、請求項８に記載の方法。
【請求項１０】
前記段階的な転送は、前記特定のノードが、前記マルチノードデータベースシステムの１つ以上の他のノードに比べてもはや酷使されていないと検出されることに応じて終了される、請求項９に記載の方法。
【請求項１１】
前記特定のノードから別のノードに特定のデータ項目の所有権を再割当する前記ステップは、１つ以上の他のノードによる、前記他のノードへの所有権の段階的な転送の一部として実行され、前記段階的な転送は、前記他のノードが前記マルチノードデータベースシステム内の１つ以上の他のノードに比べて十分に使用されていないと検出されることに応じて開始される、請求項３に記載の方法。
【請求項１２】
前記マルチノードシステムから第１のノードが除去された後に、一組のデータ項目が前記第１のノードによって継続して所有されるようにするステップと、
前記データ項目を必要とする演算の要求が検出されることに応じて、前記第１のノードから１つ以上の他のノードにデータ項目の所有権を再割当するステップとをさらに含む、請求項３に記載の方法。
【請求項１３】
前記マルチノードシステムから第１のノードが除去された後に、一組のデータ項目が前記第１のノードにより継続して所有されるようにするステップと、
第２のノードの作業負荷が予め定められたしきい値よりも下がったことが検出されたことに応じて、前記第１のノードから前記第２のノードにデータ項目の所有権を再割当するステップとをさらに含む、請求項３に記載の方法。
【請求項１４】
前記特定のデータ項目が前記他のノードに再割当されるべき時に、前記特定のノードは、揮発性メモリに前記特定のデータ項目のダーティなバージョンを記憶し、
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、前記特定のデータ項目の前記ダーティなバージョンを前記永続的な記憶に書込むステップを含む、請求項１に記載の方法。
【請求項１５】
前記特定のデータ項目が前記他のノードに再割当されるべき時に、前記特定のノードは、揮発性メモリに前記特定のデータ項目のダーティなバージョンを記憶し、
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、永続的な記憶に対し、前記ダーティなバージョンに関連する１つ以上の再実行記録を強制するステップと、前記特定のデータ項目の前記ダーティなバージョンを前記永続的な記憶に書込むことなく前記揮発性メモリから前記ダーティなバージョンを一掃するステップとを含み、
前記他のノードは、前記永続的な記憶に存在する特定のデータ項目のバージョンに前記１つ以上の再実行記録を適用することにより、前記ダーティなバージョンを再構築する、請求項１に記載の方法。
【請求項１６】
前記特定のデータ項目が前記他のノードに再割当されるべき時に、前記特定のノードは、揮発性メモリに前記特定のデータ項目のダーティなバージョンを記憶し、
前記方法はさらに、前記特定のノードに関連する揮発性メモリから、前記他のノードに関連する揮発性メモリに、前記特定のデータ項目のダーティなバージョンを転送するステップを含む、請求項１に記載の方法。
【請求項１７】
前記ダーティなバージョンを転送する前記ステップは、他のノードが前記ダーティなバージョンを要求することなく、前記特定のノードにより事前対応の態様で実行される、請求項１６に記載の方法。
【請求項１８】
前記ダーティなバージョンを転送する前記ステップは、前記他のノードからの前記ダーティなバージョンの要求に応じて前記特定のノードにより実行される、請求項１６に記載の方法。
【請求項１９】
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、前記データ項目を変更するトランザクションがコミットするのを待たずに実行され、
前記特定のデータ項目が前記特定のノードにより所有されている間に、トランザクションは第１の組の変更を行ない、
前記特定のデータ項目が前記他のノードにより所有されている間に、トランザクションは第２の組の変更を行なう、請求項１に記載の方法。
【請求項２０】
前記他のノードに関連する取消しログ内の取消し記録に基づいて前記第２の組の変更をロールバックすること、および、前記特定のノードに関連する取消しログ内の取消し記録に基づいて前記第１の組の変更をロールバックすることにより、前記トランザクションによって行なわれた変更をロールバックするステップをさらに含む、請求項１９に記載の方法。
【請求項２１】
前記方法は、
他のノードが前記データ項目を更新する要求を受信するステップと、
前記特定のノードが前記データ項目への専有モードのアクセスまたは共有モードのアクセスのいずれを保持していたかを判断するステップと、
前記特定のノードが前記データ項目への専有モードのアクセスまたは共有モードのアクセスを保持していなかった場合に、前記特定のノードが、データ項目のいずれかのダーティなバージョンの消去またはダーティなバージョンに対する再実行を待たずに、前記他のノードが前記特定のデータ項目を更新するステップとを含む、請求項１に記載の方法。
【請求項２２】
前記他のノードに前記特定のデータ項目の所有権を転送することに応じて、前記特定のデータ項目を必要とする進行中の演算を中止するステップと、
前記特定のデータ項目の所有権が前記特定のノードに転送された後に、前記進行中の演算を再実行するステップとをさらに含む、請求項１に記載の方法。
【請求項２３】
前記特定のデータ項目を必要とする演算は、前記特定のデータ項目の所有権の転送が実行されるべき時に進行中であり、
前記方法はさらに、一組の１つ以上の因子に基づき、前記進行中の演算が完了するのを待つべきかどうかを判断するステップと、
前記進行中の演算が完了するのを待たないと判断された場合に、前記進行中の演算を中止するステップとを含む、請求項１に記載の方法。
【請求項２４】
前記組の１つ以上の因子は、前記進行中の演算によってどれだけの仕事が既に実行され
たかを含む、請求項２３に記載の方法。
【請求項２５】
データを管理する方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップと、
複数のバケットの１つに各データ項目を割当てることにより、前記ノードの１つに、永続的なデータ項目の各々の所有権を割当てるステップと、
前記複数のノードの１つに各バケットを割当てるステップとを含み、
バケットが割当てられた前記ノードは、前記バケットに割当てられたすべてのデータ項目の所有者であるものと確認され、前記方法はさらに、
第１のノードが、第２のノードにより所有されるデータ項目を必要とする演算が実行されることを望むと、前記第１のノードは、前記第２のノードが演算を実行するように前記第２のノードに演算を転送する、方法。
【請求項２６】
複数のバケットの１つに各データ項目を割当てる前記ステップは、各データ項目に関連する名前にハッシュ関数を適用することによって実行される、請求項２５に記載の方法。
【請求項２７】
前記複数のノードの１つに各バケットを割当てる前記ステップは、各バケットに関連する識別子にハッシュ関数を適用することによって実行される、請求項２５に記載の方法。
【請求項２８】
複数のバケットの１つに各データ項目を割当てる前記ステップは、範囲ベースのセグメント化を用いて実行される、請求項２５に記載の方法。
【請求項２９】
前記複数のノードの１つに各バケットを割当てる前記ステップは、範囲ベースのセグメント化を用いて実行される、請求項２５に記載の方法。
【請求項３０】
複数のバケットの１つに各データ項目を割当てる前記ステップは、データ項目−バケット間の個々の関係を列挙することによって実行される、請求項２５に記載の方法。
【請求項３１】
前記複数のノードの１つに各バケットを割当てるステップは、バケット−ノード間の個々の関係を列挙することによって実行される、請求項２５に記載の方法。
【請求項３２】
バケットの数は、ノードの数よりも大きく、バケット−ノード間の関係は、多対一の関係である、請求項２５に記載の方法。
【請求項３３】
データ項目−バケット間のマッピングを変更することなくバケット−ノード間のマッピングを変更することにより、バケットにマッピングされたすべてのデータ項目の所有権を第１のノードから第２のノードに再割当するステップをさらに含む、請求項２５に記載の方法。
【請求項３４】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項３５】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項３６】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項３に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能
な媒体。
【請求項３７】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項４に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項３８】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項５に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項３９】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項６に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４０】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項７に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４１】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項８に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４２】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項９に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４３】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１０に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４４】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１１に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４５】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１２に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４６】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１３に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４７】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１４に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４８】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１５に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項４９】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１６に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５０】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１７に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５１】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１８に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５２】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１９に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５３】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２０に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５４】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２１に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５５】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２２に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５６】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２３に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５７】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２４に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５８】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２５に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項５９】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２６に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項６０】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２７に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項６１】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２８に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可
能な媒体。
【請求項６２】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項２９に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項６３】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項３０に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項６４】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項３１に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項６５】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項３２に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項６６】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項３３に記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【請求項６７】
マルチノードの非共有データベースシステムで使用するための方法であって、
前記マルチノードの非共有データベースシステムの第１のノードが、第１のデータ項目および第２のデータ項目の排他的な所有者として機能するステップを含み、前記第１のデータ項目および前記第２のデータ項目は、前記マルチノードの非共有データベースシステムによって管理されるデータベース内に永続的に記憶されたデータ項目であり、前記方法はさらに、
永続的な記憶上の第１のデータ項目の位置を変更せずに、または前記第１のノードをシャットダウンせずに、前記第１のノードから前記マルチノードの非共有データベースシステムの第２のノードに前記第１のデータ項目の所有権を再割当するステップと、
所有権を再割当した後に、前記第１のノードが第２のデータ項目の所有者として作動すること、および前記第２のデータ項目についての演算のための全要求を処理することを継続するステップとを含む、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
発明の分野
この発明は、共有されたディスクハードウェア上で稼動する非共有データベースシステムにおいてデータを管理するための技術に関する。
【背景技術】
【０００２】
発明の背景
マルチプロセッシングコンピュータシステムは一般に、３つのカテゴリ、すなわち、全共有システム、共有ディスクシステム、および非共有システムに分類される。全共有システムにおいて、すべてのプロセッサ上のプロセスは、システム内のすべての揮発性メモリデバイス（以降、包括的に「メモリ」と称する）と、すべての不揮発性メモリデバイス（以降、包括的に「ディスク」と称する）とに対して直接のアクセスを有する。したがって、全共有の機能を提供するために、コンピュータのさまざまな構成要素間には高度な配線が必要とされる。加えて、全共有アーキテクチャには、スケーラビリティの限界が存在する。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
共有ディスクシステムでは、プロセッサおよびメモリがノードにグループ化される。共有ディスクシステム内の各ノードは、それ自体が、複数のプロセッサおよび複数のメモリを含む全共有システムを構成し得る。すべてのプロセッサ上のプロセスは、システム内のすべてのディスクにアクセス可能であるが、特定のノードに属するプロセッサ上のプロセスのみが、特定のノード内のメモリに直接アクセスできる。共有ディスクシステムは一般に、必要とする配線が、全共有システムよりも少ない。共有ディスクシステムはまた、作業負荷が不均衡な状態にも容易に適合する。なぜなら、すべてのノードがすべてのデータにアクセスできるためである。しかしながら、共有ディスクシステムは、コヒーレンスオーバヘッドの影響を受けやすい。たとえば、第１のノードがデータを変更し、かつ、第２のノードがその同じデータの読出または変更を望む場合、そのデータの正しいバージョンが第２のノードに確実に提供されるように、さまざまなステップを実行しなければならないことが考えられる。
【０００４】
非共有システムでは、すべてのプロセッサ、メモリ、およびディスクがノードにグループ化される。非共有システムは、共有ディスクシステムと同様に、各ノード自体が全共有システムまたは共有ディスクシステムを構成し得る。特定のノード上で稼動するプロセスのみが、特定のノード内のメモリおよびディスクに直接アクセス可能である。マルチプロセッシングシステムの３つの一般的なタイプのうち、さまざまなシステム構成要素間で必要とされる配線の量は、一般に非共有システムが最も少ない。しかしながら、非共有システムは、作業負荷が不均衡な状態の影響を最も受けやすい。たとえば、特定のタスク中にアクセスされるべきすべてのデータが、特定のノードのディスク上に存在し得る。したがって、他のノード上のプロセスがアイドル状態であるにも関わらず、粒度の細かい仕事を実行するために、そのノード内で稼動するプロセスしか使用することができない。
【０００５】
マルチノードシステム上で稼動するデータベースは一般に、２つのカテゴリ、すなわち、共有ディスクデータベースおよび非共有データベースに分類される。
【０００６】
共有ディスクデータベース
共有ディスクデータベースは、データベースシステムによって管理されるすべてのデー
タが、データベースシステムにとって利用可能なすべての処理ノードの管理下にある（visible）という前提に基づき、仕事を調整する。その結果、共有ディスクデータベースでは、仕事中にアクセスされるであろうデータを含むディスクの位置に関係なく、サーバがいずれかのノード上のプロセスにいずれかの仕事を割当てることができる。
【０００７】
すべてのノードが同じデータへのアクセスを有し、各ノードがそれ自体の専用キャッシュを有しているため、同じデータ項目の多数のバージョンが、多くのノード中のどのような数のノードのキャッシュ内にも存在し得る。残念ながら、このことは、１つのノードが特定のデータ項目の特定のバージョンを要求する際に、そのノードが他のノードと連携して、要求を行なっているノードにそのデータ項目の特定のバージョンが転送されるようにしなければならないことを意味する。したがって、共有ディスクデータベースは、「データ転送」の概念で作動すると言われており、データは、そのデータに仕事を行なうように割当てられたノードに転送されなければならない。
【０００８】
このようなデータ転送要求は、「ピング（ping）」を生じ得る。具体的に、ピングは、１つのノードが必要とするデータ項目の複製が、別のノードのキャッシュ内に存在する際に生じる。ピングは、データ項目がディスクに書込まれた後にディスクから読出されることを必要とし得る。ピングにより必要とされるディスク動作の性能は、データベースシステムの性能を著しく下げる恐れがある。
【０００９】
共有ディスクデータベースは、非共有コンピュータシステムおよび共有ディスクコンピュータシステムのいずれの上でも稼動され得る。非共有コンピュータシステム上で共有ディスクデータベースを稼動させるために、オペレーティングシステムにソフトウェアサポートを追加するか、または、追加のハードウェアを設けて、プロセスが遠隔ディスクへのアクセスを有し得るようにすることが可能である。
【００１０】
非共有データベース
非共有データベースは、プロセスと同じノードに属するディスクにデータが含まれている場合に限り、そのプロセスがそのデータにアクセス可能であるものと想定する。したがって、特定のノードが、別のノードによって所有されるデータ項目についての演算が実行されることを望む場合、その特定のノードは、他のノードがその演算を実行するように、他のノードに要求を送信しなければならない。したがって、非共有データベースは、ノード間でデータを転送する代わりに「機能の転送」を実行すると言われる。
【００１１】
いずれかの所定のデータ片が１つのノードによってのみ所有されているため、その１つのノード（データの「所有者」）のみが、そのキャッシュ内にそのデータの複製を有する。したがって、共有ディスクデータベースシステムで必要とされたタイプのキャッシュのコヒーレンスのメカニズムが必要とされない。さらに、非共有システムは、ピングにまつわる性能の不利益を被らない。なぜなら、別のノードがそのキャッシュにデータ項目をロードすることができるように、そのデータ項目を所有するノードが、そのデータ項目のキャッシュされたバージョンをディスクに保存するように求められないためである。
【００１２】
非共有データベースは、共有ディスクマルチプロセッシングシステムおよび非共有マルチプロセッシングシステムのいずれの上でも稼動され得る。共有されたディスクマシン上で非共有データベースを稼動させるために、データベースをセグメント化して各パーティションの所有権を特定のノードに割当てるためのメカニズムを設けることができる。
【００１３】
所有を行なうノードのみがデータ片に作用し得るということは、非共有データベース内の作業負荷が極めて不均衡になり得ることを意味する。たとえば、１０個のノードのシステムにおいて、仕事の全要求の９０％が、それらのノードのうちの１つによって所有され
るデータを必要とするかもしれない。したがって、その１つのノードが酷使され、他のノードの計算リソースが十分に活用されない。作業負荷の「均衡を取り戻す」ために、非共有データベースをオフラインにすることができ、データ（およびその所有権）をノード間で再分配することができる。しかしながら、このプロセスは、潜在的に大量のデータの移動を伴い、作業負荷の偏りを一時的にしか解決しない恐れがある。
【課題を解決するための手段】
【００１４】
この発明は、添付の図面において限定ではなく例示として示される。これらの図面では、同じ参照番号が同じ要素を指す。
【発明を実施するための最良の形態】
【００１５】
発明の詳細な説明
共有ディスク記憶システムを含む非共有データベースシステムの性能を改善するためのさまざまな技術を以下に説明する。以下の記載内容では、説明のために多数の特定の詳細を明示して、この発明の完全な理解を図る。しかしながら、このような特定の詳細を用いなくてもこの発明を実施し得ることが明らかであろう。場合によっては、周知の構造およびデバイスをブロック図の形で示し、この発明をむやみに不明瞭にしないようにする場合もある。
【００１６】
機能上の概観
非共有データベースシステムを稼動する少なくとも２つのノードがディスクへの共有されたアクセスを有する非共有データベースシステムの性能を改善するためのさまざまな技術を、以下に説明する。データベースシステムの非共有アーキテクチャによって規定されるように、各データ片は依然として、いずれかの所定の時点において１つのノードによってのみ所有される。しかしながら、非共有データベースシステムを稼動する少なくともいくつかのノードがディスクへの共有されたアクセスを有するという点を利用して、非共有データベースシステムの均衡をより効率よく取り戻し、非共有データベースシステムをより効率よく回復する。
【００１７】
具体的には、永続的な記憶上のデータの位置を変更することなく、非共有データベース内のデータの所有権を変更するための技術を提供する。データの所有権を転送する間に、そのデータに対する永続的な記憶の位置が変更されないため、データを物理的に再配置することによって生じる場合よりも自由に、かつ、性能の不利益が少ない状態で、所有権を転送することができる。
【００１８】
所有権の高速かつ実行時の再割当を行なうためのさまざまな技術もまた説明する。再割当が実行時に行なわれ得るため、非共有システムは、再割当を実行するためにオフラインにされる必要がない。さらに、これらの技術は、相対的に細かい細分性を伴ってどのように再割当が実行され得るかを説明しており、ノードのうちの１つのノード上のいくつかのデータ項目の所有権を割当てるためだけに、全ノード間にわたって大量のデータの大容量の再割当を実行する必要をなくす。
【００１９】
共有ディスクシステムを含む例示的なクラスタ
図１は、この発明の実施例が実現され得るクラスタ１００を示すブロック図である。クラスタ１００は、相互接続１３０によって結合される５個のノード１０２、１０４、１０６、１０８、および１１０を含み、相互接続１３０は、これらのノードが互いに通信することを可能にする。クラスタ１００は、２つのディスク１５０および１５２を含む。ノード１０２、１０４および１０６は、ディスク１５０へのアクセスを有し、ノード１０８および１１０は、ディスク１５２へのアクセスを有する。したがって、ノード１０２，１０４および１０６とディスク１５０とを含むサブシステムは、第１の共有ディスクシステム
を構成し、ノード１０８および１１０とディスク１５２とを含むサブシステムは、第２の共有ディスクシステムを構成する。
【００２０】
クラスタ１００は、２つの共有ディスクサブシステムを含み、かつ、それらの共有ディスクサブシステム間で帰属関係が重複しない、相対的に単純なシステムの一例である。実際のシステムは、クラスタ１００よりもより一層複雑であることが考えられ、数百個のノード、数百個の共有ディスク、および、これらのノードとこれらの共有ディスクとの間に多対多の関係を有する。このようなシステムでは、多くのディスクへのアクセスを有する１つのノードが、たとえば、いくつかの別個の共有ディスクサブシステムのメンバーであることが考えられ、ここでは、共有ディスクサブシステムの各々が、共有されたディスクのうちの１つと、その共有されたディスクへのアクセスを有するすべてのノードとを含む。
【００２１】
共有ディスクシステム上の非共有データベース
例示のため、非共有データベースシステムがクラスタ１１０上で稼動しているものと想定されたい。ここで、非共有データベースシステムによって管理されるデータベースは、ディスク１５０および１５２に記憶される。データは、データベースシステムの非共有特性に基づき、５個のグループまたはパーティション１１２、１１４、１１６、１１８、および１２０に分離され得る。各パーティションは、対応するノードに割当てられる。パーティションに割当てられたノードは、そのパーティション内に存在するすべてのデータの排他的な所有者であると考えられる。この例において、ノード１０２、１０４、１０６、１０８、および１１０はそれぞれ、パーティション１１２、１１４、１１６、１１８、および１２０を所有する。ディスク１５０へのアクセスを有するノード（ノード１０２、１０４および１０６）によって所有されるパーティション１１２、１１４および１１８は、ディスク１５０に記憶される。同様に、ディスク１５２へのアクセスを有するノード（ノード１０８および１１０）によって所有されるパーティション１１８および１２０は、ディスク１５２に記憶される。
【００２２】
クラスタ１００上で稼動するデータベースシステムの非共有特性によって規定されるように、いずれかのデータ片は、いずれかの所定の時点において、多くても１つのノードによって所有される。加えて、共有されたデータへのアクセスは、機能の転送により調整される。たとえば、ＳＱＬ言語をサポートするデータベースシステムの場合、特定のデータ片を所有しないノードは、そのデータ片を所有するノードにＳＱＬステートメントのフラグメントを転送することにより、そのデータに関する演算が実行されるようにすることができる。
【００２３】
所有権のマップ
機能の転送を効率よく実行するために、すべてのノードは、どのノードがどのデータを所有しているかを認識しなければならない。したがって、所有権のマップが規定され、所有権のマップは、データ−ノード間の所有権の割当を示す。実行時に、さまざまなノードが所有権のマップに照会し、実行時に、ＳＱＬフラグメントの経路を適正なノードに指定する。
【００２４】
一実施例に従うと、データ−ノード間のマッピングは、ＳＱＬ（または他のいずれかのデータベースアクセス言語）のステートメントのコンパイル時に決定される必要はない。むしろ、以下により詳細に説明するように、データ−ノード間のマッピングは、実行時に規定および修正され得る。以下に説明する技術を用いると、データが存在するディスクへのアクセスを有する１つのノードから、データが存在するディスクへのアクセスを有する別のノードに所有権が変更する際に、データをディスク上の永続的な位置から移動させることなく所有権の変更が実行される。
【００２５】
ロッキング
ロックは、リソースへのアクセスを有するいくつかのエンティティ間でリソースへのアクセスを調整するために使用される構造である。非共有データベースシステムの場合、非共有データベース内のユーザデータへのアクセスを調整するためのグローバルロッキングが必要ではなくなる。なぜなら、いずれかの所定のデータ片が１つのノードによってのみ所有されているためである。しかしながら、非共有データベースのすべてのノードが、所有権のマップへのアクセスを要求するため、所有権のマップに対する整合性のない更新を防ぐために、何らかのロッキングが必要とされ得る。
【００２６】
一実施例に従うと、データ片の所有権が１つのノード（「以前の所有者」）から別のノード（「新規の所有者」）に再割当されている際に、２ノードロッキング方式が使用される。さらに、非共有データベースに関連するメタデータへのアクセスを制御するために、グローバルロッキング機構を使用することができる。このようなメタデータは、たとえば所有権のマップを含み得る。
【００２７】
データを移動しない所有権の転送
この発明の一局面に従うと、データの所有権は、データの移動を伴わずに１つのノード（以前の所有者）から、そのデータへの接続性を有する別のノード（新規の所有者）に変更され得る。たとえば、特定のデータ項目が、現時点でパーティション１１２に存在するものと想定されたい。データ項目がパーティション１１２に存在しているため、このデータ項目は、ノード１０２により所有される。このデータの所有権をノード１０４に変更するために、データはパーティション１１２に属することを中止して、その代わりに、パーティション１１４に属さなければならない。非共有データベースシステムの従来の実施例では、このような所有権の変更により、データ項目が一般に、パーティション１１２に対応するディスク１５０上の１つの物理的な位置から、パーティション１１４に対応するディスク１５０上の別の物理的な位置に、実際に移されていた。
【００２８】
対照的に、この発明の一実施例によると、パーティション１１２および１１４は、ディスク１５０の特定の位置に結合された物理的なパーティションではない。むしろ、パーティション１１２および１１４は、その特定のデータ項目がディスク１５２上のどこに存在するかに関係なく、ノード１０２および１０４が現時点でそれぞれ所有する一組のデータ項目を単に表す、位置に依存しないパーティションである。したがって、パーティション１１２および１１４が位置に依存しないため、ディスク１５０上のデータを実際に何ら移動させることなく、データ項目を１つのパーティションから別のパーティションに移動させる（すなわち、１つの所有者から別の所有者に割当てる）ことができる。
【００２９】
データ項目の所有権を変更することによってデータ項目の移動は必要とされないものの、所有権のマップの変更が必要とされる。非共有データベース内のユーザデータとは異なり、所有権のマップはさまざまなノード間で共有される。その結果、所有権のマップの一部は、さまざまなノードの専用キャッシュに収容されることが考えられる。したがって、データ項目の所有権の変更に応じて所有権のマップが変更され、所有権のマップのうち影響を受けた部分のキャッシュされた複製が、無効にされる。
【００３０】
代替的な一実施例に従うと、所有権の変更は、根底に存在するオブジェクトに対する概略的な変更と同様に実施される。特に、所有権のマップに対して変更が行なわれた後に、所有権のマップを参照するコンパイルされたステートメントは無効にされ、新しい所有権のマップを使用するように再コンパイルされる。
【００３１】
ノードの追加および除去
クラスタ１００の作動中に、クラスタ１００へのノードの追加、またはクラスタ１００からのノードの除去が望まれることが考えられる。従来の非共有システムにおいて、このような演算は、しばしば、ファイルまたはディスクの１つの物理的なパーティションから、別のファイルまたはディスクの別の物理的なパーティションへの大量のデータの移動を伴っていた。位置に依存しないパーティションを用いることにより、物理的に再配置されなければならないデータは、単に、そのデータが現在存在するディスクへのアクセスを有さないノードに所有権を転送されているデータである。
【００３２】
たとえば、クラスタ１００に新規のノードＸが追加され、かつ、ノードＸがディスク１５２へのアクセスを有するものの、ディスク１５０へのアクセスを有さないものと想定されたい。ノード間の作業負荷の均衡を取り戻すために、ノード１０２〜１１０によって現時点で所有されるいくつかのデータが、ノードＸに再割当され得る。以前の所有者がノード１０２〜１０６であるデータが、ノードＸがアクセスを有さないディスク１５０上に存在しているため、このデータは、ノードＸがアクセスを有するディスク１５２に物理的に移動されなければならない。しかしながら、以前の所有者がノード１０８および１１０であるデータが、ノードＸがアクセスを有するディスク１５２上に既に存在しているため、そのデータの所有権は、実際のデータを移動させずに所有権のマップを更新することにより、ノードＸに転送され得る。
【００３３】
同様に、ノードがクラスタ１００から除去される際には、そのデータ項目が存在するディスクへのアクセスを現時点で有していないノードに転送されるデータ項目のみが、物理的な再配置を必要とする。その所有権が、データが存在するディスクへのアクセスを有するノードに転送されるデータ項目は、移動させる必要がない。たとえば、クラスタ１００からノード１０２が除去され、ノード１０２がそれまで所有していたデータ項目のすべての所有権がノード１０４に転送される場合、所有権の変更に応じてデータ項目が物理的に再配置される必要はない。
【００３４】
所有権の段階的な転送
一実施例に従うと、ノードの追加または除去に応じたデータ所有権の大容量の再割当にまつわる性能の不利益は、所有権の転送を一度にすべてではなく徐々に行なうことによって減少する。たとえば、クラスタに新規のノードが追加される場合、既存のノードと同程度だけ、新規のノードを繁忙状態に置くのに十分なデータの所有権を転送する代わりに、このシステムは、まず、新規のノードに対し、僅かなあるいはデータ項目のない所有権を転送する。一実施例に従うと、所有権は、作業負荷の必要性に基づいて段階的に転送される。たとえば、データの所有権の転送は、ノードのうちの１つが酷使されていることがシステムによって検出されると生じ得る。ノードが酷使されていると検出されたことに応じて、その酷使されているノードに属するデータ項目のいくつかは、以前に追加されたノードに割当てられ得る。酷使されているノードが、もはや酷使されていないと検出されるまで、その酷使されているノードから新規のノードに、より多くのデータ項目が段階的に再割当され得る。
【００３５】
その一方で、既存のノードの作業負荷が或る一定のしきい値よりも下がると、所有権の再割当が行なわれ得る。具体的には、繁忙状態のノードの作業負荷を減らす際に、繁忙状態のノードから新規のノードに所有権のいくつかの責任を転送して、再割当の動作が、既に酷使されているノードの性能を下げないようにすることが望ましいと考えられる。
【００３６】
除去されたノードから所有権を段階的に転送することに関し、所有権の転送は、たとえば必要に応じて行なわれ得る。たとえば、データ項目Ｘが、除去されたノードにより所有されていた場合、何らかのノードがデータ項目Ｘを必要とする演算を要求したことが検出されると、データ項目Ｘは別のノードに再割当され得る。同様に、除去されたノードから
既存のノードへの所有権の転送は、既存のノードの作業負荷が或る一定のしきい値よりも下がると行なわれ得る。
【００３７】
バケットベースのセグメント化
上述のように、非共有データベースにより管理されるデータがセグメント化され、各パーティション内のデータが１つのノードにより排他的に所有される。一実施例に従うと、これらのパーティションは、データを論理バケットに割当てた後に、それらのバケットの各々を１つのパーティションに割当てることによって規定される。したがって、所有権のマップ内のデータ−ノード間のマッピングは、データ−バケット間のマッピングおよびバケット−ノード間のマッピングを含む。
【００３８】
一実施例に従うと、データ−バケット間のマッピングは、各データ項目の名前にハッシュ関数を適用することによって規定される。同様に、バケット−ノード間のマッピングは、バケットに関連する識別子に別のハッシュ関数を適用することによって規定され得る。代替的に、マッピングの一方または両方は、範囲ベースのセグメント化を用いることにより、または、個々の関係の１つ１つを単に列挙することにより、規定され得る。たとえば、１００万個のデータ項目の名前空間を５０個の範囲に分割することにより、それらのデータ項目は、５０個のバケットにマッピングされ得る。５０個のバケットは次に、各バケットに関する、（１）そのバケットを識別し、（２）現時点でバケットが割当てられたノードを識別する記録を記憶することにより、５個のノードにマッピングされ得る。
【００３９】
バケットを使用することにより、各データ項目に関して別個のマッピング記録が記憶されていたマッピングに比べ、所有権のマッピングのサイズが大幅に縮小される。さらに、バケットの数がノードの数を上回る実施例では、バケットの使用により、所定のノードが所有するデータのサブセットへの所有権の再割当が相対的に容易になる。たとえば、１つの新規のノードには、現時点で１０個のバケットが割当てられている１つのノードから、１つのバケットが割当てられ得る。このような再割当は、そのバケットについてのバケット−ノード間のマッピングを示す記録の修正を伴うに過ぎない。再割当されたデータのデータ−バケット間のマッピングは、変更されなくてよい。
【００４０】
上述のように、データ−バケット間のマッピングは、以下のものに限定されないが、ハッシュパーティション、範囲パーティション、またはリスト値を含むさまざまな技術のうちのいずれか１つを用いることによって規定され得る。範囲ベースのセグメント化が用いられ、かつ、範囲の数がノードの数よりもそれほど著しく大きくない場合は、データ項目をセグメント化するのに使用される範囲キーが変化しない値（日付等）である限り、データベースサーバは、粒度のより細かい（より狭い）範囲を用いて所望の数のバケットを得ることができる。範囲キーが変化し得る値である場合、データ項目は、特定のデータ項目についての範囲キーの値に対する変化に応じて古いバケットから除去されて、そのデータ項目の範囲キーの新規の値に対応するバケットに追加される。
【００４１】
ツリーベースのパーティション
データベースシステムによって管理されるデータ項目をサブセットにセグメント化する別の方法が、階層で分類された構造（BTree等）を有することであり、それにより、ツリー構造の上位レベル（ルート等）がすべてのノードにより所有され、かつ、より下位のレベル（葉ノード等）がノード間でセグメント化されるようにする。一実施例に従うと、ツリー構造は、複数のサブツリーを含み、ここでは、各サブツリーが特定のノードに割当てられる。さらに、より下位のレベルの各ツリーノードは、一組のデータに対応する。より下位のレベルのツリーノードに関連する一組のデータは、そのツリーノードを含むサブツリーに関連するノードによって所有される。
【００４２】
このような実施例において、サブツリーの所有権が変化すると、より上位のレベルは、ロッキング／一斉通信方式を介して無効にされる。より下位のレベルにあるポインタは変更されて、異なるノードの下でサブツリーの所有権を移動させる。
【００４３】
再割当中におけるダーティなバージョンの処理
上述のように、データの新規の所有者が、そのデータが存在するディスクへのアクセスを有するときに、データの所有権は、ディスク上のデータの物理的な位置を物理的に動かすことなくバケットをノードに再割当することによって変更される。しかしながら、以前の所有者が、その揮発性メモリに、再割当されたデータ項目の１つ以上の「ダーティな」バージョンを有していることが考えられる。データ項目のダーティなバージョンは、現時点でディスクに存在するバージョンに反映されていない変更を含むバージョンである。
【００４４】
一実施例に従うと、データ項目のダーティなバージョンは、所有権の転送動作の一部として共有ディスクに書込まれる。したがって、新規の所有者が、最近所有権を入手したデータ項目をディスクから読出すと、新規の所有者によって読出された項目のバージョンは、以前の所有者が行なった最新の変更を反映する。
【００４５】
代替的に、データ項目のダーティなバージョンをディスクに記入することに関連するオーバーヘッドを回避するために、再実行が強制されて上書きされない場合に、ダーティなデータ項目を共有ディスクに記入する前に、データ項目のダーティなバージョンを以前の所有者の揮発性メモリから一掃することができる。具体的には、所有しているノードがデータ項目に変更を行なうと、その変更を反映する「再実行」記録が生成される。その変更に関する再実行の記録が、データ項目の所有権の変更時または変更前にディスクに強制される限り、以前の所有者は、ダーティなバージョンをディスクにまず保存することなくデータ項目のダーティなバージョンを一掃することができる。この場合、新規の所有者は、（１）再実行記録を読出して、データ項目のディスクバージョンにどのような変更が行なわれなければならないかを判断すること、および（２）データ項目のディスクバージョンに対して示された変更を行なうことによってデータ項目の最新のバージョンを再構築することができる。
【００４６】
別の代替例として、ダーティなデータ項目は、自発的に（以前の所有者により先を見越して）、または、トランザクションは新規の所有者のノードにおけるデータを要求するため、（新規の所有者からの要求に応じて）オンデマンドで、新規の所有者のキャッシュに転送される。
【００４７】
所有権の変更の前にデータ項目のダーティなバージョンがディスクにフラッシュされていない場合、データ項目への変更は、複数の回復ログに反映され得る。たとえば、第１のノードがデータ項目に変更を行ない、次に、そのデータ項目の所有権が第２のノードに転送されるものと想定されたい。第１のノードは、再実行ログをディスクにフラッシュすることができるが、データ項目のダーティなバージョンを、まずディスクに記憶することなく、第２のノードに直接転送することができる。第２のノードは次に、そのデータ項目に対して第２の変更を行なうことができる。第２のノードが第２の変更についての再実行記録をディスクにフラッシュし、次に、第２のノードがデータ項目のダーティなバージョンをディスクに記憶する前に故障したと想定されたい。これらの状況下において、データ項目のディスクバージョンに再び適用されなければならない変更は、第１のノードの再実行ログおよび第２のノードの再実行ログのいずれにおいても反映される。一実施例によると、再実行ログをマージすることによってオンラインの回復を実行して、データ項目を回復する。
【００４８】
一実施例に従うと、データ項目の所有権は、データ項目を変更しているトランザクショ
ンがコミットするのを待たずに転送され得る。したがって、１つのトランザクションによりデータ項目に対して行なわれる変更は、複数の再実行ログの全体に広がり得る。これらの状況下において、データベースサーバのトランザクションロールバック機構は、複数のログからの変更を取消すように構成され、ここでは、データブロックに変更が行なわれたのとは逆の順序で、データブロックに取消し動作が実行される。加えて、すべての所有者からの再実行ログをマージする媒体回復機構が設けられ、ここで、マージ処理は、データのバックアップ以降に行なわれたすべての変更についての再実行記録を必要とする。
【００４９】
更新を阻止しない再割当
この発明の一局面に従うと、データ項目の所有権の再割当は、再割当されている最中のデータの更新を阻止することなく実行される。一実施例に従うと、所有権の割当は、再割当されたバケットに属するいずれかのデータ項目にアクセスするすべてのトランザクションがコミットすること、および、バケットに属するダーティなデータ項目のすべてがディスクにフラッシュされることをデータベースサーバに待たせることによって更新を阻止することなく実行される。このような状況下において、再割当されたバケットに属するデータは、以前の所有者がそのデータに対して専有モードのアクセスまたは共有モードのアクセスを有していない場合、直ちに（ダーティなバージョンがディスクにフラッシュされるのを待たずに）更新され得る。以前の所有者がそのデータに対して専有モードのアクセスを有している場合、以前の所有者は、そのキャッシュ内にこのデータのダーティなバージョンを有していることが考えられるため、以前の所有者がダーティなページ（または関連する変更についての再実行）を共有ディスクに書込むまで、更新は遅れる。
【００５０】
データベースサーバは、その所有権が新規に転送されたデータ項目への新規の更新を許可する前に、以前の所有者に要求された進行中の更新が完了するのを待つように構成され得る。その一方で、データベースサーバは、進行中の演算を中止してから新規の所有者にトランザクションを再発行するように構成され得る。一実施例に従うと、さまざまな因子に基づき、所定の進行中の演算が完了するのを待つべきであるかどうかに関する判断が行なわれる。このような因子には、たとえば、その演算に対してどれだけの仕事が既に行なわれたかが含まれ得る。
【００５１】
或る一定の状況下において、以前の所有者に要求された更新が完了されるのを待つことにより、偽のデッドロックが生じ得る。たとえば、行Ａがバケット１に存在し、行ＢおよびＣがバケット２に存在するものと想定されたい。そして、トランザクションＴ１が行Ａを更新し、別のトランザクションＴ２が行Ｂを更新したと想定されたい。この時点で、バケット２の所有権が新規のノードに再びマッピングされたと想定されたい。この時点でＴ１が行Ｃを更新したいと望む場合、Ｔ１は再マッピングが完了するのを待つ。したがって、Ｔ１はＴ２を待つ。Ｔ２が行Ａを更新したいと望む場合、Ｔ１とＴ２との間にデッドロックが生じる。
【００５２】
一実施例に従うと、いくつかのバケットの所有権が所望される際も、所有権の転送は１つのバケットにつき１度で実行され、再割当されたバケット内のデータにアクセスするためにトランザクションが待たなければならない時間量を最小限にする。
【００５３】
所有権を譲渡するための技術
以下の例は、この発明のさまざまな実施例に従った、共有ディスクシステム上で実現される非共有データベース内でデータの所有権を転送するための技術を示す。以下の例において、データの所有権は、データを変更したトランザクションが依然として実行中である間に変更されることが想定される。すなわち、データベースシステムは、再割当されることになっているデータにアクセスする進行中のトランザクションが静止するのを待たない。
【００５４】
オブジェクトのサブセット（「バケットＢ」）の所有権がノードＸからノードＹに変更されることが想定される一例を参照して、所有権を転送するための１つの技術を説明する。一実施例に従うと、データベースシステムはまず、バケットＢを、ＸからＹへの「移動中」であると標示する。所有権のマップの変更が次に、すべてのノードに一斉通信されるか、またはグローバルロッキングを介して無効にされる。
【００５５】
一実施例に従うと、バケットＢ内のデータを必要とするクエリ実行計画が、所有権のマップの変更に応じて再生成される。代替的に、所有権のマップの変更に応じて、キャッシュされたマップが無効にされて再ロードされる。
【００５６】
再割当の後に、バケットＢ内のデータにアクセスするいずれかの新規のサブクエリ／ｄｍｌフラグメントが、ノードＹに転送される。任意に、ＸからＹへの移動中であるとバケットに標示される前に、現時点においてＸで稼動中のＳＱＬフラグメントがロールバックされ得る。これらのフラグメントは次に、再割当の後にノードＹに再発行され得る。これらのフラグメントが属するトランザクションが、それ自体はロールバックされず、現時点での呼出のみがロールバックされて新規の所有者に再送信されることに注目されるべきである。特に、以前の呼出においてバケットＢ内のデータに対してノードＸによって行なわれた変更は、そのまま置かれる。
【００５７】
一実施例に従うと、ノードＸは、単純なローカルロッキング方式により、バケットＢ内のデータにアクセスを行なっている進行中の呼出が存在しないことを検出することができる。このロッキング方式には、たとえば、バケット内のデータにアクセスする各プロセスにバケット上の共有されたロック／ラッチを獲得させることが含まれ得る。バケットが再割当されるべき際に、再割当を実行するプロセスは、バケット上の専有のロック／ラッチを得ることができるまで待つ。再割当のプロセスは、バケット上の専有のロック／ラッチを獲得することにより、他のプロセスがそのバケットに現時点でアクセスしないようにする。
【００５８】
一実施例に従うと、ノードＸは、潜在的なデッドロックのため、バケットを移動中と標示する前にすべての呼出が成功裏に完了するのを待たない。以下の内容は、このようなデッドロックがどのように生じ得るかの一例である。再マッピングされるバケット内の３つの行１、２および３を考えられたい。
【００５９】
事象の以下のシーケンスはデッドロックを生じ得る。
【００６０】
（ａ）  Ｔ１が行２を更新する。
【００６１】
（ｂ）  Ｔ２が、行２が後に続く行１の複数行の更新を行なう。Ｔ２がＴ１を待つ。
【００６２】
（ｃ）  バケットが再マッピングされることが決定される。
【００６３】
（ｄ）  Ｔ１が行３を更新したいと望む。Ｔ１がＴ２を待つ。
【００６４】
一実施例によると、バケットＢからアクセスするデータがキャッシュ内に存在する限り、進行中の呼出に通常どおり実行を継続させることによって、ノードＸにおける進行中の呼出が強制終了されることが回避される。すなわち、Ｘは、ノード間のロッキングを行なわずにバケットＢに対するディスクからブロックを読出すことができない。キャッシュミスが存在し、かつバケットが移動中である場合、ＸはメッセージをＹに送信し、Ｙからブロックを検索するか、またはディスクからブロックを読出さなければならない。バケット
の移動中に、ＸとＹとの間でキャッシュコヒーレンスプロトコルが使用される。
【００６５】
新規の所有者における要求の処理
バケットＢがノードＹに再割当された後に、バケットＢ内のデータにアクセスする必要のあるいずれかの新規のＳＱＬフラグメントは、ノードＹにおいて実行を開始する。新規に転送されたデータ項目をディスクから読出す際にノードＹが使用する技術は、そのバケットが移動中であると標示される前に以前の所有者のノードＸが何をしたかに基づいて異なり得る。以下の事例は、新規の所有者のノードＹによって異なるシナリオがどのように処理され得るかを示す例である。
【００６６】
事例Ａ：ノードＸが進行中のすべての呼出を中止し、このバケットにマッピングするすべてのダーティなブロックを共有ディスクに書込んだと想定されたい。効率のため、各ノードは、ダーティなデータ項目をバケット毎のオブジェクトキューにリンクさせることができる。このような状況下において、ノードＹは、ディスクから直接読出しを行うことができる。キャッシュコヒーレンスは必要とされない。ノードＹは、このバケットに対する新規の所有者として直ちに標示される。
【００６７】
事例Ｂ：ノードＸが進行中のすべての呼出を中止するものの、ダーティなデータ項目は詳細に書込まれないものと想定されたい。このような状況下において、ノードＹは、ノードＸがディスクからブロックを読出す前にダーティな複製を有していないことを検索および確認する必要がない。Ｘがダーティな複製を有している場合、回復のために、および、ノードＹにおけるブロック書込によりディスクにまだ反映されておらず、かつ、ノードＸで行なわれた変更点を追い越してチェックポイントが進まないようにするために、過去の画像がノードＸに残される。Ｘ内のすべてのダーティなデータ項目が、（それ自体により、または、Ｙへの書込によって消去された過去の画像（ＰＩ）により）書込まれた後に、バケットの状態は、移動中から、所有者としてのＹに変更される。Ｙは、これにより、Ｘに確認しなくてもこのバケット内のディスクブロックにアクセスすることができる。
【００６８】
バケットの状態が移動中である間にノードＸが故障した場合、ノードＹがデータ項目の現時点での複製を有していない場合は、回復ノード（故障しなかった場合はノードＹ）が、ノードＸ内のこのバケットに対して生成された再実行（および可能性として、ノードＹも故障した場合にはノードＹにおいて生成された再実行）を適用する必要がある。
【００６９】
事例Ｃ：ノードＸが進行中の呼出を中止し、ダーティなデータ項目を消去すると想定されたい。このような状況下において、ノードＹは、キャッシュコヒーレンスを必要とせずにディスクからブロックを直接読出すことができる。しかしながら、Ｘ内に適用されていない再実行が存在する場合に、ブロックは最新のものされなければならないことが考えられる。Ｘ内で生成されたすべての再実行がＹによって適用されてディスクに書込まれるまで、バケットは移動中と考えられる。このことは、ディスク内でまだ反映されていない再実行の一部を追い越してＸがそのチェックポイントを進めることを防止するために必要である。
【００７０】
バケットの状態が移動中である間にノードＸが故障した場合、ノードＹがデータ項目の現時点での複製を有していない場合は、ノードＸ内のこのバケットに対して生成された再実行（および可能性としてノードＹも故障している場合には、ノードＹ内で生成された再実行）を適用する必要がある。
【００７１】
事例Ｄ：ノードＸが進行中の呼出を引続き実行しているものと想定されたい。ノードＸおよびノードＹはいずれも、ディスクからブロックにアクセスする前に、他方に対して確認を行なわなければならない。進行中のすべての呼出が完了して、すべてのブロックが詳
細に書込まれるか、またはＹに転送されると、Ｙが新規の所有者として標示される。この時点から、キャッシュコヒーレンスが必要とされなくなる。
【００７２】
バケットが移動中にノードＸまたはノードＹが故障した場合、回復が実行されなければならない。この場合に用いられる回復技術は、この明細書においてその各々がその全体を援用される米国特許第６，３５３，８３６号、および２００２年３月４日に出願された米国特許出願第１０／０９２，０４７号に記載されるものと同様であり得る。両方のノードが故障した場合、ＸおよびＹからの再実行ログがマージされる必要がある。
【００７３】
事例Ｄで説明したように、ノードＸに対し進行中の呼出を引続き実行させることにより、さまざまな利益が生じる。具体的には、ノードＸに対し進行中の呼出を引続き実行させることにより、現在進行中のトランザクションに与える影響を最小限にした状態で所有権の再割当を可能にする。しかしながら、バケットＢに対しノードＸとＹとの間でキャッシュコヒーレンスおよび回復の方式が実施されなければならない。
【００７４】
これらの状況下においてキャッシュコヒーレンスを提供するための１つの手法は、ノードＸがバケットＢに対して現時点でキャッシュしたすべてのデータ項目に対するロックを、ノードＸに獲得させることを含む。Ｂ内のすべてのデータ項目に対するマスタ／ディレクトリノードは、ノードＹとして割当てられ得る。次に、バケットＢがＸからＹに移されるという通知がすべてのノードに送信される。この通知は、所有権のマップを無効にし／更新し、それにより、Ｂへのさらに別のアクセスが、Ｙに送信されるようにする。
【００７５】
この時点よりも前に故障が生じた場合、所有権の再割当の動作は中止される。そうでなければ、このマップは更新されて、Ｙが新規の所有者であること、および、キャッシュコヒーレンスが効力を有していることを示す。
【００７６】
キャッシュコヒーレンスプロトコル、たとえば米国特許第６，３５３，８３６号および米国特許出願第１０／０９２，０４７号に記載されたプロトコルが次に、バケットＢ内のすべてのデータ項目に対し、ＸおよびＹにより実行される。Ｂ内にこれ以上ダーティなデータ項目が存在しない場合、キャッシュコヒーレンスプロトコルは停止し得る。Ｙは、Ｂ内のデータ項目に対してＹが獲得していたと考えられるあらゆるロックを解放することができる。
【００７７】
一実施例によると、キャッシュコヒーレンスプロトコルは常に効力を有しており、それにより、バケットを所有するノードが、それらのロックに対するマスタでもあるようにする。ほとんどの場合、各ノードはローカルなロックのみを割当て（なぜなら、各ノードがマスタであるためである）、所有権が変更する際にのみキャッシュコヒーレンスメッセージが必要とされる。所有権が変化すると、このバケット内に開いていたロックは、新規の所有者に対して動的に再びマスタにされ得る。
【００７８】
所有権の変更前の変更
一実施例に従うと、所有権の変更前にノードＸ内のデータを変更したサブトランザクションは、依然として実行中であると考えられる。なぜなら、これらの変更が、トランザクションのロールバックに必要とされるためである。トランザクションがロールバックして、ノードＸ内のこのバケットに変更を行なった場合、ノードＹは、Ｘ側の共有ディスクログからそれを読出すことにより、取消しログを適用する必要がある。
【００７９】
所有権の変更の前にノードＸ内のデータを変更したサブトランザクションは、ノードＹ内の同じデータを更新することが考えられる。このことは、トランザクションのロック、たとえばノードＹにおける行のロックまたはページのロックの要求が、ノードＸと調整さ
れることを必要とする。サブトランザクションがロックを要求し、このロックがノードＸ内のその同胞トランザクションによって既に保持されている場合、このロック要求は許可される。しかしながら、このロックが関連のないトランザクションによって保持されている場合、ロック要求は阻止される。待ちグラフは、この待ちを、親トランザクションの待ちとして反映し、それにより、グローバルなデッドロックが検出され得る。所有権の変更が完了し、ノードＸ内のバケットＢ内のデータへのアクセスに対してロックを獲得していたすべてのトランザクションが完了すると（コミットするか、または中止されると）、トランザクションのロックに対してローカルなロックのみが必要とされる。
【００８０】
トランザクションのロックの要求は、所有権の変更が開始する前にデータベースサーバに対し、トランザクションが完了するのを待たせることにより、ローカルな態様で常に調整され得る。
【００８１】
ハードウェアの概観
図２は、この発明の一実施例が実現され得るコンピュータシステム２００を示すブロック図である。コンピュータシステム２００は、バス２０２または情報を通信するための他の通信機構と、バス２０２に結合されて情報を処理するためのプロセッサ２０４とを含む。コンピュータシステム２００は、バス２０２に結合されてプロセッサ２０４が実行する命令および情報を記憶するためのメインメモリ２０６、たとえばランダムアクセスメモリ（ＲＡＭ）または他の動的記憶装置も含む。メインメモリ２０６は、プロセッサ２０４が実行する命令の実行中に、一時的数値変数または他の中間情報を記憶するためにも使用可能である。コンピュータシステム２００は、バス２０２に結合されてプロセッサ２０４に対する静的情報および命令を記憶するための読出専用メモリ（ＲＯＭ）２０８または他の静的記憶装置をさらに含む。磁気ディスクまたは光学ディスク等の記憶装置２１０が設けられてバス２０２に結合され、情報および命令を記憶する。
【００８２】
コンピュータシステム２００は、コンピュータユーザに情報を表示するためのディスプレイ２１２、たとえば陰極線管（ＣＲＴ）に、バス２０２を介して結合され得る。英数字キーおよび他のキーを含む入力装置２１４がバス２０２に結合されて、情報および指令選択をプロセッサ２０４に通信する。別の種類のユーザ入力装置が、方向情報および指令選択をプロセッサ２０４に通信してディスプレイ２１２上のカーソルの動作を制御するためのカーソル制御機器２１６、たとえばマウス、トラックボール、またはカーソル方向キーである。この入力装置は一般に、２つの軸、すなわち第１の軸（ｘ等）および第２の軸（ｙ等）において２自由度を有し、これによって入力装置は平面上で位置を特定することができる。
【００８３】
この発明は、この明細書に記載された技術を実現するためにコンピュータシステム２００を用いることに関する。この発明の一実施例によると、これらの技術は、メインメモリ２０６に含まれる１つ以上の命令の１つ以上のシーケンスをプロセッサ２０４が実行することに応じて、コンピュータシステム２００により実行される。このような命令は、別のコンピュータ読取可能な媒体、たとえば記憶装置２１０からメインメモリ２０６内に読出すことができる。メインメモリ２０６に含まれる命令のシーケンスを実行することにより、プロセッサ２０４はこの明細書に記載されたプロセスのステップを実行する。代替的な実施例では、ソフトウェア命令の代わりに、またはソフトウェア命令と組合せて結線回路を用いて、この発明を実施することができる。したがって、この発明の実施例は、ハードウェア回路およびソフトウェアのいずれかの特定の組合せに限定されない。
【００８４】
この明細書で用いられる「コンピュータ読取可能な媒体」という用語は、プロセッサ２０４に対して実行のために命令を提供することに携わる、いずれかの媒体を指す。このような媒体は、不揮発性媒体、揮発性媒体、および伝送媒体を含む多くの形態を取り得るが
、これらに限定されない。不揮発性媒体には、たとえば記憶装置２１０等の光学または磁気ディスクが含まれる。揮発性媒体には、メインメモリ２０６等の動的メモリが含まれる。伝送媒体には、同軸ケーブル、銅線、および光ファイバが含まれ、バス２０２を有するワイヤが含まれる。伝送媒体は、電波データ通信および赤外線データ通信の際に生成されるもの等の音波または光波の形を取り得る。
【００８５】
コンピュータ読取可能な媒体の一般的な形態には、たとえばフロッピー（登録商標）ディスク、フレキシブルディスク、ハードディスク、磁気テープ、他のいずれかの磁気媒体、ＣＤ−ＲＯＭ、他のいずれかの光学媒体、パンチカード、紙テープ、孔のパターンを有する他のいずれかの物理的媒体、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、他のいずれかのメモリチップもしくはカートリッジ、以下に述べる搬送波、またはコンピュータが読出すことのできる他のいずれかの媒体が含まれる。
【００８６】
プロセッサ２０４に対して実行のために１つ以上の命令の１つ以上のシーケンスを搬送することに対し、コンピュータ読取可能な媒体のさまざまな形態が関与し得る。たとえば、命令は、最初に遠隔コンピュータの磁気ディスクで搬送され得る。遠隔コンピュータはそれらの命令をそれ自体の動的メモリにロードして、それらの命令を、モデムを用いて電話回線経由で送信することができる。コンピュータシステム２００に対してローカルなモデムが電話回線上のデータを受信して、赤外線送信機を用いてそのデータを赤外線信号に変換することができる。赤外線信号によって搬送されたデータは赤外線検出器によって受信され得、適切な回路がそのデータをバス２０２上に出力することができる。バス２０２はそのデータをメインメモリ２０６に搬送し、そこからプロセッサ２０４が命令を取り出して実行する。メインメモリ２０６が受信した命令は、プロセッサ２０４による実行前または実行後のいずれかに、記憶装置２１０に任意に記憶され得る。
【００８７】
コンピュータシステム２００は、バス２０２に結合された通信インターフェイス２１８も含む。通信インターフェイス２１８は、ローカルネットワーク２２２に接続されたネットワークリンク２２０に対する双方向のデータ通信結合を提供する。たとえば通信インターフェイス２１８は、対応する種類の電話回線に対するデータ通信接続を設けるためのサービス統合デジタル網（ＩＳＤＮ）カードまたはモデムであり得る。別の例として、通信インターフェイス２１８は、互換性を有するローカルエリアネットワーク（ＬＡＮ）にデータ通信接続を設けるためのＬＡＮカードであり得る。無線リンクもまた実現することができる。このようなどの実現例においても、通信インターフェイス２１８は、さまざまな種類の情報を表わすデジタルデータストリームを搬送する電気信号、電磁信号、または光信号を送受信する。
【００８８】
ネットワークリンク２２０は一般に、１つ以上のネットワーク経由で他のデータ装置に対してデータ通信を提供する。たとえば、ネットワークリンク２２０は、ローカルネットワーク２２２経由で、ホストコンピュータ２２４か、またはインターネットサービスプロバイダ（Internet Service Provider）（ＩＳＰ）２２６により運営されるデータ装置に接続を提供することができる。ＩＳＰ２２６は次いで、現在一般に「インターネット」２２８と呼ばれるワールドワイドパケットデータ通信網を介してデータ通信サービスを提供する。ローカルネットワーク２２２およびインターネット２２８はともに、デジタルデータストリームを搬送する電気信号、電磁信号、または光信号を用いる。さまざまなネットワークを経由する信号と、ネットワークリンク２２０上の、または、通信インターフェイス２１８経由の信号とは、コンピュータシステム２００との間でデジタルデータを搬送し、情報を運ぶ搬送波の例示的形態である。
【００８９】
コンピュータシステム２００は、ネットワーク、ネットワークリンク２２０、および通信インターフェイス２１８を介してメッセージを送信して、プログラムコードを含むデー
タを受信することができる。インターネットの例では、サーバ２３０は、インターネット２２８、ＩＳＰ２２６、ローカルネットワーク２２２、および通信インターフェイス２１８経由で、アプリケーションプログラムに対して要求されたコードを送信することができる。
【００９０】
受信されたコードは、受信されたときにプロセッサ２０４によって実行され得、および／または後の実行のために記憶装置２１０もしくは他の不揮発性記憶装置に記憶され得る。このようにして、コンピュータシステム２００は搬送波の形でアプリケーションコードを得ることができる。
【００９１】
上述の明細書では、この発明の実施例を実現例ごとに異なり得る多数の特定の詳細を参照して説明してきた。したがって、この発明が何であるか、およびこの発明を目指して出願人が何を意図しているかを排他的に示す唯一のものが、この出願から発生して特有の形態をとった一組の請求項である。特有の形態においてこのような請求項は、今後のどのような補正をも含んで発生する。このような請求項に含まれる用語に対してここで明示されたどのような定義も、請求項で用いられる用語の意味を決定するものとする。したがって、請求項に明示的に記載されていない限定、要素、特性、特徴、利点または属性は、このような請求項の範囲を決して限定しない。したがって、明細書および図面は限定的な意味ではなく例示的な意味で捉えられるべきである。
【図面の簡単な説明】
【００９２】
【図１】この発明の一実施例に従った、２つの共有ディスクサブシステムを含むクラスタを示すブロック図である。
【図２】この発明の実施例が実現され得るコンピュータシステムのブロック図である。
【図１】
2007501457.tif 000003
【図２】
2007501457.tif 000004
【手続補正書】
【提出日】平成17年10月31日(2005.10.31)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを管理するための方法であって、
マルチノードデータベースシステムの複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記永続的な記憶は、マルチノードデータベースシステムによって使用される複数の永続的な記憶の第１の永続的な記憶であり、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目に関する演算を実行するように前記特定のノードに演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードからの別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように、前記他のノードに演算を転送し、前記方法はさらに、
前記第１の永続的な記憶へのアクセスを有する第１のノードから、第２の永続的な記憶へのアクセスを有するものの前記第１の永続的な記憶へのアクセスを有さない第２のノードに第２のデータ項目の所有権を再割当するステップを含み、
前記第２のデータ項目の所有権を再割当するステップは、前記第１の永続的な記憶から前記第２の永続的な記憶に第２のデータ項目を移動するステップを含む、方法。
【請求項２】
データを管理するための方法であって、マルチノードデータベース内の複数のノードに
とってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置において記憶される特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに前記演算を転送し、前記方法はさらに、
前記特定のノードが作動し続け、かつ、前記マルチノードデータベースシステムから前記特定のノードが除去されることを見越す間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップと、
前記マルチノードデータベースシステムから前記特定のノードが除去されることを見越して、前記特定のノードから前記永続的な記憶へのアクセスを有さない前記マルチノードデータベースシステムのノードに再割当された第２のデータ項目を、前記永続的な記憶から別の永続的な記憶に物理的に移動するステップとを含み、
再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在している時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに演算を転送する、方法。
【請求項３】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップは、前記特定のノードから１つ以上の他のノードへのデータ項目の所有権の段階的な転送の一部として実行され、
再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに演算を転送する、方法。
【請求項４】
前記特定のノードから別のノードに特定のデータ項目の所有権を再割当する前記ステップは、前記複数のノード間で共有される所有権のマップを更新するステップを含む、請求項３に記載の方法。
【請求項５】
前記複数のノードは、マルチノードデータベースシステムのノードである、請求項３に記載の方法。
【請求項６】
前記マルチノードデータベースシステムは、前記永続的な記憶へのアクセスを有さないノードを含む、請求項５に記載の方法。
【請求項７】
前記特定のノードから別のノードに特定のデータ項目の所有権を再割当するステップは、前記他のノードを前記マルチノードデータベースシステムに追加することに応じて実行される、請求項５に記載の方法。
【請求項８】
前記段階的な転送は、前記特定のノードが前記マルチノードデータベースシステム内の１つ以上の他のノードに比べて酷使されていると検出されることに応じて開始される、請求項３に記載の方法。
【請求項９】
前記段階的な転送は、前記特定のノードが、前記マルチノードデータベースシステムの１つ以上の他のノードに比べてもはや酷使されていないと検出されることに応じて終了される、請求項８に記載の方法。
【請求項１０】
データ項目の所有権の前記段階的な転送は、
所有権が転送されるべき前記特定のノードにより所有される一組のデータ項目を識別するステップと、
前記特定のノードからの所有権の転送に関して識別された１つ以上の他のデータ項目の所有権の転送が完了する前に、前記他のノードに対し、前記識別されたデータ項目の１つ以上を利用可能にするステップとを含む、請求項３に記載の方法。
【請求項１１】
データを管理するための方法であって、
マルチノードシステム内の複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、１つ以上の他のノードによる、前記他のノードへの所有権の段階的な転送の一部として実行され、前記段階的な転送は、前記他のノードが前記マルチノードシステム内の１つ以上の他のノードに比べて十分に使用されていないと検出されることに応じて開始され、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに演算を転送する、方法。
【請求項１２】
データを管理するための方法であって、
マルチノードシステム内の複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに演算を転送し、前記方法はさらに、
前記マルチノードシステムから第１のノードが除去された後に、一組のデータ項目が前記第１のノードによって継続して所有されるようにするステップと、
前記データ項目を必要とする演算の要求を検出することに応じて、前記第１のノードから１つ以上の他のノードにデータ項目の所有権を再割当するステップとを含む、方法。
【請求項１３】
データを管理するための方法であって、
マルチノードシステム内の複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに前記演算を転送し、前記方法はさらに、
前記マルチノードシステムから第１のノードが除去された後に、一組のデータ項目が第１のノードにより継続して所有されるようにするステップと、
第２のノードの作業負荷が予め定められたしきい値よりも下がったことが検出されたことに応じて、前記第１のノードから前記第２のノードにデータ項目の所有権を再割当するステップとを含む、方法。
【請求項１４】
前記特定のデータ項目が前記他のノードに再割当されるべき時に、特定のノードは、揮発性メモリに前記特定のデータ項目のダーティなバージョンを記憶し、
前記特定のノードから別のノードに特定のデータ項目の所有権を再割当するステップは、前記特定のデータ項目の前記ダーティなバージョンを前記永続的な記憶に書込むステップを含む、請求項１３に記載の方法。
【請求項１５】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを前記望むノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、前記特定のデータ項目が前記他のノードに再割当されるべき時に、前記特定のノードは揮発性メモリに前記特定のデータ項目のダーティなバージョンを記憶し、所有権を再割当する前記ステップは、
永続的な記憶に対し、前記ダーティなバージョンに関連する１つ以上の再実行記録を強制するステップと、
前記特定のデータ項目の前記ダーティなバージョンを前記永続的な記憶に書込むことなく前記揮発性メモリから前記ダーティなバージョンを一掃するステップとを含み、
前記他のノードは、前記永続的な記憶に存在する前記特定のデータ項目のバージョンに前記１つ以上の再実行記録を適用することにより、前記ダーティなバージョンを再構築し、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに演算を転送する、方法。
【請求項１６】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶される特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが特定のデータ項目についての演算を実行するように特定のノードに演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から特定のデータ項目を移動することなく特定のノードから別のノードに特定のデータ項目の所有権を再割当するステップを含み、前記特定のデータ項目が前記他のノードに再割当されるべき時に、前記特定のノードは揮発性メモリに前記特定のデータ項目のダーティなバージョンを記憶し、前記方法はさらに、
前記特定のノードに関連する揮発性メモリから前記他のノードに関連する揮発性メモリに前記特定のデータ項目のダーティなバージョンを転送するステップを含み、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが特定のデータ項目についての前記演算を実行するように前記他のノードに演算を転送する、方法。
【請求項１７】
前記ダーティなバージョンを転送する前記ステップは、他のノードが前記ダーティなバージョンを要求することなく、前記特定のノードにより事前対応の態様で実行される、請求項１６に記載の方法。
【請求項１８】
前記ダーティなバージョンを転送する前記ステップは、前記他のノードからの前記ダーティなバージョンの要求に応じて前記特定のノードにより実行される、請求項１６に記載の方法。
【請求項１９】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが特定のデータ項目についての演算を実行するように特定のノードに前記演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく、かつ、前記データ項目を変更するトランザクションがコミットするのを待つことなく、前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、前記特定のデータ項目が前記特定のノードによって所有されている間に前記トランザクションは第１の組の変更を行ない、前記特定のデータ項目が前記他のノードによって所有されている間に前記トランザクションは第２の組の変更を行ない、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての前記演算を実行するように前記他のノードに前記演算を転送する、方法。
【請求項２０】
前記他のノードに関連する取消しログ内の取消し記録に基づいて前記第２の組の変更をロールバックすること、および、前記特定のノードに関連する取消しログ内の取消し記録に基づいて前記第１の組の変更をロールバックすることにより、前記トランザクションによって行なわれた変更をロールバックするステップをさらに含む、請求項１９に記載の方法。
【請求項２１】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての前記演算を実行するように前記特定のノードに前記演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデー
タ項目の所有権を再割当するステップを含み、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに演算を転送し、前記方法はさらに、
前記他のノードが前記データ項目を更新する要求を受信するステップと、
前記要求を受信したことに応じて、前記特定のノードがデータ項目への専有モードのアクセスまたは共有モードのアクセスのいずれを保持していたかを判断するステップと、
前記特定のノードがデータ項目への専有モードのアクセスまたは共有モードのアクセスを保持していなかった場合に、特定のノードがデータ項目のいずれかのダーティなバージョンまたはダーティなバージョンに対する再実行を永続的な記憶にフラッシュするのを待たずに、前記他のノードが前記特定のデータ項目を更新するステップとを含む、方法。
【請求項２２】
前記他のノードに前記特定のデータ項目の所有権を転送することに応じて、前記特定のデータ項目を必要とする進行中の演算を中止するステップと、
前記特定のデータ項目の所有権が前記特定のノードに転送された後に、前記進行中の演算を自動的に再実行するステップとをさらに含む、請求項２１に記載の方法。
【請求項２３】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに前記演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、前記特定のデータ項目を必要とする演算は、前記特定のデータ項目の所有権の転送が実行されるべき時に進行中であり、前記方法はさらに、
一組の１つ以上の因子に基づいて、前記進行中の演算が完了するのを待つかどうかを判断するステップと、
前記進行中の演算が完了するのを待たないと判断された場合に、前記進行中の演算を中止するステップとを含み、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに演算を転送する、方法。
【請求項２４】
前記組の１つ以上の因子は、前記進行中の演算によってどれだけの仕事が既に実行されたかを含む、請求項２３に記載の方法。
【請求項２５】
データを管理する方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、１つ以上のパーティションを含むテーブル内の行であり、前記１つ以上のパーティションの少なくとも１つは、第１の永続的
なデータ項目および第２の永続的なデータ項目を含み、前記方法はさらに、
複数のバケットの１つに各データ項目を割当てることにより、前記ノードの１つに、前記永続的なデータ項目の各々の所有権を割当てるステップを含み、
前記第１の永続的なデータ項目は第１のバケットに割当てられ、前記第２の永続的なデータ項目は第２のバケットに割当てられ、前記第１のバケットは前記第２のバケットとは異なり、前記方法はさらに、
前記複数のノードの１つに各バケットを割当てるステップを含み、
バケットが割当てられた前記ノードは、前記バケットに割当てられたすべてのデータ項目の所有者であるものと確認され、
第１のノードが、第２のノードにより所有されるデータ項目を必要とする演算が実行されることを望むと、前記第１のノードは、前記第２のノードが前記演算を実行するように前記第２のノードに前記演算を転送する、方法。
【請求項２６】
複数のバケットの１つに各データ項目を割当てる前記ステップは、各データ項目に関連する名前にハッシュ関数を適用することによって実行される、請求項２５に記載の方法。
【請求項２７】
前記複数のノードの１つに各バケットを割当てる前記ステップは、各バケットに関連する識別子にハッシュ関数を適用することによって実行される、請求項２５に記載の方法。
【請求項２８】
複数のバケットの１つに各データ項目を割当てる前記ステップは、範囲ベースのセグメント化を用いて実行される、請求項２５に記載の方法。
【請求項２９】
複数のノードの１つに各バケットを割当てる前記ステップは、範囲ベースのセグメント化を用いて実行される、請求項２５に記載の方法。
【請求項３０】
複数のバケットの１つに各データ項目を割当てる前記ステップは、データ項目−バケット間の個々の関係を列挙することによって実行される、請求項２５に記載の方法。
【請求項３１】
複数のノードの１つに各バケットを割当てる前記ステップは、バケット−ノード間の個々の関係を列挙することによって実行される、請求項２５に記載の方法。
【請求項３２】
バケットの数は、ノードの数よりも大きく、バケット−ノード間の関係は、多対一の関係である、請求項２５に記載の方法。
【請求項３３】
データ項目−バケット間のマッピングを変更することなくバケット−ノード間のマッピングを変更することにより、バケットにマッピングされたすべてのデータ項目の所有権を第１のノードから第２のノードに再割当するステップをさらに含む、請求項２５に記載の方法。
【請求項３４】
前記第１のバケットを異なるノードに割当てるステップをさらに含む、請求項２５に記載の方法。
【請求項３５】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１〜３４のいずれかに記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【手続補正書】
【提出日】平成18年3月28日(2006.3.28)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データを管理するための方法であって、
マルチノードシステム内の複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置に記憶された特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目に関する演算を実行するように前記特定のノードに前記演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードからの別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、
前記再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、他のノードが前記特定のデータ項目についての演算を実行するように、前記他のノードに前記演算を転送し、前記方法はさらに、
前記マルチノードシステムから第１のノードが除去された後に、一組のデータ項目が前記第１のノードによって継続して所有されるようにするステップと、
前記データ項目を必要とする演算の要求を検出することに応じて、前記第１のノードから１つ以上の他のノードにデータ項目の所有権を再割当するステップとを含む、方法。
【請求項２】
データを管理するための方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、前記永続的な記憶上の特定の位置において記憶される特定のデータ項目を含み、前記方法はさらに、
前記ノードの１つに、前記永続的なデータ項目の各々の排他的な所有権を割当てるステ
ップを含み、前記複数のノードの特定のノードには、前記特定のデータ項目の排他的な所有権が割当てられ、
いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在する時に、前記特定のノードが前記特定のデータ項目についての演算を実行するように前記特定のノードに前記演算を転送し、前記方法はさらに、
前記特定のノードが作動し続ける間に、前記永続的な記憶上の前記特定の位置から前記特定のデータ項目を移動することなく前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当するステップを含み、前記特定のデータ項目が前記他のノードに再割当されるべき時に、前記特定のノードは揮発性メモリに前記特定のデータ項目のダーティなバージョンを記憶し、所有権を再割当する前記ステップは、
永続的な記憶に対し、前記ダーティなバージョンに関連する１つ以上の再実行記録を強制するステップを含み、
再割当の後に、いずれかのノードが前記特定のデータ項目を必要とする演算が実行されることを望むと、前記演算が実行されることを望む前記ノードは、前記特定のデータ項目が前記特定の位置に存在している時に、他のノードが前記特定のデータ項目についての演算を実行するように前記他のノードに前記演算を転送する、方法。
【請求項３】
データを管理する方法であって、
複数のノードにとってアクセス可能な永続的な記憶上に複数の永続的なデータ項目を保存するステップを含み、前記永続的なデータ項目は、１つ以上のパーティションを含むテーブル内の行であり、前記１つ以上のパーティションの少なくとも１つは、第１の永続的なデータ項目および第２の永続的なデータ項目を含み、前記方法はさらに、
複数のバケットの１つに各データ項目を割当てるステップ、および前記複数のノードの１つに各バケットを割当てるステップにより、前記ノードの１つに、前記永続的なデータ項目の各々の所有権を割当てるステップを含み、前記第１の永続的なデータ項目は第１のバケットに割当てられ、前記第２の永続的なデータ項目は第２のバケットに割当てられ、前記第１のバケットは前記第２のバケットとは異なり、
バケットが割当てられた前記ノードは、前記バケットに割当てられたすべてのデータ項目の所有者であるものと確認され、
第１のノードが、第２のノードにより所有されるデータ項目を必要とする演算が実行されることを望むと、前記第１のノードは、前記第２のノードが前記演算を実行するように前記第２のノードに前記演算を転送する、方法。
【請求項４】
複数のバケットの１つに各データ項目を割当てる前記ステップは、各データ項目に関連する名前にハッシュ関数を適用することによって実行される、請求項３に記載の方法。
【請求項５】
前記複数のノードの１つに各バケットを割当てる前記ステップは、各バケットに関連する識別子にハッシュ関数を適用することによって実行される、請求項３に記載の方法。
【請求項６】
複数のバケットの１つに各データ項目を割当てる前記ステップは、範囲ベースのセグメント化を用いて実行される、請求項３に記載の方法。
【請求項７】
前記複数のノードの１つに各バケットを割当てる前記ステップは、範囲ベースのセグメント化を用いて実行される、請求項３に記載の方法。
【請求項８】
複数のバケットの１つに各データ項目を割当てる前記ステップは、データ項目−バケット間の個々の関係を列挙することによって実行される、請求項３に記載の方法。
【請求項９】
前記複数のノードの１つに各バケットを割当てる前記ステップは、バケット−ノード間
の個々の関係を列挙することによって実行される、請求項３に記載の方法。
【請求項１０】
バケットの数は、ノードの数よりも大きく、バケット−ノード間の関係は、多対一の関係である、請求項３に記載の方法。
【請求項１１】
データ項目−バケット間のマッピングを変更することなくバケット−ノード間のマッピングを変更することにより、バケットにマッピングされたすべてのデータ項目の所有権を第１のノードから第２のノードに再割当するステップをさらに含む、請求項３に記載の方法。
【請求項１２】
前記第１のバケットを異なるノードに割当てるステップをさらに含む、請求項３に記載の方法。
【請求項１３】
前記特定のデータ項目の前記ダーティなバージョンを前記永続的な記憶に書込むことなく前記揮発性メモリから前記ダーティなバージョンを一掃するステップをさらに含む、請求項２に記載の方法。
【請求項１４】
前記他のノードは、前記永続的な記憶に存在する前記特定のデータ項目のバージョンに前記１つ以上の再実行記録を適用することにより、前記ダーティなバージョンを再構築する、請求項１３に記載の方法。
【請求項１５】
前記他のノードは、前記永続的な記憶に存在する前記特定のデータ項目のバージョンに前記１つ以上の再実行記録を適用することにより、前記ダーティなバージョンを再構築する、請求項２に記載の方法。
【請求項１６】
前記特定のノードに関連する揮発性メモリから前記他のノードに関連する揮発性メモリに前記特定のデータ項目の前記ダーティなバージョンを転送するステップをさらに含む、請求項２に記載の方法。
【請求項１７】
前記ダーティなバージョンを転送する前記ステップは、前記他のノードが前記ダーティなバージョンを要求することなく、前記特定のノードにより事前対応の態様で実行される、請求項１６に記載の方法。
【請求項１８】
前記ダーティなバージョンを転送する前記ステップは、前記他のノードからの前記ダーティなバージョンの要求に応じて前記特定のノードにより実行される、請求項１６に記載の方法。
【請求項１９】
前記特定のノードから別のノードに前記特定のデータ項目の所有権を再割当する前記ステップは、前記特定のノードから１つ以上の他のノードへのデータ項目の所有権の段階的な転送の一部として実行される、請求項２に記載の方法。
【請求項２０】
前記段階的な転送は、前記他のノードが前記マルチノードデータベースシステム内の１つ以上の他のノードに比べて十分に使用されていないと検出されることに応じて開始される、請求項１９に記載の方法。
【請求項２１】
前記段階的な転送は、前記特定のノードが、前記マルチノードデータベースシステムの１つ以上の他のノードに比べてもはや酷使されていないと検出されることに応じて終了される、請求項２０に記載の方法。
【請求項２２】
前記特定のデータ項目の所有権を再割当する前記ステップは、前記特定のデータ項目を
変更するトランザクションがコミットするのを待つことなく実行される、請求項２に記載の方法。
【請求項２３】
前記特定のデータ項目が前記特定のノードによって所有されている間に前記トランザクションは第１の組の変更を行ない、前記特定のデータ項目が前記他のノードによって所有されている間に前記トランザクションは第２の組の変更を行なう、請求項２２に記載の方法。
【請求項２４】
前記他のノードに関連する取消しログ内の取消し記録に基づいて前記第２の組の変更をロールバックすること、および、前記特定のノードに関連する取消しログ内の取消し記録に基づいて前記第１の組の変更をロールバックすることにより、前記トランザクションによって行なわれた変更をロールバックするステップをさらに含む、請求項２３に記載の方法。
【請求項２５】
前記他のノードが、前記データ項目を更新する要求を受信するステップと、
前記要求を受信したことに応じて、前記特定のノードが前記特定のデータ項目への専有モードのアクセスまたは共有モードのアクセスのいずれを保持していたかを判断するステップと、
前記特定のノードが前記特定のデータ項目への専有モードのアクセスまたは共有モードのアクセスを保持していなかった場合に、前記特定のノードが前記特定のデータ項目のいずれかのダーティなバージョンまたは前記ダーティなバージョンに対する再実行を永続的な記憶にフラッシュするのを待たずに、前記他のノードが前記特定のデータ項目を更新するステップとをさらに含む、請求項２に記載の方法。
【請求項２６】
前記他のノードに前記特定のデータ項目の所有権を転送することに応じて、前記特定のデータ項目を必要とする進行中の演算を中止するステップと、
前記特定のデータ項目の所有権が前記他のノードに転送された後に、前記進行中の演算を自動的に再実行するステップとをさらに含む、請求項２５に記載の方法。
【請求項２７】
１つ以上のプロセッサによって実行されると、前記１つ以上のプロセッサに請求項１〜２６のいずれかに記載の方法を実行させる命令の１つ以上のシーケンスを搬送する、コンピュータ読取可能な媒体。
【国際調査報告】
2007501457.tif 000005
2007501457.tif 000006
2007501457.tif 000007