誇張ではなく、絶対にそうはならない

01. はじめに

データのクエリ速度を向上させるために、キャッシュがよく使用されます。キャッシュ容量には制限があるため、キャッシュ容量が上限に達すると、新しいデータを追加できるように、一部のデータを削除してスペースを確保する必要があります。キャッシュされたデータはランダムに削除することはできません。一般的に、特定のアルゴリズムに基づいてキャッシュされたデータを削除する必要があります。一般的な除去アルゴリズムには、LRU、LFU、FIFO などがあります。この記事では、LRU アルゴリズムについて説明します。

02. LRUの紹介

LRU は Least Recently Used の略です。このアルゴリズムでは、最も最近使用されたデータはホット データであり、次回も高い確率で再び使用されるとみなされます。最近ほとんど使用されていないデータは、次回も使用されなくなる可能性があります。キャッシュ容量がいっぱいになると、最近あまり使用されていないデータが最初に削除されます。

キャッシュの内部データが以下のようになっていると仮定します。

ここでは、リストの最初のノードをヘッド ノード、最後のノードをテール ノードと呼びます。

キャッシュを呼び出してキー = 1 のデータを取得する場合、図に示すように、LRU アルゴリズムはノード 1 をヘッド ノードに移動する必要があり、他のノードは変更されません。

次にkey=8のノードを挿入します。このときキャッシュ容量が上限に達しているため、追加する前にデータを削除する必要があります。各クエリはデータをヘッド ノードに移動するため、クエリされていないデータはテール ノードに移動します。テールのデータは最もアクセスが少ないデータであると考えられるため、テール ノードのデータは削除されます。

次に、データをヘッドノードに直接追加します。

LRU アルゴリズムの具体的な手順の概要は次のとおりです。

• 新しいデータはリストの先頭に直接挿入されます
• キャッシュデータがヒットし、データがリストの先頭に移動される
• キャッシュがいっぱいになったら、リストの末尾にあるデータを削除します。

03. LRUアルゴリズムの実装

上記の例からわかるように、LRU アルゴリズムではヘッド ノードを追加し、テール ノードを削除する必要があります。リンクリスト内のノードの追加/削除の時間計算量は O(1) であるため、ストレージ キャッシュ データ コンテナーとして非常に適しています。ただし、通常の一方向リンク リストは使用できません。一方向リンク リストには、いくつかの欠点があります。

1. 任意のノードからデータを取得するたびに、最初のノードからトラバースする必要があり、その結果、ノードを取得する複雑さは O(N) になります。
2. 中間ノードをヘッドノードに移動するには、中間ノードの前のノードの情報を知る必要があるため、一方向リンクリストを再度走査して情報を取得する必要があります。

上記の問題は、他のデータ構造を組み合わせることで解決できます。

ハッシュテーブルを使用してノードを格納すると、ノードを取得する複雑さは O(1) に削減されます。ノード移動の問題は、前のノード情報を記録するための先行ポインタをノードに追加することで解決できます。これにより、リンク リストが一方向リンク リストから双方向リンク リストに変更されます。

要約すると、図に二重リンクリストとハッシュテーブルの組み合わせを使用したデータ構造が示されています。

2 つの「センチネル」ノードは双方向リンク リストに意図的に追加されており、データの保存には使用されません。センチネル ノードを使用すると、ノードを追加/削除するときに境界ノードが存在しないかどうかを考慮する必要がなくなり、プログラミングの難易度が軽減され、コードの複雑さが軽減されます。

LRU アルゴリズムの実装コードは次のとおりです。簡略化のため、key と val は両方とも int 型とみなされます。

パブリッククラスLRUCache { 
 
 エントリーヘッド、テール;
 int容量;
整数 サイズ;
 マップキャッシュ; 
 
 
パブリックLRUCache( int容量) {
 this.capacity = 容量;
 // リンクリストを初期化する
 リンクリストを初期化します。
サイズ= 0;
 キャッシュ = 新しい HashMap<>(容量 + 2);
 } 
 
 /**
 * ノードが存在しない場合は -1 を返します。存在する場合は、ノードをヘッド ノードに移動し、ノードのデータを返します。
 *
 * @paramキー 
 * @戻る 
 */
公共  int get( int  鍵） {
 エントリノード = cache.get( key );
 if (ノード == null ) {
 -1 を返します。
 }
 // モバイルノードがあります
 ノードを先頭に移動します。
ノード値を返します。
 } 
 
 /**
 * ヘッドノードにノードを追加します。容量がいっぱいになると、テールノードは削除されます。
 *
 * @paramキー 
 * @パラメータ値
 */
パブリックvoid put( int  キー、 int値）{
 エントリノード = cache.get( key );
 if (ノード ​​!= null ) {
 ノードの値 = 値;
 ノードを先頭に移動します。
戻る;
 }
 // 存在しません。最初に追加し、その後末尾のノードを削除します
 // この時点で容量がいっぱいなので、末尾のノードを削除します
 if (サイズ== 容量 ) {
 エントリ lastNode = tail.pre;
 最後のノードを削除します。
 cache.remove( lastNode.key );
サイズ- ;  
 }
 // ヘッドノードを追加する
 
 エントリ newNode = new Entry();
 newNode.key =キー;
 新しいノードの値 = 値;
 ノードを追加します(新しいノード)。
 cache.put(キー、newNode);
サイズ++; 
 
 } 
 
 プライベート void moveToHead(エントリノード) {
 // まず元のノードの関係を削除します
 ノードを削除します。
 ノードを追加します。
 } 
 
 プライベート void addNode(エントリノード) {
 ノードを次のノードにドラッグします。
 ノードの次=ヘッドの次; 
 
 ノードの先頭に、
 ノードを次に示します。
 } 
 
 プライベート void deleteNode(エントリノード) {
 ノードのpre.next =ノードのnext ;
 ノードを次のノードにリンクします。
 } 
 
 
公共 静的クラスエントリ{
公開エントリー事前;
公開エントリ次へ;
公共 整数 鍵;
公共  int値; 
 
パブリックエントリ( int  キー、 int値）{
 this.key =キー;
 this.value = 値;
 } 
 
パブリックエントリ() {
 }
 } 
 
 プライベートvoid initLinkedList() {
 head = 新しいエントリ();
 tail = 新しいエントリ(); 
 
 ヘッドの次= テール;
 tail.pre = ヘッド; 
 
 } 
 
公共 静的void main(String[] args) { 
 
 LRUCache キャッシュ = 新しい LRUCache(2); 
 
 キャッシュに1をセットします。
 キャッシュにデータを格納する。
 System.out.println (cache.get(1)) ;
 キャッシュにデータを格納する。
 System.out.println (cache.get(2)) ; 
 
 }
 }

04. LRUアルゴリズムの分析

キャッシュ ヒット率は、キャッシュ システムの非常に重要な指標です。キャッシュ システムのキャッシュ ヒット率が低すぎると、クエリがデータベースに逆流し、データベースにかかる負荷が増加します。

上記の分析と組み合わせると、LRU アルゴリズムの長所と短所がわかります。

LRU アルゴリズムの利点は、実装が難しくなく、ホット データの場合、LRU 効率が非常に優れていることです。

LRU アルゴリズムの欠点は、履歴データのバッチ クエリなどの不定期のバッチ操作では、キャッシュ内の人気データがこれらの履歴データに置き換えられ、キャッシュ汚染が発生し、キャッシュ ヒット率が低下し、通常のデータ クエリが遅くなる可能性があることです。

05. LRUアルゴリズムの改善

以下のソリューションはMySQL InnoDB LRU改良アルゴリズムから派生したものである。

図に示すように、リンク リストをホット データ領域とコールド データ領域の 2 つの部分に分割します。

改善後、アルゴリズムのフローは次のようになります。

1. アクセスされたデータがホット データ領域にある場合、以前の LRU アルゴリズムと同様に、ホット データ領域のヘッド ノードに移動されます。
2. データを挿入するときに、キャッシュがいっぱいの場合は、末尾のノードにあるデータを削除します。次に、コールド データ領域のヘッド ノードにデータを挿入します。
3. コールド データ領域のデータにアクセスするたびに、次の判断を行う必要があります。
4. データが指定された時間（1 秒など）を超えてキャッシュ内に保持されている場合、そのデータはホット データ領域のヘッド ノードに移動されます。
5. データが指定された時間より前の時間に存在する場合、位置は変更されません。

時々実行されるバッチ クエリの場合、データは単にコールド データ領域に送られ、すぐに削除されます。よく使用されるデータ領域のデータは影響を受けないため、LRU アルゴリズムのキャッシュ ヒット率が低下する問題が解決されます。

その他の改良された方法には、LRU-K、2Q、LIRS アルゴリズムなどがあります。興味のある学生はぜひチェックしてみてください。