Saya sedang memikirkan bagaimana penyimpanan nilai kunci saat ini menerapkan "tanggal kedaluwarsa" untuk item. Saat ini saya memiliki 2 varian untuk itu dalam pikiran saya:
- mereka tidak melakukan apa-apa (menyimpan data kadaluarsa), dan hanya memeriksa ketika Anda melakukannya, misalnya, DAPATKAN oleh beberapa kunci. Masalahnya di sini adalah bahwa jika Anda terbatas dalam memori, item kadaluarsa tidak akan dihapus.
mereka menyimpan struktur data tambahan untuk bisa "paling awal untuk kedaluwarsa". Saya melihat hal itu dapat dilakukan dengan sesuatu seperti ini:
storage_data = dict(key -> [value, expire_timestamp]) expire_tree = SomeBinaryLikeTree(expire_timestamp -> [keys])
sumber
Saya menganggap penyimpanan kunci-nilai terlalu besar untuk hanya mengulangi semua pasangan kv untuk mencari tahu mana yang dapat kedaluwarsa. Saya juga berasumsi bahwa setiap akses baca menyegarkan stempel waktu kedaluwarsa, jadi hanya item yang belum diakses selama beberapa waktu yang kedaluwarsa.
Tantangannya adalah untuk secara efisien menemukan semua catatan yang dapat kedaluwarsa (setiap kali pembersihan harus dilakukan), tetapi juga secara efisien menyegarkan cap waktu kedaluwarsa pada setiap akses baca (jadi kita harus menemukan kunci dalam struktur yang digunakan untuk kedaluwarsa).
Proposal saya: kelompok expiry_timestamps ke dalam ember; misalnya, jika barang hidup selama 8 jam, buat satu ember per jam. Ember itu disimpan dalam daftar tertaut; ketika kedaluwarsa terjadi, ember pertama dikosongkan dan daftar berkurang. Jumlah bucket adalah rentang umur / pembersihan. Setiap ember berisi hashSet dari semua kunci yang harus kadaluwarsa. Iterasi atas semua kunci dalam hashset cukup efisien.
Selama akses baca, program memeriksa ember mana yang saat ini menjadi kunci dan ember mana yang sekarang menjadi miliknya. Dalam kebanyakan kasus, ini adalah ember yang sama, jadi tidak ada tindakan lebih lanjut yang diperlukan. Kalau tidak, hapus kunci dari ember lama (menghapus dari hash set efisien) dan masukkan ke dalam ember baru.
sumber