⚡ Go Senior Mentor Engine | Phase 1: Week 1 - Day 3 (Master Edition)
Score: 0 / 15
Answered: 0 / 15
Accuracy: 0%
Phase 1: Week 1 Map Internals Master Edition (15 Questions + 3 Labs)

Day 3: Map Internals, `hmap`/`bmap` Architecture & Evacuation Mechanics

เจาะลึกสถาปัตยกรรมระดับฮาร์ดแวร์ของ Go Map: ล้างภาพจำจาก Java HashMap ทำความเข้าใจบทบาทของ hmap, bmap, tophash, กลไกการขยายขนาดแบบ Incremental Evacuation และข้อจำกัด Unaddressable Value ในระบบ Race Ingestion

0. The "Why": ทำไม Go Map ถึงไม่เหมือน Map ในภาษาอื่น?

ในฝั่ง Java / Spring Boot คุณคุ้นเคยกับคำว่า: "Map ก็แค่กล่องเก็บ Key-Value คู่กัน อยากได้อะไรก็ map.get(key) จบ"
แต่ในระดับวิศวกรรมระบบของ Go ทีมออกแบบต้องเผชิญปัญหาฮาร์ดแวร์ 2 ข้อใหญ่:

  1. CPU Cache Miss: ถ้าเอา Key กับ Value ไปผูกเป็น Node เล็กๆ แล้วกระจายทั่วมุม RAM แบบ Java HashMap ทุกครั้งที่ค้นหา CPU ต้องกระโดดข้ามตำแหน่ง RAM ไปมา (Pointer Chasing) ทำให้ระบบช้าลงมหาศาล
  2. Memory Alignment Waste (รูโหว่ Padding): ถ้า Key กับ Value มีขนาดไม่เท่ากัน (เช่น Key 1 Byte, Value 8 Bytes) การจัดวางคู่กันซ้ำๆ จะเกิด Memory Hole ไร้ประโยชน์จำนวนมาก

Go จึงแก้ปัญหานี้ด้วยการแบ่งหน้าที่สถาปัตยกรรมออกเป็น 4 คำศัพท์สำคัญ:

  • `hmap` (Header Map - "ผู้จัดการแผนที่"): Struct หลักที่คุมภาพรวมของ Map เช่น เก็บจำนวนข้อมูลทั้งหมด (count), จำนวนถังทั้งหมด (คำนวณผ่าน B), และถือ Pointer ชี้ไปยังอาร์เรย์ของถังข้อมูลจริง
  • `bmap` (Bucket Map - "ถังเก็บของขนาด 8 สล็อต"): ถังเก็บข้อมูลจริง โดย 1 ถังจุได้ 8 คู่พอดี เพื่อให้ขนาดของถังฟิตกับ CPU Cache Line (~64 Bytes) และจัดวางแบบ Key 8 ตัวติดกัน แล้วตามด้วย Value 8 ตัวติดกัน เพื่อขจัด Padding Bytes ทิ้งไป 100%
  • `tophash` ("ป้ายแท็กย่อหน้าถัง"): อาร์เรย์ของเลขย่อ 1 ไบต์ (ตัดมาจาก 8 บิตบนของรหัสแฮช) แปะไว้หน้าสล็อตทั้ง 8 ช่อง เวลาค้นหา CPU จะเอาเลขนี้ไปกวาดเทียบอย่างรวดเร็วระดับ Vectorized Register ถ้าป้ายไม่ตรงจะข้ามทันทีโดยไม่ต้องเสียเวลาอ่าน Key ก้อนเต็ม
  • `Evacuation` ("การทยอยอพยพข้อมูล"): การขยายขนาดถังเป็น 2 เท่าเมื่อข้อมูลแน่นเกินเกณฑ์ โดย Go จะทยอยย้ายข้อมูลทีละ 2 ถังทุกครั้งที่มีการเขียนหรือลบ เพื่อไม่ให้ระบบเกิด Latency Spike บล็อกโปรแกรม
1. Deep-Dive: สถาปัตยกรรมภายในของ `hmap` และ `bmap`

1.1 Header Map (`hmap`) - ผู้จัดการใหญ่ของ Map

ใน Go runtime ตัวแปร m := make(map[K]V) คือ Pointer ขนาด 8 Bytes ที่ชี้ไปยัง Struct hmap บน Heap:

type hmap struct {
    count      int            // จำนวน Element ทั้งหมดใน Map
    flags      uint8          // บิตตรวจจับ Concurrent Read/Write (ถ้าชนกันจะ Fatal Crash)
    B          uint8          // ค่า log2 ของจำนวน Buckets (มีทั้งหมด 2^B buckets)
    noverflow  uint16         // จำนวน overflow buckets โดยประมาณ
    hash0      uint32         // Hash seed สุ่มเพื่อป้องกัน Hash Flooding DoS
    buckets    unsafe.Pointer // Pointer ชี้ไปยังอาร์เรย์ของ bmap ตัวจริง
    oldbuckets unsafe.Pointer // Pointer ชี้ไปยังอาร์เรย์เดิมระหว่างทำ Evacuation
    nevacuate  uintptr        // ความคืบหน้าของการย้ายข้อมูลไปยัง Bucket ใหม่
}

1.2 Bucket Map (`bmap`) - โครงสร้างจัดเก็บข้อมูลจริงที่ Compiler สร้างขึ้น

ถ้าคุณไปเปิดดูซอร์สโค้ด Go ที่ไฟล์ src/runtime/map.go คุณจะพบเพียง: 

type bmap struct {
    tophash [8]uint8
}

ทำไมถึงมีแค่นี้? เพราะ Go ไม่มี Generics ในระดับ Runtime และไม่ต้องการทำ Boxing ให้เป็น interface{}/Object บน Heap เหมือน Java HashMap<K,V> ตัว Go Compiler จึงทำการ Synthesized โครงสร้าง Struct จริงขึ้นมาในหน่วยความจำตามชนิดของ Key และ Value ดังนี้: 

type bmap struct {
    tophash  [8]uint8      // 8 บิตบนของ Hash Code สำหรับเปรียบเทียบสล็อตอย่างรวดเร็ว (8 Bytes)
    keys     [8]KeyType    // อาร์เรย์เก็บ Key เรียงติดกัน 8 ตัว (ไม่สลับกับ Value!)
    elems    [8]ValueType  // อาร์เรย์เก็บ Value เรียงติดกัน 8 ตัว
    overflow *bmap         // Pointer 8 Bytes ชี้ไปยัง Overflow Bucket ถัดไปเมื่อเกิด Collision เกิน 8 ตัว
}
🎯 ทำไมต้องเรียง Key 8 ตัว แล้วตามด้วย Value 8 ตัว?
หากจัดเรียงสลับคู่ Key/Value, Key/Value ในกรณีที่ Key และ Value มีขนาดไบต์ไม่เท่ากัน (เช่น Key 1 Byte, Value 8 Bytes) จะเกิด Alignment Padding แทรก 7 Bytes ทุกๆ คู่ รวมเสียพื้นที่ทิ้งเปล่า 56 Bytes ต่อ Bucket!
การจัดกลุ่ม keys [8]Key แล้วตามด้วย elems [8]Value ทำให้ข้อมูลขนาดเท่ากันเรียงติดกัน กำจัดรูโหว่ Padding ทิ้งได้ 100%
+---------------------------------------------------------------------------------------------------+ | bmap MEMORY LAYOUT IN RAM (map[uint8]uint64 - ความจุ 8 สล็อต) | +---------------------------------------------------------------------------------------------------+ | [0x00 - 0x07] : tophash [8]uint8 | | [ t0 | t1 | t2 | t3 | t4 | t5 | t6 | t7 ] = 8 Bytes | +---------------------------------------------------------------------------------------------------+ | [0x08 - 0x0F] : keys [8]uint8 | | [ k0 | k1 | k2 | k3 | k4 | k5 | k6 | k7 ] = 8 Bytes | +---------------------------------------------------------------------------------------------------+ | [0x10 - 0x4F] : elems [8]uint64 | | [ val0 ][ val1 ][ val2 ][ val3 ] | | [ val4 ][ val5 ][ val6 ][ val7 ] = 64 Bytes | +---------------------------------------------------------------------------------------------------+ | [0x50 - 0x57] : overflow *bmap | | [ 8-byte pointer to next overflow bucket or nil ] = 8 Bytes | +---------------------------------------------------------------------------------------------------+ | รวมขนาดทั้งสิ้น: 88 Bytes เต็มเม็ดเต็มหน่วย ไม่มี Memory Alignment Padding แทรกแม้แต่ไบต์เดียว! | +---------------------------------------------------------------------------------------------------+

1.3 กฎเหล็ก 128-byte Indirection ของ Bucket

หากชนิดข้อมูลของ Key หรือ Value มีขนาด มากกว่า 128 Bytes ตัว Go Compiler จะปรับสถาปัตยกรรมอัตโนมัติ โดยไม่เก็บก้อน Struct ก้อนยักษ์นั้นลงใน bmap ตรงๆ แต่จะเปลี่ยนไปเก็บ Pointer ขนาด 8 ไบต์ชี้ไปยัง Heap แทน เพื่อป้องกันไม่ให้ขนาดของ bmap บวมจนหลุดออกจากขนาด CPU L1/L2 Cache Line

⚠️ Spring Boot / JVM Mental Trap (Unaddressable Value):
ใน Java คุณเขียน map.get(key).setCheckpoint(2) ได้เพราะมันคือ Reference แต่ใน Go: ค่า Value ที่เก็บใน Map ไม่สามารถขอ Memory Address ได้ (Unaddressable) ห้ามสั่ง &m[k] หรือแก้ไขฟิลด์ของ Struct ใน Value โดยตรง เช่น m[bib].Checkpoint = 2 จะคอมไพล์ไม่ผ่านทันที เพราะตำแหน่ง RAM ของ Struct นั้นอาจถูกย้ายตลอดเวลาเมื่อเกิด Evacuation!
2. Visual Architecture: วงจรการค้นหา (Hash $\to$ Bucket $\to$ Tophash)

เมื่อมีคำสั่งค้นหานักวิ่งด้วยคำสั่ง s := m[key] ขั้นตอนในระดับ Assembly และ RAM มีดังนี้:

  1. นำ Key ไปคำนวณผ่าน Hash Function ร่วมกับ hmap.hash0 ได้รหัสแฮชขนาด 64-bit
  2. Low-order bits (B บิตท้าย): นำบิตท้ายจำนวน $B$ บิต ไปคำนวณหาตำแหน่ง Bucket Index (เช่น $B=4$, บิตท้ายคือ 1011 = 11 $\to$ ตกใน Bucket เบอร์ 11) จากนั้นกระโดดไปยัง Address ของ Bucket นั้นทันที
  3. High-order bits (8 บิตแรก): นำบิตบน 8 บิตแรกมาเป็น tophash กวาดเทียบกับอาร์เรย์ tophash [8]uint8 ใน Bucket ด้วย Vectorized Instruction
  4. ถ้าค่า tophash ตรงกัน จึงเข้าไปเทียบค่า Key ใน keys[i] ถ้าตรงกันจึงดึงข้อมูลจาก elems[i] ส่งกลับ
  5. ถ้าค้นครบ 8 ช่องใน Bucket แล้วยังไม่พบ และฟิลด์ overflow != nil ตัว Runtime จะวิ่งตาม Pointer ไปค้นหาต่อใน Overflow Bucket จนกว่าจะเจอหรือสิ้นสุด linked-list
+---------------------------------------------------------------------------------------------------+ | LOOKUP WORKFLOW: s := m[key] | +---------------------------------------------------------------------------------------------------+ | 1. Hash(key, hash0) = 0xFA3C9981_0000000B (64-bit Hash) | | │ │ | | ┌───────────────────┘ └────────────────────┐ | | ▼ High 8 bits (0xFA) ▼ Low B bits (e.g. B=4 -> 0x0B=11)| | [tophash Target] [Bucket Target: #11] | | │ │ | | │ ▼ | | │ Go to hmap.buckets[11] | | │ │ | | v v | | 2. สแกน tophash ใน bmap #11: | | +------------------------------------------------------------------------------------------+ | | | tophash : [ 0x12 | 0xFA | 0x00 | 0x88 | 0x00 | 0x00 | 0x00 | 0x00 ] | | | +---------------------▲--------------------------------------------------------------------+ | | │ | | └─ MATCH AT SLOT #1! (สแกนเร็วระดับนาโนวินาที) | | │ | | 3. ตรวจสอบ Key จริง: ▼ | | keys[1] == key? ──(YES)──> Return elems[1] ทันที! | | └──(NO)──> Hash collision! สแกนช่องถัดไป หรือตาม overflow pointer | +---------------------------------------------------------------------------------------------------+
3. Growth Trigger & Incremental Evacuation Mechanics

3.1 เกณฑ์การขยายขนาด (Growth Trigger)

Go Map จะเริ่มเตรียมขยายขนาดเมื่อเข้าเงื่อนไขข้อใดข้อหนึ่ง:

  • Load Factor เกินเกณฑ์: ค่าเฉลี่ยข้อมูล $\frac{\text{count}}{2^B} > 6.5$ (เฉลี่ยใน 1 ถังเริ่มมีข้อมูลเกิน 6.5 ตัว จากความจุ 8 ตัว) $\to$ ทำการ Double Growth ($B = B + 1$) จอง Bucket ใหม่เป็นสองเท่า
  • มี Overflow Buckets มากเกินไป (Same-size Grow): มีถังล้นเยอะผิดปกติแม้ข้อมูลรวมจะน้อย (เกิดจากการเพิ่มแล้วลบซ้ำๆ ทำให้ถังพรุนเป็นรูโหว่) $\to$ ทำการ Re-organize จัดเรียงข้อมูลใหม่ในขนาด $B$ เท่าเดิมเพื่อคืนพื้นที่ Memory

3.2 Incremental Evacuation (ย้ายข้อมูลแบบไม่หยุดโลก)

  • Go จะเก็บ oldbuckets ไว้ และจอง buckets ใหม่ที่มีขนาด 2 เท่า
  • การย้ายข้อมูล (Evacuation) จะเกิดขึ้น ทีละ 2 Buckets ในทุกๆ ครั้งที่มีคำสั่ง Write หรือ Delete เข้ามาใน Map
  • ระหว่างที่ยังย้ายไม่เสร็จ คำสั่ง Read จะตรวจสอบก่อนว่า Bucket นั้นย้ายแล้วหรือยัง ถ้ายังจะวิ่งไปอ่านจาก oldbuckets
⚠️ Fatal Error: concurrent map read and map write
Go Map **ไม่ใช่ Thread-safe** ภายในตัว `hmap` มีบิต `flags` ถ้ามีกอร์ลูทีนหนึ่งกำลังเขียน แล้วมีอีกกอร์ลูทีนเข้ามาอ่านหรือเขียน ตัว Runtime จะทำการ Panic/Crash ทันที (Exit Code 2) โดยที่ไม่สามารถใช้ recover() ดักจับได้! ในงานระบบ Concurrent ต้องป้องกันด้วย sync.RWMutex หรือใช้ sync.Map เสมอ
🧠 Knowledge Verification: Master 15-Question Matrix (Map Architecture)
🛠️ Hands-on Lab 1.3.1: Pre-allocating Map Capacity for Ingestion Stream
Zero-Evacuation Ingestion
📋 โจทย์ข้อกำหนด:
  1. สร้างฟังก์ชัน InitRunnerIndex(expectedRunners int) map[int64]string
  2. ต้องใช้ make(map[int64]string, cap) จอง Bucket ล่วงหน้าเพื่อไม่ให้เกิด Incremental Evacuation ระหว่าง Ingestion
  3. หาก expectedRunners <= 0 ให้คืนค่า empty map ที่จองขนาด 0
🛠️ Hands-on Lab 1.3.2: Struct Value Mutation Workaround in Map
Unaddressable Value Fix
📋 โจทย์ข้อกำหนด:
  1. กำหนด struct RunnerSplit มีฟิลด์ Bib int64 และ Checkpoint int64
  2. ฟังก์ชัน UpdateCheckpoint(m map[int64]RunnerSplit, bib int64, newCP int64) ต้องอัปเดต Checkpoint ให้สำเร็จ
  3. ต้องแก้ปัญหา cannot assign to struct field in map ด้วยการดึง Value ออกมาแก้แล้ว Re-assign กลับลง Map
🛠️ Hands-on Lab 1.3.3: High-Performance Set Using `struct{}`
Zero-Byte Value Optimization
📋 โจทย์ข้อกำหนด:
  1. เขียนฟังก์ชัน RecordUniqueCheckpoints(chips []int64) map[int64]struct{}
  2. ใช้ map[int64]struct{} เพื่อทำ Set จัดเก็บคีย์ที่ไม่ซ้ำกัน โดย Value ต้องใช้ struct{}{} ซึ่งมีขนาด 0 Bytes เพื่อประหยัด RAM สูงสุด