distsys-class

An Introduction to Distributed Systems Copyright Kyle Kingsbury & Jepsen, LLC. This outline accompanies a 16 to 32 hour overview class on distributed systems fundamentals. The course aims to introduce software engineers to the practical basics of distributed systems, through lecture and discussion, and optional labwork. Participants will gain an intuitive understanding of key distributed systems terms, an overview of the algorithmic landscape, and explore production concerns. Intro My name is Kyle Kingsbury Pronouns: he/him Email: aphyr@jepsen.io This outline: https://github.com/aphyr/distsys-class I've worked on distributed systems from several perspectives 2003--2009: sysadmin, network operations, web developer 2009--2014: backend engineer, database wrangler at various web startups 2014--now: distributed systems safety testing (Jepsen) This class is aimed at practitioners "Things I Wish I Would Have Known" Backend engineers Frontend engineers Ops folks Product managers This class aims to prepare you to write, operate, and use distributed systems First half: theoretical framework A map of how concepts fit together Not about memorizing everything; it's about knowing where to look Establish a shared language To talk with your peers To read a paper To evaluate a system's claims Understand fundamental principles Time, ordering, nodes, networks, faults, liveness, safety Classes of algorithms What they can and can't do, when to apply each Second half: practical concerns A grab bag of design patterns Illustrative anecdotes Computers were, in fact, a mistake What isn't in the papers? Finally, production concerns Deployment, debugging, monitoring Class logistics This class is what you make of it We can go as deep as you want, or skip over familiar ground Jump in with questions, challenges, ideas at any time We'll take ~10-minute breaks every hour or so, plus lunch If you need to duck out for whatever reason, that's fine! Outages, kids, pets, whatever The outline on GitHub can help fill in the gaps You can ask me during class or a break about something you missed! I'll ask for your thoughts often, but you can also jump in whenever If you don't want to be called on, that's cool--please let me know If you think of something after class, you can email me! Or write it down for the next day's discussion Recording is prohibited Teaching is my livelihood And this outline is free! If we're doing labs: There are labs for this class! Mostly in the middle Remind folks of the prereq: Getting Ready If we're remote: You can turn off video whenever you like But please, if some people can be on video, that's really helpful Seeing faces helps me know whether the lecture is working for you! For the labs, we'll be doing a shared tmux session OK, let's get going! What makes a thing distributed? Lamport, 1987: A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable. First glance: *nix boxen in our colo, running processes communicating via TCP or UDP. Or boxes in EC2, Rackspace, etc Maybe communicating over InfiniBand Separated by inches and a LAN Or by kilometers and the internet Most mobile apps are also taking part in a distributed system Communicating over a truly awful network Same goes for desktop web browsers It's not just servers--it's clients too! More generally: distributed systems are Made up of parts which interact Slowly And often unreliably Whatever those mean for you So also: Redundant CPUs in an airplane ATMs and Point-of-Sale terminals Space probes Paying bills Doctors making referrals Trying to make plans via text message Every business meeting ever Nodes and networks We call each part of a distributed system a node Also known as processes, agents, or actors Nodes Characteristic latency Operations inside a node are "fast" Operations between nodes are "slow" What's fast or slow depends on what the system does Nodes are reliable Fail as a unit You know when problems occur State is coherent State transitions occur in a nice, orderly fashion Typically modeled as some kind of single-threaded state machine A node could itself be a distributed system But so long as that system as a whole provides "fast, coherent" operations, we can treat it as a single node. Formal models for processes Actor model Communicating Sequential Processes Pi-calculus Ambient calculus Formal models for node failure Crash-stop Crash-recover Crash-amnesia Byzantine Networks as message flows Nodes interact via a network Humans interact via spoken words Particles interact via fields Computers interact via IP, or UDP, or SCTP, or ... We model those interactions as discrete messages sent between nodes Messages take time to propagate This is the "slow" part of the distributed system We call this "latency" Messages can often be lost This is another "unreliable" part of the distributed system Network is rarely homogenous Some links slower/smaller/more-likely-to-fail than others Causality diagrams We can represent the interaction of nodes and the network as a diagram Time flows left-to-right, or top-to-bottom Nodes are lines in the direction of time (because they stay in place) Messages as slanted paths connecting nodes Synchronous networks Nodes execute in lockstep: time between node steps is always 1. Message delay is bounded Effectively a perfect global clock Easy to prove stuff about You probably don't have one Semi-synchronous networks Like synchronous, but the clock is only approximate, e.g. in [c, 1] Asynchronous networks Execute independently, whenever: step time is anywhere in [0, 1] Unbounded message delays No global clocks Weaker than semi- or synchronous networks Implies certain algorithms can't be as efficient Implies certain algorithms are impossible See e.g. Attiya & Mavronicolas, "Efficiency of Semi-Synchronous vs Asynchr