Bagaimana Anda mengimplementasikan cache LRU-K?

Perintah dan konteks

Implementasikan cache LRU-K terbatas yang mendukung get, put, dan pengeluaran (eviction). Simpan K akses paling baru per kunci. Entri dengan akses kurang dari K membentuk tingkat riwayat tidak lengkap (history-incomplete) dan harus dikeluarkan sebelum entri yang panas (hot). Perjelas K, kapasitas, pembaruan pada kunci yang ada, panggilan konkuren, dan kunci yang tidak ditemukan.

Apa yang sedang diuji oleh pewawancara

• Apakah Anda mengelola riwayat akses dan dua tingkatan kandidat dengan benar.
• Apakah Anda dapat memilih heap, hash map, atau struktur terurut dan menganalisis biayanya.
• Apakah Anda menangani penimpaan (overwrite), kapasitas nol, K yang tidak valid, dan visibilitas konkuren.
• Apakah Anda memahami bahwa LRU-K menyaring polusi pemindaian (scan pollution) alih-alih selalu unggul di setiap beban kerja.

Pertanyaan klarifikasi sebelum menjawab

Konfirmasikan keamanan thread (thread safety), pengeluaran aproksimasi, nilai yang dapat diubah (mutable), persyaratan TTL, dan metrik hit-rate. Pengurutan yang ketat biasanya membutuhkan kunci (lock) atau pembaruan yang diserialkan; throughput yang lebih tinggi mungkin memerlukan sharding dan kebijakan aproksimasi.

Kerangka jawaban 30 detik

Simpan nilai, K stempel waktu logis (logical timestamps) terbaru, dan versi per kunci. Bagi kandidat ke dalam tingkat riwayat tidak lengkap dan tingkat panas. Ketika melebihi kapasitas, keluarkan item terlama di tingkat yang tidak lengkap; jika tidak ada, keluarkan item panas dengan stempel waktu ke-K paling baru terkecil. Hash map memberikan pencarian O(1) dan heap mempertahankan kandidat; versi membuang node heap yang basi (stale). get dan put yang ketat diperkirakan O(log n), dengan ruang riwayat O(capacity·K).

Pembahasan mendalam langkah demi langkah

1. Mencatat riwayat akses

Tambahkan nilai jam logis pada setiap hit atau penulisan dan pertahankan hanya K nilai terbaru. Jam logis membandingkan urutan tanpa lompatan jam dinding (wall-clock) dan membedakan akses dalam milidetik yang sama. Penimpaan dihitung sebagai akses kecuali jika petunjuk menyatakan penulisan tidak dihitung.

2. Mempertahankan kandidat pengeluaran

Tingkat yang tidak lengkap diurutkan berdasarkan akses terbarunya; tingkat panas berdasarkan akses ke-K paling barunya. Pertahankan dua min-heap dari (key, version, rank). Akses baru memasukkan (push) node baru dan menambah versi; pengeluaran memvalidasi versi dan peringkat saat ini, melewati node yang basi.

3. Batasan dan konkurensi

Jangan menyimpan ke cache jika kapasitas nol atau negatif; tolak K jika nol atau negatif. Pengeluaran dan pembaruan nilai harus berbagi critical section sehingga panggilan put konkuren tidak dapat melebihi kapasitas. Sharded lock meningkatkan throughput, tetapi kapasitas global kemudian membutuhkan koordinasi.

Contoh jawaban berkualitas tinggi

Saya memisahkan entri ke dalam tingkat riwayat tidak lengkap dan tingkat panas. Setiap entri menyimpan nilainya, K waktu logis terbaru, dan versi; sebuah akses memperbarui riwayat dan memasukkan node peringkat baru ke dalam min-heap yang relevan. Pengeluaran memeriksa heap yang tidak lengkap terlebih dahulu, kemudian heap panas, memvalidasi versi untuk melewati node yang basi. Pencarian adalah O(1) melalui map, operasi heap adalah O(log n), dan ruang riwayat adalah O(capacity·K). Pengujian mencakup K=1 yang berperilaku seperti LRU, promosi setelah akses berulang, pemindaian satu kali, penimpaan, kapasitas nol, penulisan melebihi kapasitas secara konkuren, node heap yang basi, dan hit rate. LRU-K menargetkan polusi pemindaian; Redis menggunakan aproksimasi LRU sampel dan PostgreSQL menggunakan clock-sweep, sehingga biaya dan perilakunya tidak boleh disamakan.

Kesalahan umum

• Menyimpan satu stempel waktu dan secara tidak sengaja mengimplementasikan LRU biasa.
• Memperlakukan akses terbaru sebagai akses ke-K paling baru.
• Menghapus root heap tanpa menangani node basi yang duplikat.
• Membiarkan panggilan put konkuren melebihi kapasitas atau memperbarui riwayat di luar lock.
• Mengklaim LRU-K selalu mengalahkan LRU.

Pertanyaan lanjutan dan tanggapan

Apa yang harus terjadi jika K sama dengan 1?

Akses pertama memberikan semantik panas pada entri, sehingga pengeluaran diurutkan berdasarkan akses terbarunya dan kebijakannya tereduksi menjadi pengurutan LRU biasa.

Bagaimana Anda dapat mengurangi memori node heap?

Gunakan indeks dan heap yang dapat diubah untuk mengurangi node duplikat, atau pilih antrean generasi (generational queues) atau pengeluaran berdasarkan sampel. Nyatakan bahwa pengurutan menjadi perkiraan (aproksimasi) dan ukur ulang hit rate.

Bagaimana Anda mengukur pengurangan polusi pemindaian?

Buat set panas siklik, lalu masukkan banyak kunci yang hanya diakses satu kali. Bandingkan LRU dan LRU-K pada hit rate set panas, pengeluaran, latensi, dan memori, termasuk set panas yang mendekati kapasitas.