Bucket-Based Expiration Algorithm: Improving Eviction Efficiency for In-Memory Key-Value Database
Guochao Xie, Yeh‐Ching Chung · 2020
Evicting expired keys for an in-memory key-value database is essential to save its memory resources and control its memory usage not exceeding its memory limit. Existing randomized expiration algorithms randomly sample keys from the key space associated with expiration, evict all expired ones and proceed to the next iteration if the proportion of expired keys exceeds a pre-defined threshold. The randomized algorithm has been adopted by Redis currently.