>

> "How do we store data persistently and then efficiently look it up later?"

Isn't that two problems?

Kudos for that!

  ~/bin/cooper-db-set
  ===================
  #! /bin/bash

  key="$1"
  value="$2"

  echo "${key}:${value}" >> /dev/null


  ~/bin/cooper-db-get
  ===================
  #! /bin/bash

  key="$1"
  </dev/null awk -F: -v key="$key" '$1 == key {result = $2} END {print result}'

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.

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