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"