Introduction

One of the most common book recommendations that I’ve come across for software engineers, architects, site reliability engineers, and many other roles is Designing Data Intensive Applications by Martin Kleppmann. This is typically cited as the jumping off point for digging deeper into systems design, databases, and other distributed systems topics, after finishing it I can absolutely agree - it is incredibly well written, although keep in mind that it is very dense which is somewhat understandable as the amount of content which is covered. Personally, I don’t believe it is possible to take a single reading pass of this book and come away properly understanding what you have read, I realised this after a couple of chapters and decided to take things much slower, instead opting to properly digest the content by producing small-scale projects which are related to the particular chapter. Granted, I do not think this would be entirely feasible for all chapters of the book, I found the database and consensus sections incredibly useful, whereas the first section felt a little tedious to get through - this may be because it is not too relevant in my work or as intriguing to me as databases and distributed systems.

This leads into the most interesting relevation for me from the book: log structured databases.

Log Structured Database

Conceptually, this is an incredibly simple idea which powers so many different technologies that are used today, some examples of this are:

  • Write-Ahead Logs (e.g. from PostgreSQL)
  • Apache Cassandra
  • InfluxDB (slightly modified to be based on contiguous timestamps)
  • MongoDB’s WiredTiger engine
  • And many others!

Simplest Database

To understand the general concept, albeit a simplified version of it, Martin presents two bash functions which stand-in for our log-structured database functionality. From this, you can realise how clever the idea: simple and incredibly powerful.

db_set() {
    echo "$1,$2" >> database
}

db_get() {
    grep "^$1," database | sed -e "s/^$1,//" | tail -n 1
}

Breaking this down:

  • To set/add a new record, we simply append the <id>,<value> to the file. It is the latest entry to it.
  • To read/get a record, we find the ID we are looking for, typically represented as a byte offset in the file, and display the latest one.

These two operations provide the simplest log structured database engine. There can be extra complexity added for segmenting the database file, splitting it across multiple nodes, tombstone records, and other things, but the concept itself is powerful. This database is persistent when a node fails, as it is written to disk, provides high write throughput, since it is such a simple operation to append to a file, and moderate read throughput, the longer the file the less efficient this becomes, although there are many ways to greatly help. As we’re appending to a file, this also implies immutability making the data structure even simpler to handle.

This concept was so intriguing to me, that I even did a not-so-concise rewrite of it in Go! In this project, I opted to implement a common solution for increasing the read throughput of the log file, by maintaining a separate hash map of byte offsets. This means that a value is stored alongside its byte-offset, map[string]int64 in Go terms, so that we can seek to the relevant position, as opposed to requiring a full scan of the database, which would become a problem in a larger system. I tried to ensure that I was extremely verbose with comments, meaning that I can continually come back to this project if I were to forget the general concept.

Later, I plan on creating a module for a B-Tree, which is another type of database structure which is used for storage, this is page-oriented rather than log-structured.