Build your own fast, persistent KV store | Hacker News Reader

Build your own fast, persistent KV store

dinesh.wiki

176 pointsdineshgowda2448 comments

I 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

There's an AVL tree that farleyknight wrote and a btree that I wrote that need to be integrated into it.

> "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.

https://en.wikipedia.org/wiki/Trie#History,_etymology,_and_p...

The idea was independently described in 1960 by Edward Fredkin, who coined the term trie, pronouncing it /ˈtriː/ (as "tree"), after the middle syllable of retrieval. However, other authors pronounce it /ˈtraɪ/ (as "try"), in an attempt to distinguish it verbally from "tree".

Minutes 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.

Intended to be like "tree", usually pronounced "try".

I 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 ;-)

I've heard before that it's meant to be re-TRIE-val and therefore is pronounced "tree"

I usually pronounce it as "trye" with the y as in try and the e as the first e in Mercedes

tree-eh

I'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

I've found that reinventing wheels is a great way to learn, even if you never use them.

I recently implemented the Bitcask paper in Golang and shared my learnings: https://mrkaran.dev/posts/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.

Is there an elegant solution to the garbage collection problem that append only DBs have to deal with?

This 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/Tracing_garbage_collection#Gen...

I 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.

If 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 . 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

Going 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.

Any 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.

I 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.

Sometimes you just want to have fun. But I agree, I don’t know why he suggests it would be fast…

Bitcask 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.

One big limitation of Bitcask is that all keys must fit in memory. Still my favorite format for simple KV.

I 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

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

Building 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.

Strictly 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.

How 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.

I'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.

If 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.

Thanks!

The hardest problem with the databases seems to be how it handles a sudden power down event. Most implementations don't pass that test.

Very 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/sqlite

Thank 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/) which have you build your own redis and mysql-lite compatible db. Looking forward to going through this.

Building 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"

I'd be curious to hear more about this. KV stores as a basis for distributed databases are really interesting.

Here's a FB engineering blog post from 2021 that covers ZippyDB pretty well. https://engineering.fb.com/2021/08/06/core-data/zippydb/

https://www.igvita.com/2012/02/06/sstable-and-log-structured...

May be of interest to you

Hey, 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.

This might interest you as well: 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

Just went through the course syllabi. This is something I have been looking for a long time. Thank you.

In 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-g...

I 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.

Not sure why "toy" was added to the title. It's not part of the title of the post, nor should it be.

Noted. Updated the title.

The 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?

I'm writing Quickiebase[1], a NoSQL database with an API similar to MongoDB. it has a roadmap: https://github.com/cabalamat/quickiebase/wiki/roadmap

[1]: https://github.com/cabalamat/quickiebase

I 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

This reminded me of Terry A. Davis, thanks, got a good giggle out of it.

Reply on news.ycombinator.com