Capstone — cluster kaen-kvstore หลาย replica บน std::net: quorum + CRDT + consistent-hash

เจ็ดบทที่ผ่านมาเราสร้างชิ้นส่วนไว้ครบแล้ว: vector clock (บท 1) ไว้ตรวจว่า write สองอันเป็นลำดับกันหรือ concurrent; consistent hashing (บท 2) ไว้ตอบว่า key ควรอยู่ replica ไหน; quorum W+R>N + read-repair (บท 3) ไว้การันตีว่าอ่านทับเขียนล่าสุดเสมอ; CRDT กับกฎ merge แบบ semilattice (บท 4–5) ไว้ให้ replica ลู่เข้าหาค่าเดียวกันโดยไม่ต้อง coordinate; Merkle + gossip anti-entropy (บท 6) ไว้ sync ส่วนที่ต่าง; และ harness ฉีด partition แบบดีเทอร์มินิสติก (บท 7) ไว้ยืนยันสมบัติที่ compiler มองไม่เห็น

บทนี้คือ การประกอบร่าง — เอาทุกชิ้นมาต่อกันเป็น replicated cluster เดียวที่รันได้จริง: N replica ของ kaen-kvstore คุยกันบน std::net แต่ละ key เก็บสำเนาไว้หลายที่แล้วยังลู่เข้าหาค่าเดียวกันได้แม้เครือข่ายจะขาด นี่คือนิยามของสองคำที่เป็นหัวใจของบท: replication (เก็บสำเนาของ key เดียวกันไว้หลาย replica แล้วทำให้ทุกสำเนาเห็นตรงกัน) และ eventual consistency (ถ้าหยุดเขียนสักพัก ทุก replica จะลู่เข้าเป็นค่าเดียวกัน ในที่สุด — ไม่รับประกัน “ตอนนี้”)

📦 kaen-kvstore

บทนี้ ต่อยอด repo kaen-kvstore จาก #22 (code ตัวอย่างกำลังจัดทำ) เป็นบทปิด — เราประกอบทุกชั้นที่สร้างมาตลอด 8 บทเข้าเป็น cluster เดียว: N replica ของ store เดิม (log + write→fsync→ack + hash index + immutable segment ของ #22) คุยกันผ่าน wire แบบ length-prefixed ของ #22 (write_frame/read_frame, ไม่มี serde) #23 แขวน replication/quorum/version-vector/anti-entropy ทับ store เดิม — ไม่รื้อเขียนใหม่ Rust std ล้วน สุ่มด้วย splitmix64 + std SipHash (DefaultHasher) ไม่มี tokio/proptest THE SCOPE LINE (ปิดคอร์สย้ำ): เราลง code รันจริง เฉพาะส่วนที่ enumerate/property-test ได้ (quorum, version vector, CRDT merge, read-repair) — ส่วน consensus/Raft ที่ตรวจครบไม่ได้ คงไว้เป็น กล่องไดอะแกรม เท่านั้น (ดูหัวข้อ “กล่องไดอะแกรม” ด้านล่าง)

toolchain ที่ pin ไว้ + std ที่บทนี้ใช้

ทุก snippet pin ที่ Rust stable 1.97.1 (ออก 2026-07-16) และ edition = “2024” [dependencies] ว่างเปล่า — ZERO external crate code ในบทนี้แตะ std เพียง std::collections (BTreeMap) เท่านั้น ทุกโปรแกรม compile แบบ zero-warnings (-D warnings) และ รันจริง บน musl + rust-lld — เลขทุกตัวด้านล่างคือ output จริงที่ seed ล็อกไว้ รันซ้ำได้ byte-identical

การประกอบร่าง: stack ของ Dynamo ย่อสเกลลงบน kaen-kvstore

สิ่งที่เรากำลังจะสร้างไม่ใช่ของกุขึ้นเพื่อสอน — มันคือ stack จริงของ Amazon Dynamo (DeCandia et al. 2007): consistent-hash placement + quorum W/R + version-vector conflict detection + application/CRDT resolution + read-repair + Merkle anti-entropy เราแค่ย่อมันลงมาบน kaen-kvstore ที่ scale ของเล่น หัวใจอยู่ที่ ชนิดของ value ที่เก็บ: แต่ละ key ไม่ได้เก็บ byte ดิบๆ แต่เก็บเป็น Versioned ที่ประกอบจากสองส่วน

value: Lww — payload ที่เป็น CRDT (LWW-Register จากบท 4–5) ทำหน้าที่ แก้ (resolve) conflict เมื่อ write 2 concurrent มาชนกัน
vv: VersionVector — causal metadata (vector clock จากบท 1 ที่ key ด้วยผู้เขียน) ทำหน้าที่ ตรวจ (detect) ว่า2 write เป็นลำดับกัน (อัน1 dominate อีกอัน) หรือ concurrent

แยกหน้าที่ให้ชัด: version vector ตรวจ, CRDT แก้ ถ้า write ใหม่ dominate ของเก่า (เห็นทุกอย่างที่ของเก่าเห็น) ก็ทับได้ตรงๆ ไม่มี conflict; แต่ถ้าสองอัน concurrent — vv เทียบกันไม่ได้ — นั่นคือ conflict จริง ต้องให้ CRDT merge ตัดสิน (LWW เลือกอันที่ (ts, origin) สูงกว่า) ไม่ใช่แอบเลือก “ค่า max” มั่วๆ

use std::collections::BTreeMap;

#[derive(Clone, Debug, Default, PartialEq)]
struct VersionVector {
    entries: BTreeMap<u64, u64>,
}
impl VersionVector {
    fn get(&self, node: u64) -> u64 {
        *self.entries.get(&node).unwrap_or(&0)
    }
    fn increment(&mut self, node: u64) {
        *self.entries.entry(node).or_insert(0) += 1;
    }
    // element-wise max over the union = the semilattice join (LUB)
    fn merge(&self, other: &Self) -> Self {
        let mut out = self.clone();
        for (&n, &c) in &other.entries {
            let e = out.entries.entry(n).or_insert(0);
            if c > *e {
                *e = c;
            }
        }
        out
    }
    // self is strictly causally newer than other: >= on every component AND != .
    fn dominates(&self, other: &Self) -> bool {
        let mut keys: Vec<u64> = self.entries.keys().copied().collect();
        for k in other.entries.keys() {
            if !self.entries.contains_key(k) {
                keys.push(*k);
            }
        }
        let mut strictly = false;
        for k in keys {
            let (a, b) = (self.get(k), other.get(k));
            if a < b {
                return false;
            }
            if a > b {
                strictly = true;
            }
        }
        strictly
    }
}

Lww คือ payload ที่ resolve conflict ด้วย total order (ts, origin, val) — tie ทุกกรณีถูกตัดสินแบบดีเทอร์มินิสติก merge จึง commutative:

#[derive(Clone, Debug)]
struct Lww {
    ts: u64,
    origin: u64,
    val: Vec<u8>,
}
impl Lww {
    fn merge(&self, other: &Self) -> Lww {
        if (other.ts, other.origin, &other.val) > (self.ts, self.origin, &self.val) {
            other.clone()
        } else {
            self.clone()
        }
    }
}

แล้ว Versioned::reconcile คือหัวใจที่รวมสองอย่างเข้าด้วยกัน — vv ตรวจก่อน, ถ้า concurrent ค่อยให้ CRDT แก้:

#[derive(Clone, Debug)]
struct Versioned {
    value: Lww,
    vv: VersionVector,
}
impl Versioned {
    // version vector DETECTS the relationship; the CRDT RESOLVES a genuine conflict.
    fn reconcile(&self, other: &Versioned) -> Versioned {
        if self.vv.dominates(&other.vv) {
            self.clone() // self causally newer -> it wins outright
        } else if other.vv.dominates(&self.vv) {
            other.clone()
        } else {
            // equal or CONCURRENT: join the vv, let the CRDT pick the value
            Versioned {
                value: self.value.merge(&other.value),
                vv: self.vv.merge(&other.vv),
            }
        }
    }
}

แผนที่กลับไปที่ #22 และ std::net

ใน code สาธิตด้านล่าง แต่ละ replica คือ BTreeMap<Vec<u8>, Versioned> หนึ่งตัว — มันคือตัวแทนของ kaen-kvstore instance หนึ่งเครื่อง ที่ในระบบจริงจะเข้าถึงผ่าน std::net ด้วย wire แบบ length-prefixed ของ #22 (write_frame/read_frame) โดยไม่แตะ serde เลย ส่วน partition mask up[i] (node ไหนติดต่อได้ตอนนี้) คือสิ่งที่ harness ของบท 7 พลิกเข้า-ออก #23 จึงเป็นแค่ชั้นบางๆ ที่ แขวน replication + quorum + version-vector + anti-entropy ทับบน log / write→fsync→ack / hash-index / immutable-segment ของ #22 ไม่ได้เขียน store ใหม่ และ การเลือก replica set ของแต่ละ key ใช้ ring ของบท 2 — consistent-hash วางแต่ละ key ลงชุด node ที่รับผิดชอบ แล้ว coordinator ก็ทำ quorum กับชุดนั้น

Cluster รวม replica ทั้งหมด + parameter n/w/r แล้วให้ quorum_write, read (พร้อม read-repair) กับตัวแยก prepare/commit (ที่ทำให้ทดลอง write ที่ concurrent ได้):

struct Cluster {
    replicas: Vec<BTreeMap<Vec<u8>, Versioned>>,
    n: usize,
    w: usize,
    r: usize,
}
impl Cluster {
    fn new(n: usize, w: usize, r: usize) -> Cluster {
        Cluster {
            replicas: (0..n).map(|_| BTreeMap::new()).collect(),
            n,
            w,
            r,
        }
    }

    // read reachable base, build the NEW Versioned (bump coord, fresh Lww) WITHOUT committing.
    // Splitting prepare/commit lets two coordinators branch from the SAME base = concurrent writes.
    fn prepare(&self, coord: u64, key: &[u8], val: &[u8], ts: u64, up: &[bool]) -> Versioned {
        let mut base = VersionVector::default();
        for i in 0..self.n {
            if up[i] {
                if let Some(v) = self.replicas[i].get(key) {
                    base = base.merge(&v.vv);
                }
            }
        }
        base.increment(coord);
        Versioned {
            value: Lww { ts, origin: coord, val: val.to_vec() },
            vv: base,
        }
    }

    // commit to every reachable replica by RECONCILE (merge-on-write, never blind overwrite).
    // ack = reachable replicas; the write is durable iff ack >= W.
    fn commit(&mut self, key: &[u8], v: &Versioned, up: &[bool]) -> Result<usize, usize> {
        let mut ack = 0;
        for i in 0..self.n {
            if up[i] {
                let merged = match self.replicas[i].get(key) {
                    Some(cur) => cur.reconcile(v),
                    None => v.clone(),
                };
                self.replicas[i].insert(key.to_vec(), merged);
                ack += 1;
            }
        }
        if ack >= self.w { Ok(ack) } else { Err(ack) }
    }

    fn quorum_write(&mut self, coord: u64, key: &[u8], val: &[u8], ts: u64, up: &[bool]) -> Result<usize, usize> {
        let v = self.prepare(coord, key, val, ts, up);
        self.commit(key, &v, up)
    }

    // R-quorum read: gather reachable replicas, reconcile to the LUB, then READ-REPAIR
    // every reachable replica whose stored version differs.
    fn read(&mut self, key: &[u8], up: &[bool]) -> Result<Option<Vec<u8>>, usize> {
        let reachable: Vec<usize> = (0..self.n).filter(|&i| up[i]).collect();
        if reachable.len() < self.r {
            return Err(reachable.len()); // cannot assemble a read quorum
        }
        let mut lub: Option<Versioned> = None;
        for &i in &reachable {
            if let Some(v) = self.replicas[i].get(key) {
                lub = Some(match lub {
                    Some(acc) => acc.reconcile(v),
                    None => v.clone(),
                });
            }
        }
        if let Some(ref win) = lub {
            for &i in &reachable {
                let repaired = match self.replicas[i].get(key) {
                    Some(cur) => cur.reconcile(win),
                    None => win.clone(),
                };
                self.replicas[i].insert(key.to_vec(), repaired);
            }
        }
        Ok(lub.map(|v| v.value.val))
    }

    fn replica_value(&self, i: usize, key: &[u8]) -> Option<Vec<u8>> {
        self.replicas[i].get(key).map(|v| v.value.val.clone())
    }
}

สังเกตว่า commit และ read ไม่เคยเขียนทับดิบๆ — มัน reconcile เข้ากับค่าเดิมเสมอ นี่คือ CRDT-as-value จากบท 5: write กลายเป็น merge ทำให้ idempotent (ส่งซ้ำไม่มีผล) และ commutative (ลำดับส่งไม่มีผล) — เงื่อนไขเดียวกับที่ทำให้ eventual consistency เป็นจริง

สองสมบัติความปลอดภัย ที่ harness เป็นออราเคิลให้

happy-path demo บอกอะไรเราไม่ได้เลย สิ่งที่ต้องพิสูจน์คือสองสมบัติที่ เห็นได้เฉพาะเมื่อฉีด partition เข้าไป — และมันคือสิ่งที่ harness ของบท 7 ยืนยัน (ที่นี่เราสาธิตด้วยฉากที่ล็อกไว้ให้อ่านง่าย ตัว harness เต็มคือของบท 7 ที่รัน 500 seed)

สมบัติ 1 — “write ที่ ack แล้วต้องไม่หาย ถ้า W+R>N”: เขียน x=a ตอน replica 2 ถูกตัดขาด — ack จากฝั่งที่ติดต่อได้ {0,1} (2 ≥ W=2) ถือว่าสำเร็จ replica 2 พลาด write นี้ไป แต่พอ heal แล้วอ่านครั้งเดียว read-repair จะพา a ไปถึง replica 2 เพราะ read quorum ทับ write quorum เสมอ (W+R=4>3)

สมบัติ 2 — “replica ลู่เข้าหลัง heal”: 2 write ที่ concurrent (coordinator คนละตัว branch จาก base เดียวกัน) reconcile กันด้วย version vector + CRDT merge จนทุก replica เห็นค่าเดียวกัน

fn s(o: &Option<Vec<u8>>) -> String {
    match o {
        Some(v) => String::from_utf8_lossy(v).into_owned(),
        None => "None".to_string(),
    }
}

fn main() {
    // N=3, W=2, R=2  =>  W+R = 4 > 3  => every read quorum meets the newest write quorum.
    let mut c = Cluster::new(3, 2, 2);
    let all = [true, true, true];

    // ---- Property 1: NO LOST ACKED WRITE under W+R>N (durability across a partition) ----
    let masked = [true, true, false]; // replica 2 partitioned away
    let ack = c.quorum_write(0, b"x", b"a", 1, &masked).expect("W-quorum {0,1} must ack");
    println!("write x=a while replica 2 partitioned -> acked by {ack} replicas (W=2) OK");
    assert_eq!(c.replica_value(2, b"x"), None, "replica 2 missed the write during the partition");

    let got = c.read(b"x", &all).expect("R-quorum available after heal");
    println!("after heal, read x -> {} ; read-repair fires", s(&got));
    for i in 0..3 {
        assert_eq!(c.replica_value(i, b"x").as_deref(), Some(&b"a"[..]), "replica {i} not repaired");
    }
    println!("Property 1 holds: acked write x=a present on ALL 3 replicas (no lost acked write)");

    // ---- Property 2: REPLICAS CONVERGE AFTER HEAL (concurrent writes reconcile) ----
    let wa = c.prepare(1, b"y", b"aa", 5, &all); // vv {1:1}, ts=5
    let wb = c.prepare(2, b"y", b"bb", 7, &all); // vv {2:1}, ts=7
    assert!(!wa.vv.dominates(&wb.vv) && !wb.vv.dominates(&wa.vv), "the two writes must be concurrent");
    c.commit(b"y", &wa, &all).expect("W ok");
    c.commit(b"y", &wb, &all).expect("W ok");
    let y = c.read(b"y", &all).expect("R ok");
    println!("concurrent y: aa@ts5 (node1) || bb@ts7 (node2) -> converges to {}", s(&y));
    for i in 0..3 {
        assert_eq!(c.replica_value(i, b"y").as_deref(), Some(&b"bb"[..]), "replica {i} did not converge");
    }
    println!("Property 2 holds: all 3 replicas converged to bb (aa was concurrent, LWW-dropped)");
    println!("PART A: quorum + version-vector + CRDT composition -- both safety properties hold.");
}

รันจริงบน musl ได้ผลตามนี้:

write x=a while replica 2 partitioned -> acked by 2 replicas (W=2) OK
after heal, read x -> a ; read-repair fires
Property 1 holds: acked write x=a present on ALL 3 replicas (no lost acked write)
concurrent y: aa@ts5 (node1) || bb@ts7 (node2) -> converges to bb
Property 2 holds: all 3 replicas converged to bb (aa was concurrent, LWW-dropped)
PART A: quorum + version-vector + CRDT composition -- both safety properties hold.

x=a ที่ ack ไปตอน replica 2 ล่ม กลับมาอยู่ครบทั้ง 3 replica หลัง read-repair — ไม่มี write ที่ ack แล้วหาย ส่วน y ที่มี2 write concurrent (aa@ts5 กับ bb@ts7) ลู่เข้าเป็น bb เหมือนกันทุก replica เพราะ LWW เลือก ts สูงกว่า (aa ถูกทิ้งอย่างเงียบๆ — lossy โดย design ถ้ารับไม่ได้ต้องใช้ OR-Set/PN-Counter จากบท 5 แทน)

flowchart TB
    subgraph cluster["cluster kaen-kvstore (N=3, W=2, R=2)"]
        R0["replica 0<br/>x=a"]
        R1["replica 1<br/>x=a"]
        R2["replica 2<br/>(partitioned)"]
    end
    C["client เขียน x=a"] -->|ack จาก W=2| R0
    C -->|ack จาก W=2| R1
    C -.->|ข้อความไม่ถึง| R2
    R0 -->|heal + read-repair| R2
    R1 -->|heal + read-repair| R2

    subgraph box["📦 กล่องไดอะแกรมเท่านั้น — ไม่ลง code (FLP 1985 / Raft S16)"]
        L["leader"] -->|log replication| F1["follower"]
        L -->|log replication| F2["follower"]
        L -.->|commit index / leader election| L
    end

คำบรรยายภาพ: capstone — quorum + read-repair + CRDT ลู่เข้าได้ พิสูจน์ด้วย harness ที่รันจริง (client เขียนได้ ack จากฝั่ง majority, พอ heal แล้ว read-repair พา x=a ไปถึง replica ที่เคยขาด); ส่วน consensus (leader election, log replication, commit index) อยู่ใน กล่องไดอะแกรมเท่านั้น — Rust พิสูจน์ให้ไม่ได้

keystone: quorum intersection คือข้อเท็จจริงที่ enumerate ครบได้

ทำไมสมบัติ 1 ถึง “ลง code รันจริง” ได้อย่างมั่นใจ ในขณะที่ consensus ต้องอยู่ในกล่องไดอะแกรม คำตอบคือ quorum intersection เป็นข้อเท็จจริงเชิงการจัดหมู่ที่สถิต — สำหรับ N ที่กำหนด เรา เอ็นนิวเมอเรตทุก W-set กับทุก R-set ได้ครบ แล้วยืนยันว่าทุกคู่ทับกันก็ต่อเมื่อ W+R>N ไม่ใช่การสุ่มตัวอย่าง แต่คือการตรวจครบทั้ง space:

fn every_wr_pair_intersects(n: usize, w: usize, r: usize) -> bool {
    let total: u32 = 1u32 << n;
    for a in 0..total {
        if (a.count_ones() as usize) != w {
            continue;
        }
        for b in 0..total {
            if (b.count_ones() as usize) != r {
                continue;
            }
            if (a & b) == 0 {
                return false; // a disjoint W/R pair exists -> a read can miss the write
            }
        }
    }
    true
}

fn main() {
    let n = 5;
    let (mut checked, mut disagreements) = (0u32, 0u32);
    for w in 1..=n {
        for r in 1..=n {
            let all_intersect = every_wr_pair_intersects(n, w, r);
            let predicted = w + r > n;
            if all_intersect != predicted { disagreements += 1; }
            assert_eq!(all_intersect, predicted);
            checked += 1;
        }
    }
    println!("N={n}: verified {checked} (W,R) pairs -- exhaustive intersection == (W+R>N) both directions");
    println!("disagreements = {disagreements} (PASS)");
    let corner_ok = every_wr_pair_intersects(n, 3, 3);
    let corner_bad = every_wr_pair_intersects(n, 3, 2);
    assert!(corner_ok && !corner_bad);
    println!("boundary: (W=3,R=3) always intersects; (W=3,R=2) has a disjoint pair -- as predicted");
}

N=5: verified 25 (W,R) pairs -- exhaustive intersection == (W+R>N) both directions
disagreements = 0 (PASS)
boundary: (W=3,R=3) always intersects; (W=3,R=2) has a disjoint pair -- as predicted

ทั้ง 25 คู่ (W,R) ที่ N=5 ตรงกับสูตร W+R>N เป๊ะ ทั้งสองทาง — คู่ที่ W+R>N ทับกันเสมอจริง และคู่ที่ W+R≤N มีคู่ disjoint จริง นี่คือสิ่งที่ Rust พิสูจน์ให้ได้ บนเครื่องเดียว เพราะมันเป็น combinatorics ที่ปิด ไม่ใช่พฤติกรรม runtime ที่ต้องภาวนา

กฎลู่เข้า: G-Counter semilattice ที่ทำให้ทุกอย่างทำงาน

สมบัติ 2 (ลู่เข้าหลัง heal) วางอยู่บนกฎเดียว: merge ต้องเป็น join ของ semilattice (commutative + associative + idempotent) กฎนี้เองที่ทำให้ replica เห็นชุด write เดียวกัน (ไม่ว่าลำดับหรือส่งซ้ำแค่ไหน) ลู่เข้าหาสถานะเดียวกันเสมอ เราปิดคอร์สด้วยการพิสูจน์มันอีกครั้งบน G-Counter — ซึ่งมีโครงเหมือน version vector ของบท 1 เป๊ะ (merge = element-wise max) จึงลู่เข้าด้วย เหตุผลเดียวกับ CRDT payload ของ capstone ใช้ splitmix64 seed คงที่ 0xDEADBEEF, 3000 triple:

#[derive(Clone, PartialEq)]
struct GCounter {
    slots: BTreeMap<u64, u64>,
}
impl GCounter {
    fn new() -> Self { Self { slots: BTreeMap::new() } }
    fn inc(&mut self, node: u64, by: u64) {
        *self.slots.entry(node).or_insert(0) += by;
    }
    fn merge(&self, other: &Self) -> Self {
        let mut out = self.clone();
        for (&n, &c) in &other.slots {
            let e = out.slots.entry(n).or_insert(0);
            if c > *e { *e = c; }
        }
        out
    }
    fn value(&self) -> u64 { self.slots.values().sum() }
}

ตัว property test สุ่ม triple x, y, z แล้วยืนยันสามกฎทุกชุด (commutative x|y==y|x, associative (x|y)|z==x|(y|z), idempotent x|x==x) — ตัว driver ที่ขับ loop นี้คือ pattern splitmix64 + law-loop ตัวเดียวกับ property test ในบท 1/บท 4 (ไม่กาง code ซ้ำที่นี่) seed 0xDEADBEEF คงที่จึงได้ checks=9000 ที่รันซ้ำได้:

G-Counter demo: merge([0:3],[1:5]) = value 8 (order-independent: true)
--- G-Counter semilattice property test (seed=0xdeadbeef, 3000 cases) ---
checks = 9000, violations = 0
PART C: G-Counter merge is a join-semilattice -- the capstone's convergence guarantee.

checks=9000 violations=0 — 3 กฎ × 3000 เคส ไม่มีข้อไหนพลาด นี่คือ Strong Eventual Consistency ที่ Shapiro et al. (2011) พิสูจน์ไว้: semilattice + eventual delivery ⇒ ลู่เข้า โดยไม่ต้อง consensus เลย และนั่นคือเหตุผลลึกๆ ว่าทำไม CRDT ถึงอยู่ฝั่งซ้ายของเส้น scope ส่วน consensus อยู่ฝั่งขวา

กล่องไดอะแกรม: ทำไม consensus/Raft ไม่ลง code

กล่องไดอะแกรมเท่านั้น — consensus / leader-based replication / linearizable multi-key txn

สามอย่างนี้ ไม่มีใน code ที่ ship และจะไม่มีตลอดคอร์ส — มันอยู่ในไดอะแกรมด้านบนเท่านั้น:

1. Raft / consensus correctness. Raft ให้ leader หนึ่งตัวรับ write, replicate log ไปยัง follower, แล้วเลื่อน commit index เมื่อ majority ยืนยัน (Ongaro–Ousterhout, ATC 2014) โครงสร้างนี้ เข้าใจง่าย แต่ พิสูจน์ความถูกต้องบนเครื่องเดียวไม่ได้: Raft ที่ผิดนิดเดียว (เช่น เงื่อนไข election หรือ log-matching เพี้ยน) ก็ยัง compile zero-warnings และผ่าน happy path เพราะ Rust พิสูจน์ความถูกต้อง ในเครื่องเดียว (memory/type/data-race) ไม่ใช่ แบบกระจาย bug จะโผล่เฉพาะตอน partition + reorder + clock-skew ที่ ไม่เกิดซ้ำใน process เดียว

2. ทำไมตรวจครบไม่ได้ (FLP 1985). Fischer–Lynch–Paterson พิสูจน์ว่า ไม่มี algorithm consensus แบบ asynchronous ที่การันตีได้ว่าจะ จบและถูกต้อง ถ้ามี node เสียแม้เพียงหนึ่ง — ต่อ scheduler ที่เป็นปฏิปักษ์ ดังนั้น green test ของ Raft ที่เขียนเองจะเป็น คำกล่าวอ้างความถูกต้องที่เท็จ ต่างจาก quorum arithmetic ที่ enumerate ครบได้ (25 คู่ข้างบน) — state space ของ Raft ระเบิด ตรวจครบไม่ได้

3. linearizable multi-key transaction ก็อยู่ในกล่องนี้ด้วย: quorum ซื้อแค่ การทับกัน (intersection) ไม่ได้ซื้อ linearizability และไม่ได้ซื้อ agreement บนลำดับ — เราพูดตรงๆ ว่า cluster นี้เป็น eventually consistent ไม่ใช่ linearizable (checker ของบท 7 คืน false บน history ของ store นี้ โดยตั้งใจ — มันมาร์กเส้นที่ linearizable-txn/consensus ออกจากส่วนที่ ship ได้พอดี)

honesty spine 4 เส้น (บทปิดยึดครบทั้งสี่ เหมือนบทเปิด)

A — Rust พิสูจน์ “ในเครื่องเดียว” ไม่ใช่ “แบบกระจาย”: borrow checker จับ data race ใน process เดียว แต่มองไม่เห็น partition/reorder/skew — harness ฉีด partition (บท 7) คือ ออราเคิล ของสมบัติแบบกระจาย และมันคือการ ตรวจแบบมีขอบเขต ไม่ใช่บทพิสูจน์ (FLP 1985): ผ่าน 500 seed แปลว่าสำรวจเฉพาะ interleaving ที่ PRNG เดินไปถึง

B — เส้น scope: quorum arithmetic enumerate ครบทุก subset ได้ (25 คู่) จึง ลง code รันจริง; consensus/Raft/leader-replication/linearizable-txn ตรวจครบไม่ได้ จึงอยู่ใน กล่องไดอะแกรม เท่านั้น

C — ดีเทอร์มินิสซึมคือวินัย: seed คงที่ (0xDEADBEEF) + single-scheduler + hard timeout + BTreeMap (ไม่ใช่ HashMap ที่ RandomState สลับลำดับต่อ process) ทุก harness มี round budget มิฉะนั้นมัน ค้าง (compiler จับ deadlock ไม่ได้) หรือ โกหก (รันแดงซ้ำไม่ได้)

D — นี่คือกลไกจริงของ Dynamo/Cassandra/Riak: consistent-hash + quorum + version vector + CRDT + Merkle + gossip คือ stack จริงของ Amazon Dynamo — สอนตรงต้นฉบับที่ scale ของเล่นบน kaen-kvstore ไม่ใช่ของกุขึ้น

คนละเลนกับ #8 (bounded-contexts-integration)

อย่าสับสนสองคอร์สนี้ #8 คือ message DELIVERY ข้าม bounded context (Wolverine outbox/RabbitMQ, at-least-once event transport) — ส่ง เหตุการณ์ ให้ถึงอีกบริการ ส่วน #23 คือ data REPLICATION ของ state ของ key เดียว ข้าม replica (quorum + CRDT convergence) — ทำให้ สำเนาของค่าเดียวกัน เห็นตรงกัน คนละเลน คนละการันตี

ปิดคอร์ส: เส้นเรื่อง Systems pillar

คุณเดินครบสามคอร์สของ Systems pillar แล้ว:

#21 rust-from-scratch — เรียน Rust: ownership/borrow/lifetime, trait, error handling, thread + channel — เครื่องมือทั้งชุดที่พิสูจน์ความถูกต้อง ในเครื่องเดียว
#22 rust-kvstore — สร้างเอนจิน: เอา Rust นั้นมาสร้าง kaen-kvstore node เดียวที่รันจริง — network server, append-only log + hash index, write→fsync→ack durability, tombstone/compaction, thread pool
#23 rust-distributed-systems — กระจายมัน: เลื่อน node เดียวขึ้นเป็น cluster — logical clock → consistent hashing → quorum → CRDT → anti-entropy → harness → capstone นี้ ทั้งหมด Rust std ล้วน พิสูจน์ด้วย property test ที่รันได้จริง

บทเรียนกลางของทั้ง pillar คือ เส้น scope: Rust พิสูจน์ความถูกต้อง ในเครื่องเดียว ได้อย่างทรงพลัง — เราจึงลง code รันจริงเฉพาะสมบัติที่ enumerate/property-test ได้ (quorum, CRDT, logical clock) ส่วนความถูกต้อง แบบกระจาย ที่ scheduler เป็นปฏิปักษ์ (consensus/Raft) เราซื่อสัตย์ว่าตรวจครบไม่ได้ จึงคงไว้เป็นไดอะแกรม นี่ไม่ใช่ข้อจำกัดที่น่าอาย แต่คือ วินัยทางวิศวกรรม: รู้ว่าอะไรพิสูจน์ได้ อะไรพิสูจน์ไม่ได้ แล้วไม่กล่าวอ้างเกินจริง

จากตรงนี้ ถ้าอยากไปต่อในโลกจริง: อ่าน DDIA (Kleppmann 2017) ให้ครบ ch5 (replication) + ch9 (consistency & consensus), ลอง Jepsen (Jepsen) ของจริงกับระบบ production, และถ้าจะแตะ consensus ให้ใช้ library ที่ผ่านการทดสอบมาแล้ว — ไม่ใช่เขียน Raft เองจาก scratch แล้วเชื่อ green test

🔗 อ้างอิงต้นทางของบทนี้

บทนี้อิงต้นทางที่ลงวันที่กำกับ อ่านต่อได้โดยตรง:

Giuseppe DeCandia et al. — “Dynamo: Amazon’s Highly Available Key-value Store” (SOSP’07) (เข้าถึง 2026-07-24) — stack ที่ capstone นี้ประกอบ: consistent-hash placement + quorum + version-vector detection + application/CRDT resolution + read-repair + Merkle anti-entropy ทั้งชุด
Martin Kleppmann — “Designing Data-Intensive Applications” (DDIA), ch5 Replication + ch9 Consistency & Consensus (2017) (เข้าถึง 2026-07-24) — quorum ซื้อ การทับกัน ไม่ใช่ linearizability; W+R>N คุม staleness ไม่ใช่ consensus; CRDT ลู่เข้าก็ต่อเมื่อ merge เป็น join-semilattice
Diego Ongaro, John Ousterhout — “In Search of an Understandable Consensus Algorithm” (Raft, USENIX ATC’14) (เข้าถึง 2026-07-24) — โครงสร้าง consensus ในกล่องไดอะแกรม: leader election, log replication, commit index — ที่เรา ไม่ ลง code เพราะพิสูจน์บนเครื่องเดียวไม่ได้
Fischer, Lynch, Paterson — “Impossibility of Distributed Consensus with One Faulty Process” (FLP, JACM 32(2), 1985) (เข้าถึง 2026-07-24) — เหตุผลรากที่ consensus อยู่ในกล่องไดอะแกรม: ไม่มี asynchronous consensus ที่การันตีจบ+ถูกต้องถ้ามี node เสียแม้หนึ่ง จึงตรวจครบด้วย test ไม่ได้

เช็กความเข้าใจ — บทที่ 8

ข้อ 1 / 3

ทำไม quorum arithmetic (W+R>N) ถึง 'ลง code รันจริง' ได้ แต่ consensus/Raft ต้องอยู่ในกล่องไดอะแกรมเท่านั้น?

Capstone — cluster kaen-kvstore หลาย replica บน std::net: quorum + CRDT + consistent-hash

การ​ประกอบ​ร่าง: stack ของ Dynamo ย่อ​สเกล​ลง​บน kaen-kvstore

แผนที่​กลับ​ไป​ที่ #22 และ std::net

สอง​สมบัติ​ความ​ปลอดภัย ที่ harness เป็น​ออราเคิล​ให้

keystone: quorum intersection คือ​ข้อเท็จจริง​ที่ enumerate ครบ​ได้

กฎ​ลู่​เข้า: G-Counter semilattice ที่​ทำให้​ทุก​อย่าง​ทำงาน

กล่อง​ไดอะแกรม: ทำไม consensus/Raft ไม่​ลง code

ปิด​คอร์ส: เส้น​เรื่อง Systems pillar