A Write-friendly Store for SILT: Part III
Learn how to design a key-value store for fast writing.
We'll cover the following
GET
requests
Since we are using a partial key, it is important to note how this will affect GET
requests. We will only proceed with a lookup for a GET
request if the tag matches the key in the request. By lookup, we mean lookup in storage. So, when the write-friendly store receives a GET
request for key Kg
:
It computes the candidate buckets
h1(Kg)
andh2(Kg)
and looks inside these buckets.Inside
h1(Kg)
, it looks for the tagh2(Kg)
. If the computed tagh2(Kg)
matches the tag inside bucketh1(Kg)
, then it looks up the entry in the storage log stored on the offset marked withh2(Kg)
.Inside
h2(Kg)
, it looks for the tagh1(Kg)
. If the computed tagh1(Kg)
matches the tag inside bucketh2(Kg)
, then it looks up the entry in the storage log stored on the offset marked withh1(Kg)
.
Upon a
in either of the two cases above, it looks up the key-value pair (in the storage log) at the offset marked with the computed tag:successful match computed tag matches tag in bucket (Ks, Vs)
. It then matches the keyKs
from the key-value pair returned from storage withKg
to confirm that we have looked up the correct key.If the keys match (
Kg
equalsKs
), we check the valueVs
in the key-value pair returned from storage.If
Vs
is not the specialDELETE
indicator (Vs
does not equal toDELETE
), the write-friendly store signals that theGET
request should terminate and return thatVs
is the value stored againstKg
.If
Vs
is the specialDELETE
indicator (Vs
equalsDELETE
), the write-friendly store signals that theGET
request should terminate and return thatKg
is not stored in the key-value store (the entire key-value store and not just the write-friendly store).
If the keys do not match (
Kg
is not equal toKs
), the write-friendly store signals thatKg
is not present inside the write-friendly store, and theGET
request should continue in the intermediary stores.
Upon an
in both candidate buckets, the write-friendly store signals thatunsuccessful match computed tag does not match tag in bucket Kg
is not present inside the write-friendly store, and theGET
request should continue in the intermediary stores. This is the case where our hash table acts as an in-memory filter. We have returned thatKg
is not stored inside the write-friendly store without checking the storage log.
Improving design for memory efficiency
We can further improve our design using the techniques mentioned below.
Memory bound
Although we have tried to keep per-key memory consumption low, this store will still take up more per-key memory than our other stores. Therefore, we will keep a memory cap beyond which this store will not grow. Once the store size becomes greater than or equal to this memory bound, we will initialize a new store and send the old one for conversion to an intermediary store. From this point, this new store will serve incoming requests.
One store
Since this store is relatively expensive in terms of per-key memory consumption, we will only have one instance of this store in our system at a time.
One consideration is that having more write-friendly stores could parallelize new requests. For example, consider having two write-friendly stores serving. If one of the stores is busy inserting a request, the other can serve requests. On average, requests are served faster than in a single write-friendly store.
We must consider that the hash table's memory is allocated as soon as the write-friendly store is initialized. The store's per-key memory consumption reduces as more and more keys are entered into the hash table.
With the two write-friendly stores, we are using twice the memory, and to make using the two stores worthwhile, we will have to ensure high occupancy of two stores rather than one store. These two stores will take longer to reach our desired occupancy. On average, our system will have more per-key memory consumption.
If we were going to give up per-key memory consumption in the first place, we could have kept a lower number of displacements before we initialized a new write-friendly store. This way average occupancy of the in-memory hash table would have been lower (higher per-key memory consumption), but the design would insert requests faster (on average).
While an argument for parallelization by having more than one store can be made, for now, it is important to understand that the trade-offs involved with having more than one write-friendly store are the same as with configuring a single write-friendly store.
What’s next?
When the condition to initialize a new write-friendly store is met, what happens to the old one? It is converted to another store that is easy to convert to our memory-efficient store. We’ll discuss this further in the next lesson.
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.