Quorum R/W/N และ read-repair — ทำไม W+R>N ถึงการันตีการทับกัน

บท 1 ให้เวลาเชิงตรรกะ (vector clock) ไว้ตรวจว่าเหตุการณ์ไหนเกิดก่อนไหน บท 2 ให้ consistent hashing ไว้ตอบว่า key แต่ละตัว ควรอยู่ node ไหน — และตอนวางแต่ละ key เราไม่ได้วางแค่สำเนาเดียว แต่วางลง N replica เพื่อให้ทน node ล่ม บทนี้ตอบคำถามที่ตามมาทันที: ถ้า key หนึ่งมีสำเนาอยู่ N ที่ เวลาเขียนต้องเขียนกี่ที่ เวลาอ่านต้องอ่านกี่ที่ ถึงจะ มั่นใจว่าอ่านเจอค่าที่เพิ่งเขียน โดยไม่ต้องรอครบทุก node (ซึ่งจะทำให้ระบบตายทั้ง cluster เมื่อ node เดียวช้า)

คำตอบคือ quorum: เขียนให้ ack อย่างน้อย W ที่ อ่านให้ตอบอย่างน้อย R ที่ กติกาข้อเดียวที่ทำให้มันเวิร์กคือ W + R > N และเหตุผลที่มันเวิร์กสวยงามกว่าที่คิด — มันไม่ใช่คุณสมบัติ runtime ที่ต้องภาวนาให้ถูก แต่เป็น ข้อเท็จจริงเชิงการจัดหมู่ที่สถิต (static) ที่เรา เอ็นนิวเมอเรตครบทุกกรณีได้จริง บทนี้จึงพิสูจน์มันแบบ exhaustive ไม่ใช่แบบสุ่มตัวอย่าง

📦 kaen-kvstore

คอร์สนี้ ต่อยอด repo kaen-kvstore จาก #22 (code ตัวอย่างกำลังจัดทำ) — บทนี้ยกแต่ละ key จากสำเนาเดียวขึ้นเป็น N replica แล้วเพิ่มชั้น quorum coordinator ทับ store เดิม: เขียนกระจายไป W replica อ่านรวมจาก R replica ทั้งหมด Rust std ล้วน ไม่มี serde/tokio/proptest — สุ่มด้วย splitmix64 ที่ seed ซ้ำได้ 100% THE SCOPE LINE: quorum arithmetic เป็นข้อเท็จจริงเชิงการจัดหมู่ที่ เอ็นนิวเมอเรตครบได้ เราจึงลง code รันจริงและตรวจครบทุก subset — ต่างจาก consensus/Raft ที่ตรวจครบไม่ได้และคงไว้เป็นไดอะแกรม (บท 8) code ในบทนี้แตะ std เพียง std::vec/std::iter (ไม่มี import นอก std เลย); ทุกโปรแกรม compile แบบ zero-warnings บน Rust 1.97.1 / edition 2024 และ รันจริง — เลขทุกตัวด้านล่างคือ output จริงที่ seed ล็อกไว้ รันซ้ำได้ byte-identical

กติกา N / W / R และการทับกันแบบรับประกัน

ตั้งค่าให้ชัด: key หนึ่งมีสำเนาอยู่ N replica; การเขียนหนึ่งครั้งจะถือว่าสำเร็จ (ack กลับหา client) เมื่อได้ ack จากอย่างน้อย W replica; การอ่านหนึ่งครั้งจะรวบคำตอบจากอย่างน้อย R replica แล้วเลือกค่าที่ใหม่ที่สุด W คือ write quorum R คือ read quorum

หัวใจอยู่ที่ประโยคเดียว: ถ้า W + R > N แล้วทุก write-set ขนาด W กับทุก read-set ขนาด R จะมี node ร่วมกันอย่างน้อยหนึ่งตัวเสมอ เพราะ node ร่วมตัวนั้นเคยรับ write ล่าสุดไว้ การอ่านจึง ต้อง เห็นค่านั้นอย่างน้อยหนึ่งสำเนา — อ่านไม่มีทางพลาด write ที่ ack ไปแล้ว

พิสูจน์ด้วย pigeonhole ตรงๆ ไม่ต้องอ้อม ให้ W และ R เป็นเซ็ตของ replica ที่ถูกเขียน/ถูกอ่าน:

|W ∩ R| = |W| + |R| − |W ∪ R|  ≥  w + r − n  >  0

บรรทัดกลางใช้ข้อเท็จจริงว่า |W ∪ R| ≤ n (ทั้งสองเซ็ตเป็น subset ของ replica ทั้ง N ตัว) ดังนั้นถ้า w + r > n ขนาดของ intersection จะมากกว่า 0 เสมอ — มี node ร่วมแน่นอน นี่คือกฎของ Gifford (Weighted Voting for Replicated Data, SOSP 1979) ที่ Dynamo และ Cassandra ใช้จริงจนถึงทุกวันนี้ (DDIA บท 5, Kleppmann 2017)

graph LR
    W["write quorum<br/>W = 3"] -->|เขียน| N0["replica 0"]
    W -->|เขียน| N1["replica 1"]
    W -->|เขียน| N2["replica 2 ★"]
    R["read quorum<br/>R = 3"] -->|อ่าน| N2
    R -->|อ่าน| N3["replica 3"]
    R -->|อ่าน| N4["replica 4"]
    N2 -->|"node ร่วม → อ่านเห็น write ล่าสุด"| OUT["ค่าที่ใหม่ที่สุด"]

คำบรรยายภาพ: N=5, write-set {0,1,2} (W=3) กับ read-set {2,3,4} (R=3) — W+R = 6 > 5 จึงบังคับให้มี node ร่วมอย่างน้อยหนึ่งตัว (ที่นี่คือ replica 2 ★) การอ่านที่แตะ replica 2 จึงเห็น write ล่าสุดเสมอ ต่อให้ read-set กับ write-set จะเลือก node ต่างกันอย่างไรก็ตาม

ทำไมต้อง enumerate ไม่ใช่สุ่มทดสอบ

จุดที่คนมักพลาด: W + R > N เป็นคุณสมบัติ สถิต — มันไม่ขึ้นกับเวลา ข้อความ หรือลำดับ runtime เลย มันเป็นแค่ข้อเท็จจริงเรื่อง subset ของเซ็ตจำกัด เมื่อของมันสถิตและ เอ็นนิวเมอเรตครบได้ การเอา property test แบบสุ่มมายิงคือการตอบผิดเครื่องมือ — random test อาจ พลาดขอบที่คับที่สุด คือกรณี w + r = n + 1 ที่ intersection เหลือแค่ 1 พอดี ถ้าสุ่มไม่โดนคู่นั้น เราจะเข้าใจผิดว่า “ผ่าน” ทั้งที่ยังไม่เคยตรวจกรณีวิกฤต

เราจึง ตัดสิน มันด้วยการ enumerate: สำหรับ n แต่ละค่า แทน replica แต่ละตัวด้วย1 bit ของเลข n bit แล้วไล่ทุก write-set (a) คู่กับทุก read-set (b) ครบทั้ง 2^n × 2^n คู่ ตรวจสองอย่าง (1) ถ้า w + r > n แต่ a & b ว่าง (intersection = 0) นับเป็น counterexample; (2) เก็บ intersection ที่ เล็กที่สุด ของแต่ละ (w, r) ไว้เทียบกับ oracle รูปปิด max(0, w+r−n) — ค่านี้คือ intersection ที่น้อยที่สุดที่ เป็นไปได้จริง ของ w-subset กับ r-subset (และมี disjoint pair ก็ต่อเมื่อ w + r ≤ n)

// Quorum W+R>N intersection: EXHAUSTIVE combinatorial verification (pure std).
// STATIC, DECIDABLE fact -- verify by ENUMERATION, not sampling. Enumerate EVERY
// (W-subset, R-subset) pair for all n up to N_MAX (n-bit masks) and cross-check
// the enumerated minimum intersection against the closed-form oracle max(0,w+r-n).
const N_MAX: usize = 12;

fn main() {
    let mut counterexamples: u64 = 0; // W+R>N pairs that were nonetheless disjoint
    let mut oracle_mismatch: u64 = 0; // enumeration disagreed with max(0,w+r-n)
    let mut pairs_checked: u64 = 0;

    for n in 1..=N_MAX {
        // min_int[w][r] = smallest |A ∩ B| seen over all w-subsets A, r-subsets B.
        let mut min_int = vec![vec![usize::MAX; n + 1]; n + 1];
        let total: u32 = 1u32 << n;

        for a in 0..total {
            let w = a.count_ones() as usize;
            if w == 0 {
                continue;
            }
            for b in 0..total {
                let r = b.count_ones() as usize;
                if r == 0 {
                    continue;
                }
                pairs_checked += 1;
                let inter = (a & b).count_ones() as usize;

                // SAFETY INVARIANT under test: W + R > N  =>  quorums intersect.
                if w + r > n && inter == 0 {
                    counterexamples += 1;
                }
                if inter < min_int[w][r] {
                    min_int[w][r] = inter;
                }
            }
        }

        // Independent oracle: the achievable minimum intersection of a w-subset
        // and an r-subset of an n-set is EXACTLY max(0, w+r-n); a disjoint pair
        // exists iff w+r <= n. Cross-check the whole (w,r) table.
        for w in 1..=n {
            for r in 1..=n {
                let oracle = (w + r).saturating_sub(n); // = max(0, w+r-n)
                if min_int[w][r] != oracle {
                    oracle_mismatch += 1;
                }
            }
        }
    }

    println!("N_MAX = {N_MAX}");
    println!("subset pairs exhaustively checked : {pairs_checked}");
    println!("W+R>N intersection counterexamples: {counterexamples}");
    println!("closed-form oracle mismatches     : {oracle_mismatch}");
    assert_eq!(counterexamples, 0, "found a DISJOINT quorum pair despite W+R>N");
    assert_eq!(oracle_mismatch, 0, "enumeration disagreed with max(0,w+r-n) oracle");
    println!("PASS: for every n<=N_MAX and every (w,r), W+R>N guarantees intersection");
}

รันจริงบน musl:

N_MAX = 12
subset pairs exhaustively checked : 22353252
W+R>N intersection counterexamples: 0
closed-form oracle mismatches     : 0
PASS: for every n<=N_MAX and every (w,r), W+R>N guarantees intersection

22,353,252 คู่ subset ตรวจครบ ได้ 0 counterexample และ enumeration ตรงกับ oracle รูปปิดทุกช่อง — สองบรรทัดนี้ยืนยันคนละทาง: counterexample = 0 บอกว่า “ไม่มีคู่ที่ W+R>N แล้วยัง disjoint”; oracle mismatch = 0 บอกว่า “intersection ที่เล็กที่สุดที่เจอตรงกับสูตรทุกกรณี” รวมกันคือหลักฐานว่าเราตรวจ ขอบที่คับที่สุด (w+r = n+1) แล้วจริง ไม่ได้ผ่านเพราะโชคดี

ระวัง O(4^n) ระเบิด — เหตุผลที่ cap ไว้ที่ N_MAX = 12

การ enumerate นี้เป็น O(4^n) เพราะไล่ 2^n write-set คูณ 2^n read-set: N_MAX = 12 คือ ~22.4 ล้านคู่ รันในราว 0.4 วินาที แต่ n = 16 ขึ้นไปจะระเบิดเป็นหลักพันล้านทันที ถ้าต้องพิสูจน์ n ใหญ่กว่านี้ อย่าไล่ทุก subset — จัดกลุ่มด้วย popcount (จำนวน bit) แล้วพึ่ง oracle รูปปิด max(0, w+r−n) ที่เราครอสเช็กไว้แล้วแทน สำหรับสอนหลักการ N_MAX = 12 ครอบขอบวิกฤตครบและรันไว

read-repair: เขียนค่าที่ merge แล้วกลับไปกลบตัวที่เก่า

quorum การันตีว่า อ่านเจอ ค่าล่าสุด แต่ตอนอ่านเราอาจเจอ replica ที่ยัง เก่า ปนอยู่ใน read-set (มันไม่ได้อยู่ใน write-set ครั้งก่อน) จะปล่อยไว้ก็เสี่ยงว่ารอบหน้ามันตอบค่าเก่าอีก read-repair คือกลไกซ่อมตรงนี้: ระหว่างที่อ่านอยู่แล้ว ให้คำนวณค่าที่ใหม่ที่สุดของ read-set แล้ว เขียนมันกลับ ไปกลบ replica ที่เก่าหรือที่ยังไม่มีค่า — เป็น anti-entropy แบบฉวยโอกาสบนเส้นทางอ่าน

แต่ “ใหม่ที่สุด” คำนวณยังไงเมื่อ replica เก็บ version vector (จากบท 1: vector clock ที่ key ด้วยผู้เขียน ใช้แยกว่า write สองอันเป็นลำดับกันหรือ concurrent)? เราเอา LUB (least upper bound = join แบบ element-wise max) ของ version vector ทั้ง read-set นั่นคือ version ที่ dominate ทุกตัว แล้วเลือก ค่า ที่ถือ version เท่ากับ LUB นั้น จุดตายที่ต้องรักษาให้ถูกคือ function relate() ที่เทียบ version vector สองตัว — มันต้องแยกออกได้สี่ทาง (Equal / Greater / Less / Concurrent) โดยต้องเช็ก ทั้ง any_gt และ any_lt; ถ้าเผลอเทียบด้วย >= อย่างเดียว มันจะยัดให้ sibling ที่ concurrent กลายเป็นมีลำดับกันเงียบๆ — bug เดียวกับ partial_cmp ที่ยัด Some ในบท 1

// Version vector: state-based semilattice, join = elementwise max.
#[derive(Clone, PartialEq, Eq, Debug)]
struct Vv(Vec<u64>);

#[derive(PartialEq, Debug)]
enum Rel {
    Equal,
    Greater,    // self is strictly newer (dominates)
    Less,       // self is strictly older
    Concurrent, // siblings: neither dominates -> conflict
}

impl Vv {
    fn zero(n: usize) -> Vv {
        Vv(vec![0; n])
    }
    // LUB / join: the least upper bound in the version-vector lattice.
    fn join(&self, other: &Vv) -> Vv {
        Vv(self.0.iter().zip(&other.0).map(|(a, b)| (*a).max(*b)).collect())
    }
    // MUST track BOTH any_gt AND any_lt: a >=-only compare silently orders siblings.
    fn relate(&self, other: &Vv) -> Rel {
        let mut any_gt = false;
        let mut any_lt = false;
        for (a, b) in self.0.iter().zip(&other.0) {
            if a > b {
                any_gt = true;
            }
            if a < b {
                any_lt = true;
            }
        }
        match (any_gt, any_lt) {
            (false, false) => Rel::Equal,
            (true, false) => Rel::Greater,
            (false, true) => Rel::Less,
            (true, true) => Rel::Concurrent,
        }
    }
}

ตัว cluster เก็บ (Vv, u64) ต่อ replica (version + ค่า) การเขียนแบบ quorum จะบวกช่องของผู้เขียนหนึ่ง (เป็น causal event ใหม่) แล้วประทับลงทุก replica ใน write-set; การอ่านแบบ read-repair ทำสามสเต็ป — คำนวณ LUB ของ read-set, เลือกค่าที่ถือ version = LUB (ถ้าไม่มีเพราะ concurrent ก็ ตั้งธง ไว้ให้ LWW/CRDT จัดการ), แล้วเขียน (LUB, value) กลับไปทุก replica ที่ยังไม่เท่ากับ LUB:

fn read_repair(&mut self, read_set: &[usize]) -> (Vv, u64, bool) {
    let mut lub = Vv::zero(self.n);
    for &i in read_set {
        lub = lub.join(&self.replicas[i].0);
    }
    // concurrency detection among the read set's versions
    let mut concurrent = false;
    for x in 0..read_set.len() {
        for y in (x + 1)..read_set.len() {
            if let Rel::Concurrent =
                self.replicas[read_set[x]].0.relate(&self.replicas[read_set[y]].0)
            {
                concurrent = true;
            }
        }
    }
    // value carried by a replica whose version already == LUB (the causal newest).
    // If none exists (concurrent), fall back to a placeholder that lessons 4-5
    // replace with an LWW clock or a CRDT merge.
    let value = read_set
        .iter()
        .find(|&&i| self.replicas[i].0 == lub)
        .map(|&i| self.replicas[i].1)
        .unwrap_or_else(|| read_set.iter().map(|&i| self.replicas[i].1).max().unwrap());
    // write the merged version + value back to stale replicas
    for &i in read_set {
        if self.replicas[i].0 != lub {
            self.replicas[i] = (lub.clone(), value);
        }
    }
    (lub, value, concurrent)
}

พิสูจน์ด้วย code: convergence, freshness และความซื่อสัตย์เรื่อง concurrency

เราตรวจสี่อย่างด้วย property test (seed คงที่ = รันซ้ำได้ 100%): (A) กฎ semilattice ของ join (commutative / associative / idempotent) บน 3000 triple — กฎเดียวกับบท 1 ที่บท 4–5 จะใช้ซ้ำ; (B) convergence ของ read-repair — หลังอ่านซ่อมแล้วทุก replica ใน read-set ต้องถือ LUB; (C) freshness ภายใต้ W+R>N — เขียน1 write ล่าสุดลง W-quorum สุ่ม แล้วอ่านจาก R-quorum สุ่มที่ W+R>N ต้อง ไม่มีทางพลาด write นั้น (นี่คือผลตอบแทนของ intersection invariant ที่ enumerate ไว้ข้างบน แต่คราวนี้ทดสอบบน cluster จริงที่มี read-repair); (D) ความซื่อสัตย์เรื่อง concurrency — write สองอันที่ concurrent ต้องถูก ตรวจเจอและตั้งธง ไม่ใช่แอบเลือกค่าให้เงียบๆ

(A) semilattice laws       : 3000 triples PASS (commutative/associative/idempotent)
(B) read-repair convergence: 2000/2000 read sets converge to LUB
(C) freshness W+R>N        : 5000 reads, 0 missed committed writes
    (of those, 0 read sets were concurrent -> LWW/CRDT territory)
(D) concurrency honesty    : sibling writes detected and FLAGGED, not silently linearized
PASS: read-repair converges, W+R>N is fresh-not-linearizable, concurrency is surfaced

สังเกตบรรทัด (C): 5000 การอ่าน 0 ครั้งที่พลาด committed write — ยืนยันว่า intersection invariant ที่เรา enumerate ในเชิงทฤษฎีทำงานจริงบน cluster ที่มีสถานะ และ “of those, 0” ที่ต่อท้ายคือความจงใจ: ในการทดสอบ (C) เราเขียน write ล่าสุด ครั้งเดียว ก่อนอ่าน — write เดียวสร้าง sibling ไม่ได้ จึงไม่มี concurrent เป็นเรื่องปกติ ส่วนกรณี concurrent จริงถูกแยกไปทดสอบใน (D) ต่างหาก ซึ่งเขียน2 write จากผู้เขียนคนละคนแล้วยืนยันว่า relate() คืน Rel::Concurrent และ read-repair ตั้งธง conc = true จริง

ความจริงที่ต้องพูดตรงๆ: fresh ไม่ใช่ linearizable

จุดที่ขายกันเกินบ่อยที่สุด: W+R>N คุมแค่ staleness ไม่ใช่ linearizability มันการันตีว่า read-set แตะ write-set ล่าสุด จึง เห็น ค่าใหม่ — แต่มันไม่ได้จัดลำดับรวมของ operation ทั้งหมด แม้ strict quorum ก็ ไม่ linearizable: การอ่านสองครั้งที่ concurrent กันสามารถเห็นค่า “ถอยหลัง” ได้ (read แรกเจอ replica ที่ซ่อมแล้ว read ที่สองไปโดน replica ที่ยังไม่ถูกซ่อม) พูดให้ตรงคือ “fresh, not linearizable” — quorum ซื้อ intersection มาให้ ไม่ได้ซื้อ consensus (DDIA บท 5/บท 9)

และเมื่อ write สองอัน concurrent จริง version vector จะ ตรวจเจอ ว่ามันเป็น sibling (neither dominates) — read-repair คำนวณ LUB ที่ dominate ทั้งคู่ได้ แต่ ค่า ที่ควรอยู่คือ conflict แท้ๆ ที่ระบบต้องเลือก เราจึง DETECT แล้ว FLAG ไม่แอบ “เอาค่า max” เพราะการทำแบบนั้นทำข้อมูลหายเงียบๆ การตัดสินว่าจะเลือกค่าไหนคือหน้าที่ของ LWW-Register หรือ CRDT ในบท 4–5 — ไม่ใช่หน้าที่ของ read-repair

sloppy quorum + hinted handoff — availability ที่แลกมาด้วย intersection

ระบบจริงอย่าง Dynamo เพิ่มลูกเล่นชื่อ sloppy quorum: ตอน partition ถ้า W replica “ที่ถูกต้อง” เอื้อมไม่ถึง มันจะเขียนลง node สำรองที่เอื้อมถึงชั่วคราวแทน แล้วให้ node นั้นถือ hinted handoff — เก็บ hint ไว้ว่า “ค่านี้จริงๆ เป็นของ node โน้น” แล้วส่งคืนเมื่อเครือข่ายกลับมา ข้อดีคือเขียนยังสำเร็จระหว่าง partition (availability ไม่ตก) แต่ราคาที่ต้องพูดตรงๆ คือ: ระหว่างที่ handoff ยังไม่เสร็จ การการันตี W+R>N intersection พังชั่วคราว เพราะ write ไปตกที่ node ที่ไม่ได้อยู่ในเซ็ต N เดิม อย่าอ้าง strict guarantee ทับ sloppy quorum — เรียกชื่อมันตรงๆ ว่ามันแลก intersection เอา availability (Dynamo SOSP 2007 / DDIA บท 5)

honesty spine ของบทนี้

เส้น scope (Thread B): quorum arithmetic เป็นข้อเท็จจริงเชิงการจัดหมู่ที่ เอ็นนิวเมอเรตครบทุก subset ได้ (22,353,252 คู่, 0 counterexample) เราจึง “ลง code รันจริง” — ต่างจาก consensus/Raft ที่ state space ของ partition/reorder ระเบิด ตรวจครบไม่ได้ จึงอยู่ใน “กล่องไดอะแกรม” (บท 8) เท่านั้น quorum ≠ consensus

ตรวจแบบมีขอบเขต ไม่ใช่บทพิสูจน์ (Thread A): ส่วน enumerate ของ quorum นั้น ครบจริง สำหรับ n ≤ 12 (จึงเป็นบทพิสูจน์ในช่วงนั้น) แต่ property test ของ read-repair (B/C/D) คือการ ตรวจแบบมีขอบเขต — ผ่าน 5000 seed แปลว่าสำรวจเฉพาะสถานะที่ splitmix64 เดินไปถึง ไม่ใช่ทุกความเป็นไปได้ (FLP 1985)

นี่คือกลไกจริงของ Dynamo/Cassandra/Riak (Thread D): quorum (W+R>N) + version vector + read-repair + hinted handoff คือ stack จริงของ Amazon Dynamo — สอนตรงตามต้นฉบับที่สเกล toy บน kaen-kvstore ไม่ใช่ของกุขึ้นเพื่อสอน

สรุปก่อนไปต่อ

บทนี้เพิ่มชั้น replication ทับ kaen-kvstore: แต่ละ key มีสำเนา N ตัว เขียนให้ ack ≥ W อ่านให้ตอบ ≥ R; กติกา W + R > N การันตีว่า write-set กับ read-set ทับกันเสมออย่างน้อย1 node (pigeonhole |W∩R| ≥ w+r−n > 0) — และเพราะมันเป็นข้อเท็จจริง สถิต เราจึง enumerate ครบทุกคู่ subset (22,353,252 คู่, n ≤ 12) เทียบ oracle max(0, w+r−n) ได้ 0 counterexample แทนที่จะสุ่มทดสอบซึ่งอาจพลาดขอบ w+r = n+1; read-repair เอา LUB ของ version vector ที่อ่านมาเขียนกลับไปกลบ replica ที่เก่า โดย relate() ต้องแยก Concurrent ออกจริง (เช็กทั้ง any_gt/any_lt ไม่ใช่ >= อย่างเดียว); property test ยืนยัน convergence 2000/2000, freshness 5000 reads 0 missed และ concurrency ถูกตั้งธงไม่แอบกลบ ที่สำคัญที่สุด — W+R>N คุม staleness ไม่ใช่ linearizability: fresh ไม่ใช่ linearizable, write ที่ concurrent ยังต้องรอ LWW/CRDT และ quorum ไม่ใช่ consensus ทุก snippet compile zero-warnings บน Rust 1.97.1 / edition 2024 / std ล้วน และรันได้เลขตามที่เห็น

บท 4 เราจะตอบคำถามที่บทนี้ค้างไว้: เมื่อ write สอง อัน concurrent จริงๆ จะ เลือกค่า อย่างไรให้ replica ลู่เข้าหากันเองโดยไม่ต้อง coordinate — คำตอบคือ CRDT และกฎ semilattice (merge = join ที่ commutative/associative/idempotent) ที่เราเห็นเค้าโครงมาตั้งแต่บท 1 จะเป็นทฤษฎีบทเต็มตัวในบทหน้า

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

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

David K. Gifford — “Weighted Voting for Replicated Data” (SOSP 1979) (เข้าถึง 2026-07-24) — ต้นกำเนิดของ quorum voting: การกำหนดน้ำหนักเสียงให้ write/read quorum ทับกันเพื่อการันตีว่าอ่านเห็นเขียนล่าสุด รากของกฎ W+R>N
Martin Kleppmann — “Designing Data-Intensive Applications” (DDIA), บท 5 Replication + บท 9 Consistency & Consensus (2017) (เข้าถึง 2026-07-24) — quorum W+R>N คุม staleness ไม่ใช่ linearizability; sloppy quorum + hinted handoff แลก intersection เอา availability; write ที่ concurrent ต้องใช้ LWW/CRDT เลือกค่า
DeCandia et al. — “Dynamo: Amazon’s Highly Available Key-value Store” (SOSP 2007) (เข้าถึง 2026-07-24) — stack จริงที่รวม quorum + version vector + read-repair + hinted handoff ที่บทนี้ย่อสเกลลงมาสอน

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

ข้อ 1 / 3

ทำไมเราถึง enumerate ทุกคู่ (write-set, read-set) แทนที่จะสุ่มทดสอบว่า W+R>N การันตีการทับกัน?

Quorum R/W/N และ read-repair — ทำไม W+R>N ถึง​การันตี​การ​ทับ​กัน

กติกา N / W / R และ​การ​ทับ​กัน​แบบ​รับประกัน

ทำไม​ต้อง enumerate ไม่ใช่​สุ่ม​ทดสอบ

read-repair: เขียน​ค่าที่ merge แล้วกลับ​ไป​กลบ​ตัว​ที่​เก่า

พิสูจน์​ด้วย code: convergence, freshness และ​ความ​ซื่อสัตย์​เรื่อง concurrency

ความ​จริง​ที่​ต้อง​พูดตรงๆ: fresh ไม่ใช่ linearizable

สรุป​ก่อน​ไป​ต่อ