Coordination & Agreement

1Mutual Exclusion แบบกระจาย

2Election Algorithm: เลือกผู้ประสานงานเมื่อไม่มีใครเป็นผู้นำ

3Multicast Ordering: ทบทวนและขยายจากบทที่ 2

4Consensus Problem

5Byzantine Generals Problem

6ทันสมัย: จาก Paxos สู่ Raft และการใช้งานจริงใน Cloud-Native

7เริ่มจากแยกโจทย์: Coordination ไม่เท่ากับ Consensus

ระบบหลายตัวต้อง “ทำงานร่วมกัน” แต่ไม่ได้หมายความว่าทุกปัญหาต้องใช้ consensus การใช้เครื่องมือหนักเกินโจทย์ทำให้ระบบช้าและดูแลยากโดยไม่จำเป็น ก่อนเลือก algorithm ควรถามว่าต้องการสิ่งใดกันแน่

8Failure Detector: เรารู้ได้อย่างไรว่าใครล่ม

ในระบบ asynchronous การไม่ได้รับคำตอบแยกไม่ออกว่าเครื่องปลายทางล่ม เครือข่ายขาด หรือเพียงช้า Timeout จึงไม่ใช่หลักฐานการเสียชีวิต แต่เป็นการตัดสินใจเชิงปฏิบัติว่า “รอนานพอแล้ว” นี่คือเหตุผลที่ระบบใช้คำว่า suspect มากกว่า know

• Completeness — ในที่สุด failure detector สงสัย process ที่ล่มจริงหรือไม่
• Accuracy — มันหลีกเลี่ยงการกล่าวหา process ที่ยังทำงานอยู่ได้มากเพียงใด
• Heartbeat — node ส่งสัญญาณเป็นระยะ ถ้าขาดหลายรอบจึงเริ่มสงสัย
• Adaptive timeout — ปรับเวลารอตาม latency ที่สังเกตได้ แทนการใช้ตัวเลขตายตัวในทุกสถานการณ์

Timeout สั้นทำให้ failover เร็วแต่ false positive มาก Timeout ยาวลดการกล่าวหาผิดแต่ระบบตอบสนองต่อ failure ช้า ไม่มีค่าหนึ่งที่เหมาะกับทั้งระบบในทุกช่วงเวลา

9Distributed Lock, Lease และ Fencing Token

Lock บนเครื่องเดียวพึ่งหน่วยความจำร่วม แต่ distributed lock พึ่งข้อความและเวลา สมมติ worker A ได้ lock แล้วหยุดชั่วคราวเพราะ GC pause จน lease หมด Worker B ได้ lease ใหม่และเริ่มเขียน ระหว่างนั้น A ฟื้นขึ้นมาและยังคิดว่าตนมีสิทธิ์ ถ้าปลายทางรับคำสั่งจาก A เราได้ผู้ถือ lock สองคนในทางปฏิบัติ

10Leader Election กับ Consensus เกี่ยวกันอย่างไร

Bully และ Ring election สอนแก่นของการเลือกผู้ประสานงาน แต่การมีผู้ชนะไม่ได้แปลว่าทุกคนเห็นผู้ชนะคนเดียวกันตลอดเวลา เมื่อเกิด partition แต่ละฝั่งอาจเลือก leader ของตนเองได้ ระบบที่ต้องรักษา safety จึงผูก election เข้ากับ term/epoch และ quorum

ใน Raft ผู้สมัครต้องได้เสียงข้างมากจึงเป็น leader และแต่ละ node ลงคะแนนได้หนึ่งครั้งต่อ term เพราะ quorum สองชุดที่เป็นเสียงข้างมากต้องทับกันอย่างน้อยหนึ่ง node จึงช่วยป้องกัน leader สองตัวใน term เดียว อย่างไรก็ตาม leader เก่าจาก term ก่อนอาจยังไม่รู้ว่าตนหมดอำนาจ ผู้รับคำสั่งจึงต้องตรวจ term หรือ fencing token ด้วย

11Consensus กำลังรับประกันอะไร

Consensus ไม่ได้แปลว่า node ทุกตัวตอบพร้อมกัน หรือไม่มีใครล่ม แต่โดยทั่วไปต้องการคุณสมบัติหลักต่อไปนี้

• Agreement — process ที่ตัดสินใจแล้วต้องไม่ตัดสินคนละค่า
• Validity — ค่าที่ตัดสินต้องมาจากค่าที่ถูกเสนอภายใต้เงื่อนไขของ algorithm
• Integrity — process หนึ่งไม่ตัดสินใจซ้ำหลายค่ารอบเดียวกัน
• Termination — process ที่ถูกต้องควรตัดสินใจได้ในที่สุดภายใต้สมมติฐานเรื่อง timing และ failure ที่กำหนด

Safety คือ “สิ่งเลวร้ายต้องไม่เกิด” เช่น commit คนละ log ส่วน liveness คือ “สิ่งดีต้องเกิดในที่สุด” เช่นระบบกลับมา commit ต่อได้ Algorithm มักรักษา safety แม้เครือข่ายแย่มาก แต่ liveness อาจหยุดจนกว่าจะมีช่วงที่เครือข่ายนิ่งพอ

12FLP: เป็นไปไม่ได้ แต่ระบบจริงยังทำงานได้

FLP แสดงว่า consensus แบบ deterministic ในระบบ asynchronous ที่ process อาจล่มแม้เพียงหนึ่งตัว ไม่สามารถรับประกัน termination ได้ทุก execution ประโยคนี้ไม่ได้บอกว่า consensus ทำไม่ได้เลย และไม่ได้บอกว่า Raft ผิด แต่มันบอกว่าไม่มี algorithm ใดสัญญาได้ว่าจะเดินหน้าต่อเสมอภายใต้ความล่าช้าที่ไม่มีขอบเขต

ระบบจริงหลบมุมที่เป็นไปไม่ได้ด้วยสมมติฐานเชิงปฏิบัติ เช่น partial synchrony คือเครือข่ายอาจแย่มากอยู่ช่วงหนึ่ง แต่ในที่สุดมีช่วงที่ข้อความไปถึงภายในเวลาพอประมาณ รวมถึงใช้ randomized timeout เพื่อลดโอกาสผู้สมัครชนกันซ้ำ ๆ Safety ยังต้องคงอยู่แม้ timeout ผิด ส่วน liveness กลับมาเมื่อสภาพแวดล้อมดีพอ

13Raft แบบเดินตามหนึ่งคำสั่ง

1. Client ส่งคำสั่งไปยัง leader
2. Leader เพิ่ม entry ลง log ของตนใน term ปัจจุบัน
3. Leader ส่ง AppendEntries ไป follower พร้อม index และ term ของ entry ก่อนหน้า เพื่อยืนยันว่า log ต่อกันได้
4. เมื่อ entry ถูกเก็บบน quorum และผ่านกติกา commit ของ Raft leader ขยับ commit index
5. แต่ละ node นำ entry ที่ commit แล้วไปใช้กับ state machine ตามลำดับ
6. Leader ตอบ client หลังผลลัพธ์มีสถานะตาม durability guarantee ที่ระบบกำหนด

Leader เปลี่ยนแล้วข้อมูลไม่หายได้อย่างไร

ผู้สมัครที่ log ล้าหลังไม่ควรได้รับเสียงจาก node ซึ่งมี log ใหม่กว่า กฎ election restriction จึงเชื่อมการเลือก leader กับความครบถ้วนของข้อมูล ไม่ใช่เลือกเพียง ID สูงสุด นี่คือความต่างสำคัญจาก election algorithm แบบเบื้องต้น

14Raft Membership Change และ Snapshot

Cluster ที่ใช้งานจริงต้องเพิ่มหรือลด node ถ้าเปลี่ยนรายชื่อสมาชิกแบบทันที ฝั่งเก่าและฝั่งใหม่อาจมี quorum ที่ไม่ทับกันและสร้าง leader สองตัว วิธี joint consensus ให้ระบบผ่านช่วงที่ configuration เก่าและใหม่มีผลร่วมกันก่อน จึงค่อยเปลี่ยนเต็มรูปแบบ

Log ยาวไม่สิ้นสุดไม่ได้ จึงต้อง snapshot state machine ณ index หนึ่ง แล้วตัด log ส่วนก่อนหน้าออก Follower ที่ล้าหลังมากอาจรับ snapshot แทนการ replay entry หลายล้านรายการ Snapshot จึงเป็นทั้งเรื่องพื้นที่จัดเก็บและเวลาฟื้นตัว ไม่ใช่แค่การสำรองข้อมูล

15Paxos กับ Raft: อย่าเทียบแค่ความยากในการอ่าน

ทั้งสองพึ่ง quorum intersection และรับมือ crash fault ไม่ใช่ Byzantine fault การบอกว่า Raft “ดีกว่า Paxos” โดยไม่ระบุมิติ จึงไม่แม่นกว่าเดิมนัก ควรถามเรื่อง implementation, membership, performance, proof และ operational tooling ของระบบนั้น

16Byzantine Fault: เมื่อ node ไม่ได้แค่เงียบ

Crash fault คือ node หยุดตอบ ส่วน Byzantine fault รวมถึงการส่งคำตอบต่างกันให้คนละฝ่าย ปลอมข้อมูล หรือทำงานผิดโดยคาดเดาไม่ได้ ถ้าต้องทน Byzantine node จำนวน f ตัว ระบบแบบดั้งเดิมมักต้องมีอย่างน้อย 3f+1 replicas เพื่อให้ quorum ที่ถูกต้องยังทับกันพอแยกความจริงจากข้อมูลเท็จ

แต่ replication มากขึ้นไม่ใช่คำตอบทั้งหมด ต้องมี authentication, message digest, view change และกติกาป้องกัน replay ด้วย ระบบองค์กรที่ควบคุมเครื่องและเครือข่ายได้มักเลือก crash-fault consensus เพราะต้นทุนต่ำกว่า ส่วน permissionless blockchain ต้องรับมือผู้เข้าร่วมที่ไม่รู้จักกัน จึงเพิ่ม economic mechanism และ Sybil resistance เข้ามาอีกชั้น

17Exactly-Once และ Idempotency: Consensus ช่วยได้แค่ไหน

แม้ cluster ตกลง log เดียวกันได้ Client ก็อาจ timeout หลังคำสั่ง commit แต่ก่อนเห็น response แล้ว retry ถ้าคำสั่ง “หักเงิน 100 บาท” ถูกประมวลผลซ้ำ ผลยังผิดได้ ระบบจึงต้องมี request ID และเก็บผลลัพธ์ของคำขอที่เคยทำ หรือออกแบบ operation ให้ idempotent

Consensus ทำให้สมาชิกตกลงว่า request ใดอยู่ใน log ตำแหน่งใด แต่ขอบเขต end-to-end ยังรวม client, load balancer และระบบภายนอก เช่น payment gateway คำว่า exactly-once จึงควรถามต่อทันทีว่า “exactly once ภายในขอบเขตไหน”

18กรณีศึกษา: Metadata ของระบบจัดเก็บข้อมูล

สมมติระบบต้องเก็บว่าไฟล์แต่ละชิ้นอยู่ data node ใด ถ้ามี metadata leader สองตัวอาจสั่งให้ block เดียวกันมีเจ้าของคนละชุด หรือ allocate ID ซ้ำกัน การใช้ replicated log จึงเหมาะ เพราะ metadata มีขนาดไม่ใหญ่เท่าข้อมูลจริงแต่ต้องการลำดับที่ชัด

1. ใช้ Raft group จำนวนคี่ เช่น 3 หรือ 5 node เพื่อให้ quorum ชัด
2. Data node ส่ง heartbeat และรายงาน block แต่ failure detector ระบุเพียง suspect
3. Leader ทุก term ใช้ epoch/fencing token เมื่อสั่งงาน data node
4. คำสั่งเปลี่ยน metadata ต้อง commit ก่อนตอบ client
5. ข้อมูลไฟล์ขนาดใหญ่ replicate แยกต่างหาก ไม่ส่งทุก byte ผ่าน consensus log

19การทดสอบและดูแลระบบ Consensus

• ฉีด failure: kill leader, delay packet, แยก partition และทำ disk ช้า แล้วตรวจทั้ง safety กับ recovery time
• ติดตาม term change, election rate, commit latency, quorum availability และ follower lag
• แจ้งเตือนเมื่อ clock หรือ disk latency ผิดปกติ แม้ algorithm ไม่พึ่ง wall clock เพื่อ safety แต่ timing กระทบ liveness อย่างมาก
• สำรอง snapshot และทดลอง restore ไป cluster ใหม่ เพราะ quorum ไม่ใช่ backup
• เปลี่ยนสมาชิกผ่านขั้นตอนที่ protocol รองรับ ห้ามแก้ configuration หลายฝั่งพร้อมกันด้วยมือ

20แบบฝึกคิดเชิงออกแบบ

คำตอบที่ดีอาจไม่ใช่ algorithm ที่ซับซ้อนที่สุด หากผลข้างเคียงทำซ้ำได้อย่างปลอดภัย การยอมให้ at-least-once แล้วใช้ idempotency อาจง่ายและทนทานกว่าการสร้าง distributed lock สำหรับทุกงาน

21การอ่านจากระบบ Consensus

การเขียนผ่าน leader และ quorum ยังไม่ตอบโดยอัตโนมัติว่าการอ่านจาก follower เป็น linearizable Follower อาจล้าหลังหรือไม่รู้ว่า leader ใหม่ commit อะไรแล้ว วิธีที่ตรงที่สุดคืออ่านผ่าน leader และให้ leader ยืนยันว่าตนยังมี quorum แต่เพิ่ม round trip และภาระที่ leader

• Read index / quorum confirmation — leader ตรวจว่ายังเป็น leader ใน term ปัจจุบันก่อนตอบ โดยไม่ต้องเพิ่ม log entry ทุกการอ่าน
• Lease read — leader ตอบจาก local state ภายในช่วง lease อาศัยสมมติฐานเรื่องเวลาอย่างระมัดระวัง
• Follower read — latency ต่ำและกระจายโหลดได้ แต่ต้องยอม stale หรือใช้ bounded-staleness guarantee

ดังนั้นคำว่า “ฐานข้อมูลใช้ Raft” ไม่ได้แปลว่าทุก query เป็น linearizable ต้องดู read path และ consistency option ที่ client เลือกด้วย

22Log, State Machine และ Determinism

Replicated log ทำให้ทุก replica เห็น command ตามลำดับเดียวกัน แต่จะได้ state เดียวกันต่อเมื่อ state machine ประมวลผลแบบ deterministic ถ้า command เรียกเวลาปัจจุบัน สุ่มเลข หรืออ่านไฟล์ท้องถิ่น แต่ละ replica อาจได้ผลต่างกันแม้ log ตรงกัน

วิธีแก้คือให้ leader เลือกค่าที่ไม่ deterministic แล้วใส่ผลนั้นลง log เช่น บันทึก timestamp ที่เลือกแล้วแทนคำสั่ง “ใช้เวลาตอนนี้” หรือใช้ pseudorandom seed เดียวกัน ทุก input ที่มีผลต่อ state ต้องเป็นส่วนหนึ่งของ replicated command มิฉะนั้น consensus ตกลงกันได้เพียงคำสั่ง แต่ไม่ได้ตกลงผลลัพธ์

23Client Session เมื่อ Leader เปลี่ยน

Client อาจค้าง connection กับ leader เก่า หลัง election คำขอใหม่ต้องถูก redirect ไป leader ใหม่ แต่ client ไม่ควร retry แบบทันทีไม่จำกัด เพราะช่วง election ทุกคนอาจทำเช่นเดียวกันจนเกิด retry storm

• ใช้ exponential backoff และ jitter เพื่อกระจายเวลาลองใหม่
• แนบ client ID และ monotonically increasing request number เพื่อ deduplicate
• เก็บผลของ request ล่าสุดใน replicated state หากต้องการ exactly-once appearance ต่อ session
• กำหนด deadline ทั้ง operation ไม่ใช่เริ่ม timeout ใหม่เต็มจำนวนทุก retry

24Quorum Size และ Failure Budget

Cluster 3 node ทน crash ได้ 1 ตัวเพราะ quorum คือ 2 ส่วน 5 node ทนได้ 2 ตัวเพราะ quorum คือ 3 การเพิ่มจาก 3 เป็น 4 ไม่เพิ่มจำนวน failure ที่ทนได้ เพราะ quorum กลายเป็น 3 และยังทนได้เพียง 1 ตัว จึงนิยมสมาชิกลงคะแนนจำนวนคี่

แต่ node มากขึ้นเพิ่ม message, disk และ tail latency จึงไม่ควรเพิ่มสมาชิกเพื่อหวัง throughput Data replica หรือ learner ที่ไม่ลงคะแนนอาจช่วยอ่านหรือสำรองโดยไม่ขยาย quorum path ทั้งหมด

25การกระจาย Node ตาม Fault Domain

มี 3 node อยู่ rack เดียวกันไม่ได้ทนต่อไฟดับ rack แม้ทน process crash ได้ การจัด placement ต้องมอง power supply, switch, availability zone และ region Node ที่ดูเป็นอิสระในแผนภาพอาจแชร์ failure domain ที่ซ่อนอยู่

ในสาม availability zones การวางหนึ่ง voting member ต่อ zone เป็นรูปแบบทั่วไป แต่ถ้า latency ระหว่าง zone สูง commit latency ก็สูงตาม quorum path การวางสมาชิกส่วนใหญ่ไว้ zone เดียวทำให้เร็วขึ้นแต่เมื่อ zone นั้นล่ม cluster หยุด จึงต้องเลือกให้ตรงกับ failure ที่ธุรกิจต้องการทน ไม่ใช่กระจายเพราะคำว่า distributed ฟังดูดี

26Split Vote, Election Storm และ Pre-Vote

เมื่อ follower หลายตัว timeout พร้อมกัน อาจต่างคนต่างเป็น candidate และแบ่งคะแนนจนไม่มีใครได้ quorum Randomized election timeout ลดโอกาสนี้ แต่ node ที่เครือข่ายขาดเป็นพัก ๆ อาจเพิ่ม term ซ้ำเมื่อกลับมา ทำให้ leader ที่ดีต้องลงจากตำแหน่ง

Pre-vote ให้ node สำรวจก่อนว่ามีโอกาสได้เสียงข้างมากหรือไม่ โดยยังไม่เพิ่ม term หากยังติดต่อ quorum ไม่ได้ มันจึงไม่ก่อกวน cluster เมื่อ node โดดเดี่ยวกลับมา กลไกเสริมแบบนี้ชี้ว่า paper algorithm เป็นแก่น แต่ production protocol ต้องรับรายละเอียดจากเครือข่ายจริงอีกมาก

27Joint Consensus ผ่านตัวอย่าง

สมมติ configuration เดิมคือ A, B, C และต้องเปลี่ยนเป็น B, C, D ถ้าฝั่งหนึ่งใช้ชุดเดิมทันทีและอีกฝั่งใช้ชุดใหม่ อาจเกิด quorum A+B กับ C+D ซึ่งไม่ทับกันและ commit คนละค่า Joint configuration บังคับให้การตัดสินใจช่วงเปลี่ยนผ่านได้รับเสียงตามกติกาของทั้งชุดเก่าและชุดใหม่ ทำให้ quorum ที่ถูกต้องยังเชื่อมประวัติเดียวกัน

การเพิ่ม node ควรรอให้ node ใหม่ตาม log ทันก่อนให้สิทธิ์ลงคะแนน ไม่เช่นนั้น quorum อาจพึ่งสมาชิกที่ยังไม่มีข้อมูลพอ ส่วนการนำ node ออกต้องระวัง node เก่ายังทำงานและรับ traffic อยู่ Fencing และ configuration version จึงสำคัญพอ ๆ กับรายชื่อสมาชิก

28Consensus กับ Transaction Commit ต่างกันอย่างไร

Two-phase commit ถามผู้เข้าร่วมของ transaction ว่าเตรียม commit ได้หรือไม่ แล้ว coordinator ประกาศผล หาก coordinator หายหลังผู้เข้าร่วม prepared บางตัวอาจ block เพราะไม่รู้ผล ส่วน consensus ให้กลุ่ม replica ตกลงค่าหนึ่งแม้บางสมาชิก crash โดยอาศัย quorum

ระบบฐานข้อมูลสมัยใหม่อาจใช้ consensus replicate สถานะของ transaction coordinator เพื่อลดจุดล้มเหลว แต่ไม่ได้ทำให้ atomic commit ข้าม shard หายไป ทั้งสองปัญหาซ้อนกันได้: consensus ดูแลว่าแต่ละ shard และ coordinator มีสถานะทนทาน ส่วน transaction protocol ดูแลว่าหลาย shard commit หรือ abort สอดคล้องกัน

29Coordination Avoidance: บางครั้งคำตอบคือไม่ต้องตกลง

Coordination ทำให้ invariant แข็งแรงแต่มี latency และลด availability ถ้าออกแบบข้อมูลใหม่ให้ operation commute หรือแยก ownership ได้ เราอาจรักษาความถูกต้องโดยไม่ให้ทุก request ผ่าน consensus

• แบ่ง quota 1,000 หน่วยเป็น escrow ให้แต่ละ region ใช้ส่วนของตนโดยไม่ชนกัน
• ใช้ unique ID ที่มี node/region prefix แทน lock เลขลำดับกลาง
• ใช้ CRDT counter เมื่อยอมรวมผลภายหลังได้
• กำหนด single writer ต่อ entity แทน global leader ทั้งระบบ

หลักคิดคือแยก invariant ที่จำเป็นจริงออกจากความเคยชินในการสั่งทุกอย่างเป็นลำดับเดียว Total order ให้เหตุผลง่าย แต่ระบบจำนวนมากไม่ต้องการ total order ระหว่างเหตุการณ์ที่เป็นอิสระจากกัน

30Failure Timeline สำหรับใช้สอน

1. ถามก่อนว่า X commit แล้วหรือยัง โดยดู quorum และกฎ commit ไม่ใช่ดูว่า client ได้ response หรือไม่
2. ถ้า X อยู่ใน committed log ของ B ผู้นำใหม่ที่ถูกต้องต้องไม่ทำให้ X หาย
3. Retry อาจทำให้ X ปรากฏสองครั้ง ถ้าไม่มี request ID แม้ consensus ทำงานถูก
4. A ต้องไม่เขียนผลข้างเคียงภายนอกต่อหลังหมด term จึงต้องมี fencing ที่ resource ปลายทาง

Timeline แบบนี้มีประโยชน์กว่าท่องชื่อ state เพราะทำให้นักศึกษาแยกมุมมองของ client, leader, follower และ resource ภายนอก ซึ่งแต่ละฝ่ายรู้ข้อมูลไม่เท่ากัน

31Checklist เลือกใช้ Coordination Service

• ข้อมูลใดจำเป็นต้อง linearizable และข้อมูลใดยอม stale ได้
• ต้องการ lock, election, configuration store หรือ replicated database กันแน่
• การหยุดรับงานเมื่อเสีย quorum กระทบผู้ใช้อย่างไร มี degraded mode หรือไม่
• ผลข้างเคียงปลายทางรองรับ fencing และ idempotency หรือยัง
• ขนาดข้อมูลและ write rate เหมาะกับ consensus log หรือควรเก็บเฉพาะ metadata
• ทีมซ้อม member replacement, backup restore และ region failure แล้วหรือไม่

32สรุปและขั้นตอนถัดไป

Coordination คือการจัดความสัมพันธ์ระหว่างงานหลายตัว ส่วน consensus เป็นกรณีเฉพาะที่ต้องตกลงค่าเดียวกันภายใต้ failure เราเริ่มจาก timeout ที่ให้ได้เพียงความสงสัย ต่อด้วย election, lease, fencing, quorum และ replicated log จึงเห็นว่า “การมี leader” ไม่ใช่จุดจบ แต่ต้องพิสูจน์ด้วย term และป้องกัน leader เก่ากลับมาเขียน

เมื่อออกแบบระบบจริง ควรเริ่มจาก invariant และ failure model แล้วเลือกกลไกที่เบาที่สุดซึ่งยังรักษาสัญญาได้ เพราะ coordination ที่ไม่จำเป็นก็คือการนำ latency และจุดหยุดรอเข้ามาในระบบด้วยตัวเราเองครับ

บทถัดไปจะเปลี่ยนมุมจาก cluster ที่สมาชิกรู้จักกัน ไปสู่ P2P, mobile และ ubiquitous systems ซึ่งสมาชิกเข้าออกบ่อย ตำแหน่งเปลี่ยน และการเชื่อมต่อไม่แน่นอน เครื่องมือเดิมยังอยู่ แต่สมมติฐานเปลี่ยนจนต้องออกแบบ overlay, discovery และ conflict handling ใหม่ครับ