(by Martin Kleppmann)

Chapter 1: Reliable, Scalable, and Maintainable Applications

Thinking About Data Systems


Hardware Faults
Software Errors
Human Errors


Describing Load
Describing Performance
Approaches for Coping with Load


Operability: Making Life Easy for Operations
Simplicity: Managing Complexity
Evolvability: Making Change Easy


Chapter 2: Data Models and Query Languages

Relational Model Versus Document Model

The Birth of NoSQL
The Object-Relational Mismatch
Many-to-One and Many-to-Many Relationships
Are Document Databases Repeating History?
The relational model
Comparison to document databases
Relational Versus Document Databases Today
Which data model leads to simpler application code?
Schema flexibility in the document model
Data locality for queries

Query Languages for Data

MapReduce Querying

Graph-Like Data Models

Property Graphs
Graph Queries in SQL
Triple-Stores and SPARQL
The Foundation: Datalog

Chapter 3: Storage and Retrieval

Data Structures That Power Your Database

Hash Indexes
SSTables and LSM-Trees
Constructing and maintaining SSTables
Making an LSM-tree out of SSTables
Performance optimizations
Making B-trees reliable
B-tree optimizations
Comparing B-Trees and LSM-Trees
Advantages of LSM-trees
Downsides of LSM-trees
Other Indexing Structures
Storing values within the index
Multi-column indexes
Full-text search and fuzzy indexes
Keeping everything in memory

Transaction Processing or Analytics?

Data Warehousing
The divergence between OLTP databases and data warehouses
Stars and Snowflakes: Schemas for Analytics

Column-Oriented Storage

Column Compression
Memory bandwidth and vectorized processing
Sort Order in Column Storage
Several different sort orders
Writing to Column-Oriented Storage
Aggregation: Data Cubes and Materialized Views


Chapter 4: Encoding and Evolution

Formats for Encoding Data

Language-Specific Formats
JSON, XML, and Binary Variants
Binary encoding
Thrift and Protocol Buffers
Field tags and schema evolution
Datatypes and schema evolution
The writer's schema and the reader's schema
Schema evolution rules
Dynamically generated schemas
The Merits of Schemas

Modes of Dataflow

Dataflow through Databases
Different values written at different times
Dataflow Through Services: REST and RPC
Web services
The problems with remote procedure calls (RPCs)
Current directions for RPC
Data encoding and evolution for RPC
Message-Passing Dataflow
Message brokers
Distributed actor frameworks

Chapter 5: Replication

Leaders and Followers

Synchronous Versus Asynchronous Replication
Setting Up New Followers
Handling Node Outages
Follower failure: Catch-up recovery
Leader failure: Failover
Implementation of Replication Logs
Statement-based replication
Write-ahead log (WAL) shipping
Logical (row-based) log replication
Trigger-based replication

Problems with Replication Lag

Reading Your Own Writes
Monotonic Reads
Consistent Prefix Reads
Solutions for Replication Lag

Multi-Leader Replication

Use Cases for Multi-Leader Replication
Multi-datacenter operation
Clients with offline operation
Handling Write Conflicts
Synchronous versus asynchronous conflict detection
Converging toward a consistent state
Custom conflict resolution logic
Multi-Leader Replication Topologies

Leaderless Replication

Writing to the Database When a Node is Down
Read repair and anti-entropy
Quorums for reading and writing
Limitations of Quorum Consistency
Monitoring staleness
Sloppy Quorums and Hinted Handoff
Detecting Concurrent Writes
Last write wins (discarding concurrent writes)
The "happens-before" relationship and concurrency
Capturing the happens-before relationship
Merging concurrently written values
Version vectors

Chapter 6: Partitioning

Partitioning and Replication

Partitioning of Key-Value Data

Partitioning by Key Range
Partitioning by Hash of Key
Skewed Workloads and Relieving Hot Spots

Partitioning and Secondary Indexes

Partitioning Secondary Indexes by Document
Partitioning Secondary Indexes by Term

Rebalancing Partitions

Strategies for Rebalancing
How not to do it: hash mod N
Fixed number of partitions
Dynamic partitioning
Partitioning proportionally to nodes
Operations: Automatic or Manual Rebalancing

Request Routing

Chapter 7: Transactions

The Slippery Concept of a Transaction

The Meaning of ACID
Single-Object and Multi-Object Operations
Single-object writes
The need for multi-object transactions
Handling errors and aborts

Weak Isolation Levels

Read Committed
No dirty reads
No dirty writes
Implementing read committed
Snapshot Isolation and Repeatable Read
Implementing snapshot isolation
Visibility rules for observing a consistent snapshot
Indexes and snapshot isolation
Repeatable read and naming confusion
Preventing Lost Updates
Atomic write operations
Explicit locking
Automatically detecting lost updates
Conflict resolution and replication
Write Skew and Phantoms
Phantoms causing write skew
Materializing conflicts


Actual Serial Execution
Encapsulating transactions in stored procedures
Pros and cons of stored procedures
Two-Phase Locking (2PL)
Implementation of two-phase locking
Performance of two-phase locking
Predicate locks
Index-range locks
Serializable Snapshot Isolation (SSI)
Pessimistic versus optimistic concurrency control
Decisions based on an outdated premise
Detecting stale MVCC reads
Detecting writes that affect prior reads
Performance of serializable snapshot isolation


Chapter 8: The Trouble with Distributed Systems

Faults and Partial Failures

Cloud Computing and Supercomputing

Unreliable Networks

Network Faults in Practice
Detecting Faults
Timeouts and Unbounded Delays
Network congestion and queueing
Synchronous Versus Asynchronous Networks
Can we not simply make network delays predictable?

Unreliable Clocks

Monotonic Versus Time-of-Day Clocks
Time-of-day clocks
Monotonic clocks
Clock Synchronization and Accuracy
Relying on Synchronized Clocks
Timestamps for ordering events
Clock readings have a confidence interval
Synchronized clocks for global snapshots
Process Pauses
Response time guarantees
Limiting the impact of garbage collection

Knowledge, Truth, and Lies

The Truth is Defined by the Majority
The leader and the clock
Fencing tokens
Byzantine Faults
System Model and Reality
Correctness of an algorithm
Safety and liveness
Mapping system models to the real world


Chapter 9: Consistency and Consensus

Consistency Guarantees


What Makes a System Linearizable?
Relying on Linearizability
Locking and leader election
Constraints and uniqueness guarantees
Cross-channel timing dependencies
Implementing Linearizable Systems
The Cost of Linearizability
Linearizability and network delays

Ordering Guarantees

Ordering and Causality
The causal order is not a total order
Linearizability is stronger than causal consistency
Capturing causal dependencies
Sequence Number Ordering
Noncausal sequence number generators
Lamport timestamps
Timestamp ordering is not sufficient
Total Order Broadcast
Using total order broadcast
Implementing linearizable storage using total order broadcast
Implementing total order broadcast using linearizable storage

Distributed Transactions and Consensus

Atomic Commit and Two-Phase Commit (2PC)
From single-node to distributed atomic commit
Introduction to two-phase commit
A system of promises
Coordinator failure
Distributed Transactions in Practice
XA transactions
Holding locks while in doubt
Recovering from coordinator failure
Limitations of distributed transactions
Fault-Tolerant Consensus
Consensus algorithms and total order broadcast
Epoch numbering and quorums
Limitations of consensus
Membership and Coordination Services
Allocating work to nodes
Service discovery

Chapter 10: Batch Processing

Batch Processing with Unix Tools

Simple Log Analysis
Sorting versus in-memory aggregation
The Unix Philosophy
A uniform interface
Separation of logic and wiring
Transparency and experimentation

MapReduce and Distributed Filesystems

MapReduce Job Execution
Distributed execution of MapReduce
MapReduce workflows
Reduce-Side Joins and Grouping
Example: analysis of user activity events
Sort-merge joins
Bringing related data together in the same place
Handling skew
Map-Side Joins
Broadcast hash joins
Partitioned hash joins
Map-side merge joins
MapReduce workflows with map-side joins
The Output of Batch Workflows
Key-value stores as batch process output
Philosophy of batch process outputs
Comparing Hadoop to Distributed Databases
Diversity of storage
Diversity of processing models
Designing for frequent faults

Beyond MapReduce

Materialization of Intermediate State
Dataflow engines
Fault tolerance
Discussion of materialization
Graphs and Iterative Processing
The Pregel processing model
Fault tolerance
Parallel execution
High Level APIs and Languages
The move toward declarative query languages
Specialization for different domains


Chapter 11: Stream Processing

Transmitting Event Streams

Messaging Systems
Direct messaging from producers to consumers
Message brokers
Message brokers compared to databases
Multiple consumers
Acknowledgments and redelivery
Partitioned Logs
Using logs for message storage
Logs compared to traditional messaging
Consumer offsets
Disk space usage
When consumers cannot keep up with producers

Databases and Streams

Keeping Streams in Sync
Change Data Capture
Implementing change data capture
Initial snapshot
Log compaction
Event Sourcing
Deriving current state from the event log
Commands and events
State, Streams, and Immutability
Advantages of immutable events
Deriving several views from the same event log
Concurrency control
Limitations to immutability

Processing Streams

Uses of Stream Processing
Complex event processing
Stream analytics
Search on streams
Reasoning About Time
Event time versus processing time
Knowing when you're ready
Whose clock are you using, anyway?
Types of windows
Stream Joins
Stream-stream join (window join)
Stream-table join (stream enrichment)
Table-table join (materialized view maintenance)
Time-dependence of joins
Fault Tolerance
Microbatching and checkpointing
Atomic commit revisited
Rebuilding state after a failure


Chapter 12: The Future of Data Systems

Data Integration

Combining Specialized Tools by Deriving Data
Reasoning about dataflows
Derived data versus distributed transactions
The limits of total ordering
Ordering events to capture causality
Batch and Stream Processing
Maintaining derived state
Reprocessing data for application evolution
The lambda architecture

Unbundling Databases

Composing Data Storage Technologies
The meta-database of everything
Making unbundling work
Unbundling versus integrated systems
Designing Applications Around Dataflow
Application code as a derivation function
Separation of application code and state
Dataflow: Interplay between state changes and application code
Stream processors and services
Observed Derived State
Materialized views and caching
Stateful, offline-capable clients
Pushing state changes to clients
End-to-end event streams
Reads are events too
Multi-partition data processing

Aiming for Correctness

The End-to-End Argument for Databases
Exactly-once execution of an operation
Duplicate suppression
Uniquely identifying requests
The end-to-end argument
Applying end-to-end thinking in data systems
Enforcing Constraints
Uniqueness constraints require consensus
Uniqueness in log-based messaging
Multi-partition request processing
Timeliness and Integrity
Correctness of dataflow systems
Loosely interpreted constraints
Coordinating-avoiding data systems
Trust, but Verify
Maintaining integrity in the face of software bugs
Don't blindly trust what they promise
Designing for auditability
The end-to-end argument again
Tools for auditable data systems

Doing the Right Thing

Predictive Analytics
Bits and discrimination
Responsibility and accountability
Feedback loops
Privacy and Tracking
Consent and freedom of choice
Privacy and use of data
Data as assets and power
Remembering the Industrial Revolution

Tags: reading   storage  

Last modified 06 April 2022