Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems

by Martin Kleppmann

Instead of writing a triple as (subject, predicate, object), we write it as predicate(subject, object).

Datalog is a subset of Prolog,

less convenient for simple one-off queries, but it can cope better if your data is complex.

One thing that document and graph databases have in common is that they typically don’t enforce a schema

researchers have written specialized genome database software like GenBank [

there is a big difference between storage engines that are optimized for transactional workloads and those that are optimized for analytics.

In this book, log is used in the more general sense: an append-only sequence of records.

An index is an additional structure that is derived from the primary data. Many databases allow you to add and remove indexes, and this doesn’t affect the contents of the database; it only affects the performance of queries.

Any kind of index usually slows down writes, because the index also needs to be updated every time data is written.

Compaction means throwing away duplicate keys in the log, and keeping only the most recent update for each key.

it is difficult to make an on-disk hash map perform well. It requires a lot of random access I/O, it is expensive to grow when it becomes full, and hash collisions require fiddly logic

Storage engines that are based on this principle of merging and compacting sorted files are often called LSM storage engines.

the LSM-tree algorithm can be slow when looking up keys that do not exist in the database: you have to check the memtable, then the segments all the way back to the oldest (possibly having to read from disk for each one)

(A Bloom filter is a memory-efficient data structure for approximating the contents of a set. It can tell you if a key does not appear in the database, and thus saves many unnecessary disk reads for nonexistent keys.)

In size-tiered compaction, newer and smaller SSTables are successively merged into older and larger SSTables.

In leveled compaction, the key range is split up into smaller SSTables and older data is moved into separate “levels,” which allows the compaction to proceed more incrementally and use less disk space.

B-trees break the database down into fixed-size blocks or pages, traditionally 4 KB in size (sometimes bigger), and read or write one page at a time.

The number of references to child pages in one page of the B-tree is called the branching factor.

a B-tree with n keys always has a depth of O(log n).

it is common for B-tree implementations to include an additional data structure on disk: a write-ahead log (WAL, also known as a redo log).

each leaf page may have references to its sibling pages to the left and right, which allows scanning keys in order without jumping back to parent pages.

LSM-trees are typically faster for writes, whereas B-trees are thought to be faster for reads

one write to the database resulting in multiple writes to the disk over the course of the database’s lifetime — is known as write amplification.

LSM-trees are typically able to sustain higher write throughput than B-trees, partly because they sometimes have lower write amplification

Since LSM-trees are not page-oriented and periodically rewrite SSTables to remove fragmentation, they have lower storage overheads,

On many SSDs, the firmware internally uses a log-structured algorithm to turn random writes into sequential writes on the underlying storage chips, so the impact of the storage engine’s write pattern is less pronounced

A downside of log-structured storage is that the compaction process can sometimes interfere with the performance of ongoing reads and writes.

Another issue with compaction arises at high write throughput: the disk’s finite write bandwidth needs to be shared between the initial write (logging and flushing a memtable to disk) and the compaction threads running in the background.

it can happen that compaction cannot keep up with the rate of incoming writes. In this case, the number of unmerged segments on disk keeps growing until you run out of disk space, and reads also slow down because they need to check more segment files. Typically, SSTable-based storage engines do not throttle the rate of incoming writes, even if compaction cannot keep up, so you need explicit monitoring to detect this situation

secondary index can easily be constructed from a key-value index. The main difference is that in a secondary index, the indexed values are not necessarily unique;

the place where rows are stored is known as a heap file, and it stores data in no particular order

heap file approach is common because it avoids duplicating data when multiple secondary indexes are present:

In some situations, the extra hop from the index to the heap file is too much of a performance penalty for reads, so it can be desirable to store the indexed row directly within an index. This is known as a clustered index.

compromise between a clustered index (storing all row data within the index) and a nonclustered index (storing only references to the data within the index) is known as a covering index or index with included columns, which stores some of a table’s columns within the index [33].

As with any kind of duplication of data, clustered and covering indexes can speed up reads, but they require additional storage and can add overhead on writes.

Some in-memory key-value stores, such as Memcached, are intended for caching use only, where it’s acceptable for data to be lost if a machine is restarted. But other in-memory databases aim for durability, which can be achieved with special hardware (such as battery-powered RAM), by writing a log of changes to disk, by writing periodic snapshots to disk, or by replicating the in-memory state to other machines.

Redis offers a database-like interface to various data structures such as priority queues and sets. Because it keeps all data in memory, its implementation is comparatively simple.

anti-caching approach works by evicting the least recently used data from memory to disk when there is not enough memory,

Whenever the leader writes new data to its local storage, it also sends the data change to all of its followers as part of a replication log or change stream.

When a client wants to read from the database, it can query either the leader or any of the followers.

if you enable synchronous replication on a database, it usually means that one of the followers is synchronous, and the others are asynchronous. If the synchronous follower becomes unavailable or slow, one of the asynchronous followers is made synchronous.

a fully asynchronous configuration has the advantage that the leader can continue processing writes, even if all of its followers have fallen behind.

follower connects to the leader and requests all the data changes that have happened since the snapshot was taken. This requires that the snapshot is associated with an exact position in the leader’s replication log. That position has various names: for example, PostgreSQL calls it the log sequence number, and MySQL calls it the binlog coordinates.

each follower keeps a log of the data changes it has received from the leader.

best candidate for leadership is usually the replica with the most up-to-date data changes from the old leader (to minimize any data loss).

The system needs to ensure that the old leader becomes a follower and recognizes the new leader.

The new leader may have received conflicting writes in the meantime. The most common solution is for the old leader’s unreplicated writes to simply be discarded, which may violate clients’ durability expectations.

could happen that two nodes both believe that they are the leader. This situation is called split brain, and it is dangerous: if both leaders accept writes, and there is no process for resolving conflicts (see “Multi-Leader Replication”), data is likely to be lost or corrupted. As a safety catch, some systems have a mechanism to shut down one node if two leaders are detected.

Any statement that calls a nondeterministic function, such as NOW() to get the current date and time or RAND() to get a random number, is likely to generate a different value on each replica.

the leader can replace any nondeterministic function calls with a fixed return value when the statement is logged so that the followers all get the same value.