It is a single problem that contains two smaller problems, but the actual hard part (a third problem, if you wish) is putting them together. If you limit yourself to solve those two problems independently you won't have a (useful) database.
You can decompose in 2 problems, because well is better, but is in fact one. Can be argued that is only this single problem:
How, in ACID way, store data that will be efficiently look it up later by a unknown number of clients and unknown access patterns, concurrently, without blocking all the participants, in a fast way?
I was tempted to knee-jerk dismiss this as "don't write your own database, don't even use a KV database, just use SQL". And then I remembered the only reason I'd say this is because I went through designing my own DB or using KV databases just to avoid SQL...only to realise i was badly reinventing SQL. It could be worth the lesson.
It's very nice, but I think he should expand on why hash tables are fast/constant time lookup. It's a central concept to why the index makes the db fast.
Part of the reason why I'm not a "maker" is because my mind gets ahead of me with all the things that I would need to do in order to do things properly. So the article starts out interesting and then gets more and more, well, not exactly stressful but I get a bit weary by it.
Not that I would aspire to implement a general-purpose database. But even smaller tasks can make my mind spin too much.
I absolutely love this "first principles" approach of explaining a topic. You can really go through this and at each time understand what problem needs to be solved and what other problems this introduces, until you get at a reasonably satisfying solution.
The first example in the "Sorting in Practice" section appears to be broken. The text makes it seem like the list should be sorted in-memory and then written to disk sorted, but the example un-sorts the list when it's written to disk.
Edit: the flush example (2nd one) in the recap section does the same thing, when the text says that the records are supposed to be written to the file in sorted order.
Nice interactivity, but this is taken straight from the Designing Data-Intensive Applications. Literally all the content here is an interactive version of chapter 3.
Great read. I’ve been modeling developer activity as a time series key value system where each developer is a key and commits are values.
Faced the same issues: logs grow fast, indexes get heavy, range queries slow down.
How do you decide what to drop when compacting segments? Balancing freshness and retention is tricky.
“LSM trees are the underlying data structure used for [..] DynamoDB, and they have proven to perform really well at scale [..] 80 million requests per second!”
This is a tad bit misleading, as the LSM is used for the node-level storage engine, but doesn’t explain how the overall distributed system scales to 80 million rps.
iirc the original Dynamo paper used BerkeleyDB (b-tree or LSM), but the 2012 paper shifted to a fully LSM-based engine.
I more or less built my own database in Erlang a few months ago. I say "more or less" because I did use Bitcask as the underlying store, and I used the riak_core libraries initially, but I did handle replication and different fault tolerance techniques on my own.
It was actually very fun; a key-value database is something that can be any level of difficulty that you want. If you want a simple KV "database", you could just serialize and deserialize a JSON string all the time, or write a protobuf, but there is of course no limit to the level of complexity.
I use the JSON example because that was actually how I started; I was constantly serializing and deserializing JSON with base64 binary encoded strings, just because it was easy and good enough, and over the course of building the project I ended up making a proper replicated database. I even had a very basic "query language" to handle some basic searches.
One of our final projects during university was to design and program a basic database in C. Even after 20 years I think that was one of the most one I've had in a project.
This gets fuzzy around the end - indexes are depicted as separate (partial) entities. Do we store all of those separated in different files? If so, do we need to open them all to search for a record?
Great post and beautiful website. I got a bit confused by the flush operation that happens when the memtable is full. A quick note that a new on-disk segment is created would help. In the recap at the end, segmentation is also not mentioned.
39 comments
[ 0.17 ms ] story [ 54.0 ms ] thread>
> "How do we store data persistently and then efficiently look it up later?"
Isn't that two problems?
No, that would be regexes.
How, in ACID way, store data that will be efficiently look it up later by a unknown number of clients and unknown access patterns, concurrently, without blocking all the participants, in a fast way?
And then add SQL (ouch!)
> Isn't that two problems?
Only if you're creating a write-only database, in which case just write it to /dev/null.
Kudos for that!
Exercises like this also seem fun in general. It's a real test of how much you know to start anything from scratch.
I made a pointless program to help w/ this on macOS for kicks: https://github.com/radiofreejohn/xattrkv
When I made it I also found a bug in the xattr implementation for Darwin and submitted it to Apple, they eventually fixed it.
I would say without transactions it is not a database yet from a practical standpoint.
Not that I would aspire to implement a general-purpose database. But even smaller tasks can make my mind spin too much.
Edit: the flush example (2nd one) in the recap section does the same thing, when the text says that the records are supposed to be written to the file in sorted order.
I wish this came out earlier, there are a few insights in there that took me me a while to understand :)
Maybe give credit?
This is a tad bit misleading, as the LSM is used for the node-level storage engine, but doesn’t explain how the overall distributed system scales to 80 million rps.
iirc the original Dynamo paper used BerkeleyDB (b-tree or LSM), but the 2012 paper shifted to a fully LSM-based engine.
It was actually very fun; a key-value database is something that can be any level of difficulty that you want. If you want a simple KV "database", you could just serialize and deserialize a JSON string all the time, or write a protobuf, but there is of course no limit to the level of complexity.
I use the JSON example because that was actually how I started; I was constantly serializing and deserializing JSON with base64 binary encoded strings, just because it was easy and good enough, and over the course of building the project I ended up making a proper replicated database. I even had a very basic "query language" to handle some basic searches.