This article is attractively presented and seems to be well written, but I disagree with the framing:
> Databases were made to solve one problem:
> How do we store data persistently and then efficiently look it up later?
There are indeed things described as "databases" which are made to solve that problem, but more commonly such things are instead called "file formats" or, to old IBMers, "access methods".
As I see it, the much more interesting problem that databases solve, the one that usually distinguishes what we call "databases" from what we call "file formats", is query evaluation:
> How do we organize a large body of information such that we can easily answer questions efficiently from it?
Prolog, Datalog, QBE, QUEL, and SQL are approaches to expressing the questions, and indexing, materialized views, query planning, resolution, the WAM, and tabled resolution are approaches to answering them efficiently.
dbm is not a database. ISAM is not a database. But SQLite in :memory: is still a database.
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.
Any repo? even if not production ready. I'm curious about how you approached replication, compared to mnesia or couchdb, especially now that erlang natively supports json.
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.
my only minor critique is using lorem ipsum examples. It tends to make me want to gloss over instead of reading; I prefer seeing realistic data. other than that, it's a really cool post
It also creates the tables, including invoice and lineitem tables. It's still a bit of a dull accounting example, rather than something like food, superheroes, social networks, zoo animals, sports, or dating, but I think the randomness does add a little bit of humor.
Although now we have LLMs, and maybe they'd do a better job.
Was going to post the same thing. Lorem Ipsum makes the data too hard to distinguish. I get that due to the dynamic nature of the examples the text needed to be generated, but Latin isn't the best choice IMO.
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.
I remember an article here, maybe a year ago, where somebody showed some database concepts from bash examples (like "write your db in bash"), but I can't find it anywhere, does anybody have it ?
“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.
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 have this same issue but lately I am realizing it is about belief and made great progress fixing it.
For me it is all about believing that I’ll succeed and realizing that the belief doesn’t really correlate with technical aspect as much as I think it does.
If I believe I won’t succeed, I spend every moment trying to find the problem that will finally end me. And every problem becomes a death sentence.
If I believe I’ll succeed, problems become temporary obstacles and all my focus is on how I’ll overcome the current obstacle.
I don't disagree with your take in general, but I do think it's different reading about minutiae than being invested in it. If you actually are curing these requirements it's probably quite engaging. If not, the eyes and mind start to gloss over them.
As a different example: I'm moving this week. I've known I'm moving for a while. Thinking about moving -- and all the little things I have to do -- is way more painful than doing them. Thinking about them keeps me up at night, getting through my list today is only fractionally painful.
I'm also leveling up a few aspects of my "way of living" in the midst of all this, and it'd be terribly boring to tell others about it, but when next Monday comes.. it'll be quite sweet indeed.
> As a different example: I'm moving this week. I've known I'm moving for a while. Thinking about moving -- and all the little things I have to do -- is way more painful than doing them. Thinking about them keeps me up at night, getting through my list today is only fractionally painful.
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.
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.
I've found Kill The Newsletter works pretty well for the few things I want to follow that still insist on email delivery. https://kill-the-newsletter.com/
You can implement two-phase commit instead. It requires a bit of additional planning in terms of data management but I actually find it much more elegant and it scales better. DB transactions are expensive and unnecessarily complicated.
You can have a really simple two-phase commit system where you initially mark all records as 'pending' and then update them as 'settled' once all the necessary associated rows have been inserted into their respective tables. You can record a timestamp so that you know where to resume the settlement process from. I once had multiple processes doing settlement in parallel by hashing the ids to map to specific processes so it scales really well.
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.
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.
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.
I'm curious how much data you have? I have 12 years of dev data and reports are generated in seconds, if not milliseconds. What is your key patterns? It sounds like a key-design problem.
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?
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.
While the text itself is my own words, the logical structure and the examples were indeed based off DDIA's chapter 3. I dropped the ball here - the site has been updated with proper attribution.
Come on, that's not enough. a) The parent said "taken straight from" but you've watered that down to "inspired by"; which is it? b) You've edited this post on HN, but the actual original article still makes no mention of the source.
Yep, fair enough. We've had contact with the post's publisher, and whilst it would be unfair of us to disclose the details of the communication, I've now updated the header text (to what I originally posted there when I first saw the root comment's allegation), and have down-weighted the post.
It's amusing to me that this is really quite a pedantic observation yet it's driving very earnest engagement from hackernews. Myself included. Absolutely nothing in this article is riding on if its 1 or 2 problems - it's an aside at best. Yet I'm still trying to think through if it's 1 or 2. I mean, the "and" is right there - that clearly suggests two. It's almost comical even, to say "Here is one problem: X and Y." Yet in another way it seems like 2 sides of the same coin.
I guess there is a rather fine line between philosophy and pedantry.
Maybe we can think about it from another angle. If they are 2 problems databases were designed to solve, then that means this is a problem databases were designed to solve: storing data persistently.
Is that really a problem database were designed to solve? Not really. We had that long before databases. It was already solved. It's a pretty fundamental computer operation. Isn't it fair to say this is one thing? "Storing data so it can be retrieved efficiently."
How do we reconstruct past memory states? That's the fundamental problem.
Efficiency of storage or retrieval, reliability against loss or corruption, security against unwanted disclosure or modification are all common concerns, and the relative values assigned to these features and others motivate database design.
Can you elaborate? That certainly seems to be what happens in a typical crud app. You have some model for your data which you persist so that it can be loaded later. Perhaps partially at times.
In another context perhaps you're ingesting data to be used in analytics. Which seems to fit the "reconstruct past memory stat" less.
I think it was a joke. It sounds like you read it as append-only, like most LSM tree databases (not rewriting files in the course of write operations), but I think GP meant it as write-only to the exclusion of reads, roughly equivalent to `echo $data > /dev/null`
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?
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.
Well, if you just want to store data, you can use files. Lookup is a bit tedious and inefficient.
So, if we consider that persistent storage is a solved problem, then we can say that the reason for databases was how to look up data efficiently. In fact, that is why they were invented, even if persistent storage is a prerequisite.
This article is attractively presented and seems to be well written, but I disagree with the framing:
> Databases were made to solve one problem:
> How do we store data persistently and then efficiently look it up later?
There are indeed things described as "databases" which are made to solve that problem, but more commonly such things are instead called "file formats" or, to old IBMers, "access methods".
As I see it, the much more interesting problem that databases solve, the one that usually distinguishes what we call "databases" from what we call "file formats", is query evaluation:
> How do we organize a large body of information such that we can easily answer questions efficiently from it?
Prolog, Datalog, QBE, QUEL, and SQL are approaches to expressing the questions, and indexing, materialized views, query planning, resolution, the WAM, and tabled resolution are approaches to answering them efficiently.
dbm is not a database. ISAM is not a database. But SQLite in :memory: is still a database.
seems you've overlooked the word "efficiently" in "store data persistently and then efficiently look it up later"?
No, I did not. Possibly you think I did because you don't know what ISAM or dbm are.
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.
Any repo? even if not production ready. I'm curious about how you approached replication, compared to mnesia or couchdb, especially now that erlang natively supports json.
Sadly it’s in a private repo as I had ambitions of trying to sell the product, which I haven’t completely given up on yet.
That said, a lot of the concepts come from riak_core, which is FOSS: https://github.com/OpenRiak/riak_core
I love the design and examples in this post. Easy to read for sure.
Exercises like this also seem fun in general. It's a real test of how much you know to start anything from scratch.
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.
my only minor critique is using lorem ipsum examples. It tends to make me want to gloss over instead of reading; I prefer seeing realistic data. other than that, it's a really cool post
You may be interested in http://canonical.org/~kragen/sw/dev3/exampledb.py -sql -n 2 example.sql:
It also creates the tables, including invoice and lineitem tables. It's still a bit of a dull accounting example, rather than something like food, superheroes, social networks, zoo animals, sports, or dating, but I think the randomness does add a little bit of humor.Although now we have LLMs, and maybe they'd do a better job.
Was going to post the same thing. Lorem Ipsum makes the data too hard to distinguish. I get that due to the dynamic nature of the examples the text needed to be generated, but Latin isn't the best choice IMO.
Otherwise great article, thank you!
It's the same for me when foo and bar are used as examples.
Someone gave me the advice to use animals, ideally animals of very different sizes or colours. People instantly picture them and remember them.
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.
I also recommend this free online book to build a database https://build-your-own.org/database/
I remember an article here, maybe a year ago, where somebody showed some database concepts from bash examples (like "write your db in bash"), but I can't find it anywhere, does anybody have it ?
https://tontinton.com/posts/database-fundementals/
I clicked through a couple of the articles in the OP, and I must say, the design and animations are extremely pretty!
Kudos for that!
The framework OP uses for his blog: https://github.com/nandanmen/NotANumber
“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.
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 have this same issue but lately I am realizing it is about belief and made great progress fixing it.
For me it is all about believing that I’ll succeed and realizing that the belief doesn’t really correlate with technical aspect as much as I think it does.
If I believe I won’t succeed, I spend every moment trying to find the problem that will finally end me. And every problem becomes a death sentence.
If I believe I’ll succeed, problems become temporary obstacles and all my focus is on how I’ll overcome the current obstacle.
I don't disagree with your take in general, but I do think it's different reading about minutiae than being invested in it. If you actually are curing these requirements it's probably quite engaging. If not, the eyes and mind start to gloss over them.
As a different example: I'm moving this week. I've known I'm moving for a while. Thinking about moving -- and all the little things I have to do -- is way more painful than doing them. Thinking about them keeps me up at night, getting through my list today is only fractionally painful.
I'm also leveling up a few aspects of my "way of living" in the midst of all this, and it'd be terribly boring to tell others about it, but when next Monday comes.. it'll be quite sweet indeed.
> As a different example: I'm moving this week. I've known I'm moving for a while. Thinking about moving -- and all the little things I have to do -- is way more painful than doing them. Thinking about them keeps me up at night, getting through my list today is only fractionally painful.
this sounds familiar... :)
Have you considered if you have ADHD?
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.
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.
if author is reading, can you add an rss feed to your site? i want to add to feedly.
I've found Kill The Newsletter works pretty well for the few things I want to follow that still insist on email delivery. https://kill-the-newsletter.com/
omg genius lol. thats such a simple and smart utility. i might try and make a chrome extension for this.
I was quite excited to add this one! And shocked to not find it, given the overall high production quality.
>Problem. How do we store data persistently and then efficiently look it up later?"
I would say without transactions it is not a database yet from a practical standpoint.
I think a lot of databases would disagree
You can implement two-phase commit instead. It requires a bit of additional planning in terms of data management but I actually find it much more elegant and it scales better. DB transactions are expensive and unnecessarily complicated.
You can have a really simple two-phase commit system where you initially mark all records as 'pending' and then update them as 'settled' once all the necessary associated rows have been inserted into their respective tables. You can record a timestamp so that you know where to resume the settlement process from. I once had multiple processes doing settlement in parallel by hashing the ids to map to specific processes so it scales really well.
>"You can implement two-phase commit instead"
Two-phase commit is a particular way of implementing transaction when system is distributed. There is no "instead" here
System doesn't have to be distributed. In general it just needs to separate the insertion of records from their settlement.
You might be on to something here ;)
But they are web scale!
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.
I have spending the last ~4 weeks writing a triple store!
I wish this came out earlier, there are a few insights in there that took me me a while to understand :)
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.
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.
I'm curious how much data you have? I have 12 years of dev data and reports are generated in seconds, if not milliseconds. What is your key patterns? It sounds like a key-design problem.
Here's a simple key-value store inspired by D.B. Cooper:
/dev/null is persistent across restarts and cache friendly, so it's got you covered.
A very nice explanation with visual interactions of how database works internally. author is a great teacher.
It looks like it got hugged to death already.
Needs a faster database
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?
thanks for share
am i the only one who IS a huge fan of this blogpost layout
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.
Maybe give credit?
Hey! Author of the post here.
While the text itself is my own words, the logical structure and the examples were indeed based off DDIA's chapter 3. I dropped the ball here - the site has been updated with proper attribution.
Thanks, we've added this to the thread's top text.
Come on, that's not enough. a) The parent said "taken straight from" but you've watered that down to "inspired by"; which is it? b) You've edited this post on HN, but the actual original article still makes no mention of the source.
Yep, fair enough. We've had contact with the post's publisher, and whilst it would be unfair of us to disclose the details of the communication, I've now updated the header text (to what I originally posted there when I first saw the root comment's allegation), and have down-weighted the post.
> Databases were made to solve one problem:
>
> "How do we store data persistently and then efficiently look it up later?"
Isn't that two problems?
It's amusing to me that this is really quite a pedantic observation yet it's driving very earnest engagement from hackernews. Myself included. Absolutely nothing in this article is riding on if its 1 or 2 problems - it's an aside at best. Yet I'm still trying to think through if it's 1 or 2. I mean, the "and" is right there - that clearly suggests two. It's almost comical even, to say "Here is one problem: X and Y." Yet in another way it seems like 2 sides of the same coin.
I guess there is a rather fine line between philosophy and pedantry.
Maybe we can think about it from another angle. If they are 2 problems databases were designed to solve, then that means this is a problem databases were designed to solve: storing data persistently.
Is that really a problem database were designed to solve? Not really. We had that long before databases. It was already solved. It's a pretty fundamental computer operation. Isn't it fair to say this is one thing? "Storing data so it can be retrieved efficiently."
How do we reconstruct past memory states? That's the fundamental problem.
Efficiency of storage or retrieval, reliability against loss or corruption, security against unwanted disclosure or modification are all common concerns, and the relative values assigned to these features and others motivate database design.
> How do we reconstruct past memory states? That's the fundamental problem.
reconstructing past memory states is rarely, if ever, a requirement that needs to be accommodated in the database layer
Can you elaborate? That certainly seems to be what happens in a typical crud app. You have some model for your data which you persist so that it can be loaded later. Perhaps partially at times.
In another context perhaps you're ingesting data to be used in analytics. Which seems to fit the "reconstruct past memory stat" less.
I always wanted to ship a write-only database. Lightning fast.
Back in the 80s a professor at our college got a presentation on the concept of «write-only memory» accepted for some symposium.
Good times.
Very secure!
Pretty much how eventstoredb works. Deleting data fully only happens at scavenge which rewrites the data files.
I think it was a joke. It sounds like you read it as append-only, like most LSM tree databases (not rewriting files in the course of write operations), but I think GP meant it as write-only to the exclusion of reads, roughly equivalent to `echo $data > /dev/null`
I've forgotten how to count that low. [0]
0 - https://www.youtube.com/watch?v=3t6L-FlfeaI
That would be useful for logging.
If it's write-only, and no reads ever happen, one can write to /dev/null without loss of utility.
It would be good for before going to sleep then.
Also useful for backups, so long as you don't need to restore.
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?
And then add SQL (ouch!)
Off by 1 error is indeed a hard problem.
>> "How do we store data persistently and then efficiently look it up later?"
> Isn't that two problems?
Only if you're creating a write-only database, in which case just write it to /dev/null.
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.
Store data persistently so it can be looked up efficiently* sounds like a single problem.
Definitely two.
"Store data persistently" implies "it can be looked up" since if you cannot look it up it is impossible to know if it is stored persistently.
The "efficiently" part can be considered a separate problem though.
Well, if you just want to store data, you can use files. Lookup is a bit tedious and inefficient.
So, if we consider that persistent storage is a solved problem, then we can say that the reason for databases was how to look up data efficiently. In fact, that is why they were invented, even if persistent storage is a prerequisite.
How about "store data in certain way." That sounds more like 1 problem and encompasses an even larger problem space.
It’s not persistent if it can’t be recovered later
Puts message in a bottle and tosses into the most convenient black hole.
Doesn't the black hole compresses the bottle beyond recovery?
Not necessarily, opinions vary.
https://www.sciencenewstoday.org/do-black-holes-destroy-or-s...
This is analogous to an elevator that’s unidirectional
One that lets people enter. We will figure out exiting later, with exiting on a different floor as a stretch goal.
Or just a paternoster
> Isn't that two problems?
No, that would be regexes.
You're thinking of regex
[dead]
[dead]