キャッシュ淘汰アルゴリズム-LRUの実現原理について

前言
キャッシュ容量が限られているため、キャッシュ容量が上限に達すると、一部のデータを削除してスペースを移動する必要があり、新しいデータを追加することができます.キャッシュデータはランダムに削除できません.一般的には、あるアルゴリズムに基づいてキャッシュデータを削除する必要があります.よく使われる淘汰アルゴリズムにはLRU,LFU,FIFOがあり,この文章ではLRUアルゴリズムについて述べる.
LRUの概要
LRUはLeast Recently Usedの略で、このアルゴリズムは最近使用されているデータが人気データであり、次の大きな確率で再び使用されると考えている.最近あまり使われていないデータは、次回は使わない確率が高い.キャッシュ容量が満たされると、最近あまり使用されていないデータを優先的に淘汰します.
キャッシュされた内部データが図のように表示されるとします.
ここでは、リストの最初のノードをヘッダノードと呼び、最後のノードをテールノードと呼びます.
キャッシュを呼び出してkey=1のデータを取得する場合、LRUアルゴリズムは、図に示すように、1というノードをヘッダノードに移動する必要があります.
次にkey=8ノードを挿入します.キャッシュ容量が上限に達したので、参加する前にデータを削除する必要があります.クエリーのたびにデータが先頭ノードに移動するため、クエリーされていないデータは末尾ノードに沈み、末尾のデータは最もアクセスされているデータとみなされるため、末尾ノードのデータは削除されます.
次に、データをヘッダノードに直接追加します.
LRUアルゴリズムの具体的な手順をまとめます.

新しいデータはリストヘッダ

に直接挿入される.

キャッシュデータがヒットし、リストヘッダ

にデータが移動する.

キャッシュがいっぱいになったら、リストの末尾のデータを削除します.

LRUアルゴリズム実装
上記の例では、LRUアルゴリズムがヘッダノードを追加し、エンドノードを削除する必要があることがわかります.チェーンテーブルにノードを追加/削除する時間の複雑さO(1)は,ストレージキャッシュデータコンテナとして最適である.しかし、普通の一方向チェーンテーブルは使用できません.一方向チェーンテーブルにはいくつかの劣勢があります.

任意のノードデータを取得するたびに、最初からノードを巡回する必要があり、これにより、取得ノードの複雑さはO(N)となる.

は中間ノードのヘッダノードを移動し、中間ノードの前のノードの情報を知る必要があり、一方向チェーンテーブルは再び情報を取得しなければならない.

以上の問題に対して,他のデータ構造と組み合わせて解決できる.
ハッシュ・テーブル・ストレージ・ノードを使用すると、ノードの取得の複雑さはO(1)に低下します.ノード移動の問題は、ノードに前駆ポインタを追加し、前のノード情報を記録することで、チェーンテーブルが一方向チェーンテーブルから双方向チェーンテーブルに変わります.
総合的に双方向チェーンテーブル分散リスト結合体を使用し、データ構造を図のように示す.
双方向チェーンテーブルにわざわざ2つの「哨兵」ノードを追加し、データを格納するために使用しません.哨兵ノードを使用すると,ノードを追加/削除する際に境界ノードが存在しないことを考慮せずにプログラミングの難易度を簡素化し,コードの複雑さを低減できる.
LRUアルゴリズム実装コードは,keyを簡略化するためにvalはintタイプと考える.

public class LRUCache {

    Entry head, tail;
    int capacity;
    int size;
    Map 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));

    }
}

LRUアルゴリズム解析
キャッシュ・ヒット率は、キャッシュ・システムの非常に重要な指標です.キャッシュ・システムのキャッシュ・ヒット率が低すぎると、クエリーがデータベースに戻り、データベースの圧力が上昇します.
以上の分析LRUアルゴリズムの長所と短所を組み合わせた.
LRUアルゴリズムの利点は、アルゴリズムの実現が困難であることであり、ホットスポットデータに対してLRU効率が良好であることである.
LRUアルゴリズムの劣勢は、偶発的なロット操作、例えばロットクエリー履歴データに対して、キャッシュ中の人気データをこれらの履歴データに置き換え、キャッシュ汚染をもたらし、キャッシュヒット率を低下させ、正常なデータクエリーを遅らせる可能性があることである.
LRUアルゴリズムの改善案
以下のシナリオソースとMySQL InnoDB LRU改善アルゴリズム
チェーンテーブルを2つの部分に分割し、図に示すようにホットデータ領域とコールドデータ領域に分けます.
改善されると、アルゴリズム・プロセスは次のようになります.

アクセスデータがホットデータ領域にある場合、以前のLRUアルゴリズムと同様にホットデータ領域のヘッダノードに移動する.

データを挿入すると、キャッシュがいっぱいになると、エンドノードのデータが淘汰されます.次に、冷たいデータ領域のヘッダノードにデータを挿入します.

コールドデータ領域にあるデータがアクセスされるたびに、次のように判断する必要があります.

このデータがキャッシュに指定された時間を超えている場合、例えば1 sであれば、ホットデータ領域のヘッダノードに移動する.

このデータが所定時間未満に存在する場合、位置は変わらない.

偶発的な一括クエリーでは、データは冷たいデータ領域に落ちるだけで、すぐに淘汰されます.人気データ領域のデータは影響を受けません.これにより、LRUアルゴリズムのキャッシュヒット率が低下する問題が解決されます.
他にもLRU-K,2 Q,LIRSアルゴリズムがあり,興味のある学生は自分で調べることができる.
私の公衆番号に注目してください:プログラムが通じて、日常の乾物のプッシュを獲得します.私のテーマの内容に興味があれば、私のブログにも注目してください:studyidea.cn