Bucket-Based Expiration Algorithm: Improving Eviction Efficiency for In-Memory Key-Value Database
Published in The International Symposium on Memory Systems (MEMSYS) 2020, 2020
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.
Recommended citation: https://dl.acm.org/doi/10.1145/3422575.3422797