Oracle データベース LRU アルゴリズムの詳細な説明 - LRU チェーン、ダーティ ブロック、ダーティ LRU チェーン

[[326308]]

概要

いわゆる LRU (Least Recently Used) アルゴリズムの基本的な概念は、メモリの残りの使用可能スペースが不十分な場合、バッファはユーザーが最も頻繁に使用するデータを最初に保持しようとすることです。つまり、「あまり使用されないデータ」をクリアしてスペースを解放することを優先します。「あまり使用されないデータ」が引用符で囲まれているのは、ここでのいわゆるあまり使用されないデータの判断基準が人為的であり、厳密ではないためです。いわゆる MRU (Most Recently Used) アルゴリズムは、LRU アルゴリズムの正反対です。

Oracle は、高速バッファの動作メカニズムにこのアルゴリズムを使用しています。一緒に見てみましょう。

LRU チェーン:

キャッシュのサイズには制限があり、キャッシュされるデータよりも常に小さくなります。バッファ キャッシュがデータ ファイルをキャッシュするために使用されるのと同様に、データ ファイルのサイズはバッファ キャッシュよりもはるかに大きくなります。

したがって、キャッシュは常にいっぱいになります。キャッシュ内に空きメモリ ブロックがない場合、新しいデータをキャッシュに入れる必要があると、キャッシュ内の元のデータからのみ犠牲データが選択され、その犠牲データはキャッシュに入る新しいデータで上書きされます。この犠牲者の選択は非常に重要です。キャッシュの目的はデータの再利用を可能にすることなので、通常はキャッシュ内で再利用される可能性が最も低いブロックが対象として選択されます。犠牲者の選択は、CPU の L1 および L2 キャッシュから共有プールおよびバッファ キャッシュ プールまで、ほとんどのキャッシュ プールは有名な LRU アルゴリズムを使用しますが、Oracle では、改良された LRU アルゴリズムを使用します。具体的なアルゴリズムは発表されていないが、LRU アルゴリズムの全体的な目的は「最も最近アクセスされていない」ことであり、これは現在から最も遠い最後にアクセスされたメモリ ブロックが犠牲として扱われることを意味します。

たとえば、A、B、C という 3 つのメモリ ブロックがあるとします。A は 10 回アクセスされており、最終アクセスは 10:20 です。B は 15 回アクセスされており、最終アクセスは 10:18 です。C も 10 回アクセスされており、最終アクセスは 10:22 です。被害者を選ぶ段階になると、B が最も多く訪問されているため、間違いなく被害者ではありません。 A と C の訪問回数は同じですが、A は 10:20 に訪問され、C は 10:22 に訪問されました。A の方が先に訪問されたため、A が被害者です。

LRU 機能を実装するために、Oracle はバッファ キャッシュに LRU リンク リストを作成します。Oracle は、バッファ キャッシュ内のすべてのメモリ ブロックをアクセス回数とアクセス時間に基づいてソートし、リンク リストに並べます。リンク リストの 2 つの端は、以下に示すように、ホット エンドとコールド エンドと呼ばれます。

ブロックに初めてアクセスするときに、そのブロックがバッファ キャッシュ内にない場合、Oracle はそれをバッファ キャッシュに読み込むことを選択します。バッファ キャッシュ内で犠牲者を選択する場合、Oracle はコールド エンドから開始します。上記の例では、メモリ ブロック U が犠牲者になります。

上記のように、新しいブロックが U に読み込まれ、U の元の内容が上書きされます。ここでは、新しいブロックが V であると仮定します。しかし、ブロック V はコールド エンドには配置されません。コールド エンドのブロックは犠牲権としてすぐにカバーされるためです。これは、「最終アクセス時間が最も遠いブロックを犠牲として取得する」という原則に準拠していません。ブロック V は、最後の時間が現在の瞬間に最も近いブロックであり、次の犠牲者になるべきではありません。 Oracle が LRU をどのように実験するかを引き続き見てみましょう。

Oracle は LRU チェーンを中央から 2 つに分割し、一方の半分はホット エンド ブロックを記録し、もう一方の半分はコールド エンド ブロックを記録します。上記のように、アクセスされたブロック V は次のようになります。

新しいブロックがバッファ キャッシュに入ると、たとえばブロック X がバッファ キャッシュに読み込まれると、以下に示すように、ブロック T が上書きされ、ブロック V の前に移動されます。

このように続けると、一番右のコールド エンドにあるブロックは、最終アクセス時刻が現在から最も遠いブロックになるはずです。したがって、何度もアクセスされるブロックは犠牲者として選択されません。Oracle はどのようにしてこれを実現するのでしょうか。これは非常に簡単です。Oracle は通常、2 回を基準としています。ブロックが 2 回以上アクセスされると、ホット エンドに入る機会があります。

Oracle は、メモリ内の各ブロックへのアクセス回数を記録するためのフラグを追加します。図の各ブロックへのアクセス回数が次のとおりであると仮定します。

新しいブロックをバッファ キャッシュに読み込む場合、Oracle はコールド エンドから犠牲者を探し始めます。コールド エンドの最初のブロック S のアクセス回数は 2 なので、上書きできません。アクセス回数が 2 以上であれば、Oracle は頻繁にアクセスされる可能性があると判断します。Oracle はそれをホット エンドに移動し、今度は犠牲者として R を選択します。

ブロック S はコールド エンドからホット エンドに移動され、アクセス カウントはゼロにリセットされます。この時点では、ブロック R は 2 回未満しかアクセスされていないため、被害を受けています。

新しいブロック Y はブロック R を上書きし、コールド エンド ブロックの先頭に移動され、そのアクセス カウントは 1 になります。ブロック Y にもう一度アクセスすると、アクセス回数は 2 になります。

Y は 2 回アクセスされていますが、すぐにホット エンドに移動されるわけではありません。元の位置に残ります。新しいブロックが追加され、その前に挿入されると、Y は後方に押し出され続けます。

上の図に示すように、多くの新しいブロックが追加され、Y はコールド エンドにプッシュされます。新しいブロックがバッファ キャッシュに入ると、Y は犠牲にはなりません。ホット エンド S の前に移動されます。Y の後ろにある Z は、アクセス回数が 2 に達しない場合、犠牲になります。

上記は、Oracle におけるバッファ キャッシュ管理 LRU の原理です。このように動作することで、Oracle は頻繁に使用されるブロックをバッファ キャッシュにできるだけ長く保持できます。さらに、新しいブロックがバッファ キャッシュに入るたびに、Oracle はコールド エンドから右から左へ被害者ブロックを検索します。コールド エンドに近づくほど、ブロックへのアクセス回数が少なくなり、最終アクセス時刻が現在から最も遠くなるためです。

ダーティ ブロックとダーティ LRU チェーン:

Oracle でブロックを変更する場合のルールは、バッファ キャッシュ内のブロックのみを変更し、ディスク上のブロックを直接変更しないことです。変更するブロックがバッファ キャッシュにない場合、Oracle はまずそのブロックをバッファ キャッシュに読み込み、次にバッファ キャッシュ内で変更します。

バッファ キャッシュ内のブロックが変更されると、Oracle はそれを「ダーティ」ブロックとしてマークします。ダーティ ブロックには、ユーザーによって変更されたダーティ データが含まれます。 Oracle は定期的にダーティ ブロックをディスクに書き込みます。ダーティ ブロックをディスクに書き込む役割を担う特別なバックグラウンド プロセスが DBWn です。また、DBWn がダーティ ブロックをディスクに書き込むプロセスを、ダーティ ブロックをリフレッシュするプロセスとも呼びます。リフレッシュ後、ダーティ ブロックはダーティではなくなり、再びクリーン ブロックになります。実際には、ブロック A が存在します。バッファ キャッシュ内のこのブロックのデータがディスク上のブロックのデータと一致していない場合、このブロックはダーティ ブロックです。それ以外の場合は、クリーンなブロックです。変更が完了すると、Oracle はバッファ キャッシュのみを変更するため、ブロック内のデータはディスクと確実に不整合になり、ブロックはダーティ ブロックになります。ブロックが更新されると、ブロックがディスクに書き込まれるため、ディスク上のブロック データとバッファ キャッシュ内のブロック データが整合し、ブロックは再びクリーンなブロックになります。

ダーティ ブロックがディスクに書き戻される前、つまりダーティ ブロックがまだダーティ ブロックである間は、ダーティ ブロックにはユーザーによって変更されたデータが含まれており、このデータはディスクに書き込まれていないため、上書きできません。この時点でダーティ ブロックが上書きされると、ユーザーの変更結果は失われます。

現在の LRU チェーンが上の図のようになっていると仮定します。ここで、V、L、O、P、Q はダーティ ブロックです。新しいブロックがバッファ キャッシュに入力される直前に、Oracle はコールド エンドから犠牲ブロックの選択を開始します。Q、P、および O はダーティ ブロックであるため、犠牲ブロックとして使用できません。今回は N が犠牲ブロックです。新しく入力されたブロックは N を上書きし、その後、新しいブロックが Y の前に挿入されます。次に、ブロックがバッファ キャッシュに入ると、Oracle はコールド エンドから検索を開始します。また、Q、P、O もチェックし、いずれも上書きできないことが判明した場合は、M を犠牲として決定します。待ってください、O、P、Q を毎回チェックするのは時間の無駄です。Oracle はそれほど愚かではありません。Oracle はダーティ ブロックを格納するためにダーティ LRU チェーンを用意しています。ブロックがダーティになった場合、すぐにダーティ LRU に移動されるわけではありません。Oracle がコールド エンドから開始して対象を探すときにのみ、見つかったダーティ ブロックがダーティ LRU チェーンに移動します。これを行う目的は、次回被害者を探すときにこれらのダーティ ブロックをチェックしないようにすることです。

要約する

LRU チェーンとダーティ LRU チェーンの原理から、Oracle は LRU のコールド エンドで被害者を探す作業に多くの作業を残していることがわかります。ブロックへのアクセス回数が 2 回を超えて増加した場合、LUR チェーン内のブロックの位置は変更されません。ブロックがダーティになった場合、LRU チェーン内のブロックの位置は変更されません。 LRU のコールド エンドから被害者を検索する場合にのみ、見つかったダーティ ブロックがダーティ LRU チェーンに移動され、アクセス時間が 2 回を超えるブロックがホット エンドに挿入されます。これは、Oracle の改良された LRU アルゴリズムです。

アクセス時間が 2 を超えるブロックやダーティ ブロックが多すぎる場合、これらのブロックは上書きできないため、Oracle はそれらを適切な場所に移動する必要があります。このようなブロックの数が LRU 内のブロック総数の 40% を超えると、つまり、LRU チェーンの半分を検索してもカバーする対象が見つからない場合、Oracle は検索を停止し、DBWn を起動してダーティ ブロックを更新します。 DBWn リフレッシュ中の待機は、空きバッファ待機イベントに記録されます。

対象ブロックの検索中にダーティ ブロックが見つかると、Oracle はそれをダーティ LRU チェーンに移動します。ただし、ダーティ LRU チェーン内のダーティ ブロックの数が制限に達すると、DBWn が起動してダーティ ブロックのリフレッシュを開始します。Oracle は、対象ブロックの検索を続行する前に、ダーティ ブロックがリフレッシュされるまで待機する必要があります。この期間中の待機イベントも、検査された空きバッファに記録されます。

つまり、空きバッファ待機イベントが発生する主な理由は、LRU で被害者を見つけるのに時間がかかりすぎることです。この待機イベントが頻繁に発生する場合は、バッファ キャッシュ内にダーティ ブロックが多すぎることを意味します。これは通常、DBWn 書き込み更新速度が遅いことが原因です。