5 ms·
I actually ran into some of the same problems while trying to write a bw-tree implementation a couple of years ago. My naive implementation ended up having very
by d4l3k 8y ago
I actually ran into some of the same problems while trying to write a bw-tree implementation a couple of years ago. My naive implementation ended up having very poor performance compared to other in memory KV stores due to the inefficient busy waiting on contention. There were a few tricks that make it more efficient, but never got around to fleshing them out.
I guess I should have polished it up and wrote a paper about it.
If anyone is interested the code is available at https://github.com/d4l3k/skeletondb https://github.com/d4l3k/skeletondb
- ovao 8y agoInteresting work. In general, how does it perform compared to LMDB, BoltDB, Badger, etc.? What kind of performance increases would you expect from the optimizations you didn't get around to?
- d4l3k 8y agoThis was mostly just a toy project, I wouldn't recommend actually using it for anything. It's kind of depends when it comes to performance. A perfect implementation would likely get better performance than all those databases there since it resides entirely in memory. I'm not sure how it currently compares. The main thing that caused issues was that compaction of logs into the main tree conflicted with appends. This ended up causing a lot of thrashing since the compaction cycle would run a lot more than necessary. The key point of bw-trees is that once changes have been added to the log, only the last element will change (to point to the next item). Thus, instead of trying to compact the entire log, you can compact everything but the last item to make it conflict free.