Think Distributed Systems (Dominik Tornow) (Z-Library)

📄 File Format: PDF

💾 File Size: 1.4 MB

📖 Read Online ⬇️ Download

Registered users can read the full content for free

Register as a Gaohf Library member to read the complete e-book online for free and enjoy a better reading experience.

📄 Page 1

M A N N I N G Dominik Tornow

📄 Page 2

State of C1 State of C3 State of C5 C1 C3 C5 C2 C4 C6 State of C2 State of C4 State of C6 N et w or k A distributed system is a collection of collaborating concurrent components that communicate by sending and receiving messages over a network. Each component has exclusive access to its own local state, which other components cannot access. The network has exclusive access to its own local state, including messages that are in flight. State State' State'' ... Step Step Step The behavior of the system is represented as a sequence of states, with each step transitioning the system from one state to the next. Each step is taken by either a component or the network. These steps can be categorized as follows: ¡ External steps—Actions such as receiving or sending a message ¡ Internal steps—Actions such as performing local computations or accessing the local state To summarize, we will think about the system as one in which at any moment, exactly one component or the network will complete exactly one step. State of C1 C1 C2 State of C2 Network There is only me... ...and the rest of the system.

📄 Page 3

Think Distributed Systems

📄 Page 4

(This page has no text content)

📄 Page 5

MANN I NG Shelter ISland Dominik Tornow Think Distributed Systems

📄 Page 6

For online information and ordering of this and other Manning books, please visit www.manning.com. The publisher offers discounts on this book when ordered in quantity. For more information, please contact Special Sales Department Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 Email: orders@manning.com © 2025 Manning Publications Co. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by means electronic, mechanical, photocopying, or otherwise, without prior written permission of the publisher. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in the book, and Manning Publications was aware of a trademark claim, the designations have been printed in initial caps or all caps. Recognizing the importance of preserving what has been written, it is Manning’s policy to have the books we publish printed on acid- free paper, and we exert our best efforts to that end. Recognizing also our responsibility to conserve the resources of our planet, Manning books are printed on paper that is at least 15 percent recycled and processed without the use of elemental chlorine. ∞ Manning Publications Co. 20 Baldwin Road PO Box 761 Shelter Island, NY 11964 ISBN 9781633436176 Printed in the United States of America The author and publisher have made every effort to ensure that the information in this book was correct at press time. The author and publisher do not assume and hereby disclaim any liability to any party for any loss, damage, or disruption caused by errors or omissions, whether such errors or omissions result from negligence, accident, or any other cause, or from any usage of the information herein. Development editor: Becky Whitney Technical editor: Arun Saha Review editor: Radmila Ercegovac Production editor: Andy Marinkovich Copy editor: Keir Simpson Proofreader: Jason Everett Typesetter: Tamara ŠveliÊ SabljiÊ Cover designer: Marija Tudor

📄 Page 7

To Jihyun

📄 Page 8

vi brief contents 1 ■ Thinking in distributed systems: Models, mindsets, and mechanics 1 2 ■ System models, order, and time 23 3 ■ Failure tolerance 40 4 ■ Message delivery and processing 55 5 ■ Transactions 67 6 ■ Distributed transactions 79 7 ■ Partitioning 90 8 ■ Replication 106 9 ■ Consistency 117 10 ■ Distributed consensus 131 11 ■ Durable executions 145 12 ■ Cloud and services 156

📄 Page 9

vii contents preface xii acknowledgments xiii about this book xiv about the author xvi about the cover illustration xvii 1 Thinking in distributed systems: Models, mindsets, and mechanics 1 1.1 Software engineering and mental models 2 Mental models: The foundation of reasoning 3  ■  Correct mental models 4  ■  Complete mental models 4 1.2 Mental model of software systems 4 1.3 Different types of models 5 Different models describing the same aspects 5 Different models describing different aspects of a system 6 1.4 Thinking about distributed systems 8 Correctness 9  ■  Scalability and reliability 12 Responsiveness 12 1.5 Two big ideas 13 Systems of systems 13  ■  Global view vs. local view 15 1.6 Distributed Systems Incorporated 16

📄 Page 10

viii contents 1.7 Navigating complexity 18 Simple yet complex 18  ■  Emergent behavior 19 Changing perspective 19  ■  Think globally; act locally 20 1.8 Thinking above the code 21 2 System models, order, and time 23 2.1 System models 23 Theory and practice 24  ■  Synchronous distributed systems 25 Asynchronous distributed systems 25  ■  Partially synchronous systems 26  ■  Component and network behavior 27 Realistic system models 30 2.2 Order and time 30 The happened-before relationship 32  ■  Time and clocks 35 Physical time and physical clocks 35  ■  Logical time and logical clocks 37  ■  Physical clocks vs. logical clocks 38 3 Failure tolerance 40 3.1 In theory 41 3.2 Types of failure tolerance 42 Masking failure tolerance 42  ■  Nonmasking failure tolerance 42 Fail-safe failure tolerance 43  ■  None of the above 43 3.3 In practice 44 System model 44  ■  Failure handling 46  ■  Failure classification 47  ■  Failure detection 50  ■  Failure mitigation 52  ■  Putting everything together 52 4 Message delivery and processing 55 4.1 Exchanging messages 56 4.2 The uncertainty principle of message delivery and processing 58 Before sending the request 59  ■  After sending the request and before receiving a response 59  ■  After receiving a response 59 4.3 Silence and chatter 60 4.4 Exactly-once processing semantics 62 4.5 Idempotence 62 4.6 Case study: Charging a credit card 64

📄 Page 11

ixcontents 5 Transactions 67 5.1 Abstractions 68 5.2 The magic of transactions 70 Concurrency 70  ■  Failure 71 5.3 The model of transactions 72 Correctness 74  ■  Serializability 75  ■  Completeness 77 Application-level abort 77  ■  Platform-level abort 78 6 Distributed transactions 79 6.1 Atomic commitment: From a single RM to multiple RMs 79 Transaction on a single RM 81  ■  Transaction on multiple RMs 81  ■  Blocking and nonblocking 82 6.2 The essence of distributed transactions 82 6.3 Two-Phase Commit protocol 83 In the absence of failure 83  ■  In the presence of failure 85 Improvement 86 7 Partitioning 90 7.1 Encyclopedias and volumes 90 7.2 Thinking in partitions 92 7.3 The mechanics of partitioning and balancing 93 7.4 (Re)partitioning 94 Types of partitioning 94  ■  Data item to partition assignment strategies 97 7.5 Common item-based assignment strategies 99 Range partitioning 100  ■  Hash partitioning 100 7.6 Repartitioning 101 Range partitioning 101  ■  Hash partitioning 102 7.7 Consistent hashing 103 7.8 (Re)balancing and overpartitioning 103 8 Replication 106 8.1 Redundancy 107 8.2 Thinking about replication and consistency 109 8.3 Replication 110

📄 Page 12

x contents 8.4 The mechanics of replication 111 System model 111  ■  Replication lag 112  ■  Synchronous vs. asynchronous replication 113  ■  State-based vs. log-based replication 114  ■  Single-leader, multileader, and leaderless systems 114 9 Consistency 117 9.1 Consistency models 117 Common consistency models 119  ■  Virtues and limitations 119 9.2 Linearizability 121 Queue and stack 122  ■  Formal definition of linearizability 123 9.3 Eventual consistency 124 The shopping cart 124  ■  Variants of eventual consistency 125 Implementation 125 9.4 Consistency, availability, and partition tolerance 126 History 126  ■  Conjecture vs. theorem 127 CAP theorem 128 10 Distributed consensus 131 10.1 The challenge of reaching agreement 132 10.2 System model 132 10.3 State machine replication 133 10.4 The origin—and irony—of consensus 134 10.5 Implementing consensus 135 Leader-based consensus 135  ■  Quorum-based consensus 136 Combining leader and quorum 136 10.6 Raft 136 The log 137  ■  Terms 138  ■  Leader Election protocol 139 Log Replication protocol 140  ■  State machine safety 141 10.7 Raft puzzles 141 Puzzle 1 141  ■  Puzzle 2 142  ■  Puzzle 3 142 11 Durable executions 145 11.1 The pitfalls of partial executions 145 11.2 System model 147 Process definition 148  ■  Process execution 148

📄 Page 13

xicontents 11.3 The concept of failure-transparent recovery 149 11.4 Strategies of failure-transparent recovery 150 Restart 150  ■  Resume 151 11.5 Implementation of failure-transparent recovery 152 Application-level implementation: Sagas 152 Platform-level implementation: Durable execution 153 12 Cloud and services 156 12.1 From proactive to reactive 157 12.2 Cloud computing 157 12.3 Cloud-native computing 158 12.4 Serverless computing 159 Traditional 160  ■  Serverless 160  ■  Cold path vs. hot path 161 12.5 Service 161 Global view vs. local view 162  ■  Example recommendation service 163 12.6 Final thoughts 166 index 168

📄 Page 14

xii preface As an engineer, I am never more confident than when I truly understand a complex concept. When you deeply understand a system’s underlying mechanics, you can explain where the system is coming from and predict where the system is going. Over the course of my career working with distributed systems, I’ve focused on sys- tems thinking and modeling to develop dependable mental models—models that cut through doubt and bring distributed systems into focus. In this book, I want to share the mental models I’ve developed over 20 years. More important, I want to show you how to construct your own, replacing confusion with clar- ity, and hesitance with confidence so that you can experience the deep satisfaction of distributed systems engineering along with me.

📄 Page 15

xiii acknowledgments To my wife, Jihyun, whose encouragement and dedication made this book possible. Thank you for being on this journey with me. To my friends, who listened to me talk about distributed systems far more than any- one should have to and still wanted to spend time with me. To my colleagues and collaborators, whose challenging and insightful discussions over the years helped forge the mental models presented in these pages. To the publishers, editors, and technical staff at Manning, whose commitment and constructive feedback transformed rough ideas into clear explanations—this book is immeasurably better for your contributions. To all the reviewers: Abhay Paroha, Advait P, Ajay Thakur, Alankrit Kharbanda, Alok Ranjan, Anu Engineer, Anurag Kumar Jain, Arijit Dasgupta, Arjun Chakraborty, Ash- win Das Gururaja, Bhala Ranganathan, Bhavin Thaker, Bhupendra Singh, Carlos J. Cela, Deep Bodra, Dinesh Chitlangia, Eric Normand, Hari Mani, Jayasekhar Konduru, Karthik Penikalapati, Koushik Vikram, Krishna Kumaar, Luis Soares, Maneesh Karnati, Manikandan Vellore Muneeswaran, Marcos Oliveira, Michaeljon Miller, Naga Rishy- endar Panguluri, Narendra Reddy Sanikommu, Neha Shetty, Ori Pomerantz, Pradeep Kumar Goudagunta, Prasann Pradeep Patil, Prit Sheth, Pronnoy Goswami, Raja Rao Budaraju, Raju Ansari, Ramprasad C, Ravi Laudya, Ravi Soni, Ravi Teja Thutari, Saket Chaudhari, Samarth Shah, Sandeep Guggilam, Sandhya Vinjam, Shankar, Shubham Malhotra, Siddhartha Singh, Suresh Bysani Venkata Naga, Tharun Mothukuri, Tony Bernardino, Vaibhav Mahindroo, Vaibhav Tupe, Vishal Chaurasia, VVS Sundeep Akella, and Zhihao Yao; your thoughtful questions, comments, and evaluations pushed me to strengthen every chapter.

📄 Page 16

xiv about this book Every modern application is a distributed system. Yet despite their ubiquity, distributed systems remain notoriously difficult to understand, design, and implement. This book bridges that gap, taking you from novice or intermediate to expert, by providing the understanding and mental models you need to reason about and architect complex distributed systems with confidence. Although many resources teach specific technologies, frameworks, or platforms, Think Distributed Systems focuses on enduring principles and patterns that go beyond any single implementation. This book is not just another catalog of algorithms or protocols. Instead, it teaches you to think like a distributed systems engineer, understanding the core concepts and mechanics that define real-world distributed systems. Who should read this book? This book is for software engineers who want to build a solid foundation in distributed systems. You don’t need experience; the journey begins from first principles and builds toward advanced topics. If you’ve worked with distributed systems but found yourself frustrated by fuzzy mental models and vague intuitions, this book will transform uncer- tainty into clarity and bring complex ideas into focus. How this book is organized: A road map The book is organized into 12 chapters, taking you from fundamental to advanced concepts: ¡ Chapter 1 introduces distributed systems and their characteristics. ¡ Chapter 2 examines system models and assumptions about processes, networks, and time.

📄 Page 17

xvabout this book ¡ Chapter 3 covers failure, failure tolerance, and failure transparency. ¡ Chapter 4 explores message delivery and message processing guarantees. ¡ Chapter 5 covers transactions and atomic commitment. ¡ Chapter 6 covers distributed transactions and protocols like Two-Phase Commit. ¡ Chapter 7 examines partitioning to improve scalability. ¡ Chapter 8 examines replication to improve reliability. ¡ Chapter 9 discusses consistency models and the CAP theorem. ¡ Chapter 10 explores state machine replication and distributed consensus. ¡ Chapter 11 discusses durable execution. ¡ Chapter 12 explores cloud computing, cloud-native computing, serverless com- puting, and microservices. About the code This book deliberately features few code examples. The challenges in distributed sys- tems arise from the interactions between components, not from the implementation of one component. Instead of presenting code fragments and expecting you to deduce the distributed behavior, I use system models and illustrations to show you exactly how components communicate, collaborate, and compete, revealing the essential behav- iors that characterize distributed systems with clarity. liveBook discussion forum Purchase of Think Distributed Systems includes free access to liveBook, Manning’s online reading platform. Using liveBook’s exclusive discussion features, you can attach com- ments to the book globally or to specific sections or paragraphs. It’s a snap to make notes for yourself, ask and answer technical questions, and receive help from the author and other users. To access the forum, go to https://livebook.manning.com/ book/think-distributed-systems/discussion. Manning’s commitment to our readers is to provide a venue where meaningful dia- logue between individual readers and between readers and the author can take place. It is not a commitment to any specific amount of participation on the part of the author, whose contribution to the forum remains voluntary (and unpaid). We suggest you try asking the author some challenging questions lest their interest stray! The forum and the archives of previous discussions will be accessible on the publisher’s website as long as the book is in print.

📄 Page 18

xvi about the author Dominik Tornow is the founder and CEO of Resonate HQ, Inc. He studied software systems engineering at the Hasso Plattner Institute in Potsdam, Germany, and brings more than two decades of industry experience to his work. Dominik specializes in systems engineering, systems thinking, and systems modeling with a focus on formal and conceptual techniques that ensure that concurrent distributed systems are correct by construc- tion. He is a prolific writer, a frequent speaker at leading industry conferences, and the holder of multiple soft- ware patents.

📄 Page 19

xvii about the cover illustration The figure on the cover of Think Distributed Systems, captioned “Liburnienne,” or “Liburnian,” was published by Nepveu (Paris) in 1815 and is taken from a collection provided by Bibliothèque nationale de France. The Liburnians were an ancient tribe inhabiting the district called Liburnia, a coastal region of the northeastern Adriatic between the rivers Arsia (Raša) and Titius (Krka) in what is now Croatia. Each illustra- tion is finely drawn and colored by hand. In those days, it was easy to identify where people lived and what their trade or station in life was just by their dress. Manning celebrates the inventiveness and initiative of the computer business with book covers based on the rich diversity of regional culture cen- turies ago, brought back to life by pictures from collections such as this one.

📄 Page 20

(This page has no text content)