Leseliste zu verteilten Systemen (2014)
(dancres.github.io)- Der Kern beim Lernen verteilter Systeme liegt weniger in bestimmten Technologien als in einem Wandel der Denkweise; diese Liste führt thematisch durch die Probleme, die beim Entwurf von Systemen in Internetgröße auftreten
- Die Materialien sind gegliedert in Designphilosophie, Latenz, Fallstudien großer Systeme von Amazon und Google, Konsistenzmodelle, Theorie, Tools, Infrastruktur, Storage, Konsensalgorithmen, Gossip-Protokolle und P2P
- CAP, die Vermeidung von 2PC, eventual consistency und optimistische Replikation zeigen die operativen Trade-offs, weil Konsistenz und Verfügbarkeit kaum gleichzeitig maximiert werden können
- Die Google-Papers liefern Implementierungsbeispiele für große verteilte Systeme wie MapReduce, Chubby, GFS, BigTable, Dremel, Spanner, Photon und Mesa; die Amazon-Materialien behandeln zugleich den Wandel zu einer servicebasierten Architektur und die Organisationskultur
- Wer Paxos, Raft, FLP, Lamport Clock, Byzantine Generals sowie Chord, Kademlia und Pastry in dieser Reihenfolge liest, kann die Themen Konsens, Zeit, Replikation und Routing als zusammenhängenden Bogen einordnen
Denkweise und Designperspektive
- Der schwierigste Teil verteilter Systeme ist es, die Art des Denkens zu verändern; die Liste beginnt mit Artikeln und Papers, die diesen Übergang unterstützen
- „Thought Provokers“ behandeln die Sichtweise, dass sich nicht alle Probleme allein mit großen Servern, Datenbanken und Transaktionen lösen lassen
- Harvest, Yield and Scalable Tolerant Systems: behandelt die praktische Anwendung von CAP
- On Designing and Deploying Internet Scale Services: Material von James Hamilton zum Design und Deployment von Services in Internetgröße
- The Perils of Good Abstractions: behandelt, warum es schwierig ist, perfekte APIs und Interfaces zu schaffen
- Chaotic Perspectives: betont Unvorhersehbarkeit, Unordnung und Parallelität großer Systeme
- Ebenfalls enthalten sind Pat Hellands Data on the Outside versus Data on the Inside, Memories, Guesses and Apologies und Building on Quicksand
- Jim Waldos Why Distributed Computing? sowie A Note on Distributed Computing von Waldo, Wollrath und anderen sind ebenfalls begleitende Lektüre
Latenz und Services in Internetgröße
- „Latency“ behandelt, wie Architektur durch die Annahme beeinflusst wird, dass Latenz immer existiert
- Latency Exists, Cope!: behandelt den Umgang mit Latenz und deren architektonische Auswirkungen
- Latency - the new web performance bottleneck: behandelt Latenz als Performance-Flaschenhals im Web
- The Tail At Scale: behandelt Latenz in großen Systemen, insbesondere das Problem der Tail Latency
- Die Amazon-Materialien betrachten nicht nur Technologieentscheidungen, sondern auch Kultur und Organisation, die im Zuge des Wechsels zu einer servicebasierten Architektur entstanden sind
- A Conversation with Werner Vogels: behandelt Amazons Wechsel zu einer servicebasierten Architektur
- Discipline and Focus: behandelt ergänzend Amazons Wechsel zu einer servicebasierten Architektur
- Vogels on Scalability und SOA creates order out of chaos @ Amazon sind ebenfalls enthalten
Google-System-Papers und Konsistenzmodelle
- Das Google-Paket versammelt von MapReduce bis Mesa an einem Ort Papers zu großen Systemen, die man als „rocket science“ verteilter Systeme betrachten kann
- MapReduce
- Chubby Lock Manager
- Google File System
- BigTable
- Dremel: interaktive Analyse von Web-Scale-Datensätzen
- Megastore: Design für eine niedriglatente Paxos-Implementierung zwischen Rechenzentren
- Spanner: Googles skalierbare, multiversionale, global verteilte und synchron replizierte Datenbank
- Photon: fehlertolerante und skalierbare Joins kontinuierlicher Datenströme
- Mesa: georepliziertes, nahezu echtzeitfähiges und skalierbares Data Warehouse, das zentrale Messdaten für Googles Internet-Werbegeschäft speichert
- „Consistency Models“ besteht aus Materialien, die je nach Systemumgebung den Kompromiss zwischen Konsistenz und Verfügbarkeit ausloten
- CAP Conjecture: darüber, dass Consistency, Availability und Partition Tolerance nicht gleichzeitig vollständig erfüllt werden können
- CAP Twelve Years Later: Eric Brewer erweitert die ursprüngliche Erklärung des Trade-offs
- Enthalten sind Werner Vogels’ Consistency and Availability und Eventual Consistency
- Avoiding Two-Phase Commit und 2PC or not 2PC, Wherefore Art Thou XA? behandeln die Vermeidung und Grenzen von Two-Phase Commit
- Starbucks doesn't do two phase commit: behandelt asynchrone Mechanismen
- Optimistic Replication: behandelt einen Ansatz mit gelockerter Konsistenz für Datenreplikation
Theorie, Sprachen, Infrastruktur, Storage
- „Theory“ bündelt Materialien, die helfen, die in Designs verteilter Systeme immer wieder auftauchenden Themen Ökonomie, Fehlerannahmen, Zeit und Grenzen des Konsenses zu verstehen
- Distributed Computing Economics: Jim Gray
- Rules of Thumb in Data Engineering: Jim Gray und Prashant Shenoy
- Fallacies of Distributed Computing: Peter Deutsch
- Impossibility of distributed consensus with one faulty process: ein auch als FLP bekanntes Paper; für den Zugriff kann ein Konto oder eine Zahlung nötig sein, ein Link zu einer kostenlosen Version wird ebenfalls bereitgestellt
- Unreliable Failure Detectors for Reliable Distributed Systems: ein Umgang mit den Schwierigkeiten von FLP
- Lamport Clocks: das Problem, eine globale Sicht auf Zeit zu schaffen, wenn die Uhren einzelner Computer unabhängig sind
- The Byzantine Generals Problem
- Materialien zu Sprachen und Tools zeigen, dass Zuverlässigkeitsprobleme nicht verschwinden, nur weil man eine bestimmte Technologie auswählt
- Programming Distributed Erlang Applications: Pitfalls and Recipes: Die Wahl von Erlang und OTP allein vereinfacht den Aufbau zuverlässiger verteilter Anwendungen nicht automatisch
- Die Infrastruktur-Materialien behandeln, dass Uhrenmanagement selbst für grundlegende Aufgaben wie Debugging unverzichtbar ist
- Die Storage-Materialien führen weiter zu Designs für verteiltes Caching und Storage-Systeme wie Dynamo
Konsens, Gossip, P2P
- Das Paxos-Paket setzt bei der Annahme an, dass schon das Verständnis von Paxos schwierig ist, und empfiehlt, Paxos Made Simple zuerst zu lesen und nach den anderen Papers erneut darauf zurückzukommen
- The Part-Time Parliament: Leslie Lamport
- Paxos Made Simple: Leslie Lamport
- Paxos Made Live - An Engineering Perspective: Chandra und andere
- Revisiting the Paxos Algorithm: Lynch und andere
- How to build a highly available system with consensus: Butler Lampson
- Reconfiguring a State Machine: Änderung der Cluster-Mitgliedschaft
- Implementing Fault-Tolerant Services Using the State Machine Approach: Tutorial von Fred Schneider
- Weitere Konsens-Papers behandeln WAN-Umgebungen und Alternativen zu Paxos
- Mencius: Konsensalgorithmus für Weitverkehrsnetze
- In Search of an Understandable Consensus Algorithm: erweiterte Version des Raft-Papers und Alternative zu Paxos
- Die Materialien zu Gossip-Protokollen bündeln Kommunikations-, Monitoring- und Membership-Protokolle mit epidemischem Verhalten
- How robust are gossip-based communication protocols?
- Astrolabe: robuste und skalierbare Technik für Monitoring, Management und Data Mining verteilter Systeme
- SWIM: skalierbares, schwach konsistentes Prozessgruppen-Membership-Protokoll im Infection-Style
- Die P2P-Materialien führen durch verteilte Suche, Routing, Storage und Multicast auf Anwendungsebene
- Chord: skalierbares P2P-Suchprotokoll für Internetanwendungen
- Kademlia: P2P-Informationssystem auf Basis einer XOR-Metrik
- Pastry: skalierbare und verteilte Objektlokalisierung und Routing für große P2P-Systeme
- PAST: groß angelegte persistente P2P-Storage-Utility auf Pastry
- SCRIBE: große verteilte Multicast-Infrastruktur auf Anwendungsebene für Weitverkehrs-Messaging auf Pastry
1 Kommentare
Hacker-News-Kommentare
Diese Liste wirkt etwas veraltet; ich empfehle Heidi Howards Leseliste zu Distributed Consensus
https://github.com/heidihoward/distributed-consensus-reading...
Es kam mir seltsam vor, dass Googles MapReduce als die „Rocket Science“ dieses Bereichs dargestellt wird
Beim Nachsehen stellte sich heraus, dass diese Liste von 2014 stammt [1]; heute hat sich die Lage stark verändert, daher ist Vorsicht geboten
[1] https://news.ycombinator.com/from?site=dancres.github.io
Es gibt eine Meta-Liste von Leselisten zu verteilten Systemen, die ich vor etwa 10 Jahren erstellt habe
Auch diese Liste habe ich ungefähr 10 Jahre zu spät ergänzt, und wer weiß, wie viele der Einträge, die ich gesammelt habe, heute noch erreichbar sind
https://gist.github.com/macintux/6227368
Ebenfalls sehenswert ist https://ferd.ca/a-distributed-systems-reading-list.html, wo die ursprüngliche Liste erwähnt wird
Für Leute, die Grenzen ausloten oder neue Ansätze suchen, kann sie hilfreich sein; für alle anderen fühlt es sich so an, als würde man fragen, wie man quadratische Gleichungen löst, und bekäme 100 Papers zur Kategorientheorie
Fred Herberts Liste ist aktueller als die ursprüngliche, aber nach seinen eigenen Worten ebenfalls nicht vollständig. Er nennt „Designing Data-Intensive Applications“ als Pflichtlektüre, sagt aber sinngemäß, dass man für echtes Verständnis zuerst viele Papers lesen müsse
Wenn solche Listen als Voraussetzung fürs Verständnis präsentiert werden, kann das wie künstliches Hochsetzen der Einstiegshürde wirken
Dank der über Jahrzehnte gewachsenen Arbeit anderer muss man nicht 100 Papers über Nanokernel lesen, um ein effektiver Linux-Nutzer zu werden. Ein gutes Betriebssystem von Grund auf zu bauen, ist weiterhin schwierig, aber 99 % müssen das nicht tun; es reicht, vorhandene Tools sicher zu beherrschen
Bei verteilten Systemen ist es ähnlich: Wenn man nicht die Forschungsfront vorantreibt, muss es nicht derart schwierig sein
Software Engineers, die statt tief in die Forschung einzusteigen lieber Praxiserfahrung sammeln wollen, sollten mit NATS [1] oder YugaByte [2] etwas bauen oder ein praktisches Tutorial wie [3] durcharbeiten
Auch „Designing Data-Intensive Applications“ ist lesenswert. Es ist eines dieser Bücher, die bei jedem erneuten Lesen besser werden; man kann es einfach lesen, auch ohne 100 Papers gelesen zu haben. Wenn man auf unverständliche Stellen stößt, kann man Fragen stellen und sich Hilfe holen, und die riesigen Leselisten ruhig überspringen
1: https://nats.io/
2: https://www.yugabyte.com/
3: https://pragprog.com/titles/tjgo/distributed-services-with-g...
Und trotzdem keine Erwähnung von CRDT-Technologie?