IcebergHT · SALT Systems Lab

Overview

IcebergHT is a fast, concurrent, and resizable hash table for 64-bit keys and values. It supports insertions, deletions, and queries.

Iceberg hashing is the first hash-table design to be both stable (items stay where they are first placed) and low-associativity (each item can live in only a few places). That combination keeps operations cache- and I/O-efficient, both in DRAM and on persistent memory.

Key features

Stable and low associativity

The first hash-table design with both properties.

Concurrent and resizable

Scales across threads and grows in place.

Persistent memory

Optional PMEM build.

Vectorized

Uses vector instructions to speed up operations.

API and build

iceberg_insert(key, value);     // insert a key-value pair
iceberg_get_value(key);         // look up a value
iceberg_remove(key);            // remove a key

$ make main && ./main -s 24 -t 4                        # 2^24 slots, 4 threads
$ PMEM=1 make main && ./main -p /path/to/pmem -s 24 -t 4

Citation

@article{pandey2023iceberght,
  author  = {Prashant Pandey and Michael A. Bender and Alex Conway and Mart{\'\i}n Farach-Colton
             and William Kuszmaul and Guido Tagliavini and Rob Johnson},
  title   = {IcebergHT: High Performance Hash Tables Through Stability and Low Associativity},
  journal = {Proceedings of the ACM on Management of Data},
  volume  = {1},
  number  = {1},
  year    = {2023},
  doi     = {10.1145/3588727}
}