A Memory-efficient Store for SILT: Part I
Explore the design of SILT's memory-efficient store focusing on low per-key memory use and logarithmic lookup times. Understand how immutability and sorted key storage enable compact in-memory indexes, while trie-based indexing supports efficient access and scalability in key-value stores.
We'll cover the following...
Preamble
Memory efficiency is one of the core design goals for our key-value store. In previous lessons, we’ve enabled clients to write keys quickly (using our write-friendly store) by keeping the per-key memory consumption of our key-value store low. Our previous efforts were on stores we used to achieve other goals—fast sequential writing in the write-friendly store and accumulating intermediary stores for bulk merge to a memory-efficient store. In this lesson, we will make our most significant contribution to keeping memory-consumption low in the last-level store. Our goal will be to store the largest proportion of entries (80%) in our most memory-efficient store to ensure our design uses, on average, low memory per key.
We need our last-level store to be a memory-efficient store. Here’s a list of requirements for our last-level store:
Read-friendliness: This is essential because the last-level store will hold a large proportion of keys in our design. Chances are that most of the lookups will happen in this store.
...