YogaDB: an interesting B-tree variant, 2x faster than LSM trees at writes

[Jason E. Aten]

I thought this was an interesting systems design paper from 2022: https://www.roychan.org/assets/publications/eurosys22chen.pdf

"Building an Efficient Key-Value Store in a Flexible Address Space", by

Chen et al at the University of Illinois, Chicago. Eurosys 2022.

They claimed their design, expressed in a small C library, got performance 2x better than RocksDB (a highly tuned, state of the art, Log-structured merge-tree key/value store produced by Meta/Facebook based on the LevelDB design originally).

wow. That caught my attention.

And they had C code that built (a rarity among research projects, sigh). 

But C... Ugh. I ported it to Go. 

Turns out those performance number... were actually pretty spot on... and have a strong theoretical stand.

original C: https://github.com/flexible-address-space/flexspace

my Go: https://github.com/glycerine/yogadb

Compared to CockroachDB's Pebble (a LSM tree in Go), YogaDB (also pure Go) is 20x faster at reads and 2x faster at writes than Pebble.

Compared to BoltDB (a copy-on-write memory mapped B-tree in Go based on Howard Chu's Lightning Memory-mapped Database C design), YogaDB has comparable reads (sometimes even a little faster) and 20x faster writes than Bolt.

Enjoy,

Jason

p.s. I did a nice little virtual file system layer to test fsync durability and the recovery path. You can find that here: https://github.com/glycerine/vfs It is a fork of Pebble's vfs with a bunch of missing os package APIs fleshed out. Testing fully in memory with "go test -v -tags memfs" is about 7x faster than using the actual disk.