Table of Content

Preface

• Who Should Read This Book?
• Scope of This Book
• Outline of This Book
• References and Further Reading
• O'Reilly Safari
• How to Contact Us
• Acknowledgments

1. Trade-offs in Data Systems Architecture

• Analytical versus Operational Systems
  • Characterizing Transaction Processing and Analytics
  • Data Warehousing
    • From data warehouse to data lake
    • Beyond the data lake
  • Systems of Record and Derived Data
• Cloud versus Self-Hosting
  • Pros and Cons of Cloud Services
  • Cloud-Native System Architecture
    • Layering of cloud services
    • Separation of storage and compute
  • Operations in the Cloud Era
• Distributed versus Single-Node Systems
  • Problems with Distributed Systems
  • Microservices and Serverless
  • Cloud Computing versus Supercomputing
• Data Systems, Law, and Society
• Summary
  • References

2. Defining Nonfunctional Requirements

• Case Study: Social Network Home Timelines
  • Representing Users, Posts, and Follows
  • Materializing and Updating Timelines
• Describing Performance
  • Latency and Response Time
  • Average, Median, and Percentiles
  • Use of Response Time Metrics
• Reliability and Fault Tolerance
  • Fault Tolerance
  • Hardware and Software Faults
    • Tolerating hardware faults through redundancy
    • Software faults
  • Humans and Reliability
• Scalability
  • Describing Load
  • Shared-Memory, Shared-Disk, and Shared-Nothing Architecture
  • Principles for Scalability
• Maintainability
  • Operability: Making Life Easy for Operations
  • Simplicity: Managing Complexity
  • Evolvability: Making Change Easy
• Summary
  • References

3. Data Models and Query Languages

• Relational Model versus Document Model
  • The Object-Relational Mismatch
    • Object-relational mapping (ORM)
    • The document data model for one-to-many relationships
  • Normalization, Denormalization, and Joins
    • Trade-offs of normalization
    • Denormalization in the social networking case study
  • Many-to-One and Many-to-Many Relationships
  • Stars and Snowflakes: Schemas for Analytics
  • When to Use Which Model
    • Schema flexibility in the document model
    • Data locality for reads and writes
    • Query languages for documents
    • Convergence of document and relational databases
• Graph-Like Data Models
  • Property Graphs
  • The Cypher Query Language
  • Graph Queries in SQL
  • Triple-Stores and SPARQL
    • The RDF data model
    • The SPARQL query language
  • Datalog: Recursive Relational Queries
  • GraphQL
• Event Sourcing and CQRS
• Dataframes, Matrices, and Arrays
• Summary
  • References

4. Storage and Retrieval

• Storage and Indexing for OLTP
  • Log-Structured Storage
    • The SSTable file format
    • Constructing and merging SSTables
    • Bloom filters
    • Compaction strategies
  • B-Trees
    • Making B-trees reliable
    • B-tree variants
  • Comparing B-Trees and LSM-Trees
    • Read performance
    • Sequential vs. random writes
    • Write amplification
    • Disk space usage
  • Multi-Column and Secondary Indexes
    • Storing values within the index
  • Keeping everything in memory
• Data Storage for Analytics
  • Cloud Data Warehouses
  • Column-Oriented Storage
    • Column Compression
    • Sort Order in Column Storage
    • Writing to Column-Oriented Storage
  • Query Execution: Compilation and Vectorization
  • Materialized Views and Data Cubes
• Multidimensional and Full-Text Indexes
  • Full-Text Search
  • Vector Embeddings
• Summary
  • References

5. Encoding and Evolution

• Formats for Encoding Data
  • Language-Specific Formats
  • JSON, XML, and Binary Variants
    • JSON Schema
    • Binary encoding
  • Protocol Buffers
    • Field tags and schema evolution
  • Avro
    • The writer’s schema and the reader’s schema
    • Schema evolution rules
    • But what is the writer’s schema?
    • Dynamically generated schemas
  • The Merits of Schemas
• Modes of Dataflow
  • Dataflow Through Databases
    • Different values written at different times
    • Archival storage
  • Dataflow Through Services: REST and RPC
    • Web services
    • The problems with remote procedure calls (RPCs)
    • Load balancers, service discovery, and service meshes
    • Data encoding and evolution for RPC
  • Durable Execution and Workflows
    • Durable execution
  • Event-Driven Architectures
    • Message brokers
    • Distributed actor frameworks
• Summary
  • References

6. Replication

• Single-Leader Replication
  • 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
• Problems with Replication Lag
  • Reading Your Own Writes
  • Monotonic Reads
  • Consistent Prefix Reads
  • Solutions for Replication Lag
• Multi-Leader Replication
  • Geographically Distributed Operation
    • Multi-leader replication topologies
    • Problems with different topologies
  • Sync Engines and Local-First Software
    • Real-time collaboration, offline-first, and local-first apps
    • Pros and cons of sync engines
  • Dealing with Conflicting Writes
    • Conflict avoidance
    • Last write wins (discarding concurrent writes)
    • Manual conflict resolution
    • Automatic conflict resolution
  • CRDTs and Operational Transformation
    • What is a conflict?
• Leaderless Replication
  • Writing to the Database When a Node Is Down
    • Catching up on missed writes
    • Quorums for reading and writing
  • Limitations of Quorum Consistency
    • Monitoring staleness
  • Single-Leader vs. Leaderless Replication Performance
    • Multi-region operation
  • Detecting Concurrent Writes
    • The “happens-before” relation and concurrency
    • Capturing the happens-before relationship
    • Version vectors
• Summary
  • References

7. Sharding

• Pros and Cons of Sharding
  • Sharding for Multitenancy
• Sharding of Key-Value Data
  • Sharding by Key Range
    • Rebalancing key-range sharded data
  • Sharding by Hash of Key
    • Hash modulo number of nodes
    • Fixed number of shards
    • Sharding by hash range
    • Consistent hashing
  • Skewed Workloads and Relieving Hot Spots
  • Operations: Automatic or Manual Rebalancing
• Request Routing
• Sharding and Secondary Indexes
  • Local Secondary Indexes
  • Global Secondary Indexes
• Summary
  • References

8. Transactions

• What Exactly Is a Transaction?
  • The Meaning of ACID
    • Atomicity
    • Consistency
    • Isolation
    • Durability
  • 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
    • Multi-version concurrency control (MVCC)
    • Visibility rules for observing a consistent snapshot
    • Indexes and snapshot isolation
    • Snapshot isolation, repeatable read, and naming confusion
  • Preventing Lost Updates
    • Atomic write operations
    • Explicit locking
    • Automatically detecting lost updates
    • Conditional writes (compare-and-set)
    • Conflict resolution and replication
  • Write Skew and Phantoms
    • Characterizing write skew
    • More examples of write skew
    • Phantoms causing write skew
    • Materializing conflicts
• Serializability
  • Actual Serial Execution
    • Encapsulating transactions in stored procedures
    • Pros and cons of stored procedures
    • Sharding
    • Summary of serial execution
  • 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
• Distributed Transactions
  • Two-Phase Commit (2PC)
    • A system of promises
    • Coordinator failure
    • Three-phase commit
  • Distributed Transactions Across Different Systems
    • Exactly-once message processing
    • XA transactions
    • Holding locks while in doubt
    • Recovering from coordinator failure
    • Problems with XA transactions
  • Database-internal Distributed Transactions
    • Exactly-once message processing revisited
• Summary
  • References

9. The Trouble with Distributed Systems

• Faults and Partial Failures
• Unreliable Networks
  • The Limitations of TCP
  • 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 with a confidence interval
    • Synchronized clocks for global snapshots
  • Process Pauses
    • Response time guarantees
    • Limiting the impact of garbage collection
• Knowledge, Truth, and Lies
  • The Majority Rules
  • Distributed Locks and Leases
    • Fencing off zombies and delayed requests
    • Fencing with multiple replicas
  • Byzantine Faults
    • Weak forms of lying
  • System Model and Reality
    • Defining the correctness of an algorithm
    • Safety and liveness
    • Mapping system models to the real world
  • Formal Methods and Randomized Testing
    • Model checking and specification languages
    • Fault injection
    • Deterministic simulation testing
• Summary
  • References

10. Consistency and Consensus

• Linearizability
  • What Makes a System Linearizable?
  • Relying on Linearizability
    • Locking and leader election
    • Constraints and uniqueness guarantees
    • Cross-channel timing dependencies
  • Implementing Linearizable Systems
    • Linearizability and quorums
  • The Cost of Linearizability
    • The CAP theorem
    • Linearizability and network delays
• ID Generators and Logical Clocks
  • Logical Clocks
    • Lamport timestamps
    • Hybrid logical clocks
    • Lamport/hybrid logical clocks vs. vector clocks
  • Linearizable ID Generators
    • Implementing a linearizable ID generator
    • Enforcing constraints using logical clocks
• Consensus
  • The Many Faces of Consensus
    • Single-value consensus
    • Compare-and-set as consensus
    • Shared logs as consensus
    • Fetch-and-add as consensus
    • Atomic commitment as consensus
  • Consensus in Practice
    • Using shared logs
    • From single-leader replication to consensus
    • Subtleties of consensus
    • Pros and cons of consensus
  • Coordination Services
    • Allocating work to nodes
    • Service discovery
• Summary
  • References

11. Batch Processing

• ……
• Summary
  • References

12. Stream Processing

• ……
• Summary
  • References

13. A Philosophy of Streaming Systems

• ……
• Summary
  • References

14. Doing the Right Thing

• ……
• Summary
  • References

Glossary

Colophon

• About the Author
• Colophon