Skip list of redis source code analysis

xindoo 2021-01-21 23:55:47
skip list redis source code


I'm going to change my job recently , Through the window of the alternation of old and new work, I relaxed , So the column dragged on , But I don't feel guilty , After all, no one is pushing for more . But then again, every day I pursue drama The days of variety show painting are also very boring , I envy you people who work normally , Every day there's serious work to do , I feel like you've had a good time .[ dog's head ]

There are many kinds of data structures in the computer field , Data structures exist either to save time 、 Or to save space , Or both , So part of the data structure is Time for space , Space for time . Actually There are also some data structures that save time and space at the expense of accuracy , As I said bloomfilter It's a typical example . And what I'm going to talk about today skiplist It's also a probabilistic data structure , It is organized into a multi-level structure with random probability reduction data , Easy and fast search .

Jump watch

What is jump watch ? Let's think about this scenario first , Suppose you have an ordered list , You want to see if a particular value appears in the list , Then you can only traverse the list once to know , The time complexity is O(n).

Someone might ask why not use continuous storage directly , We can also use binary search , Using a chain list is to continue to retain its advantage of low complexity in modifying time . So how can we optimize the speed of single search ? In fact, it's like searching for ideas , But the feature that a single chain table cannot access randomly limits us , But the idea of a gradual narrowing of the two points inspired us , Can I think of any way to narrow the scope gradually ?

Can I create a new list above the original list , The new list is the original list every other node to take one . Suppose the original linked list is L0, The new list is L1,L1 The element in is L0 No 1、3、5、7、9…… Nodes , And then set up L1 and L0 Pointer to each node in the . such L1 It can be L0 Cut the range in half , Same reason L1 Create a new list L2……, Higher level The linked list is divided into larger intervals , After determining the large range of values , Step by step, scale down , Here's the picture .

Suppose we're looking for 13, We can do it in L3 To determine 2-14 The scope of the , stay L2 To determine 8-14 The scope of the , stay L1 To determine 10-14 The scope of the , stay L0 Find 13, The overall search path is shown in the red path below , Isn't it more direct than L0 In looking for 13 The green path of passes through a few nodes .

In fact, this kind of implementation is very similar to binary search , Just store the middle point of the binary search in advance , For time with extra space , It's easy to think that its time complexity is consistent with binary search , All are O(logn). The young man is very good X Do you , Invented such a cow forced data structure , Can find the time complexity of ordered list from O(n) Down to O(logn), But I have a problem , What if a node is inserted or deleted in the list ?, Is it necessary to reconstruct the entire data structure every time the data changes ?

It doesn't have to be , We don't need to strictly guarantee a one-half relationship between the two levels , It only needs to be a half probability Just go , Delete a node to say , Delete the corresponding modified nodes in a certain level directly , When inserting a node , The new node can be inserted into the upper chain table with the probability of exponential decline . such as L0 in 100% Insert ,L1 China and Israel 1/2 The probability of inserting , If L1 Inserted in ,L2 In addition to 1/2 The probability of inserting …… Be careful , As long as it is high Level There are nodes in , low Level There must be , But high Level The probability of appearing in the linked list will follow level Exponential decline , In the end, the watch might look like this .

So we reinvented skiplist.

Redis Jump watch in

Redis In order to provide an ordered set (sorted set) Related operations ( such as zadd、zrange), The underlying implementation is skiplist. Let's take a look at redis How to achieve skiplist Of .

typedef struct zskiplist {
struct zskiplistNode *header, *tail; // Head to tail pointer
unsigned long length; // skiplist The length of
int level; // The highest level of linked list
} zskiplist;

So let's see redis in zskiplist The definition of , It's nothing , Just the head and tail pointer 、 Length and series , The point is still zskiplistNode in .zskiplistNode There is a forward pointer in , therefore Level[0] It's actually a two-way list .

typedef struct zskiplistNode {
sds ele; // The specific value stored by the node
double score; // The score corresponding to the node
struct zskiplistNode *backward; // Forward pointer
struct zskiplistLevel {
struct zskiplistNode *forward; // Back pointer for each layer
unsigned long span; // The span to the next node
} level[];
} zskiplistNode;

redis Medium skiplist Implementation is a little different from what we said above , It's not a simple form of a multilevel list , It's directly in the zskiplistNode Medium level[] Will be different level The relationship between the nodes is organized ,zskiplist The structure visualization of is as follows .

Skip table operation

got it zskiplist Construction , Let's take a look at some of the main operations .

New skip table

/* Create a skip table */
zskiplist *zslCreate(void) {
int j;
zskiplist *zsl;
zsl = zmalloc(sizeof(*zsl));
zsl->level = 1;
zsl->length = 0;
zsl->header = zslCreateNode(ZSKIPLIST_MAXLEVEL,0,NULL); // Create a header node
for (j = 0; j < ZSKIPLIST_MAXLEVEL; j++) {
zsl->header->level[j].forward = NULL;
zsl->header->level[j].span = 0;
}
zsl->header->backward = NULL;
zsl->tail = NULL;
return zsl;
}

It's easier to create a skip table , Create an empty node directly as the header node .

/* Insert a new node in the jump table , */
zskiplistNode *zslInsert(zskiplist *zsl, double score, sds ele) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
unsigned int rank[ZSKIPLIST_MAXLEVEL];
int i, level;
serverAssert(!isnan(score));
x = zsl->header;
for (i = zsl->level-1; i >= 0; i--) {
/* store rank that is crossed to reach the insert position */
rank[i] = i == (zsl->level-1) ? 0 : rank[i+1];
while (x->level[i].forward &&
(x->level[i].forward->score < score ||
(x->level[i].forward->score == score &&
sdscmp(x->level[i].forward->ele,ele) < 0)))
{
rank[i] += x->level[i].span;
x = x->level[i].forward;
}
update[i] = x;
}
/* skiplist There are no duplicate elements in , But we allow duplicate scores , Because if it's a call to zslInsert() Words , There will be no repeated insertions
* The same elements , Because in zslInsert() It has been judged that hash Is there... In the table */
level = zslRandomLevel(); // Generate a random value , Determine the highest level of the list that needs to be inserted
if (level > zsl->level) {
for (i = zsl->level; i < level; i++) {
rank[i] = 0;
update[i] = zsl->header;
update[i]->level[i].span = zsl->length;
}
zsl->level = level;
}
x = zslCreateNode(level,score,ele); // Create a new node for the inserted data
for (i = 0; i < level; i++) {
x->level[i].forward = update[i]->level[i].forward;
update[i]->level[i].forward = x;
/* New nodes need to be inserted before and after updating span value */
x->level[i].span = update[i]->level[i].span - (rank[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
/* For others level increase span value , Because a new node is inserted between the original two nodes */
for (i = level; i < zsl->level; i++) {
update[i]->level[i].span++;
}
x->backward = (update[0] == zsl->header) ? NULL : update[0];
if (x->level[0].forward)
x->level[0].forward->backward = x;
else
zsl->tail = x;
zsl->length++;
return x;
}
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF)) // ZSKIPLIST_P == 0.25
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

Data insertion is a little more complicated , You need to create a new node , And then determine what needs to be in level Insert a new node in the , Also update each of the previous nodes level Of span value . Here's a little extra attention zslRandomLevel,zslRandomLevel In order to 25% The probability of whether to put a single node to the next level is decided by the probability of , instead of 50%.

void zslDeleteNode(zskiplist *zsl, zskiplistNode *x, zskiplistNode **update) {
int i;
for (i = 0; i < zsl->level; i++) {
if (update[i]->level[i].forward == x) {
update[i]->level[i].span += x->level[i].span - 1; // Deleting a node needs to be modified span Value
update[i]->level[i].forward = x->level[i].forward;
} else {
update[i]->level[i].span -= 1;
}
}
if (x->level[0].forward) {
x->level[0].forward->backward = x->backward;
} else {
zsl->tail = x->backward;
}
while(zsl->level > 1 && zsl->header->level[zsl->level-1].forward == NULL)
zsl->level--;
zsl->length--;
}
/* from skiplist Delete in ele, If the deletion succeeds, return 1, Otherwise return to 0.
*
* If the node is null, Need to call zslFreeNode() Release the node , Otherwise, it's just pointing to sds The pointer of is set to null , such
* Other nodes can continue to use this sds*/
int zslDelete(zskiplist *zsl, double score, sds ele, zskiplistNode **node) {
zskiplistNode *update[ZSKIPLIST_MAXLEVEL], *x;
int i;
x = zsl->header;
for (i = zsl->level-1; i >= 0; 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) < 0)))
{
x = x->level[i].forward;
}
update[i] = x;
}
/* There may be multiple nodes with the same socre, All have to be found and deleted */
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele,ele) == 0) {
zslDeleteNode(zsl, x, update);
if (!node)
zslFreeNode(x);
else
*node = x;
return 1;
}
return 0; /* not found */
}

Data deletion is also very simple , It is very similar to the deletion of a single linked list , But at the same time we need to update each level The data on the .

The rest of the code is more , got it skiplist The concrete realization of , Other related operations of the code is relatively easy to think of , I don't list them here , You can check it if you are interested t_zset.c

Redis Why use skiplist Not the balance tree

Redis Medium skiplist Mainly for the realization of sorted set Related functions , Of course, red and black trees can also achieve their functions , Why? redis The author used skiplist Not the red and black trees 、b Balance trees like trees ? And obviously, red and black trees are more than skiplist More memory saving ! Redis The author of antirez I have personally answered this question , See the original https://news.ycombinator.com/item?id=1171423

I translate roughly :

  1. skiplist It's not particularly memory intensive , Just adjust the next node to a higher level level Probability , You can do better than B Trees consume less memory .
  2. sorted set There may be a lot of zrange and zreverange operation , Hop table as a single chain table traversal performance is no less than other balanced trees .
  3. It's easy to implement and debug . for example , Realization O(log(N)) Time complexity ZRANK Just modify the code .

This article is about Redis Source analysis series blog , At the same time, there are also corresponding Redis Chinese annotation version , I want to learn more about it Redis Classmate , welcome star And attention . Redis Chinese annotation version warehouse :https://github.com/xindoo/Redis Redis Source analysis column :https://zxs.io/s/1h If you found this article useful , welcome One key, three links .

Participation of this paper Tencent cloud media sharing plan , You are welcome to join us , share .

版权声明
本文为[xindoo]所创,转载请带上原文链接,感谢
https://javamana.com/2021/01/20210121234656713x.html

  1. 【计算机网络 12(1),尚学堂马士兵Java视频教程
  2. 【程序猿历程,史上最全的Java面试题集锦在这里
  3. 【程序猿历程(1),Javaweb视频教程百度云
  4. Notes on MySQL 45 lectures (1-7)
  5. [computer network 12 (1), Shang Xuetang Ma soldier java video tutorial
  6. The most complete collection of Java interview questions in history is here
  7. [process of program ape (1), JavaWeb video tutorial, baidu cloud
  8. Notes on MySQL 45 lectures (1-7)
  9. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  10. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  11. 精进 Spring Boot 03:Spring Boot 的配置文件和配置管理,以及用三种方式读取配置文件
  12. Refined spring boot 03: spring boot configuration files and configuration management, and reading configuration files in three ways
  13. 【递归,Java传智播客笔记
  14. [recursion, Java intelligence podcast notes
  15. [adhere to painting for 386 days] the beginning of spring of 24 solar terms
  16. K8S系列第八篇(Service、EndPoints以及高可用kubeadm部署)
  17. K8s Series Part 8 (service, endpoints and high availability kubeadm deployment)
  18. 【重识 HTML (3),350道Java面试真题分享
  19. 【重识 HTML (2),Java并发编程必会的多线程你竟然还不会
  20. 【重识 HTML (1),二本Java小菜鸟4面字节跳动被秒成渣渣
  21. [re recognize HTML (3) and share 350 real Java interview questions
  22. [re recognize HTML (2). Multithreading is a must for Java Concurrent Programming. How dare you not
  23. [re recognize HTML (1), two Java rookies' 4-sided bytes beat and become slag in seconds
  24. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  25. RPC 1: how to develop RPC framework from scratch
  26. 造轮子系列之RPC 1:如何从零开始开发RPC框架
  27. RPC 1: how to develop RPC framework from scratch
  28. 一次性捋清楚吧,对乱糟糟的,Spring事务扩展机制
  29. 一文彻底弄懂如何选择抽象类还是接口,连续四年百度Java岗必问面试题
  30. Redis常用命令
  31. 一双拖鞋引发的血案,狂神说Java系列笔记
  32. 一、mysql基础安装
  33. 一位程序员的独白:尽管我一生坎坷,Java框架面试基础
  34. Clear it all at once. For the messy, spring transaction extension mechanism
  35. A thorough understanding of how to choose abstract classes or interfaces, baidu Java post must ask interview questions for four consecutive years
  36. Redis common commands
  37. A pair of slippers triggered the murder, crazy God said java series notes
  38. 1、 MySQL basic installation
  39. Monologue of a programmer: despite my ups and downs in my life, Java framework is the foundation of interview
  40. 【大厂面试】三面三问Spring循环依赖,请一定要把这篇看完(建议收藏)
  41. 一线互联网企业中,springboot入门项目
  42. 一篇文带你入门SSM框架Spring开发,帮你快速拿Offer
  43. 【面试资料】Java全集、微服务、大数据、数据结构与算法、机器学习知识最全总结,283页pdf
  44. 【leetcode刷题】24.数组中重复的数字——Java版
  45. 【leetcode刷题】23.对称二叉树——Java版
  46. 【leetcode刷题】22.二叉树的中序遍历——Java版
  47. 【leetcode刷题】21.三数之和——Java版
  48. 【leetcode刷题】20.最长回文子串——Java版
  49. 【leetcode刷题】19.回文链表——Java版
  50. 【leetcode刷题】18.反转链表——Java版
  51. 【leetcode刷题】17.相交链表——Java&python版
  52. 【leetcode刷题】16.环形链表——Java版
  53. 【leetcode刷题】15.汉明距离——Java版
  54. 【leetcode刷题】14.找到所有数组中消失的数字——Java版
  55. 【leetcode刷题】13.比特位计数——Java版
  56. oracle控制用户权限命令
  57. 三年Java开发,继阿里,鲁班二期Java架构师
  58. Oracle必须要启动的服务
  59. 万字长文!深入剖析HashMap,Java基础笔试题大全带答案
  60. 一问Kafka就心慌?我却凭着这份,图灵学院vip课程百度云