Storage & Retrieval
Every database answers the same two questions: where do I put this, and how do I find it again fast? This chapter — and this page — is about the trade-off that answer always comes down to: a disk head can only be in one place at a time. Sequential access is cheap. Jumping around is expensive. Everything else follows from that one fact.
Writing sequentially: the head glides forward, one block after another — this is what an append-only log does.
The world's simplest database
Two shell functions can technically be a database. db_set appends a line to a file. db_get greps the file for the key and keeps the last match. Try it below — type a key and a value, hit write, and watch the log file grow.
db_get scans every line from the top, and keeps the last match — because later writes overwrite earlier ones, but nothing is ever deleted from the file.
Writing is fast here — appending to a file is one of the cheapest operations a filesystem offers, and it's the same trick real storage engines lean on internally. Reading is the problem: db_get has to walk the entire file, so a lookup gets linearly slower as the database grows. That's the gap an index exists to close: extra, derived structure that trades a bit of write overhead for much cheaper reads. Add an index and you speed up some queries; every index you add also makes every write a little heavier, since it has to be kept in sync.
Hash indexes
The simplest fix: keep an in-memory hash map from every key to the byte offset where its latest value lives in the log. Write still just appends — but now you also drop a pin in the hash map. Read becomes: look up the offset, seek straight there, done. This is the approach Bitcask (Riak's default engine) actually uses.
Great when values are updated often but the set of distinct keys is small enough to fit in RAM — think a play-count per video URL, hammered by writes but bounded in cardinality.
Every key must fit in memory. Range queries ("everything between key A and key Z") are unsupported — a hash map has no sense of neighbors, only exact lookups. Deletes need a tombstone record; crash recovery needs a snapshot or full replay; corruption needs checksums.
Compaction & segment merging
An append-only file grows forever unless something intervenes. The fix: split the log into segments, and periodically run a background pass that keeps only the most recent value for each key, discarding everything older — then merges neighboring segments together so the segment count stays small.
Reads and writes keep being served from the old segments while this runs; only once the merged segment is ready do lookups switch over, and the stale files get deleted. Because segments are never edited in place, a crash mid-merge just leaves an incomplete new file to discard — the old ones are still intact.
SSTables & LSM-trees
One change unlocks almost everything a hash index can't do: keep each segment sorted by key instead of in write order. That's a Sorted String Table (SSTable). Sorted files merge like a merge-sort, and — crucially — you no longer need every key in memory, only a sparse index that says "key X starts around byte Y," because once you land nearby, you can just scan forward.
The segment is sorted alphabetically. The sparse index only remembers every 3rd key. Type a key to find — watch it jump to the nearest earlier index entry, then scan forward.
Writes land in an in-memory sorted structure (the memtable) — a red-black tree, say — so they're cheap and stay sorted for free. Once the memtable crosses a size threshold, it's written out as a new SSTable segment in one sequential pass, and background merging keeps the number of segments under control. A read checks the memtable first, then segments newest-to-oldest. A write-ahead log on the side protects against losing the memtable's contents in a crash.
This is the core of LevelDB, RocksDB, and — in spirit — Cassandra, HBase, and Google's Bigtable. Lucene's term dictionary (the thing Elasticsearch and Solr search) uses the same shape for a different purpose: mapping a word to the list of documents containing it. One practical wrinkle: looking up a key that doesn't exist is the expensive case, since you have to check every segment before concluding it's missing — which is why LevelDB adds Bloom filters, compact structures that can cheaply say "definitely not here" and skip most of that work.
B-trees
Despite the rise of log-structured engines, the B-tree — introduced in 1970 — is still the default index in almost every relational database. Where LSM-trees write variable-size segments sequentially, a B-tree carves the database into fixed-size pages (traditionally 4 KB) and updates individual pages in place.
Pick a key. Each page holds a handful of boundary keys and pointers to child pages covering a range. Follow the pointer whose range contains your key, page by page, until you reach a leaf.
If a leaf page is full, it splits in two, and the parent gets a new boundary key pointing at both halves. This is what keeps the tree balanced at height O(log n) no matter how large it grows.
Update-in-place vs. append-only logging
Overwriting a page in place is dangerous: a crash halfway through can leave a page half-written, or a parent pointing at a page that was never finished. B-trees guard against this with a write-ahead log (WAL) — every change is appended to a log before it touches the tree itself, so a crash can always be replayed back to a consistent state.
Every write touches disk at least twice: once to the append-only log, once to the page itself (sometimes more, if a split cascades up the tree). In return, each key lives in exactly one place — which makes range locks for transactions easy to attach directly to the tree.
Also rewrites data multiple times, just differently — through repeated background merging rather than a separate log-plus-page write. Whether that costs more or less than the B-tree's approach depends entirely on your workload; there's no universal winner, only benchmarks on your own data.
Concurrency follows the same split: B-trees need latches (lightweight locks) so concurrent threads don't observe a half-updated tree. LSM-trees sidestep most of that, since merging happens in the background against immutable files and segments are swapped in atomically.
B-trees vs. LSM-trees
Neither wins outright — but they lean in opposite directions on nearly every axis. Toggle between them.
Other indexing structures
A primary key index gets most of the attention, but real schemas need more.
Built the same way as a primary key index, except keys aren't unique — many rows can share one. Fixed either by storing a list of matching row IDs per key, or by appending a row ID onto the key to make it unique.
An index value can point to a row stored elsewhere (a heap file) — cheap when several indexes reference the same row — or the row can live directly inside the index (a clustered index, as InnoDB does for primary keys), trading storage and write cost for fewer disk hops on read.
A middle ground: store a few extra, frequently-queried columns inside the index itself, so some queries can be answered from the index alone without ever touching the underlying row.
A concatenated index just chains columns together — like a phone book sorted by (lastname, firstname). Genuinely multi-dimensional queries, like "restaurants inside this map rectangle," need something else entirely: R-trees, or a space-filling curve that folds 2D coordinates into a single sortable number.
Everything above assumes exact keys. Full-text search needs to match misspelled or nearby words — Lucene does this by turning its sparse in-memory index into a finite-state automaton over characters (like a trie), which can be converted into a Levenshtein automaton to efficiently search for words within a given edit distance.
In-memory databases
As RAM gets cheaper, "fits on disk" stops being the constraint for many datasets, and databases like Redis, VoltDB, and MemSQL keep everything resident in memory. The performance win isn't really about skipping disk reads — a disk-backed engine with enough RAM ends up caching everything anyway via the OS page cache. It's about skipping the overhead of encoding data into a disk-friendly format in the first place.
"In-memory" doesn't mean "disposable." Durability comes from writing a change log to disk, periodic snapshots, or replicating state to other machines — disk is just used as a backup mechanism, not the primary read path.
Keeping everything resident also makes it practical to offer data structures that are awkward to persist efficiently on disk — Redis's priority queues and sets, for instance.
Transaction processing or analytics?
Everything so far assumed a typical application pattern: fetch a handful of rows by key, mutate them, move on. That's OLTP. Analytics is a different animal entirely — a query might scan millions of rows just to compute one sum. That's OLAP. Same word, "query," wildly different shape.
Analysts querying live OLTP databases directly is a liability — those expensive scans compete with the transactions the business actually depends on. So data gets periodically copied out, cleaned up, reshaped, and loaded into a separate warehouse built for scanning, not seeking.
Star schemas
Warehouses converge on one modeling style almost universally: a big fact table — one row per event, like a single line-item sale — surrounded by smaller dimension tables answering who, what, where, and when. Drawn out, the fact table sits in the middle with foreign keys radiating outward like a star.
Fact tables are often event-grained and enormous — hundreds of columns, sometimes billions of rows — because keeping every raw event preserves maximum flexibility for later analysis. A snowflake schema is the same idea taken further: dimensions get normalized into sub-dimensions too. Star schemas are usually preferred anyway, because they're simpler for analysts to write queries against.
Column-oriented storage
A typical analytics query touches 4 or 5 columns out of a table that might have over a hundred. Row-oriented storage still has to load every full row off disk before it can throw most of it away. Column-oriented storage flips the layout: store all the values from one column contiguously, in a separate file, so a query only ever reads the columns it actually needs.
Query: sum quantity grouped by weekday, for fresh fruit and candy only — touches 3 of 8 columns.
Columns with few distinct values compress beautifully: split the column into one bitmap per distinct value (1 = row has that value), then run-length encode each bitmap's long runs of zeros. Type a short column of product IDs to see it happen.
Rows are sorted together across all columns — sorting one column independently would destroy the correspondence between columns. The first sort key compresses best, since matching values cluster into the longest runs; date-range queries often make a date column the obvious first key.
Inserting into the middle of a sorted, compressed column file would mean rewriting everything. The fix is the same LSM-tree idea from earlier: buffer writes in memory, then merge them into new column files in bulk — Vertica does exactly this.
Aggregation: data cubes & materialized views
If many queries all ask for the same aggregate — total sales per store, say — recomputing it from raw rows every time is wasted work. A materialized view writes the query's result to disk as an actual table, refreshed as data changes. A data cube (or OLAP cube) is the special case of pre-aggregating along every combination of dimensions.
Every cell is pre-computed. Row and column totals fall out for free by summing along an axis — no scan required.
The catch: a cube can only answer questions along the dimensions it was built with. "Sales from items over $100" is unanswerable here, because price isn't one of the axes — which is why warehouses keep the raw fact table around and use cubes only as a speed boost, not a replacement.
Summary: Storage and Retrieval
Two questions, two very different answers depending on who's asking.
User-facing, high request volume, small number of records per query, fetched by key. Two schools of thought on the index itself: log-structured (Bitcask, SSTables, LSM-trees, LevelDB, Cassandra, HBase) which only ever appends and deletes whole files, and update-in-place (B-trees) which overwrites fixed-size pages directly.
Analyst-facing, low request volume, each query scanning millions of rows to compute an aggregate. Indexes stop mattering much once you're reading most of the table anyway — the win comes from column-oriented storage, which reads only the columns a query needs and compresses each one aggressively.
The throughline across all of it: sequential I/O is cheap, random I/O is expensive, and every structure in this chapter — hash indexes, SSTables, B-trees, column files, data cubes — is a different bet on how to get more sequential access and less random seeking out of the same underlying disk.
Encoding & Evolution
“Everything changes and nothing stands still.” — Heraclitus of Ephesus (quoted by Plato in Cratylus)
Applications inevitably evolve. As features are added or modified, data formats must adapt. In large systems, code changes cannot happen instantaneously: server-side applications undergo rolling upgrades (staged rollouts), and client-side applications update at the user's discretion. System reliability depends on maintaining compatibility in both directions.
Newer code can read data written by older code. As the author of newer code, you know the historical data format and can handle it explicitly.
Older code can read data written by newer code. Requires older code to gracefully ignore additions made by newer versions without crashing or dropping fields.
Simulate deploying a new application version across a 4-node cluster while active network traffic flows between nodes. Toggle compatibility settings to observe system health during rolling upgrades.
Formats for encoding data
Programs operate on data in two distinct representations: in-memory data structures (objects, structs, pointers optimized for CPU access) and serialized byte sequences (for files or network payloads).
Encoding (serialization / marshalling) converts in-memory objects to self-contained byte sequences. Decoding (parsing / deserialization / unmarshalling) restores objects from bytes.
Built-in libraries like Java Serializable, Python pickle, and Ruby Marshal offer quick convenience but suffer from deep flaws:
- Vendor Lock-in: Reading data in another language is extremely difficult.
- Security Risks: Arbitrary class instantiation enables Remote Code Execution attacks.
- Poor Compatibility: Versioning, forward/backward compatibility are afterthoughts.
- Inefficient: High CPU overhead and bloated byte footprints.
JSON, XML, and CSV
Standardized textual encodings are widely supported and human-readable, making them dominant for data interchange across organizations despite subtle flaws.
XML & CSV cannot distinguish numbers from numeric strings without schemas. JSON distinguishes numbers but does not differentiate integers from floats and lacks precision specs. Numbers $> 2^{53}$ (like Twitter 64-bit Tweet IDs) get corrupted in JavaScript floating-point parsers, requiring APIs to output both JSON numbers and decimal strings.
JSON and XML have great Unicode support but lack native binary string support (raw byte sequences). Developers bypass this by Base64-encoding binary data into text, which increases data size by ~33% and relies on external schemas or conventions to decode properly.
Binary encodings & field tags
Internal service communication at scale requires compact, fast encodings. Binary variants of JSON (MessagePack, BSON) keep field names, whereas schema-driven formats (Thrift, Protocol Buffers, Avro) omit field names entirely or replace them with compact field tags.
Inspect the exact byte sequence of Kleppmann's example record: {"userName":"Martin", "favoriteNumber":1337, "interests":["daydreaming","hacking"]}
Field tags and schema evolution
Apache Thrift and Protocol Buffers require schema definitions (IDL) with numeric field tags. Field tags act as compact aliases in binary payloads, replacing verbose field names.
- Never change a field tag: Field tags define payload meaning. Renaming fields in IDL is safe, changing tags invalidates existing data.
- Adding fields: Every added field must be
optionalor have a default value. Old code skips unknown tags (forward compatible); new code fills defaults for old data (backward compatible). - Never make new fields required: Adding a required field breaks backward compatibility when new code reads old data lacking that field.
- Removing fields: Only optional fields can be removed. Removed field tags must never be reused.
Changing datatypes risks truncation or precision loss (e.g. 64-bit int narrowed to 32-bit int). Protocol Buffers lacks a list type, using a repeated marker instead. A repeated field simply repeats the field tag in the binary payload, allowing smooth evolution from single-valued (optional) to multi-valued (repeated)!
Apache Avro & schema resolution
Apache Avro produces the most compact binary encoding (32 bytes for Example 4-1) because it contains no field tags or datatype annotations in the binary stream — just concatenated values.
Avro relies on resolving differences between the Writer's Schema (used when encoding data) and the Reader's Schema (used when decoding data) side-by-side.
union{null, long} favoriteNumber
array<string> interests
string photoURL
long userID = 0 (new default)
array<string> interests
union{null, long} favoriteNumber
- Large Container Files: Writer's schema included once in file header (Avro Object Container File).
- Database Records: Prepend an integer schema version ID to each record; look up schema in schema registry.
- Network RPC: Negotiate schema version on connection setup.
Without field tags, Avro easily generates schemas dynamically from relational database tables (columns → field names). When DB schemas change, updated Avro schemas are generated automatically without manual tag mapping administration.
Data flow through databases
In databases, the process writing data encodes it, and the process reading data decodes it. Because data outlives application code, historical records written years prior coexist with brand new writes.
Data outlives code: database records written 5 years ago remain in original encodings unless explicitly migrated.
Watch what happens when an older app version (v1) reads a record written by a newer app version (v2 containing new field photoURL), modifies a field, and writes it back.
Data flow through services: REST & RPC
Processes communicate over network connections via APIs (clients and servers, microservices). While REST dominates public web APIs, RPC frameworks optimize inter-service communication.
REST is a design philosophy building on HTTP (URLs, status codes, cache headers, JSON/XML). SOAP is an XML protocol with complex WS-* standards and WSDL schemas enabling code generation, popular in legacy enterprise platforms.
RPC attempts to make network calls look like local function calls. This abstraction is fundamentally flawed:
- Unpredictability: Local calls either succeed or fail; network calls time out or lose packets.
- Idempotence: Retrying failed requests can duplicate non-idempotent operations.
- Latency: Local calls take nanoseconds; network RPC takes milliseconds to seconds.
- Memory: Pointers cannot be passed across network boundaries; parameters must be serialized.
Asynchronous message-passing
Message brokers (RabbitMQ, Kafka, ActiveMQ, NATS) combine the low-latency delivery of RPC with the temporary storage and durability of databases.
- Traffic Buffering: Queue buffers spikes when recipients are overloaded or offline.
- Reliability: Automatically redelivers messages if worker processes crash.
- Decoupling: Sender doesn't need to know recipient IP address or port.
- Fan-out: One message can be published to multiple subscribers simultaneously.
- Asynchronous: Sender fires and forgets without blocking on delivery.
Encapsulate logic into actors that communicate via asynchronous messages. Scale across multiple nodes (Akka, Orleans, Erlang OTP). Location transparency works better in actor models because local messaging already expects message loss and latency!
Publish messages to a topic. Toggle consumer availability to see how the broker buffers messages until consumers recover.
Summary: Encoding and Evolution
Evolvability requires systems to support rolling upgrades and heterogeneous environments where old and new code coexist.
Backward Compatibility: Newer code reads older data.
Forward Compatibility: Older code reads newer data.
Essential for zero-downtime rolling upgrades and independent service deployments.
Language-specific: Convenient, insecure, locked-in.
Textual (JSON/XML/CSV): Universal, verbose, ambiguous numbers.
Binary Schema-driven (Thrift/Protobuf/Avro): Ultra-compact, fast, explicit backward/forward compatibility rules.