Phase 3: Cellular Memory Allocators & C Internals¶
Audience: Principal Systems Software Engineer & Low-Level C Hacker
Source References:src/zmalloc.c,src/sds.c,src/dict.c,src/listpack.c,src/quicklist.c,src/defrag.c
1. Jemalloc Memory Mechanics: Arenas, Bins & Dirty Pages¶
Redis defaults to jemalloc on Linux because standard glibc ptmalloc suffers catastrophic fragmentation when handling billions of microscopic allocations.
Jemalloc Size Classification:
┌─────────────────┬──────────────────────────────────────────────────────────────┐
│ Category │ Size Classes (Bins) │
├─────────────────┼──────────────────────────────────────────────────────────────┤
│ Quantum-spaced │ 8, 16, 32, 48, 64, 80, 96, 112, 128, 160, 192, 224, 256 B │
│ Page-spaced │ 512, 1024, 2048, 4096 B │
│ Large │ Multiple of 4 KB pages (up to 4 MB) │
│ Huge │ >= 4 MB (allocated directly via mmap) │
└─────────────────┴──────────────────────────────────────────────────────────────┘
1.1 Why Standard Glibc Fails in Redis¶
Glibc malloc() manages memory via a process heap (brk) and memory-mapped chunks (mmap). When millions of small keys are deleted, glibc cannot release memory back to the Linux OS unless the allocations at the top of the brk boundary are freed. If a single 10-byte allocation remains at the top, gigabytes of holes beneath it remain trapped in the process Resident Set Size (RSS), causing memory starvation.
1.2 Jemalloc Arena Isolation & Decay¶
Jemalloc creates multiple independent arenas. It monitors dirty pages (pages containing freed memory chunks). Through dirty_decay_ms (configurable via je_mallctl), jemalloc issues madvise(MADV_DONTNEED) or madvise(MADV_FREE) kernel syscalls to notify the Linux kernel that the physical frames may be released back to the page pool, keeping RSS tightly aligned with actual allocated memory.
2. Memory Fragmentation & The Active Defragmenter¶
2.1 The Metric: mem_fragmentation_ratio¶
In INFO MEMORY:
$\(\text{mem\_fragmentation\_ratio} = \frac{\text{used\_memory\_rss}}{\text{used\_memory}}\)$
- Ratio 1.0 to 1.5: Normal, healthy operating range.
- Ratio > 1.5: Severe fragmentation. More than 50% of RAM consumed by the process consists of empty allocator holes. Risk of kernel Out-Of-Memory (OOM) kill!
- Ratio < 1.0: The system has begun swapping memory to disk, indicating imminent catastrophic latency collapse.
2.2 Active Defragmentation Algorithm (activeDefragCycle())¶
Redis 4.0+ features an online defragmenter that runs incrementally inside serverCron and beforeSleep:
activeDefragCycle() Execution Flow:
1. Sample random keys from server.db[j]->dict.
2. For each key and value pointer:
a. Call jemalloc introspection: je_mallctl("arenas.lookup", ...)
b. Ask allocator: "Is this pointer located in a page with high fragmentation?"
c. If YES:
- Allocate a brand new pointer in a dense page: new_ptr = zmalloc(size)
- memcpy(new_ptr, old_ptr, size)
- Update parent dictionary or listpack pointer to new_ptr
- Free old pointer: zfree(old_ptr)
d. Check CPU budget: If active defrag consumed > active-defrag-cycle-max CPU %,
yield back to the event loop.
Production Configuration:¶
activedefrag yes
active-defrag-ignore-bytes 100mb # Do not defrag unless wasting > 100MB RAM
active-defrag-threshold-lower 10 # Start defragging when ratio > 1.10
active-defrag-threshold-upper 30 # Maximum defrag aggression when ratio > 1.30
active-defrag-cycle-min 5 # Min 5% CPU allocated to defrag
active-defrag-cycle-max 50 # Max 50% CPU allocated during emergency
3. Simple Dynamic Strings (SDS) Cellular Anatomy¶
Standard C strings (char*) are null-terminated (\0), exposing three fatal flaws:
1. \(O(N)\) length calculation (strlen).
2. Cannot store binary data with embedded \0 bytes.
3. Vulnerable to buffer overflows on modifications.
3.1 The Packed Header Hierarchy (src/sds.h)¶
Redis defines five distinct SDS header types optimized for different string magnitudes:
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 bits type, 5 bits string length (max 31 bytes) */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 1 byte: 0 to 255 */
uint8_t alloc; /* 1 byte: allocated capacity */
unsigned char flags; /* 3 bits type (SDS_TYPE_8), 5 bits unused */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* 2 bytes: 0 to 65,535 */
uint16_t alloc; /* 2 bytes */
unsigned char flags;
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* 4 bytes: 0 to 4,294,967,295 */
uint32_t alloc;
unsigned char flags;
char buf[];
};
3.2 Pointer Arithmetic & Header Access¶
When Redis allocates an SDS string, it returns a pointer directly to the beginning of the character buffer: char *s = sh->buf.
Because headers are declared __attribute__ ((__packed__)), there is zero alignment padding. To access the flag byte, Redis executes:
3.3 SDS Pre-Allocation & Lazy Reclamation¶
When modifying an SDS string (e.g., APPEND key "value"):
- If new length \(< 1 \text{ MB}\): Redis allocates \(2 \times \text{new\_len}\) bytes of space.
- If new length \(\ge 1 \text{ MB}\): Redis allocates \(\text{new\_len} + 1 \text{ MB}\) of space.
This geometric pre-allocation amortizes \(N\) append operations down to \(O(1)\) allocations, eliminating constant realloc() calls.
4. The Dictionary Engine (dict.c) & Progressive Rehashing¶
The Redis global key space, hashes, and sets rely on dict.c—a custom open-addressing / chaining hybrid hash table.
4.1 Struct Layout¶
typedef struct dict {
dictType *type; /* Method table: hashFunction, keyDup, valDup, keyCompare */
dictEntry **ht_table[2]; /* Two hash tables: ht[0] (active), ht[1] (rehashing) */
unsigned long ht_used[2];/* Count of elements in each table */
long rehashidx; /* Current bucket index undergoing rehashing (-1 if inactive) */
int16_t pauserehash; /* >0 if rehashing paused by active iterators */
} dict;
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next; /* Linked list chaining for hash collisions */
} dictEntry;
4.2 Progressive Rehashing Mechanics¶
Reallocating a hash table with 10,000,000 keys in a single operation would require copying millions of buckets, blocking the main thread for hundreds of milliseconds.
Instead, Redis executes Progressive Rehashing:
1. When load factor (\(\frac{\text{used}}{\text{size}}\)) exceeds 1.0 (or 5.0 during background save), dictExpand() allocates ht_table[1] with next power-of-two size.
2. rehashidx is set from -1 to 0.
3. During every single read, write, or lookup (dictRehashStep()):
- Redis moves elements from ht_table[0][rehashidx] to ht_table[1].
- rehashidx++.
4. During serverCron() background cron (dictRehashMilliseconds(1)):
- Spends up to 1 millisecond migrating buckets.
5. While rehashidx != -1:
- New keys are inserted exclusively into ht_table[1].
- Lookups search ht_table[0] first; if not found, search ht_table[1].
6. Once ht_used[0] == 0:
- Free ht_table[0].
- Set ht_table[0] = ht_table[1].
- Set rehashidx = -1.
Progressive Rehashing in Action:
dict:
ht_table[0] (Old Table: size=4) ht_table[1] (New Table: size=8)
┌───┬────────────────────────┐ ┌───┬────────────────────────┐
0 │ │ Rehashed (NULL) │ 0 │ │ [Entry A] ──► NULL │
├───┼────────────────────────┤ ├───┼────────────────────────┤
1 │ │ [Entry B] ──► NULL │ ──Move─► 1 │ │ Empty │
├───┼────────────────────────┤ ├───┼────────────────────────┤
2 │ │ [Entry C] ──► NULL │ 2 │ │ [Entry B] ──► NULL │
├───┼────────────────────────┤ └───┴────────────────────────┘
3 │ │ Empty │
└───┴────────────────────────┘
rehashidx: 1 (Next read/write will migrate bucket 1)
5. Compact Encodings: Listpacks & Quicklists¶
5.1 Byte-Level Layout of a Listpack (src/listpack.c)¶
A Listpack encodes multiple strings or integers into a single contiguous byte array:
Listpack Contiguous Memory Buffer:
┌─────────────────┬─────────────────┬───────────┬───────────┬───────────┬──────────┐
│ <tot-bytes: 4B> │ <num-elts: 2B> │ Entry 1 │ Entry 2 │ Entry N │ End Byte │
│ uint32_t LE │ uint16_t LE │ Variable │ Variable │ Variable │ 0xFF │
└─────────────────┴─────────────────┴───────────┴───────────┴───────────┴──────────┘
Anatomical Layout of an Individual Entry:¶
┌─────────────────────────────────┬────────────────────────────────────────────┐
│ Encoding + Data Payload │ Backlen (Backwards-encoded Length) │
│ (Variable bytes) │ (1 to 5 bytes, highest bit indicates more) │
└─────────────────────────────────┴────────────────────────────────────────────┘
Why backlen Eliminates Cascading Updates:¶
To traverse backwards from the end of the listpack, Redis inspects the preceding byte. If the high bit (0x80) is set, it reads the next byte backwards to decode the entry length.
Because the length stored is the length of this entry itself (and NOT the preceding entry), mutating Entry 1 never alters the byte length field of Entry 2!
5.2 Quicklists (Two-Level Hybrid Lists)¶
A Redis LIST is a doubly linked list of Listpacks:
typedef struct quicklist {
quicklistNode *head;
quicklistNode *tail;
unsigned long count; /* Total elements across all listpacks */
unsigned long len; /* Number of quicklistNodes */
unsigned int compress:16; /* Node compression depth (0 = off) */
} quicklist;
typedef struct quicklistNode {
struct quicklistNode *prev;
struct quicklistNode *next;
unsigned char *entry; /* Points to contiguous Listpack */
size_t sz; /* Byte size of listpack */
unsigned int count:16; /* Count of items in listpack */
unsigned int encoding:2; /* RAW (1) or LZF Compressed (2) */
} quicklistNode;
Architectural Benefit: Combining pointers with Listpacks provides \(O(1)\) push/pop at head/tail while keeping RAM fragmentation near zero and compressing interior nodes using LZ4.