Understanding Redis Internal Data Structures: SDS, List, Set, Zset, and Hash Implementations

Table of Contents

SDS design overview

List implementation principles

Set implementation principles

Zset implementation principles

Hash implementation principles

Conclusion

SDS Design Overview

Redis is written in C but does not use the native C string type; instead it employs Simple Dynamic String (SDS) to manage strings. SDS consists of three fields: free (available space), len (length of the stored string, not counting the terminating '\0'), and buf (the character array that holds the actual data).

Advantages of SDS

String length can be obtained in O(1) via the len attribute.

Prevents buffer overflow by checking free before extending the string and reallocating the buffer when necessary.

Pre‑allocation and lazy free: extra space is allocated in advance, and freed space is not immediately returned to the system, reducing frequent allocations.

Binary‑safety: because data is stored in a char array, SDS can hold any binary data without conversion.

List Implementation Principles

Before Redis 3.2, List was implemented with ZipList or LinkedList; since 3.2, QuickList is used.

ZipList Implementation

ZipList is a contiguous memory block without explicit forward/backward pointers. Its components include:

zlbytes : total byte length of the list.

zllen : number of elements.

zltail : address of the tail node for traversal.

zlend : end marker.

entry : each element node, which contains: prevlen : length of the previous entry, used to locate the next entry. encoding : encoding format of the element. content : actual element data.

ZipList Pros and Cons

Pros: contiguous memory saves pointer overhead.

Cons: insertions or deletions in the middle may trigger costly memory moves.

LinkedList Implementation

LinkedList is a classic doubly‑linked list composed of non‑contiguous memory blocks. Its fields are:

head : pointer to the first node.

tail : pointer to the last node.

len : number of elements.

dup , free , match : function pointers for element duplication, deallocation, and comparison.

QuickList Implementation

QuickList, introduced in Redis 3.2, combines the advantages of ZipList and LinkedList. Each listNode holds a pointer to a ZipList that stores the actual elements. When a ZipList exceeds the default 8 KB size, a new listNode with a fresh ZipList is created and linked.

Set Implementation Principles

Set uses two possible representations: an integer set (IntSet) or a hash table. The integer set is chosen when all elements are integers and the set size does not exceed 512 entries (configurable).

Zset (Sorted Set) Implementation Principles

Zset also has two representations: ZipList and SkipList. ZipList is used when the number of elements is less than 128 and each element’s length is under 64 bytes; otherwise SkipList is employed.

ZipList‑Based Zset

Similar to List’s ZipList, but each entry stores a value and its associated score as a key‑value pair.

SkipList‑Based Zset

The SkipList representation consists of a dictionary for fast lookup and a skip‑list for ordered traversal; both structures share the same underlying data objects.

Hash Implementation Principles

Hash can be stored as either a ZipList or a hash table. ZipList is used when both the key and value lengths are under 64 bytes and the total number of entries is below 512. Otherwise the hash table representation is used, where each field stores a field (key) and a value .

Conclusion

The article covered the underlying implementation details of five fundamental Redis collection types, helping developers choose the appropriate data structure and related commands based on their specific use cases. The next article will discuss Redis expiration policies, AOF, and RDB files.