Post

Lately I've been playing around with a new type of LSM storage engine that has some interesting properties. Most LSM implementations split the sst data into blocks. But what if those blocks were stored in a heap instead of a file, and compaction only happened on overlapping blocks? Kinda Bε-like.

While a naive Bε-tree still has the suboptimal LSM behavior on sequential writes of copying data several times from the tip to the leaf, this block-based LSM lets sequential writes immediately be "gifted" to the last "level" (but levels no longer exist as such).

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.

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.

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.