Key positioning clarification

[delaneyj]

Since it's not documentation, when a key is retrieved is it rewritten to the memtable (so oldest keys live in the lowest level)? Basically does it act as an lru or do key live at the level they were original written?

[guycipher]

L0 - Memtable (latest version if key resides)
L1+ - if not found in memtable we check from first level (where we flush) to last. Where ever we find that key we stop. In regards to range and filters we don't supersede if existent in result set.

[guycipher]

On compactions older keys living in older levels are merged with new levels. Only the latest version will live on, if tombstoned, it is deleted.

[guycipher]

Should probably write this up on documentation somewhere and on website with some nice images! For sure :) I will do that when I get some time after work, most certainly. I appreciate the questions @delaneyj

[guycipher]

This phenomenon is called write amplification. When a key lives in multiple levels. Over time compactions try to rid this.

[delaneyj]

I grok the write amplification, just wanted to see if once a key is written it's not going to percolate back up with retrievals. If you have iterators #26 it's less of a concern.

[guycipher]

Understood. Yeah I get it. Equality operations will be quicker because the bloom can identify if key sits in an sstable klog. Doesn't have to scan a bunch of times. in regards to iterator functions, yeah you could use a min and max key per sstable but then you'd have to store those somewhere and what if keys are large? So that's the thing with that, memory efficiency. There are other types of filters that allow searching ranges as well. Could be looked at. https://db.cs.cmu.edu/papers/2019/20_srf-zhang.pdf

[guycipher]

Added info on read me.
#38