Tombstones และ compaction — ทวงคืนพื้นที่โดยไม่ทำลายความถูกต้อง

บท2 ทำให้ข้อมูลรอดการปิดโปรแกรมด้วย append-only log + hash index (model Bitcask) และบท3 ทำให้มัน ทน crash ด้วยลำดับ write → fsync → ack แต่ทั้งสองบทค้างประเด็นหนึ่งไว้ตรงๆ: file log โตไม่มีที่สิ้นสุด เพราะเราเขียนต่อท้ายอย่างเดียว ไม่เคยแก้ที่เดิม ทุก overwrite และทุก delete แค่ append record ใหม่ ทิ้งของเก่าให้ตายคา file บทนี้แก้สองเรื่องที่พันกัน: DELETE จะบันทึกอย่างไรในโลกที่ห้ามลบ และเราจะเก็บกวาด dead record ทิ้งอย่างไรโดย ไม่ทำลายความถูกต้อง แม้ crash กลางการเก็บกวาด

แนวคิดทั้งสองนี้ไม่ใช่ของที่เราคิดขึ้นเอง — มัน map กับ storage engine จริงตรงๆ: การมาร์คลบด้วย record พิเศษคือ delete marker และการเขียนเฉพาะของที่ยังมีชีวิตลง file ใหม่คือ segment merge & compaction ของ LSM/SSTable ที่ Petrov และ Kleppmann อธิบายไว้

📦 kaen-kvstore

code ลงมือของคอร์สนี้อยู่ใน repo kaen-kvstore (code ตัวอย่างกำลังจัดทำ) — repo ยืนเดี่ยวของคอร์สนี้เอง บทนี้ต่อยอด store จากบท3: เพิ่ม tombstone record สำหรับ DELETE และ method compact() ที่ทวงคืนพื้นที่แบบ crash-safe ทุก snippet ด้านล่างตัดมาจากโปรแกรมเดียวที่ compile ผ่าน (cargo check) และรันจริงบน musl (Rust 1.97.1 / edition 2024 / std ล้วน) — ตัวเลขที่ยกมาเป็นผลรันจริง ไม่ใช่ตัวเลขสมมติ

ปัญหา: log โตตามจำนวน operation ไม่ใช่จำนวน key

ทวนโครงจากบท2–3: store เก็บ index: HashMap<String, u64> จาก key → offset ของ record ล่าสุดใน file ทุก set append record [key_len u32][val_len u32][key][val] ต่อท้าย แล้วขยับ index ให้ชี้ offset ใหม่ ผลที่ตามมาคือถ้าเราเขียนทับ key เดิม 1000 ครั้ง file จะมี record ของ key นั้น 1000 อัน แต่มีเพียงอันสุดท้ายที่ index ชี้อยู่ อีก 999 อันคือ dead record — กินพื้นที่ disk ถ่วงเวลา replay ตอน boot แต่ไม่มีใครอ่านถึงอีกแล้ว

พูดให้ตรง: log โตตามจำนวน write operation ไม่ใช่จำนวน key ที่ยังมีชีวิต นี่เป็นราคาที่ append-only storage ทุกตัวต้องจ่าย — คุณแลกความเรียบง่ายกับความทนทาน (เขียนแบบ sequential, crash ได้แค่ tail ขาด) ด้วยการยอมให้ file บวม แล้วค่อยมีกลไกเก็บกวาดตามหลัง กลไกนั้นคือ compaction

DELETE ในโลกที่ห้ามลบ: tombstone

คำถามแรกที่คมกว่าที่คิด: ใน file ที่ append อย่างเดียว เราจะ “ลบ” key ได้อย่างไร?

version ดิบที่ผุดขึ้นในหัวก่อนคือ seek ไปที่ record เดิมแล้วเขียนทับ byte ให้เป็นศูนย์ หรือย้าย record ท้ายๆ มาถมช่องว่าง — ผิดทั้งคู่ มันทำลาย invariant ของ append-only log (การเขียนต้อง sequential และ record ที่เขียนแล้วต้อง immutable) และเปิดช่องให้ crash กลางการแก้ทำ record ที่ ยังมีชีวิต พังไปด้วย ทั้งที่ทั้งบทเรากันไม่ให้ crash แตะ record เก่าได้เลย

คำตอบที่ถูกคือ tombstone — record พิเศษที่ append ต่อท้าย log เพื่อ มาร์ค ว่า key นี้ถูกลบ ไม่ใช่การลบ byte เดิมทันที เราใช้ค่า sentinel ในช่อง val_len: ถ้า val_len == u32::MAX แปลว่า record นี้เป็น tombstone และ ไม่มี value bytes ตามหลัง (มีแต่ key หลัง header) — ต่างจาก Set record ปกติที่มี value bytes เสมอ

const TOMBSTONE: u32 = u32::MAX; // val_len sentinel = a delete

enum Command {
    Set { key: String, value: String },
    Delete { key: String },
}

// [key_len u32 LE][val_len u32 LE][key bytes][val bytes]
// val_len == u32::MAX => tombstone (no value bytes follow).
fn write_record<W: Write>(w: &mut W, cmd: &Command) -> io::Result<()> {
    match cmd {
        Command::Set { key, value } => {
            let kb = key.as_bytes();
            let vb = value.as_bytes();
            w.write_all(&(kb.len() as u32).to_le_bytes())?;
            w.write_all(&(vb.len() as u32).to_le_bytes())?;
            w.write_all(kb)?;
            w.write_all(vb)?;
        }
        Command::Delete { key } => {
            let kb = key.as_bytes();
            w.write_all(&(kb.len() as u32).to_le_bytes())?;
            w.write_all(&TOMBSTONE.to_le_bytes())?; // val_len == u32::MAX marks the tombstone
            w.write_all(kb)?; // NO value bytes
        }
    }
    Ok(())
}

delete() จึงหน้าตาเหมือน set() เป๊ะ — สร้าง record, append, sync_data() ให้ durable ตามลำดับของบท3, แล้วค่อย index.remove() การลบเป็น การเขียน อีกครั้งหนึ่ง ไม่ใช่การแก้ที่เดิม:

fn delete(&mut self, key: &str) -> io::Result<()> {
    let mut buf = Vec::new();
    write_record(&mut buf, &Command::Delete { key: key.to_string() })?; // append a tombstone
    self.file.seek(SeekFrom::Start(self.write_pos))?;
    self.file.write_all(&buf)?;
    self.file.sync_data()?;
    self.index.remove(key); // replay will do the same from the tombstone
    self.write_pos += buf.len() as u64;
    Ok(())
}

replay ที่รู้จัก tombstone

ตรงนี้คือกิ่งที่ ใหม่ เทียบกับ replay ในบท2–3 ซึ่งเห็นแต่ Set record ตอน boot เราสแกน log จากต้นจนจบ ทีละ record: Set สั่ง index.insert (record ที่มาทีหลังชนะโดยอัตโนมัติเพราะ insert ทับ key เดิม) ส่วน Delete/tombstone สั่ง index.remove — พอถึง EOF (read_record คืน None เมื่อ read_exact เจอ UnexpectedEof) ก็จบ สถานะสุดท้ายใน HashMap คือ “ค่าล่าสุดของทุก key ที่ยังไม่ถูก tombstone ตามมาปิด”

// Tombstone-aware replay: SET => insert (latest wins); DELETE => remove.
fn build_index(path: &Path) -> io::Result<(HashMap<String, u64>, u64)> {
    let mut file = OpenOptions::new()
        .read(true)
        .write(true)
        .create(true)
        .truncate(false) // NEVER truncate the log we mean to replay
        .open(path)?;
    let mut bytes = Vec::new();
    file.seek(SeekFrom::Start(0))?;
    Read::read_to_end(&mut file, &mut bytes)?;
    let mut cursor = Cursor::new(&bytes);
    let mut index: HashMap<String, u64> = HashMap::new();
    loop {
        let start = cursor.position();
        match read_record(&mut cursor)? {
            Some(Command::Set { key, .. }) => {
                index.insert(key, start);
            }
            Some(Command::Delete { key }) => {
                index.remove(&key);
            }
            None => break,
        }
    }
    let write_pos = cursor.position();
    Ok((index, write_pos))
}

ทำไมต้อง .truncate(false) คู่กับ .create(true)

ตั้งแต่ Rust 1.97 lint clippy::suspicious_open_options จะเตือนเมื่อใช้ .create(true) โดยไม่ระบุ .truncate(...) ให้ชัด — และตรงนี้ ต้อง เป็น false เพราะเรากำลังจะเปิด file log ที่ตั้งใจ replay การ truncate จะล้าง log ทิ้งทั้ง file (ข้อมูลหายเกลี้ยง) ส่วน file temp ของ compaction ด้านล่างเป็นอีกกรณี — มันใช้ .truncate(true) เพราะเราตั้งใจเริ่มจาก file ว่างจริงๆ

compaction: เขียนเฉพาะ record ที่ยังมีชีวิต

ทีนี้ถึงการเก็บกวาด compaction คือการเขียนเฉพาะ record ที่ยังมีชีวิต (ค่าล่าสุดต่อ key ที่ยังไม่ถูกลบ) ลง file ใหม่ แล้วสลับมาใช้ file นั้นแทน — ทวงคืนพื้นที่ที่ dead record ยึดไว้ นี่คือสิ่งเดียวกับ segment merge & compaction ในเครื่องยนต์ LSM/SSTable ตามที่ DDIA ch3 นิยามว่า “โยน key ที่ซ้ำทิ้ง เก็บไว้แต่ค่า update ล่าสุดของแต่ละ key”

จุดที่สวยของ model Bitcask คือเรา ไม่ต้องสแกนหา live set — index ชี้ไปยัง record ล่าสุดของทุก key ที่ยังมีชีวิตอยู่แล้ว (tombstone ถอด key ออกจาก index ไปแล้ว) เพราะฉะนั้น live set = self.index.keys() เป๊ะๆ เราแค่วนอ่าน record ตาม offset ในนั้นแล้วเขียนลง file temp:

fn compact(&mut self) -> io::Result<()> {
    let tmp_path = self.dir.join("kvstore.compact"); // SAME dir => same fs => atomic rename
    let mut tmp = OpenOptions::new()
        .read(true)
        .write(true)
        .create(true)
        .truncate(true)
        .open(&tmp_path)?;

    let live_keys: Vec<String> = self.index.keys().cloned().collect(); // avoids borrow conflict
    let mut new_index = HashMap::new();
    let mut new_pos = 0u64;
    for key in live_keys {
        let offset = self.index[&key];
        self.file.seek(SeekFrom::Start(offset))?;
        let value = match read_record(&mut self.file)? {
            Some(Command::Set { value, .. }) => value,
            _ => continue,
        };
        let mut buf = Vec::new();
        write_record(&mut buf, &Command::Set { key: key.clone(), value })?;
        tmp.write_all(&buf)?;
        new_index.insert(key, new_pos);
        new_pos += buf.len() as u64;
    }

    tmp.sync_all()?;                    // 1. fsync the NEW file's data
    fs::rename(&tmp_path, &self.path)?; // 2. atomic swap (POSIX rename(2))
    File::open(&self.dir)?.sync_all()?; // 3. fsync the DIRECTORY (Unix; makes the rename durable)

    self.file = tmp;                    // 4. adopt compacted fd + fresh offsets (drops old inode)
    self.index = new_index;
    self.write_pos = new_pos;
    Ok(())
}

ลำดับสี่ขั้นท้าย block คือ หัวใจ ของ crash-safety และมันนำ durability primitive ของบท3 มาใช้ซ้ำทั้งหมด — ต้องเรียงตามนี้เท่านั้น:

tmp.sync_all() — บังคับ byte ของ file ใหม่ลง storage จริงก่อน ถ้ายังไม่ durable แล้วเราไปสลับ file ใหม่ที่ยังค้างอยู่ใน page cache อาจหายตอน crash
fs::rename(tmp, log) — สลับชื่อแบบ atomic ตาม POSIX rename(2) ระบบ file รับประกันว่า ณ ทุกจังหวะ path kvstore.log ชี้ไปที่ file เก่าทั้งอัน หรือ file ใหม่ทั้งอัน ไม่มีสถานะครึ่งๆ กลางๆ ให้เห็น
File::open(&self.dir)?.sync_all() — fsync ตัว directory เอง เพราะบน Unix การ rename เปลี่ยน directory entry ตัว entry ใหม่นี้ก็ต้อง durable ด้วย ไม่งั้น crash หลัง rename แต่ก่อน metadata ของ directory ลง disk อาจกลับไปเห็นชื่อเดิม
self.file = tmp; ... = new_index; — รับ fd ใหม่พร้อม offset ชุดใหม่เข้ามา การ drop self.file เก่าจะปลด reference สุดท้ายของ inode เดิม ระบบ file ก็ unlink มันทิ้ง — พื้นที่ถูกทวงคืนตรงนี้เอง

temp file ต้องอยู่ directory เดียวกับ log — ไม่ใช่เรื่องความสะดวก แต่เป็นเงื่อนไขความถูกต้อง

std::fs::rename map กับ Unix rename(2) ซึ่ง atomic เฉพาะเมื่อ source กับ destination อยู่บน filesystem เดียวกัน ถ้า file temp ไปอยู่คนละ mount (เช่น /tmp เป็น tmpfs แยก) rename จะล้มด้วย EXDEV — ไม่ใช่การ copy ข้ามให้เงียบๆ นี่คือเหตุผลที่ tmp_path ต้อง self.dir.join(...) เสมอ อยู่ directory เดียวกับ log เป้าหมาย การวางผิดที่ทำลาย atomicity ทั้งหมดที่เราอุตส่าห์สร้าง

ลองจริง: log หด สถานะคงเดิม

โปรแกรมทดสอบทำแบบนี้: เปิด store ใน directory เฉพาะกิจ (ประกอบจาก temp_dir + pid + nanos + AtomicU64 แล้วเก็บกวาดด้วย remove_dir_all เจาะจงเฉพาะ dir ตัวเอง ไม่มี wildcard) เขียนทับ key counter 1000 ครั้ง, เพิ่ม key name อีกตัว, แล้ว set-แล้ว-delete key temp (ทิ้ง tombstone หนึ่งอัน) จากนั้นวัดขนาด → compact() → วัดใหม่ → ยืนยันความถูกต้อง → reopen store ใหม่ทั้งอันเพื่อพิสูจน์ว่า compaction รอด boot:

before compact: log = 17945 bytes, live keys = 2
after  compact: log = 42 bytes, live keys = 2
post-compaction write: counter -> Some("1000")
after reopen: counter=Some("1000"), name=Some("kaen-kvstore"), temp=None
all assertions passed

อ่านผล: 1000 overwrites + tombstone พอง file เป็น 17,945 byte สำหรับ key ที่ยังมีชีวิตเพียง 2 ตัว — หลัง compact() เหลือ 42 byte (แค่ 2 live record) หดลงกว่า 400 เท่า โดยทุก get ยังคืน byte เดิมเป๊ะ, key ที่ถูก tombstone (temp) ยังเป็น None, write หลัง compaction (counter -> "1000") อ่านกลับได้ปกติ (offset ชุดใหม่สอดคล้องกัน) และเมื่อ reopen จาก file ที่ compact แล้ว สถานะเหมือนเดิมทุกประการ — tombstone ยังถูกเคารพข้ามการ reboot

flowchart LR
    subgraph OLD["log เดิม (dead + live ปน)"]
        d1["counter=0 (dead)"]
        d2["... 998 dead ..."]
        d3["counter=999 (live)"]
        d4["name=... (live)"]
        d5["temp=... (dead)"]
        d6["tombstone temp"]
    end
    OLD -->|"อ่าน live set จาก index"| FILTER["เก็บเฉพาะ record ที่ยังมีชีวิต"]
    FILTER --> TMP["kvstore.compact\n(tmp.sync_all → fsync data)"]
    TMP -->|"fs::rename (atomic)\n+ fsync directory"| NEW["log ใหม่ (42 byte)"]
    OLD -.->|"crash ก่อน rename → log เดิมยังครบทั้งอัน"| SAFE["สถานะเดิมปลอดภัย"]

คำบรรยายภาพ: compaction อ่านเฉพาะ record ที่ยังมีชีวิต (ตาม offset ใน hash index) เขียนลง file temp ใน directory เดียวกัน fsync ให้ durable แล้วสลับด้วย atomic rename + fsync directory — ถ้า crash ก่อน rename file log เดิมยังอยู่ครบทั้งอัน ไม่มีสถานะกลางคัน

ความจริงที่ต้องพูด: การแข่งกับ write และทางออกจริงคือ segment

compact() ตัวนี้ race-free เพราะมันเป็น single-threaded — ของจริงไม่ใช่แบบนี้

compact() ข้างบนถูกต้องเพราะทั้ง store บทนี้ยัง single-threaded — ไม่มี write ตัวไหนแทรกระหว่างที่เราอ่าน live set, เขียน temp, แล้ว rename ได้เลย แต่พอถึงบท5 ที่เรา share store ให้หลาย client ผ่าน Arc<Mutex>/Arc<RwLock> compaction จะแข่งกับ write ที่วิ่งพร้อมกัน ทันที — write ที่ append หลังจากเราอ่าน index.keys() ไปแล้วจะตกหล่นจาก file ใหม่ ถ้าเราถือ lock ทั้งก้อนคร่อม compact() ที่ช้า ก็เท่ากับหยุดรับ write ทั้ง server ระหว่างเก็บกวาด

ทางออกที่ฐานข้อมูลจริงใช้คือ segment — แช่แข็ง log ปัจจุบันให้ immutable เปิด file active ใหม่ให้ write ตัวใหม่ไปลง แล้ว merge เฉพาะ segment ที่แช่แข็งแล้ว (ทำใน background thread ได้ ขณะที่ read/write ยังทำงานผ่าน segment เก่า/ใหม่ต่อไป) เราจะ ตั้งชื่อ กลไกนี้ไว้ที่นี่ ส่วนการลงมือทำจริงเลื่อนไปตอนคอร์สแตะ concurrency (บท5) และ replication (#23) — สำหรับ toy บทนี้ single-threaded คือความถูกต้องที่พิสูจน์ได้ง่ายที่สุด

และเช่นเดียวกับบท3: tombstone + length prefix กัน truncation (tail ขาดจาก crash) ได้ แต่ไม่กัน bit-flip เงียบๆ — ของจริง (Bitcask) ใส่ CRC ต่อ record; และ fsync เองก็โกหกได้ (fsyncgate 2018) เราไม่ over-promise

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

บทนี้ปิดวงจรชีวิตของข้อมูลใน log-structured store: DELETE ไม่ใช่การลบ byte เดิม แต่คือการ append tombstone record (val_len == u32::MAX ไม่มี value bytes) ที่ replay ตีความว่า index.remove — การลบเป็นการเขียนอีกครั้ง ไม่ใช่การแก้ที่เดิม จึงไม่แตะ append-only invariant; และเมื่อ dead record สะสมจน log บวม compaction เขียนเฉพาะ live set (ซึ่ง index ชี้ให้อยู่แล้ว) ลง file ใหม่ สลับด้วยลำดับ crash-safe fsync data → atomic rename → fsync directory → adopt fd โดย temp file ต้องอยู่ directory เดียวกันเพื่อให้ rename atomic จริง วัดจริงได้ log หดจาก 17,945 เหลือ 42 byte โดยความถูกต้องคงเดิมทุกจุดแม้ reopen ทั้งหมดเป็น Rust std ล้วน compile และรันได้จริงบน 1.97.1 / edition 2024

บท5 เราเปิดรับหลาย client พร้อมกัน: server single-threaded จากบท1 serialize client ทีละราย — บทหน้าเราแทนมันด้วย ThreadPool (แบบบท 21 ของ Rust Book) ที่ share store ผ่าน Arc<Mutex>/Arc<RwLock> และตรงนั้นเองที่คำเตือนเรื่อง compaction แข่งกับ write จะกลายเป็นโจทย์จริงที่ต้องออกแบบ lock scope ให้ถูก

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

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

Designing Data-Intensive Applications — ch3 “Storage and Retrieval” โดย Martin Kleppmann, 2017 (เข้าถึง 2026-07-24) — compaction คือ “โยน key ที่ซ้ำทิ้ง เก็บไว้แต่ค่า update ล่าสุดของแต่ละ key”; tombstone คือ deletion record ที่บอก merge process ให้ทิ้งค่าเก่า; และ merge/compaction ทำใน background thread ได้ขณะยังบริการ read/write ผ่าน segment เดิม
Database Internals — ch7 “Log-Structured Storage” โดย Alex Petrov, 2019 (เข้าถึง 2026-07-24) — log-structured storage มองข้อมูลบน disk เป็น immutable segment; การ update/delete กลายเป็นการ append; compaction ทวงคืนพื้นที่โดยรวม segment
std fs::rename (เข้าถึง 2026-07-24) — map กับ Unix rename(2); atomic replace เฉพาะเมื่อ source/destination อยู่บน filesystem เดียวกัน (ข้าม mount ล้มด้วย EXDEV)
std fs::File::sync_all / sync_data (เข้าถึง 2026-07-24) — sync_all = fsync(2) (data + metadata); ใช้ fsync ตัว file temp และ fsync ตัว directory เพื่อทำ rename ให้ durable

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

ข้อ 1 / 3

tombstone ใน kaen-kvstore คืออะไร และทำงานอย่างไร?

Tombstones และ compaction — ทวง​คืน​พื้นที่​โดย​ไม่​ทำลาย​ความ​ถูกต้อง

ปัญหา: log โต​ตาม​จำนวน operation ไม่ใช่​จำนวน key

DELETE ใน​โลก​ที่​ห้าม​ลบ: tombstone

replay ที่​รู้จัก tombstone

compaction: เขียน​เฉพาะ record ที่​ยัง​มี​ชีวิต

ลอง​จริง: log หด สถานะ​คง​เดิม

ความ​จริง​ที่​ต้อง​พูด: การ​แข่ง​กับ write และ​ทางออก​จริง​คือ segment

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