t zset编码转换
t_zset 编码转换源码分析(listpack 与 skiplist+dict)
ZSet 一个逻辑类型背后有两套物理编码:小集合用一块连续内存的 listpack,大集合用 skiplist+dict 双结构。
核心思路是按数据规模换数据结构——元素少时 O(N) 顺序扫比指针跳转还快且省内存,超过阈值(zset-max-listpack-entries / zset-max-listpack-value)就一次性转成双结构,让 ZSCORE 走 dict O(1)、ZRANK/ZRANGE 走跳表 O(logN)。
// 基于本地 Redis 仓 (unstable, commit 1abd489), src/object.c
// 两种编码在创建时就分家：listpack 版 ptr 指向一块裸字节数组，skiplist 版 ptr 指向 zset 结构体（dict + zsl 各一个）
robj *createZsetObject(void) {
zset *zs = zmalloc(sizeof(*zs));
robj *o;
zs->dict = dictCreate(&zsetDictType); // 双结构从出生起就成对出现，之后所有写路径必须同时维护两边
zs->zsl = zslCreate();
o = createObject(OBJ_ZSET,zs);
o->encoding = OBJ_ENCODING_SKIPLIST;
return o;
}
robj *createZsetListpackObject(void) {
unsigned char *lp = lpNew(0); // 就是一块连续内存，member 和 score 交替平铺，没有任何节点/指针开销
robj *o = createObject(OBJ_ZSET,lp);
o->encoding = OBJ_ENCODING_LISTPACK;
return o;
}// 基于本地 Redis 仓 (unstable, commit 1abd489), src/t_zset.c
// zadd 入口链路：zaddCommand -> zaddGenericCommand。编码分支不在命令层做，命令层只负责"选对初始编码/提前扩容"
robj *zsetTypeCreate(size_t size_hint, size_t val_len_hint) {
if (size_hint <= server.zset_max_listpack_entries &&
val_len_hint <= server.zset_max_listpack_value) // 两个阈值：条数 + 单个 member 长度，任一超标都不给 listpack
{
return createZsetListpackObject();
}
robj *zobj = createZsetObject(); // 一次 ZADD 塞 200 个元素的新 key，直接建 skiplist，省掉"先建小的再转"
zset *zs = zobj->ptr;
dictExpand(zs->dict, size_hint); // 按提示预扩容 dict，避免插入过程中反复 rehash
return zobj;
}
/* Check if the existing zset should be converted to another encoding based off the
* the size hint. */
void zsetTypeMaybeConvert(robj *zobj, size_t size_hint) {
if (zobj->encoding == OBJ_ENCODING_LISTPACK &&
size_hint > server.zset_max_listpack_entries) // 老 key 也一样：这批元素肯定会撑爆 listpack，就先转再插
{
zsetConvertAndExpand(zobj, OBJ_ENCODING_SKIPLIST, size_hint);
}
}
void zaddGenericCommand(client *c, int flags) {
// ... 解析 NX/XX/GT/LT/INCR/CH 选项，先把所有 score 参数解析完（有语法错就整条不执行）
/* Lookup the key and create the sorted set if does not exist. */
zobj = lookupKeyWrite(c->db,key);
if (checkType(c,zobj,OBJ_ZSET)) goto cleanup;
if (zobj == NULL) {
if (xx) goto reply_to_client; /* No key + XX option: nothing to do. */
robj *o = zsetTypeCreate(elements, sdslen(c->argv[scoreidx + 1]->ptr)); // 新 key：用元素个数当 size_hint 选编码
zobj = dbAdd(c->db,key,&o);
} else {
// ...
zsetTypeMaybeConvert(zobj, elements); // 老 key：批量插入前预判要不要升级编码
// ...
}
// ...
for (j = 0; j < elements; j++) {
double newscore;
score = scores[j];
int retflags = 0;
ele = c->argv[scoreidx+1+j*2]->ptr;
int retval = zsetAdd(zobj, score, ele, flags, &retflags, &newscore); // 真正的编码分支在 zsetAdd 里
if (retval == 0) {
addReplyError(c,nanerr);
// ...
goto cleanup;
}
if (retflags & ZADD_OUT_ADDED) added++;
if (retflags & ZADD_OUT_UPDATED) updated++;
if (!(retflags & ZADD_OUT_NOP)) processed++;
score = newscore;
}
// ... server.dirty 累加、回复客户端、keyspace 通知
}// 基于本地 Redis 仓 (unstable, commit 1abd489), src/t_zset.c
// zsetAdd：单个元素的增/改，两种编码各一个分支；listpack 分支里藏着转换触发点
int zsetAdd(robj *zobj, double score, sds ele, int in_flags, int *out_flags, double *newscore) {
// ... in_flags 拆成 incr/nx/xx/gt/lt 布尔量；score 是 NaN 直接报错返回 0
/* Update the sorted set according to its encoding. */
if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *eptr;
if ((eptr = zzlFind(zobj->ptr,ele,&curscore)) != NULL) { // O(N) 线性找 member，listpack 没有索引
/* NX? Return, same element already exists. */
if (nx) {
*out_flags |= ZADD_OUT_NOP;
return 1;
}
// ... incr 则 score += curscore；GT/LT 不满足则 NOP
if (newscore) *newscore = score;
/* Remove and re-insert when score changed. */
if (score != curscore) {
zobj->ptr = zzlDelete(zobj->ptr,eptr); // listpack 改分数只能删了重插：位置由 score 决定，原地改不了
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
*out_flags |= ZADD_OUT_UPDATED;
}
return 1;
} else if (!xx) {
/* check if the element is too large or the list
* becomes too long *before* executing zzlInsert. */
if (zzlLength(zobj->ptr)+1 > server.zset_max_listpack_entries || // 条数超限（默认 128）
sdslen(ele) > server.zset_max_listpack_value || // 单元素超长（默认 64 字节）
!lpSafeToAdd(zobj->ptr, sdslen(ele))) // listpack 总大小的安全上限兜底
{
zsetConvertAndExpand(zobj, OBJ_ENCODING_SKIPLIST, zsetLength(zobj) + 1);
// 注意：转换后不 return，直接落到下面的 skiplist 分支完成插入，不用递归
} else {
zobj->ptr = zzlInsert(zobj->ptr,ele,score);
if (newscore) *newscore = score;
*out_flags |= ZADD_OUT_ADDED;
return 1;
}
} else {
*out_flags |= ZADD_OUT_NOP;
return 1;
}
}
/* Note that the above block handling listpack would have either returned or
* converted the key to skiplist. */
if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zobj->ptr;
zskiplistNode *znode;
dictEntry *de;
dictEntryLink bucket, link;
/* Use dictFindLink to find the element and get the bucket for potential insertion.
* This avoids a second lookup in dictAdd() if the element doesn't exist. */
link = dictFindLink(zs->dict, ele, &bucket); // 查找和"没找到时该插哪个桶"一次搞定，省一次 hash 定位
if (link != NULL) {
/* Element exists - get the dictEntry from the link */
de = *link;
// ... NX 则 NOP；incr 累加；GT/LT 不满足则 NOP
/* Get the node pointer from dict entry */
znode = dictGetKey(de); // dict 的 key 直接是跳表节点指针，member 字符串内嵌在节点里
curscore = znode->score;
// ...
/* Remove and re-insert when score changes. */
if (score != curscore) {
zslUpdateScore(zs->zsl, znode, score); // 跳表内部调位置；新位置没变时还能原地改
/* Note that we did not remove the original element from
* the hash table representing the sorted set, so we don't
* need to update the dict - the node pointer stays the same. */
*out_flags |= ZADD_OUT_UPDATED; // dict 完全不用动：它存的是节点指针，分数变了指针没变
}
return 1;
} else if (!xx) {
/* Element doesn't exist - create node with embedded sds and add to skiplist */
znode = zslInsert(zs->zsl, score, ele); // 先插跳表（member 被拷贝进节点）
/* Add node pointer to dict using the bucket we already found */
dictSetKeyAtLink(zs->dict, znode, &bucket, 1); // 再把节点指针挂进 dict，两边共享同一份 member 内存
*out_flags |= ZADD_OUT_ADDED;
if (newscore) *newscore = score;
return 1;
} else {
*out_flags |= ZADD_OUT_NOP;
return 1;
}
} else {
serverPanic("Unknown sorted set encoding");
}
return 0; /* Never reached. */
}
/* Insert (element,score) pair in listpack. This function assumes the element is
* not yet present in the list. */
unsigned char *zzlInsert(unsigned char *zl, sds ele, double score) {
unsigned char *eptr = lpSeek(zl,0), *sptr;
double s;
while (eptr != NULL) { // 从头顺序扫：listpack 里 (member, score) 成对存放，按 score 升序
sptr = lpNext(zl,eptr);
serverAssert(sptr != NULL);
s = zzlGetScore(sptr);
if (s > score) {
/* First element with score larger than score for element to be
* inserted. This means we should take its spot in the list to
* maintain ordering. */
zl = zzlInsertAt(zl,eptr,ele,score);
break;
} else if (s == score) {
/* Ensure lexicographical ordering for elements. */
if (zzlCompareElements(eptr,(unsigned char*)ele,sdslen(ele)) > 0) { // 同分按 member 字典序，和跳表规则一致
zl = zzlInsertAt(zl,eptr,ele,score);
break;
}
}
/* Move to next element. */
eptr = lpNext(zl,sptr);
}
/* Push on tail of list when it was not yet inserted. */
if (eptr == NULL)
zl = zzlInsertAt(zl,NULL,ele,score);
return zl;
}
static unsigned char *zzlInsertAt(unsigned char *zl, unsigned char *eptr, sds ele, double score) {
char scorebuf[MAX_D2STRING_CHARS];
int scorelen = 0;
long long lscore;
int score_is_long = double2ll(score, &lscore); // 整数分值直接按整数编码存，比 double 转字符串省不少字节
if (!score_is_long)
scorelen = d2string(scorebuf,sizeof(scorebuf),score);
listpackEntry entries[2];
entries[0].sval = (unsigned char*)ele;
entries[0].slen = sdslen(ele);
if (score_is_long) {
entries[1].sval = NULL;
entries[1].lval = lscore;
} else {
entries[1].sval = (unsigned char*)scorebuf;
entries[1].slen = scorelen;
}
if (eptr == NULL)
zl = lpBatchAppend(zl, entries, 2);
else
zl = lpBatchInsert(zl, eptr, LP_BEFORE, entries, 2, NULL); // member+score 一次批量插，只触发一次 realloc/memmove
return zl;
}
/* Converts a zset to the specified encoding, pre-sizing it for 'cap' elements. */
void zsetConvertAndExpand(robj *zobj, int encoding, unsigned long cap) {
zset *zs;
zskiplistNode *node, *next;
sds ele;
double score;
if (zobj->encoding == encoding) return;
if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
unsigned char *zl = zobj->ptr;
// ...
zs = zmalloc(sizeof(*zs));
zs->dict = dictCreate(&zsetDictType);
zs->zsl = zslCreate();
/* Presize the dict to avoid rehashing */
dictExpand(zs->dict, cap); // 元素个数已知，一次扩到位，转换过程中零 rehash
eptr = lpSeek(zl,0);
// ...
while (eptr != NULL) { // 顺序扫 listpack，逐对搬进双结构
score = zzlGetScore(sptr);
vstr = lpGetValue(eptr,&vlen,&vlong);
if (vstr == NULL)
ele = sdsfromlonglong(vlong);
else
ele = sdsnewlen((char*)vstr,vlen);
node = zslInsert(zs->zsl,score,ele);
serverAssert(dictAdd(zs->dict, node, NULL) == DICT_OK); // dict 里存节点指针，value 为空
sdsfree(ele); /* zslInsert copied it, we can free our copy */
zzlNext(zl,&eptr,&sptr);
}
zfree(zobj->ptr); // 老 listpack 整块释放
zobj->ptr = zs;
zobj->encoding = OBJ_ENCODING_SKIPLIST;
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
// ... 反方向（skiplist -> listpack）：沿跳表底层链表顺序 append，zadd 路径不会走到
} else {
serverPanic("Unknown sorted set encoding");
}
}
/* dictType for zset's dict (maps sds to zskiplistNode*) */
dictType zsetDictType = {
dictSdsHash, /* hash function */
NULL, /* key dup */
NULL, /* val dup */
dictSdsKeyCompare, /* compares embedded sds by keyFromStoredKey */
NULL, /* key destructor - skiplist owns the node memory */ // dict 不负责释放：member 内存归跳表节点所有
NULL, /* val destructor */
NULL, /* allow to expand */
.no_value = 1, /* no values stored (only nodes) */ // 无 value 的 dict，一个 entry 只存一个节点指针
.keyFromStoredKey = zslGetNodeElementForDict, /* extract embedded sds from node */ // 查找时从节点里抠出内嵌 sds 来比较
};
int zsetScore(robj *zobj, sds member, double *score) {
if (!zobj || !member) return C_ERR;
if (zobj->encoding == OBJ_ENCODING_LISTPACK) {
if (zzlFind(zobj->ptr, member, score) == NULL) return C_ERR; // 小集合：O(N) 扫，N<=128 时无所谓
} else if (zobj->encoding == OBJ_ENCODING_SKIPLIST) {
zset *zs = zobj->ptr;
dictEntry *de = dictFind(zs->dict, member); // ZSCORE 走 dict：O(1) 拿到跳表节点
if (de == NULL) return C_ERR;
zskiplistNode *znode = dictGetKey(de);
*score = znode->score; // 分数就在节点上，dict 只是索引
} else {
serverPanic("Unknown sorted set encoding");
}
return C_OK;
}原理串讲
一次 ZADD key 10 member 的完整链路:zaddCommand -> zaddGenericCommand 先把所有选项和 score 解析完(任何语法错误都在改数据之前拦下,保证命令要么全执行要么不执行),然后 lookupKeyWrite 查 key。
key 不存在时走 zsetTypeCreate,用”这次要插几个元素、第一个 member 多长”当 hint 直接选编码——如果一条命令就要塞 500 个元素,何必先建 listpack 再转一次?key 已存在时 zsetTypeMaybeConvert 做同样的预判,把”插到第 129 个才在 zsetAdd 里触发转换”提前成”插入前一次转好”,顺便把 dict 按最终容量 dictExpand 到位。
这是第一处”为什么这么设计”:转换和 rehash 都是 O(N) 的重操作,能预知就绝不在插入循环里被动触发。
进入 zsetAdd 后按 encoding 分支。listpack 分支里 zzlFind 线性扫描找 member:找到了就处理 NX/XX/GT/LT/INCR,分数变了只能 zzlDelete + zzlInsert 删了重插,因为 listpack 是按 score 排序的连续字节流,没有”原地改分数”这种操作。
没找到且不是 XX,就到了转换触发点:三个条件(条数 +1 超过 zset-max-listpack-entries、member 长度超过 zset-max-listpack-value、lpSafeToAdd 总大小兜底)在 zzlInsert 执行之前检查。
为什么要在插入前而不是插入后检查?插进去再转,等于先付一次 listpack 的 memmove 再全量搬一次家,白做一遍;先转的话这个新元素直接以 skiplist 的方式插入。
转换本身在 zsetConvertAndExpand:新建 dict+zsl,dict 按 cap 一次扩容到位,顺序扫 listpack 把每对 (member, score) zslInsert 进跳表、节点指针 dictAdd 进 dict,最后整块释放老 listpack。
转换完 zsetAdd 不返回也不递归,代码直接落进下面的 skiplist 分支完成本次插入——两个 if 顺序排列而不用 else if,就是为了让”转换后接着插”自然发生。
skiplist 分支的双结构一致性是这版源码最值得看的地方。dict 的 key 直接存 zskiplistNode 指针(no_value dict),member 字符串内嵌在跳表节点尾部,dict 查找时通过 keyFromStoredKey 回调从节点里取出 sds 参与哈希比较。
这是第二处”为什么这么设计”:老版本 dict 存 member->score 两份独立数据,member 的 sds 被 dict 和跳表各引用一次、score 存两份,改分数要同时更新两处;现在整个 ZSet 里 member 和 score 都只有一份(在跳表节点上),dict 纯粹是”member 到节点”的索引。
所以 zsetAdd 更新分数时只调 zslUpdateScore 让跳表调整节点位置,dict 一个字节都不用动——节点指针没变。
读路径各取所长:zsetScore 走 dictFind 拿节点直接读 score,O(1);ZRANK/ZRANGE 这类跟顺序、排名相关的操作走跳表,靠每层的 span 累加 O(logN) 算出排名。
删除时(zsetRemoveFromSkiplist)顺序必须是先删 dict 再删跳表,因为 member 内存归跳表节点所有,反过来就是 use-after-free。
代码块收起展开
为什么小 ZSet 非要用 listpack?算一笔账:一个跳表节点要 score(8B) + backward 指针(8B) + 若干层 forward+span(每层 16B),外加 dict entry、哈希桶,一个元素几十字节纯开销;listpack 里一个元素就是"编码头 + 数据"平铺,整数 score 甚至只占几个字节。
更重要的是缓存局部性:128 个元素的 listpack 就几 KB,一两次缓存预取就扫完了;跳表的 O(logN) 每一跳都是一次随机内存访问,小数据量下"理论复杂度更优"输给"常数更小"。阈值卡 128 条 / 64 字节,就是卡在线性扫描还没输给指针跳转的经验区间内。
设计取舍
- 编码分支放在 zsetAdd 数据层而不是命令层,ZINCRBY/GEOADD 等所有写路径自动共享转换逻辑,命令层只做 size_hint 预判优化。
- zadd 路径的转换是单向的:只升不降。ZREM 删到只剩 3 个元素也不会退回 listpack,因为反复增删会导致来回转换抖动;降级只发生在 GEO/ZUNIONSTORE 等生成新结果集的路径(zsetConvertToListpackIfNeeded)。
- 两个阈值缺一不可:entries 限制扫描长度,value 限制单元素大小——一个 10KB 的 member 会让每次 memmove 都很贵,条数再少也不该进 listpack。
- 双结构不是”两份数据”,是”一份数据 + 一个索引”:member/score 只存在跳表节点上,dict 存节点指针。常见误区是说 dict 里存 member->score 映射,这版源码已经不是了。
- listpack 和跳表用同一套排序规则(score 升序,同分按 member 字典序),转换只是顺序搬运,无需重排。