OR-Set และ CRDT ในฐานะชนิดของ value ใน kaen-kvstore

บท 4 เราสร้าง CRDT แบบ state-based ที่ลู่เข้าได้เองด้วยกฎ semilattice — G-Counter, PN-Counter และ LWW-Register — โดยไม่ต้อง coordinate เลย ตราบใดที่ merge เป็น join ที่ commutative + associative + idempotent ทุกอย่างในบทนั้นเป็น “ตัวนับ” หรือ “ค่าเดียว” ที่ โตทางเดียว ล้วนๆ ซึ่งเป็นเหตุผลว่าทำไมมันง่าย

บทนี้เราชนกำแพงที่ยากที่สุดของ CRDT ตรงๆ: การลบ — เซ็ตที่ทั้ง add และ remove ได้ แล้วยังลู่เข้าถูกต้อง คำถามคือ ถ้า node หนึ่งลบ element ขณะที่อีก node เพิ่ม element เดิมกลับพร้อมกัน (concurrent) ผลควรเป็นอะไร คำตอบของ OR-Set คือ add-wins และกลไกที่ทำให้มันถูกต้องคือหัวใจของบทนี้ จากนั้นเราจะทำสิ่งที่ทั้งคอร์สเดินมาถึง: จับ CRDT ยัดเป็นชนิดของ value ใน kaen-kvstore เพื่อให้การ “เขียน” กลายเป็นการ “merge” ไม่ใช่ทับ — เป็นเมล็ดพันธุ์ของ capstone บท 8

📦 kaen-kvstore

คอร์สนี้ ต่อยอด repo kaen-kvstore จาก #22 (code ตัวอย่างกำลังจัดทำ) — บทนี้พา CRDT ออกจาก “โปรแกรม demo แยกเดี่ยว” มาเป็น ชนิดของ value ที่ store เก็บจริง: ค่าที่เก็บคือ byte encode ของสถานะ CRDT ผ่าน wire แบบ length-prefixed ของ #22 (to_le_bytes/from_le_bytes, ไม่มี serde) แล้ว merge_put = decode → merge → encode ทำให้ “write = merge” ตามกฎ semilattice ของบท 4 — การลู่เข้าจึงพิสูจน์ได้ถึงระดับ byte ทุกเลขด้านล่างคือ output จริงจาก Rust std ล้วนที่รันซ้ำได้ byte-identical

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

ทุก snippet pin ที่ Rust stable 1.97.1 (ออก 2026-07-16) และ edition = “2024” [dependencies] ว่างเปล่า — ZERO external crate บทนี้แตะ std เพียง std::collections (BTreeMap, BTreeSet, HashMap) กับ integer to_le_bytes/from_le_bytes เท่านั้น — สถานะ CRDT หนุนหลังด้วย BTreeMap/BTreeSet (เรียงแล้ว) เสมอ เพื่อให้ สถานะเท่ากัน encode เป็น byte เท่ากัน (ถ้าใช้ HashMap/HashSet ลำดับ iteration จะสุ่ม → byte ต่างทั้งที่สถานะเดียวกัน = การลู่เข้าจอมปลอม) ทุกโปรแกรม compile zero-warnings และรันจริง

ทำไม “การลบ” ถึงยากสำหรับ CRDT: กับดักของ 2P-Set ดิบ

ลองออกแบบเซ็ตที่ลบได้แบบตรงไปตรงมาที่สุด — 2P-Set (two-phase set): เก็บ grow-only set สองชุด ชุด added กับชุด removed การ contains(e) = e ∈ added ∧ e ∉ removed merge ก็แค่ union ทั้งสองชุด กฎ semilattice ผ่านหมด (union คือ join) compile สวย ลู่เข้าได้จริง

แต่มันมี bug เชิงความหมายที่ร้ายแรง — นี่คือ ❌ version ดิบ: พอ element ตกไปอยู่ใน removed แล้ว มัน เพิ่มกลับไม่ได้ตลอดกาล เพราะ removed โตทางเดียว ไม่มีวันเอา element ออกจากมันได้ ในโลกจริงนี่คือหายนะ: ลูกค้าลบ “นม” ออกจากตะกร้า แล้วเปลี่ยนใจกดเพิ่ม “นม” กลับ — 2P-Set จะยืนยันหน้าตายว่า “นม” ถูกลบไปแล้ว เพิ่มไม่ได้ พฤติกรรมที่เรา อยาก ได้คือ การเพิ่มครั้งใหม่ควรลบล้างการลบครั้งเก่า — แต่ 2P-Set แยก “นม ตัวเดิมที่เคยลบ” ออกจาก “นม ตัวใหม่ที่เพิ่งเพิ่ม” ไม่ได้ เพราะมันจำแค่ ค่า ไม่ได้จำ ตัวตนของแต่ละ add

OR-Set: ทุก add มี tag ที่ไม่ซ้ำ, remove ลบได้เฉพาะที่ “เห็นแล้ว”

ทางแก้คือ OR-Set (Observed-Remove Set, Shapiro et al. 2011, Specification 12) ไอเดียกลาง: แยกตัวตนของแต่ละ add ออกจากค่าของมัน ทุกครั้งที่ add(e) เราแนบ tag ที่ไม่ซ้ำทั้งระบบ ให้ element นั้น ส่วน remove(e) จะ tombstone เฉพาะ tag ที่ node นี้ เห็นแล้ว เท่านั้น — นี่คือที่มาของชื่อ observed-remove contains(e) เป็นจริงก็ต่อเมื่อ e มี add-tag อย่างน้อยหนึ่งอันที่ ยังไม่ถูก tombstone

กลไกนี้ทำให้ re-add ที่ concurrent รอด: ตอน node B เพิ่ม element กลับ มันแนบ tag ใหม่ ที่ node A (ตัวที่สั่งลบ) ยัง ไม่เคยเห็น — remove ของ A จึง tombstone ไม่ถึง tag ใหม่ตัวนี้ นี่คือ add-wins

use std::collections::{BTreeMap, BTreeSet};

#[derive(Clone, Debug, PartialEq, Eq)]
struct OrSet {
    adds: BTreeMap<Vec<u8>, BTreeSet<u64>>, // element -> tags ที่เคยถูก add
    tombs: BTreeSet<u64>,                    // tags ที่ถูก remove (observed-remove)
}
impl OrSet {
    fn new() -> Self {
        Self { adds: BTreeMap::new(), tombs: BTreeSet::new() }
    }
    // add: แนบ tag ที่ไม่ซ้ำทั้งระบบให้ element
    fn add(&mut self, elem: &[u8], tag: u64) {
        self.adds.entry(elem.to_vec()).or_default().insert(tag);
    }
    // remove: tombstone เฉพาะ tag ที่ 'เห็นแล้ว' ณ ตอนนี้เท่านั้น
    fn remove(&mut self, elem: &[u8]) {
        if let Some(tags) = self.adds.get(elem) {
            for &t in tags {
                self.tombs.insert(t);
            }
        }
    }
    fn contains(&self, elem: &[u8]) -> bool {
        match self.adds.get(elem) {
            Some(tags) => tags.iter().any(|t| !self.tombs.contains(t)),
            None => false,
        }
    }
    // merge = union ของ add-tags (ต่อ element) ∪ union ของ tombstones
    // => 2 grow-only-set join รวมกัน = comm/assoc/idempotent มาฟรี
    fn merge(&self, other: &Self) -> Self {
        let mut out = self.clone();
        for (elem, tags) in &other.adds {
            let e = out.adds.entry(elem.clone()).or_default();
            for &t in tags {
                e.insert(t);
            }
        }
        for &t in &other.tombs {
            out.tombs.insert(t);
        }
        out
    }
    fn elements(&self) -> Vec<Vec<u8>> {
        self.adds.keys().filter(|k| self.contains(k)).cloned().collect()
    }
}

tag ต้องไม่ซ้ำ 'ทั้งระบบ' ไม่ใช่ต่อ node

หัวใจความถูกต้องอยู่ที่ tag ต้อง unique ทั้ง cluster วิธีมาตรฐานคือประกอบจาก (node_id << 40) | local_counter — เอา id ของ node ขึ้น bit สูง ต่อด้วยตัวนับ monotonic ในเครื่อง ห้าม derive tag จาก ค่า ของ element หรือจาก wall-clock เด็ดขาด ถ้า2 node บังเอิญใช้ tag เดียวกันสำหรับ add คนละครั้ง การ remove ฝั่งหนึ่งจะ เงียบๆ ฆ่า add ที่ concurrent ของอีกฝั่งทิ้ง — กฎ semilattice ยังผ่านหมด (มันยังลู่เข้า) แต่ ความหมาย ผิด นี่คือ bug ประเภทที่ compiler กับ property test กฎ merge จับไม่ได้ ต้องออกแบบ tag ให้ถูกตั้งแต่ต้น

เดินเรื่อง: concurrent add ‖ remove แล้ว add ชนะ

เอาสถานการณ์ตะกร้าสินค้ามารันจริง — ทั้ง2 node เห็น apple@tag1 อยู่ก่อน แล้ว A สั่งลบ (tombstone tag1) ขณะที่ B เพิ่ม apple กลับด้วย tag2 ที่ยังไม่เคยเห็น (concurrent):

let tag1: u64 = (1u64 << 40) | 0;
let tag2: u64 = (2u64 << 40) | 0;
let mut a = OrSet::new();
let mut b = OrSet::new();
a.add(b"apple", tag1);
b.add(b"apple", tag1); // ทั้งคู่เห็น add เดิม
a.remove(b"apple");    // A tombstone tag1
b.add(b"apple", tag2); // B re-add ด้วย tag ใหม่ที่ยังไม่เห็น
let merged = a.merge(&b);
println!("concurrent add||remove -> contains(apple) = {} (add wins)", merged.contains(b"apple"));

// add แล้ว remove บน node เดียว => หายไปตามคาด
let mut c = OrSet::new();
c.add(b"pear", (1u64 << 40) | 5);
c.remove(b"pear");
println!("add then remove -> contains(pear) = {}", c.contains(b"pear"));

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

concurrent add||remove -> contains(apple) = true (add wins)
add then remove -> contains(pear) = false

หลัง merge สถานะคือ adds{apple:{tag1, tag2}} กับ tombs{tag1} — contains(apple) ไล่ tag ของ apple เจอว่า tag2 ไม่ อยู่ใน tombstones จึงคืน true: add ชนะ ตรงข้ามกับ 2P-Set ดิบที่จะบอกว่า apple ถูกลบถาวร ส่วน pear ที่ add แล้ว remove บน node เดียว (เห็น tag ตัวเองครบ) ถูก tombstone หมดจึงคืน false ถูกต้อง

merge ของ OR-Set คือ join ของ semilattice (ได้มาฟรี)

merge ของ OR-Set ไม่มีอะไรมากไปกว่า union ของ grow-only set สองก้อน: union ของ add-tags (ทีละ element) ∪ union ของ tombstones set union เป็น join ของ semilattice อยู่แล้ว — commutative, associative, idempotent — ดังนั้น OR-Set ที่ประกอบจาก grow-only set สองชุดจึง สืบทอด สามกฎนี้มา โดยไม่ต้องพิสูจน์ใหม่ นี่คือลีลาการออกแบบ CRDT ที่สำคัญ: ประกอบของใหม่จาก semilattice ที่รู้แล้วว่าลู่เข้า แทนที่จะคิด merge law ขึ้นเองแล้วเสี่ยงพลาด

เราพิสูจน์ด้วย property test เดิมจากบท 4 — สุ่ม OR-Set สามก้อนด้วย splitmix64 (seed 0x000F_5E70, 3000 เคส) แล้วยืนยันทั้งสามกฎทุกเคส:

let seed: u64 = 0x000F_5E70;
let mut rng = SplitMix64::new(seed);
let (mut checks, mut violations) = (0u64, 0u64);
for _ in 0..3000 {
    let x = random_orset(&mut rng);
    let y = random_orset(&mut rng);
    let z = random_orset(&mut rng);
    if x.merge(&y) != y.merge(&x) { violations += 1; }          // commutative
    checks += 1;
    if x.merge(&y).merge(&z) != x.merge(&y.merge(&z)) { violations += 1; } // associative
    checks += 1;
    if x.merge(&x) != x { violations += 1; }                    // idempotent
    checks += 1;
}

หมายเหตุ: random_orset(&mut rng) ไม่ได้กาง code body ไว้ตรงนี้ — มันคือคู่อนาล็อกแบบ OR-Set ของตัวสุ่มจากบท 4 ที่สุ่มบน element universe เล็ก (a–d) กับ tag id 0–7 (จึงทำให้ tag ชนกันข้ามก้อนบ่อย merge/tombstone interaction ไม่เป็นสุญญากาศ)

--- OR-Set semilattice laws (seed=0x000f5e70, 3000 cases) ---
commutative + associative + idempotent : checks=9000 violations=0
ALL OR-Set semilattice laws hold.

9000 checks, 0 violations — 3000 เคส × 3 กฎ เพราะ random_orset สุ่มบน element universe เล็ก (a,b,c,d) กับ tag universe เล็ก (0–7) tag จึงชนกันข้ามก้อนบ่อย ทำให้ merge/tombstone interaction ไม่เป็นสุญญากาศ การเทียบเท่ากันใช้ derived Eq บน BTreeMap/BTreeSet ที่เทียบเชิงโครงสร้างตามลำดับเรียง จึงถูกต้องโดยไม่ต้องเขียน PartialEq เอง (ต่างจาก vector clock ในบท 1 ที่ implicit-zero บังคับให้เขียนเอง)

sequenceDiagram
    participant A as replica A
    participant B as replica B
    Note over A,B: ทั้งคู่เห็น apple@tag1
    Note over A: remove(apple) → tombstone {tag1}
    Note over B: add(apple, tag2) — re-add ที่ concurrent, tag ใหม่ยังไม่ถูกเห็น
    A->>B: ส่ง state adds{apple:{tag1}}, tombs{tag1}
    B->>A: ส่ง state adds{apple:{tag1,tag2}}
    Note over A,B: merge → adds{apple:{tag1,tag2}}, tombs{tag1}<br/>tag2 ไม่อยู่ใน tombs → contains(apple)=true

คำบรรยายภาพ: add-wins — การ re-add ที่ concurrent พก tag2 ตัวใหม่ที่ยังไม่มีใคร tombstone หลัง merge สองทาง tag2 จึงรอด และ apple ยังอยู่ในเซ็ต ต่างจาก 2P-Set ดิบที่ลบแล้วเพิ่มกลับไม่ได้ตลอดกาล

แล้ว LWW-map ล่ะ — และความจริงที่ต้องพูด: LWW ทิ้ง write ที่ concurrent

OR-Set แก้ปัญหา “เก็บทุก add ไว้แล้วให้ add ชนะ” แต่บางครั้งเราไม่ได้อยากเก็บทุกอย่าง — เราอยากได้ ค่าล่าสุดค่าเดียว ต่อ key เช่น field โปร file นั่นคืองานของ LWW-Register ที่บท 4 สร้างไว้ (Last-Write-Wins: เก็บค่าที่ (ts, node) สูงสุด) ขยายเป็น LWW-map ก็แค่ BTreeMap จาก key ไปหา LWW-Register แล้ว merge ทีละ key

แต่ต้องพูดตรงๆ ให้ครบ: LWW ทิ้ง write ที่ concurrent ทิ้งอย่างเงียบๆ โดย design (Kleppmann, DDIA ch5) ถ้า2 node เขียน key เดียวกันแบบ concurrent มีแค่ค่าเดียวที่ (ts, node) สูงกว่าที่รอด อีกค่า หายไปโดยไม่มีร่องรอย — ไม่มีการ merge ค่า ไม่มี sibling ให้เห็น เทียบกับ OR-Set/PN-Counter ที่ รักษา ทุก operation ที่ concurrent ไว้ LWW เลือก “เรียบง่ายและค่าเดียว” แลกกับ “ยอมทำ update หาย” นี่คือเหตุผลที่ LWW ห้ามใช้กับตะกร้าสินค้า ยอดเงิน หรือเซ็ต (ใช้ OR-Set/PN-Counter แทน) แต่โอเคกับ field ที่ “ค่าล่าสุดถูกเสมอ”

tie-break ของ LWW ต้อง deterministic เสมอ

timestamp อย่างเดียว ไม่ใช่ total order — 2 node ประทับ ts เดียวกันได้ ถ้าตอน ts เท่ากันแล้ว merge ไม่ตัดสินให้เด็ดขาด merge จะเลิกเป็น commutative (A merge B ได้ค่าหนึ่ง, B merge A ได้อีกค่า → ไม่ลู่เข้า) ทางแก้คือใส่ tie-break ที่ deterministic เข้าไปในลำดับ — เทียบเป็น tuple (ts, node, value) ครบทุกชั้น อย่างที่บท 4 ทำ node id จึงตัดสินตอน ts เสมอ ค่าที่ได้จึงไม่ขึ้นกับลำดับ merge นี่คือเงื่อนไขที่ทำให้ LWW ยังเป็น CRDT ที่ถูกต้อง

จับ CRDT ยัดเป็น value ของ kaen-kvstore: “write = merge”

ตอนนี้ถึงจุดที่ทั้งคอร์สเดินมา — เอา CRDT ไป เป็นชนิดของ value ที่ store เก็บจริง ใน kaen-kvstore ปกติ store คือ key → bytes และ “write” คือ ทับ ค่าเดิม แต่ถ้าเราให้ value เป็น byte-encode ของ CRDT แล้วนิยาม write ใหม่เป็น merge_put = decode → merge → encode การเขียนจะกลายเป็นการ merge ไม่ใช่ทับ — และการลู่เข้าจะพิสูจน์ได้ถึงระดับ byte

encode ใช้ wire แบบ length-prefixed ของ #22 ตรงๆ ไม่มี serde: นับจำนวน entry เป็น u32, ต่อด้วย key (length-prefixed) และ tag แต่ละตัวเป็น u64 ผ่าน to_le_bytes กุญแจสำคัญคือหนุนสถานะด้วย BTreeMap/BTreeSet ที่เรียงแล้ว — สถานะที่เท่ากันจึง encode ออกมาเป็น byte ที่เท่ากันเป๊ะ (byte-canonical) ทำให้ “byte เท่ากัน” เป็นพยานของ “ลู่เข้าแล้ว”:

fn encode(set: &OrSet) -> Vec<u8> {
    let mut out = Vec::new();
    out.extend_from_slice(&(set.adds.len() as u32).to_le_bytes());
    for (elem, tags) in &set.adds {            // BTreeMap => ลำดับ key คงที่
        out.extend_from_slice(&(elem.len() as u32).to_le_bytes());
        out.extend_from_slice(elem);
        out.extend_from_slice(&(tags.len() as u32).to_le_bytes());
        for &t in tags {                       // BTreeSet => ลำดับ tag คงที่
            out.extend_from_slice(&t.to_le_bytes());
        }
    }
    out.extend_from_slice(&(set.tombs.len() as u32).to_le_bytes());
    for &t in &set.tombs {
        out.extend_from_slice(&t.to_le_bytes());
    }
    out
}

ฝั่งอ่านใช้ Cursor เดินไล่ byte (อ่าน u32/u64 ผ่าน from_le_bytes, อ่าน frame ที่ length-prefixed) แล้ว decode กลับเป็น OrSet ส่วน store เก็บ value เป็น HashMap<Vec<u8>, Vec<u8>> (key → encoded CRDT bytes) และ merge_put ทำงานสามจังหวะ:

struct KvStore {
    map: HashMap<Vec<u8>, Vec<u8>>,
}
impl KvStore {
    // wire = 1 frame length-prefixed ที่พก encoded OR-Set state
    fn merge_put(&mut self, key: &[u8], wire: &[u8]) {
        let mut cur = Cursor::new(wire);
        let payload = cur.frame();
        let incoming = decode(&payload);
        let current = self.map.get(key).map(|b| decode(b)).unwrap_or_else(OrSet::new);
        let merged = current.merge(&incoming);      // <-- write = merge, ไม่ใช่ทับ
        self.map.insert(key.to_vec(), encode(&merged));
    }
}

ทดสอบสมบัติที่สำคัญที่สุด — ลู่เข้าถึงระดับ byte ภายใต้ reorder + duplicate: 2 node เก็บตะกร้าเดียวกันใต้ key cart:42 node 1 เพิ่ม milk, เพิ่ม apple, แล้ว ลบ apple; node 2 re-add apple ด้วย tag ใหม่ (concurrent) แล้วเพิ่ม bread แต่ละฝั่งส่งสถานะเป็น frame แล้ว node 1 รับ frame ซ้ำ (duplicate) ส่วน node 2 รับ2 frame ในลำดับกลับกัน (reversed):

let frame1 = put_frame(&encode(&local1)); // สถานะ node 1
let frame2 = put_frame(&encode(&local2)); // สถานะ node 2

let mut node1 = KvStore::new();
node1.merge_put(b"cart:42", &frame1);
node1.merge_put(b"cart:42", &frame2);
node1.merge_put(b"cart:42", &frame2); // DUPLICATE — idempotent no-op

let mut node2 = KvStore::new();
node2.merge_put(b"cart:42", &frame2);
node2.merge_put(b"cart:42", &frame1); // ลำดับกลับกันกับ node1

let identical = node1.value_bytes(b"cart:42") == node2.value_bytes(b"cart:42");

converged cart:42 bytes identical on both nodes = true
converged members = ["apple", "bread", "milk"] (apple survived via add-wins)
stored value size = 86 bytes

node 1 รับ frame ซ้ำหนึ่งครั้ง node 2 รับกลับลำดับ แต่ byte ที่เก็บสุดท้ายเท่ากันเป๊ะ — idempotent ทำให้ frame ซ้ำเป็น no-op, commutative ทำให้ลำดับไม่มีผล นี่คือกฎ semilattice ของบท 4 ทำงานถึงระดับ byte จริงๆ ไม่ใช่แค่ระดับ logical state และ apple รอดมาอยู่ในสมาชิกด้วย add-wins (tag ที่ re-add ไม่ถูก tombstone) ค่า 86 bytes นั้น pin กับ encoding นี้ + tag ที่ใช้ — เปลี่ยน layout หรือ tag เมื่อไหร่เลขก็เปลี่ยน แต่ในเงื่อนไขคงที่นี้มันซ้ำได้ 100%

tombstones โตทางเดียว — toy นี้ไม่มี GC (พูดตรงๆ)

tombs ใน OR-Set (และ metadata ของ CRDT ทุกตัว) โตทางเดียวเท่านั้น ลบ element เยอะๆ tombstones ก็บวมไม่หยุด ระบบจริง (Riak, Akka) ต้องมี causal-stability pruning — ตัด tag/tombstone ที่ทุก replica เห็นครบแล้วทิ้งได้ (Shapiro et al. 2011 §3.3) แต่ toy ในบทนี้ ไม่ทำ GC เลย และนั่นคือขอบเขตที่เราตั้งใจไว้: เราพิสูจน์ ความถูกต้องของการลู่เข้า ให้ครบ ส่วนการ prune ที่ถูกต้อง (ต้องรู้ว่า operation ใด causally stable แล้ว) เป็นอีกชั้นที่ production ต้องมี — บทนี้เอ่ยถึงแต่ไม่ลง code

honesty spine ของบทนี้

D — นี่คือกลไกจริงของ Dynamo/Riak: OR-Set กับ CRDT-as-value คือหัวใจของ Riak Data Types และ Dynamo-style store จริง ไม่ใช่ของกุขึ้นเพื่อสอน — เราลงตาม Shapiro et al. 2011 (Specification 12) ที่สเกล toy บน kaen-kvstore

A — Rust พิสูจน์ความถูกต้อง “ในเครื่องเดียว”: compiler การันตีว่า encode/decode ไม่มี memory bug แต่ มันมองไม่เห็น ว่า merge law ถูกหรือเปล่า — property test 9000 checks คือ ออราเคิล ของการลู่เข้า และมันคือการ ตรวจแบบมีขอบเขต ไม่ใช่บทพิสูจน์ ผ่าน 3000 เคสแปลว่าสำรวจเฉพาะ OR-Set ที่ seed เดินไปถึง ที่ร้ายกว่านั้น: tag ที่ไม่ unique จะทำให้ semantics ผิดทั้งที่กฎ merge ยังผ่านหมด — เป็น bug ที่อยู่นอกสายตาทั้ง compiler และ property test กฎ ต้องออกแบบ tag ให้ถูก

C — ดีเทอร์มินิสซึมคือวินัย: seed คงที่ (0x000F_5E70) + BTreeMap/BTreeSet แทน HashMap/HashSet ทุกที่ที่ลำดับ iteration ป้อน byte-canonical convergence มิฉะนั้นสถานะเดียวกันจะ encode ต่าง byte = การลู่เข้าจอมปลอม

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

บทนี้ปิดช่องว่างที่ยากที่สุดของ CRDT — การลบ — และพา CRDT ลงไปอยู่ใน store จริง: 2P-Set ดิบลบแล้วเพิ่มกลับไม่ได้ตลอดกาลเพราะจำแค่ค่าไม่จำตัวตนของ add; OR-Set แก้ด้วยการแนบ tag ที่ไม่ซ้ำ ให้ทุก add แล้ว remove tombstone เฉพาะ tag ที่เห็นแล้ว → re-add ที่ concurrent พก tag ใหม่จึงรอด = add-wins; merge = union ของ grow-only set สองชุด จึงได้ comm/assoc/idempotent มาฟรี (9000 checks, 0 violations); LWW-Register ที่ขยายเป็น LWW-map นั้นเรียบง่ายแต่ ทิ้ง write ที่ concurrent อย่างเงียบๆ โดย design — ห้ามใช้กับตะกร้า/ยอดเงิน/เซ็ต และ tie-break ต้อง deterministic; สุดท้ายเราจับ CRDT เป็น value ของ kaen-kvstore ผ่าน wire length-prefixed ของ #22 ทำให้ “write = merge” และพิสูจน์การลู่เข้าถึงระดับ byte (86 bytes เท่ากันเป๊ะ2 node) ภายใต้ reorder + duplicate; tombstones โตทางเดียว toy นี้ไม่ GC (พูดตรงๆ) ทุก snippet compile zero-warnings บน Rust 1.97.1 / edition 2024 / std ล้วน และรันได้เลขตามที่เห็น

บท 6 เราจะทำให้ replica เทียบและ sync กันเองอย่างมีประสิทธิภาพ: ตอนนี้เรารู้แล้วว่า value ที่ merge ได้หน้าตาเป็นอย่างไร บทหน้าถามว่า 2 node จะรู้ได้เร็วๆ ว่าตรงไหน diverge โดยไม่ต้องส่งข้อมูลทั้งก้อนมาเทียบ — คำตอบคือ Merkle tree ที่เทียบ root ก่อนแล้วลงเฉพาะ subtree ที่ต่าง (anti-entropy) กับ gossip ที่กระจายข่าวแบบระบาดใน O(log N) รอบ

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

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

Shapiro, Preguiça, Baquero, Zawirski — “A Comprehensive Study of Convergent and Commutative Replicated Data Types” (INRIA RR-7687, 2011) (เข้าถึง 2026-07-24) — Specification 12 คือ OR-Set (observed-remove, add-wins) ต้นฉบับ: ทุก add ติด unique tag, remove ลบเฉพาะ tag ที่เห็นแล้ว, merge = union; §3.3 พูดเรื่อง causal-stability pruning ของ tombstones
Martin Kleppmann — “Designing Data-Intensive Applications” ch5 (Replication), 2017 (เข้าถึง 2026-07-24) — LWW เก็บ write ที่ timestamp สูงสุดและ ทิ้ง write ที่ concurrent อย่างเงียบๆ (lossy by design); เหตุผลที่ตะกร้า/ยอดเงินต้องใช้ CRDT ที่รักษา operation ไว้แทน

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

ข้อ 1 / 3

ทำไม OR-Set ถึงทำให้ re-add ที่ concurrent กับ remove 'รอด' (add-wins) ในขณะที่ 2P-Set ดิบทำไม่ได้?

OR-Set และ CRDT ใน​ฐานะ​ชนิด​ของ value ใน kaen-kvstore

ทำไม “การ​ลบ” ถึง​ยาก​สำหรับ CRDT: กับดัก​ของ 2P-Set ดิบ

OR-Set: ทุก add มี tag ที่​ไม่​ซ้ำ, remove ลบ​ได้​เฉพาะ​ที่ “เห็น​แล้ว”

เดิน​เรื่อง: concurrent add ‖ remove แล้ว add ชนะ

merge ของ OR-Set คือ join ของ semilattice (ได้​มา​ฟรี)

แล้ว LWW-map ล่ะ — และ​ความ​จริง​ที่​ต้อง​พูด: LWW ทิ้ง write ที่ concurrent

จับ CRDT ยัด​เป็น value ของ kaen-kvstore: “write = merge”

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