Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems

Appeared in Proc. of ACM SIGMETRICS 2020.

Abstract

Key-value lookup engines running in fast memory are crucial components of many networked and distributed systems such as packet forwarding, virtual network functions, content distribution networks, distributed storage, and cloud/edge computing. These lookup engines must be memory-efficient because fast memory is small and expensive. This work presents a new key-value lookup design, called Ludo Hashing, which costs the least space (3.76 + 1.05l bits per key-value item for l-bit values) among known compact lookup solutions including the recently proposed partial-key Cuckoo and Bloomier perfect hashing. In addition to its space efficiency, Ludo Hashing works well with most practical systems by supporting fast lookups, fast updates, and concurrent writing/reading. We implement Ludo Hashing and evaluate it with both micro-benchmark and two network systems deployed in CloudLab. The results show that in practice Ludo Hashing saves 40% to 80%+ memory cost compared to existing dynamic solutions. It costs only a few GB memory for 1 billion key-value items and achieves high lookup throughput: over 65 million queries per second on a single node with multiple threads

Publication date:
June 2020

Authors:
Shouqian Shi
Chen Qian

Projects:

Available media

Full paper text: PDF
Presentation: video

Bibtex entry

@inproceedings{Ludo-hashing,
  author       = {Shouqian Shi and Chen Qian},
  title        = {Ludo Hashing: Compact, Fast, and Dynamic Key-value Lookups for Practical Network Systems},
  booktitle    = {Proc. of ACM SIGMETRICS 2020},
  month        = jun,
  year         = {2020},
}