RwHash: Rewritable Hash Table for Fast Network Processing with Dynamic Membership Updates
Tian Song, Yating Yang, Patrick Crowley · 2017
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.