Hash tables are an essential data-structure for numerous networking applications (e.g., connection tracking, firewalls, network address translators). Among these, cuckoo hash tables provide excellent performance by allowing lookups to be processed with very few memory accesses (2 to 3 per lookup). Yet, for large tables, cuckoo hash tables remain memory bound and each memory access impacts performance. In this paper, we propose algorithmic improvements to cuckoo hash tables allowing to eliminate some unnecessary memory accesses; these changes are conducted without altering the properties of the original cuckoo hash table so that all existing theoretical analysis remain applicable. On a single core, our hash table achieves 37M lookups per second for positive lookups (i.e., when the key looked up is present in the table), and 60M lookups per second for negative lookups, a 50 improvement over the implementation included into the DPDK. On a 18-core, with mostly positive lookups, our implementation achieves 496M lookups per second, a 45 improvement over DPDK.
MemC3 @cite_1 integrates additional functions into the hash table data structure. In the context of memcached, they replace two inter-dependant data structures, the first managing key value association, and the second keeping track of entries for providing LRU replacement by a single hash table integrating a CLOCK-based LRU eviction. The goal of this integration is to simplify software and to improve performance by reducing overhead, similarly to what we achieve by integrating timers directly into the hash table. Note that, entries are over-written thus providing a form of lazy deletion. Yet, this lazy deletion differs from lazy deletion in open-addressing hash table @cite_7 where entries are marked with a tombstone, which still required a memory access. In open addressing hash tables predating cuckoo hash table, these tombstones were useful to avoid costly restructuration of hash tables upon deletion.
@cite_1 @cite_7
83339351 2079527850
This paper presents a set of architecturally and workload-inspired algorithmic and engineering improvements to the popular Memcached system that substantially improve both its memory efficiency and throughput. These techniques--optimistic cuckoo hashing, a compact LRU-approximating eviction algorithm based upon CLOCK, and comprehensive implementation of optimistic locking--enable the resulting system to use 30 less memory for small key-value pairs, and serve up to 3x as many queries per second over the network. We have implemented these modifications in a system we call MemC3--Memcached with CLOCK and Concurrent Cuckoo hashing--but believe that they also apply more generally to many of today's read-intensive, highly concurrent networked storage and caching systems. Abstract We present new, improved algorithms for performing deletions and subsequent searches in hash tables. Our method is based on open addressing hashing extended to allow efficient reclamation of unoccupied space due to deletions which enables dynamic shortening of probe sequence lengths. We present an analysis on the number of table probes required to locate an element in the table. Specifically, we present a formula which bounds the average number of cells visited during searches of a data element over its lifetime assuming a system in equilibrium. The formula is a function of the probability that an accessed element is deleted and is exact at the extreme points when the probability is 0 and 1. In the case that the probability is 0 and the load factor is α, the number of cell visits per search access is − ln (1−α) α , and in the case that the probability is 1 the number of cell visits per search access is 1 (1−α) .