With an LSM, you tend to want to maintain an index of the ranges of keys that each sst block holds anyway. And for this block-first style, it does the same. But compaction becomes a bit more sophisticated, where range density can be more explicitly reasoned about. - ThreadSky

About ThreadSky

ak47.io • 182 days ago

With an LSM, you tend to want to maintain an index of the ranges of keys that each sst block holds anyway. And for this block-first style, it does the same. But compaction becomes a bit more sophisticated, where range density can be more explicitly reasoned about.

Comments

ak47.io•182 days ago

And one of the nice things is that it is fairly clean to bolt this onto a heap-backed B+tree to give it nice LSM-style asymptotics for random write workloads while still retaining optimal B+tree write amplification for sequential writes via the block gifting trick.

ak47.io•182 days ago

Compared to a Bw-Tree where you need to maintain pointers to every delta update that needs to be read along with the base page for a point lookup, this has a much lower metadata:data ratio, but that metadata is less specific, so filters are useful.

ak47.io•182 days ago

LSM, Bε, Bw trees all try to avoid moving data around until doing so can be amortized, with them forming a spectrum of how specifically a particular block/page can be rewritten in response to write locality. Plain LSM is locality blind. Bε rewrites data as it moves back. Bw is hyper local.

ak47.io•182 days ago

The thing that appeals to me about the heap-backed LSM block approach is that it gives you a way to decide at runtime how much effort you will spend compacting overlapping ranges in order to make the overall block index more specific, while avoiding copying unchanging blocks as a plain LSM would.

Posting Rules

Be respectful to others
No spam or self-promotion
Stay on topic
Follow Bluesky's terms of service

Comments

Posting Rules

Reply