Ein Artikel, der den LRU-Algorithmus in Redis ausführlich erklärt

package com.lizba.redis.lru;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedDeque;

/**
 * <p>
 *      LRU简单实现
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/9/17 23:47
 */
public class SimpleLru {

    /** 数据缓存 */
    private ConcurrentHashMap<string> cacheData;
    /** 访问顺序记录 */
    private ConcurrentLinkedDeque<string> sequence;
    /** 缓存容量 */
    private int capacity;

    public SimpleLru(int capacity) {
        this.capacity = capacity;
        cacheData = new ConcurrentHashMap(capacity);
        sequence = new ConcurrentLinkedDeque();
    }


    /**
     * 设置值
     *
     * @param key
     * @param value
     * @return
     */
    public Object setValue(String key, Object value) {
        // 判断是否需要进行LRU淘汰
        this.maxMemoryHandle();
        // 包含则移除元素，新访问的元素一直保存在队列最前面
        if (sequence.contains(key)) {
            sequence.remove();
        }
        sequence.addFirst(key);
        cacheData.put(key, value);
        return value;
    }


    /**
     * 达到最大内存，淘汰最近最少使用的key
     */
    private void maxMemoryHandle() {
        while (sequence.size() >= capacity) {
            String lruKey = sequence.removeLast();
            cacheData.remove(lruKey);
            System.out.println("key: " + lruKey + "被淘汰！");
        }
    }


    /**
     * 获取访问LRU顺序
     *
     * @return
     */
    public List<string> getAll() {
        return Arrays.asList(sequence.toArray(new String[] {}));
    }
}复制代码</string></string></string>

package com.lizba.redis.lru;

/**
 * <p>
 *      测试最近最少使用
 * </p>
 *
 * @Author: Liziba
 * @Date: 2021/9/18 0:00
 */
public class TestSimpleLru {

    public static void main(String[] args) {
        SimpleLru lru = new SimpleLru(8);
        for (int i = 0; i <p><br>Testergebnisse: <strong></strong></p><p><strong></strong>Wie aus den obigen Testergebnissen ersichtlich ist, wurden key0 und key1, die zuerst hinzugefügt wurden, eliminiert und entfernt zuletzt hinzugefügt Der Schlüssel ist auch der zuletzt am Anfang der Sequenz gespeicherte Schlüssel. </p>Mit dieser Lösung kann der LRU-Algorithmus leicht implementiert werden. Die Lösung erfordert jedoch die Verwendung zusätzlicher Datenstrukturen, um die Schlüsselzugriffssequenz zu speichern, was den Speicherverbrauch von Redis selbst erhöht Speicher optimieren, aber es verbraucht viel Speicher, was offensichtlich nicht möglich ist. <p><strong><h2 data-id="heading-4">5. Ungefähre LRU von Redis</h2>
<p>Als Reaktion auf diese Situation verwendet Redis den ungefähren LRU-Algorithmus, der die in letzter Zeit am seltensten verwendeten Schlüssel nicht vollständig eliminiert, aber die Gesamtgenauigkeit kann garantiert werden. <br>Der ungefähre LRU-Algorithmus ist sehr einfach. Im Redis-Schlüsselobjekt werden 24 Bits hinzugefügt, um den Systemzeitstempel des letzten Zugriffs zu speichern erreicht maxmemory. Zu diesem Zeitpunkt wird das verzögerte Löschen ausgelöst. Der Redis-Dienst wählt durch Zufallsstichprobe 5 Schlüssel aus, die die Bedingungen erfüllen mit eingestellter Ablaufzeit (Zufallsstichprobe), vergleichen Sie den letzten im Schlüsselobjekt aufgezeichneten Zugriffszeitstempel und entfernen Sie den ältesten Schlüssel unter den fünf Schlüsseln. Wenn der Speicher immer noch nicht ausreicht, wiederholen Sie diesen Schritt. <strong></strong><strong></strong>Beachten Sie, dass 5 die standardmäßige Größe des Zufallsstichprobenwerts von Redis ist, die über maxmemory_samples in redis.conf konfiguriert werden kann: <br></p>
<p><strong></strong></p>
<p>Für den oben genannten zufälligen LRU-Algorithmus hat der Redis-Beamte ein Testdiagramm für die Genauigkeitsdaten bereitgestellt : <img src="https://img.php.cn/upload/image/866/655/134/163409192913128Ein%20Artikel,%20der%20den%20LRU-Algorithmus%20in%20Redis%20ausf%C3%BChrlich%20erkl%C3%A4rt" title="163409192913128Ein Artikel, der den LRU-Algorithmus in Redis ausführlich erklärt" alt="Ein Artikel, der den LRU-Algorithmus in Redis ausführlich erklärt"></p>
<p><strong>Die obere hellgraue Ebene stellt die eliminierten Schlüssel dar. Abbildung 1 ist ein schematisches Diagramm der Standard-LRU-Algorithmus-Eliminierung. </strong></p>Die mittlere dunkelgraue Ebene stellt die alten Schlüssel dar, die nicht eliminiert wurden Die hellgrüne Schicht stellt den zuletzt aufgerufenen Schlüssel dar. <ul>
<li>
<li>
<li>Wenn in Redis 3.0 maxmemory_samples auf 10 gesetzt ist, kommt der ungefähre LRU-Algorithmus von Redis dem echten LRU-Algorithmus sehr nahe, aber wenn maxmemory_samples auf 10 gesetzt wird, verbraucht es offensichtlich mehr CPU als bei maxmemory_samples 5 Berechnungszeit: Da die Probendaten jedes Mal zunehmen, erhöht sich auch die Berechnungszeit. </li>
</ul>Der LRU-Algorithmus von Redis3.0 ist genauer als der LRU-Algorithmus von Redis2.8<p>, da Redis3.0 einen Eliminierungspool mit der gleichen Größe wie maxmemory_samples hinzufügt. Jedes Mal, wenn ein Schlüssel eliminiert wird, wird er zuerst mit dem verglichen Der Eliminierungspool wartet darauf, eliminiert zu werden, und der älteste Schlüssel wird schließlich eliminiert. Tatsächlich werden die zur Eliminierung ausgewählten Schlüssel erneut zusammengestellt und verglichen, und der älteste Schlüssel wird eliminiert. <img src="https://img.php.cn/upload/image/618/208/647/163409193623649Ein%20Artikel,%20der%20den%20LRU-Algorithmus%20in%20Redis%20ausf%C3%BChrlich%20erkl%C3%A4rt" title="163409193623649Ein Artikel, der den LRU-Algorithmus in Redis ausführlich erklärt" alt="Ein Artikel, der den LRU-Algorithmus in Redis ausführlich erklärt"></p>6. Es gibt Probleme<p><br>Der LRU-Algorithmus scheint einfacher zu verwenden zu sein, aber es gibt auch unzumutbare Stellen. Beispielsweise wurden eine Stunde vor der Eliminierung zwei Schlüssel A und B gleichzeitig hinzugefügt Zuerst wurde in 49 Minuten 1.000 Mal zugegriffen, in den nächsten 11 Minuten wurde jedoch nur einmal in der 59. Minute zugegriffen, wenn zu diesem Zeitpunkt der LRU-Algorithmus verwendet wurde Durch Redis-Sampling ausgewählt, wird A eliminiert. Offensichtlich ist dies unvernünftig. <strong>Als Reaktion auf diese Situation hat Redis 4.0 den LFU-Algorithmus (am seltensten verwendet) hinzugefügt. Dieser Algorithmus ist sinnvoller als LRU. Bitte beachten Sie den Eliminierungsalgorithmus meine Kolumne. </strong></p>Weitere Kenntnisse zum Thema Programmierung finden Sie unter: <h2 data-id="heading-5">Programmierlehre</h2>! ! <p></p></strong></p>