RwHash: Rewritable Hash Table for Fast Network Processing with Dynamic Membership Updates

Hash table is one of the most fundamental and critical data structures for membership query and maintenance. However, the performance of a standard hash table degrades greatly when the hash collision is large due to high load factor or unpredictable dynamic membership updates, especially per-packet updates in network processing. In this paper, we shape a hash table from the conventional slim-and-tall style to a wide-and-short style by facilitating an extension of logical cache block. Then, a cache aware hash table (CaHash) is given and explored in detail. Based on an observation that the operation sequences may be in a potential and probabilistic successive order, especially for network applications, a rewritable hash table (RwHash) is finally proposed, which provides two rewritable policies to dynamically move elements within a bucket when updating. Theoretical analysis shows that, no matter what load factor and collision are, RwHash can achieve near-optimal performance the same as the performance when a standard hash table in the case of no collision. Real experiments show that RwHash can achieve 4.10 times speedup in some parameter and even more with different configurations than a standard hash table in the case of heavy collisions. Our approaches are elegantly practical in implementation for both software and hardware.