This was originally posted on Dangling Pointers. My goal is to help busy people stay current with recent academic developments. Head there to subscribe for regular summaries of computer science research.
Zombie Hashing: Reanimating Tombstones in Graveyard Yuvaraj Chesetti, Benwei Shi, Jeff M. Phillips, and Prashant Pandey SIGMOD'25
The Problem with Tombstones
Linear probing hash tables are great, as long as you never want to delete an element. A trick for fast deletion is to replace the deleted element with a tombstone. Subsequent insertions treat tombstones as empty slots. Subsequent deletions treat tombstones as full (i.e., the delete algorithm continues probing).
Over time however, hash tables tend to fill up with tombstones, at which point deletions run slowly, which defeats the whole point of tombstones. One can fix this with occasional defragmentation (i.e., rebuild the hash table), but that negatively impacts tail latency (think of a stop-the-world-garbage collector).
This paper describes an approach which allows defragmentation without large periods of downtime during which defragmentation occurs.
Incremental Rebuilds
The incremental rebuild algorithm is:
Divide the hash table into a set of contiguous rebuild intervals
Designate an evenly spaced subset of table slots as primitive tombstone positions
After each insertion, rebuild one of the intervals
As long as there are many rebuild intervals (i.e., each rebuild interval is small), then the tax added to each insertion is tolerable.
The rebuild process starts at the first slot in an interval and iterates to the last slot in an interval. When a tombstone is encountered in a non-primitive position, it is moved (i.e., pushed) toward the end of the interval. As a tombstone is pushed toward the end of the interval, a few situations can happen:
If an empty slot is encountered and that slot is a primitive tombstone position, then the tombstone is left there
If an empty slot is encountered and that slot is not a primitive tombstone position, then the tombstone is removed
If a valid item is encountered and that item is not in its home position (i.e., the initial location where probing would start for that item), then that item is moved toward its home position
If a tombstone is pushed to the end of the rebuild interval, it is left there for a future rebuild operation to continue pushing it
That last point (leaving tombstones at the end of the rebuild interval) is the key to bounding the rebuild time for any interval.
Results
Table 3 contains throughput results, ZombieHT is the algorithm described in this paper. This algorithm shines for update-heavy workloads.
Source: https://dl.acm.org/doi/10.1145/3725424
Table 5 contains latency distributions. ZombieHT provides much lower worst-case performance for CRUD operations (see the rows in the table labeled 'Max').
Source: https://dl.acm.org/doi/10.1145/3725424
Dangling Pointers
This approach is great for reducing tail latency, but the throughput numbers make me think a dramatically different approach is out there to be found for some applications. The performance numbers were generated on a single core of a 2GHz Ice Lake CPU. The throughput numbers are single-digit mega-ops per second. That means each CRUD operation takes 200-1000 cycles. Large hash tables run into the memory wall, is there nothing to be done?
Another way to look at this is DRAM throughput. Assume each operation performs a single 64-byte memory access. With the throughput numbers in table 3, it looks like a single core uses 180-450MiB/sec of DRAM bandwidth, which seems low.
Top comments (0)