Persistence — append-only log + hash index ในหน่วยความจำ (model Bitcask)
บท1 เราต่อโครงบนเครือข่ายเสร็จ — wire protocol แบบ length-prefixed, server/client TCP, และ store ที่เป็น HashMap ในหน่วยความจำล้วนๆ แต่มีจุดตายอยู่หนึ่งจุด: HashMap นั้น ตายพร้อม process ปิดโปรแกรมทีข้อมูลหายเกลี้ยง บทนี้เราลง disk — ทำให้ทุก set/delete รอด การปิดโปรแกรม ด้วยท่าเดียวที่ตรงไปตรงมาที่สุด: append ทุกคำสั่งเป็น record ต่อท้าย file log file เดียว แล้วเก็บ index ในหน่วยความจำที่ชี้จาก key ไปยังตำแหน่งของ record ล่าสุดใน file นั้น
นี่ไม่ใช่ท่าที่เราคิดขึ้นเอง — มันคือ model Bitcask ที่ฐานข้อมูลจริง (Riak) ใช้ และเป็นแกนของ log-structured storage ที่ตำราฐานข้อมูลพูดถึงตรงๆ (Petrov ch7, DDIA ch3) เราแค่ย่อมันลงมาระดับ toy เพื่อ เข้าใจ ว่ามันทำงานอย่างไร
code ลงมือของคอร์สนี้อยู่ใน repo kaen-kvstore (code ตัวอย่างกำลังจัดทำ) — ตลอด 8 บทเราสร้าง key-value store บนเครือข่ายที่กู้คืนจาก crash ได้ หนึ่งตัว ด้วย Rust std ล้วน (ไม่มี async/tokio, ไม่มี serde — serialization เขียนเองด้วย byte แบบ length-prefixed) บทนี้เปลี่ยน store จาก HashMap ในหน่วยความจำ ให้เป็น append-only log บน disk + hash index ในหน่วยความจำ (model Bitcask) — record framing ตัวเดียวกับบท1 ย้ายจาก socket มาเขียนลง File ส่วน durability จริง (fsync) ยังไม่มาจนบท3
HashMap ตายพร้อม process — ทางออกคือ log
หัวข้อที่มีชื่อว่า “HashMap ตายพร้อม process — ทางออกคือ log”ฐานข้อมูลทุกตัวต้องตอบคำถามเดียวกัน: จะเก็บข้อมูลลง storage ที่ รอด การปิดเครื่องได้อย่างไรให้เร็ว การเขียนทับที่เดิม (in-place update) ใน file ฟังดูตรงไปตรงมา แต่มันช้า (ต้อง seek ไปมา) และอันตราย (crash กลางการเขียนทับ = record เดิมพัง) ทางเลือกที่ log-structured storage เลือกคือกลับด้าน: ไม่แก้ที่เดิมเลย เขียนต่อท้ายอย่างเดียว
append-only logappend-only logfile ที่เขียนต่อท้ายอย่างเดียว ไม่แก้ที่เดิม เป็นแกนของ log-structured storage คือ file ที่เราเขียน ต่อท้าย อย่างเดียว ไม่เคยย้อนไปแก้ byte ที่เขียนไปแล้ว ทุก set คือ append record ใหม่หนึ่งอัน ทุก delete ก็ append record พิเศษ (tombstone) หนึ่งอัน — file จึงเป็น ประวัติการเขียนทั้งหมด เรียงตามเวลา ไม่ใช่ ภาพสถานะปัจจุบัน ข้อดีที่ได้มาฟรีมีสองชั้น: การเขียนกลายเป็น sequential write ล้วน (เร็วทั้งบน HDD และ SSD) และ crash กลาง append ทำได้แค่ทำให้ record ตัวสุดท้าย ขาดหาย ไม่มีทางไปทำลาย record เก่าที่เขียนครบไปแล้ว แนวคิดนี้ตรงกับ WAL / commit log ในตำรา — เพียงแต่ในฐานข้อมูล log-structured ตัว log คือ ข้อมูลเอง ไม่ใช่ log แยกที่เขียนก่อนแก้หน้าจริง (เส้นนี้เราจะขีดชัดในบท3)
แต่ log ล้วนๆ มีปัญหาหนึ่ง: จะ get key ให้ไว โดยไม่ต้องอ่านทั้ง file ได้อย่างไร คำตอบคือ index
hash index — key ทุกตัวอยู่ใน RAM ค่าอยู่บน disk
หัวข้อที่มีชื่อว่า “hash index — key ทุกตัวอยู่ใน RAM ค่าอยู่บน disk”hash indexhash indexแผนที่ในหน่วยความจำจาก key → offset ใน file log อ่านได้เกือบ 1 I/O คือ HashMap ในหน่วยความจำที่ map จากทุก key ไปยัง ตำแหน่ง byte ใน file log ของ record ล่าสุดของ key นั้น อ่านค่าหนึ่งครั้ง = หา key ใน hash map (เกือบ O(1)) ได้ offsetoffsetตำแหน่ง byte ใน file ที่ record หรือ value เริ่มต้น แล้ว seek ไปตรงนั้นใน file แล้วอ่านค่าออกมา — 1 hash lookup + 1 seek + 1 read เท่านั้น นี่คือหัวใจของ BitcaskBitcaskmodel storage engine: append-only log + hash index ทุก key อยู่ใน RAM: ทุก key ต้องอยู่ใน RAM ครบ (จึงจำกัดที่จำนวน key ไม่ใช่ขนาดค่า) แต่ค่าจริงอยู่บน disk ตาม DDIA ch3 อธิบายไว้ตรงตัว
index ของเราเก็บมากกว่าแค่ offset นิดหน่อย — เก็บทั้งตำแหน่งเริ่มของ ค่า และความยาวของค่า เพื่อจะอ่านได้พอดีในทีเดียว:
// index เก็บตำแหน่งของ value payload (ไม่ใช่ต้น record) + ความยาว#[derive(Clone, Copy, Debug)]struct ValuePos { value_offset: u64, // byte offset ใน file ที่ค่าเริ่มต้น value_len: u32, // อ่านค่าออกมากี่ byte}record layout — เขียน byte เอง ไม่พึ่ง serde
หัวข้อที่มีชื่อว่า “record layout — เขียน byte เอง ไม่พึ่ง serde”ก่อน append ได้ ต้องตกลงหน้าตา record บน disk ก่อน เราใช้ format length-prefixed ตัวเดียวกับ frame ในบท1 เป๊ะ เพียงย้ายปลายทางจาก socket มาเป็น File:
[ key_len: u32 LE ][ val_len: u32 LE ][ key bytes ][ val bytes ]8 byte แรกคือ header (ความยาว key และความยาว value แบบ little-endian) แล้วตามด้วย byte ของ key และ value ตามจำนวนนั้นพอดี delete คือ tombstone: record ที่ val_len == u32::MAX (ค่า sentinel) และ ไม่มี byte ของ value ตามมาเลย ค่า u32::MAX ปลอดภัยเป็น sentinel เพราะไม่มีทางเป็นความยาวค่าจริง (จะเท่ากับค่าขนาด 4 GiB) เราสร้าง record ทั้งก้อนไว้ใน Vec<u8> เดียวก่อน แล้วค่อย write_all ครั้งเดียว — หนึ่ง write_all = 1 append ทำให้ crash ตัดได้แค่หางเดียว ไม่ได้ตัดกลาง record จนโครงสร้างเพี้ยน
to_le_bytes แปลงความยาวเป็น byte แบบ little-endian คงที่ทุกสถาปัตยกรรม (เหตุผลเดียวกับบท1) และเพราะ key/value เป็น byte ดิบ (Vec<u8>) ทั้งคู่ ไม่ใช่ String — store จึงรับค่า binary อะไรก็ได้ ตรงข้ามกับ version ดิบ ที่เก็บทีละบรรทัดด้วย \n คั่น ซึ่งพังทันทีเมื่อ value มี newline หรือไม่ใช่ UTF-8
โครงสร้าง Store — writer/reader แยก handle
หัวข้อที่มีชื่อว่า “โครงสร้าง Store — writer/reader แยก handle”Store ถือ3 state: handle สำหรับ เขียน (เปิดด้วย append(true)), handle สำหรับ อ่าน แบบ random-access, และ hash index กับ offset ปลาย file:
use std::collections::HashMap;use std::fs::{File, OpenOptions};use std::io::{self, BufReader, Read, Seek, SeekFrom, Write};use std::path::Path;
const TOMBSTONE: u32 = u32::MAX; // val_len == นี้ = คำสั่ง delete
struct Store { writer: File, // append handle: ทุก write ลงท้าย file reader: File, // read handle: cursor อิสระสำหรับ get() index: HashMap<Vec<u8>, ValuePos>, // key -> ตำแหน่งค่าล่าสุด tail: u64, // offset ปลาย file (append ถัดไปลงตรงนี้)}
impl Store { fn open(path: &Path) -> io::Result<Store> { // append(true): ทุก write() ลง EOF เสมอ ไม่ว่า cursor อยู่ตรงไหน (O_APPEND) let writer = OpenOptions::new().create(true).append(true).open(path)?; let reader = OpenOptions::new().read(true).open(path)?; let mut store = Store { writer, reader, index: HashMap::new(), tail: 0 }; store.rebuild_index()?; // สแกน log ที่มีอยู่เพื่อสร้าง index Ok(store) }}การเปิดด้วย OpenOptions::append(true) ให้ semantics แบบ O_APPEND: ทุก write ลงท้าย file เสมอ ไม่ว่า cursor จะอยู่ตรงไหน — จึงมี handle แยกสำหรับอ่าน (ที่ seek ไปมาได้อิสระใน get) โดยไม่รบกวนตำแหน่งที่ append ลง สองมุมมองบน file เดียวกัน ไม่ชนกัน
set และ delete — append แล้วอัปเดต index
หัวข้อที่มีชื่อว่า “set และ delete — append แล้วอัปเดต index”set สร้าง record ทั้งก้อนแล้ว write_all ทีเดียว จากนั้นชี้ index ไปที่ ค่า (ไม่ใช่ต้น record) — คือ tail + 8 + key_len เพราะค่าเริ่มหลัง header 8 byte และ key:
impl Store { fn set(&mut self, key: &[u8], value: &[u8]) -> io::Result<()> { let key_len = key.len() as u32; let val_len = value.len() as u32; // สร้าง buffer เดียว แล้ว write() ครั้งเดียว -> 1 append let mut rec = Vec::with_capacity(8 + key.len() + value.len()); rec.extend_from_slice(&key_len.to_le_bytes()); rec.extend_from_slice(&val_len.to_le_bytes()); rec.extend_from_slice(key); rec.extend_from_slice(value); self.writer.write_all(&rec)?;
let value_offset = self.tail + 8 + key_len as u64; // ชี้ที่ค่า ไม่ใช่ header self.index.insert(key.to_vec(), ValuePos { value_offset, value_len: val_len }); self.tail += rec.len() as u64; Ok(()) }
fn delete(&mut self, key: &[u8]) -> io::Result<()> { let key_len = key.len() as u32; // record tombstone: val_len = TOMBSTONE, ไม่มี byte ของค่า let mut rec = Vec::with_capacity(8 + key.len()); rec.extend_from_slice(&key_len.to_le_bytes()); rec.extend_from_slice(&TOMBSTONE.to_le_bytes()); rec.extend_from_slice(key); self.writer.write_all(&rec)?; self.index.remove(key); // ลบออกจาก index แต่ record ยังคาอยู่ใน file self.tail += rec.len() as u64; Ok(()) }}สังเกตว่า delete ไม่ได้ ลบ byte ใน file — มันแค่ append tombstone แล้วเอา key ออกจาก index เท่านั้น record เก่าของ key ยังนอนอยู่ใน file (นี่คือเหตุที่ log โตไม่หยุด — บท4 จะทวงคืนด้วย compaction) การคำนวณ value_offset ที่ tail + 8 + key_len เป็นจุดที่ ต้องตรงกับ การคำนวณตอน replay เป๊ะๆ ไม่งั้น index เพี้ยน
get — hash lookup แล้ว seek + read_exact
หัวข้อที่มีชื่อว่า “get — hash lookup แล้ว seek + read_exact”get คือหัวใจ Bitcask ที่จ่ายผลตอบแทน: หา key ใน index ได้ ValuePos แล้ว seek ไปที่ค่าตรงๆ อ่านออกมาพอดี value_len byte ด้วย read_exact:
impl Store { fn get(&mut self, key: &[u8]) -> io::Result<Option<Vec<u8>>> { let pos = match self.index.get(key) { Some(p) => *p, None => return Ok(None), // ไม่มีใน index = ไม่มีค่า }; self.reader.seek(SeekFrom::Start(pos.value_offset))?; let mut buf = vec![0u8; pos.value_len as usize]; self.reader.read_exact(&mut buf)?; // อ่านให้ครบ value_len พอดี Ok(Some(buf)) }}ไม่ต้องสแกน file ไม่ต้องอ่าน header ซ้ำตอน get — index บอกตำแหน่งและความยาวมาให้แล้ว 1 seek + หนึ่ง read_exact จบ
rebuild_index — replay ทั้ง log, last-write-wins ได้มาฟรี
หัวข้อที่มีชื่อว่า “rebuild_index — replay ทั้ง log, last-write-wins ได้มาฟรี”ตอนเปิด store เราต้องสร้าง index ขึ้นใหม่จาก file ที่มีอยู่ วิธีคือสแกนตั้งแต่ต้นจนจบ ตามลำดับที่เขียน แล้ว apply ทีละ record — SET ก็ insert, tombstone ก็ remove เพราะเราสแกนตามเวลา record ที่มาทีหลังของ key เดิมจะ insert ทับตัวก่อนโดยอัตโนมัติ last-write-wins จึงตกมาฟรี ไม่ต้องเขียน logic เปรียบเทียบเวลาอะไรเลย:
impl Store { fn rebuild_index(&mut self) -> io::Result<()> { let mut r = BufReader::new(&self.reader); r.seek(SeekFrom::Start(0))?; let mut offset: u64 = 0; loop { // อ่าน header 8 byte; EOF สะอาดตรงนี้ = จบ log let mut header = [0u8; 8]; match r.read_exact(&mut header) { Ok(()) => {} Err(e) if e.kind() == io::ErrorKind::UnexpectedEof => break, Err(e) => return Err(e), } let key_len = u32::from_le_bytes([header[0], header[1], header[2], header[3]]); let val_len = u32::from_le_bytes([header[4], header[5], header[6], header[7]]);
let mut key = vec![0u8; key_len as usize]; r.read_exact(&mut key)?;
if val_len == TOMBSTONE { self.index.remove(&key); // delete: ไม่มี byte ค่าตามมา offset += 8 + key_len as u64; } else { let value_offset = offset + 8 + key_len as u64; // ตรงกับสูตรใน set() self.index.insert(key, ValuePos { value_offset, value_len: val_len }); r.seek(SeekFrom::Current(val_len as i64))?; // ข้าม byte ของค่า offset = value_offset + val_len as u64; } } self.tail = offset; Ok(()) }}จุดสำคัญคือ UnexpectedEof ตอนอ่าน header คือ ตัวจบ loop ปกติ — ไม่ใช่ error เมื่อสแกนถึงปลาย file read_exact จะได้ UnexpectedEof เรา break เงียบๆ (ในบท3 การ match แบบเดียวกันนี้จะกลายเป็นเครื่องมือ ทน torn tail จาก crash ด้วย) และ value_offset = offset + 8 + key_len ตรงนี้ต้องตรงกับสูตรใน set เป๊ะ — ถ้าคลาดกันแม้ byte เดียว get หลัง reopen จะอ่านผิดตำแหน่ง
flowchart LR
subgraph IDX["hash index ในหน่วยความจำ"]
K1["key: lang"]
K2["key: db"]
end
subgraph LOG["append-only log บน disk (เรียงตามเวลา)"]
R1["rec เก่า: lang = rust"]
R2["rec: db = kaen-kvstore"]
R3["rec ล่าสุด: lang = rust-2024"]
end
K1 -->|value_offset| R3
K2 -->|value_offset| R2
R1 -.->|ถูกทับ ไม่มีใครชี้| R1
คำบรรยายภาพ: hash index ในหน่วยความจำชี้ไปยัง offset ของ record ล่าสุด ของแต่ละ key ใน append-only log — record เก่าของ lang ยังนอนอยู่ใน file แต่ไม่มีใครใน index ชี้หา (พื้นที่ตายที่ compaction ในบท4 จะทวงคืน)
รันจริง — set/get roundtrip ข้าม2 session
หัวข้อที่มีชื่อว่า “รันจริง — set/get roundtrip ข้าม2 session”โปรแกรมทดสอบ: session แรกเขียน+ลบ+อ่านกลับ, ปิด, แล้ว session สองเปิดใหม่ให้ rebuild_index สแกน log สร้าง index ขึ้นมาเอง แล้วยืนยันว่าได้สถานะเดิมเป๊ะ (รวมถึง tombstone ที่ต้องรอด replay):
fn main() -> io::Result<()> { let dir = std::env::temp_dir().join("kaen_kvstore_verify"); std::fs::create_dir_all(&dir)?; let path = dir.join("data.log"); let _ = std::fs::remove_file(&path);
// session 1: เขียน ลบ อ่านกลับ { let mut store = Store::open(&path)?; store.set(b"lang", b"rust")?; store.set(b"edition", b"2024")?; store.set(b"lang", b"rust-2024")?; // overwrite: append ใหม่ชนะ store.delete(b"edition")?; assert_eq!(store.get(b"lang")?, Some(b"rust-2024".to_vec())); assert_eq!(store.get(b"edition")?, None); assert_eq!(store.get(b"missing")?, None); }
// session 2: reopen -> rebuild_index สแกน log ใหม่ทั้ง file { let mut store = Store::open(&path)?; assert_eq!(store.get(b"lang")?, Some(b"rust-2024".to_vec())); assert_eq!(store.get(b"edition")?, None, "tombstone ต้องรอด replay"); }
println!("all assertions passed; log at {}", path.display()); Ok(())}รันบน musl (Rust 1.97.1, std ล้วน) ได้ผล:
all assertions passed; log at /tmp/kaen_kvstore_verify/data.logและ hexdump ของ file log ยืนยันว่า byte บน disk ตรงกับ wire format เป๊ะ — รวมถึง tombstone (ff ff ff ff = u32::MAX) ที่มี key edition แต่ไม่มี byte ของค่าตามมา:
00000000: 0400 0000 0400 0000 6c61 6e67 7275 7374 ........langrust00000010: 0700 0000 0400 0000 6564 6974 696f 6e32 ........edition200000020: 3032 3404 0000 0009 0000 006c 616e 6772 024........langr00000030: 7573 742d 3230 3234 0700 0000 ffff ffff ust-2024........00000040: 6564 6974 696f 6e editionอ่านทีละ record: lang=rust (4+4 header, 0x04/0x04), edition=2024, lang=rust-2024 (overwrite — val_len=0x09), แล้ว tombstone ของ edition (val_len = ff ff ff ff, ตามด้วย key เปล่าๆ ไม่มีค่า) — index หลัง replay จึงเห็น lang → rust-2024 และ edition หายไป ตรงกับที่ assertion ยืนยัน
สองความจริงที่เราพูดตรงๆ
หัวข้อที่มีชื่อว่า “สองความจริงที่เราพูดตรงๆ”1. “append แล้ว” ยังไม่เท่ากับ “durable” — write_all คืน Ok แปลว่า byte ถึง page cache ของ OS แล้วเท่านั้น ยังไม่ ถึงจาน disk จริง ถ้าไฟดับตอนนี้ byte ที่ยังค้างใน page cache หายได้ Durability ที่แท้จริงต้องบังคับ byte ลง storage ด้วย fsync (File::sync_all/sync_data) ก่อนถือว่า commit — เรื่องนี้ทั้งเรื่องคือ บท3 ตอนนี้ store เราแค่ persistent ข้ามการปิดโปรแกรมปกติ ยังไม่ crash-safe
2. log โตไม่หยุด — ทุก set/overwrite/delete append อย่างเดียว ไม่เคยลบ byte เดิม เขียนทับ key เดิม 1000 ครั้งก็ได้ 1000 record ทั้งที่มี key มีชีวิตแค่ตัวเดียว file จึงโตตามจำนวน operation ไม่ใช่จำนวน key ที่มีชีวิต การทวงคืนพื้นที่ (เขียนเฉพาะ record ที่ยังมีชีวิตลง file ใหม่) คือ compaction ในบท4
สรุปก่อนไปต่อ
หัวข้อที่มีชื่อว่า “สรุปก่อนไปต่อ”บทนี้เปลี่ยน store จาก HashMap ที่ตายพร้อม process เป็น model Bitcask: append-only log บน disk เป็นแหล่งความจริง เขียนต่อท้ายอย่างเดียว (sequential + crash ตัดได้แค่หาง); hash index ในหน่วยความจำ map key → ValuePos (offset ของค่า + ความยาว) ทำให้ get เป็น1 lookup + seek + read_exact; record layout [key_len][val_len][key][val] แบบ little-endian เขียนเองด้วย to_le_bytes/write_all ไม่พึ่ง serde; delete เป็น tombstone (val_len == u32::MAX); และ rebuild_index สแกน log ตั้งแต่ต้นจนจบให้ last-write-wins ตกมาฟรี ทุก snippet compile และรันได้จริง
บท3 เราปิดช่องความจริงข้อแรก: ทำให้ “append แล้ว” กลายเป็น “durable” จริง ด้วยลำดับ write_all → fsync → update index → ack ที่ห้ามสลับ — พร้อมพูดตรงๆ ว่า fsync เองก็โกหกได้ (fsyncgate) และ toy ของเรา ทน truncation แต่ ไม่ทน corruption
บทนี้อิงต้นทางที่ลงวันที่กำกับ อ่านต่อได้โดยตรง:
- Database Internals — ch7 “Log-Structured Storage” (และ ch3 “File Formats”) — Alex Petrov, 2019 (เข้าถึง 2026-07-24) — append-only / log-structured storage เปลี่ยน update เป็น sequential write และมองข้อมูลบน disk เป็น immutable; append ที่ถูกขัดจังหวะทำได้แค่ทิ้งหางขาด ไม่ทำลาย record เดิม
- Designing Data-Intensive Applications — ch3 “Storage and Retrieval” — Martin Kleppmann, 2017 (เข้าถึง 2026-07-24) — hash index แบบ log-structured (Bitcask): map ทุก key → byte offset ของ record ล่าสุด, อ่าน = 1 hash lookup + seek + read, และ ทุก key ต้องอยู่ใน RAM
- Bitcask: A Log-Structured Hash Table for Fast Key/Value Data — Sheehy & Smith (Basho), 2010 (เข้าถึง 2026-07-24) — model ต้นฉบับ: append-only log + in-memory keydir; record layout จริงมี
crc | tstamp | ksz | value_sz | key | value(toy ของเราตัด crc/tstamp ออก) - std
fs::OpenOptions(เข้าถึง 2026-07-24) —append(true)ให้ semanticsO_APPEND: ทุกwriteลง EOF เสมอไม่ว่า cursor อยู่ไหน - std
Read::read_exact(เข้าถึง 2026-07-24) — อ่านให้เต็มbuf.len()พอดี หรือคืนUnexpectedEofเมื่อสายจบก่อน — ตัวจบ loop ของ replay - std
u32::to_le_bytes(เข้าถึง 2026-07-24) — byte little-endian คงที่ 4 byte เสถียรตั้งแต่ 1.32.0
เช็กความเข้าใจ — บทที่ 2
ข้อ 1 / 3hash index ในหน่วยความจำของ model Bitcask เก็บอะไรไว้ต่อ1 key?