A list sounds simple—until Redis has to optimize it
After looking at how Redis implements Sorted Set, one pattern becomes hard to ignore: Redis rarely settles for a single underlying structure. It switches strategies depending on data size, and sometimes combines multiple structures to squeeze out better memory usage and performance.
List follows the same philosophy.
At the surface, a list is just a long sequence of data. Most programming languages offer some version of it, whether backed by an array or a linked list. The behavior looks similar, but the performance characteristics are completely different. In Java, for example, ArrayList and LinkedList make that trade-off obvious.
Redis also has to make that choice—but it goes further than choosing one over the other.
Earlier Redis versions
In older Redis versions, List used a strategy similar to Sorted Set: the internal representation changed with the amount of data.
When the list was small, Redis stored it as a ziplist, a compact structure that can be thought of as array-like storage. Once the data grew beyond certain limits, it switched to linkedlist, meaning a doubly linked list.
The key idea behind ziplist was that it used length information to locate neighboring entries, avoiding the explicit prev/next pointers required by a typical doubly linked list.
In newer Redis versions, though, List is implemented with quicklist, so that is where the interesting design really begins.
quicklist: not a plain linked list
The outer structure
The first thing to inspect is the structure definition:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | /* quicklist is a 40 byte struct (on 64-bit systems) describing a quicklist. * 'count' is the number of total entries. * 'len' is the number of quicklist nodes. * 'compress' is: 0 if compression disabled, otherwise it's the number * of quicklistNodes to leave uncompressed at ends of quicklist. * 'fill' is the user-requested (or default) fill factor. * 'bookmarks are an optional feature that is used by realloc this struct, * so that they don't consume memory when not used. */ typedef struct quicklist { quicklistNode *head; quicklistNode *tail; unsigned long count; /* total count of all entries in all listpacks */ unsigned long len; /* number of quicklistNodes */ signed int fill : QL_FILL_BITS; /* fill factor for individual nodes */ unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */ unsigned int bookmark_count: QL_BM_BITS; quicklistBookmark bookmarks[]; } quicklist;
The important parts are easy to spot:
- head
- tail
- length
So yes, at first glance this already looks very much like a linked list. Which means the real question is not the quicklist itself, but what each quicklistNode actually contains.
The node structure
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /* quicklistNode is a 32 byte struct describing a listpack for a quicklist. * We use bit fields keep the quicklistNode at 32 bytes. * count: 16 bits, max 65536 (max lp bytes is 65k, so max count actually < 32k). * encoding: 2 bits, RAW=1, LZF=2. * container: 2 bits, PLAIN=1 (a single item as char array), PACKED=2 (listpack with multiple items). * recompress: 1 bit, bool, true if node is temporary decompressed for usage. * attempted_compress: 1 bit, boolean, used for verifying during testing. * extra: 10 bits, free for future use; pads out the remainder of 32 bits */ typedef struct quicklistNode { struct quicklistNode *prev; struct quicklistNode *next; unsigned char *entry; size_t sz; /* entry size in bytes */ unsigned int count : 16; /* count of items in listpack */ unsigned int encoding : 2; /* RAW==1 or LZF==2 */ unsigned int container : 2; /* PLAIN==1 or PACKED==2 */ unsigned int recompress : 1; /* was this node previous compressed? */ unsigned int attempted_compress : 1; /* node can't compress; too small */ unsigned int dont_compress : 1; /* prevent compression of entry that will be used later */ unsigned int extra : 9; /* more bits to steal for future usage */ } quicklistNode;
Seeing prev and next, it is tempting to conclude that this is just a doubly linked list again. But if that were all Redis needed, there would have been little reason to redesign the implementation.
The real clue appears in the operations.
What happens when Redis pushes to the tail
Take quicklistPushTail as an example:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | /* Add new entry to tail node of quicklist. * * Returns 0 if used existing tail. * Returns 1 if new tail created. */ int quicklistPushTail(quicklist *quicklist, void *value, size_t sz) { quicklistNode *orig_tail = quicklist->tail; if (unlikely(isLargeElement(sz))) { __quicklistInsertPlainNode(quicklist, quicklist->tail, value, sz, 1); return 1; } if (likely( _quicklistNodeAllowInsert(quicklist->tail, quicklist->fill, sz))) { quicklist->tail->entry = lpAppend(quicklist->tail->entry, value, sz); quicklistNodeUpdateSz(quicklist->tail); } else { quicklistNode *node = quicklistCreateNode(); node->entry = lpAppend(lpNew(0), value, sz); quicklistNodeUpdateSz(node); _quicklistInsertNodeAfter(quicklist, quicklist->tail, node); } quicklist->count++; quicklist->tail->count++; return (orig_tail != quicklist->tail); }
The logic splits into two branches:
- one branch appends the element directly into the current tail node’s
entry - the other branch creates a brand new node, appends the element there, and links that node into the quicklist
That alone tells us quicklist is not an ordinary doubly linked list where each node stores exactly one element. Instead, each linked-list node is a container. Only when certain limits are reached does Redis allocate another node.
This is the central idea of quicklist: instead of having a very long linked list made of tiny individual nodes, Redis groups multiple elements together into a compact block, then links those blocks together.
It is a fairly aggressive design, but a very practical one.
That leaves two natural questions:
- When does Redis decide to create a new node?
- How are multiple elements stored inside one node?
When does a quicklist create a new node?
The answer is tied to size limits, which you can see in _quicklistNodeAllowInsert:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | REDIS_STATIC int _quicklistNodeAllowInsert(const quicklistNode *node, const int fill, const size_t sz) { if (unlikely(!node)) return 0; if (unlikely(QL_NODE_IS_PLAIN(node) || isLargeElement(sz))) return 0; /* Estimate how many bytes will be added to the listpack by this one entry. * We prefer an overestimation, which would at worse lead to a few bytes * below the lowest limit of 4k (see optimization_level). * Note: No need to check for overflow below since both `node->sz` and * `sz` are to be less than 1GB after the plain/large element check above. */ size_t new_sz = node->sz + sz + SIZE_ESTIMATE_OVERHEAD; if (unlikely(quicklistNodeExceedsLimit(fill, new_sz, node->count + 1))) return 0; return 1; }
The comments here are unusually direct.
If the element is too large—such as something on the order of 1 GB—Redis does not try to pack it together with other elements. It gives that value its own node.
And then there is the other limit hidden in the comment: the lowest limit of 4k.
So a quicklist node is allowed to keep absorbing new entries only while it stays within the configured thresholds. Once it exceeds those constraints, Redis creates another node.
There is one more important detail in this function: listpack.
That is the format used inside the node.
What is actually inside a quicklist node?
In older explanations of Redis internals, quicklist is often described as “a linked list of ziplists.” That was true for earlier implementations. But newer Redis code increasingly replaces ziplist with listpack, and looking at the newer design is more revealing.
So to understand modern quicklist, you need to understand why ziplist was no longer enough.
Why ziplist became a problem
The biggest issue with ziplist is cascading updates.
A ziplist uses stored length information to locate the next and previous entries. That keeps the structure compact, but it also creates a weakness: if an entry changes and its encoded length changes, the positions of later entries may have to move as well.
In other words, when one item’s size changes, a whole sequence of subsequent entries may need to be shifted.
Direct in-place updates are not the most common list operation, so this is not always painful. But when that scenario does happen, the cost can become awkward very quickly.
A normal doubly linked list does not suffer from this in the same way, because each node is independent and connected through pointers. Changing one node’s payload does not force the neighboring nodes to relocate.
To avoid ziplist’s chain-update problem, Redis needed a better encoding strategy.
listpack: compact storage with a different encoding idea
The design of listpack can be summarized by its element representation.
1 2 3 4 5 6 7 8 | /* Each entry in the listpack is either a string or an integer. */ typedef struct { /* When string is used, it is provided with the length (slen). */ unsigned char *sval; uint32_t slen; /* When integer is used, 'sval' is NULL, and lval holds the value. */ long long lval; } listpackEntry;
A single element is laid out like this:
1 2 3 4 | <encoding-type><element-data><element-tot-len> | | +--------------------------------------------+ (This is an element)
That means each entry contains three parts:
encoding-typeelement-dataelement-tot-len, where the length islen(encoding-type + element-data)
At first this may look almost too simple. But the key is the encoding.
The encoding-type tells Redis what kind of data follows and how many bits are used to store it. For example, a pattern like 11110001 can indicate a 16-bit integer, which means the actual value is stored in the next 2 bytes.
This is where listpack improves on ziplist.
Ziplist relies on length changes to navigate, which means modifying data can affect the placement of following elements. Listpack, by contrast, emphasizes encoding. For values of the same type—say, a 16-bit integer—the storage width is fixed, so changing the value does not inherently change its occupied size.
When scanning backward, listpack still uses element-tot-len to locate the previous entry, so reverse traversal remains possible without reintroducing the same cascading update issue.
What this design really achieves
Before digging into Redis List internals, it is easy to assume that a list is trivial: just use an array and be done with it.
But Redis operates under two forms of pressure at once:
- it needs high performance
- it needs to conserve memory under large-scale workloads
Under those constraints, even a basic data structure becomes something worth redesigning.
Quicklist shows two especially valuable ideas.
First, Redis combines structures instead of treating them as mutually exclusive. A doubly linked list gives flexible insertion and navigation at the block level, while listpack compresses multiple elements inside each block.
Second, encoding matters. Better encoding is not just about saving bytes; it also changes update behavior and affects how safely and efficiently the structure can evolve.
Most applications will never need this level of optimization. But the design itself is worth studying, because it shows how far a “simple list” can be pushed when memory and performance are both taken seriously.