Bucket-Based Expiration Algorithm: Improving Eviction Efficiency for In-Memory Key-Value Database
Published in The International Symposium on Memory Systems (MEMSYS) 2020, 2020
Recommended citation: https://dl.acm.org/doi/10.1145/3422575.3422797
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.
In this paper, we present a novel approach, a hybrid algorithm combining a deterministic one using buckets and a randomized one inherited from Redis expiration algorithm, to improve the efficiency of eviction of expired keys. For the main part, we adopt a deterministic algorithm to discretize the expiration timestamps into buckets and evict keys bucket by bucket; if time permitted, we also run the Redis expiration algorithm after finishing the deterministic part. Furthermore, our experiment using Redis randomized algorithm as the baseline shows that our algorithm is more effective in reducing memory usage with an acceptable impact on the overall throughputs.
Accepted by The International Symposium on Memory Systems (MEMSYS) 2020.
Recommended citation: Guochao Xie and Yeh-Ching Chung. 2020. Bucket-Based Expiration Algorithm: Improving Eviction Efficiency for In-Memory Key-Value Database. In The International Symposium on Memory Systems (MEMSYS 2020). Association for Computing Machinery, New York, NY, USA, 248–259. DOI: https://doi.org/10.1145/3422575.3422797.