Gesaan dan konteks
Laksanakan cache LRU-K berbatas yang menyokong get, put, dan penyingkiran. Simpan K akses paling terkini bagi setiap kunci. Entri dengan kurang daripada K akses membentuk peringkat sejarah tidak lengkap (history-incomplete tier) dan mesti disingkirkan sebelum entri hangat (hot). Jelaskan K, kapasiti, kemas kini kepada kunci sedia ada, panggilan serempak, dan kunci yang hilang.
Perkara yang diuji oleh penemu duga
- Sama ada anda mengekalkan sejarah akses dan dua peringkat calon dengan betul.
- Sama ada anda boleh memilih timbunan (heap), peta cincangan (hash map), atau struktur teratur serta menganalisis kosnya.
- Sama ada anda mengendalikan tulis ganti (overwrites), kapasiti sifar, K tidak sah, dan kebolehlihatan serempak.
- Sama ada anda memahami bahawa LRU-K menapis pencemaran imbasan (scan pollution) dan bukannya menang dalam setiap beban kerja.
Soalan penjelasan sebelum menjawab
Sahkan keselamatan benang (thread safety), penyingkiran anggaran, nilai boleh ubah, keperluan TTL, dan metrik kadar capaian (hit-rate). Susunan yang ketat biasanya memerlukan kunci (lock) atau kemas kini bersiri; daya pemprosesan (throughput) yang lebih tinggi mungkin memerlukan pemecahan (sharding) dan dasar anggaran.
Rangka kerja jawapan 30 saat
Simpan nilai, K cap masa logik terkini, dan versi bagi setiap kunci. Bahagikan calon kepada peringkat sejarah tidak lengkap dan peringkat hangat. Apabila melebihi kapasiti, singkirkan item paling lama dalam peringkat tidak lengkap; jika tiada, singkirkan item hangat dengan cap masa ke-K paling terkini yang terkecil. Peta cincangan memberikan carian O(1) dan timbunan mengekalkan calon; versi membuang nod timbunan lapuk (stale). get dan put yang ketat dijangka O(log n), dengan ruang sejarah O(capacity·K).
Penerangan mendalam langkah demi langkah
1. Merekod sejarah akses
Tambahkan nilai jam logik pada setiap capaian (hit) atau penulisan dan kekalkan hanya K nilai terkini. Jam logik membandingkan susunan tanpa lompatan jam dinding dan membezakan akses dalam milisaat yang sama. Tulis ganti dikira sebagai akses melainkan jika gesaan menyatakan penulisan tidak dikira.
2. Mengekalkan calon penyingkiran
Peringkat tidak lengkap disusun mengikut akses terbarunya; peringkat hangat mengikut akses ke-K paling terkininya. Kekalkan dua min-heap bagi (key, version, rank). Akses baharu menolak (push) nod baharu dan meningkatkan versi; penyingkiran mengesahkan versi dan kedudukan semasa, melangkau nod lapuk.
3. Sempadan dan keserempakan
Jangan lakukan cache apabila kapasiti adalah sifar atau negatif; tolak K apabila ia sifar atau negatif. Penyingkiran dan kemas kini nilai mesti berkongsi bahagian kritikal (critical section) supaya panggilan put serempak tidak boleh melebihi kapasiti. Kunci berpecah (sharded locks) meningkatkan daya pemprosesan, tetapi kapasiti global kemudiannya memerlukan penyelarasan.
Contoh jawapan berkualiti tinggi
Saya mengasingkan entri kepada peringkat sejarah tidak lengkap dan peringkat hangat. Setiap entri menyimpan nilainya, K masa logik terkini, dan versi; suatu akses mengemas kini sejarah dan menolak nod kedudukan baharu ke dalam min-heap yang berkaitan. Penyingkiran memeriksa timbunan tidak lengkap terlebih dahulu, kemudian timbunan hangat, mengesahkan versi untuk melangkau nod lapuk. Carian adalah O(1) melalui peta, kerja timbunan adalah O(log n), dan ruang sejarah adalah O(capacity·K). Ujian merangkumi K=1 yang berkelakuan seperti LRU, kenaikan pangkat selepas akses berulang, imbasan sekali sahaja, tulis ganti, kapasiti sifar, penulisan melebihi kapasiti secara serempak, nod timbunan lapuk, dan kadar capaian. LRU-K menyasarkan pencemaran imbasan; Redis menggunakan anggaran LRU bersampel dan PostgreSQL menggunakan clock-sweep, jadi kos dan tingkah lakunya tidak boleh dikelirukan.
Kesilapan biasa
- Mengekalkan satu cap masa dan secara tidak sengaja melaksanakan LRU biasa.
- Menganggap akses terkini sebagai akses ke-K paling terkini.
- Mengeluarkan punca timbunan (heap root) tanpa mengendalikan nod lapuk yang pendua.
- Membiarkan panggilan
putserempak melebihi kapasiti atau mengemas kini sejarah di luar kunci (lock). - Mendakwa bahawa LRU-K sentiasa mengatasi LRU.
Soalan susulan dan jawapan
Apakah yang sepatutnya berlaku apabila K bersamaan dengan 1?
Akses pertama memberikan semantik hangat kepada entri, jadi penyingkiran disusun mengikut akses terkininya dan dasarnya terturun kepada susunan LRU biasa.
Bagaimanakah anda boleh mengurangkan memori nod timbunan?
Gunakan indeks dan timbunan boleh ubah untuk mengurangkan nod pendua, atau pilih giliran generasi (generational queues) atau penyingkiran bersampel. Nyatakan bahawa susunan menjadi anggaran dan ukur semula kadar capaian.
Bagaimanakah anda akan mengukur pengurangan pencemaran imbasan?
Cipta set hangat berkitar, kemudian masukkan banyak kunci yang diakses sekali sahaja. Bandingkan LRU dan LRU-K pada kadar capaian set hangat, penyingkiran, kependaman (latency), dan memori, termasuk set hangat yang hampir dengan kapasiti.