7 ms·
Build your own fast, persistent KV store
- abadger9 4y agoThank YOU! I have literally been looking for something like this to try to build a rocksdb-like project for fun. I've been waiting to pull the trigger on YC's code crafters (https://codecrafters.io/ https://codecrafters.io/) which have you build your own redis and mysql-lite compatible db. Looking forward to going through this.
- dineshgowda24 4y agoHey, thank you. If you are blocked on anything, check out the GitHub repo I have added to the article. It has all the working code. TIL about code crafters. Looks promising; I will check it out.
- packetslave 4y agoBuilding a distributed RocksDB-based system is also a fun project... and practical, too! Large swaths of Facebook services are built on top of ZippyDB, which is basically "distributed RocksDB as a service"
- LAC-Tech 4y agoI'd be curious to hear more about this. KV stores as a basis for distributed databases are really interesting.
- yawgmoth 4y agohttps://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/ https://www.igvita.com/2012/02/06/sstable-and-log-structured... May be of interest to you
- packetslave 4y agoHere's a FB engineering blog post from 2021 that covers ZippyDB pretty well. https://engineering.fb.com/2021/08/06/core-data/zippydb/ https://engineering.fb.com/2021/08/06/core-data/zippydb/
- itsmemattchung 4y agoThis might interest you as well: https://github.com/emichael/dslabs https://github.com/emichael/dslabs That distributed systems lab is what Georgia Tech's Distributed System lab[0] is based on, at least when I took the course back in 2021 [0] - https://omscs.gatech.edu/cs-7210-distributed-computing https://omscs.gatech.edu/cs-7210-distributed-computing
- dineshgowda24 4y agoJust went through the course syllabi. This is something I have been looking for a long time. Thank you.
- robbs 4y agoBuilding your own database is a great exercise. There's lots of topics to explore, like distributed computing, how indexes work, caching, parsing, etc and you can pick and choose what to implement.
- ignoramous 4y agoStrictly speaking, building a database is more system engineering than distributed computing, but folks skip right past that when they opt to use "boltdb" or "rocksdb" or "innodb" and so on.
- bachmeier 4y agoNot sure why "toy" was added to the title. It's not part of the title of the post, nor should it be.
- dineshgowda24 4y agoNoted. Updated the title.
- samsquire 4y agoI wrote a simple dynamodb style database with a python dictionary and a Google pygtrie ("trie" data structure) It's still a toy but I kept adding features. I then kept working on it and added distribution with consistent hashing, rudimentary SQL joins, Cypher graph database queries and document storage. You can even query documents with SQL. I didn't get around to changing the graph storage to be multimodal. It takes very little code to write something with lots of features. https://GitHub.com/samsquire/hash-db https://GitHub.com/samsquire/hash-db There's an AVL tree that farleyknight wrote and a btree that I wrote that need to be integrated into it.
- cabalamat 4y ago> "trie" data structure How is that word pronounced? If it's pronounced "tree", it clashes with the name of another data structure. But if it's pronounced "try", it clashes with the name of a reserved word in many languages.
- Volt 4y agoIntended to be like "tree", usually pronounced "try".
- moosedev 4y agoMinutes of fun to be had in trying to pronounce it at the precise midpoint of however you pronounce "tree" and "try". (That word breaks my brain, too - the above is a coping mechanism.) In the past I recall reading/hearing "trie-tree" (pronounced "try tree") as an ambiguity reducer, but I don't know how common that is now, or ever was.
- meling 4y agoI usually pronounce it as “try”, as I think I’ve heard others do the same, but I’m non-native English speaker so don’t take my word for it ;-)
- CornCobs 4y agoI've heard before that it's meant to be re-TRIE-val and therefore is pronounced "tree"
- megiddo 4y ago[flagged]
- simscitizen 4y agoDepends on whether the author is pedantic about the use of GB vs. GiB.
- JustSomeNobody 4y agoRead the rest and see. good grief.
- vitiral 4y agoHow are the keys indexed and looked up? How does it handle disk fragmentation? This has always seemed to me to be one of the harder problems with databases.
- bob1029 4y agoI've built an append-only scheme where the on-disk format consists of 1 gigantic splay tree with updates being written as a modified sub-tree. The last element you write to disk is always the (latest) root node. Append-only implicitly solves most disk fragmentation concerns. It also has GC capabilities by having the physical log divided into multiple files. The actual "cleanup" is simply taking an old file and feeding its items into the storage engine again. The heuristics for determining when to do this are based upon statistics collected at insert/update time. Assuming the root node knows how to find the various things you are looking for (i.e. physical offsets to child nodes), this is how you can address the storage. The trickiest part is finding the latest root node in adverse scenarios (i.e. plug pulled/partial write to disk). You can develop some 2-tier system where a 32-bit magic cookie is scanned for in blocks from back to front, and once it is encountered the relevant offsets are applied and the candidate attempts deserialization+checksum. No partial writes can be recovered in this scheme and wind up as wasted bytes in the log. At some point I had intended to use this for a work project, but then SQLite came in and ruined my little party.
- azurelake 4y agoIf you want to read about an option that doesn't suffer from fragmentation (no pedantic replies please), check out LSM Trees which are what RocksDB uses. Designing Data-Intensive Applications has a VERY clear and understandable chapter about them. Once you've finished reading it, you'll have the tools to whip together a toy implementation for something like this.
- deleted 4y ago[deleted]
- vitiral 4y agoThanks!
- itsmemattchung 4y agoIf building a distributed KV store interests you, you might want to check out Georgia Tech's OMSCS Distributed Computing course: https://omscs.gatech.edu/cs-7210-distributed-computing https://omscs.gatech.edu/cs-7210-distributed-computing . While rewarding, this class was hell and still gives me nightmares.... By the way, the course is built on top of Distributed System's lab: https://github.com/emichael/dslabs https://github.com/emichael/dslabs
- MooseBurger 4y agoGoing through this class now, and I can attest that it is in fact tough as hell. However, I already feel as if it will be the most rewarding learning experience in the entire program.
- ddlutz 4y agoAny way to watch the lectures while not a current GT student? I'm an alumni on the OMSCS, but this course was not available before I graduated.
- codr7 4y agoI've built several versions of a log based db with composite keys over the years, the most complete version so far in Common Lisp: https://github.com/codr7/whirlog https://github.com/codr7/whirlog I've found that reinventing wheels is a great way to learn, even if you never use them.
- mr-karan 4y agoI recently implemented the Bitcask paper in Golang and shared my learnings: https://mrkaran.dev/posts/barreldb/ https://mrkaran.dev/posts/barreldb/ https://github.com/mr-karan/barreldb/ https://github.com/mr-karan/barreldb/ Bitcask is an excellent paper that is not overwhelming to understand and offers a great stepping stone in building your own data stores. The simple yet powerful design of an append only file is eloquent and performant. I’d love to read about more such implementations, if anyone has any recommendations.
- whartung 4y agoIs there an elegant solution to the garbage collection problem that append only DBs have to deal with?
- mr-karan 4y agoI think what bitcask proposes (to routinely collect datafiles and mark them as stale and GC them later) is quite a simple solution. It would work for a lot of usecases.
- yencabulator 4y agoThis is most exhaustively talked about in the context of Log-Structured Merge Trees, like LevelDB and RocksDB. They essentially structure the append-only/write-once chunks into tiers of generations (each compaction shifting the still-alive data to a more long-lived tier), reminiscent of generational GC except now shaped like a tree. https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Log-structured_merge-tree https://en.wikipedia.org/wiki/Tracing_garbage_collection#Generational_GC_(ephemeral_GC) https://en.wikipedia.org/wiki/Tracing_garbage_collection#Gen...
- artificial 4y agoIn a similar vein is Distributed Services with Go[0]. It's book available at pragprog (and on Oreilly, formerly Safari) that walks through creating a distributed log using key value storage and raft consensus. I found it very helpful as a practical Go project that gets you hands on with grpc, docker, and tests. [0] https://pragprog.com/titles/tjgo/distributed-services-with-go/ https://pragprog.com/titles/tjgo/distributed-services-with-g...
- dineshgowda24 4y agoI have read this book. The hands-on section is what I loved about the book. In our previous org, we had a state machine that implemented consensus using Raft.
- lakomen 4y agoI wrote a distributed kv store. kv is simple shit. idk why there's so much fuss about it. k=v it doesn't get simpler than that
- alpb 4y agoThis reminded me of Terry A. Davis, thanks, got a good giggle out of it.
- cabalamat 4y agoI'm writing Quickiebase[1], a NoSQL database with an API similar to MongoDB. it has a roadmap: https://github.com/cabalamat/quickiebase/wiki/roadmap https://github.com/cabalamat/quickiebase/wiki/roadmap [1]: https://github.com/cabalamat/quickiebase https://github.com/cabalamat/quickiebase
- didgetmaster 4y agoThe title describes the KV store as being both persistent and fast. There is a quite a bit of information about the persistent part, but no mentions of actual speed. How fast can you store 10 million integers mapped to keys using this? 10 million strings? Doubles? other data types?
- mvuksano 4y agoI like how the author says "fast" kV store but puts no performance analysis. From looking at the implementation and just making a guess this looks like is a very slow KV store. If you need a fast and performant kV store stick to RocksDb or LevelDb. Don't reinvent the wheel. Most of performance comes from optimizing for OS and CPU.
- human 4y agoSometimes you just want to have fun. But I agree, I don’t know why he suggests it would be fast…
- zambal 4y agoBitcask was a storage engine created by basho for their riak db (dynamodb like distributed db). The other storage engine riak could use was google's levellb. At the time bitcask was as fast or faster than leveldb for most tasks. This was I think around 2010. I have no idea how it compares with a recent version of rocksdb, but at the time it was pretty fast.
- iampims 4y agoOne big limitation of Bitcask is that all keys must fit in memory. Still my favorite format for simple KV.
- avinassh 4y agoI am a big fan of Build Your Own X educational projects. Recently, I released a Go version of my build your own KV Store project. 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. When all the tests pass, you will have written a persistent key-value store. go - https://github.com/avinassh/go-caskdb https://github.com/avinassh/go-caskdb python - https://github.com/avinassh/py-caskdb https://github.com/avinassh/py-caskdb
- sarupbanskota 4y agoVery well-explained. Shameless plug, we've got an interactive Build your own Redis and Build your own SQLite module on CodeCrafters, which subscribes to the same learning philosophy https://codecrafters.io/redis https://codecrafters.io/redis & https://codecrafters.io/sqlite https://codecrafters.io/sqlite