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

Dieser Artikel stellt Ihnen LRU (Least Recent Used) in Redis vor. Ich hoffe, er wird Ihnen hilfreich sein!

Redis ist eine Schlüsselwertdatenbank, die auf Speicherspeicherung basiert. Wir wissen, dass der Speicher zwar schnell ist, aber nur über wenig Speicherplatz verfügt. Dies liegt daran, dass der physische Speicher sehr langsam ist Der Swap-Mechanismus speichert einen Teil des Speichers. Die Daten werden auf die Swap-Partition übertragen, und der Austausch mit Swap stellt sicher, dass das System weiterhin läuft. Swap ist jedoch ein Festplattenspeicher und seine Geschwindigkeit ist weitaus langsamer Insbesondere bei einem Dienst mit sehr hohem QPS wie Redis ist dies beim Empfang nicht möglich. (Beachten Sie, dass ein Fehler im System auftritt, wenn auch der Swap-Partitionsspeicher voll ist!) [Verwandte Empfehlung: Redis-Video-Tutorial]

Das Linux-Betriebssystem kann die Swap-Größe über free -m:

überprüfen

Wie ist es also sehr wichtig, zu verhindern, dass diese Situation in Redis auftritt (der Interviewer fragt fast nie nach diesem Wissenspunkt, wenn er nach Redis gefragt wird).

2. Maxmemory-Konfiguration

Redis bietet eine Maxmemory-Konfiguration, um die oben genannten Probleme zu lösen. Diese Konfiguration kann normalerweise in der Datei redis.conf konfiguriert werden, oder sie kann mit CONFIG SET konfiguriert werden Befehl zur Laufzeit.
Schematische Darstellung der Konfigurationselemente in der Datei redis.conf:

Standardmäßig ist das Konfigurationselement maxmemory nicht aktiviert. 64-Bit-Betriebssysteme haben standardmäßig kein Speicherlimit und 32 -Bit-Betriebssysteme verfügen standardmäßig über eine implizite Speicherkonfiguration von 3 GB. Wenn maxmemory 0 ist, bedeutet dies, dass der Speicher unbegrenzt ist.

Wenn wir also eine Cache-Architektur erstellen, müssen wir geeignete Maxmemory-Konfigurationen basierend auf Hardwareressourcen und Geschäftsanforderungen vornehmen.

3. Was soll ich tun, wenn der maximale Speicher erreicht ist? Wenn der maximale Speicher erreicht ist, kann Redis nicht mehr mit diesem Problem umgehen. Dies ist der Schwerpunkt dieses Artikels. Redis bietet eine Strategie zur Eliminierung der Maxmemory-Richtlinie (

Dieser Artikel befasst sich nur mit LRU und bezieht sich nicht auf LFU

, LFU wird im nächsten Artikel beschrieben), mit der Schlüssel gelöscht werden, die die genannten Bedingungen erfüllen Verabschieden Sie sich vom Alten und begrüßen Sie das Neue. maxmemory-policy Eliminierungsstrategie:

noeviction:
• Wenn das Speicherlimit erreicht ist und der Client versucht, einen Befehl auszuführen, der möglicherweise mehr Speicher belegt, wird ein Fehler zurückgegeben. Einfach ausgedrückt, werden Lesevorgänge ausgeführt immer noch erlaubt, aber Schreibvorgänge sind nicht erlaubt. Für neue Daten sind del (delete)-Anfragen in Ordnung .
allkeys-lru:
• Eliminieren Sie alle Schlüssel durch den LRU-Algorithmus (Least Latest Used - Least Latest Used).
allkeys-random:
• Entfernen Sie zufällig alle Schlüssel Wenn eine Ablaufzeit festgelegt ist, werden sie durch den LRU-Algorithmus (Least Latest Used) eliminiert. Dadurch wird sichergestellt, dass Daten, für die keine Ablaufzeit festgelegt ist und die gespeichert werden müssen, nicht für die Eliminierung ausgewählt werden - zufällig: Nach dem Zufallsprinzip aus allen Schlüsseln mit festgelegter Ablaufzeit entfernen
• volatile-ttl: Aus allen Schlüsseln mit festgelegter Ablaufzeit durch Vergleich des Werts der verbleibenden Ablaufzeit TTL des Schlüssels gilt: Je kleiner die TTL, desto früher Eliminiert
• und volatile-lfu/allkeys-lfu werden weiter unten besprochen. Die beiden Algorithmen sind unterschiedlich!
Bei der zufälligen Eliminierung müssen nur einige Schlüssel zum Löschen und Freigeben von Speicherplatz ausgewählt werden. Die TTL-Ablaufzeit ist gering, und diejenigen mit der kleinsten Ablaufzeit können zuerst entfernt werden. Sie können auch die Größe des TTL vergleichen und löschen Schlüssel mit dem kleinen TTL-Wert, um den Speicherplatz freizugeben.
• Wie wird LRU implementiert? Woher weiß Redis, welcher Schlüssel kürzlich verwendet wurde und welcher Schlüssel kürzlich nicht verwendet wurde?
4. Implementierung des LRU-Algorithmus

Wir verwenden zunächst Java-Container, um einen einfachen LRU-Algorithmus zu implementieren. Wir verwenden ConcurrentHashMap, um die Zuordnungsbeziehung von Schlüsselwert-Ergebnisspeicherelementen durchzuführen, und verwenden ConcurrentLinkedDeque, um die Schlüsselzugriffssequenz aufrechtzuerhalten.

LRU-Implementierungscode:

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>

Testcode:

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>

Das obige ist der detaillierte Inhalt vonEin Artikel, der den LRU-Algorithmus in Redis ausführlich erklärt. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!