How Redis Internally Implements Memory Efficient Lists: Ziplist and Quicklist

Redis, an in-memory data store, is renowned for its speed and efficiency. A significant part of this performance stems from its highly optimized internal data structures. One such structure is the List, which Redis implements using a combination of Ziplist and Quicklist to achieve remarkable memory and CPU cache efficiency.

Redis Lists and Their Internal Encoding

When you interact with Redis lists, for example, by using the LPUSH command, Redis internally manages the storage. To inspect the underlying data structure, you can use the DEBUG OBJECT <key> command. For a newly created list, you’ll often observe that Redis employs an encoding called Quicklist.

127.0.0.1:6379> LPUSH klist s
(integer) 1
127.0.0.1:6379> DEBUG OBJECT klist
Value at:0x7f8b9c000000 refcount:1 encoding:quicklist lru:154562 lru_seconds_idle:1 type:list ...

This output indicates that Redis uses Quicklist to store list elements. The implementation details for Quicklist can be found in the quicklist.c source file within the Redis codebase.

Why Not a Standard Doubly Linked List?

A traditional doubly linked list is a common choice for implementing lists due to its flexibility in insertions and deletions. However, for an in-memory database like Redis, a naive implementation of a doubly linked list introduces significant overheads:

1. Memory Overhead

Each node in a standard doubly linked list typically requires:

• A pointer to the previous node (prev).
• A pointer to the next node (next).
• A pointer to the actual value.

On a 64-bit system, each pointer consumes 8 bytes. Thus, a single node incurs 24 bytes (3 pointers * 8 bytes/pointer) of overhead. Furthermore, Redis stores every value as a redisObject, which itself adds approximately 16 bytes of metadata (e.g., reference count, type, encoding). This means that for each element in a list, there’s a minimum overhead of 40 bytes (24 bytes for pointers + 16 bytes for redisObject metadata), even before storing the actual data. For small values, this overhead is disproportionately large. For instance, storing a 5-character string (roughly 10 bytes) would require 40 bytes of metadata plus the string’s storage, making it highly inefficient.

2. CPU Cache Inefficiency

When a standard doubly linked list is populated, its nodes are typically allocated randomly across the heap. This scattered memory allocation leads to poor CPU cache utilization. As the CPU traverses the list, it frequently jumps between non-contiguous memory locations. Each jump can result in a CPU cache miss, forcing the CPU to fetch data from slower main memory (RAM). This process, involving memory page faults and bringing 4KB memory pages into the cache, significantly degrades performance, especially during sequential access patterns.

Ziplist: A Memory-Efficient Contiguous Block

To address the inefficiencies of traditional linked lists, Redis introduced Ziplist. A Ziplist is a highly optimized, contiguous block of memory designed to store a small number of elements efficiently. It’s essentially an array-like structure that