Under the Hood: Storage and Retrieval (Designing Data-Intensive Applications Chapter 4)

Image source: By SqlPac - Own work, CC BY-SA 3.0

In the first three chapters, we explored high-level architectural trade-offs, nonfunctional requirements, and the various ways we model data. Now, Chapter 4 of Designing Data-Intensive Applications (Second Edition), "Storage and Retrieval," shifts the focus to the database's perspective: how it actually stores the data you give it and how it finds that data again. 

As Richard Feynman once observed, "A computer does not primarily compute in the sense of doing arithmetic... They primarily are filing systems". Understanding the internal mechanics of these filing systems is crucial for selecting the right storage engine and tuning it for your specific workload.

The Core Divide: OLTP vs. OLAP

The authors begin by distinguishing between storage engines optimized for Online Transaction Processing (OLTP) and those built for Online Analytical Processing (OLAP). 

1. OLTP: The World of Key-Value Lookups

OLTP systems handle a high volume of requests, each usually reading or writing a small number of records. There are two dominant families of storage engines for these workloads:

• Log-Structured Merge-Trees (LSM-Trees): This approach treats the database as an append-only log. Modern implementations use an in-memory memtable to buffer incoming writes in sorted order. When the memtable reaches a size threshold, it is flushed to disk as an immutable SSTable (Sorted Strings Table). A background merging and compaction process eventually combines these segments to reclaim space. To speed up reads for non-existent keys, these engines often use Bloom filters.
• B-Trees: The most widely used index structure since 1970, B-trees break the database into fixed-size pages (usually 4–16 KiB) and overwrite them in place. They use a Write-Ahead Log (WAL) to ensure the tree remains consistent if the database crashes during a page update. 

The Trade-off: As a rule of thumb, LSM-trees are generally better for write throughput because they turn random writes into sequential ones, while B-trees are often faster for reads due to their predictable structure.

2. OLAP: The Power of Columnar Storage

While OLTP databases store data in a row-oriented fashion (all values of a row together), this is inefficient for analytical queries that aggregate over millions of rows but only access a few columns. 

Column-oriented (columnar) storage solves this by storing all values from each column together. This provides two massive advantages:

• Reduced I/O: Queries read and parse only the specific columns they need.
• High Compression: Since columns often contain repeating values, they lend themselves to highly effective compression techniques like bitmap encoding and run-length encoding.

For even faster analytics, some systems use materialized aggregates like Data Cubes (OLAP cubes), which are precomputed grids of common aggregates grouped by different dimensions.

3. Specialized Indexing: Text and Vectors

The chapter also looks beyond simple key-value lookups to more advanced query types:

• Full-Text Search: Uses inverted indexes (like those in Lucene) to map keywords to "postings lists" of document IDs.
• Vector Search: Driven by the rise of AI, specialized vector indexes like IVF (Inverted File) and HNSW (Hierarchical Navigable Small World) allow for semantic search by finding documents whose vector embeddings are closest to a query vector.

Conclusion: No Silver Bullet

Chapter 4 reinforces the book’s central theme: there is no one-size-fits-all storage engine. A system that is a perfect fit for a high-frequency trading platform (OLTP) would be a disaster for a business intelligence dashboard (OLAP). By understanding how these engines manage disks, memory, and compression, you can look past the marketing buzzwords and choose the tool that truly fits your application's needs.

 

Reference 

Designing Data-Intensive Applications: The Big Ideas Behind Reliable, Scalable, and Maintainable Systems
Book by Martin Kleppmann and Chris Riccomini

This blog post is a summary of my personal notes and understanding from reading "Designing Data-Intensive Applications" by Martin Kleppmann. All credit for the original ideas belongs to the author.