Intermediary Store(s) in SILT

A write-friendly store will not add more entries beyond a certain point when the memory bound is reached or the store cannot find an empty bucket in the allocated number of displacements. Now, we will convert this store into a more memory-efficient immutable store. We will call this our intermediary store.

Why we need an extra store

Keeping data around in our completed write-friendly stores incurs high memory overhead due to the indices. On the other hand, if we merge a completed write-friendly log to the final (our most memory-efficient store, which uses sorting for compaction of keys), it might require an excessive movement of keys for merging and re-sorting. The intermediate store helps us find a reasonable middle ground between the above two bad options (high memory overhead if we keep a write-friendly log and possible movement of many keys on each log merging). In the following lesson, we will explain this situation in detail.

We will see later that our memory-efficient store will also be our largest store and keep our key-value pairs sorted. Due to the memory-efficient store's compact representation (one of the reasons why it is memory-efficient), it will be immutable (unchangeable). Frequently sorting our small write-friendly store's entries into our memory-efficient store will require a lot of rewriting and results in a higher write amplification.

Keeping many write-friendly stores before merging their entries will reduce write amplification. However, this increases memory use because of the write-friendly store's in-memory hash table.

Our multi-store approach allows us to solve this problem by introducing a new store between our write-friendly and memory-efficient stores. We will convert our write-friendly store to an intermediary store as soon as it stops accepting new entries. During the conversion, a newly initialized write-friendly store will serve PUT and DELETE requests.

This intermediary store will be immutable. As a result, we will have one intermediary store for every instance of a write-friendly store. This store will consume less memory than the write-friendly store for the same number of entries, ensuring lower memory use for accumulating entries before merging with the memory-efficient store, which is next in line.

Storing entries in hash order for reduced memory consumption

Transforming a write-friendly store to an intermediary store requires reordering the key-value entries in storage. Previously, in the write-friendly store, entries were stored in the order we received them (insertion order). Our conversion algorithm will rearrange the entries in the new intermediate store as per the order of their hash values—the order of the keys' hashes in the write-friendly hash table—and alleviate the need to store their offsets in memory.

Here is the conversion from the write-friendly store to the intermediary store in storage.