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

   2. Otherwise, store K1 in the empty bucket.

3. If neither bucket is empty, check if K1 is stored in one of the occupied buckets.

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

   2. Otherwise, K1 displaces K2 in one of the K1 candidate buckets. We will insert K2 into its other candidate bucket.

      1. If the other candidate bucket for K2 is empty, it is stored there.

      2. If the other candidate bucket is not empty, K2 displaces K3, which resides in its other candidate bucket.

      3. We will repeat the process in 3(II) for K3 until we find an empty bucket for a limited number of displacements. If we reach our allowed number of displacements and cannot find an empty bucket, we will initialize a new write-friendly store and store the displaced key in one of its candidate buckets in the new store.