redis zset源码

1. 结构体定义

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

2. debug日志


void print_zsl(zskiplist *zsl) {
    struct zskiplistNode *x;

    printf("print_zsl length:%lu level:%d\n", zsl->length, zsl->level);
    
    printf("----[from header]---\n");
    for (int i=zsl->level-1; i>=0; i--) {
        x = zsl->header;
        printf("level:%d [header] -> ", i);
        for (;x->level[i].forward; x=x->level[i].forward) {
            //printf("print_zsl level:%d, ele:%s, score:%lf, span:%lu\n", 
            //     i, x->level[i].forward->ele, x->level[i].forward->score, 
            //    x->level[i].span);
            printf("[%s:%lf] -> ", x->level[i].forward->ele, x->level[i].forward->score);
        }
        printf("\n");
    }
    printf("-------\n");

    x = zsl->tail;
    printf("----[from tail]---\n");
    for (;x;x=x->backward)  {
        printf("[%s:%lf] -> ", x->ele, x->score);
    }
    printf("\n-------\n");
}

3. 跳表结构 核心代码

zskiplist *zslCreate(void);
void zslFree(zskiplist *zsl);
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele);
zskiplistNode *zslFirstInRange(zskiplist *zsl, zrangespec *range);
zskiplistNode *zslLastInRange(zskiplist *zsl, zrangespec *range);

4. 压缩链表转换为跳表

int zsetAdd(robj *zobj, double score, sds ele, int *flags, double *newscore) 

  zobj->ptr = zzlInsert(zobj->ptr,ele,score);
            if (zzlLength(zobj->ptr) > server.zset_max_ziplist_entries)
                zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);
            if (sdslen(ele) > server.zset_max_ziplist_value)
                zsetConvert(zobj,OBJ_ENCODING_SKIPLIST);

举例说明

修改配置文件,将zset压缩链表 最小val长度改为1,
这样member名称长度>1,zset将用跳表结构
zset-max-ziplist-value 1

假设zset key=z1, 有8个元素
score值分别是
1,2,3,4,5,6,7,8
其中
1在1层
2在2层
3在1层
4在3层
5在1层
6在2层
7在1层
8在4层

那么跳表结构如下

debug日志输出如下:

print_zsl length:8 level:4
----[from header]---
level:3 [header] -> [m8:8.000000] -> 
level:2 [header] -> [m4:4.000000] -> [m8:8.000000] -> 
level:1 [header] -> [m2:2.000000] -> [m4:4.000000] -> [m6:6.000000] -> [m8:8.000000] -> 
level:0 [header] -> [m1:1.000000] -> [m2:2.000000] -> [m3:3.000000] -> [m4:4.000000] -> [m5:5.000000] -> [m6:6.000000] -> [m7:7.000000] -> [m8:8.000000] -> 
-------
----[from tail]---
[m8:8.000000] -> [m7:7.000000] -> [m6:6.000000] -> [m5:5.000000] -> [m4:4.000000] -> [m3:3.000000] -> [m2:2.000000] -> [m1:1.000000] -> 

评论

暂无评论