Patterns of Distributed Systems

Foreword xvii
Preface xix
Acknowledgments xxiii
About the Author xxv

Part I: Narratives 1

Chapter 1: The Promise and Perils of Distributed Systems 3
The Limits of a Single Server 3
Separate Business Logic and Data Layer 5
Partitioning Data 6
A Look at Failures 7
Replication: Masking Failures 9
Defining the Term "Distributed Systems" 10
The Patterns Approach 10

Chapter 2: Overview of the Patterns 13
Keeping Data Resilient on a Single Server 14
Competing Updates 15
Dealing with the Leader Failing 17
Multiple Failures Need a Generation Clock 21
Log Entries Cannot Be Committed until They Are Accepted by a Majority Quorum 26
Followers Commit Based on a High-Water Mark 29
Leaders Use a Series of Queues to Remain Responsive to Many Clients 34
Followers Can Handle Read Requests to Reduce Load on the Leader 40
A Large Amount of Data Can Be Partitioned over Multiple Nodes 42
Partitions Can Be Replicated for Resilience 45
A Minimum of Two Phases Are Needed to Maintain Consistency across Partitions 46
In Distributed Systems, Ordering Cannot Depend on System Timestamps 49
A Consistent Core Can Manage the Membership of a Data Cluster 58
Gossip Dissemination for Decentralized Cluster Management 62

Part II: Patterns of Data Replication 69

Chapter 3: Write-Ahead Log 71
Problem 71
Solution 71
Examples 76

Chapter 4: Segmented Log 77
Problem 77
Solution 77
Examples 79

Chapter 5: Low-Water Mark 81
Problem 81
Solution 81
Examples 83

Chapter 6: Leader and Followers 85
Problem 85
Solution 85
Examples 92

Chapter 7: HeartBeat 93
Problem 93
Solution 93
Examples 98

Chapter 8: Majority Quorum 99
Problem 99
Solution 100
Examples 102

Chapter 9: Generation Clock 103
Problem 103
Solution 104
Examples 107

Chapter 10: High-Water Mark 109
Problem 109
Solution 109
Examples 115

Chapter 11: Paxos 117
Problem 117
Solution 117
Examples 132

Chapter 12: Replicated Log 133
Problem 133
Solution 133
Examples 158

Chapter 13: Singular Update Queue 159
Problem 159
Solution 159
Examples 166

Chapter 14: Request Waiting List 167
Problem 167
Solution 167
Examples 173

Chapter 15: Idempotent Receiver 175
Problem 175
Solution 175
Examples 181

Chapter 16: Follower Reads 183
Problem 183
Solution 183
Examples 191

Chapter 17: Versioned Value 193
Problem 193
Solution 193
Examples 201

Chapter 18: Version Vector 203
Problem 203
Solution 203
Examples 216

Part III: Patterns of Data Partitioning 217

Chapter 19: Fixed Partitions 219
Problem 219
Solution 220
Examples 241

Chapter 20: Key-Range Partitions 243
Problem 243
Solution 244
Examples 255

Chapter 21: Two-Phase Commit 257
Problem 257
Solution 257
Examples 297

Part IV: Patterns of Distributed Time 299

Chapter 22: Lamport Clock 301
Problem 301
Solution 301
Examples 307

Chapter 23: Hybrid Clock 309
Problem 309
Solution 309
Examples 316

Chapter 24: Clock-Bound Wait 317
Problem 317
Solution 318
Examples 332

Part V: Patterns of Cluster Management 335

Chapter 25: Consistent Core 337
Problem 337
Solution 337
Examples 342

Chapter 26: Lease 345
Problem 345
Solution 345
Examples 354

Chapter 27: State Watch 355
Problem 355
Solution 355
Examples 362

Chapter 28: Gossip Dissemination 363
Problem 363
Solution 363
Examples 373

Chapter 29: Emergent Leader 375
Problem 375
Solution 375
Examples 392

Part VI: Patterns of Communication between Nodes 393

Chapter 30: Single-Socket Channel 395
Problem 395
Solution 395
Examples 397

Chapter 31: Request Batch 399
Problem 399
Solution 399
Examples 404

Chapter 32: Request Pipeline 405
Problem 405
Solution 405
Examples 408

References 409
Index 413