Data & Storage

Data models

The shapes a database can give your data, and what each shape is good at.

• Relational databases

  Tables that store each fact once, rules that the database enforces, and joins that put the facts back together.

• Key-value and document stores

  Stores that give up joins: what they can look up, what they cannot, and how to shape data for them.

• Wide-column, graph and time-series stores

  Three specialised shapes: tables read one partition at a time, data that is all relationships, and measurements over time.

• Normalization and denormalization

  Storing each fact once, and when to break that rule on purpose. Builds on Relational databases.

• Choosing a database from access patterns

  How the reads and writes of an application pick its database, and what a second database costs. Builds on What one modern server can do.

Indexing

How a database finds rows without reading all of them, and what that costs on every write.

• What an index costs and buys

  How an index turns a search through millions of rows into a few steps, and what every write pays for it.

• How B-tree indexes find rows

  Sorted pages, a short descent from root to leaf, and why a function on the column breaks it.

• LSM trees and SSTables

  A storage design that never changes a file once it is written, and why that makes writes cheap and reads more work.

• Composite and covering indexes

  Indexes on several columns: why their order decides which queries they serve, and when the table need not be read at all.

• Inverted indexes

  How text search finds the documents that contain a word, without reading the documents.

Transactions and isolation

How a database keeps changes whole and keeps concurrent work from colliding.

• Transactions and the write-ahead log

  How a database makes several changes count as one, and how it keeps a commit through a crash. Builds on ACID and BASE.

• Isolation levels and their anomalies

  What transactions that run at the same time can see of each other, and how strictly a database can keep them apart.

• MVCC

  How a database lets readers and writers work on the same rows at the same time, by keeping more than one version.

• Pessimistic locking

  Claiming a row before you change it, so that two transactions cannot both act on the same old value, and what goes wrong when locks cross.

• Optimistic locking

  Detecting a conflict at the moment of writing, in place of preventing it with a lock, and when that is the better deal.

Replication

Keeping copies of the data on several machines, and what the copies can promise.

• Leader-follower replication

  One machine takes the writes and the others copy them: what that buys, and what it does not. Builds on Transactions and the write-ahead log.

• Synchronous and asynchronous replication

  When a leader confirms a write decides what a failure can cost: time on every write, or the last few writes. Builds on PACELC.

• Replication lag and read-your-writes

  Followers are always a little behind. What users notice of that, and how to hide it. Builds on Consistency models.

• Multi-leader replication and conflicts

  Several machines that all accept writes: why anyone wants that, and what happens when two of them change the same thing.

• Leaderless replication and quorums

  Replication with no leader at all: writing to several replicas, reading from several, and the arithmetic that makes the two overlap.

Partitioning and sharding

Splitting data that no longer fits one machine, and living with the split.

• Vertical and horizontal partitioning

  Two ways to cut up data that has grown too large, and why spreading it over machines is the last resort.

• Choosing a shard key

  The one column that decides where every row lives, which queries stay cheap, and whether the load spreads at all.

• Range and hash partitioning

  Two ways to turn a key into a partition: one keeps neighbours together, the other spreads everything evenly.

• Consistent hashing

  A way to place keys on machines so that adding or removing one moves only a small share of the data. Builds on Range and hash partitioning.

• Hot partitions, rebalancing and cross-shard queries

  Living with a sharded database: one shard that gets too much, moving data while the system runs, and work that spans shards.

Caching

• Why cache at all?

  Latency, load and the hit ratio: what a cache buys you and what it costs.

• Cache-aside vs read-through

  Two ways to fill a cache on a miss, and what changes when the cache does the loading.

• Invalidation strategies

  TTLs, write-through, and why invalidation is one of the two hard problems.

• Hot keys and thundering herds

  When one key draws the traffic, or expires under load, and the three fixes that work.

• Eviction policies

  A cache is smaller than the data behind it. What it throws out when it is full decides how often it helps.

• Where to cache: client, CDN, application, database

  A response passes several places that can remember it. Which one to use for what, and who is allowed to share a copy.

Object and blob storage

Where files go: images, videos and backups that do not belong in a database.

• Block, file and object storage

  Three ways to keep bytes, and why images, videos and backups end up in the third.

• Presigned URLs and multipart uploads

  Letting a client send and fetch large files directly, without opening the bucket and without passing every byte through your servers.

• Durability and erasure coding

  How a storage service keeps data through drive failures, and why it does not simply keep three copies of everything.

• Metadata in the database, bytes through a CDN

  The usual shape of file handling in an application: a database row that describes each file, an object that holds it, and a CDN that delivers it.