キャッシュ除去アルゴリズムLRU実装原理についてお話しましょう

[[315530]]

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 型とみなされます。

 public class LRUCache { Entry head, tail; int capacity; int size; Map<Integer, Entry> cache; public LRUCache(int capacity) { this.capacity = capacity; // 初始化链表initLinkedList(); size = 0; cache = new HashMap<>(capacity + 2); } /** * 如果节点不存在，返回-1.如果存在，将节点移动到头结点，并返回节点的数据。 * * @param key * @return */ public int get(int key) { Entry node = cache.get(key); if (node == null) { return -1; } // 存在移动节点moveToHead(node); return node.value; } /** * 将节点加入到头结点，如果容量已满，将会删除尾结点* * @param key * @param value */ public void put(int key, int value) { Entry node = cache.get(key); if (node != null) { node.value = value; moveToHead(node); return; } // 不存在。先加进去，再移除尾结点// 此时容量已满删除尾结点if (size == capacity) { Entry lastNode = tail.pre; deleteNode(lastNode); cache.remove(lastNode.key); size--; } // 加入头结点Entry newNode = new Entry(); newNode.key = key; newNode.value = value; addNode(newNode); cache.put(key, newNode); size++; } private void moveToHead(Entry node) { // 首先删除原来节点的关系deleteNode(node); addNode(node); } private void addNode(Entry node) { head.next.pre = node; node.next = head.next; node.pre = head; head.next = node; } private void deleteNode(Entry node) { node.pre.next = node.next; node.next.pre = node.pre; } public static class Entry { public Entry pre; public Entry next; public int key; public int value; public Entry(int key, int value) { this.key = key; this.value = value; } public Entry() { } } private void initLinkedList() { head = new Entry(); tail = new Entry(); head.next = tail; tail.pre = head; } public static void main(String[] args) { LRUCache cache = new LRUCache(2); cache.put(1, 1); cache.put(2, 2); System.out.println(cache.get(1)); cache.put(3, 3); System.out.println(cache.get(2)); }}

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

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

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

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

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

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

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

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

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

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

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

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