Redis uses SDS as its core string representation and implements multiple underlying structures for Hash, ZSet, and List, including ZipList/ListPack, SkipList, and QuickList, to balance memory efficiency with read/write performance. This article focuses on three core challenges: string storage, compact encoding, and skip list lookup. Keywords: Redis, SDS, SkipList.
Technical specifications at a glance
| Parameter | Description |
|---|---|
| Core topic | Redis string and collection internals |
| Language | C |
| Protocol / stack | RESP application-layer protocol, in-memory data structure implementation |
| Applicable versions | Redis 3.2+, Redis 7.0+ |
| GitHub stars | Not provided in the source input; this article does not fabricate values |
| Core dependencies | sds.h, ziplist/listpack, skiplist, quicklist |
Redis strings are not ordinary C strings
Redis keys and many value elements are fundamentally built on string semantics. Hash field/value pairs, List elements, Set members, and ZSet members all rely on strings as a unified data carrier.
However, Redis does not fully reuse native C strings. Instead, it introduces SDS (Simple Dynamic String). The reason is straightforward: high-frequency reads and writes, binary storage, and dynamic resizing all expose performance and safety limitations in traditional \0-terminated strings.
The SDS structure stores length and free space explicitly
SDS is a dynamic string structure defined in src/sds.h. It includes at least the used length len, the remaining free space free, and the actual data buffer buf[], so retrieving the string length no longer requires traversal.
AI Visual Insight: The image shows the SDS structure definition in the Redis source code. Its key fields include a length field that records the number of used bytes, a free field that tracks remaining capacity, and a character buffer that stores the actual content contiguously. This design shows that Redis manages string metadata and payload together, enabling O(1) length access while laying the groundwork for resizing and lazy space reclamation.
typedef struct {
int len; // Used length; gets string length in O(1)
int free; // Unused space; reduces repeated reallocations
char buf[]; // Actual data buffer; still keeps \0 at the end for C API compatibility
} sdshdr;This structure definition shows that SDS replaces the implicit conventions of C strings with explicit metadata.
AI Visual Insight: The image shows the memory layout of a string such as china in SDS: bytes are stored contiguously in the data buffer, a trailing \0 is still preserved, and the structure fields separately record length and remaining space. This layout reflects Redis’s tradeoff between binary safety and compatibility with traditional C interfaces.
SDS solves three core problems in high-frequency Redis string operations
Length retrieval is no longer a performance bottleneck
Getting the length of a C string requires scanning from the beginning until \0. When a value is large and accessed frequently, length reads degrade to O(n). SDS reads len directly, keeping the complexity at O(1).
SDS is binary-safe by design
Binary data may contain \0 internally. A C string would treat that byte as the terminator, but SDS only trusts len, so it can safely store images, compressed archives, and serialized objects in full.
size_t sdsLen(sds s) {
return s->len; // Return the stored length directly without scanning the content
}This snippet illustrates the constant-time nature of SDS length access.
Preallocation and lazy release reduce reallocation overhead
When SDS expands, it allocates not only the required space but also extra reserved capacity. In general, when len < 1MB, the extra space is roughly equal to the current length; when len >= 1MB, the extra capacity is typically capped at about 1MB.
When a string shrinks, Redis does not immediately return the extra memory. Instead, it records that capacity in free. This lazy release strategy significantly reduces memory churn during repeated append and trim operations.
Hashes and ZSets switch between compact storage and efficient lookup
Redis does not use only one internal structure for Hashes and ZSets. Instead, it automatically chooses an underlying representation that is either more memory-efficient or faster for lookups, depending on the number of elements and the size of each element.
Before Redis 7, compact encodings mainly relied on ZipList. Starting with Redis 7, ListPack gradually replaces ZipList to reduce implementation complexity and the cost of cascading updates.
ZipList is a compact encoding structure on contiguous memory
A ZipList consists of three parts: head, entries, and end, all stored in one contiguous memory block. The header records the total byte size, the offset of the tail node, and the number of entries, while a fixed marker terminates the structure.
In addition to data and encoding type, each entry stores the previous node length prevlength, which enables backward traversal. However, this also creates the risk of cascading updates during insertions in the middle.
head = zlbytes + zltail + zllen
entry = prevlength + encoding + data
end = 0xFFThis sketch shows the three-part organization of ZipList.
ListPack is a more robust replacement after Redis 7
ListPack also uses contiguous memory, but it removes ZipList’s zltail and prevlength. Instead, it stores element-total-len at the end of each entry.
This change matters: it still supports backward traversal, but it avoids large-scale metadata rewrites when inserting or modifying entries in the middle, making it better suited for modern Redis write-heavy workloads.
SkipList gives ZSet near-balanced-tree lookup efficiency
When a ZSet grows larger or when element sizes exceed the threshold for compact structures, Redis switches to SkipList. A SkipList is essentially a multi-level ordered linked list that achieves fast lookup, insertion, and range access through randomized level heights.
It is not a strictly balanced tree, but with much lower implementation complexity, it can still deliver average query performance close to O(log n). That makes it well suited for score-ordered sorted set workloads.
AI Visual Insight: The image shows the linear structure of a regular ordered linked list. Each node maintains only a single-level successor pointer, so finding or inserting a target element requires sequential comparisons, and the time complexity can easily degrade to O(n). This is exactly the starting point that skip lists optimize.
AI Visual Insight: The image shows a linked list with higher-level indexes added to some nodes. The lookup first follows a high-level fast path and then descends to lower levels for precise positioning, clearly reducing the number of comparisons and illustrating the core idea behind skip list layered indexing.
AI Visual Insight: The image further shows the shape of a multi-level indexed linked list. As the number of levels increases, the search path becomes shorter, showing how skip lists use a probabilistic layered structure to approach balanced-tree lookup efficiency while preserving linked-list simplicity.
def skiplist_search(levels, target):
node = levels.top_head # Start from the head node at the highest level
while node:
while node.next and node.next.score < target:
node = node.next # Jump horizontally within the current level first
node = node.down # Once the boundary is found, descend to the next level
return nodeThis pseudocode demonstrates the typical skip list search path: move horizontally first, then descend.
QuickList gives List both linked-list flexibility and compact storage
Starting with Redis 3.2, QuickList became the primary implementation for List. It is neither a plain linked list nor a single ZipList. Instead, it is a hybrid structure in which each linked-list node contains a compact list internally.
The design goal is clear: avoid the pointer overhead of traditional linked lists while also avoiding the update cost of a single oversized ZipList in very long list workloads.
AI Visual Insight: The image shows the segmented layout of QuickList: the outer layer is a doubly linked list, and each inner node stores a compact data block. This structure shows how Redis balances sequential access, head/tail insertion, and memory usage through block-based compression plus bidirectional linking.
When retrieving an index, Redis walks QuickList nodes and cumulatively counts the number of elements in each compact block. After locating the target block, it performs an in-block lookup. For insertion, Redis decides whether to write directly into the target block or split the node based on the available space.
AI Visual Insight: The image shows the split or reorganization process during QuickList insertion. When a single compact block approaches its capacity threshold, Redis redistributes data across adjacent blocks, preventing any one node from growing too large and keeping update costs under control.
Understanding these internals helps explain Redis performance boundaries
From SDS to ListPack, then to SkipList and QuickList, Redis follows a consistent design principle: dynamically trade off memory efficiency, write cost, and query speed.
For developers, the key is not to memorize structure names mechanically, but to understand the selection logic: small and short data prefers compact encoding, while large and complex data moves to faster indexed structures. This is one of the core reasons Redis maintains high throughput across general-purpose workloads.
FAQ
1. Why doesn’t Redis use C strings directly?
Because retrieving the length of a C string requires traversal, and C strings cannot safely store binary data containing \0. SDS records length explicitly with len and supports dynamic expansion, making it a better fit for a high-frequency in-memory database.
2. What is the core difference between ZipList and ListPack?
ZipList relies on prevlength to support backward traversal, but inserting a node in the middle can trigger cascading updates. ListPack instead records the total length of the current element, which still supports backward traversal while reducing structural update costs.
3. When is ZSet more likely to use SkipList?
When the number of elements exceeds the configured threshold, or when member strings become too long to continue using compact encoding, Redis switches to SkipList to provide more stable lookup, insertion, and range query performance.
Core summary: This article systematically reviews the underlying structures used for Redis strings and collections. It focuses on how SDS solves C string limitations around length retrieval, binary safety, and frequent resizing, and explains the implementation differences and selection logic among ZipList, ListPack, SkipList, and QuickList for Hash, ZSet, and List.