Fastest ordered key value store?
Added 2018-02-04 23:42:01 +0000 UTCBased on all the numbers I've seen, it looks like bcachefs's b-tree might actually be the fastest ordered key value store around (there are faster persistent hash tables).
If anyone knows of anything that might be faster, I'd love to hear it - and I might rig up some head to head benchmarks.
Comments
No, it's heavily optimized for writes. If you look at the benchmarks, we can do almost half as many random _updates_ per second as we can random _lookups_ - that's seriously impressive, in my opinion. Fractal trees and other compacting data structures ought to beat bcachefs's b+ tree on random updates when the index no longer fits in RAM - but the thing is, in practice if your working set doesn't fit in RAM and you care about performance you're going to buy more RAM anyways.
Kent Overstreet
2018-02-05 10:07:26 +0000 UTCbcachefs' b-tree isn't a write-optimized one, right? In this case, I'd expect indices like Fractal tree index (in use by Percona TokuDB currently) to be significantly faster on random-insertion benchmarks. I'd be interested to know more about the techniques you used btw. Excited to see this progress!
2018-02-05 09:48:38 +0000 UTCI really like to learn them!
2018-02-05 01:40:23 +0000 UTCThat's what I was curious about. I do devops and maintain a few web apps that have simple key value stores. Thanks!
2018-02-04 23:56:15 +0000 UTC(can't do multiple paragraphs on mobile, wtf) Also, it wouldn't be out of the question to turn bcachefs's b+-tree into a general purpose key value store - the code is already mostly structured that way and it builds in userspace
Kent Overstreet
2018-02-04 23:54:16 +0000 UTCMainly? It's bragging rights! And, it'd be motivation to write about the techniques it uses so perhaps other people could learn from them.
Kent Overstreet
2018-02-04 23:50:18 +0000 UTC
