Rumah > Artikel > pangkalan data > Kuasai sepenuhnya pelaksanaan algoritma penghapusan cache LRU Redis
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.
Pembelajaran yang disyorkan: Tutorial pembelajaran Redis
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:menyediakan anggaran pelaksanaan algoritma LRU .
2 Pelaksanaan anggaran algoritma LRU dalam RedisBagaimanakah 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.
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?Cara melaksanakan anggaran algoritma LRU, iaitu apabila penghapusan data dicetuskan dan mekanisme penghapusan sebenar dilaksanakan
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?
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.
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?
Sebab mengapa Redis melaksanakan anggaran LRU adalah untuk mengurangkan overhed sumber memori dan masa operasi.
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.
Pelaksanaan boleh dibahagikan kepada langkah berikut:
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.
performEvictions calls evictionPoolPopulate, yang akan mula-mula memanggil dictGetSomeKeys untuk mendapatkan nombor K tertentu secara rawak daripada jadual cincang untuk dijadikan sampel :
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:
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.
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.
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:
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!