บทที่ 2 — Consensus + Replication

← บทที่ 1 | สารบัญ | บทที่ 3 →

หลังจบบท คุณจะ:

เข้าใจ consensus algorithm (Raft, Paxos)
เห็นภาพ leader election, log replication
เข้าใจ etcd, ZooKeeper, Spanner internals
รู้จัก Byzantine consensus

1. Consensus — ทำไมต้องมี

หัวใจของระบบกระจายหลายอย่างคือ "หลาย node ต้องตกลงกันให้ได้ค่าเดียว" — ใครเป็น leader, config ปัจจุบันคืออะไร, transaction นี้ commit หรือ abort แต่บน network ที่เชื่อถือไม่ได้และ node ที่ล่มได้ การตกลงกันให้สำเร็จเป็นโจทย์ยาก จึงต้องมี consensus algorithm มาจัดการ:

text

ปัญหา:
- N nodes ต้องตกลงกันเรื่องใดเรื่องหนึ่ง
- Leader election (ใครเป็น master?)
- การเปลี่ยน config (เพิ่ม/ลบ node)
- Distributed transaction จะ commit/abort
- State machine replication (รัน state machine ให้ตรงกัน)

ข้อจำกัด:
- network เชื่อถือไม่ได้
- node อาจ crash
- partition เกิดได้
- ต้องตกลงกันให้ได้ "ทั้งที่" มี failure

→ ต้องใช้ consensus algorithm

2. FLP Impossibility — ผลลัพธ์ทฤษฎีที่โด่งดัง

ภาษาคนก่อน: ทฤษฎีบอกว่า ในเครือข่ายที่ไม่รับประกันเวลาตอบ (= โลกอินเทอร์เน็ตจริง) ถ้ามีเครื่องเสียแม้แค่เครื่องเดียว ก็ไม่มีทางที่จะให้ทุกคนตกลงกันได้แน่นอน 100% — ต้องมี trade-off เสมอ

text

FLP (Fischer-Lynch-Paterson — สามนักวิจัยที่พิสูจน์ปี 1985)
Paper: "Impossibility of Distributed Consensus with One Faulty Process" (J.ACM 1985)

   "ในระบบ distributed แบบ asynchronous (= ไม่มีการรับประกันเวลาตอบ)
    ที่มี process (= โปรเซสหรือเครื่อง) เสียแม้แค่ 1 ตัว
    ไม่มี consensus algorithm แบบ deterministic (= ผลแน่นอนทุกครั้ง) ที่ทำงานได้"

ทำไม?
- แยก "ช้า" กับ "ตาย" ไม่ออก
- algorithm จะค้างรอไม่จบ

consensus ในของจริง:
- ใช้ timeout (สมมติว่า network sync เป็นบางช่วง
  = partial synchrony — sync บางช่วงเท่านั้น ไม่ sync ตลอด)
- รับประกันแบบ probabilistic (เชิงความน่าจะเป็น — ไม่ 100% แต่ใกล้ 100%)
- หรือใส่ randomness (ความสุ่ม) เข้าไปช่วยตัดสินใจ

→ สรุป (takeaway): Consensus เป็นปัญหายากโดยธรรมชาติใน async network — ในทางปฏิบัติจึงต้องอาศัย timeout หรือ randomness ช่วย (ดู FLP ใน glossary บท 11)

3. Paxos (อ่าน "แพก-ซอส") — algorithm ที่ Lamport (แลม-พอร์ต) เองยังบอกว่ายาก

Paxos = consensus algorithm ตัวแรกที่พิสูจน์ทางคณิตศาสตร์ได้ — แต่ขึ้นชื่อเรื่องเข้าใจยากมาก

📜 เกร็ดประวัติ (footnote): Lamport เขียน paper Paxos ปี 1989 แต่ submit ใช้เวลาถึง ~10 ปีกว่าจะมีคน "ยอมรับ/เข้าใจ" จน publish ปี 1998 (ไม่ใช่ algorithm ผิด — แค่อ่านยาก) ต่อมาเขาเขียน "Paxos Made Simple" ปี 2001 ซึ่งก็ยังยากอยู่ดี

3 บทบาท (Roles)

ในการ run Paxos — node แต่ละตัวมีบทบาทหนึ่งใน 3 อย่าง (อาจ overlap ได้):

text

Proposer (โพร-โพ-เซอร์ = ผู้เสนอ) — "เสนอค่า"
   "ผมจะให้ค่า x = 5 เห็นด้วยไหม?"

Acceptor (แอ็ค-เซป-เทอร์ = ผู้โหวต) — "โหวต"
   "ผม accept หรือ reject ข้อเสนอ"

Learner (เลิร์น-เนอร์ = ผู้เรียนรู้) — "เรียนรู้ค่าที่ agree"
   "พวกเรา agree ที่ค่าอะไร?"

2 Phase (สำหรับ Single Value)

💡 ภาพรวมก่อนดู pseudocode (trace-first): นาย P1 (Proposer) อยากให้คณะกรรมการ A, B, C (Acceptors) อนุมัติค่า x = 5
Phase 1 (ขอจอง): P1 ส่งใบขอจอง "ฉันขอเลขคิว N=1" ไปหาทุกคน — ทุกคนตอบ "OK สัญญาว่าจะไม่รับใบอื่นที่เลขเก่ากว่า 1"
Phase 2 (เสนอจริง): P1 ส่งใบเสนอ "เลข 1, ค่า=5" — ทุกคน accept เพราะยังไม่มีใครจองเลขใหญ่กว่า
เสร็จ: Learner เห็นว่า majority (2 จาก 3) accept → ค่า 5 ถูก "chosen" ตลอดกาล ตอนนี้ลองอ่าน pseudocode ด้านล่าง แล้วเทียบกับ trace ตัวอย่างถัดไป

Phase 1: Prepare (จองเลขคิว / round number)

text

Proposer:
   เลือก proposal number N (เพิ่มจากเก่า)
   ส่ง PREPARE(N) ไปทุก Acceptor

Acceptor:
   ถ้า N > N_เก่าที่เคยตอบ:
      บันทึก N
      ส่งกลับ PROMISE(N) + ค่าที่เคย accept (ถ้ามี)
      "สัญญาว่าจะไม่ accept ข้อเสนอที่ N เก่ากว่านี้"
   ถ้า N ≤ N_เก่า:
      Reject (เพราะมีคนเสนอด้วยเลขใหญ่กว่าแล้ว)

Phase 2: Accept (เสนอค่าจริง)

text

Proposer:
   ถ้าได้ PROMISE จาก majority → ดี
   ส่ง ACCEPT(N, value) ไปทุก Acceptor
   (ถ้า Acceptor เคย accept ค่าอื่นมาก่อน → ใช้ค่านั้นแทน)

Acceptor:
   ถ้า N ≥ N_ล่าสุดที่ promise:
      Accept ค่า
      ส่ง ACCEPTED ไปทุก Learner

Learner:
   ถ้าได้ ACCEPTED จาก majority → ค่านั้น "chosen"

Trace ตัวอย่าง — 3 Acceptors

text

Initial: Acceptors A, B, C (ยังไม่มีค่า)

Proposer P1 อยากเสนอ x=5:

Phase 1:
P1 → PREPARE(N=1) → A, B, C
A, B, C: ตอบ PROMISE(1), ไม่มีค่าเก่า

Phase 2:
P1 ได้ PROMISE จาก 3/3 (majority)
P1 → ACCEPT(N=1, value=5) → A, B, C
A, B, C: Accept → ส่ง ACCEPTED → Learner
Learner: chosen = 5 ✅

Trace สอง proposers ชนกัน

text

Initial: A, B, C ว่าง

P1 → PREPARE(N=1) → A (accept, promise 1)
P2 → PREPARE(N=2) → A, B, C (accept all, promise 2)

A: ขณะนี้ promised 2 (มากกว่า 1)
P1 → ACCEPT(N=1, value=5) → A
A: REJECT (เพราะ promised 2)

P1: ต้องเริ่ม Phase 1 ใหม่ด้วย N สูงกว่า
   → PREPARE(N=3) → ...

→ P1 vs P2 อาจ "ไล่กัน" ไม่จบ
   = livelock (ไลฟ์-ล็อก = ติดวนทำงานไปเรื่อย ๆ
                ต่างจาก deadlock ที่หยุดสนิทไม่ทำอะไร)
   วิธีแก้: เลือก leader คนเดียว (Multi-Paxos)

→ ใน production จึงใช้ Multi-Paxos (1 leader ตัดสิน) — เหมือน Raft

ทำไม Paxos ยากกว่า Raft?

	Paxos	Raft
Role separation	3 roles ที่ overlap ได้	3 states ที่ชัด
Algorithm	กระจัดกระจาย, abstract	เป็นขั้นตอน
Multi-value	ต้อง extend เอง	Built-in
Implementation	หลาย variant, ไม่มาตรฐาน	มาตรฐานเดียว
Visualization	ยากเล่า	https://raft.github.io ดู interactive

บทเรียน: Raft เกิดมาเพื่อทดแทน Paxos ในส่วน "เข้าใจง่าย + implement ง่าย" — แต่ Paxos ยังใช้ใน Google (Chubby, Spanner)

🔬 Paxos variants ที่น่าสนใจ (อ่านเพิ่ม):
Multi-Paxos — เลือก leader คนเดียวให้ propose ค่าทีละหลาย ๆ ค่า (ใช้จริงใน Chubby)
EPaxos (Egalitarian Paxos, 2013) — ไม่มี leader คงที่, commit แบบ commutative ขนานได้ดี เหมาะกับ WAN
Flexible Paxos (2016) — แยก quorum ของ Phase 1 กับ Phase 2 ได้ → tune ตาม workload (read-heavy/write-heavy)
ในทางปฏิบัติ Paxos จะแยกเรื่องไม่ค่อยชัด ต้อง implement เอง: leader election ≠ log replication ≠ membership change ≠ snapshot Raft แยกชัดเจน 4 เรื่องนี้ในตัว algorithm เอง

4. Raft (2014, Ongaro + Ousterhout) — ⭐ (อ่าน "ราฟต์")

📌 ชื่อนักวิจัย: Diego Ongaro (ออน-กา-โร) + John Ousterhout (อูส-เตอร์-เฮาท์) — paper "In Search of an Understandable Consensus Algorithm" (USENIX ATC 2014)
🌟 Raft = consensus protocol ของยุคนี้ — กว่า 90% ของระบบ open source สมัยใหม่ใช้ Raft (etcd, Consul, TiKV, CockroachDB, RethinkDB, Nomad)

Raft ออกแบบมาเพื่อ "เข้าใจง่าย" เป็น goal ขั้นต้นเลย — ให้ guarantee เทียบเท่า Paxos แต่ implement ได้ตรงไปตรงมากว่ามาก จึงเป็น consensus algorithm ที่นิยมที่สุดในระบบ open source ทุกวันนี้

text

ออกแบบให้ "เข้าใจง่าย (UNDERSTANDABLE)" เป็นเป้าหมายหลัก
ให้การรับประกันเท่า Paxos แต่ง่ายกว่า

ใช้ใน:
- etcd (K8s control plane)
- Consul
- TiKV / CockroachDB
- RocketChat (chat)

Raft Roles — 3 บทบาท

text

แต่ละ node อยู่ในสถานะใดสถานะหนึ่งจาก 3 อย่าง:

Follower (ผู้ตาม):
- รับคำสั่งจาก leader
- เป็นสถานะเริ่มต้น
- รีเซ็ต election timer ทุกครั้งที่ได้ heartbeat จาก leader

Candidate (ผู้สมัคร):
- election timer หมด (ไม่ได้ heartbeat จาก leader)
- ขอ vote จากคนอื่น

Leader (ผู้นำ):
- รับ request จาก client
- replicate ไปยัง follower
- ส่ง heartbeat เพื่อรักษาตำแหน่งผู้นำ

Raft — Leader Election (เลือกผู้นำ)

text

1. ทุกตัวเริ่มเป็น Follower
2. election timer ของ Follower หมด (สุ่ม 150-300ms)
3. กลายเป็น Candidate, เพิ่ม term, vote ให้ตัวเอง
4. ส่ง RequestVote ไปยัง peer
5. ได้ vote ข้างมาก (majority) → กลายเป็น Leader
   ถ้าไม่ได้ majority → รอ + ลองใหม่
6. Leader ส่ง heartbeat เพื่อรักษาตำแหน่ง

text

Term (วาระ — ตัวเลขนับวาระของการเลือกตั้ง คล้าย "สมัยของประธานาธิบดี"):
- เป็น logical clock (ตัวนับ ไม่ใช่เวลานาฬิกาจริง — รายละเอียดในบท 4)
  หมายเหตุ: term ของ Raft ≠ Lamport clock เต็มรูปแบบ
  เป็นแค่ "election counter" — เพิ่มขึ้นทางเดียว
- การเลือกตั้งแต่ละครั้ง = term ใหม่ (1, 2, 3, ...)
- ติด term ไปกับทุก message
- term สูงกว่าชนะ (term เก่ากว่า: ต้อง step down ลงเป็น follower)

Raft — Log Replication (กระจาย log)

text

Client ส่งคำสั่งมาที่ leader:
1. Leader ต่อ log ของตัวเอง (ยัง uncommitted = ยังไม่ยืนยัน)
2. replicate ไปยัง follower
   (ผ่าน AppendEntries RPC — RPC = Remote Procedure Call
    = เรียกฟังก์ชันข้ามเครื่องผ่าน network)
3. follower ต่อ log ของตัวเอง (state machine = เครื่องสถานะ)
4. เมื่อ majority (รวม leader) มี entry นี้แล้ว:
   → Leader mark ว่า COMMITTED (ยืนยันแล้ว)
   → apply เข้า state machine
   → บอก follower (ใน heartbeat ถัดไป) ให้ commit ตาม
5. ตอบ client: สำเร็จ

text

Log structure:
[Term, Index, Command]
[1, 1, "x=5"]
[1, 2, "y=10"]
[2, 3, "z=15"]
[2, 4, "x=20"]

Indexed and ordered by term + index

Raft — Safety Properties (สมบัติความปลอดภัย)

text

1. Election Safety: มี leader ได้แค่ 1 ตัวต่อ 1 term
2. Leader Append-Only: leader ไม่เคยเขียนทับ log ตัวเอง (ต่อท้ายอย่างเดียว)
3. Log Matching: ถ้า 2 log มี entry ที่ (term, index) เดียวกัน → entry ก่อนหน้าทั้งหมดตรงกัน
4. Leader Completeness: entry ที่ committed แล้วจะอยู่ใน log ของ leader ทุกตัวในอนาคต
5. State Machine Safety: ถ้า node หนึ่ง apply entry ไปแล้ว node อื่นจะไม่ apply ค่าที่ต่างออกไปที่ index เดียวกัน

Visualizing Raft — ดูภาพประกอบ

text

Use https://raft.github.io/ — interactive Raft visualization
- See leader election
- See log replication
- See partition + recovery

5. Raft Step-by-Step — เดินทีละขั้น

สถานะเริ่มต้น

text

[A] Follower, term 0, log [empty]
[B] Follower, term 0, log [empty]
[C] Follower, term 0, log [empty]

Election — timer ของ A หมดอายุ

text

[A] Candidate, term 1, voted for self
[A] → RequestVote(term=1) → B, C

B + C:
- term 0 → term 1, vote for A
- Reset election timer

[A] receives 2 votes (with self = 3)
[A] Leader of term 1

Client Write — ลูกค้าเขียนข้อมูล

text

Client → [A] write "x=5"

[A]:
- Append [term=1, index=1, x=5] to log (uncommitted)
- Send AppendEntries(entry, prev=empty) to B, C

B + C:
- Append entry
- Reply success

[A] sees 2 successes (majority of 3)
- Mark entry as committed
- Apply "x=5" to state machine
- Reply success to client

Next heartbeat:
- A tells B, C: commit index = 1
- B, C apply "x=5"

Network Partition — network ขาด

text

Partition: [A] | [B, C]

A side (minority):
- Can't get majority for new writes
- Block writes
- A still thinks it's leader (until later)

B + C side (majority):
- B's timer expires
- B becomes candidate, term=2
- Gets C's vote (majority of 3)
- B becomes leader

Now: 2 leaders! (A in term 1, B in term 2)
- A's writes fail (can't get majority)
- B accepts new writes

Partition heals:
- A sees B's heartbeat with term=2 > A's term=1
- A steps down to follower
- A's uncommitted entries discarded
- A catches up from B

→ Raft จัดการ partition ได้อย่างถูกต้อง — ฝั่งที่ไม่มี majority จะหยุดเขียน รอจน partition heal แล้วค่อยตามมา catch up

⚠️ คำเตือน — Raft split-brain ชั่วคราว: ระหว่าง partial partition อาจมี 2 ตัวเชื่อว่าตัวเองเป็น leader ชั่วคราว (A คิดว่ายังเป็น leader term 1, B กลายเป็น leader term 2 จริง) — A จะรู้ตัวก็ต่อเมื่อ:
เห็น heartbeat ของ B ที่มี term สูงกว่า → step down ทันที, หรือ
leader lease ของ A หมดอายุ (ถ้า implement leader lease optimization)
ระหว่างนั้น A อาจ "อ่าน" (ไม่ใช่เขียน) ค่าเก่าให้ client ได้ — เขียนไม่สำเร็จเพราะไม่มี majority สรุปคือ safety ของ write ปลอดภัย แต่ stale read อาจหลุดได้ ถ้าไม่ใช้ ReadIndex/Lease Read

5.5 Raft at Scale — Multi-Raft (มัล-ติ-ราฟต์) + Production Optimizations

⚠️ (ขั้นต่อยอด · Senior+ level / DB engineer) — basic ที่เข้าใจ single Raft แล้ว ข้าม section นี้ทั้งหมดได้ ไม่กระทบ ไปอ่าน section 6 ต่อได้เลย — กลับมาเมื่อจะ implement distributed SQL database หรือ debug CockroachDB/TiKV production

Multi-Raft (มัล-ติ-ราฟต์) = การรัน Raft groups หลาย ๆ กลุ่มพร้อมกันเพื่อ scale write throughput — single-leader Raft มี throughput limit (leader bottleneck) — production distributed databases ใช้ Multi-Raft: แต่ละ shard (= ส่วนย่อยของข้อมูล) มี Raft group แยก, 1 cluster มี Raft groups เป็นพัน ๆ groups พร้อมกัน

Multi-Raft Pattern

text

CockroachDB / TiKV / YugabyteDB pattern:

Cluster มี data split เป็น "ranges" (64MB-256MB each):
- Range 0: key [a-c) → Raft group {nodeA, nodeB, nodeC}, leader=A
- Range 1: key [c-f) → Raft group {nodeB, nodeD, nodeE}, leader=D
- Range 2: key [f-k) → Raft group {nodeA, nodeC, nodeE}, leader=C
- ... 10,000 ranges

แต่ละ range = 1 Raft group ที่อิสระ
- Leader คนละ node → parallel write throughput
- Replica คนละชุด → fault tolerance per range
- 1 transaction ที่ข้าม ranges → ต้อง 2PC ระหว่าง Raft groups (CockroachDB ใช้ parallel commits)

💡 Throughput math (เป็นค่าประมาณ — ขึ้นกับ hardware/network):
Single Raft (HDD/network-bound classic): ~10K writes/sec — leader bound
Single Raft (etcd 3.5+ บน NVMe SSD): 50K+ writes/sec (เลข 10K เป็นค่าประมาณยุค HDD)
Multi-Raft 1000 groups: theoretical scaling ระดับ 1M+ wps; ตัวเลข "10M wps" เป็นขอบบนทางทฤษฎี — CockroachDB benchmark ในของจริงไปถึงราว 1M qps ด้วย tuning ดี ๆ
Trade-off: cross-range transactions ช้ากว่า single-range (ต้อง 2PC)

Production Optimizations ที่ Raft paper ไม่ลึก

📌 ต่อไปนี้คือ optimization ขั้นต่อยอด — basic ข้ามได้ ทำความเข้าใจ Raft พื้นฐาน (sections 4-5) ก่อนค่อยกลับมาอ่านส่วนนี้เมื่อจะ deploy production cluster

2 ตัวที่ต้องรู้ก่อน (core):

text

1. Pre-Vote (พรี-โหวต = โหวตซ้อมก่อนโหวตจริง)
   - ก่อน election → ตรวจสอบ "ฉันมีโอกาสชนะไหม?"
   - ป้องกัน node ที่ partition กลับมา bump term ผิด ๆ
   - Default ใน etcd, TiKV (มี config disable ได้)
   - Reference: Section 9.6 ของ Ongaro's PhD thesis (2014)
     ⚠️ ไม่ใช่ Raft Extended paper — Pre-Vote อยู่ใน thesis เท่านั้น

2. Leader Lease (ลีส = สัญญาเช่าตำแหน่ง leader)
   - Leader hold "lease" (เช่น 9 วินาที) → ไม่ต้อง quorum สำหรับ read
   - Linearizable reads ที่ leader (ตาม CockroachDB approach)
   - ต้อง assume clock skew < lease/2

3 ตัวที่เหลือ (รู้ว่ามี — implementation รายละเอียดใน Raft Extended Paper):

text

3. Witness (วิท-เนส) / Non-voting Replica
   - Replica ที่ vote ได้แต่ไม่เก็บ full data
   - Use case: 3-node setup ใน 2 DC + 1 witness ใน 3rd DC
   - Cost-effective HA

4. Joint Consensus (จอยน์ คอน-เซน-ซัส = consensus ร่วม)
   - membership change (เพิ่ม/ลด node) แบบปลอดภัย
   - Raft paper Section 6 — multi-step protocol
   - Add/remove node → C_old,new joint config → C_new
   - ป้องกัน split-brain ตอน topology change

5. Read Index / Lease Read
   - Linearizable read โดยไม่ต้อง append log entry
   - ส่ง heartbeat → confirm leadership → read state machine
   - ลด tail latency 2-3x

Multi-Raft vs Single-Raft — เลือกตามขนาด

	Single Raft	Multi-Raft
Throughput	10K wps (leader bound)	1M+ wps (parallel)
Complexity	ต่ำ	สูง (range splitting, rebalancing)
Cross-range txn	N/A (single group)	ต้อง 2PC / parallel commits
ใช้ใน	etcd, Consul (config-sized data)	CockroachDB, TiKV, YugabyteDB (TB+ data)
เหมาะกับ	< 10 GB total state	TB+ horizontal scaling

📚 เรียนต่อ: CockroachDB blog "How CockroachDB Distributes Atomic Transactions" + TiKV docs "Raft in TiKV"

6. ทำไม Raft ถึงเป็นที่นิยม

Raft กับ Paxos ให้การรับประกันเหมือนกัน แต่ Raft ชนะใจวงการเพราะ "เข้าใจง่ายกว่ามาก" — ออกแบบมาให้แยกส่วน (leader election, log replication, safety) ชัดเจน implement ถูกและ debug ง่ายกว่า จึงเป็นเหตุผลที่ระบบดัง ๆ อย่าง etcd/Consul/TiKV เลือกใช้:

text

✅ Understandable
✅ Practical (most implementations)
✅ Visualizations + papers
✅ Used by many open source (etcd, Consul, TiKV)

Compared to Paxos:
- Same guarantees
- Easier to implement correctly
- Easier to debug

7. ZooKeeper และ ZAB

ZooKeeper เป็นบริการ coordination รุ่นเก๋าที่ใช้ algorithm ของตัวเองชื่อ ZAB (คล้าย Paxos/Raft) — ระบบ Big Data จำนวนมาก (Kafka เดิม, HBase, Hadoop) พึ่งมันสำหรับ lock, config, leader election ฟีเจอร์เด่นคือ ephemeral node ที่หายเองเมื่อ client หลุด เหมาะกับ leader election และ service registry:

text

ZooKeeper Atomic Broadcast (ZAB)
- Similar to Paxos / Raft (มี leader election + log replication เหมือนกัน)
- ต่างจาก Raft: ZAB เน้น "primary-backup" + ordered broadcast
  สำหรับ ZooKeeper โดยเฉพาะ ไม่ใช่ general-purpose consensus
- มือใหม่: รู้แค่ว่ามี ZAB ใช้ใน ZooKeeper พอ ไม่ต้องลึก
- Used in: Kafka (ก่อน 4.0), HBase, Hadoop

ZooKeeper provides:
- Distributed lock
- Configuration management
- Leader election (for other apps)
- Group membership

API:
- create, delete, exists, getData, setData, getChildren
- Watches (notification on change)
- Ephemeral nodes (auto-delete on client disconnect)

Ephemeral Node — node ชั่วคราว

text

Client creates: /lock-12345
- Lives only while client connected
- Disconnect → auto-delete

Used for:
- Leader election (all candidates create ephemeral, lowest wins)
- Service registry (service alive while connected)
- Distributed lock

8. etcd กับ ZooKeeper — เทียบกัน

etcd กับ ZooKeeper ทำงานคล้ายกัน (coordination service) แต่ต่างยุคต่างปรัชญา — etcd ใหม่กว่า เขียนด้วย Go ใช้ Raft + gRPC (Kubernetes เลือกใช้), ส่วน ZooKeeper เก่ากว่า อยู่ในสาย Java/Hadoop ตารางนี้ช่วยตัดสินใจ ระบบใหม่ ๆ มักเลือก etcd:

text

etcd:
- Go-based
- Raft consensus
- gRPC API
- K8s uses it
- Modern, simpler

ZooKeeper:
- Java-based
- ZAB consensus
- Custom binary protocol
- Hadoop ecosystem
- Older, harder to operate

→ New systems prefer etcd
→ Existing Hadoop: ZooKeeper
→ Kafka: ย้ายจาก ZooKeeper → KRaft (Kafka's own Raft) แล้ว
   Timeline:
   - Kafka 3.0 (2021) → KRaft preview
   - Kafka 3.3 (2022) → KRaft GA (production-ready)
   - Kafka 3.5 (2023) → KRaft เป็น default
   - Kafka 4.0 (มี.ค. 2025) → ลบ ZooKeeper ทิ้งทั้งหมด, KRaft เป็น mode เดียว

9. Use Cases — Consensus ใช้ทำอะไรได้บ้าง

consensus ฟังดูเป็นทฤษฎี แต่จริง ๆ มันอยู่เบื้องหลังงานที่เราใช้ทุกวัน — distributed lock, service discovery, config management, leader election, distributed transaction และ replicated state machine ส่วนนี้รวมการใช้งานจริงที่ consensus เป็นรากฐาน:

text

1. Distributed lock
   - Only 1 process can do action
   - Examples: distributed cron, leader-only operation

2. Service discovery
   - Register service, others find
   - Examples: K8s services, Consul

3. Configuration management
   - Same config across all nodes
   - Examples: feature flags, secrets

4. Leader election
   - 1 master coordinates work
   - Examples: distributed scheduler

5. Distributed transactions
   - All-or-nothing across nodes
   - Examples: 2PC, Paxos commit

6. Replicated state machine
   - All replicas execute same operations in same order
   - Examples: distributed database

10. Spanner — "เวทย์มนตร์ของ Google" (ที่ใช้ฮาร์ดแวร์จริงๆ)

Spanner = distributed SQL database ที่ linearizable consistent ระดับ global (ทั่วทั้งโลก) นี่เป็นไปไม่ได้ตามทฤษฎีปกติ — แต่ Google ทำได้ด้วยการ "โกง" ที่ฮาร์ดแวร์

ปัญหา — ทำไม global linearizable ถึงยาก

text

ปัญหาหลัก: clock บนแต่ละ data center "ไม่ตรงกัน"
- Data center US ตี 10:00:00
- Data center EU ตี 10:00:01  (ช้ากว่า 1 วินาที)
- Data center Asia ตี 09:59:59 (เร็วกว่า 1 วินาที)

ถ้า transaction เกิดที่ US ตี 10:00:00 และ EU ตี 10:00:00
→ ใครเกิดก่อน? เราตอบไม่ได้!

ดังนั้น cross-region transactions = ไม่สามารถ order ได้
จึง impossibile to do linearizable globally

TrueTime — เทคนิคของ Google

Google แก้ปัญหานี้ด้วย TrueTime API ที่ให้ clock ที่ "เกือบ" ตรงกัน

text

TrueTime API:
  now() returns INTERVAL [earliest, latest]
  เช่น now() = [10:00:00.000, 10:00:00.007]

หมายความว่า "เวลาปัจจุบันอยู่ระหว่าง 2 ค่านี้ แน่นอน 100%"
ช่วงห่าง (uncertainty / ε หรือ epsilon = ค่าความไม่แน่นอนของเวลา):
  - paper Spanner ปี 2012: ~7 ms
  - Spanner ปัจจุบัน (Google talks 2023+): ลดเหลือ ~1-2 ms ในบาง region

Hardware ที่ใช้:

GPS receivers — sync กับสัญญาณ satellite (พลาด ms ลง)
Atomic clocks — สำรองเมื่อ GPS ไม่ทำงาน
TrueTime daemon — รวมข้อมูลจากหลายแหล่ง รายงาน "uncertainty"

Commit-Wait Protocol — เหตุที่ Linearizable ระดับ Global

นี่คือ trick ที่สำคัญที่สุด — เรียกว่า commit-wait:

text

Transaction T1 commit:
1. ขอเวลาจาก TrueTime: [t_earliest, t_latest]
2. เลือก commit timestamp = t_latest  (เลือก "ขอบบน" ของช่วง)
3. ทำงานต่อ (write data)
4. WAIT จนกว่า "now().earliest > t_latest"
   → คือรอจนเวลาจริง "เลย" t_latest ไปแล้ว
   → ใช้เวลาราวช่วงห่าง (~7ms ในยุคแรก, ~1-2ms ในยุคนี้)
5. Commit สำเร็จ → return success ให้ client

Transaction T2 ที่เริ่มหลัง T1 return success:
- ขอเวลาใหม่จาก TrueTime → t_T2.earliest > t_T1_commit
- → T2 มี timestamp ใหญ่กว่า T1 แน่นอน
- → order ถูกต้อง!

ตัวอย่าง trace:

text

(หน่วยเวลาทั้งหมดเป็น millisecond — 10:00:00.000 ถึง 10:00:00.020 = ช่วง 0-20 ms)

Wall clock:    10:00:00.000 ──→ 10:00:00.020   (= 20 ms)
T1 begin:      now()=[10:00:00.000, 10:00:00.007]
T1 chooses:    commit_ts = 10:00:00.007
T1 writes data, then WAIT until clock past 10:00:00.007
   (รอประมาณ 7 ms = ค่าช่วงห่าง / epsilon)
T1 returns:    10:00:00.008

T2 begin:      now()=[10:00:00.010, 10:00:00.017]
T2 chooses:    commit_ts = 10:00:00.017
T2.commit_ts (10:00:00.017) > T1.commit_ts (10:00:00.007) ✅

→ เคล็ดลับ: เสียเวลารอช่วงห่าง (epsilon) ระหว่าง commit → ทำให้ทุก transaction มี order ที่ถูกต้องในเวลาจริง

ผลกระทบของ Spanner

text

✅ Linearizable consistent ระดับ global
✅ SQL + ACID transactions cross-region
✅ Google's secret sauce — สำคัญต่อ Adwords, Gmail backend

❌ ต้องใช้ hardware เฉพาะ — GPS + atomic clocks
❌ ต้องมี data center ของ Google เอง
❌ Commit ช้ากว่า single-region database (มี wait)
❌ ราคาสูง (สำหรับ Google Cloud Spanner managed service)

Open Source Alternatives — สำหรับคนที่ไม่ใช่ Google

ส่วนใหญ่ไม่มี GPS + atomic clocks — ใช้ software-only clock แทน:

CockroachDB

Inspired by Spanner แต่ใช้ HLC (Hybrid Logical Clock) แทน TrueTime (HLC = combo ของ physical clock + logical counter — รายละเอียดในบท 4)
Open source + Postgres-compatible
Latency สูงกว่า Spanner (ไม่มี hardware clock) แต่ถูกกว่ามาก
เหมาะกับ: SaaS ที่ต้องการ distributed SQL

YugabyteDB

Postgres + Cassandra API compatible
Similar architecture กับ CockroachDB
Open source

TiDB

Inspired by Spanner
HTAP (OLTP + OLAP) — OLTP (Online Transaction Processing = งานธุรกรรมเรียลไทม์) + OLAP (Online Analytical Processing = งานวิเคราะห์) ทำได้ทั้งคู่
Open source

Comparison

	Spanner	CockroachDB	TiDB	YugabyteDB
Clock	TrueTime (hardware)	HLC (software)	TSO = Timestamp Oracle (แหล่งเวลาเดียว)	Hybrid HLC
API	SQL	Postgres SQL	MySQL SQL	Postgres + Cassandra
Managed	Google Cloud only	Self-host or Cloud	Self-host or Cloud	Self-host or Cloud
Global strong consistency	✅	✅ (with ms-level lag)	⚠️ Region-only	✅

11. Replicated State Machine — รัน state machine แบบ replicate

นี่คือแนวคิดที่เชื่อม consensus เข้ากับ replication — ถ้าทุก replica เริ่มจาก state เดียวกันแล้ว execute "ชุดคำสั่งเดียวกันในลำดับเดียวกัน" มันก็จะได้ state ปลายทางเหมือนกันเป๊ะ หน้าที่ของ consensus คือทำให้ทุก node เห็นด้วยกับ "ลำดับ" ของคำสั่ง — นี่คือหลักการเบื้องหลัง distributed database และแม้แต่ blockchain:

text

แนวคิด:
- ทุก replica execute ชุด operation เดียวกัน
- state เริ่มต้นเดียวกัน + operation เดียวกัน = state ปลายทางเดียวกัน
- ใช้ consensus เพื่อตกลง "ลำดับ" ของ operation

State machine:
- Deterministic (ผลแน่นอน input เดียวกันได้ output เดียวกันเสมอ)
- Input: คำสั่ง (command)
- Output: ผลลัพธ์ (response)

Replication ผ่าน consensus:
- ทุก replica ตกลงลำดับเดียวกัน: [op1, op2, op3, ...]
- ต่างคนต่าง apply ตามลำดับ → ทุกตัว consistent กัน

ใช้ใน:
- ระบบ Raft / Paxos
- distributed database
- blockchain (โดยพื้นฐานก็คือสิ่งนี้)

12. Byzantine Fault Tolerance (BFT) — "ถ้ามี node ที่นิสัยเสีย/โดน hack ละ?"

Raft/Paxos สมมติว่า node ทุกตัว "ซื่อสัตย์" — อาจตายได้ ช้าได้ แต่ไม่โกหก แต่ในโลกที่ node อาจถูก compromise ได้ (เช่น blockchain) — ต้องมี BFT

Byzantine Generals Problem (1982) — Intuition

text

ลองนึกถึงสงครามที่ Byzantine:
  3 นายพล (A, B, C) ต้องตัดสินใจร่วมกันว่า "โจมตี" หรือ "ถอย"
  ต้อง agree ทุกคน — ไม่งั้นแพ้
  
  ปัญหา: บางคน "เป็นไส้ศึก" — บอก A ว่า "โจมตี" แต่บอก C ว่า "ถอย"

ลองคิดดู — 3 generals, มีไส้ศึก 1 คน:

text

สมมุติ B เป็นไส้ศึก:
- A → "โจมตี"
- B (พูดกับ A) → "โจมตี"
- B (พูดกับ C) → "ถอย"
- C → "ฉันได้รับข้อความขัดกัน A บอกโจมตี, B บอกถอย — ใครพูดจริง?"

A ไม่รู้ว่า C ได้ข้อความตรงกันไหม
C ไม่รู้ว่า A ได้ข้อความตรงกันไหม

→ ไม่สามารถ agree ได้ ด้วย 3 นายพล + 1 ไส้ศึก!

ทฤษฎี — ต้องมี 3F + 1 node

text

ทฤษฎีพิสูจน์ได้:
  ต้องการ tolerate F Byzantine failures
  → ต้องมี total nodes ≥ 3F + 1

ตัวอย่าง:
F = 1 (มีไส้ศึก 1 คน):     ต้องมี ≥ 4 nodes  (3·1+1)
F = 2 (มีไส้ศึก 2 คน):     ต้องมี ≥ 7 nodes  (3·2+1)
F = 10 (มีไส้ศึก 10 คน):   ต้องมี ≥ 31 nodes (3·10+1)

ทำไม 3F+1? (derivation ที่ถูกต้อง)

  สมมติทั้งหมด N nodes, มี F เป็น Byzantine (โกหก/ส่งข้อมูลขัดกัน)
  → มี honest = N - F

  เพื่อให้ honest "outvote" Byzantine ได้:
  1. ต้องการ quorum ขนาด 2F+1 ในการ commit
     (เพราะถ้า quorum = 2F+1, แม้ Byzantine F ตัวจะ vote ทั้งหมดในนั้น
      ก็ยังเหลือ honest อย่างน้อย F+1 ที่ "ชนะ")
  2. quorum ขนาด 2F+1 จาก N nodes ใด ๆ ต้อง intersect (ตัดกัน)
     ในอย่างน้อย 1 honest node (เพื่อ safety)
     จำนวน intersection ≥ 2(2F+1) - N
     ต้องมี ≥ F+1 (เพื่อให้แน่ใจว่ามี ≥ 1 honest ในนั้น)
     → 2(2F+1) - N ≥ F+1
     → 4F + 2 - N ≥ F + 1
     → N ≤ 3F + 1
     → ดังนั้น N ≥ 3F + 1

ทำไมแพงกว่า Raft?

text

Raft (crash-only):
- ต้องการ majority (N/2 + 1)
- 3 nodes ทน 1 fail → ยังทำงานได้

BFT:
- ต้องการ 2F + 1 honest จาก 3F + 1 total
- 4 nodes สำหรับ 1 ไส้ศึก
- ต้องส่งข้อความเยอะกว่ามาก (cross-verify)
- Throughput:
  - classical PBFT: ต่ำกว่า Raft 10-100x
  - modern HotStuff/Tendermint: ภายใน 2-5x ของ Raft
    (linear message complexity ทำให้ scale ดีขึ้นมาก)

เมื่อไหร่ใช้ BFT? (ปกติ = ไม่ใช้)

Environment	Failure model	ใช้ algorithm
ออฟฟิศ/บริษัทเดียวกัน data center	Crash only	Raft / Paxos
Microservices internal	Crash only	Raft (etcd)
Multi-org consortium (3-10 orgs)	อาจมีไส้ศึก	PBFT / Tendermint
Public blockchain (Bitcoin, Ethereum)	Anyone can join	PoW / PoS (probabilistic BFT)

BFT Algorithms ที่ใช้จริง

PBFT (Practical BFT) — 1999

BFT แบบแรกที่ "practical" (ก่อนหน้ามีแต่ทฤษฎี)
ใช้ใน blockchain ยุคแรก
Throughput: classical PBFT ~1-10K tps; modern variants (HotStuff family) ขึ้นไปถึง 100K+ tps
Scale ไม่ค่อยดีเพราะ O(n²) messages — แก้ด้วย HotStuff (linear O(n))

Tendermint — ทันสมัย

ใช้ใน Cosmos blockchain
Round-based, leader rotation
Throughput ~1-10K tps

HotStuff — ใหม่กว่า

ใช้ใน Aptos (AptosBFT — HotStuff variant)
Linear message complexity (O(n)) → scale ดีกว่า PBFT มาก
หมายเหตุการใช้งานอื่น:
- Diem/Libra (Facebook) เคยใช้ HotStuff — ปัจจุบัน defunct (ปิดตัวปี 2022)
- Sui ไม่ใช้ HotStuff — ใช้ Bullshark/Narwhal/Mysticeti (DAG-based BFT)

Proof of Work (Bitcoin)

ไม่ใช่ BFT classical — เป็น probabilistic consensus
ใช้ "computational puzzle" แทน voting
ทนต่อ Byzantine attack ได้ถ้า hash power ของ honest > 50% ⚠️ caveat: เป็นขอบเขตทางทฤษฎี — selfish mining attack ทำได้ที่ ~33%
เปลือง energy มหาศาล

Proof of Stake (Ethereum)

Ethereum migrated to PoS via The Merge (15 ก.ย. 2022) หมายเหตุ: คำว่า "Ethereum 2.0" deprecated ไปแล้ว (Ethereum Foundation ประกาศต้นปี 2022)
ใช้ "stake" (จำนวนเงินที่ lock) แทน hash power
Energy efficient (-99.95% เทียบกับ PoW)
Slashing — ถ้า cheat → เสีย stake

สรุปสำหรับมือใหม่

text

ในงานทั่วไป (microservices, data infrastructure):
   → ไม่ต้องใช้ BFT
   → Raft / Paxos เพียงพอ
   → ถือว่า node ในออฟฟิศ "ซื่อสัตย์"

ในงาน blockchain / multi-organization:
   → ต้องใช้ BFT
   → เลือก algorithm ตาม trade-off (throughput vs decentralization)

→ Most apps: ไม่ต้องเรียนลึก — รู้ว่ามี + เมื่อไหร่ใช้ ก็พอ

13. Multi-Region Replication — replicate ข้าม region

การ replicate ข้ามทวีปเจอกำแพงใหญ่คือ latency 100-300ms ที่ทำให้ sync write ช้าจนใช้ไม่ได้ — จึงมีหลายกลยุทธ์ให้เลือกตาม trade-off: cluster แยกต่อ region แล้ว async ระหว่างกัน (เร็วแต่ eventual), global consensus แบบ Spanner (strong แต่ช้า) หรือ read-only replica ตาม region:

text

Challenges:
- High latency between regions (100-300 ms)
- Sync writes too slow
- Network partitions across regions

Strategies:

1. Per-Region Cluster, Async Inter-Region
   - Strong within region
   - Eventually consistent across
   - Lower latency
   
2. Global Consensus (Spanner)
   - Strong across regions
   - High latency (round-trip + uncertainty wait)
   - Worth: global apps + compliance

3. Read-only Replicas
   - Master in 1 region
   - Followers in other regions
   - Local reads fast, writes go to master (slow)

14. Replication Mode ใน Postgres

มาดูทฤษฎี replication ในของจริงที่ใช้กันมากที่สุด — PostgreSQL รองรับหลายโหมด: async (default, เร็วแต่เสี่ยงข้อมูลหาย), synchronous (รอ standby ตอบ, ไม่เสียข้อมูล), quorum-based (รอ N จาก M) เข้าใจตรงนี้จะตั้งค่า HA ของ Postgres ได้ตรงกับความต้องการ:

text

1. Asynchronous (default):
   - Primary writes, sends to standby async
   - Risk: data loss if primary crashes before send

2. Synchronous:
   - Wait for standby ACK before return
   - No data loss
   - Slower (especially cross-region)

3. Quorum-based (since PG 9.6):
   - Wait for N of M standbys
   - Configurable

4. Apply Mode:
   - Standby received WAL ≠ Standby applied
   - Configurable: streaming, hot_standby_feedback

sql

-- pg_hba.conf
synchronous_standby_names = 'FIRST 1 (replica1, replica2)'
-- Wait for at least 1 of these

15. Failover — สลับ primary เมื่อ fail

text

Primary fails → promote replica to primary

Tools:
- Patroni — popular Postgres HA (uses etcd)
- Repmgr — Postgres
- Stolon — Postgres (uses etcd/Consul)
- AWS RDS Multi-AZ — managed
- GCP Cloud SQL HA — managed

Patroni Architecture — เดินทีละขั้น

Patroni เป็น Python script ที่ wrap รอบ Postgres และคุยกับ etcd/Consul/ZooKeeper

Walkthrough — ตอน operation ปกติ

text

Patroni A (primary):
1. Lock leader key ใน etcd ทุก 10 วินาที (renew lease)
   PUT /service/postgres/leader = "patroni-a"  TTL=30s
   
2. Postgres A: accept writes
3. WAL streaming ไปยัง Postgres B (replica)

Patroni B (replica):
1. ดู leader key ใน etcd
2. เห็นว่า "patroni-a" ถือ leader
3. Configure Postgres B เป็น replica ของ A
4. Watch leader key (รอ event ถ้าเปลี่ยน)

Walkthrough — ตอน Failover

text

[t=0]   Patroni A: รัน healthcheck on Postgres A → ผ่าน
[t=1s]  Patroni A: ตาย (kernel panic, network drop, OOM)
[t=10s] Patroni A: ไม่ได้ renew lease ของ leader key → key ยังอยู่
[t=30s] etcd: lease ของ leader key หมดอายุ
        → keys ที่ผูกกับ lease นั้นถูก auto-removed
        (etcd ใช้กลไก lease ไม่ใช่ TTL บน key ตรง ๆ)

[t=31s] Patroni B: เห็น leader key หาย
        - ตรวจสอบว่า Postgres B sync ทันไหม (replica lag)
        - ถ้า lag เกิน threshold → ไม่ promote (กลัวเสีย data)
        - ถ้า lag น้อย → continue

[t=32s] Patroni B: พยายามขึ้นเป็น leader
        PUT /service/postgres/leader = "patroni-b" (compare-and-swap)
        
[t=33s] etcd: ยอม (key ว่าง) → Patroni B = leader
[t=34s] Patroni B: รัน "pg_promote" → Postgres B กลายเป็น primary
[t=35s] Update DNS / HAProxy / pgBouncer config
[t=40s] Application: connect ไป primary ใหม่

→ Total time: ~15-60 วินาที (ขึ้นกับ TTL/loop_wait config — ตัวอย่างนี้ TTL=30s)

Split Brain Prevention — Patroni ป้องกันยังไง

Scenario: Patroni A "ฟื้น" หลัง failover

text

[t=60s] Patroni A: ฟื้นจาก network drop
[t=61s] Patroni A: ตรวจสอบ etcd
        - เห็น leader key = "patroni-b" (ไม่ใช่ตัวเอง)
        - รู้ว่าตัวเอง "ตกขบวน"
[t=62s] Patroni A: รัน "pg_rewind"
        - หา divergence point ระหว่าง A กับ B
        - Rollback WAL ที่ A เคย commit แต่ B ไม่มี
        - ทำให้ A กลายเป็น replica ของ B
[t=70s] Patroni A: เริ่ม replica streaming จาก Postgres B

→ Key safety mechanism:

etcd lock: ห้ามมี 2 leader พร้อมกัน (ผ่าน compare-and-swap)
pg_rewind: rollback divergent WAL อัตโนมัติ
Fencing (optional):
- แบบ legacy: STONITH = "Shoot The Other Node In The Head" — kill old primary ผ่าน power switch / IPMI / cloud API ถ้าไม่ตอบ
- แบบ cloud-native ปัจจุบัน: K8s Postgres operators (CloudNativePG, Crunchy Postgres for K8s, Zalando postgres-operator) ใช้ etcd leader lock + pod eviction แทน IPMI/STONITH (เซ็ตง่ายกว่า, ไม่ต้องมี hardware fencing)

Split Brain Prevention — เทียบหลายแนวทาง

text

1. Fencing (STONITH):
   - Kill old primary ที่ infrastructure level
   - Pacemaker + IPMI หรือ AWS API stop instance
   - แน่ใจ 100% ว่าไม่มี 2 primary
   - แต่: เซ็ตยาก, ต้องมี API

2. Witness/Quorum:
   - Old primary ต้องมี majority ถึงจะอยู่ได้
   - ถ้า partition ไป minority → step down
   - ใช้ใน MongoDB replica set

3. Consensus-based lock:
   - Patroni + etcd ทำแบบนี้
   - ต้อง hold lock ใน etcd → ถึงเป็น primary ได้
   - etcd ใช้ Raft → ป้องกัน split brain ในตัว

Failover Time — ปรับ tuning parameters

Parameter	ค่าปกติ	Trade-off
`ttl`	30s	สั้น = failover เร็ว, ยาว = ทน network blip ได้ดี
`loop_wait`	10s	Patroni check interval
`retry_timeout`	10s	timeout สำหรับ etcd operation
`maximum_lag_on_failover`	1 MB	replica lag ที่ยอมรับได้ก่อน promote

text

ต้องการ failover < 15s:
   ttl=15, loop_wait=5
   → เสี่ยง false positive เพิ่ม

16. Quorum-Based Replication — สไตล์ Cassandra (Leaderless / Dynamo-style)

ระบบ leaderless (= ไร้ master, ทุก node เท่ากัน) อย่าง Cassandra/ScyllaDB/Riak/DynamoDB ไม่มี master — กระจายข้อมูลเป็น N สำเนาแล้วใช้ quorum (W+R>N) รับประกัน consistency

text

N = จำนวน replica (Replication Factor, RF) เช่น 3
W = จำนวน node ที่ต้องยืนยัน write ก่อน return success
R = จำนวน node ที่ต้องอ่านก่อน return ค่า

กฎทอง: W + R > N → strong consistency
  (รับประกันว่า write set กับ read set ต้องตัดกันอย่างน้อย 1 node
   → read จะเห็น write ล่าสุดเสมอ)

ตัวอย่าง N=3:
- W=3, R=1 → write ช้า, read เร็ว (ดีสำหรับ read-heavy)
- W=1, R=3 → write เร็ว, read ช้า (ดีสำหรับ write-heavy)
- W=2, R=2 → balanced (CQL default = QUORUM)
- W=1, R=1 → eventual consistency (W+R=2 ≤ N=3 ✗)

⚠️ Cassandra "AP" กับ QUORUM+LWT caveat: Cassandra ปกติเป็น AP ใน CAP — เลือก Availability เหนือ Consistency แม้ใช้ QUORUM consistency level (W+R>N) ก็เป็นแค่ "strong read-your-writes" ไม่ใช่ linearizable ถ้าต้อง linearizable จริง ๆ (เช่น compare-and-set) ต้องใช้ LWT (Lightweight Transactions) ที่ใช้ Paxos ใต้ฟ้าด — แลกด้วย latency 4 round-trips, ช้ากว่าปกติ ~5-10x สรุป: Cassandra = AP โดย default; เป็น CP แค่ในส่วน LWT เท่านั้น

ส่วนนี้ยังครอบกลไกซ่อมข้อมูลที่หลุดให้กลับมาตรงกัน 3 แบบ:

กลไก	เมื่อไหร่ทำงาน	จุดประสงค์
Hinted Handoff	ตอน write แล้ว replica ลง	เก็บข้อมูลไว้ส่งทีหลังเมื่อ replica กลับมา
Read Repair	ตอน read แล้วเจอ replica ไม่ตรงกัน	ซ่อมสด ๆ ตอนอ่าน
Anti-Entropy (Merkle tree)	งาน background รัน periodic	ซ่อมข้อมูลที่ค้างหลังจาก hinted+read repair ไม่ครอบ

text

Each piece of data: N replicas (RF = 3 typical)

Write flow (W=2, N=3):
- Coordinator (node ที่ client ติดต่อ) ส่ง write ไปทั้ง 3 replica
- รอ ACK 2 ตัวก็ตอบ success → ตัวที่ 3 ตามไปเองทีหลัง

Read flow (R=2, N=3):
- Coordinator ส่ง read ไปทั้ง 3 (หรือเลือก digest read)
- รอ response 2 ตัว → compare → latest wins (per timestamp)
- ถ้าเจอไม่ตรง → trigger read repair

Hinted Handoff — เก็บไว้ส่งทีหลัง

text

ตอน write ไปยัง replica → ถ้า replica ตัวนึง down:
- Coordinator (หรือ replica อื่น) เก็บ "hint" = ข้อความบอกว่า
  "ตัวนี้ยังไม่ได้รับ write นี้นะ"
- เมื่อ down node กลับมา → node อื่นส่ง hints ที่เก็บไว้ให้
- → eventually all replicas updated

ข้อจำกัด:
- ถ้า down นานเกิน hint_window (Cassandra default 3 ชม.) → hint จะถูก drop
  ต้อง fallback ไปใช้ read repair / anti-entropy แทน
- Resilient ต่อ outage สั้น ๆ

Read Repair — ซ่อมสด ๆ ตอน read

text

ตอน read ถ้าเจอ replica มีค่าไม่ตรงกัน:
- เลือกตัวที่ timestamp ใหม่สุด → return ให้ client
- ส่ง write ไปอัปเดต replica ที่ stale
  (ทำแบบ async = ไม่หน่วง read ที่ตอบ client แล้ว)
- หรือ sync (blocking read repair) สำหรับ consistency level สูง

Anti-Entropy — ซ่อม background ด้วย Merkle Tree

text

Cassandra/DynamoDB/Riak รัน job เป็นระยะ:
- แต่ละ replica คำนวณ "Merkle tree"
  (= hash tree ของข้อมูลทั้งหมด, ใบ = hash ของแต่ละ chunk)
- เทียบ Merkle tree ระหว่าง replica
- ส่งเฉพาะส่วน "diff" (subtree ที่ hash ไม่ตรง) ไป sync
  → ไม่ต้องส่งข้อมูลทั้งหมด → efficient

ใช้ใน: Cassandra (nodetool repair), DynamoDB, Riak

17. Geo-replication Patterns — รูปแบบ replicate ข้ามภูมิภาค

Single Leader — ง่ายสุด

text

[Primary in Region A]
   ↓ replicate (async)
[Replica in Region B] [Replica in Region C]

Writes: only to A
Reads: any region (some lag)

✅ Simple
❌ Writes slow for non-A users

Multi-Leader — ซับซ้อน

text

[Leader A] ←──→ [Leader B] ←──→ [Leader C]

Writes accepted anywhere
Sync between leaders (async)

✅ Local writes (fast)
❌ Conflicts (need resolution)
❌ Complex

Sharded — แบบที่ใช้บ่อย

text

Asia users → Asia leader (their region)
EU users → EU leader
US users → US leader

Cross-region:
- API call (slow but rare)
- Or copy of relevant data

✅ Fast for users
✅ Compliance (data residency)
❌ Cross-region operations harder

18. Tools ที่ใช้ Consensus ในชีวิตจริง

เพื่อให้เห็นว่า consensus ไม่ใช่แค่ทฤษฎี นี่คือรายชื่อเครื่องมือจริงที่คุณอาจใช้อยู่แล้วและ algorithm ที่มันใช้ — etcd/Consul (Raft), ZooKeeper (ZAB), CockroachDB/TiDB (Raft), ไปจนถึง blockchain (PoW/PoS/BFT) สังเกตว่า Raft ครองตลาดระบบยุคใหม่:

text

etcd — Raft (used by K8s, Kubernetes)
Consul — Raft (HashiCorp)
ZooKeeper — ZAB (used by HBase, Hadoop; Kafka ก่อน 4.0)
Kafka 4.0+ — KRaft (Kafka's own Raft, ZooKeeper removed)
Cassandra — Paxos for LWT (Lightweight Transactions) เท่านั้น
            — normal writes ใช้ quorum (W+R>N), ไม่ใช้ Paxos
CockroachDB — Raft per range (Multi-Raft)
TiDB / TiKV — Raft per region
MongoDB — Raft (Protocol Version 1 / pv1, ตั้งแต่ MongoDB 3.2 ปี 2015
          — เป็น Raft จริง แค่มีการ modify เล็กน้อย)
Postgres + Patroni — uses etcd for coordination

Single-leader / Multi-leader / Leaderless replication:
- Single-leader: Postgres, MySQL (1 master รับ write)
- Multi-leader: Active-Active + CRDT (CouchDB, Riak)
- Leaderless: Dynamo-style (Cassandra, ScyllaDB, Riak)
              ใช้ N/R/W quorum: W+R>N → strong consistency

Blockchain:
Bitcoin — PoW (proof of work)
Ethereum — PoS (proof of stake, ตั้งแต่ The Merge ก.ย. 2022;
            คำว่า "Ethereum 2.0" deprecated แล้ว)
Tendermint — BFT consensus (Cosmos)
Aptos — AptosBFT (HotStuff variant)
Sui — Bullshark/Narwhal/Mysticeti (DAG-BFT)

19. Distributed Database — หมวดหมู่

distributed database มีหลายประเภทตามรูปแบบข้อมูลและการรับประกัน — distributed SQL (CockroachDB/Spanner), wide-column (Cassandra), document (MongoDB), key-value (Redis), time-series, search รู้จักหมวดหมู่เหล่านี้จะช่วยให้เลือก DB ตรงกับงานแทนที่จะยัด workload ลงเครื่องมือที่ไม่เหมาะ:

text

Distributed SQL:
- CockroachDB
- TiDB
- YugabyteDB
- Google Spanner

Wide-column / NoSQL:
- Cassandra
- ScyllaDB (faster Cassandra)
- HBase
- DynamoDB

Document:
- MongoDB (replica set + sharded cluster)
- CouchDB (multi-leader)

Key-Value:
- Redis Cluster
- etcd
- DynamoDB

Time-series:
- TimescaleDB
- InfluxDB cluster

Search:
- Elasticsearch cluster
- OpenSearch

20. Operational Concerns — เรื่อง operation ที่ต้องคิด

ออกแบบเสร็จยังไม่จบ — การ "รัน" ระบบกระจายใน production มีเรื่องต้องดูแลอีกมาก: ขนาด cluster (ควรเป็นเลขคี่ ≥3), ความเร็ว disk/network, การ monitor replication lag และ quorum, backup และที่สำคัญคือ "ทดสอบ" สถานการณ์ล่ม ส่วนนี้รวมเช็กลิสต์ operation ที่ต้องเตรียม:

text

Running distributed system:

1. Cluster size — minimum 3, often 5
2. Network reliability — same region/AZ
3. Disk speed — SSD required usually
4. Memory — buffer pool sizing
5. CPU — depends on workload
6. Monitor:
   - Replication lag
   - Quorum reachable
   - Latency per node
   - Disk usage per node
   - Network throughput

7. Backup — full + WAL incremental
8. Test:
   - Node failure
   - Partition
   - Slow disk
   - Full disk

21. ตัวอย่างจริง — etcd Walkthrough

มาดูทุกอย่างทำงานจริงผ่าน etcd cluster 3 node — ไล่ทีละขั้นว่า PUT 1 ค่าเดินทางจาก client → leader → replicate ไป follower → commit เมื่อได้ majority → apply อย่างไร และทำไม read จาก follower อาจได้ค่าเก่า ตัวอย่างนี้ทำให้ Raft ที่เรียนมาเป็นรูปธรรม:

text

3-node etcd cluster:

[etcd-1] (leader)
[etcd-2] (follower)
[etcd-3] (follower)

Client: PUT /users/42 → "Anna"

1. Client → etcd-1 (leader)
2. etcd-1 appends [term, index, PUT users/42=Anna] to log
3. etcd-1 → AppendEntries → etcd-2, etcd-3
4. Both write to their log + ACK
5. etcd-1 has 2/3 commit → COMMITTED
6. Apply to state machine (in-memory K/V)
7. Return success to client
8. Next heartbeat: tell etcd-2, etcd-3 to apply

Client: GET /users/42

1. Client → any node (let's say etcd-2)
2. etcd-2 returns: "Anna"

Note: read can be slightly stale on followers
For strict consistency: read from leader

22. เลือก Tool ให้ตรงงาน

สรุปเป็นตารางตัดสินใจเร็ว ๆ — งานแต่ละแบบมีเครื่องมือที่เหมาะของมัน: service discovery ใช้ Consul/etcd, distributed SQL ใช้ CockroachDB, scale มหาศาลแบบ eventual ใช้ Cassandra/DynamoDB จับคู่ความต้องการกับเครื่องมือให้ถูกตั้งแต่แรกจะประหยัดความเจ็บปวดทีหลัง:

text

Need:                              Tool:
─────────                          ─────
Service discovery + config         Consul / etcd
K8s control plane                   etcd
Distributed lock                    Redis (Redlock) or ZooKeeper
Distributed SQL (strong consist)    CockroachDB / Spanner
Massive scale (eventual consist)   Cassandra / DynamoDB
Document store                      MongoDB
Time-series                          TimescaleDB / InfluxDB
Search                               Elasticsearch
Cache                                Redis
Coordinator (Hadoop ecosystem)      ZooKeeper

23. Pitfalls — กับดักที่พบบ่อย

รวมความผิดพลาดที่ทำให้ระบบ consensus/replication พัง — เขียน consensus เอง (เสี่ยงบั๊กลึก), ใช้ node จำนวนคู่ (เกิด tie), ไม่กัน split-brain, ไม่ backup เพราะคิดว่า "distributed แล้วปลอดภัย" รู้กับดักพวกนี้ไว้จะช่วยให้รอดจากหายนะที่กู้ไม่ได้:

text

1. Roll-your-own consensus
   - Subtle bugs
   - Use library (Raft implementation, etcd)

2. Even number of nodes (2, 4)
   - Can't form majority (2/2 = tie)
   - Use odd: 3, 5, 7

3. Geographic split
   - Cluster across regions = high latency consensus
   - Use per-region cluster + async cross-region

4. No fencing / split-brain prevention
   - Old leader continues writing
   - Data inconsistency
   - Use STONITH / consensus lock

5. No backup
   - "It's distributed, no backup needed"
   - Bug deletes all replicas → data loss
   - Always backup

6. Underestimate complexity
   - Operating distributed DB = hard
   - Consider managed service (RDS, Cloud Spanner)

7. Replication lag ignored
   - Read from replica → stale data
   - Plan UX or use leader for critical reads

24. Checkpoint

ลงมือทำเพื่อให้เข้าใจ consensus จริง ๆ — แบบฝึกหัดนี้ให้คุณดู Raft ทำงานผ่าน visualization, รัน etcd cluster จริง, ทดสอบ failover และเลือกเครื่องมือให้เหมาะกับโจทย์ ทำครบแล้วจะเห็นภาพทฤษฎีในบทนี้เป็นรูปธรรม:

🛠️ Checkpoint 2.1 — Raft Visualization
เข้าไปที่ https://raft.github.io/

ดู leader election
ลองสร้าง partition
ดูการ recover

🛠️ Checkpoint 2.2 — รัน etcd

bash

# etcd 3 node
docker run -d --name etcd1 -p 2379:2379 quay.io/coreos/etcd
# หรือทำตาม official tutorial

เขียน key แล้วอ่านจากอีก node
หยุด leader → ดู leader ใหม่ถูกเลือก

🛠️ Checkpoint 2.3 — ทดสอบ Failover
ใช้ Postgres + Patroni หรือ RDS Multi-AZ:

บังคับให้ primary ล่ม
จับเวลา failover
ตรวจสอบว่าไม่มีข้อมูลหาย

🛠️ Checkpoint 2.4 — อ่าน DDIA บทที่ 9
"Consistency and Consensus" — อ่าน + เขียนสรุป

🛠️ Checkpoint 2.5 — เลือก Tool
ออกแบบระบบ distributed สำหรับ:

บล็อกระดับโลก (อ่านเยอะ)
ธนาคาร (ต้อง strong consistency)
IoT telemetry (เขียนเยอะ, time-series)
ตะกร้าสินค้า e-commerce (eventual consistency ก็ได้)

25. สรุปบท

ทบทวนแก่นของบทนี้ — ตั้งแต่ปัญหา consensus และ FLP impossibility, algorithm หลัก (Paxos/Raft), การทำ replicated state machine, ความมหัศจรรย์ของ Spanner ไปจนถึง quorum และเครื่องมือจริง เช็กลิสต์นี้คือสิ่งที่ควรเข้าใจก่อนไปต่อ:

✅ Consensus = N nodes ตกลงค่าเดียวกันได้แม้มี failure
✅ FLP impossibility — ไม่มี consensus ที่สมบูรณ์แบบใน network async ล้วน
✅ Paxos — พิสูจน์ได้แต่ implement ยาก
✅ Raft — ออกแบบให้เข้าใจง่าย ใช้กันแพร่หลาย
✅ 3 บทบาท: Follower, Candidate, Leader
✅ Leader election ด้วยการโหวต (เสียงข้างมากชนะ)
✅ Log replication + commit เมื่อ majority ACK
✅ Spanner — strong consistency ระดับ global ด้วย TrueTime (hardware)
✅ Quorum: W + R > N ได้ strong consistency
✅ BFT สำหรับสภาพแวดล้อมที่มีศัตรู (blockchain)
✅ เครื่องมือที่ใช้ consensus: etcd, ZooKeeper, Spanner, CockroachDB
✅ Postgres HA ทำผ่าน Patroni + etcd
✅ Multi-region: แลก trade-off ระหว่าง latency กับ consistency

← บทที่ 1 | บทที่ 3 → Distributed Transactions

บทที่ 2 — Consensus + Replication ​

1. Consensus — ทำไมต้องมี ​

2. FLP Impossibility — ผลลัพธ์ทฤษฎีที่โด่งดัง ​

3. Paxos (อ่าน "แพก-ซอส") — algorithm ที่ Lamport (แลม-พอร์ต) เองยังบอกว่ายาก ​

3 บทบาท (Roles) ​

2 Phase (สำหรับ Single Value) ​

Phase 1: Prepare (จองเลขคิว / round number) ​

Phase 2: Accept (เสนอค่าจริง) ​

Trace ตัวอย่าง — 3 Acceptors ​

Trace สอง proposers ชนกัน ​

ทำไม Paxos ยากกว่า Raft? ​

4. Raft (2014, Ongaro + Ousterhout) — ⭐ (อ่าน "ราฟต์") ​

Raft Roles — 3 บทบาท ​

Raft — Leader Election (เลือกผู้นำ) ​

Raft — Log Replication (กระจาย log) ​

Raft — Safety Properties (สมบัติความปลอดภัย) ​

Visualizing Raft — ดูภาพประกอบ ​

5. Raft Step-by-Step — เดินทีละขั้น ​

สถานะเริ่มต้น ​

Election — timer ของ A หมดอายุ ​

Client Write — ลูกค้าเขียนข้อมูล ​

Network Partition — network ขาด ​

5.5 Raft at Scale — Multi-Raft (มัล-ติ-ราฟต์) + Production Optimizations ​

Multi-Raft Pattern ​

Production Optimizations ที่ Raft paper ไม่ลึก ​

Multi-Raft vs Single-Raft — เลือกตามขนาด ​

6. ทำไม Raft ถึงเป็นที่นิยม ​

7. ZooKeeper และ ZAB ​

Ephemeral Node — node ชั่วคราว ​

8. etcd กับ ZooKeeper — เทียบกัน ​

9. Use Cases — Consensus ใช้ทำอะไรได้บ้าง ​

10. Spanner — "เวทย์มนตร์ของ Google" (ที่ใช้ฮาร์ดแวร์จริงๆ) ​

ปัญหา — ทำไม global linearizable ถึงยาก ​

TrueTime — เทคนิคของ Google ​

Commit-Wait Protocol — เหตุที่ Linearizable ระดับ Global ​

ผลกระทบของ Spanner ​

Open Source Alternatives — สำหรับคนที่ไม่ใช่ Google ​

CockroachDB ​

YugabyteDB ​

TiDB ​

Comparison ​

11. Replicated State Machine — รัน state machine แบบ replicate ​

12. Byzantine Fault Tolerance (BFT) — "ถ้ามี node ที่นิสัยเสีย/โดน hack ละ?" ​

Byzantine Generals Problem (1982) — Intuition ​

ทฤษฎี — ต้องมี 3F + 1 node ​

ทำไมแพงกว่า Raft? ​

เมื่อไหร่ใช้ BFT? (ปกติ = ไม่ใช้) ​

BFT Algorithms ที่ใช้จริง ​

PBFT (Practical BFT) — 1999 ​

Tendermint — ทันสมัย ​

HotStuff — ใหม่กว่า ​

Proof of Work (Bitcoin) ​

Proof of Stake (Ethereum) ​

สรุปสำหรับมือใหม่ ​

13. Multi-Region Replication — replicate ข้าม region ​

14. Replication Mode ใน Postgres ​

15. Failover — สลับ primary เมื่อ fail ​

Patroni Architecture — เดินทีละขั้น ​

Walkthrough — ตอน operation ปกติ ​

Walkthrough — ตอน Failover ​

Split Brain Prevention — Patroni ป้องกันยังไง ​

Split Brain Prevention — เทียบหลายแนวทาง ​

Failover Time — ปรับ tuning parameters ​

16. Quorum-Based Replication — สไตล์ Cassandra (Leaderless / Dynamo-style) ​

Hinted Handoff — เก็บไว้ส่งทีหลัง ​

Read Repair — ซ่อมสด ๆ ตอน read ​

Anti-Entropy — ซ่อม background ด้วย Merkle Tree ​

17. Geo-replication Patterns — รูปแบบ replicate ข้ามภูมิภาค ​

Single Leader — ง่ายสุด ​

Multi-Leader — ซับซ้อน ​

Sharded — แบบที่ใช้บ่อย ​

18. Tools ที่ใช้ Consensus ในชีวิตจริง ​

19. Distributed Database — หมวดหมู่ ​

20. Operational Concerns — เรื่อง operation ที่ต้องคิด ​

21. ตัวอย่างจริง — etcd Walkthrough ​

22. เลือก Tool ให้ตรงงาน ​

23. Pitfalls — กับดักที่พบบ่อย ​

24. Checkpoint ​

25. สรุปบท ​

บทที่ 2 — Consensus + Replication

1. Consensus — ทำไมต้องมี

2. FLP Impossibility — ผลลัพธ์ทฤษฎีที่โด่งดัง

3. Paxos (อ่าน "แพก-ซอส") — algorithm ที่ Lamport (แลม-พอร์ต) เองยังบอกว่ายาก

3 บทบาท (Roles)

2 Phase (สำหรับ Single Value)

Phase 1: Prepare (จองเลขคิว / round number)

Phase 2: Accept (เสนอค่าจริง)

Trace ตัวอย่าง — 3 Acceptors

Trace สอง proposers ชนกัน

ทำไม Paxos ยากกว่า Raft?

4. Raft (2014, Ongaro + Ousterhout) — ⭐ (อ่าน "ราฟต์")

Raft Roles — 3 บทบาท

Raft — Leader Election (เลือกผู้นำ)

Raft — Log Replication (กระจาย log)

Raft — Safety Properties (สมบัติความปลอดภัย)

Visualizing Raft — ดูภาพประกอบ

5. Raft Step-by-Step — เดินทีละขั้น

สถานะเริ่มต้น

Election — timer ของ A หมดอายุ

Client Write — ลูกค้าเขียนข้อมูล

Network Partition — network ขาด

5.5 Raft at Scale — Multi-Raft (มัล-ติ-ราฟต์) + Production Optimizations

Multi-Raft Pattern

Production Optimizations ที่ Raft paper ไม่ลึก

Multi-Raft vs Single-Raft — เลือกตามขนาด

6. ทำไม Raft ถึงเป็นที่นิยม

7. ZooKeeper และ ZAB

Ephemeral Node — node ชั่วคราว

8. etcd กับ ZooKeeper — เทียบกัน

9. Use Cases — Consensus ใช้ทำอะไรได้บ้าง

10. Spanner — "เวทย์มนตร์ของ Google" (ที่ใช้ฮาร์ดแวร์จริงๆ)

ปัญหา — ทำไม global linearizable ถึงยาก

TrueTime — เทคนิคของ Google

Commit-Wait Protocol — เหตุที่ Linearizable ระดับ Global

ผลกระทบของ Spanner

Open Source Alternatives — สำหรับคนที่ไม่ใช่ Google

CockroachDB

YugabyteDB

TiDB

Comparison

11. Replicated State Machine — รัน state machine แบบ replicate

12. Byzantine Fault Tolerance (BFT) — "ถ้ามี node ที่นิสัยเสีย/โดน hack ละ?"

Byzantine Generals Problem (1982) — Intuition

ทฤษฎี — ต้องมี 3F + 1 node

ทำไมแพงกว่า Raft?

เมื่อไหร่ใช้ BFT? (ปกติ = ไม่ใช้)

BFT Algorithms ที่ใช้จริง

PBFT (Practical BFT) — 1999

Tendermint — ทันสมัย

HotStuff — ใหม่กว่า

Proof of Work (Bitcoin)

Proof of Stake (Ethereum)

สรุปสำหรับมือใหม่

13. Multi-Region Replication — replicate ข้าม region

14. Replication Mode ใน Postgres

15. Failover — สลับ primary เมื่อ fail

Patroni Architecture — เดินทีละขั้น

Walkthrough — ตอน operation ปกติ

Walkthrough — ตอน Failover

Split Brain Prevention — Patroni ป้องกันยังไง

Split Brain Prevention — เทียบหลายแนวทาง

Failover Time — ปรับ tuning parameters

16. Quorum-Based Replication — สไตล์ Cassandra (Leaderless / Dynamo-style)

Hinted Handoff — เก็บไว้ส่งทีหลัง

Read Repair — ซ่อมสด ๆ ตอน read

Anti-Entropy — ซ่อม background ด้วย Merkle Tree

17. Geo-replication Patterns — รูปแบบ replicate ข้ามภูมิภาค

Single Leader — ง่ายสุด

Multi-Leader — ซับซ้อน

Sharded — แบบที่ใช้บ่อย

18. Tools ที่ใช้ Consensus ในชีวิตจริง

19. Distributed Database — หมวดหมู่

20. Operational Concerns — เรื่อง operation ที่ต้องคิด

21. ตัวอย่างจริง — etcd Walkthrough

22. เลือก Tool ให้ตรงงาน

23. Pitfalls — กับดักที่พบบ่อย

24. Checkpoint

25. สรุปบท