Merkle anti-entropy และ gossip/SWIM membership — ตามกันให้ทันแบบ sub-linear
ห้าบทที่ผ่านมาเราประกอบชิ้นส่วนของ cluster ครบเกือบหมด: vector clock บอกลำดับเชิงเหตุผล (บท 1), consistent hashing วาง key ลง node (บท 2), quorum + read-repair ทำให้อ่านทับเขียนล่าสุด (บท 3), และ CRDT ที่ merge กันแล้วลู่เข้าเองโดยไม่ต้อง coordinate (บท 4–5) แต่ read-repair ซ่อมได้เฉพาะ key ที่ มีคนอ่าน เท่านั้น — key ที่ไม่มีใครแตะเลยหลัง partition หายจะ ดริฟต์ค้างไว้อย่างนั้น ไปเรื่อยๆ บทนี้เติมชิ้นสุดท้ายก่อนไปประกอบร่างเป็น cluster จริง: กระบวนการ เบื้องหลัง ที่ให้ replica เทียบสถานะกันเองแล้ว sync ส่วนที่ต่างจนลู่เข้า — เรียกว่า anti-entropyanti-entropyกระบวนการเบื้องหลังที่ให้ replica เทียบสถานะแล้ว sync ส่วนที่ต่างกันจนลู่เข้ากัน
คำถามที่ต้องตอบมีสองข้อ (1) จะรู้ได้อย่างไรว่า replica สองตัว ต่างกันตรงไหน โดยไม่ต้องส่งทั้ง store มาเทียบทีละ key — คำตอบคือ Merkle tree ที่หาช่วง key ที่ diverge แบบ sub-linear (2) จะ กระจาย ข่าว (ค่าที่อัปเดต, ใครเข้า/ออก cluster) ให้ทั่วทั้ง N node อย่างทนทานได้อย่างไร — คำตอบคือ gossip แบบ epidemic ที่ครบทุก node ใน O(log N) รอบ ทั้งสองคือกลไกจริงของ Dynamo/Cassandra/Riak ปิดท้ายด้วยเส้น scope: การ ตรวจเจ๊ง (failure detection) ของ SWIM ที่ผูกกับ timing จริง เราคงไว้เป็น ไดอะแกรม ไม่ลง code — เหตุผลอยู่ท้ายบท
คอร์สนี้ ต่อยอด repo kaen-kvstore จาก #22 (code ตัวอย่างกำลังจัดทำ) — บทนี้เพิ่มชั้น anti-entropy เบื้องหลัง ให้แต่ละ replica ของ kaen-kvstore: Merkle tree สร้างเหนือ key-space ของ store (leaf = ช่วง key ที่ติดกัน, hash ด้วย std DefaultHasher) เพื่อหา segment ที่ต่างแล้ว sync เฉพาะส่วนนั้น, และ gossip กระจาย membership view ระหว่าง node ทั้งหมด Rust std ล้วน — ไม่มี serde, ไม่มี tokio, ไม่มี proptest ความสุ่มมาจาก splitmix64 ที่เขียนเอง (seed ซ้ำได้ 100%) ในบท 8 ชิ้นนี้จะกลายเป็น anti-entropy loop ที่ซ่อม key ที่ read-repair เอื้อมไม่ถึง
ทุก snippet pin ที่ Rust stable 1.97.1 (ออก 2026-07-16) และ edition = “2024” [dependencies] ว่างเปล่า — ZERO external crate code ในบทนี้แตะ std เพียง std::collections::BTreeMap (จำเป็น: ให้ leaf feed แบบเรียง key = byte-canonical) กับ std::hash (DefaultHasher, Hash, Hasher) เท่านั้น ทุกโปรแกรม compile zero-warnings (-D warnings) และ รันจริง บน musl — เลขทุกตัวด้านล่างคือ output จริงที่ seed ล็อกไว้ รันซ้ำได้ byte-identical (ยืนยันแล้ว: รัน merkle สองครั้งได้ md5 เดียวกัน)
ปัญหา: replica ดริฟต์ห่างกัน แต่เทียบทุก key คือ O(keys)
หัวข้อที่มีชื่อว่า “ปัญหา: replica ดริฟต์ห่างกัน แต่เทียบทุก key คือ O(keys)”หลัง partition หายหรือหลัง node รีบูตกลับมา replica สองตัวที่ ควร เก็บ key ชุดเดียวกันอาจต่างกันไม่กี่ key จากทั้งหมดเป็นล้าน วิธีดิบที่สุดคือส่งทั้ง key-space มาเทียบทีละตัว — นั่นคือ O(keys) ทั้ง bandwidth และเวลา ต่อให้ต่างกันแค่ key เดียว ก็ยังต้องขนทั้ง store มากอง version ดิบแบบนี้ใช้ไม่ได้บน cluster จริงที่ต้องทำ anti-entropy วนทุก node ตลอดเวลา
สิ่งที่เราต้องการคือ “บอกได้เร็วๆ ว่าต่างกันไหม และถ้าต่าง ต่างตรงช่วงไหน” โดยจ่ายค่าใช้จ่ายเป็นสัดส่วนกับ ปริมาณที่ต่าง ไม่ใช่ ขนาดทั้งหมด — นี่คือสิ่งที่ Merkle tree ให้
Merkle tree: ต้นไม้ hash ที่เทียบ root ก่อน
หัวข้อที่มีชื่อว่า “Merkle tree: ต้นไม้ hash ที่เทียบ root ก่อน”Merkle treeMerkle treeต้นไม้ hash ที่เทียบ root แล้วลงเฉพาะ subtree ที่ต่าง หาช่วง key ที่ diverge แบบ sub-linear (Merkle, CRYPTO 1987) คือต้นไม้ที่ ใบ (leaf) เก็บ hash ของข้อมูลจริง และ node ภายใน เก็บ hash ของลูกทั้งสอง ไล่ขึ้นไปจนถึง root ที่เป็น hash สรุปของทั้งต้น คุณสมบัติที่ใช้ประโยชน์คือ: ถ้า root ของสองต้น เท่ากัน แสดงว่าทั้งต้นเหมือนกัน (ภายใต้ collision resistance ของ hash) — จบใน 1 การเทียบ; ถ้า root ต่างกัน เรารู้ว่ามีอะไรต่าง แล้ว ลงเฉพาะ subtree ที่ hash ต่าง เท่านั้น subtree ที่ hash ตรงกันตัดทิ้งได้ทั้งดุ้นโดยไม่ต้องแตะข้างใน
เราวางต้นไม้แบบ heap ใน Vec<u64> ตัวเดียว: tree[1] = root, node ภายในอยู่ช่วง [1, LEAVES), ใบอยู่ช่วง [LEAVES, 2*LEAVES) ลูกของ node i คือ 2*i กับ 2*i+1 — ไม่ต้องมี pointer เลย ให้ KEYSPACE = 4096, LEAVES = 64 (เป็นกำลังของสอง → ต้นไม้สมบูรณ์ ลึก log2(64) = 6) แต่ละใบดูแลช่วง key ที่ติดกัน 64 key และ hash ของใบคือ hash ของคู่ (key, value) ที่เรียงตาม key — จุดนี้สำคัญ: ต้อง feed แบบเรียง (ผ่าน BTreeMap ที่ iterate ตามลำดับ key) มิฉะนั้น replica สองตัวที่ เหมือนกัน แต่ feed คนละลำดับจะได้ hash คนละค่า แล้วดูเหมือนต่างทั้งที่ไม่ต่าง
use std::collections::hash_map::DefaultHasher;use std::collections::BTreeMap;use std::hash::{Hash, Hasher};
const KEYSPACE: u64 = 4096; // keys are 0..KEYSPACEconst LEAVES: usize = 64; // power of two -> perfect binary tree, depth 6
// contiguous range: which leaf does a key fall intofn leaf_of(key: u64) -> usize { (key * LEAVES as u64 / KEYSPACE) as usize}
fn hash_pair(a: u64, b: u64) -> u64 { let mut h = DefaultHasher::new(); a.hash(&mut h); b.hash(&mut h); h.finish()}
// Heap-laid-out Merkle tree: index 1 = root, leaves at [LEAVES .. 2*LEAVES).// Leaf hash = hash of sorted (key,value) pairs in that leaf's range.fn build_tree(store: &BTreeMap<u64, u64>) -> Vec<u64> { let mut leaf_hashers: Vec<DefaultHasher> = (0..LEAVES).map(|_| DefaultHasher::new()).collect(); // feed each (key,value) into its leaf, in key order (BTreeMap iterates sorted) for (&k, &v) in store.iter() { let l = leaf_of(k); k.hash(&mut leaf_hashers[l]); v.hash(&mut leaf_hashers[l]); } let mut tree = vec![0u64; 2 * LEAVES]; for i in 0..LEAVES { tree[LEAVES + i] = leaf_hashers[i].finish(); } for i in (1..LEAVES).rev() { tree[i] = hash_pair(tree[2 * i], tree[2 * i + 1]); } tree}ต่อด้วยหัวใจของ anti-entropy: diff_tree ที่เริ่มจาก root แล้ว ลงเฉพาะ subtree ที่ต่าง — เราใช้ stack ของ index node แทน recursion และนับจำนวน “การเทียบ hash ต่อ node” (node-hash compares) เพื่อวัดค่าใช้จ่ายจริง:
// Recurse from root, descending only into differing subtrees.// Returns (differing leaf indices, count of node-hash comparisons performed).fn diff_tree(a: &[u64], b: &[u64]) -> (Vec<usize>, usize) { let mut differing_leaves = Vec::new(); let mut compares = 0usize; let mut stack = vec![1usize]; // start at root (index 1) while let Some(i) = stack.pop() { compares += 1; if a[i] == b[i] { continue; // subtree identical -> prune (this is the O(log) win) } if i >= LEAVES { differing_leaves.push(i - LEAVES); } else { stack.push(2 * i); stack.push(2 * i + 1); } } differing_leaves.sort_unstable(); (differing_leaves, compares)}บรรทัด if a[i] == b[i] { continue; } คือทั้งหมดของกำไร: เจอ subtree ที่ hash ตรง = ตัดทิ้งลูกหลานทั้งกอ ไม่แตะ key แม้แต่ตัวเดียว ที่อยู่ข้างใน เมื่อได้ใบที่ต่างมาแล้ว เราค่อยเปิดดู เฉพาะช่วง key ในใบเหล่านั้น ว่า key ตัวไหนต่างจริง (keys_in_leaves) แล้วเทียบกับ oracle ที่สแกนเต็ม (ground_truth_diff) — code 2 function นี้ตรงไปตรงมา (เดิน range ของแต่ละใบ / เดินทั้ง store) จึงขอข้ามมาดูผลรัน
กำไรจริง: key เดียวใน 4096 เจอด้วยการเทียบ 13 ครั้ง
หัวข้อที่มีชื่อว่า “กำไรจริง: key เดียวใน 4096 เจอด้วยการเทียบ 13 ครั้ง”test รูปธรรมที่สุด: store ที่มีครบ 4096 key เหมือนกันเป๊ะ ต่างกันแค่ key เดียว (b.insert(2718, 999999)) ต้นไม้ลึก 6 การหาใบที่ต่าง ใบเดียว ต้องเทียบ root (1 ครั้ง) แล้วที่แต่ละชั้นลงไปเทียบ ทั้งลูกซ้ายและลูกขวา (ลูกที่ตรงตัดทิ้ง ลูกที่ต่างลงต่อ) รวม 1 + 2*6 = 13 การเทียบ — เทียบกับ 4096 ถ้าสแกนทุก key:
graph TD
R["root — เทียบก่อน: ต่าง!"]
R --> A["subtree ซ้าย: hash ตรง ✓ ตัดทิ้ง ~2048 key"]
R --> B["subtree ขวา: hash ต่าง → ลงต่อ"]
B --> B1["ลูกหนึ่ง: ตรง ✓ ตัดทิ้ง"]
B --> B2["อีกลูก: ต่าง → ลงต่อ"]
B2 --> D["...ลงตามชั้นจนถึง..."]
D --> L["leaf 42: ช่วง key 2688–2751 — key 2718 ต่าง"]
คำบรรยายภาพ: เทียบ root ก่อน แล้วลงเฉพาะ subtree ที่ต่าง — subtree ที่ hash ตรง (สีเทา) ถูกตัดทิ้งทั้งกอ ไม่แตะ ~4032 key ที่เหมือนกันเลย ทางสีแดง root→leaf คือเส้นเดียวที่เราเดินลงไปจริง จบที่ leaf 42 ซึ่งครอบ key 2718
รันจริงบน musl ได้ตามนี้:
=== MERKLE ANTI-ENTROPY ===KEYSPACE=4096, LEAVES=64 (tree depth = log2 = 6)property test: 2000 seeded trials, mismatches = 0seed 7: 3 divergent keys, 2 of 64 leaves differ, 23 node-hash compares (full-tree = 127 nodes)worst-case node-hash compares over all trials = 109single-key divergence in 4096-key space: found=[2718], leaves-differing=1, node-hash compares=13 (vs 4096 keys if we scanned everything)RESULT: OK — diff flags exactly the divergent keys; transfer is O(differing_leaves * log LEAVES), not O(keys).found=[2718] และ node-hash compares=13 — ต้นไม้ชี้ตรงไปที่ key เดียวที่ต่าง โดยเทียบ hash แค่ 13 ครั้ง ไม่ใช่ 4096
property test: diff ตรงกับ oracle เป๊ะ — และความจริงของ “O(log)”
หัวข้อที่มีชื่อว่า “property test: diff ตรงกับ oracle เป๊ะ — และความจริงของ “O(log)””การหาใบที่ต่างถูกต้อง เป๊ะ หมายความว่า: ชุด key ที่ Merkle diff รายงาน ต้องเท่ากับ symmetric difference จริงของ2 store ทุกครั้ง ไม่ขาด (false negative) ไม่เกิน (false positive) เราพิสูจน์ด้วย property test 2000 trial: แต่ละ trial สร้าง store พื้นฐานแล้วสุ่ม mutate อีกฝั่งด้วยจำนวนการเปลี่ยน 0–39 ครั้ง (เพิ่ม/แก้/ลบ) แล้วยืนยันว่า keys_in_leaves(diff) == ground_truth_diff — ผลคือ mismatches = 0 seed แต่ละ trial derive จาก seed * 0x2545F4914F6CDD1D ^ 0x123456789ABCDEF0 (พิมพ์ seed = repro handle)
แต่ตรงนี้ต้องพูดความจริง “O(log)” เป็นจริงเฉพาะตอนที่ความต่าง กระจุก (ใบไม่กี่ใบ) ค่าใช้จ่ายจริงคือ O(differing_leaves × log LEAVES) ไม่ใช่ O(log) เฉยๆ ดูสองบรรทัดในผลรัน: seed 7 มี 3 key ต่างที่ตกอยู่ 2 ใบ → 23 การเทียบ (ยังถูกกว่า 127 มาก); แต่ worst-case = 109 จาก 127 node ทั้งต้น — trial ที่ความต่าง กระจาย ไปเกือบทุกใบทำให้ Merkle เกือบเสื่อมเป็นการสแกนเต็ม นี่คือธรรมชาติของมัน: มันเร็วเมื่อ replica ใกล้ตรงกัน (ซึ่งเป็นกรณีปกติของ anti-entropy วนบ่อยๆ) และไม่ได้วิเศษเมื่อทั้งคู่ต่างกันมหาศาล
13, 23, 109 และ hash ทุกค่าในต้นไม้ reproduce ได้ ก็เพราะ เราใช้ DefaultHasher::new() ของ std (SipHash-1-3, fixed keys — ไม่ใช่ RandomState ของ HashMap ที่สุ่ม seed ต่อ process) และ feed ใบแบบเรียง key ผ่าน BTreeMap ถ้าใช้ RandomState เป็น hasher ของใบ replica ที่ เหมือนกันเป๊ะ จะได้ root คนละค่าแล้วดูเหมือน diverge ทั้งที่ไม่ — anti-entropy จะขน store มาเทียบมั่วตลอด เช่นเดียวกับบท 2 std เตือนว่า algorithm ของ DefaultHasher “ไม่รับประกันคงที่ข้าม version” — เลขชุดนี้จึง pin กับ Rust 1.97.1 การ เทียบ ไม่พังข้าม version (สองฝั่งใช้ hasher เดียวกัน) แต่ ตัวเลข จะเลื่อนได้
gossip: กระจายข่าวแบบ epidemic ใน O(log N) รอบ
หัวข้อที่มีชื่อว่า “gossip: กระจายข่าวแบบ epidemic ใน O(log N) รอบ”Merkle บอกว่า ต่างตรงไหน แต่ยังต้อง กระจาย ค่าที่อัปเดต (และข่าวสมาชิกภาพ: ใครเข้า ใครออก ใครสงสัยว่าเจ๊ง) ให้ทั่ว cluster วิธีที่ทนทานที่สุดคือ gossipgossipการกระจายข่าวแบบระบาด (epidemic): แต่ละ node สุ่มบอกเพื่อน ๆ ครบทั้ง N ใน O(log N) รอบ — การกระจายแบบ ระบาด (epidemic, Demers et al. PODC 1987): แต่ละ node ที่ “รู้ข่าวแล้ว” สุ่มบอกเพื่อน fanout ตัวต่อรอบ เหมือนไวรัสแพร่ ไม่มีตัวกลาง ไม่มีลำดับตายตัว — node ล้มไปบ้างก็ยังกระจายต่อได้ ทฤษฎีบอกว่าข่าวเดียวถึงครบทั้ง N node ใน O(log N) รอบ
เราจำลอง membership view: ทุก node เริ่มเชื่อว่า peer เป้าหมาย {incarnation: 1, alive: true} แล้ว ฉีดอัปเดตหนึ่งตัว ที่ node เดียว ({incarnation: 2, alive: false} — “peer นี้ถูกตั้งเป็น suspect ที่ incarnation 2”) จากนั้นรัน push-gossip จนทุก node เห็นตรงกัน disseminate มี hard round cap = 200 เป็นเพดานตายตัว: harness ค้างไม่ได้เด็ดขาด แม้ config จะไม่ยอมลู่เข้า (compiler จับ deadlock ไม่ได้ — เพดานนี้คือกันชนที่ต้องมีทุกครั้ง)
// One entry of a node's view of some peer's status.#[derive(Clone, Copy, PartialEq, Eq, Debug)]struct Status { incarnation: u64, alive: bool, // false = suspect/dead (dead wins ties, monotone)}
// Semilattice merge (commutative, associative, idempotent): take the newer fact.fn merge(a: Status, b: Status) -> Status { if a.incarnation != b.incarnation { if a.incarnation > b.incarnation { a } else { b } } else { // tie on incarnation -> "dead" (alive=false) dominates: suspicion is monotone Status { incarnation: a.incarnation, alive: a.alive && b.alive } }}
// Run one dissemination, return rounds-to-converge (or None if it hit the cap).// Every node that knows the update contacts `fanout` random peers this round and// pushes the fact; contacted peers merge it in (epidemic push).fn disseminate(n: usize, fanout: usize, round_cap: usize, seed: u64) -> Option<usize> { let old = Status { incarnation: 1, alive: true }; let new = Status { incarnation: 2, alive: false }; // the injected update let mut view = vec![old; n]; view[0] = merge(view[0], new); // inject at node 0 only
let mut rng = seed ^ 0xD1B54A32D192ED03; for round in 1..=round_cap { // snapshot who knows BEFORE this round (push based on this-round state) let knows_before: Vec<bool> = view.iter().map(|s| *s == new).collect(); for i in 0..n { if !knows_before[i] { continue; // only informed nodes gossip } for _ in 0..fanout { let peer = (splitmix64(&mut rng) % n as u64) as usize; view[peer] = merge(view[peer], view[i]); } } if view.iter().all(|s| *s == new) { return Some(round); } } None}หมายเหตุ: splitmix64(&mut rng) ที่เรียกใน loop คือ PRNG แบบ hand-rolled ตัวเดียวกับที่นิยามไว้ในบท 1 (define-once-reuse — ไม่กาง code ซ้ำที่นี่) seed คงที่จึงรันซ้ำได้ byte-identical
กวาด N แบบ log-spaced แล้วเฉลี่ยรอบต่อ 200 seed (fanout = 3) ได้ตารางนี้:
=== GOSSIP / SWIM DISSEMINATION ===merge = semilattice (max incarnation; dead wins ties). push-gossip, fanout=3.
N | log2(N) | avg rounds | max rounds 10 | 3.32 | 3.27 | 6 32 | 5.00 | 4.37 | 6 100 | 6.64 | 5.64 | 7 316 | 8.30 | 7.02 | 9 1000 | 9.97 | 8.21 | 11 3162 | 11.63 | 9.31 | 11 10000 | 13.29 | 10.56 | 13จำนวนรอบเฉลี่ยเดินตาม log2(N) เกือบเป๊ะ (จริงๆ ต่ำกว่าเล็กน้อยเพราะ fanout 3 ไม่ใช่ 1) — N โต 1000 เท่า (10 → 10000) รอบเพิ่มแค่ราว 3 เท่า (3.27 → 10.56) นี่คือ เหตุผล ที่ gossip สเกลได้: ค่าใช้จ่ายในการกระจายโตแบบ logarithmic ไม่ใช่ linear
“O(log N)” เป็นจริง แต่ ค่าคงที่ ขึ้นกับ fanout และรูปแบบ (push / pull / push-pull): push fanout-1 ล้วน ≈ log₂N + ln N (Pittel 1987), push-pull ≈ log₃N เราวัด fanout-3 push ได้ตัวเลขข้างบน — รายงานเลขที่วัดจริงพร้อม model ไม่ใช่ยกทฤษฎีมาอ้างลอยๆ
membership merge = monotone semilattice — view เดินหน้าทางเดียว
หัวข้อที่มีชื่อว่า “membership merge = monotone semilattice — view เดินหน้าทางเดียว”สังเกต merge ของ Status: มันคือ join ของ semilattice ตัวเดิมจากบท 1/4 — เอา incarnation ที่มากกว่าเป็นหลัก, เสมอกันให้ alive = a.alive && b.alive (dead/suspect ชนะ) กติกานี้ทำให้ view เดินหน้าทางเดียว (monotone): สถานะที่ merge เข้ามาไม่เคยทำให้ node “ย้อนกลับ” ไปคิดว่า peer ที่ตายแล้วยังมีชีวิต การ bump incarnation คือวิธี “ลบล้าง” ข่าวเก่า (peer ที่ถูกหาว่าตายแต่จริงๆ ยังอยู่ ก็ bump incarnation ตัวเองประกาศว่า “ฉันยังอยู่ version ใหม่กว่า”)
เพราะ merge เป็น semilattice (commutative + associative + idempotent) การกระจายแบบ gossip ที่ลำดับมั่ว ส่งซ้ำ ส่งซ้อน จึงไม่มีผลต่อค่าปลายทาง — node ที่เห็นชุดข่าวเดียวกัน (ลำดับใดก็ได้) ลู่เข้าสถานะเดียวกันเสมอ โดยไม่ต้อง coordinate เราพิสูจน์ property + กฎ merge:
property test: 3000 seeded runs (N=8..507), non-converged = 0round-cap sweep hit cap (any_fail) = falsemerge laws: commutative + associative + idempotent — verified over 5000 seeded triples.RESULT: OK — one injected update reaches all N nodes; rounds grow ~log2(N) (epidemic bound).non-converged = 0 จาก 3000 run (N สุ่ม 8–507) — ทุก config ลู่เข้าภายใน cap; any_fail = false — ไม่มี run ไหนชน round cap เลย; และกฎ semilattice ทั้งสามผ่าน 5000 triple (domain ของ Status มีแค่ 8 ค่า → 5000 ครอบคลุมแทบครบทุกความเป็นไปได้)
SWIM: แยก “ตรวจเจ๊ง” ออกจาก “กระจายข่าว” — และเส้น scope
หัวข้อที่มีชื่อว่า “SWIM: แยก “ตรวจเจ๊ง” ออกจาก “กระจายข่าว” — และเส้น scope”protocol จริงที่รวมสองส่วนนี้เข้าด้วยกันคือ SWIMSWIMprotocol membership: แยก 'ตรวจเจ๊ง' (ping/ping-req + incarnation) ออกจาก 'กระจายข่าว' (gossip) (Das, Gupta, Motivala, DSN 2002) หัวใจของ SWIM คือ แยก งานสองอย่างออกจากกันชัดเจน: failure DETECTION (ตรวจว่า node ไหนเจ๊ง) กับ DISSEMINATION (กระจายผลให้ทั่ว) — ส่วน dissemination + membership merge คือสิ่งที่เราลง code รันจริงไปแล้วข้างบน แต่ส่วน detection ผูกกับ timing จริง และนั่นคือจุดที่เส้น scope ของคอร์สลากผ่าน
SWIM ตรวจเจ๊งด้วยจังหวะเวลา: node A ping node B แล้ว รอ timeout; ถ้า B เงียบ A ส่ง ping-req(B) ให้ node พยานช่วยลอง ping แทน (กันเน็ตขาดเฉพาะคู่ A–B); ถ้ายังเงียบ A ตั้ง B เป็น suspect แล้วให้ gossip พา incarnation number ไปกระจาย ก่อนจะ ยืนยันว่าตาย หลังเวลาผ่านไปอีกช่วง
sequenceDiagram
participant A as node A
participant B as node B
participant C as node พยาน
A->>B: ping แล้วรอ timeout
Note over A,B: B ไม่ตอบภายในเวลา
A->>C: ping-req(B) — ฝากพยานลอง ping แทน
C->>B: ping (ยังเงียบ)
Note over A,B: A ตั้ง B = suspect แล้ว bump incarnation
Note over A,C: กระจาย suspect ผ่าน gossip — ส่วนนี้เท่านั้นที่ลง code
คำบรรยายภาพ: SWIM แยก detection (ping/ping-req/suspicion ตามจังหวะเวลา — ไดอะแกรมเท่านั้น) ออกจาก dissemination (gossip + membership merge — ลง code รันจริงข้างบน) กล่องซ้ายของแผนภาพผูกกับ wall-clock timeout จึงพิสูจน์ในเครื่องเดียวไม่ได้
C — ดีเทอร์มินิสซึมคือวินัย: dissemination + merge เรา เอ็นนิวเมอเรตด้วย property test ได้ (5000 triple ครอบ domain 8 ค่า, 3000 run ลู่เข้าครบ) เพราะมันคือ semilattice บน state คงที่ — seed คงที่ + splitmix64 + hard round cap ทำให้รันซ้ำได้และค้างไม่ได้ แต่ failure detection ของ SWIM ตัดสินจาก timeout เทียบ wall-clock — “B ตอบช้าเพราะเน็ตหน่วง” กับ “B ตายจริง” แยกจากกันไม่ได้ในเครื่องเดียว เพราะไม่มี partition/หน่วง/skew จริงให้ reproduce; green test ของ detection จึงเป็นคำโกหก เราจึงคงมันเป็น ไดอะแกรม
A — Rust พิสูจน์ความถูกต้อง “ในเครื่องเดียว” ไม่ใช่ “แบบกระจาย”: property test ที่ผ่าน (2000 Merkle trial, 3000 gossip run) คือ ออราเคิล ของสมบัติแบบกระจาย และมันคือการ ตรวจแบบมีขอบเขต ไม่ใช่บทพิสูจน์ (FLP 1985) — ผ่านแปลว่าสำรวจเฉพาะ interleaving ที่ seed เดินไปถึง
D — นี่คือกลไกจริงของ Dynamo/Cassandra/Riak: Merkle anti-entropy คือกลไก sync replica จริงของ Dynamo, gossip membership คือของ Cassandra/Riak เราสอน ตรงตามต้นฉบับ ที่สเกล toy บน kaen-kvstore ไม่ใช่ของกุขึ้นเพื่อสอน
สรุปก่อนไปต่อ
หัวข้อที่มีชื่อว่า “สรุปก่อนไปต่อ”บทนี้เติมชั้น anti-entropy เบื้องหลัง ให้ cluster: Merkle treeMerkle treeต้นไม้ hash ที่เทียบ root แล้วลงเฉพาะ subtree ที่ต่าง หาช่วง key ที่ diverge แบบ sub-linear เหนือ key-space (leaf = ช่วง key ที่ติดกัน hash ด้วย DefaultHasher แบบเรียง, node ใน = hash ของลูก) ให้เราเทียบ root ก่อน แล้วลงเฉพาะ subtree ที่ต่าง — key เดียวใน 4096 เจอด้วยการเทียบ hash 13 ครั้ง, diff ตรงกับ oracle เป๊ะทุก 2000 trial (mismatches=0) แต่ค่าใช้จ่ายจริงคือ O(differing_leaves × log LEAVES) เร็วเมื่อ replica ใกล้ตรงกัน (worst-case 109/127 เมื่อความต่างกระจาย) — และเลขทุกตัว pin กับ DefaultHasher fixed-key + Rust 1.97.1; gossipgossipการกระจายข่าวแบบระบาด (epidemic): แต่ละ node สุ่มบอกเพื่อน ๆ ครบทั้ง N ใน O(log N) รอบ แบบ epidemic กระจายข่าวถึงครบทุก node ใน O(log N) รอบ (วัดจริง fanout-3: N=10 → 3.27, N=10000 → 10.56) โดย membership merge เป็น monotone semilattice (max incarnation, tie → dead ชนะ) ที่ลู่เข้าเองไม่ต้อง coordinate — กฎ merge ผ่าน 5000 triple, ลู่เข้าครบทุก 3000 run ภายใน hard round cap; และ SWIMSWIMprotocol membership: แยก 'ตรวจเจ๊ง' (ping/ping-req + incarnation) ออกจาก 'กระจายข่าว' (gossip) แยก detection (timing — ไดอะแกรมเท่านั้น) ออกจาก dissemination (code ที่รันจริง) ทุก snippet compile zero-warnings บน std ล้วน + splitmix64 รันซ้ำได้ byte-identical
บท 7 เราสร้าง harness ฉีด partition: เรามีชิ้นส่วนครบแล้ว — clock, hashing, quorum, CRDT, anti-entropy บทหน้าเราจะสร้าง harness แบบดีเทอร์มินิสติก (Jepsen-lite) ที่ฉีด partition เข้าไปจริงๆ ด้วย single-scheduler + seed คงที่ + hard timeout แล้วยืนยันสมบัติการลู่เข้า พร้อม linearizability checker ที่บอกตรงๆ ว่า quorum+LWW ของเรา ไม่ linearizable — ก่อนประกอบทุกอย่างเป็น cluster จริงในบท 8
บทนี้อิงต้นทางที่ลงวันที่กำกับ อ่านต่อได้โดยตรง:
- Ralph C. Merkle — “A Digital Signature Based on a Conventional Encryption Function” (CRYPTO 1987) (เข้าถึง 2026-07-24) — ต้นกำเนิดของ hash tree: เทียบ root ก่อน ลงเฉพาะ subtree ที่ต่าง หาส่วนที่ diverge แบบ sub-linear
- Giuseppe DeCandia et al. — “Dynamo: Amazon’s Highly Available Key-value Store” (SOSP 2007) (เข้าถึง 2026-07-24) — Dynamo ใช้ Merkle tree ทำ anti-entropy ระหว่าง replica และ gossip กระจาย membership: stack จริงที่บทนี้ย่อสเกลลงมา
- Das, Gupta, Motivala — “SWIM: Scalable Weakly-consistent Infection-style Process Group Membership Protocol” (DSN 2002) (เข้าถึง 2026-07-24) — แยก failure detection (ping/ping-req/suspicion — timing, ไดอะแกรมเท่านั้น) ออกจาก dissemination (gossip — ลง code) และ incarnation number ที่ทำให้ membership merge เป็น monotone
- Demers et al. — “Epidemic Algorithms for Replicated Database Maintenance” (PODC 1987) (เข้าถึง 2026-07-24) — gossip แบบ infection-style ถึงครบทุก node ใน O(log N) รอบ
- Boris Pittel — “On Spreading a Rumor” (SIAM J. Appl. Math., 1987) (เข้าถึง 2026-07-24) — ค่าคงที่ของการแพร่ข่าวว่าขึ้นกับ model: push fanout-1 ≈ log₂N + ln N (ที่มาของคำเตือนเรื่องอย่า overclaim ค่าคงที่)
- Rust std —
std::collections::hash_map::DefaultHasher(เข้าถึง 2026-07-24) — SipHash-1-3, fixed keys (deterministic ต่างจากRandomState); algorithm “ไม่รับประกันคงที่ข้าม version” จึง pin เลข Merkle กับ Rust 1.97.1
เช็กความเข้าใจ — บทที่ 6
ข้อ 1 / 3ทำไมการหา key ที่ diverge ด้วย Merkle tree ถึงเป็น sub-linear เมื่อความต่างกระจุก และค่าใช้จ่ายจริงคืออะไร?