My LSM tree was slower than a B-tree. Then I profiled it
aasheesh.vercel.app
My LSM tree was slower than a B-tree. Then I profiled it
1–10 of 33 posts
Re: My LSM tree was slower than a B-tree. Then I profiled it
#2Writing to disk for every write is required, otherwise you're not durable.
Sure it's faster to never write to disk, then you reboot and you've lost data.
/dev/null is a webscale database that is even faster!
Re: My LSM tree was slower than a B-tree. Then I profiled it
#3Writing to disk for every write is required, otherwise you're not durable. Sure it's faster to never write to disk, then you reboot and you've lost data. /dev/null is a webscale database that is even faster!
read the whole article. WAL is the transaction log and the author tested correctness after a crash.
Re: My LSM tree was slower than a B-tree. Then I profiled it
#4> A 100-bit bloom filter holding 100,000 keys is saturated instantly. Every bit is set. It returns “maybe present” for every key you ask about — which means it filters nothing, and every read falls through to a full file scan.
Hahaha. (Seems like the bloom filter library isn't set for maximum false positive rate and/or to autoexpand.)
Edit: Actually there's a BloomFalsePositive setting, maybe it never gets used? Also maybe it's not a library and it's a custom implementation.
Re: My LSM tree was slower than a B-tree. Then I profiled it
#5Writing to disk for every write is required, otherwise you're not durable. Sure it's faster to never write to disk, then you reboot and you've lost data. /dev/null is a webscale database that is even faster!
read the whole article. WAL is the transaction log and the author tested correctness after a crash.
"Every batch of writes called file.Write on the write-ahead log"
You don't write to the WAL on a batch.
> the author tested correctness after a crash.
You mean the LLM?
Re: My LSM tree was slower than a B-tree. Then I profiled it
#6Your right should go into a queue and get compacted later on?
That's what Cassandra does iirc
Re: My LSM tree was slower than a B-tree. Then I profiled it
#7> A 100-bit bloom filter holding 100,000 keys is saturated instantly
> This is the kind of bug you only find by building the thing and measuring it.
No? I mean, maybe if you're vibecoding it's the only way, but in the prehistoric days you could reason about what code would do before you ran it.
Re: My LSM tree was slower than a B-tree. Then I profiled it
#8> A 100-bit bloom filter holding 100,000 keys is saturated instantly. Every bit is set. It returns “maybe present” for every key you ask about — which means it filters nothing, and every read falls through to a full file scan. Hahaha. (Seems like the bloom filter library isn't set for maximum false positive rate and/or to autoexpand.) Edit: Actually there's a BloomFalsePositive setting, maybe it never gets used? Also…
I guess you've never made a silly mistake, found it, and admitted it.
The author wrote this as a learning exercise. And is sharing the process.
Re: My LSM tree was slower than a B-tree. Then I profiled it
#9> A 100-bit bloom filter holding 100,000 keys is saturated instantly > This is the kind of bug you only find by building the thing and measuring it. No? I mean, maybe if you're vibecoding it's the only way, but in the prehistoric days you could reason about what code would do before you ran it.
Mistakes are always easy to recognize in retrospect, so hopefully this comment isnt too unfair, but one thing that caught me about this, is that logically it makes no sense. You would never use a bloom filter for just 10 entries. If you have only 10 entries it is almost certainly faster to skip the bloom filter. So i feel like that is the part that should have instantly stood out.
[Obviously, i've made my own silly mistakes over the years, many much sillier than this, its just weird to describe this one as only detectable by profiling]
Re: My LSM tree was slower than a B-tree. Then I profiled it
#10The article doesn't link to it but this appears to be the repo in question: https://github.com/AasheeshLikePanner/lsm-tree-go
I'm very amused by this obviously AI-generated "benchmark program": https://github.com/AasheeshLikePanner/lsm-tree-go/blob/main/...