1. 什么是List？
List是Redis的数据类型之一，给用户提供一个双向链表的功能。核心优势是头尾操作O(1)。
2. List的编码模式
List的编码模式有两种：LISTPACK和QUICKLIST。（下文用全大写表示编码名称，首字母大写表示数据结构）
Quicklist本身就是节点为Listpack的链表，所以实际上LISTPACK编码可以看成只有一个节点的QUICKLIST编码，没有本质区别。
单独设计一个LISTPACK编码的目的是，在元素较少的时候可以节省Quicklist结构体的内存空间。
3. List的编码策略
- 默认编码是
LISTPACK，当元素大小或数量超过Listpack阈值时切换到QUICKLIST。 - 当元素删除后，减少到
Listpack上限阈值的一半时，切换到LISTPACK。减少到一半再切换的目的是：避免刚好在Listpack上限阈值边界频繁增删的时候反复触发切换编码。
缩容代码如下：
static void listTypeTryConvertQuicklist(robj *o, int shrinking, beforeConvertCB fn, void *data) {serverAssert(o->encoding == OBJ_ENCODING_QUICKLIST); // 必须是QUICKLIST编码才允许转换size_t sz_limit;unsigned int count_limit;quicklist *ql = o->ptr; // QUICKLIST 编码下, ptr指向quicklist/***************************************************************1. 只有单节点的 Quicklist 才允许转换到 Listpack 2. 如果 Quicklist 里面的元素是超过大小阈值的元素, 只能用Quicklist ****************************************************************/if (ql->len != 1 || ql->head->container != QUICKLIST_NODE_CONTAINER_PACKED)return;/* 读取配置文件设置的大小阈值和数量阈值并减半，小于一半才转换 */quicklistNodeLimit(server.list_max_listpack_size, &sz_limit, &count_limit);if (shrinking) {sz_limit /= 2;count_limit /= 2;}if (ql->head->sz > sz_limit || ql->count > count_limit) return;if (fn) fn(data); // 如果参数有回调则调用回调/* 从 quicklist 唯一的一个节点中取出 listpack 然后删除 quicklist */o->ptr = ql->head->entry;ql->head->entry = NULL;quicklistRelease(ql);o->encoding = OBJ_ENCODING_LISTPACK;
}
扩容代码如下：
static void listTypeTryConvertListpack(robj *o, robj **argv, int start, int end,beforeConvertCB fn, void *data)
{serverAssert(o->encoding == OBJ_ENCODING_LISTPACK); // 必须是LISTPACK编码才允许转换size_t add_bytes = 0;size_t add_length = 0;/* 如果是PUSH命令，遍历计算需要新增的元素大小和个数 */if (argv) {for (int i = start; i <= end; i++) {if (!sdsEncodedObject(argv[i]))continue;add_bytes += sdslen(argv[i]->ptr);}add_length = end - start + 1;}// 判断新的元素大小和个数是否会超过配置文件设置的阈值if (quicklistNodeExceedsLimit(server.list_max_listpack_size,lpBytes(o->ptr) + add_bytes, lpLength(o->ptr) + add_length)){if (fn) fn(data); // 如果参数有回调则调用回调/* 创建一个空quicklist，并设置配置文件的 listpack上限阈值 和 quicklist压缩深度 */quicklist *ql = quicklistNew(server.list_max_listpack_size, server.list_compress_depth);if (lpLength(o->ptr))quicklistAppendListpack(ql, o->ptr); // listpack 有元素则直接添加指针作为节点elselpFree(o->ptr); // listpack 没有有元素则直接释放o->ptr = ql;o->encoding = OBJ_ENCODING_QUICKLIST;}
}
4. 添加元素
根据不同的编码类型头尾插入节点代码如下：
void listTypePush(robj *subject, robj *value, int where) {if (subject->encoding == OBJ_ENCODING_QUICKLIST) {int pos = (where == LIST_HEAD) ? QUICKLIST_HEAD : QUICKLIST_TAIL;if (value->encoding == OBJ_ENCODING_INT) {char buf[32];ll2string(buf, 32, (long)value->ptr);quicklistPush(subject->ptr, buf, strlen(buf), pos);} else {quicklistPush(subject->ptr, value->ptr, sdslen(value->ptr), pos);}} else if (subject->encoding == OBJ_ENCODING_LISTPACK) {if (value->encoding == OBJ_ENCODING_INT) {subject->ptr = (where == LIST_HEAD) ?lpPrependInteger(subject->ptr, (long)value->ptr) :lpAppendInteger(subject->ptr, (long)value->ptr);} else {subject->ptr = (where == LIST_HEAD) ?lpPrepend(subject->ptr, value->ptr, sdslen(value->ptr)) :lpAppend(subject->ptr, value->ptr, sdslen(value->ptr));}} else {serverPanic("Unknown list encoding");}
}
Listpack内部本身就有检测数据是否是整数的功能，QUICKLIST编码时只保留了统一的插入string接口，导致了：
插入数字使用ll2string()转成string，到了底层的Listpack又转回数字，是一个浪费性能的点。