Artikel yang menerangkan algoritma LRU dalam Redis secara terperinci

Artikel ini akan memperkenalkan anda kepada LRU (Paling Kurang Digunakan) dalam Redis. Saya harap ia akan membantu anda!

Redis ialah pangkalan data nilai kunci berdasarkan storan memori Kami tahu bahawa walaupun memori adalah pantas, ia mempunyai ruang yang kecil apabila memori fizikal mencapai bahagian atas had, sistem akan berjalan Ia sangat perlahan kerana mekanisme swap akan memindahkan sebahagian daripada data memori ke partition swap, dan pertukaran dengan swap memastikan sistem terus berjalan, bagaimanapun, swap adalah storan cakera keras, dan kelajuannya jauh lebih perlahan daripada memori, terutamanya untuk Redis Untuk perkhidmatan dengan QPS yang sangat tinggi, keadaan ini tidak boleh diterima. (Perhatikan bahawa jika memori partition swap juga penuh, ralat akan berlaku dalam sistem!) [Cadangan berkaitan: Tutorial video Redis]

Sistem pengendalian Linux boleh melihat swap melalui percuma -m Saiz:

Oleh itu, cara untuk mengelakkan perkara ini daripada berlaku di Redis adalah sangat penting (penemuduga hampir tidak pernah bertanya tentang Redis tanpa bertanya tentang titik pengetahuan ini ).

2. Konfigurasi maxmemory

Redis menyediakan konfigurasi maxmemory untuk menyelesaikan masalah di atas Konfigurasi ini boleh menentukan set data maksimum storan Redis. Ia biasanya dikonfigurasikan dalam fail redis.conf baik. Konfigurasi satu kali boleh dilakukan pada masa jalan menggunakan arahan CONFIG SET.
Gambar rajah skematik item konfigurasi dalam fail redis.conf:

Item konfigurasi maxmemory tidak didayakan secara lalai Redis diperkenalkan secara rasmi Sistem pengendalian 64-bit Tiada had memori secara lalai Konfigurasi memori tersirat lalai bagi sistem pengendalian 32-bit ialah 3GB Jika memori maksimum ialah 0, ini bermakna memori tidak terhad.

Oleh itu, apabila kita membina seni bina cache, kita mesti membuat konfigurasi memori maksimum yang sesuai berdasarkan sumber perkakasan dan keperluan perniagaan.

3. Apakah yang perlu saya lakukan jika memori mencapai maxmemory

Jelas sekali memori maksimum dikonfigurasikan apabila maxmemory mencapai had maksimum, adalah mustahil untuk Redis berhenti berfungsi. Jadi bagaimana Redis menanganinya Bagaimana dengan masalah ini? Ini adalah fokus artikel ini. Redis menyediakan strategi penghapusan dasar memori maksimum (Artikel ini hanya bercakap tentang LRU dan tidak melibatkan LFU, LFU akan diterangkan dalam artikel seterusnya), yang memadamkan kunci yang memenuhi syarat untuk mengucapkan selamat tinggal kepada yang lama dan mengalu-alukan yang baru.
dasar penghapusan dasar memori maksimum:

• noeviction: Apabila had memori dicapai dan klien cuba melaksanakan arahan yang mungkin menyebabkan lebih banyak memori untuk digunakan Ralat dikembalikan secara ringkas, operasi baca masih dibenarkan, tetapi data baharu tidak dibenarkan untuk ditulis permintaan del (padam) boleh dibuat .
• allkeys-lru: Hapuskan semua kekunci melalui algoritma lru (Paling Kurang Digunakan - Paling Kurang Digunakan)
• allkeys-random: Hapuskan secara rawak daripada semua kekunci
• volatile-lru: Hapuskan daripada semua kunci dengan masa tamat tempoh ditetapkan melalui algoritma lru (Paling Kurang Digunakan - Paling Kurang Digunakan Baru-baru ini) Ini memastikan data yang tidak mempunyai masa tamat tempoh yang ditetapkan dan perlu diteruskan tidak akan dipilih untuk penyingkiran
• rawak meruap: Alih keluar semua kunci secara rawak dengan set masa tamat
• mudah meruap- ttl: Daripada semua kunci dengan masa tamat tempoh ditetapkan, dengan membandingkan baki masa tamat tempoh nilai TTL kunci, lebih kecil TTL, lebih awal ia akan dihapuskan

Terdapat juga tidak menentu- lfu/allkeys-lfu yang akan dibincangkan di bawah kedua-dua algoritma adalah berbeza!

Penghapusan rawak hanya perlu memilih beberapa kekunci secara rawak untuk memadam dan melepaskan ruang memori; ttl. Hanya kosongkan ruang ingatan.
Jadi bagaimana LRU dilaksanakan? Bagaimanakah Redis mengetahui kunci mana yang telah digunakan baru-baru ini dan kunci mana yang belum digunakan baru-baru ini?

4. Pelaksanaan algoritma LRU

Kami mula-mula menggunakan bekas Java untuk melaksanakan algoritma LRU mudah Kami menggunakan ConcurrentHashMap untuk melakukan hubungan pemetaan elemen storan hasil nilai kunci, dan menggunakan ConcurrentLinkedDeque untuk Mengekalkan urutan akses kunci.
Kod pelaksanaan LRU:

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>

Kod ujian:

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><strong>Hasil ujian: </strong>Melalui penyelesaian ini, algoritma LRU boleh dilaksanakan dengan mudah, tetapi kelemahannya juga sangat jelas. mengoptimumkan ingatan. Penyelesaian ini menggunakan banyak memori, yang jelas tidak boleh dilaksanakan. </p><p><img src="https://img.php.cn/upload/image/775/594/750/163409191823487Artikel%20yang%20menerangkan%20algoritma%20LRU%20dalam%20Redis%20secara%20terperinci" title="163409191823487Artikel yang menerangkan algoritma LRU dalam Redis secara terperinci" alt="Artikel yang menerangkan algoritma LRU dalam Redis secara terperinci"></p><h2 data-id="heading-4">5. Anggaran LRU Redis</h2><p>Sebagai tindak balas kepada situasi ini, Redis menggunakan anggaran algoritma LRU, yang tidak tepat sepenuhnya dalam menghapuskan kekunci yang paling kurang kerap digunakan baru-baru ini, tetapi ketepatan keseluruhannya juga Dijamin. <br>Algoritma LRU anggaran adalah sangat mudah Dalam objek kunci Redis, 24 bit ditambah untuk menyimpan cap masa sistem bagi akses terkini Apabila pelanggan menghantar permintaan berkaitan penulisan kunci kepada pelayan Redis, didapati bahawa memori mencapai maxmemory. Lazy deleted dicetuskan pada masa ini; perkhidmatan Redis memilih 5 kekunci yang memenuhi syarat melalui pensampelan rawak (perhatikan bahawa pensampelan rawak <strong>allkeys-lru</strong> secara rawak daripada semua kekunci, <strong>volatile-lru</strong>Diambil secara rawak daripada semua kekunci dengan masa tamat tempoh), bandingkan dengan cap waktu capaian terkini yang direkodkan dalam objek utama, dan hapuskan kunci tertua di antara 5 kekunci jika memori masih tidak mencukupi, teruskan ulangi langkah ini. <br></p><p><strong>Perhatikan bahawa 5 ialah saiz nilai pensampelan rawak lalai Redis, yang boleh dikonfigurasikan melalui maxmemory_samples dalam redis.conf: </strong></p><p><img src="https://img.php.cn/upload/image/866/655/134/163409192913128Artikel%20yang%20menerangkan%20algoritma%20LRU%20dalam%20Redis%20secara%20terperinci" title="163409192913128Artikel yang menerangkan algoritma LRU dalam Redis secara terperinci" alt="Artikel yang menerangkan algoritma LRU dalam Redis secara terperinci"></p><p><strong>Untuk algoritma LRU rawak yang disebutkan di atas, Redis secara rasmi menyediakan carta data untuk menguji ketepatan: </strong></p>

• Lapisan atas kelabu muda mewakili kekunci yang disingkirkan 1 ialah gambarajah skematik penghapusan algoritma LRU standard
• Lapisan kelabu gelap di tengah mewakili kekunci lama yang belum dihapuskan
• Lapisan hijau muda di bahagian bawah mewakili yang diakses baru-baru ini kunci

Dalam Redis 3.0 apabila maxmemory_samples ditetapkan kepada 10, algoritma LRU anggaran Redis adalah sangat hampir dengan algoritma LRU sebenar, tetapi jelas menetapkan maxmemory_samples kepada 10 menggunakan lebih banyak CPU daripada menetapkan maxmemory_samples kepada 5. Masa pengiraan, kerana data sampel yang diambil sampel setiap kali meningkat, masa pengiraan juga akan meningkat.
Algoritma LRU Redis3.0 lebih tepat daripada algoritma LRU Redis2.8, kerana Redis3.0 menambah kumpulan penyingkiran dengan saiz yang sama dengan maxmemory_samples Setiap kali kunci dihapuskan. ia mula-mula dihapuskan dengan Kunci yang menunggu untuk dihapuskan dalam kumpulan dibandingkan, dan kunci tertua akhirnya dihapuskan Malah, kunci yang dipilih untuk penyingkiran disatukan dan dibandingkan, dan yang tertua di antaranya dihapuskan.

6. Masalah

Algoritma LRU nampaknya lebih mudah digunakan, tetapi terdapat juga tempat yang tidak munasabah, contohnya, dua kekunci A dan B adalah sama satu jam sebelum penyingkiran. Masa ditambah ke Redis A telah dilawati 1,000 kali dalam 49 minit pertama, tetapi tidak dilawati dalam 11 minit terakhir B hanya dikunjungi sekali pada minit ke-59 dalam jam ini; jika A, B semuanya dipilih oleh pensampelan Redis, dan A akan dihapuskan. Jelas sekali ini adalah tidak munasabah.
Sebagai tindak balas kepada situasi ini, Redis 4.0 menambah algoritma LFU, (Paling jarang digunakan), yang merupakan yang paling kerap digunakan Algoritma ini lebih munasabah daripada LRU Kami akan mempelajari algoritma penyingkiran bersama-sama di bawah perhatikan ruangan saya.

Untuk lebih banyak pengetahuan berkaitan pengaturcaraan, sila lawati: Pengajaran Pengaturcaraan! !

Atas ialah kandungan terperinci Artikel yang menerangkan algoritma LRU dalam Redis secara terperinci. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!