redis 5.0.7 源码阅读——跳跃表skiplist
2024-09-07 04:23:38
redis中并没有专门给跳跃表两个文件。在5.0.7的版本中，结构体的声明与定义、接口的声明在server.h中，接口的定义在t_zset.c中，所有开头为zsl的函数。
一、数据结构
单个节点：
typedef struct zskiplistNode {
//key，唯一
sds ele;
//分值，可重复
double score;
//后退指针
struct zskiplistNode *backward;
//层
struct zskiplistLevel {
//前进指针
struct zskiplistNode *forward;
//到本层下一节点的跨度，用于计算rank
unsigned long span;
} level[];
} zskiplistNode;
zskiplistNode定义了跳跃表中每个节点的数据结构，它是一个变长结构体。
/*
+------------------------+
|sds ele | /+-----------------------------+
+------------------------+ / |struct zskiplistNode *forward|
|double score | / +-----------------------------+
+------------------------+ / |unsigned long span |
|zskiplistNode * backward| / +-----------------------------+
+------------------------+/ . .
|zskiplistLevel level[] | . .
+------------------------+\ . .
\ +-----------------------------+
\ |struct zskiplistNode *forward|
\ +-----------------------------+
\ |unsigned long span |
\+-----------------------------+
*/
将用以下结构表示：
/*
+--------+
|level[1]|
|1(span) |
+--------+
|level[0]|
|1(span) |
+--------+
|backward|
+--------+
|score |
+--------+
|ele |
+--------+
*/
如：
/*
+--------+ +--------+ +--------+
|level[1]|--------------->|level[1]|--------------->|level[1]|
|2 | |2 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|
|1 | |1 | |1 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
|backward|<--|backward|<--|backward|<--|backward|<--|backward|
+--------+ +--------+ +--------+ +--------+ +--------+
|1 | |2 | |3 | |4 | |5 |
+--------+ +--------+ +--------+ +--------+ +--------+
|a | |b | |c | |d | |e |
+--------+ +--------+ +--------+ +--------+ +--------+
*/
跳表：
typedef struct zskiplist {
//头/尾节点
struct zskiplistNode *header, *tail;
//总长度
unsigned long length;
//总层数
int level;
} zskiplist;
因其头节点固定为空节点，固整体结构：
/*
+--------+ +--------+ +--------+
|level[1]|--------------->|level[1]|--------------->|level[1]|
|2 | |2 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|
|1 | |1 | |1 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
|backward|<--|backward|<--|backward|<--|backward|<--|backward|
+--------+ +--------+ +--------+ +--------+ +--------+
|0 | |2 | |3 | |4 | |5 |
+--------+ +--------+ +--------+ +--------+ +--------+
|NULL | |b | |c | |d | |e |
+-->+--------+ +--------+ +--------+ +--------+ +--------+<--+
| |
| +--------+ |
+---|header | |
+--------+ |
|tail |-------------------------------------------------------+
+--------+
|length=4|
+--------+
|level=2 |
+--------+
*/
每个level层都是一条单身链表，其中level[0]中包含所有元素。
二、创建
根据指定的level，创建一个跳表节点：
zskiplistNode *zslCreateNode(int level, double score, sds ele) {
zskiplistNode *zn =
zmalloc(sizeof(*zn)+level*sizeof(struct zskiplistLevel));
zn->score = score;
zn->ele = ele;
return zn;
}
创建一个跳表：
#define ZSKIPLIST_MAXLEVEL 64 /* Should be enough for 2^64 elements */
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = ;
zsl->length = ;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,,NULL);
for (j = ; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = ;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}
redis中定义的最大层数为64层。且在刚创建时，会生成一个空的头节点，这样就可以不用再考虑节点数从0至1或者从1至0时要处理的各种特殊情况。
刚创完的跳表结构（结构中以4做为最大层数，后同）：
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+
|level[1]|-->NULL
|0 |
+--------+
|level[0]|-->NULL
|0 |
+--------+
NULL<-|backward|
+--------+
|0 |
+--------+
|NULL |
+-->+--------+
|
| +--------+
+---|header |
+--------+
|tail |-->NULL
+--------+
|length=0|
+--------+
|level=1 |
+--------+
*/
三、插入节点
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
int zslRandomLevel(void) {
int level = ;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += ;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
redis中使用的决定新插入节点层数据的方法是抛硬币法，且“硬币”只有25%的几率是正面。
插入方法：
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
//update数组，用于存储查找路径
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
//rank数组，用于存储每层路径节点的排名
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
x = zsl->header;
//先查找插入位置
for (i = zsl->level-; i >= ; i--) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-) ? : rank[i+];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < )))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
//随机一个level
level = zslRandomLevel();
//若当前最大level不够，则补齐update与rank数组
if (level > zsl->level) {
for (i = zsl->level; i < level; i++) {
rank[i] = ;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
//创建一个节点，并插入
x = zslCreateNode(level,score,ele);
for (i = ; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
x->level[i].span = update[i]->level[i].span - (rank[] - rank[i]);
update[i]->level[i].span = (rank[] - rank[i]) + ;
}
//update数组中，比插入节点level更高的各成员的跨度增加
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
x->backward = (update[] == zsl->header) ? NULL : update[];
if (x->level[].forward)
x->level[].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
从注释可知，redis的跳表允许同score的情况发生，但是不允许同ele，且是由调用者在外部保证。若插入顺序为e，b，c，d，则插入e时：
step1、定义update数组与rank数组。
/*
update rank
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
*/
实际在linux环境运行时，不会默认初始化，应该是一堆脏数据，此处是为了方便处理结构
step2、查找位置后
/*
update rank
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|header | |0 |
+--------+ +--------+
*/
step3、e的level为2，比跳表的大，故要补齐update与rank数组
/*
update rank
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|header | |0 |
+--------+ +--------+
|header | |0 |
+--------+ +--------+
*/
step4、插入节点，与单身链表插入相同，将新节点e各层，插入到update数组中记录的各层节点之后，并使用rank数组，计算跨度
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+ +--------+
|level[1]|-->|level[1]|-->NULL
|1 | |0 |
+--------+ +--------+
|level[0]|-->|level[0]|-->NULL
|1 | |0 |
+--------+ +--------+
NULL<-|backward| |backward|
+--------+ +--------+
|0 | |5 |
+--------+ +--------+
|NULL | |e |
+-->+--------+ +--------+
|
| +--------+
+---|header |
+--------+
|tail |
+--------+
|length=0|
+--------+
|level=1 |
+--------+
*/
step5、处理新插入节点的backward指针，与跳表的tail指针：
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+ +--------+
|level[1]|-->|level[1]|-->NULL
|1 | |0 |
+--------+ +--------+
|level[0]|-->|level[0]|-->NULL
|1 | |0 |
+--------+ +--------+
NULL<-|backward| |backward|
+--------+ +--------+
|0 | |5 |
+--------+ +--------+
|NULL | |e |
+-->+--------+ +--------+<--+
| |
| +--------+ |
+---|header | |
+--------+ |
|tail |----------------+
+--------+
|length=1|
+--------+
|level=2 |
+--------+ */
此时插入b：
找到位置后的update与rank数组：
/*
update rank
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|header | |0 |
+--------+ +--------+
|header | |0 |
+--------+ +--------+
*/
插入b节点后：
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+ +--------+
|level[1]|--------------->|level[1]|-->NULL
|2 | |0 |
+--------+ +--------+ +--------+
|level[0]|-->|level[0]|-->|level[0]|-->NULL
|1 | |1 | |0 |
+--------+ +--------+ +--------+
NULL<-|backward| |backward|<--|backward|
+--------+ +--------+ +--------+
|0 | |2 | |5 |
+--------+ +--------+ +--------+
|NULL | |b | |e |
+-->+--------+ +--------+ +--------+<--+
| |
| +--------+ |
+---|header | |
+--------+ |
|tail |-----------------------------+
+--------+
|length=2|
+--------+
|level=2 |
+--------+
*/
需要注意的是，update数组idx = 1的节点并没有新的插入操作，span要自增，表示本层跨度增加了1。
插入c时的update与rank数组：
/*
update rank
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|header | |0 |
+--------+ +--------+
|b | |1 |
+--------+ +--------+
*/
插入c后：
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+ +--------+ +--------+
|level[1]|--------------->|level[1]|-->|level[1]|-->NULL
|2 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+
|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
|1 | |1 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+
NULL<-|backward| |backward|<--|backward|<--|backward|
+--------+ +--------+ +--------+ +--------+
|0 | |2 | |3 | |5 |
+--------+ +--------+ +--------+ +--------+
|NULL | |b | |c | |e |
+-->+--------+ +--------+ +--------+ +--------+<--+
| |
| +--------+ |
+---|header | |
+--------+ |
|tail |------------------------------------------+
+--------+
|length=3|
+--------+
|level=2 |
+--------+
/*
最后插入d：
update与rank数组：
/*
update rank
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|c | |2 |
+--------+ +--------+
|c | |2 |
+--------+ +--------+
*/
插入d：
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+ +--------+ +--------+
|level[1]|--------------->|level[1]|--------------->|level[1]|-->NULL
|2 | |2 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
|1 | |1 | |1 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
NULL<-|backward| |backward|<--|backward|<--|backward|<--|backward|
+--------+ +--------+ +--------+ +--------+ +--------+
|0 | |2 | |3 | |4 | |5 |
+--------+ +--------+ +--------+ +--------+ +--------+
|NULL | |b | |c | |d | |e |
+-->+--------+ +--------+ +--------+ +--------+ +--------+<--+
| |
| +--------+ |
+---|header | |
+--------+ |
|tail |-------------------------------------------------------+
+--------+
|length=4|
+--------+
|level=2 |
+--------+
/*
如果此时要新插入节点a，score为4.5，则update与rank数组分别为：
/*
update rank
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|NULL | |0 |
+--------+ +--------+
|c | |2 |
+--------+ +--------+
|d | |3 |
+--------+ +--------+
*/
四、删除节点
在已经查找到位置，与已知update数组时的删除方法：
void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = ; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].span += x->level[i].span - ;
update[i]->level[i].forward = x->level[i].forward;
} else {
update[i]->level[i].span -= ;
}
}
if (x->level[].forward) {
x->level[].forward->backward = x->backward;
} else {
zsl->tail = x->backward;
}
while(zsl->level > && zsl->header->level[zsl->level-].forward == NULL)
zsl->level--;
zsl->length--;
}
删除本节点之后，对应路径相应得做处理。
从跳表中删除指定节点的操作：
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
//先用score与ele查找，生成update数组
x = zsl->header;
for (i = zsl->level-; i >= ; i--) {
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < )))
{
x = x->level[i].forward;
}
update[i] = x;
}
//跳表允许同score，防止误删，做一下ele校验
if (x && score == x->score && sdscmp(x->ele,ele) == ) {
zslDeleteNode(zsl, x, update);
if (!node)
zslFreeNode(x);
else
*node = x;
return ;
}
return ;
}
如以下跳表：
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+ +--------+ +--------+
|level[1]|--------------->|level[1]|--------------->|level[1]|-->NULL
|2 | |2 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
|1 | |1 | |1 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+ +--------+
NULL<-|backward| |backward|<--|backward|<--|backward|<--|backward|
+--------+ +--------+ +--------+ +--------+ +--------+
|0 | |2 | |3 | |4 | |5 |
+--------+ +--------+ +--------+ +--------+ +--------+
|NULL | |b | |c | |d | |e |
+-->+--------+ +--------+ +--------+ +--------+ +--------+<--+
| |
| +--------+ |
+---|header | |
+--------+ |
|tail |-------------------------------------------------------+
+--------+
|length=4|
+--------+
|level=2 |
+--------+
/*
要删除节点d，生成的update数组为：
/*
update
+--------+
|NULL |
+--------+
|NULL |
+--------+
|c |
+--------+
|c |
+--------+
*/
由于d的level为1，故在level[0]层，使用从单向链表中删除节点的操作，把d移出，再给高于level[0]的update数组中所有成员的span自减，节点少了，跨度要跟着降低。
删除d之后的跳表：
/*
+--------+
|level[3]|-->NULL
|0 |
+--------+
|level[2]|-->NULL
|0 |
+--------+ +--------+ +--------+
|level[1]|--------------->|level[1]|-->|level[1]|-->NULL
|2 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+
|level[0]|-->|level[0]|-->|level[0]|-->|level[0]|-->NULL
|1 | |1 | |1 | |0 |
+--------+ +--------+ +--------+ +--------+
NULL<-|backward| |backward|<--|backward|<--|backward|
+--------+ +--------+ +--------+ +--------+
|0 | |2 | |3 | |5 |
+--------+ +--------+ +--------+ +--------+
|NULL | |b | |c | |e |
+-->+--------+ +--------+ +--------+ +--------+<--+
| |
| +--------+ |
+---|header | |
+--------+ |
|tail |------------------------------------------+
+--------+
|length=3|
+--------+
|level=2 |
+--------+
/*
五、销毁
void zslFreeNode(zskiplistNode *node) {
sdsfree(node->ele);
zfree(node);
}
void zslFree(zskiplist *zsl) {
zskiplistNode *node = zsl->header->level[].forward, *next;
zfree(zsl->header);
while(node) {
next = node->level[].forward;
zslFreeNode(node);
node = next;
}
zfree(zsl);
}
销毁操作本身只是在level[0]层遍历所有节点，依次销毁。
redis 5.0.7 下载链接
http://download.redis.io/releases/redis-5.0.7.tar.gz
源码阅读顺序参考：
https://github.com/huangz1990/blog/blob/master/diary/2014/how-to-read-redis-source-code.rst
最新文章
- BoneCP 升级遇到的问题
- 龙之谷手游WebVR技术分享
- Java的几种常用设计模式
- zend studio 常用快捷键
- MySQL好用的数学函数
- html5开发之viewport使用
- JavaScript Patterns 2.9 Coding Conventions
- 解决xshell 中文乱码
- 【HDOJ】4183 Pahom on Water
- PyQt5创建第一个窗体(正规套路)
- IE8’s Substr() Bug
- c#中serialPort1_DataReceived串口接收事件处理
- java设计模式案例详解:代理模式
- spring boot 入门操作(三)
- rtx web 分级管理系统 二次开发
- Http持久连接与HttpClient连接池
- 015_python原生在线调试工具
- 盘点和反思在微信的阴影下艰难求生的移动端IM应用
- 使用 VS Code 开发和调试 .NET Core 程序
- Matlab数据处理——数据的保存和读取方法操作