Show HN: CaskDB – project to teach you building a key value store | Hacker News Reader

Show HN: CaskDB – project to teach you building a key value store

github.com

175 pointsavinassh12 comments

Hey HN! For the past few months, I have been learning about the internals of database systems. After doing a batch at Recurse Center (Nov 2021) researching databases, I have been working on writing my toy database. I found many excellent articles on building compilers, but I could not find many practical resources for databases. CaskDB is the project I wish I had started with.

CaskDB is based on Riak's Bitcask paper. The idea of Bitcask is brilliant yet straightforward, which makes it attractive for newbies to learn about key-value store internals and implement one.

I have set up this project in TDD fashion with the tests. So, you start with simple functions, pass the tests, and the difficulty level goes up. There are hints if you get stuck (e.g. https://github.com/avinassh/py-caskdb/blob/e0819f7/format.py...). When all the tests pass, in the end, you would have written a persistent key-value store.

I had great fun implementing this, and I hope you do too. And I hope this makes you dig deep into the fantastic world of database engineering.

link - https://github.com/avinassh/py-caskdb

Nice! A (really terrible) Bitcask implementation was one of the first things I ever wrote in Go (https://github.com/pandemicsyn/bitcasket). Had no clue wtf i was doing but the Riak bitcask paper was clear enough that I was able to at least make a go of it. That whole experiment sent me on a different career trajectory - and was key to me switching from Devops/SRE style career path to a dev path.

Yes! bitcask paper is straightforward to read and understand. The idea of bitcask was suggested to Riak's devs when Eric Brewer (of CAP theorem fame) joined Riak's board:

> None of the local key/value storage systems available were ideal with regard to all of the above goals. We were discussing this issue with Eric Brewer when he had a key insight about hash table log merging: that doing so could potentially be made as fast or faster than LSM-trees.

(from the paper)

> That whole experiment sent me on a different career trajectory - and was key to me switching from Devops/SRE style career path to a dev path

How did it go? Do you have any suggestions/insights to share? I am also hoping to make a career transition from backend dev to database dev down the line.

In short, keys are stored in a hash table in RAM, k/v pairs are written to log files. Dead simple, but powerful enough.

I hadn't heard about bitcask before. Its design looks like a great alternative to LSM trees or B+trees like lmdb. Are there any good benchmarks comparing the approaches?

The introductory whitepaper on bitcask's design is here: https://riak.com/assets/bitcask-intro.pdf

I am not aware of any benchmarks with rocksdb (LSM) or lmdb (b-tree), but theoretically it will be much faster at the cost of extra RAM

- In Bitcask, reads have at most single seek. Writes are just append

- LSM - writes are just append, but reads are slower. Like in rocksdb, it has to check multiple files for the key

- B Tree - both read/writes require multiple seeks

Bitcask is that middle ground gives best of both, but takes up more RAM since it has to store all the keys.

Riak also provides a memory calculator - https://docs.riak.com/riak/kv/latest/setup/planning/bitcask-...

The other downside of Bitcask is that it requires periodic compaction operations to avoid continuously increasing disk utilization. LSM trees and B+Trees do this work "on the fly".

I'm not sure how big a downside that is in practice, but it might be unfair to compare lmdb or rocksdb with bitcask if bitcask is never compacting.

LSM also requires periodic compaction, right?

> I'm not sure how big a downside that is in practice, but it might be unfair to compare lmdb or rocksdb with bitcask if bitcask is never compacting.

Bitcask also does compactions, they call it merge. It is mentioned in the paper too, but not much in detail.

Nice project! I have been studying system design recently and read a lot about Dynamo, Cassandra, Kafka, etc. and I realized that they have much more in common than I thought. I'm mainly learning for system design interview, but I plan to do some implementation myself after getting a new job. So I might use this repo as a starting point! Thanks for the effort OP

That is some thorough documentation!

This looks excellent!

Nit: Typo in the hyperlink to the paper.

Thank you, fixed the typo.

Reply on news.ycombinator.com