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

摘要

Ludo Hashing is a key-value lookup design for networked and distributed systems such as packet forwarding and distributed storage. Ludo costs the least space (3.76 + 1.05l bits per key-value item for l-bit values) among known compact lookup solutions and supports fast lookups, fast updates, and concurrent writing/reading. The experimental results show that 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 over 65 million queries per second on a single node with multiple threads.