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