คุมด้วย lock แล้วจ่ายด้วยการรอ

ก่อนจะมี MVCC ปัญหานี้มีคำตอบอยู่แล้ว และคำตอบนั้นตรงกว่ามาก คือให้ทุกคนขออนุญาตก่อนแตะข้อมูล

วิธีนี้ไม่ใช่หุ่นฟางที่ยกมาเพื่อล้ม มันถูกต้องจริง และเอนจินที่ใช้งานอยู่ทุกวันนี้หลายตัว ยังคุมการเขียนด้วยวิธีนี้อยู่

สิ่งที่มันเก็บเป็นค่าตอบแทนคือ การรอ กับ การที่บางคนต้องถูกยกเลิกทั้งก้อน ทั้งสองอย่างนับได้ และบทนี้จะนับให้ดู

📦 ทั้งบทนี้อยู่ใน src/lock.rs ที่เดียว

lock manager ของคอร์สนี้ยาวไม่ถึงร้อยบรรทัด ไม่มี thread ไม่มีการหน่วงเวลา และไม่เรียกนาฬิกา สักครั้ง เทสต์ I7 กวาดซอร์สทุกตัวเพื่อบังคับข้อนี้

ราคาที่บทนี้รายงานจึงเป็นจำนวนนับสองตัว คือจำนวนก้าวที่ถูกบล็อก กับจำนวน deadlock ไม่ใช่เวลาบนนาฬิกาซึ่งเปลี่ยนไปตามเครื่องที่รัน

สองช่วงที่ห้ามสลับกัน

หัวข้อนี้อธิบายกฎสองช่วงของ 2PL และเหตุผลที่การคืน lock ก่อนขอตัวถัดไปทำลายความถูกต้อง

Two-Phase Locking แบ่งอายุของ transaction ออกเป็นสองช่วง ช่วงแรกขอ lock ได้อย่างเดียว ช่วงที่สองคืนได้อย่างเดียว จุดที่ขอ lock ตัวสุดท้ายคือเส้นแบ่งระหว่างสองช่วงนั้น

กฎมีข้อเดียวคือห้ามคืนแล้วกลับไปขอใหม่ และเหตุผลของกฎข้อนี้ไม่ได้อยู่ที่ความเป็นระเบียบ

สมมติว่า t1 อ่าน order:1 ด้วย shared lock แล้วคืนทันที จากนั้นค่อยขอ lock ของ order:2 ระหว่างสองจังหวะนั้น t2 เข้ามาแก้ order:1 แล้ว commit ได้เต็มที่

ผลที่ได้คือ t1 อ่านค่าก่อนที่ t2 จะแก้ แต่เขียนหลังจาก t2 เขียนไปแล้ว มันจึงอยู่ทั้งก่อนและหลัง t2 พร้อมกัน และไม่มีลำดับเรียงทีละตัวลำดับไหนอธิบายผลนั้นได้

ตราบใดที่ทุกคนไม่คืนก่อนขอครบ เส้นแบ่งของแต่ละ transaction เรียงลำดับกันได้เสมอ และลำดับของเส้นแบ่งนั้นเองคือลำดับเรียงทีละตัวที่อธิบายผลลัพธ์ได้ นี่คือสิ่งที่ 2PL ซื้อมา

    /// คืน lock ทั้งหมดของ transaction หนึ่ง — จุดเริ่มของช่วงที่สองใน 2PL
    pub fn release_all(&mut self, xid: Xid) {
        for held in self.holders.values_mut() {
            held.retain(|(other, _)| *other != xid);
        }
        self.waits.remove(&xid);
        self.waits.retain(|_, waiting_for| *waiting_for != xid);
    }

เอนจินนี้ไม่มีทางคืน lock ทีละตัวเลย มีแต่คืนทั้งหมดทีเดียว รูปร่างของ API จึงบังคับกฎสองช่วง ไว้ในตัวมันเอง

การคืนทีเดียวทั้งหมดตอนจบงานคือรูปแบบที่เข้มที่สุดของกฎนี้ และมันมีของแถมมาด้วย คือไม่มีใครอ่านค่าที่ยังไม่ commit ได้เลย

ถ้าคืน exclusive ก่อนจบงาน คนที่อ่านต่อจากนั้นจะอ่านค่าที่ยังไม่แน่นอนไปใช้ และต้องถูกยกเลิก ตามไปทั้งแถวเมื่อเจ้าของค่าถูกยกเลิก

shared กับ exclusive และกฎที่ยาวบรรทัดเดียว

หัวข้อนี้แสดงสองโหมดของ lock สามผลลัพธ์ที่การขอคืนกลับมา และกฎความเข้ากันได้ทั้งหมดของเอนจิน

#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Mode {
    Shared,
    Exclusive,
}

#[derive(Debug, PartialEq, Eq)]
pub enum Outcome {
    Granted,
    /// ต้องรอ transaction ที่ระบุ
    Blocked(Xid),
    /// รอแล้วจะวนเป็นวง ต้องมีคนถูก abort
    Deadlock(Xid),
}

Granted แปลว่าได้ไปเลย ส่วนอีกสองตัวพ่วงหมายเลข transaction กลับมาด้วย เพราะคำตอบว่ารอ ไม่มีประโยชน์ถ้าไม่บอกว่ารอใคร

กฎที่ตัดสินว่าใครต้องรอมีอยู่บรรทัดเดียวในทั้งเอนจิน

    /// lock สองตัวอยู่ร่วมกันได้ก็ต่อเมื่อทั้งคู่เป็น shared
    fn compatible(existing: Mode, wanted: Mode) -> bool {
        existing == Mode::Shared && wanted == Mode::Shared
    }

อ่านออกมาเป็นภาษาพูดได้ประโยคเดียว lock สองตัวอยู่ร่วมกันได้ก็ต่อเมื่อทั้งคู่เป็น shared นอกนั้นรอทั้งหมด

ตัวที่ถืออยู่	ตัวที่ขอ	ผล
shared	shared	อยู่ร่วมกันได้ ไม่มีใครรอ
shared	exclusive	ต้องรอ
exclusive	shared	ต้องรอ
exclusive	exclusive	ต้องรอ

ตอนที่ acquire มองหาตัวขวาง มันข้ามรายการของตัวเองทิ้งเสมอ คนที่ถือ shared อยู่แล้ว จึงขอยกระดับเป็น exclusive ได้ โดยไม่ติด lock ของตัวเอง

ข้อนี้ฟังดูเหมือนความสะดวกเล็กๆ แต่มันคือปากทางของทั้งบท

รันจริง สองคนขอ shared แล้วต่างขอยกระดับ

หัวข้อนี้อ่านผลรันทีละบรรทัด และชี้ว่าตัวเลขสองตัวในบรรทัดสรุปคือราคาของบทนี้

== บทที่ 3 คุมด้วย lock แล้วจ่ายด้วยการรอ ==
  t1 ขอ shared  order:1   Granted
  t2 ขอ shared  order:1   Granted
  → shared สองตัวอยู่ร่วมกันได้ ไม่มีใครต้องรอ

  t1 ขอ exclusive order:1 Blocked(2)
  t2 ขอ exclusive order:1 Deadlock(1)

  ก้าวที่ถูกบล็อก 1 · deadlock 1
  ทั้งคู่ถือ shared อยู่แล้วต่างขอยกระดับ จึงรอกันเป็นวง
  ไม่มีใครถอยเองได้ ต้องมีคนถูก abort นี่คือราคาของ 2PL ที่นับได้
  abort t1 แล้วคืน lock ทั้งหมดของมัน → t2 เดินต่อได้

สามบรรทัดถัดจากหัวเรื่องคือกำไรของ shared mode ทั้ง t1 และ t2 ขออ่านคีย์เดียวกันพร้อมกัน และได้ทั้งคู่ ไม่มีใครต้องรอใครสักก้าว

บรรทัดถัดมา t1 ขอยกระดับเป็น exclusive แล้วได้ Blocked(2) กลับมา มันต้องรอให้ t2 คืน shared ก่อน ซึ่งเป็นคำตอบที่ตรงไปตรงมา

บรรทัดที่ต้องหยุดอ่านคือบรรทัดของ t2 มันขอสิ่งเดียวกันแล้วได้ Deadlock(1) นี่คือ Deadlock สภาพที่ต่างฝ่ายต่างถือของที่อีกฝ่ายรออยู่

บรรทัดสรุปคือหน่วยที่คอร์สนี้ใช้ทั้งเล่ม ก้าวที่ถูกบล็อกหนึ่งก้าว และ deadlock หนึ่งครั้ง ไม่มีตัวเลขจากนาฬิกาสักตัว

ไม่มีใครถอยเองได้

หัวข้อนี้อธิบายว่าทำไมทางออกเดียวของวงนี้คือการยกเลิกใครสักคนทั้งก้อน

t1 ถือ shared อยู่ และรอให้ t2 คืน shared ส่วน t2 ก็ถือ shared อยู่ และรอให้ t1 คืนเหมือนกัน

ทางออกที่ดูสมเหตุสมผลที่สุดคือให้ใครสักคนคืน shared ของตัวเองไปก่อน แล้วค่อยขอใหม่ทีหลัง

ทางนั้นคือทางที่หัวข้อแรกห้ามไว้ การคืนตอนที่ยังจะขอเพิ่มคือการเปิดช่วงที่สองก่อนช่วงแรกจบ ความถูกต้องที่กลไกนี้ซื้อมาจะหายไปพร้อมกับการคืนครั้งนั้น

ทางออกที่เหลือจึงมีทางเดียว คือ abort ตัวใดตัวหนึ่งทิ้งทั้งก้อน แล้วคืน lock ทุกตัวของมัน การคืนครั้งนั้นถูกกติกา เพราะ transaction ตัวนั้นจบไปแล้ว ไม่มีอะไรจะขอเพิ่มอีก

บรรทัดสุดท้ายของผลรันทำแบบนั้นพอดี เอนจินคืน lock ทั้งหมดของ t1 หลังจากนั้นไม่มีตัวขวางของ t2 เหลืออยู่บนคีย์นั้นอีก

งานที่ t1 ทำมาทั้งหมดหายไปด้วย และคนที่ต้องเริ่มใหม่คือคนเขียนโปรแกรม ไม่ใช่เอนจิน บทที่ 6 จะได้บิลใบเดียวกันนี้อีกครั้งจากกลไกคนละตัว

flowchart LR
  S["ก้าวแรก · ทั้งคู่ขอ shared บน order 1<br/>Granted ทั้งคู่ ไม่มีใครรอ"]
  T1["t1 · ถือ shared อยู่<br/>ขอยกระดับเป็น exclusive"]
  T2["t2 · ถือ shared อยู่<br/>ขอยกระดับเป็น exclusive"]
  S --> T1
  S --> T2
  T1 ==>|รอ t2 คืน shared · Blocked| T2
  T2 -.->|รอ t1 คืน shared · การเดินสายเจอวง| T1

คำบรรยายภาพ: ขอบสองเส้นชี้กลับหากันจนครบวง เอนจินจึงตอบ Deadlock แทนที่จะให้ t2 รอเพิ่มอีกตัว

เอนจินรู้ได้อย่างไรว่ากำลังจะวน

หัวข้อนี้เดินตามการตรวจหาวงทีละก้าว แล้วเทียบกับวิธีที่ PostgreSQL ใช้จริง

#[derive(Debug, Default)]
pub struct LockManager {
    holders: BTreeMap<String, Vec<(Xid, Mode)>>,
    /// ใครรอใครอยู่ · หนึ่ง transaction รอได้ทีละหนึ่งตัวเท่านั้น
    waits: BTreeMap<Xid, Xid>,
    pub blocked_steps: u32,
    pub deadlocks: u32,
}

waits คือทะเบียนว่าใครรอใครอยู่ และมันเก็บได้ตัวละหนึ่งรายการเท่านั้น สายการรอในเอนจินนี้ จึงเป็นเส้นตรงเสมอ ไม่ใช่กราฟที่แตกกิ่ง

    /// เดินตามสายการรอจาก `from` ว่าไปจบที่ `target` ไหม — ถ้าใช่แปลว่าจะเกิดวง
    fn would_cycle(&self, from: Xid, target: Xid) -> bool {
        let mut at = from;
        // จำนวนขอบมีจำกัด จึงวนได้ไม่เกินจำนวน transaction ที่รออยู่
        for _ in 0..=self.waits.len() {
            match self.waits.get(&at) {
                Some(&next) if next == target => return true,
                Some(&next) => at = next,
                None => return false,
            }
        }
        false
    }

การเดินเริ่มจากตัวที่ขวางเราอยู่ แล้วถามทะเบียนต่อไปเรื่อยๆ ว่าตัวนั้นรอใครอยู่อีกทอด

ถ้าเดินไปเจอตัวที่กำลังขออยู่ตอนนี้ แปลว่าการรอครั้งใหม่จะปิดวงพอดี
ถ้าเดินไปเจอตัวที่ไม่ได้รอใคร แปลว่าสายจบแล้ว รอได้อย่างปลอดภัย
จำนวนรอบวนถูกจำกัดด้วยจำนวนรายการในทะเบียน การเดินจึงไม่มีทางวนไม่รู้จบ

ข้อสุดท้ายไม่ใช่ของประดับ ถ้ามีวงค้างอยู่ในทะเบียนแล้วด้วยเหตุใดก็ตาม การเดินที่ไม่มีขอบเขต จะค้างอยู่ตรงนั้นไปเรื่อยๆ

ลองเดินตามผลรันจริง ตอน t1 ขอ ทะเบียนยังว่าง การเดินจาก t2 จึงจบทันทีเพราะ t2 ไม่ได้รอใคร เอนจินบันทึกว่า t1 รอ t2 แล้วบวกก้าวที่ถูกบล็อกไปหนึ่ง

ตอน t2 ขอ ตัวขวางคือ t1 การเดินจาก t1 อ่านทะเบียนได้ทันทีว่า t1 รอ t2 ซึ่งคือตัวที่กำลังขออยู่ เอนจินจึงบวก deadlock ไปหนึ่ง แล้วตอบกลับพร้อมหมายเลขของตัวที่ขวางอยู่ ซึ่งบทนี้เลือกให้เป็นเหยื่อ

PostgreSQL ทำสองอย่างนี้ต่างจากเอนจินของเรา อย่างแรกมันไม่ตรวจทุกครั้งที่มีคนรอ มันรอตามค่า deadlock_timeout ก่อนแล้วค่อยตรวจ เพราะมันสมมติว่า deadlock ไม่ได้เกิดบ่อย

อย่างที่สอง เอกสารของมันเขียนไว้ตรงๆ ว่ามันจะ abort ตัวใดตัวหนึ่งเอง และคาดเดาไม่ได้ว่าตัวไหน โปรแกรมที่เรียกใช้จึงต้องพร้อมรับ error นั้นทุกตัว ไม่ใช่พร้อมเฉพาะตัวที่คิดว่าจะแพ้

ราคาที่นับได้ และทางที่บทที่ 4 เลือก

หัวข้อนี้สรุปว่า 2PL ซื้ออะไรมาด้วยอะไร และบอกว่าบทถัดไปเปลี่ยนคำถามอย่างไร

2PL ให้ผลที่ถูกต้องจริง ไม่ใช่ถูกต้องโดยประมาณ ถ้าทุกคนเดินตามกฎสองช่วง ผลที่ได้อธิบาย ด้วยลำดับเรียงทีละตัวได้เสมอ

ราคาของมันมีสองก้อนที่นับได้ ก้อนแรกคือก้าวที่ถูกบล็อก ซึ่งเป็นงานที่หยุดรออยู่เฉยๆ ก้อนที่สองคือ abort ซึ่งเป็นงานที่ทำไปแล้วและถูกโยนทิ้ง

ทั้งสองก้อนโตขึ้นตามจำนวนคนที่แย่งของชิ้นเดียวกัน และผู้อ่านซึ่งไม่ได้แก้อะไรเลยก็ต้องจ่ายด้วย เพราะ shared lock ของเขายังขวาง exclusive ของคนอื่นอยู่ดี

บทที่ 4 เปลี่ยนคำถาม แทนที่จะถามว่าใครมีสิทธิ์แตะค่านี้ มันถามว่าใครควรเห็นค่าไหน ผู้อ่านจึงไม่ต้องขออนุญาตใครสักครั้ง และไม่มีอะไรให้รอ

MVCC ไม่ได้ทำให้บิลเป็นศูนย์ มันย้ายบิลไปไว้ที่อื่น ผู้เขียนสองคนที่แย่งคีย์เดียวกันยังต้องกันกันเอง เหมือนเดิม และบทที่ 1 แสดงไปแล้วว่าของที่ไม่มีใครเห็นยังกินที่ในที่เก็บอยู่จริง

บทที่ 5 จะเก็บบิลใบที่แพงที่สุดของ MVCC มาวางบนโต๊ะ คือ anomaly ที่ snapshot มองไม่เห็นเลย และไม่มีใครถูกบล็อกหรือถูก abort สักคนระหว่างที่มันเกิด

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

PostgreSQL 18 Documentation — 13.3. Explicit Locking (ตรวจแล้ว 2026-08-13) — ตารางโหมด lock ของจริงที่มีมากกว่าสองโหมด และหัวข้อ Deadlocks ที่ระบุว่า PostgreSQL ตรวจพบสภาพนี้เองแล้ว abort ตัวใดตัวหนึ่ง โดยคาดเดาไม่ได้ว่าตัวไหน
PostgreSQL 18 Documentation — 19.12. Lock Management (ตรวจแล้ว 2026-08-13) — deadlock_timeout และเหตุผลที่มันมีอยู่ คือรอไว้ก่อนแล้วค่อยตรวจ เพราะสมมติว่า deadlock ไม่ได้เกิดบ่อยในระบบจริง

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

ข้อ 1 / 3

2PL ห้ามคืน lock ตัวหนึ่งแล้วกลับไปขอ lock ตัวถัดไป ข้อใดอธิบายเหตุผลของข้อห้ามนี้ได้ถูกต้อง

คุม​ด้วย lock แล้ว​จ่าย​ด้วย​การ​รอ

สอง​ช่วง​ที่​ห้าม​สลับ​กัน

shared กับ exclusive และ​กฎ​ที่​ยาว​บรรทัด​เดียว

รัน​จริง สอง​คน​ขอ shared แล้ว​ต่าง​ขอ​ยก​ระดับ

ไม่มี​ใคร​ถอย​เอง​ได้

เอนจินรู้​ได้​อย่างไร​ว่า​กำลัง​จะ​วน

ราคา​ที่​นับ​ได้ และ​ทาง​ที่​บท​ที่ 4 เลือก