ACEKV: An In-Memory Key-Value Store with Optimized Cuckoo Insertion

In-memory key-value stores (IMKVs) are essential for large-scale web applications, providing rapid data access with low latency and high throughput. They typically adopt hash tables as the index data structure for fast data retrieval. As new items are continuously inserted into IMKVs, the index insertion of these items incurs a rising number of hash collisions, which in turn adversely affects the system’s performance. Although current IMKVs adopt various policies to mitigate hash collisions and avoid endless loops of reinsertion, they still suffer from high insertion latency and degraded performance. This paper presents ACEKV, an in-memory key-value store that leverages a cuckoo hash table optimized for efficient hash insertions. It proposes a kickCounter algorithm that prioritizes selecting a cuckoo path with infrequent access, which enables hash indexes to be evenly distributed in the hash table and effectively reduces the average length of the cuckoo path. Evaluation results show that the holistic design of ACEKV significantly enhances insertion efficiency and consistently achieves high performance under various workloads.