Kuasai sepenuhnya pelaksanaan algoritma penghapusan cache LRU Redis-Redis-php.cn

Artikel ini membawa anda pengetahuan yang berkaitan tentang Redis, yang terutamanya memperkenalkan pelaksanaan algoritma penghapusan cache LRU, termasuk pelaksanaan anggaran algoritma LRU Redis, pelaksanaan sebenar algoritma LRU anggaran, dan lain-lain, harap ia membantu semua orang.

Kuasai sepenuhnya pelaksanaan algoritma penghapusan cache LRU Redis

Pembelajaran yang disyorkan: Tutorial pembelajaran Redis

1 Prinsip pelaksanaan LRU standard

LRU, Paling Kurang Digunakan Baru-baru ini (LRU), algoritma caching klasik.

LRU akan menggunakan senarai terpaut untuk mengekalkan status akses setiap data dalam cache, dan melaraskan kedudukan data dalam senarai terpaut berdasarkan akses masa nyata data, dan kemudian menggunakan kedudukan data dalam senarai terpaut untuk menunjukkan bahawa data tersebut telah Dilawati baru-baru ini, atau sudah lama tidak melawati.

LRU akan menetapkan kepala dan ekor rantai ke hujung MRU dan hujung LRU masing-masing:

Sebelah LRU, data yang paling sedikit diakses di sini

LRU boleh dibahagikan kepada situasi berikut:

kes1: Apabila data baharu dimasukkan , LRU akan memasukkan data ke dalam kepala rantai, dan pada masa yang sama memindahkan data di kepala senarai terpaut asal dan data selepasnya ke ekor dengan satu
case2: Apabila terdapat data yang baru sahaja Setelah mengakses sekali, LRU akan mengalihkan data dari kedudukan semasanya dalam senarai terpaut ke kepala rantai. Alihkan semua data lain dari kepala senarai terpaut ke kedudukan semasanya sedikit ke arah ekor
kes3: Apabila panjang senarai terpaut tidak lagi dapat menampung lebih banyak data dan data baharu dimasukkan, LRU Mengalih keluar data pada penghujung senarai terpaut juga sama dengan menghapuskan data daripada cache

Ilustrasi kes 2: Panjang senarai terpaut ialah 5, dan data disimpan dari kepala ke ekor senarai yang dipautkan ialah 5, 33, dan 9 masing-masing ,10,8. Andaikan bahawa data 9 diakses sekali, kemudian 9 akan dialihkan ke kepala senarai terpaut, dan pada masa yang sama, data 5 dan 33 kedua-duanya akan dialihkan satu kedudukan ke penghujung senarai terpaut.

Jadi jika ia dilaksanakan dengan ketat mengikut LRU, dengan mengandaikan bahawa Redis menyimpan banyak data, ia perlu dilaksanakan dalam kod:

ialah Apabila Redis menggunakan memori maksimum, ia mengekalkan senarai terpaut untuk semua data yang boleh ditampung
Ruang memori tambahan diperlukan untuk menyimpan senarai terpaut
Setiap kali data baharu dimasukkan atau data sedia ada dipadamkan Untuk mengakses semula, anda perlu melakukan berbilang operasi senarai terpaut
Dalam proses mengakses data, Redis dipengaruhi oleh overhed pergerakan data dan dipautkan operasi senarai

Akhirnya membawa kepada penurunan prestasi akses Redis.

Oleh itu, sama ada untuk menjimatkan memori atau mengekalkan prestasi tinggi Redis, Redis tidak dilaksanakan secara ketat mengikut prinsip asas LRU, tetapi

menyediakan anggaran pelaksanaan algoritma LRU .

2 Pelaksanaan anggaran algoritma LRU dalam Redis

Bagaimanakah mekanisme penghapusan memori Redis membolehkan algoritma LRU anggaran? Parameter konfigurasi berikut dalam redis.conf:

maxmemory, tetapkan kapasiti memori maksimum yang boleh digunakan oleh pelayan Redis Setelah jumlah sebenar memori yang digunakan oleh pelayan melebihi ambang ini, Pelayan akan melakukan operasi penghapusan memori mengikut dasar konfigurasi dasar memori maksimum
dasar memori maksimum, dan menetapkan dasar penghapusan memori pelayan Redis , termasuk anggaran penghapusan nilai LRU, LFU dan TTL dan penghapusan rawak, dsb.

Jadi, setelah pilihan maxmemory ditetapkan, dan maxmemory- polisi dikonfigurasikan sebagai allkeys-lru atau volatile-lru , anggaran LRU didayakan. Kedua-dua allkeys-lru dan volatile-lru akan menggunakan anggaran LRU untuk menghapuskan data Perbezaannya ialah:

volatile-. lru menapis data yang akan dihapuskan dalam pasangan KV dengan set TTL

Bagaimanakah Redis melaksanakan anggaran algoritma LRU?

Pengiraan nilai jam LRU global
Cara mengira nilai jam LRU global untuk menilai ketepatan masa akses data
Permulaan dan kemas kini nilai jam LRU bagi pasangan nilai kunci
Fungsi yang manakah memulakan dan mengemas kini nilai jam LRU yang sepadan dengan setiap pasangan nilai kunci?
Pelaksanaan sebenar algoritma LRU anggaran
Cara melaksanakan anggaran algoritma LRU, iaitu apabila penghapusan data dicetuskan dan mekanisme penghapusan sebenar dilaksanakan

Algoritma LRU anggaran masih perlu membezakan ketepatan masa capaian data yang berbeza, iaitu, Redis perlu mengetahui masa capaian terkini data. Oleh itu, jam LRU: merekodkan cap masa setiap akses kepada data.

Redis akan menggunakan struktur redisObject untuk menyimpan penuding kepada V untuk V dalam setiap pasangan KV. Selain penunjuk yang merekodkan nilai, redisObject juga menggunakan 24 bit untuk menyimpan maklumat jam LRU, yang sepadan dengan pembolehubah ahli lru. Dengan cara ini, setiap pasangan KV akan merekodkan cap masa akses terkininya dalam pembolehubah lru.

definisi redisObject mengandungi definisi pembolehubah ahli lru:

Bagaimanakah nilai jam LRU bagi setiap pasangan KV dikira? Pelayan Redis menggunakan jam LRU global peringkat contoh, dan masa LRU bagi setiap pasangan KV ditetapkan mengikut jam LRU global.

Jam LRU global ini disimpan dalam pembolehubah ahli pelayan berubah global Redis lruclock

Apabila Redis Server bermula, panggil initServerConfig untuk memulakan Apabila menetapkan pelbagai parameter, getLRUClock akan dipanggil untuk menetapkan nilai lruclock:

Jadi, anda perlu memberi perhatian, **Jika selang masa antara dua akses kepada data ialah

Fungsi getLRUClock membahagikan cap waktu UNIX yang diperolehi oleh LRU_CLOCK_RESOLUTION untuk mendapatkan cap masa UNIX yang dikira dengan ketepatan jam LRU, iaitu nilai jam LRU semasa.

getLRUClock akan melakukan operasi DAN antara nilai jam LRU dan definisi makro LRU_CLOCK_MAX (nilai maksimum yang boleh diwakili oleh jam LRU).

Jadi secara lalai, nilai jam LRU global ialah cap waktu UNIX yang dikira dengan ketepatan 1s dan dimulakan dalam initServerConfig.

Bagaimanakah nilai jam LRU global dikemas kini apabila Pelayan Redis sedang berjalan? Ia berkaitan dengan serverCron yang sepadan dengan acara masa yang kerap dijalankan Pelayan Redis dalam rangka kerja dipacu peristiwa.

serverCron, sebagai fungsi panggil balik untuk peristiwa masa, akan dilaksanakan secara berkala, nilai kekerapannya ditentukan oleh item konfigurasi hz Nilai lalai ialah 10, iaitu , fungsi serverCron akan melaksanakan setiap 100ms ( 1s/10 = 100ms) dijalankan sekali. Dalam serverCron, nilai jam LRU global akan dikemas kini secara berkala mengikut kekerapan pelaksanaan fungsi ini dengan memanggil getLRUClock:

Dengan cara ini, setiap pasangan KV boleh mendapatkan yang terkini daripada cap waktu Akses jam LRU global.

Untuk setiap pasangan KV, di manakah fungsi redisObject.lru yang sepadan dimulakan dan dikemas kini?

2.2 Permulaan dan kemas kini nilai jam LRU bagi pasangan nilai kunci

Untuk pasangan KV, nilai jam LRU pada mulanya ditetapkan apabila pasangan KV dibuat operasi pemulaan ini Dipanggil dalam fungsi createObject , fungsi ini akan dipanggil apabila Redis ingin mencipta pasangan KV.

Selain memperuntukkan ruang memori kepada redisObject, createObject juga akan memulakan redisObject.lru mengikut konfigurasi maxmemory_policy.

Jika maxmemory_policy=LFU, nilai pembolehubah lru akan dimulakan dan ditetapkan kepada nilai terkira algoritma LFU
maxmemory_policy≠LFU, kemudian createObject memanggil LRU_CLOCK untuk menetapkan nilai lru , iaitu nilai jam LRU pasangan KV yang sepadan.

LRU_CLOCK mengembalikan nilai jam LRU global semasa. Kerana sebaik sahaja pasangan KV dibuat, ia bersamaan dengan akses, dan nilai jam LRU yang sepadan mewakili cap masa aksesnya:

Pasangan KV yang manakah Bilakah jam LRU akan nilai dikemas kini semula?

Selagi pasangan KV diakses, nilai jam LRUnya akan dikemas kini! Apabila pasangan KV diakses, operasi capaian akhirnya akan memanggil lookupKey.

lookupKey akan mencari pasangan KV untuk diakses daripada jadual cincang global. Jika pasangan KV wujud, lookupKey akan mengemas kini nilai jam LRU bagi pasangan nilai kunci, iaitu cap masa aksesnya, berdasarkan nilai konfigurasi maxmemory_policy.

Apabila maxmemory_policy tidak dikonfigurasikan sebagai dasar LFU, fungsi lookupKey akan memanggil fungsi LRU_CLOCK untuk mendapatkan nilai jam LRU global semasa dan menetapkannya kepada pembolehubah lru dalam struktur redisObject bagi pasangan nilai kunci

Dengan cara ini, sebaik sahaja setiap pasangan KV diakses, ia akan mendapat cap masa akses terkini. Tetapi anda mungkin ingin tahu: Bagaimanakah cap masa akses ini akhirnya digunakan untuk menganggarkan algoritma LRU untuk penghapusan data?

2.3 Pelaksanaan sebenar algoritma LRU anggaran

Sebab mengapa Redis melaksanakan anggaran LRU adalah untuk mengurangkan overhed sumber memori dan masa operasi.

2.3.1 Bilakah pelaksanaan algoritma dicetuskan?

Logik utama anggaran LRU adalah dalam performEvictions.

performEvictions dipanggil oleh evictionTimeProc, dan fungsi evictionTimeProc dipanggil oleh processCommand.

processCommand, Redis akan memanggil semasa memproses setiap arahan:

Kemudian, isSafeToPerformEvictions akan menilai semula sama ada untuk meneruskan pelaksanaan performEvictions berdasarkan syarat berikut:

Setelah performEvictions dipanggil dan maxmemory-policy ditetapkan kepada allkeys-lru atau volatile-lru, anggaran pelaksanaan LRU akan dicetuskan.

2.3.2 Proses pelaksanaan khusus anggaran LRU

Pelaksanaan boleh dibahagikan kepada langkah berikut:

2.3.2.1 Tentukan penggunaan memori semasa

Panggil getMaxmemoryState untuk menilai penggunaan memori semasa dan tentukan sama ada kapasiti memori semasa yang digunakan oleh Redis Server melebihi nilai konfigurasi maxmemory.

Jika maxmemory tidak melebihi, C_OK akan dikembalikan, dan performEvictions juga akan dikembalikan terus.

Apabila getMaxmemoryState menilai penggunaan memori semasa, jika ia mendapati bahawa memori yang digunakan melebihi maxmemory, ia akan mengira jumlah memori yang perlu dikeluarkan. Saiz memori yang dikeluarkan ini = jumlah memori yang digunakan - maxmemory.

Tetapi amaun memori yang digunakan tidak termasuk saiz penimbal salinan yang digunakan untuk replikasi induk-hamba, yang dikira oleh getMaxmemoryState dengan memanggil freeMemoryGetNotCountedMemory.

Jika jumlah memori yang digunakan oleh Pelayan pada masa ini melebihi had atas memori maksimum , performEvictions akan melaksanakan gelung sementara untuk menghapuskan data dan melepaskan memori.

ialah data penyingkiran Redis mentakrifkan tatasusunan EvictionPoolLRU untuk menyimpan pasangan KV yang akan dihapuskan Jenis elemen ialah struktur evictionPoolEntry, yang menjimatkan masa melahu, K yang sepadan dan maklumat pasangan KV yang lain. untuk dihapuskan:

Dengan cara ini, apabila Redis Server melaksanakan initSever untuk permulaan, ia akan memanggil evictionPoolAlloc untuk memperuntukkan ruang memori untuk Tatasusunan EvictionPoolLRU Saiz tatasusunan ditentukan oleh EVPOOL_SIZE dan boleh ditetapkan secara lalai Simpan 16 pasangan KV calon untuk dihapuskan.

performEvictions akan mengemas kini set pasangan KV calon yang akan dihapuskan, iaitu tatasusunan EvictionPoolLRU, semasa proses kitaran penghapusan data.

2.3.2.2 Kemas kini set pasangan KV calon yang akan disingkirkan

performEvictions calls evictionPoolPopulate, yang akan mula-mula memanggil dictGetSomeKeys untuk mendapatkan nombor K tertentu secara rawak daripada jadual cincang untuk dijadikan sampel :

Jadual cincang yang disampel oleh dictGetSomeKeys ditentukan oleh item konfigurasi maxmemory_policy:
- Jika maxmemory_policy=allkeys_lru, jadual cincang yang akan diambil sampel ialah cincang global jadual Pelayan Redis, iaitu Sampel
- dalam semua pasangan KV Jika tidak, jadual cincang yang akan dijadikan sampel ialah jadual cincang yang memegang K dengan set TTL.

Bilangan K sampel dalam dictGetSomeKeys ditentukan oleh item konfigurasi maxmemory-samples, lalai 5:

Oleh itu, dictGetSomeKeys mengembalikan set pasangan KV sampel. evictionPoolPopulate melaksanakan gelung berdasarkan bilangan sebenar kiraan pasangan KV sampel: panggil estimateObjectIdleTime untuk mengira masa melahu setiap pasangan KV dalam set pensampelan:

Kemudian, evictionPoolPopulate melintasi menunggu Set pasangan KV calon yang disingkirkan, iaitu tatasusunan EvictionPoolLRU, cuba memasukkan setiap pasangan KV sampel ke dalam tatasusunan EvictionPoolLRU, bergantung pada salah satu syarat berikut:

boleh mencari KV pasangan yang masih belum dimasukkan dalam tatasusunan Setelah bit kosong
boleh mencari masa melahu pasangan KV dalam tatasusunan

telah ditubuhkan, evictionPoolPopulate boleh memasukkan pasangan KV sampel ke dalam tatasusunan EvictionPoolLRU. Selepas semua pasangan nilai kunci sampel diproses, fungsi evictionPoolPopulate selesai mengemas kini set pasangan nilai kunci calon untuk dihapuskan.

Seterusnya, performEvictions mula memilih pasangan KV yang akhirnya akan disingkirkan.

2.3.2.3 Pilih pasangan KV yang disingkirkan dan padamkannya

Oleh kerana evictionPoolPopulate telah mengemas kini tatasusunan EvictionPoolLRU dan K dalam tatasusunan adalah daripada kecil hingga besar dalam keadaan terbiar masa Sudah disusun. Oleh itu, performEvictions merentasi tatasusunan EvictionPoolLRU sekali dan mula memilih daripada K terakhir dalam tatasusunan Jika K yang dipilih tidak kosong, ia akan digunakan sebagai K terakhir untuk dihapuskan.

Logik pelaksanaan proses ini:

Setelah K yang disingkirkan dipilih, performEvictions akan melakukan pemadaman segerak atau pemadaman tak segerak berdasarkan konfigurasi pemadaman malas bagi pelayan Redis Dipadamkan:

Pada ketika ini, performEvictions telah menghapuskan K. Jika ruang memori yang dikeluarkan pada masa ini tidak mencukupi, iaitu ruang yang akan dikeluarkan tidak tercapai, performEvictions juga akan mengulang proses mengemas kini set pasangan KV calon yang akan dihapuskan dan memilih pasangan KV akhir sehingga ia berpuas hati Keperluan saiz ruang yang akan dilepaskan.

melaksanakan proses Pengusiran:

Algoritma LRU anggaran tidak menggunakan senarai terpaut yang memakan masa dan memakan ruang, tetapi menggunakan set data bersaiz tetap untuk dihapuskan dan secara rawak memilih beberapa K untuk ditambahkan pada baris gilir setiap kali Hapuskan pengumpulan data.

Akhir sekali, mengikut tempoh masa melahu K dalam set yang akan dihapuskan, padamkan K dengan masa melahu yang paling lama.

Ringkasan

Mengikut prinsip asas algoritma LRU, didapati jika algoritma LRU dilaksanakan dengan ketat mengikut prinsip asas, sistem yang dibangunkan memerlukan ruang memori tambahan untuk menyimpan senarai terpaut LRU, dan sistem juga akan terjejas oleh LRU apabila berjalan Kesan overhed operasi senarai terpaut.

Sumber memori dan prestasi Redis adalah penting, jadi Redis melaksanakan anggaran algoritma LRU:

Pertama, jam LRU global ditetapkan dan dalam KV Dapatkan nilai jam LRU global sebagai cap masa capaian semasa membuat, dan dapatkan nilai jam LRU global semasa setiap capaian, dan kemas kini cap masa capaian
Kemudian, apabila Redis memproses arahan, performEvictions dipanggil untuk menentukan sama ada ia diperlukan. Jika memori yang digunakan melebihi memori maksimum, pilih beberapa pasangan KV secara rawak untuk membentuk set calon untuk dihapuskan, dan pilih data tertua untuk dihapuskan berdasarkan cap masa capaian mereka

Prinsip dan algoritma asas algoritma Di sana akan menjadi kompromi tertentu dalam pelaksanaan sebenar pembangunan sistem, dan keperluan sumber dan prestasi sistem yang dibangunkan perlu dipertimbangkan secara menyeluruh untuk mengelakkan sumber dan overhed prestasi yang disebabkan oleh mengikut ketat pelaksanaan algoritma.

Pembelajaran yang disyorkan: Tutorial Redis

Atas ialah kandungan terperinci Kuasai sepenuhnya pelaksanaan algoritma penghapusan cache LRU Redis. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!