A Write-friendly Store for SILT: Part II

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 ...