10 · Distributed Systems
10 · ระบบกระจาย
This chapter is the floor where "the computer" stops being a noun — the machine is now many machines, and the abstraction of one is something you have to build.
ชั้นนี้คือที่ที่ "คอมพิวเตอร์" เลิกเป็นคำนามเดี่ยว — เครื่องกลายเป็นหลายเครื่อง และนามธรรม (abstraction) ของการเป็นหนึ่งเดียวคือของที่ต้องสร้างเอง
What breaks when there is no "now"?
ไม่มี "ตอนนี้" แล้วอะไรพัง
At 22:52 UTC on 21 October 2018, engineers replacing failing optical equipment briefly severed the link between GitHub's East Coast network hub and its primary East Coast data center. Connectivity was restored in forty-three seconds. In those seconds the system that keeps the databases healthy did exactly what it was built to do: unable to reach the East Coast primaries, it promoted replicas on the West Coast. Writes had by then been accepted on both coasts. Neither side was wrong, neither could be discarded, and reconciling them took twenty-four hours and eleven minutes (GitHub post-incident analysis).
สายที่ขาดไป 43 วินาที ทำให้ GitHub ต้องใช้เวลา 24 ชั่วโมง 11 นาที ตามเก็บกวาด เวลา 22:52 UTC วันที่ 21 ตุลาคม 2018 วิศวกรกำลังถอดเปลี่ยนอุปกรณ์ใยแก้วนำแสงที่เสีย และตัดลิงก์ระหว่างศูนย์เครือข่ายฝั่งตะวันออกของ GitHub กับดาต้าเซ็นเตอร์หลักฝั่งตะวันออกไปชั่วขณะ ในช่วงเวลานั้นเอง ระบบที่คอยดูแลสุขภาพของฐานข้อมูลทำงานตามที่ถูกสร้างมาให้ทำเป๊ะๆ — ติดต่อ primary ฝั่งตะวันออกไม่ได้ มันจึงเลื่อน replica ฝั่งตะวันตกขึ้นเป็น primary แทน ถึงตอนนั้นข้อมูลถูกเขียนรับเข้าไปแล้วทั้งสองฝั่ง ไม่มีฝั่งไหนผิด ไม่มีฝั่งไหนทิ้งได้ และการประสานทั้งสองฝั่งให้ตรงกันใหม่กินเวลาไปเท่านั้น (GitHub post-incident analysis)
Nothing failed. That is the shape of every hard problem on this floor. The link came back, the machines were healthy, the failover logic was correct — and the system still could not say what had happened, because for forty-three seconds there was no shared answer to the question what is true right now.
ไม่มีอะไรพังสักอย่าง นั่นคือรูปร่างของปัญหายากทุกข้อบนชั้นนี้ ลิงก์กลับมา เครื่องทุกเครื่องแข็งแรงดี ตรรกะ failover ก็ถูกต้อง แต่ระบบยังบอกไม่ได้ว่าเกิดอะไรขึ้น เพราะตลอด 43 วินาทีนั้นไม่มีคำตอบร่วมกันสักคำตอบเดียวสำหรับคำถามว่า ตอนนี้อะไรคือความจริง
Start with why that question has no easy answer. Two machines have two clocks, clocks drift, and no amount of care makes a timestamp from one comparable with a timestamp from the other. Leslie Lamport's response, in 1978, was to stop asking for time and ask only for order. His "happened before" relation says one event precedes another if they occur in sequence on the same machine, or if the first is the sending of a message and the second its receipt — plus whatever follows by chaining those together. Everything else is concurrent: genuinely unordered, so that any consistent story about which came first is as good as any other (Lamport, CACM 21(7), 1978). Physics reached this first: simultaneity is not absolute, and the only real ordering is the one causation can carry. In a distributed system, messages are the light cones.
คำถามนั้นไม่มีคำตอบง่ายๆ เพราะเครื่องสองเครื่องมีนาฬิกาสองเรือน นาฬิกาเหวี่ยงออกจากกัน และต่อให้ระวังแค่ไหน timestamp ของเครื่องหนึ่งก็เทียบกับของอีกเครื่องไม่ได้ Leslie Lamport ตอบเรื่องนี้ในปี 1978 ด้วยการเลิกถามหาเวลา เหลือถามหาแค่ ลำดับ ความสัมพันธ์ "happened-before" ของเขาบอกว่าเหตุการณ์หนึ่งเกิดก่อนอีกเหตุการณ์ก็ต่อเมื่อทั้งคู่เกิดตามลำดับบนเครื่องเดียวกัน หรือเหตุการณ์แรกคือการส่งข้อความและเหตุการณ์หลังคือการรับข้อความนั้น บวกกับอะไรก็ตามที่ไล่ต่อกันเป็นสายจากสองแบบนี้ ที่เหลือทั้งหมดคือ concurrent — ไม่มีลำดับจริง เรื่องเล่าที่สอดคล้องกันเองแบบไหนก็ตามว่าอะไรมาก่อน ย่อมดีเท่ากันหมด (Lamport, CACM 21(7), 1978) ฟิสิกส์ถึงข้อสรุปนี้ก่อน: ความพร้อมกันไม่ใช่สิ่งสัมบูรณ์ ลำดับที่แท้จริงมีแค่ลำดับที่ความเป็นเหตุเป็นผลพาไปได้ ในระบบกระจาย ข้อความคือ light cone
The second difficulty is worse, because no formalism softens it. On one machine a component either works or has crashed. Across machines there is a third state indistinguishable from the other two: no answer yet. A silent peer may be dead, overloaded, or healthy behind a broken link, and no timeout separates these: a timeout says the answer has not arrived, never that it will not. Lamport's much-quoted definition captures what this does to the experience of building anything: "A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable" (Lamport, 28 May 1987). Failure here is not an event. It is an ambiguity.
ปัญหาที่สองหนักกว่า เพราะไม่มีรูปแบบทางคณิตศาสตร์ไหนช่วยผ่อนมันได้ บนเครื่องเดียว คอมโพเนนต์หนึ่งไม่ทำงานอยู่ก็ล่มไปแล้ว ข้ามเครื่องกันมีสถานะที่สามที่แยกจากสองแบบแรกไม่ออก คือ ยังไม่มีคำตอบ เพื่อนร่วมเครือข่ายที่เงียบไปอาจตายแล้ว อาจโหลดเกิน หรืออาจแข็งแรงดีแต่อยู่หลังลิงก์ที่ขาด ไม่มี timeout ไหนแยกสามอย่างนี้ออกจากกัน — timeout บอกได้แค่ว่าคำตอบยังไม่มา ไม่เคยบอกว่ามันจะไม่มา นิยามที่ถูกอ้างบ่อยที่สุดของ Lamport จับภาพว่าเรื่องนี้ทำอะไรกับประสบการณ์การสร้างของทุกอย่าง — "ระบบกระจายคือระบบที่ความล้มเหลวของคอมพิวเตอร์เครื่องหนึ่งซึ่งคุณไม่รู้ด้วยซ้ำว่ามีอยู่ สามารถทำให้คอมพิวเตอร์ของคุณเองใช้งานไม่ได้" (A distributed system is one in which the failure of a computer you didn't even know existed can render your own computer unusable) (Lamport, 28 May 1987) ความล้มเหลวตรงนี้ไม่ใช่เหตุการณ์ มันคือความกำกวม
Given ambiguity, can machines at least agree on one value — which replica is primary, which transaction committed, who holds the lock? This is the consensus problem, and it is the hardest thing here. Fischer, Lynch and Paterson proved in 1985 that in an asynchronous system, where messages can be delayed arbitrarily, no deterministic protocol can guarantee that all correct processes decide if even one process may crash (JACM 32(2): 374–382). The proof is not about bad engineering. It is the impossibility of telling a dead process from a slow one, elevated into a theorem.
อยู่กับความกำกวมแบบนั้น เครื่องต่างๆ ยังพอตกลงกันได้สักค่าเดียวไหม — replica ไหนคือ primary, transaction ไหน commit แล้ว, ใครถือ lock อยู่? นี่คือปัญหา ฉันทามติ (consensus) และมันคือเรื่องยากที่สุดบนชั้นนี้ Fischer, Lynch และ Paterson พิสูจน์ไว้ในปี 1985 ว่าในระบบอะซิงโครนัส (asynchronous) ที่ข้อความถูกหน่วงได้นานเท่าไรก็ได้ ไม่มีโพรโทคอลเชิงกำหนดแน่นอน (deterministic) ตัวไหนรับประกันได้ว่าโพรเซสที่ถูกต้องทุกตัวจะตัดสินใจได้ ถ้ามีแม้แต่โพรเซสเดียวที่อาจล่ม (JACM 32(2): 374–382) บทพิสูจน์นี้ไม่ได้ว่าด้วยวิศวกรรมที่แย่ มันคือการยกความเป็นไปไม่ได้ที่จะแยกโพรเซสที่ตายแล้วออกจากโพรเซสที่แค่ช้า ขึ้นเป็นทฤษฎีบท
Working systems live inside that result. Paxos, and Raft after it, never sacrifice safety — they will not decide two different values. What they give up is the promise to decide promptly: during a bad enough network they make no progress, and when it recovers, they do. Lamport submitted Paxos in 1990 as an archaeological account of a fictional Greek parliament, and it went unpublished for eight years while reviewers puzzled over the joke (ACM TOCS 16(2), 1998); he later wrote a four-page version, "Paxos Made Simple". Diego Ongaro and John Ousterhout's Raft made understandability an explicit design goal and won a best-paper award for it (USENIX ATC '14). GitHub's failover ran on Raft. Raft did not malfunction; it agreed, correctly and quickly, on the wrong thing.
ระบบที่ใช้งานจริงอยู่ภายในผลลัพธ์นั้น Paxos และ Raft ที่ตามมา ไม่ยอมเสีย ความปลอดภัย เด็ดขาด — มันจะไม่ตัดสินใจไปที่ค่าสองค่าที่ต่างกัน สิ่งที่ยอมเสียคือคำมั่นว่าจะตัดสินใจได้ ทันท่วงที ระหว่างที่เครือข่ายแย่มากพอ มันไม่คืบหน้าเลย พอเครือข่ายกลับมาดี มันก็เดินหน้าต่อ Lamport ส่ง Paxos เข้าตีพิมพ์ในปี 1990 ในรูปรายงานเชิงโบราณคดีว่าด้วยรัฐสภากรีกที่แต่งขึ้น และมันค้างอยู่แปดปีเพราะผู้ตรวจทานงงกับมุกนั้น (ACM TOCS 16(2), 1998) ภายหลังเขาเขียนฉบับสี่หน้าชื่อ "Paxos Made Simple" Raft ของ Diego Ongaro และ John Ousterhout ตั้งเป้าการออกแบบไว้ตรงๆ ว่าต้องเข้าใจง่าย และคว้ารางวัล best paper มาจากเป้านั้น (USENIX ATC '14) failover ของ GitHub วิ่งอยู่บน Raft และ Raft ไม่ได้ทำงานผิด มันตกลงกันได้ ถูกต้องและรวดเร็ว บนเรื่องที่ผิด
Because consensus costs round trips, systems trade it away. Eric Brewer proposed in a July 2000 keynote that consistency, availability and partition tolerance cannot all be had (PODC keynote); Seth Gilbert and Nancy Lynch made the conjecture a theorem in 2002 (SIGACT News 33(2)). The popular reading — pick two of three — is wrong, and Brewer said so twelve years later: partitions are a fact of networks, not a design choice, so the only real decision is what to do during one, and it can be made differently for different operations (IEEE Computer 45(2), 2012). Refuse writes on both sides and stay consistent; accept them and stay available. GitHub's day of repair is the bill for the second option.
ฉันทามติมีต้นทุนเป็น round trip ระบบจำนวนมากจึงยอมแลกมันทิ้ง Eric Brewer เสนอไว้ในคีย์โน้ตเดือนกรกฎาคม 2000 ว่าความสอดคล้อง (consistency) ความพร้อมใช้งาน (availability) และการทนต่อการแยกขาดของเครือข่าย (partition tolerance) ไม่มีทางได้ครบสามอย่างพร้อมกัน (PODC keynote) Seth Gilbert กับ Nancy Lynch ยกข้อสันนิษฐานนี้ขึ้นเป็นทฤษฎีบทในปี 2002 (SIGACT News 33(2)) แต่คำอ่านยอดนิยม — เลือกได้สองในสาม — ผิด และ Brewer พูดเองสิบสองปีให้หลัง การแยกขาดของเครือข่ายเป็นข้อเท็จจริงของเครือข่าย ไม่ใช่ทางเลือกในการออกแบบ สิ่งที่ตัดสินใจได้จริงจึงมีอย่างเดียว คือจะทำอะไร ระหว่างที่ มันเกิดขึ้น และแต่ละปฏิบัติการเลือกคำตอบต่างกันได้ (IEEE Computer 45(2), 2012) ปฏิเสธการเขียนทั้งสองฝั่ง แล้วรักษาความสอดคล้องไว้ หรือรับการเขียนไว้ แล้วรักษาความพร้อมใช้งานไว้ วันซ่อมของ GitHub คือบิลของทางเลือกที่สอง
So consistency became a menu rather than a property. At the strict end is linearizability — every operation appears to take effect at a single instant between its start and its finish, which is to say the system successfully pretends to be one machine (Herlihy & Wing, ACM TOPLAS 12(3), 1990). At the loose end is eventual consistency: replicas may disagree now and will converge if you stop writing (Vogels, CACM 52(1), 2009). Between them lies a long spectrum, and choosing a point on it is the central architectural decision of any system spanning a building, let alone a planet.
ความสอดคล้องจึงกลายเป็นเมนู ไม่ใช่คุณสมบัติตายตัว ปลายด้านเข้มงวดคือ linearizability — ทุกปฏิบัติการดูเหมือนมีผลขึ้นในจุดเดียวระหว่างจุดเริ่มกับจุดจบของมัน พูดอีกอย่างคือระบบแกล้งเป็นเครื่องเดียวได้สำเร็จ (Herlihy & Wing, ACM TOPLAS 12(3), 1990) ปลายด้านหลวมคือ eventual consistency: replica ไม่ตรงกันตอนนี้ได้ และจะลู่เข้าหากันถ้าหยุดเขียน (Vogels, CACM 52(1), 2009) ระหว่างสองปลายคือสเปกตรัมยาวเหยียด การเลือกจุดหนึ่งบนนั้นคือการตัดสินใจเชิงสถาปัตยกรรมที่สำคัญที่สุดของระบบใดก็ตามที่กว้างเกินตึกเดียว ไม่ต้องพูดถึงกว้างเท่าดาวเคราะห์
One more move is available: buy "now" back with hardware. Google's Spanner equips its data centers with GPS receivers and atomic clocks, and its TrueTime interface reports not a timestamp but an interval — the uncertainty ε "varies from about 1 to 7 ms over each poll interval," roughly 4 ms most of the time (OSDI 2012). A transaction that must be globally ordered waits out the uncertainty before committing. It is the most literal illustration of the tower: a floor that could not assume a global clock bought one, in satellites, and sold the result upward as an ordinary database.
ยังมีอีกท่าหนึ่ง คือซื้อ "ตอนนี้" กลับมาด้วยฮาร์ดแวร์ Spanner ของ Google ติดเครื่องรับ GPS และนาฬิกาอะตอมไว้ในดาต้าเซ็นเตอร์ของตัวเอง และอินเทอร์เฟซ TrueTime รายงานออกมาไม่ใช่ timestamp แต่เป็น ช่วง (interval) — ความไม่แน่นอน ε "แกว่งอยู่ราว 1 ถึง 7 มิลลิวินาทีต่อรอบโพล" (varies from about 1 to 7 ms over each poll interval) ราว 4 มิลลิวินาทีในเวลาส่วนใหญ่ (OSDI 2012) transaction ที่ต้องเรียงลำดับกันทั่วโลกจะรอให้ความไม่แน่นอนนั้นหมดไปก่อนค่อย commit นี่คือภาพหอคอยที่ตรงตัวที่สุด: ชั้นที่สมมติเรื่องนาฬิกากลางไม่ได้ ก็ซื้อนาฬิกากลางมาเองด้วยดาวเทียม แล้วขายผลลัพธ์ขึ้นชั้นบนในรูปฐานข้อมูลธรรมดา
The oldest warning here is still the most useful. Around 1994 Peter Deutsch listed the false assumptions newcomers make — the network is reliable, latency is zero, bandwidth is infinite, the network is secure, topology doesn't change, there is one administrator, transport cost is zero — and James Gosling later added the eighth, that the network is homogeneous (Gosling). Each is a place where the abstraction of "one machine" leaks, and every large outage of the last thirty years is a receipt for one of them.
คำเตือนที่เก่าแก่ที่สุดในเรื่องนี้ยังใช้ได้ดีที่สุด ราวปี 1994 Peter Deutsch ไล่รายการความเชื่อผิดๆ ของคนมาใหม่ — เครือข่ายเชื่อถือได้ ความหน่วงเป็นศูนย์ แบนด์วิดท์ไม่จำกัด เครือข่ายปลอดภัย โทโพโลยีไม่เปลี่ยน มีผู้ดูแลระบบคนเดียว ต้นทุนการส่งข้อมูลเป็นศูนย์ — และ James Gosling เติมข้อที่แปดในภายหลังว่าเครือข่ายเป็นเนื้อเดียวกันหมด (Gosling) แต่ละข้อคือจุดที่ abstraction ของ "เครื่องเดียว" รั่ว และเหตุขัดข้องครั้งใหญ่ทุกครั้งในสามสิบปีที่ผ่านมาคือใบเสร็จของข้อใดข้อหนึ่ง
Connections
เชื่อมโยง
Below: chapter 09 supplies the messages and, crucially, their unreliability — this floor exists because that one cannot promise delivery. Chapter 05 owns concurrency within one machine, where locks work and failure is unambiguous; the gap between them is exactly what shared memory was buying. Chapter 08 supplies the guarantees traded away here. Above: chapter 07 pays the operational cost of every decision on this floor; chapter 11 replaces "machines may crash" with "machines may lie," a strictly harder problem; chapter 12 trains its models on clusters that are distributed systems in every respect above.
ชั้นล่าง: บทที่ 09 ส่งข้อความมาให้ และที่สำคัญกว่านั้น ส่งความไม่น่าเชื่อถือของข้อความมาด้วย — ชั้นนี้มีอยู่ได้เพราะชั้นนั้นรับประกันการส่งถึงไม่ได้ บทที่ 05 ถือเรื่องการทำงานพร้อมกันภายในเครื่องเดียว ที่ที่ lock ใช้ได้จริงและความล้มเหลวไม่กำกวม ช่องว่างระหว่างสองบทคือสิ่งที่หน่วยความจำร่วม (shared memory) เคยซื้อไว้ให้พอดี บทที่ 08 ส่งการรับประกัน (guarantee) ที่ถูกแลกทิ้งตรงนี้มาให้ ชั้นบน: บทที่ 07 จ่ายต้นทุนด้านปฏิบัติการของทุกการตัดสินใจบนชั้นนี้ บทที่ 11 เปลี่ยน "เครื่องอาจล่ม" เป็น "เครื่องอาจโกหก" ซึ่งยากกว่าเดิมอย่างเคร่งครัด บทที่ 12 เทรนโมเดลบนคลัสเตอร์ที่เป็นระบบกระจายในทุกแง่มุมข้างต้น
Open questions
คำถามที่ยังเปิดอยู่
Is consensus getting cheaper? Tight clock synchronization and fast data-center networks have narrowed the gap between the theory's worst case and the common one, and how much of the CAP trade is fundamental rather than an artifact of 2000-era networks is unsettled. Second: consistency models are precise but not intuitive, and most production bugs here come from engineers reasoning about a model they could define but not feel. Third, and largest: partial failure is the one thing no abstraction has ever fully hidden — every attempt to make a remote call look local has leaked. A flaw awaiting a fix, or the honest shape of the world showing through?
ฉันทามติกำลังถูกลงไหม? การซิงก์นาฬิกาที่แม่นขึ้นและเครือข่ายดาต้าเซ็นเตอร์ที่เร็วขึ้นทำให้ช่องว่างระหว่างกรณีแย่สุดตามทฤษฎีกับกรณีที่พบจริงแคบลง และยังไม่มีข้อสรุปว่าการแลกแบบ CAP เป็นเรื่องพื้นฐานแค่ไหน หรือเป็นแค่ร่องรอยของเครือข่ายยุค 2000 ข้อที่สอง: แบบจำลองความสอดคล้อง (consistency model) แม่นยำแต่ไม่ตรงสัญชาตญาณ และบั๊กส่วนใหญ่ในงานจริงตรงนี้มาจากวิศวกรที่ให้เหตุผลกับแบบจำลองที่ตัวเองนิยามได้แต่รู้สึกไม่ได้ ข้อที่สาม และใหญ่ที่สุด: ความล้มเหลวบางส่วน (partial failure) คือสิ่งเดียวที่ไม่มี abstraction ไหนเคยซ่อนได้มิด — ทุกความพยายามทำให้การเรียกข้ามเครื่องดูเหมือนเรียกในเครื่องเดียวกัน ล้วนรั่วมาแล้ว นี่คือข้อบกพร่องที่รอการแก้ หรือคือรูปร่างที่แท้จริงของโลกที่โผล่ออกมาให้เห็น?
Go deeper
อ่านต่อ
- Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM 21, no. 7 (1978): 558–565 — eight pages under everything above; award citation and links.
- Fischer, Lynch & Paterson, "Impossibility of Distributed Consensus with One Faulty Process," JACM 32, no. 2 (1985): 374–382 — the boundary of the possible; award citation.
- Maarten van Steen & Andrew S. Tanenbaum, Distributed Systems, 4th ed., 2023 — free PDF at distributed-systems.net. For the practitioner's view, Kleppmann & Riccomini, Designing Data-Intensive Applications, 2nd ed., O'Reilly, 2026.
- Leslie Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM 21, no. 7 (1978): 558–565 — แปดหน้าที่รองรับทุกอย่างข้างต้นอยู่ข้างใต้; award citation and links
- Fischer, Lynch & Paterson, "Impossibility of Distributed Consensus with One Faulty Process," JACM 32, no. 2 (1985): 374–382 — เส้นแบ่งของสิ่งที่เป็นไปได้; award citation
- Maarten van Steen & Andrew S. Tanenbaum, Distributed Systems, 4th ed., 2023 — PDF ฟรีที่ distributed-systems.net ถ้าอยากได้มุมมองแบบคนทำงานจริง อ่าน Kleppmann & Riccomini, Designing Data-Intensive Applications, 2nd ed., O'Reilly, 2026