← Redis
Bare-Metal Memory Engineering
Redis Core Principles & Deep RAM Internals
The Engineering Blueprint: Memory Allocators (jemalloc), Object Headers, Compact Encodings, Cache-Line Physics, and Eviction Math
1. Bare-Metal Reality: RAM Access Physics vs Disk-First Abstraction
ในการพัฒนาซอฟต์แวร์ระดับองค์กร ภาพจำเดิมจากฝั่ง RDBMS (เช่น PostgreSQL หรือ MySQL) คือการมองว่า "ดิสก์คือบ้านถาวรของข้อมูล ส่วน RAM เป็นเพียง Buffer Pool ชั่วคราว (shared_buffers)"
แต่สำหรับ Redis ปรัชญาสถาปัตยกรรมถูกกลับด้าน 180 องศาเป็น "RAM คือ Single Source of Truth ถาวรในการประมวลผล ส่วน Disk เป็นเพียง Backup Stream ชั่วคราว"
+-------------------------------------------------------------------------+
| CPU CACHE & MEMORY ACCESS LATENCIES |
+-------------------------------------------------------------------------+
| L1 Data Cache | 0.5 - 1.0 ns | [64B Cache Line] Shifter / ALU cycle |
| L2 Data Cache | 3.0 - 4.0 ns | Core-private L2 SRAM |
| L3 Shared Cache| 10 - 20 ns | Unified LLC (Last Level Cache) |
| Main RAM (DDR5)| 60 - 80 ns | Memory Bus -> DRAM Capacitor Read |
+----------------+---------------+----------------------------------------+
| NVMe SSD (PCIe)| 10,000-30,000ns| Flash Controller Bus + Page Read |
| Mechanical HDD | 10,000,000 ns | Physical Seek Head + Rotational Platter|
+-------------------------------------------------------------------------+
The 400x Latency Chasm: ความเร็วระหว่าง RAM (80 ns) กับ NVMe Read (30,000 ns) ห่างกันเกือบ 400 เท่า ! หากสถาปัตยกรรมของคุณต้องแตะ Storage Controller เพื่ออ่านหรือบันทึกข้อมูลก่อนตอบกลับ Client Latency ระดับ Sub-millisecond (หลักสิบไมโครวินาที) จะไม่มีทางเกิดขึ้นได้จริง
2. Redis Object Header (`robj`) & Memory Footprint Anatomy
ทุกๆ Key และ Value ใน Redis ไม่ได้ถูกเก็บเป็น Raw Bytes ธรรมดา แต่ถูกครอบด้วย C Struct ที่ชื่อว่า redisObject (robj)
typedef struct redisObject {
unsigned type:4; /* 4 bits: OBJ_STRING, OBJ_LIST, OBJ_SET, OBJ_ZSET, OBJ_HASH */
unsigned encoding:4; /* 4 bits: OBJ_ENCODING_RAW, EMBSTR, INT, LISTPACK, SKIPLIST */
unsigned lru:24; /* 24 bits: LRU timestamp (seconds) หรือ LFU counter (freq) */
int refcount; /* 4 bytes (32 bits): Reference counting สำหรับแชร์ Memory */
void *ptr; /* 8 bytes (64 bits): Pointer ชี้ไปยังเนื้อหาข้อมูลจริงใน Heap */
} robj; /* รวมขนาด Header คงที่ = 16 Bytes (บน 64-bit Architecture) */
เจาะลึก 16-byte Header Fields
type (4 bits): บอกชนิดข้อมูลระดับ Logical (String, List, Hash, Set, ZSet)encoding (4 bits): บอกโครงสร้างจัดเก็บจริงใน RAM (เช่น เป็น embstr หรือ raw หรือ listpack) สถาปัตยกรรมนี้ทำให้ Redis สามารถเปลี่ยนรูปแบบการเก็บใน RAM ได้โดยที่ Client ไม่ต้องเปลี่ยนคำสั่งlru (24 bits): พื้นที่จัดเก็บตัวเลขอายุกาลสำหรับ Eviction Policy หากเปิดโหมด LRU จะเก็บ Timestamp วินาทีล่าสุด แต่ถ้าเปิดโหมด LFU บิตชุดนี้จะถูกแบ่งเป็น 16 bits (Last Decr Time) + 8 bits (Logarithmic Access Counter) refcount (4 bytes): จัดการวงจรชีวิตของ Object และแชร์ Shared Integers (0–9999) ใน RAM เพื่อประหยัดพื้นที่ptr (8 bytes): Pointer 64-bit ชี้ไปยังตำแหน่ง Physical RAM Address ที่ข้อมูลจริงตั้งอยู่
3. Simple Dynamic String (SDS) & Memory Locality Physics
Redis ไม่ใช้ Standard C-String (char* ที่ปิดท้ายด้วย ) เพราะ C-String มีข้อจำกัดสองข้อใหญ่:
การหาความยาวสตริงผ่าน strlen() มี Time Complexity เป็น $O(N)$ บล็อก CPU นาน
ไม่เป็น Binary-Safe หากเนื้อหาข้างในเป็นไฟล์รูปภาพหรือ Protobuf ที่มีไบต์ คั่นกลาง C-String จะตัดสตริงจบทันที
Redis จึงสร้างโครงสร้าง SDS (Simple Dynamic String) ขึ้นมา:
+--------------------+--------------------+--------------------+--------------------+
| len (uint32_t) | alloc (uint32_t) | flags (uint8_t) | buf[] (char array) |
| ความยาวข้อมูลจริง | RAM ทั้งหมดที่จอง | บอกชนิด SDS Header | ข้อมูลจริง + ' ' |
+--------------------+--------------------+--------------------+--------------------+
ความแตกต่างระดับฮาร์ดแวร์: `embstr` vs `raw` Encoding
EMBSTR ENCODING (สตริงขนาด <= 44 ไบต์) -> เรียก Allocator ครั้งเดียว (One Malloc Chunk)
+-------------------------------+-----------------------------------+
| redisObject Header (16B) | SDS Header + Buffer (<= 48B) | Total = 64 Bytes!
+-------------------------------+-----------------------------------+
^
|--- จัดสรรใน Cache Line เดียวกัน (CPU ดึงเข้า L1 Cache พร้อมกันใน 1 Cycle!)
RAW ENCODING (สตริงขนาด > 44 ไบต์) -> เรียก Allocator สองครั้ง (Two Malloc Chunks)
+-------------------------------+ +---------------------------------------------+
| redisObject Header (16B) |------>| SDS Header + Buffer (Allocated Elsewhere) |
+-------------------------------+ (ptr) +---------------------------------------------+
ทำไมต้อง 44 ไบต์? (CPU Cache Line Physics): 64 Bytes พอดี! เมื่อ Redis ต้องการให้ `embstr` บรรจุอยู่ภายใน 1 Cache Line:
44 Bytes สูงสุดพอดี!
4. Compact Memory Encodings: The War on Pointer Overhead
ในภาษาอย่าง Java/Kotlin การสร้าง Object มี Memory Overhead ของ Object Header (12-16B) + References (4-8B ต่อ pointer) ใน C บน 64-bit Pointer ทุกตัวกิน RAM ถึง 8 Bytes หากสร้าง Linked List 1,000,000 โหนด เราจะเสีย RAM ไปกับ Pointer ถึง 16 MB โดยที่ยังไม่ได้เก็บข้อมูลจริงเลยสักตัว!
1. Intset (Integer Set)
หาก Set เก็บเฉพาะตัวเลขจำนวนเต็ม Redis จะใช้ intset ซึ่งเป็น Array ก้อนเดียวต่อเนื่องใน RAM:
ไม่มี Pointer ข้ามไปข้ามมา
ปรับขนาดอัตโนมัติตามค่าสูงสุด: INTSET_ENC_INT16 (2B) $
ightarrow$ INTSET_ENC_INT32 (4B) $
ightarrow$ INTSET_ENC_INT64 (8B)
ประหยัด RAM ลงได้กว่า 80% เมื่อเทียบกับการใช้ Hash Table ปกติ
2. Listpack (Compact Sequential Bytes - แทนที่ Ziplist เดิม)
ใช้ใน Hash, List, และ Sorted Set ขนาดเล็ก บีบข้อมูล Entry ทุกตัวอัดเรียงกันเป็นไบต์ต่อเนื่องใน RAM Memory Chunk เดียว:
+------------------+------------------+---------+---------+-----+-----------+
| Total Bytes (4B) | Num Elements (2B)| Entry 1 | Entry 2 | ... | End (0xFF)|
+------------------+------------------+---------+---------+-----+-----------+
|
v
+---------------------------------------+
| Encoding (1B) | Content | Backlen (1B)|
+---------------------------------------+
ทำไม Listpack ถึงเร็วกว่าในระดับ CPU? เพราะข้อมูลเรียงติดกันใน Physical RAM เมื่อ CPU ดึง Entry 1 เข้า L1/L2 Cache Line ข้อมูลของ Entry 2 และ 3 จะถูก Hardware Prefetcher ดึงติดเข้ามาใน CPU Cache ล่วงหน้าทันที ไร้ปัญหา Cache Misses
3. Skip List (`zskiplist`) ใน Sorted Set
เมื่อ Sorted Set มีขนาดเกิน zset-max-listpack-entries (128 ชิ้น) หรือค่าเกิน 64 ไบต์ ระบบจะยกระดับเป็น Skip List ผสาน Hash Table :
Level 4: [Head] -------------------------------------------------> [85] -> NULL
Level 3: [Head] ------------------------> [35] -------------------> [85] -> NULL
Level 2: [Head] -----------> [15] ------> [35] ------> [60] ------> [85] -> NULL
Level 1: [Head] -> [5] ----> [15] -> [25]-> [35] ->[50]-> [60] -> [70]-> [85] -> NULL
(Doubly linked at Level 1 for bidirectional reverse scans)
Time Complexity: ค้นหา, แทรก, ลบ ได้ใน $O(\log N)$ทำไมไม่ใช้ Red-Black Tree? Skip List ทำ Range Scan ได้ราบรื่นมากเพียงแค่เดินตาม Linked List ใน Level 1 และการจัดลำดับชั้นอาศัยการสุ่ม (Probabilistic Height) ไม่ต้องหมุน Tree (No Tree Rotation) ทำให้โค้ดกระชับและ Lock-free Friendly
5. The Memory Allocator: jemalloc Architecture & Memory Fragmentation
Redis ไม่ได้ร้องขอ RAM จาก Linux Kernel โดยตรงทุกครั้งที่มีคำสั่ง SET (เพราะ System Call brk() หรือ mmap() ช้ามาก) แต่ทำงานผ่าน Memory Allocator (โดยค่าเริ่มต้นคือ jemalloc)
+-------------------------------------------------------------------------+
| JEMALLOC ALLOCATION SLABS |
+-------------------------------------------------------------------------+
| Small Bins (Fixed Sizes): |
| [8B] [16B] [32B] [48B] [64B] [80B] [96B] [112B] [128B] ... [2048B] |
+-------------------------------------------------------------------------+
| หาก Redis ขอจอง Memory ขนาด 33 Bytes: |
| jemalloc จะปัดขึ้นและจัดสรรให้ใน Bin ขนาด 48 Bytes ทันที |
| -> เกิด Internal Fragmentation ขนาด 15 Bytes! |
+-------------------------------------------------------------------------+
สูตรคำนวณ Memory Fragmentation Ratio
mem_fragmentation_ratio = used_memory_rss / used_memory
used_memory: ขนาด RAM ที่ Redis นำไปเก็บข้อมูลและ Structs จริงๆused_memory_rss (Resident Set Size): ปริมาณ Physical RAM ที่ OS Kernel จัดสรรให้ Process ของ Redis จริง (รวม Slab ช่องว่างที่ยังไม่ได้คืน OS)
ค่า Fragmentation Ratio
ความหมายทางเทคนิค
ผลกระทบ & การแก้ไข
1.0 - 1.2 สภาวะปกติ ยอดเยี่ยม (Healthy)
Allocator จัดการหน้า Page ได้กระชับ
> 1.5 High Fragmentation (RAM รั่วจากช่องว่าง)
มีการลบข้อมูลบ่อยแต่ Allocator คืน OS ไม่ทัน สั่งแก้ด้วย activedefrag yes
< 1.0 (เช่น 0.8) วิกฤตขั้นสูงสุด (Severe Swapping) RAM กายภาพหมด OS เริ่มดันข้อมูลลง Disk Swap Space ทำให้ Latency ร่วงเป็น 10-50ms ทันที
6. Eviction Policies & Expiration Algorithms Deep Dive
1. กลไกการหมดอายุของแคช (Expiration Mechanics): Passive vs Active
Redis ไม่ได้สร้าง Background Timer หรือ Thread มาเฝ้าดู Key ทีละตัว (เพราะเปลืองทรัพยากรเกินไป) แต่ใช้วิธีผสมผสาน 2 กลยุทธ์:
Passive Elimination (Lazy Expire): เมื่อ Client ส่งคำสั่งมาอ่าน Key (เช่น GET key) Redis จะเช็ค Expire Dictionary ก่อน หากพบว่าเวลาปัจจุบันเลย TTL แล้ว Redis จะลบทิ้งทันทีและคืนค่า nilActive Elimination (Probabilistic Active Cycle): รันใน serverCron 10 ครั้งต่อวินาที:
25% (5 Keys จาก 20) Redis จะวน Loop ทำซ้ำทันทีจนกว่าจำนวนคีย์หมดอายุจะต่ำกว่า 25% เพื่อระบาย RAM เชิงรุก
2. Approximated LRU vs True LRU
True LRU ต้องใช้ Doubly Linked List ร้อยทุกๆ Object เข้าด้วยกัน ซึ่งจะกิน Memory เพิ่ม 16 ไบต์ต่อ Object และมี Lock/Pointer Contention มหาศาล Redis จึงใช้ Approximated LRU :
ใช้วิธีสุ่มตัวอย่าง (Sampling) หยิบ Keys ขึ้นมา $N$ ตัว (ค่าคอนฟิก maxmemory-samples 5)
ดูฟิลด์ lru (24 bits) ใน robj หาตัวที่มีค่า Idle Time นานที่สุด แล้วเตะตัวนั้นทิ้ง
ผลการทดสอบทางคณิตศาสตร์: ที่ maxmemory-samples 10 ผลลัพธ์ของ Approximated LRU มีความแม่นยำเทียบเท่ากับ True LRU ถึง 99% แต่ประหยัด RAM ลงได้มหาศาล
3. LFU (Least Frequently Used) Logarithmic Counter Math
ฟิลด์ 24-bit LRU จะถูกนำมาแปลงเป็น:
+--------------------------------------+--------------------------------------+
| 16 Bits: Last Decrement Time (LDT) | 8 Bits: Logistic Access Counter (LOG_C)
| บันทึกเวลา Stamp นาทีล่าสุด | ตัวนับความถี่แบบ Logarithmic (0-255) |
+--------------------------------------+--------------------------------------+
ตัวนับ 8 บิตเก็บค่าได้สูงสุดเพียง 255 แต่สามารถรองรับการถูกเรียกใช้ได้นับล้านครั้งผ่าน Morris Counter / Logarithmic Probability โดยทุกครั้งที่ถูกเรียก ค่าจะไม่ได้บวก 1 ตรงๆ แต่ขึ้นอยู่กับความน่าจะเป็นตามค่า lfu-log-factor
7. Redis RAM Internals Assessment Bank (20 Deep Architectural Questions)
ชุดข้อสอบประเมินสถาปัตยกรรมระดับลึก 20 ข้อ เพื่อทดสอบความเข้าใจเรื่อง Memory Allocator, Object Header, Cache Line Physics, Skip List และ Eviction Algorithms พร้อมผลวิเคราะห์ทันที
Assessment Live Score:
0 / 20
Reset All Answers