4 ms·

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

175 points by avinassh 4y ago

avinassh 4y ago
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#L42 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 https://github.com/avinassh/py-caskdb
ofpiyush 4y ago
That is some thorough documentation!
dandanua 4y ago
In short, keys are stored in a hash table in RAM, k/v pairs are written to log files. Dead simple, but powerful enough.
pandemicsyn 4y ago
Nice! A (really terrible) Bitcask implementation was one of the first things I ever wrote in Go (https://github.com/pandemicsyn/bitcasket 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.
- avinassh 4y ago
  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.
josephg 4y ago
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 https://riak.com/assets/bitcask-intro.pdf
- avinassh 4y ago
  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-capacity-calc/index.html https://docs.riak.com/riak/kv/latest/setup/planning/bitcask-...
  - josephg 4y ago
    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.
    - avinassh 4y ago
      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.
unmole 4y ago
This looks excellent! Nit: Typo in the hyperlink to the paper.
- avinassh 4y ago
  Thank you, fixed the typo.
kwizzt 4y ago
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
deleted 4y ago
[deleted]

175 points by avinassh 4y ago

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#L42 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 https://github.com/avinassh/py-caskdb

ofpiyush 4y ago

That is some thorough documentation!

dandanua 4y ago

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

pandemicsyn 4y ago

Nice! A (really terrible) Bitcask implementation was one of the first things I ever wrote in Go (https://github.com/pandemicsyn/bitcasket 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.

avinassh 4y ago
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.

josephg 4y ago

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 https://riak.com/assets/bitcask-intro.pdf

avinassh 4y ago
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-capacity-calc/index.html https://docs.riak.com/riak/kv/latest/setup/planning/bitcask-...
- josephg 4y ago
  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.
  - avinassh 4y ago
    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.

unmole 4y ago

This looks excellent! Nit: Typo in the hyperlink to the paper.

avinassh 4y ago
Thank you, fixed the typo.

kwizzt 4y ago

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

deleted 4y ago

[deleted]