Consistent hashing — วงแหวน, virtual node และการวัดการย้าย key
บท 1 ตอบคำถามว่า เมื่อ event เกิดคนละเครื่อง จะรู้ลำดับเชิงเหตุผลได้อย่างไร — เราได้ vector clock เป็นเครื่องมือ ตอนนี้ขึ้นคำถามถัดไปของการยก kaen-kvstore ขึ้นเป็น cluster: key แต่ละตัวควรอยู่ replica ไหน ใน cluster N node เราต้อง map key ทุกตัวไปยัง node ที่รับผิดชอบมัน แบบที่ กระจายโหลดเรียบ และ — สำคัญกว่านั้น — เพิ่มหรือลด node แล้วไม่รื้อทั้ง cluster
คำถามนี้ฟังดูง่ายจนน่าจะตอบด้วยบรรทัดเดียว node = hash(key) % N แต่บรรทัดนั้นคือกับดัก บทนี้จะวัดให้เห็นด้วยเลขจริงว่ามันพังอย่างไร แล้วสร้าง consistent hashingconsistent hashingวาง node กับ key บนวงแหวน hash เดียวกัน เพิ่ม node ที่ N+1 ย้าย key แค่ ~1/(N+1) ไม่ใช่ทั้งหมด ที่ระบบจริง (Dynamo, Cassandra, Riak) ใช้จริงขึ้นมาแทน — วงแหวน hash เดียวที่วางทั้ง node และ key ลงไป พร้อม virtual nodevirtual nodeวาง node จริงหนึ่งตัวไว้ V จุดบนวงแหวน เพื่อเกลี่ยโหลดให้เรียบ (เหตุผลของ token ใน Dynamo) ที่เกลี่ยโหลด และเราจะพูดความจริงเรื่อง hash-sensitivity กันตรงๆ ว่าเลข “~1/(N+1)” ที่จะเห็นนั้น รันซ้ำได้ก็ต่อเมื่อ pin อะไรไว้บ้าง
คอร์สนี้ ต่อยอด repo kaen-kvstore จาก #22 (code ตัวอย่างกำลังจัดทำ) — บทนี้เพิ่มชั้น การวางตำแหน่ง key (key placement) ทับบน store เดิม: แทนที่แต่ละ key จะอยู่ node เดียว เราจะเลือกว่ามันควรอยู่ replica ไหนด้วยวงแหวน consistent hashing ยังยึด THE SCOPE LINE เดิม — consistent hashing เป็นฝั่ง ลง code รันจริง เพราะการย้าย key และ monotonicity นั้น วัดและ property-test ได้ ทั้งบทใช้ Rust std ล้วน: std SipHash (DefaultHasher) เป็นตัว hash เพียงตัวเดียว — ไม่มี serde, ไม่มี tokio, ไม่มี proptest วงแหวนที่สร้างในบทนี้จะกลับมาเลือก replica set ให้แต่ละ key อีกครั้งใน capstone (บท 8)
ทุก snippet pin ที่ Rust stable 1.97.1 (ออก 2026-07-16) และ edition = “2024” — เช็กเองด้วย rustc --version [dependencies] ใน Cargo.toml ว่างเปล่าตลอดคอร์ส — ZERO external crate code ในบทนี้แตะ std เพียง std::collections::BTreeMap กับ std::hash (DefaultHasher, Hash, Hasher) เท่านั้น ทุกโปรแกรม compile แบบ zero-warnings บน musl และ รันจริง — เลขทุกตัวด้านล่างคือ output จริงจากรันเดียวกัน seed ล็อกไว้ รันซ้ำได้ byte-identical
hash(key) % N — วิธีดิบที่พังตอนเพิ่ม node
หัวข้อที่มีชื่อว่า “hash(key) % N — วิธีดิบที่พังตอนเพิ่ม node”สัญชาตญาณแรกคือ: มี N node ก็เอา hash(key) % N เป็นเลข node กระจายดีมากตอนนิ่งๆ ปัญหาโผล่ตอน cluster เปลี่ยนขนาด — ซึ่งเกิดตลอดในชีวิตจริง (node เจ๊ง, สเกลออก, เพิ่มเครื่อง)
ลองคิดเลข: key ตัวหนึ่ง hash = h เมื่อ N=4 มันอยู่ node h % 4 พอเพิ่มเป็น N=5 มันอยู่ node h % 5 — ค่าสองอันนี้ตรงกันแค่บังเอิญเท่านั้น สำหรับ key ส่วนใหญ่ h % 4 ≠ h % 5 แทบทุก key ต้องย้ายบ้าน และการย้ายบ้านในระบบเก็บข้อมูลไม่ใช่เรื่องเล่นๆ — มันคือ copy ข้อมูลข้ามเครื่องมหาศาล cache miss ทั้ง cluster ในจังหวะเดียว
วัดจริงด้วย code เดียวกับที่บทนี้ใช้ (100,000 key, hash ตัวเดียวกัน):
let mut mod_moved = 0u64;for kk in &keys { let h = hash_u64(kk); if h % 4 != h % 5 { // อยู่คนละ node เมื่อ N: 4 -> 5 mod_moved += 1; }}// moved = 79759 (0.7976)--- naive hash(key) % N, N: 4 -> 5 ---moved=79759 (0.7976) — reshuffles ~all keysเพิ่ม node เดียว ย้าย key เกือบ 80% — เป็นสัดส่วนที่ไม่ขึ้นกับว่าเพิ่มจาก 4 เป็น 5 หรือ 40 เป็น 41 ด้วยซ้ำ นี่คือสิ่งที่ consistent hashing แก้: Karger และคณะเสนอในปี 1997 (STOC’97) ว่ามีวิธีจัดวางที่การเพิ่ม node ที่ N+1 ย้าย key แค่ ~1/(N+1) ไม่ใช่เกือบทั้งหมด
วงแหวน: วางทั้ง node และ key ลงบน u64 เส้นเดียว
หัวข้อที่มีชื่อว่า “วงแหวน: วางทั้ง node และ key ลงบน u64 เส้นเดียว”ไอเดียหลักสวยมาก แทนที่จะ map key ไป ดัชนี node (ซึ่งเปลี่ยนความหมายทุกครั้งที่ N เปลี่ยน) เรา hash ทั้ง node และ key ลงบน ปริภูมิเดียวกัน คือ u64 ทั้งช่วง แล้วจินตนาการว่า u64 เป็น วงแหวน (0 ต่อกับ u64::MAX) กฎการหาเจ้าของ key: จาก hash ของ key ให้ เดินตามเข็มนาฬิกาไปหา node ตัวแรกที่เจอ
โครงสร้างที่เหมาะเป๊ะคือ BTreeMap<u64, NodeId> — มันเรียง key ให้อัตโนมัติ และมี range(k..).next() ที่แปลว่า “node ตัวแรกที่ hash ≥ k” พอดี ส่วนการวนขอบวงแหวน (key ที่ hash สูงกว่า node ทุกตัว) ก็ห่อกลับไปหา node ที่ hash น้อยที่สุด:
use std::collections::hash_map::DefaultHasher;use std::collections::BTreeMap;use std::hash::{Hash, Hasher};
type NodeId = u32;
// hash เดียวของทั้งบท: std DefaultHasher = SipHash-1-3, fixed keys -> deterministicfn hash_u64<T: Hash>(x: &T) -> u64 { let mut h = DefaultHasher::new(); x.hash(&mut h); h.finish()}
struct Ring { vnodes: u32, points: BTreeMap<u64, NodeId>,}impl Ring { fn new(vnodes: u32) -> Self { Ring { vnodes, points: BTreeMap::new() } } fn add(&mut self, node: NodeId) { for v in 0..self.vnodes { // hash (node, v) — ไม่ใช่ node เดี่ยว ๆ (จะอธิบายในหัวข้อ virtual node) self.points.insert(hash_u64(&(node, v)), node); } } fn route(&self, key: &str) -> NodeId { let k = hash_u64(&key); match self.points.range(k..).next() { Some((_, &n)) => n, // node ตัวแรกตามเข็ม (hash >= k) None => *self.points.values().next().unwrap(), // วนขอบ: ห่อไป node hash ต่ำสุด } }}route คือหัวใจทั้งหมด: hash key แล้ว range(k..).next() คว้า node ตัวแรกที่ hash ≥ k ถ้าไม่มี (key อยู่เลย node สุดท้ายบนวง) ก็ วนขอบ กลับไปหา values().next() คือ node hash ต่ำสุด จุดตายที่พลาดกันคือลืมกรณีวนขอบนี้ — range(k..).next() จะคืน None แล้วโปรแกรม panic หรือ route key ที่ hash สูงสุดผิด node
สมบัติที่ทำให้ consistent hashing มีค่าไม่ใช่แค่ “ย้ายน้อย” แต่คือ monotonicity: การเพิ่ม node ใหม่ ขโมย key มาจาก node เดิมได้เท่านั้น มัน ไม่มีวันสับ key ไปมาระหว่าง node เดิมด้วยกัน (Karger 1997) เหตุผลเชิงเรขาคณิตชัดมาก — node ใหม่ลงไปนั่งที่จุดหนึ่งบนวง มันรับผิดชอบเฉพาะช่วงส่วนโค้งที่ ตกทอดมาจาก node ถัดไปตามเข็ม เท่านั้น key นอกช่วงนั้นยังเดินไปเจอ node เดิมตัวเดิมเป๊ะ นี่คือ invariant ที่ ตรวจได้จริง: ทุก key ที่ย้าย ปลายทางต้องเป็น node ใหม่ (illegal_reshuffle == 0)
วัดการย้าย key: 4 → 5 ย้ายแค่ ~1/(N+1)
หัวข้อที่มีชื่อว่า “วัดการย้าย key: 4 → 5 ย้ายแค่ ~1/(N+1)”ทีนี้วัดของจริง เราตั้งวงแหวนด้วย 4 node (id 0–3) แต่ละ node วาง V=100 จุดบนวง กระจาย K=100,000 key ("key:0" ถึง "key:99999") จดว่าแต่ละ key อยู่ node ไหน แล้ว เพิ่ม node ที่ 5 (id 4) route ใหม่ทั้งหมด แล้วนับว่ากี่ key ย้าย และย้ายไปไหน:
let v = 100u32;let n = 4u32; // 4 node เดิม: 0,1,2,3let mut ring = Ring::new(v);for node in 0..n { ring.add(node); }let before = assign_all(&ring, &keys);
ring.add(n); // เพิ่ม node ที่ (N+1) id = 4let after = assign_all(&ring, &keys);
let mut moved = 0u64;let mut moved_to_new = 0u64;let mut illegal_reshuffle = 0u64;for i in 0..k { if before[i] != after[i] { moved += 1; if after[i] == n { moved_to_new += 1; } else { illegal_reshuffle += 1; } }}let frac = moved as f64 / k as f64;assert_eq!(illegal_reshuffle, 0, "monotonicity: existing nodes must not reshuffle");assert_eq!(moved, moved_to_new, "every moved key must go to the NEW node");assert!((frac - 1.0 / (n as f64 + 1.0)).abs() < 0.03, "movement not near 1/(N+1)");--- consistent hashing: V=100, K=100000, N=4 -> add node 4 ---moved=19195 (0.1920) ideal 1/(N+1) = 0.2000load=[21347, 19633, 21701, 18124, 19195] (max/min imbalance = 1.20x)illegal_reshuffle=0 moved_to_new=19195OK: both properties hold (monotonic + near 1/(N+1))เทียบกับวิธีดิบที่ย้าย 0.7976 — consistent hashing ย้ายแค่ 0.1920 ใกล้ค่าอุดมคติ 1/(N+1) = 1/5 = 0.20 มาก และสังเกตสองบรรทัดสำคัญ: illegal_reshuffle=0 (ไม่มี key ไหนสับไปมาระหว่าง node เดิม) และ moved == moved_to_new == 19195 (key ที่ย้ายทุกตัว ย้ายเข้า node ใหม่ หมด) — นี่คือ monotonicity ที่วัดได้เป็นตัวเลข ไม่ใช่คำกล่าวอ้าง
สังเกต assert ตัวที่สาม: (frac - 1.0/(N+1)).abs() < 0.03 — เรา ไม่ assert_eq!(moved, 19195) เพราะ 19195 เป็นเลขที่ ขึ้นกับ hasher + จำนวน vnode + keyset + Rust version ทั้งชุด สิ่งที่ทฤษฎีการันตีคือ “ใกล้ 1/(N+1)” ไม่ใช่ “เท่ากับ 19195 เป๊ะ” การ assert แบบ band คือการ test สมบัติที่ เป็นจริงตามทฤษฎี ส่วน 19195 คือ หลักฐานการรัน ที่ pin ไว้ — สองอย่างนี้คนละเรื่องกัน
graph TD
subgraph Ring["วงแหวน u64 (เดินตามเข็มนาฬิกา)"]
A["node A · vnode หลายจุด"]
B["node B · vnode หลายจุด"]
C["node C · vnode หลายจุด"]
NEW["node ใหม่ D (เพิ่งเพิ่ม)"]
end
K1["key: hash(k)"] -->|"เดินตามเข็มไปเจอ vnode ตัวถัดไป"| A
NEW -.->|"ขโมยเฉพาะช่วงโค้งที่ตัวเองครอบ"| B
K2["key ที่เคยไป B ในช่วงนั้น"] -->|"หลังเพิ่ม D"| NEW
คำบรรยายภาพ: key เดินตามเข็มนาฬิกาไปหา vnode ตัวถัดไปบนวงแหวน เพิ่ม node D = วาง vnode ใหม่หลายจุดลงวง แต่ละจุด ขโมย เฉพาะ key ในช่วงโค้งที่ตัวเองครอบมาจาก node ถัดไป — key นอกช่วงยังเดินไปเจอ node เดิมเป๊ะ (นั่นคือ monotonicity: illegal_reshuffle=0)
virtual node: ทำไม V=1 ถึงกระจายโหลดพัง
หัวข้อที่มีชื่อว่า “virtual node: ทำไม V=1 ถึงกระจายโหลดพัง”ใน code add เราวาง node หนึ่งตัวลง V จุด บนวง ไม่ใช่จุดเดียว แต่ละจุดคือ virtual node (Dynamo เรียก token) ทำไมต้องทำแบบนี้? ลองคิดถ้า V=1: node 4 ตัวคือ 4 จุดสุ่มบนวง ช่วงโค้งระหว่างจุดที่อยู่ติดกันจะ ยาวไม่เท่ากันเลย — node ที่บังเอิญมีช่วงโค้งกว้างจะรับ key เยอะกว่า node ที่ช่วงแคบมาก เกิด hotspot
วิธีแก้คือวาง node เดียวไว้ หลายจุด: ยิ่ง V สูง ช่วงโค้งรวมของแต่ละ node ยิ่งเข้าใกล้ค่าเฉลี่ยตามกฎของเลขจำนวนมาก โหลดจึงเรียบขึ้น วัดจริงด้วยการกวาดค่า V แล้วดู imbalance = โหลดสูงสุด / โหลดต่ำสุด (ยิ่งใกล้ 1.00 ยิ่งเรียบ) บน cluster 5 node หลังเพิ่ม:
--- virtual-node sweep (N=4 -> add node 4) --- V movement imbalance(max/min, 5 nodes) 1 0.2181 3.26x 10 0.2121 1.63x 50 0.1735 1.56x 100 0.1920 1.20x 200 0.1938 1.21x 500 0.1991 1.05xV=1 node ที่โหลดหนักสุดรับงานมากกว่า node ที่เบาสุด 3.26 เท่า — ยอมรับไม่ได้ในโปรดักชัน พอ V=500 imbalance ลงเหลือ 1.05 เท่า เกือบเรียบสนิท นี่คือเหตุผลตรงๆ ที่ Dynamo (SOSP’07) วางแต่ละ node เป็นหลาย token บนวง ไม่ใช่ token เดียว สังเกตด้วยว่า column movement แกว่งอยู่แถว 0.17–0.22 รอบๆ 1/(N+1)=0.20 ทุกค่า V — การย้าย key น้อยเป็นสมบัติของ วงแหวน ส่วนการกระจายโหลดเรียบเป็นสมบัติของ จำนวน vnode คนละเรื่องที่จูนแยกกัน
จุดพลาดที่ callout add เตือนไว้เชื่อมตรงนี้พอดี: ถ้า hash แค่ node เดี่ยวๆ แทน (node, v) ทุก vnode ของ node เดียวกันจะ hash ไปจุดเดียวกันหมด — V ยุบเหลือ 1 ทันที กลับไป hotspot 3.26× โดยที่ code ยัง ดูเหมือน วาง V จุด
ความจริงเรื่อง hash-sensitivity: ทำไม 0.1920 ถึงไม่ใช่เลขศักดิ์สิทธิ์
หัวข้อที่มีชื่อว่า “ความจริงเรื่อง hash-sensitivity: ทำไม 0.1920 ถึงไม่ใช่เลขศักดิ์สิทธิ์”เลข 19195 (0.1920) รันซ้ำได้ byte-identical ก็ต่อเมื่อ สี่อย่างนี้ pin ครบ: (1) ตัว hash เป็น DefaultHasher::new() — SipHash-1-3 ที่ std ตั้ง key คงที่ (0, 0) ให้ ทำให้ deterministic; (2) จำนวน vnode V=100; (3) keyset เป๊ะ "key:0".."key:99999"; (4) Rust version 1.97.1 เพราะ std เขียนกำกับไว้ตรงๆ ว่า algorithm ของ DefaultHasher “ไม่รับประกันว่าจะคงเดิมข้าม version”
HashMap ปกติใช้ RandomState ที่ สุ่ม key ของ SipHash ใหม่ทุกครั้งที่ process เริ่ม (กัน HashDoS) ถ้าเผลอเอา hasher แบบนั้นมาสร้างวงแหวน การวาง key จะ เปลี่ยนทุกครั้งที่รันโปรแกรม — เลข 0.1920 จะกลายเป็นคนละค่าทุกรัน property test จะ โกหก (รันแดงซ้ำไม่ได้) เราจึงเรียก DefaultHasher::new() ตรงๆ ซึ่ง fixed-key เสมอ ไม่ใช่ RandomState — วิธีตรวจว่าเราทำถูกคือ รันโปรแกรมซ้ำ 3 รอบแล้วต้องได้ 19195 เท่ากันทุกรอบ (ยืนยันแล้วว่าเป็นเช่นนั้น)
ที่จริงจังกว่านั้น: ตอนสร้าง framework ของคอร์ส แผงทดสอบวัดได้ 19.3% ส่วนรันของบทนี้วัดได้ 19.2% — ส่วนต่างเล็กๆ นี้ ไม่ใช่ bug มันคือ หลักฐานสด ว่าเลขนี้ไวต่อ keyset/V ที่ต่างกันแม้เพียงนิดเดียว บทเรียนคือ: สอนว่า “ใกล้ 1/(N+1)” แล้ว assert ด้วย band abs < 0.03 เสมอ ห้าม assert_eq! บนจำนวนเป๊ะๆ — นั่นคือการ hard-code หลักฐานการรันครั้งหนึ่งขึ้นเป็นทฤษฎี ซึ่งจะพังทันทีที่ใครอัป Rust หรือเปลี่ยน keyset
C — ดีเทอร์มินิสซึมคือวินัย: เลข 19195 รันซ้ำได้เพราะ DefaultHasher::new() fixed-key + V + keyset + Rust version pin ครบ ไม่ใช่ RandomState (ซึ่งสุ่มใหม่ทุก process → placement มั่ว, เลขไม่มีวันซ้ำ) — ตรวจด้วยการรันซ้ำต้องได้ค่าเดิม และ assert ด้วย tolerance band ไม่ใช่ค่าเป๊ะ
D — นี่คือกลไกจริงของ Dynamo/Cassandra/Riak: consistent hashing + virtual node/token คือวิธีวาง key จริงของ Amazon Dynamo (SOSP’07) ไม่ใช่ของกุขึ้นเพื่อสอน — imbalance 3.26×→1.05× ที่วัดได้คือเหตุผลเชิงตัวเลขว่าทำไม Dynamo ถึงวางแต่ละ node เป็นหลาย token บนวง
สรุปก่อนไปต่อ
หัวข้อที่มีชื่อว่า “สรุปก่อนไปต่อ”บทนี้ตอบว่า key ควรอยู่ replica ไหน: วิธีดิบ hash(key) % N ย้าย key เกือบทั้ง cluster ทุกครั้งที่เพิ่ม node (วัดได้ 0.7976 บน 4→5) เพราะ h % 4 กับ h % 5 ตรงกันแค่บังเอิญ; consistent hashingconsistent hashingวาง node กับ key บนวงแหวน hash เดียวกัน เพิ่ม node ที่ N+1 ย้าย key แค่ ~1/(N+1) ไม่ใช่ทั้งหมด วางทั้ง node และ key ลงบนวงแหวน u64 เดียว (BTreeMap<u64, NodeId>) key เดินตามเข็มไปหา node ตัวแรกด้วย range(k..).next() แล้ววนขอบที่ seam — เพิ่ม node ที่ N+1 ย้าย key แค่ ~1/(N+1) (วัดได้ 19195/100000 = 0.1920 บน 4→5) และย้ายเข้า node ใหม่ เท่านั้น (illegal_reshuffle=0, moved==moved_to_new) คือ monotonicity ที่ตรวจได้; virtual nodevirtual nodeวาง node จริงหนึ่งตัวไว้ V จุดบนวงแหวน เพื่อเกลี่ยโหลดให้เรียบ (เหตุผลของ token ใน Dynamo) (token ของ Dynamo) วางแต่ละ node เป็น V จุดเพื่อเกลี่ยโหลด — imbalance ลดจาก 3.26× (V=1) เหลือ 1.05× (V=500); และเลข 0.1920 นั้น ไม่ใช่เลขศักดิ์สิทธิ์ — มันรันซ้ำได้ก็เพราะ DefaultHasher::new() fixed-key + V + keyset + Rust 1.97.1 pin ครบ (แผงวัด 19.3% รันนี้วัด 19.2% = หลักฐานสดของ hash-sensitivity) จึงตรวจด้วย tolerance band เสมอ ทุก snippet compile zero-warnings บน Rust 1.97.1 / edition 2024 / std ล้วน และรันได้เลขตามที่เห็น
บท 3 เราจะกระจายสำเนา: ตอนนี้เรารู้แล้วว่า key ตัวหนึ่ง ควรอยู่ node ไหน บทหน้าเราจะเก็บมันไว้ หลาย replica แล้วถามว่าต้องเขียนสำเร็จกี่ตัว (W) อ่านตอบกี่ตัว (R) จาก N สำเนา ถึงจะการันตีว่า อ่านเจอค่าล่าสุดเสมอ — คำตอบคือ quorumquorumเขียนต้อง ack ≥W อ่านต้องตอบ ≥R; ถ้า W+R>N อ่านจะทับ write ล่าสุดเสมอ และเงื่อนไข W+R>N พร้อม read-repair ที่เอา version vector จากบท 1 มาใช้ตรวจ conflict
บทนี้อิงต้นทางที่ลงวันที่กำกับ อ่านต่อได้โดยตรง:
- Karger, Lehman, Leighton, Panigrahy, Levine, Lewin — “Consistent Hashing and Random Trees” (STOC’97, 1997) (เข้าถึง 2026-07-24) — ต้นกำเนิดของ consistent hashing: เพิ่ม node ที่ N+1 ย้าย key แค่ ~1/(N+1) เทียบกับ ~ทั้งหมดของ modulo-N และสมบัติ monotonicity (เพิ่ม node ไม่สับ key ระหว่าง node เดิม)
- DeCandia et al. — “Dynamo: Amazon’s Highly Available Key-value Store” (SOSP’07, 2007) (เข้าถึง 2026-07-24) — Dynamo ใช้ consistent hashing + virtual node/token จริงในการวาง key; เหตุผลของ token คือเกลี่ยโหลดให้เรียบ (ที่บทนี้วัดเป็น imbalance 3.26×→1.05×)
- Rust std —
std::collections::hash_map::DefaultHasher(เข้าถึง 2026-07-24) — SipHash-1-3 ที่ตั้ง key คงที่ให้ deterministic แต่ std กำกับไว้ว่า algorithm “ไม่รับประกันว่าคงเดิมข้าม version”; ต่างจากRandomStateของHashMapที่สุ่ม key ใหม่ทุก process
เช็กความเข้าใจ — บทที่ 2
ข้อ 1 / 3ทำไม hash(key) % N ถึงย้าย key เกือบทั้ง cluster (วัดได้ 0.7976) ตอนเพิ่ม node จาก 4 เป็น 5?