Search⌘ K
AI Features
Home
Courses
System Design Deep Dive: Real-World Distributed Systems

A Write-friendly Store for SILT: Part II

Explore techniques for optimizing write-friendly key-value stores by using partial-key cuckoo hashing to reduce per-key memory usage and improve hash table occupancy. Understand the insertion process, displacement limits, and how tagging keys by alternate buckets prevents costly disk reads. Learn how these methods enable scalable, low-latency stores in distributed systems.

We'll cover the following...

Indexing for reduced per-key memory consumption

Since this store contains the least amount of keys, the overall impact of using the hash table on per-key memory consumption will be low. However, since reduced per-key memory consumption is our goal, we should find ways to reduce the impact of the above hash table. We can reduce per-key memory used by the write-friendly store by:

  1. Ensuring high occupancy of the hash table

  2. Using a partial key instead of the full key

Partial-key cuckoo hashing for higher occupancy

The technique we will use for hashing is partial-key cuckoo hashing. The partial-key means we will use a part of the key.

Hash functions

Cuckoo hashing requires two hash functions, h1, and h2. Both map a key K to two candidate buckets, h1(K) and h2(K), on the same table.

Insertion algorithm

To insert a new key, K1, we will compute its candidate buckets h1(K1) and h2(K1) and check if one, both, or none of the two buckets are empty.

  1. If both buckets are empty, store K1 in one of the buckets.

  2. If one bucket is empty, check if K1 is stored in the occupied bucket.

    1. If K1 is already stored, update the offset. ...