Redis 跳跃表实现的独特设计思路
2022-04-024.5k 阅读
Redis 跳跃表概述
在 Redis 中，跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表在 Redis 中主要用于实现有序集合（Sorted Set）数据结构的底层存储之一（另一种是压缩列表，当有序集合元素较少且成员和分值都较短时使用压缩列表）。
跳跃表相比平衡树等其他有序数据结构，实现相对简单，而且在平均情况下具有和平衡树相近的时间复杂度，插入、删除和查找操作的平均时间复杂度都是 O(log n)，最坏情况下为 O(n)，这里的 n 是跳跃表中的节点数量。
跳跃表的设计目标
- 高效的查找：能够快速定位到目标元素，在大数据量下依然保持较好的查找性能，避免像链表那样需要依次遍历每个节点，提升查找效率。
- 动态的插入和删除：在数据动态变化（插入新元素或删除已有元素）的情况下，依然能维持较好的性能，并且插入和删除操作的实现要相对简单，避免过于复杂的逻辑。
- 空间复杂度可控：在保证查找、插入和删除性能的同时，要合理控制额外的空间开销，不能因为提升性能而导致空间占用过大。
Redis 跳跃表的节点结构设计
Redis 跳跃表的节点结构定义在 server.h 文件中，如下：
typedef struct zskiplistNode {
sds ele; // 成员对象，即有序集合中的元素
double score; // 分值，用于对节点进行排序
struct zskiplistNode *backward; // 后退指针，用于从后向前遍历
struct zskiplistLevel {
struct zskiplistNode *forward; // 前进指针
unsigned long span; // 跨度，表示从当前节点到 forward 指向节点之间的节点数量
} level[]; // 柔性数组，用于存储不同层级的指针和跨度信息
} zskiplistNode;
- ele：是一个 SDS（Simple Dynamic String）类型，用于存储有序集合的成员元素。SDS 是 Redis 自定义的字符串表示，相比 C 语言原生字符串，具有更多优点，如获取长度时间复杂度为 O(1)，杜绝缓冲区溢出等。
- score：双精度浮点数类型，作为节点排序的依据。在有序集合中，元素是按照分值从小到大排序的。
- backward：后退指针，它使得跳跃表可以反向遍历。这在一些场景下很有用，比如在获取某个元素的前一个元素时，可以通过后退指针快速实现。
- level：柔性数组，它的大小是动态的。每个元素是
zskiplistLevel结构体，包含forward指针和span跨度。forward指针指向同一层的下一个节点，span记录了从当前节点到forward指向节点之间的节点数量（不包括当前节点，但包括forward指向的节点）。
跳跃表的层级结构设计
Redis 跳跃表整体由多层节点组成，最高层的节点形成了一个稀疏的索引结构。每个节点的层级数在插入节点时随机生成。
- 随机层级生成算法：
在 Redis 中，使用
zslRandomLevel函数来生成节点的层级数，代码如下：
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
这里 ZSKIPLIST_P 是一个概率值，定义为 0.25，意味着有 25% 的概率将节点的层级数增加一层。ZSKIPLIST_MAXLEVEL 定义了跳跃表的最大层级数，默认是 32。
这种随机层级生成算法保证了跳跃表在平均情况下具有较好的结构，使得查找操作可以快速跳过中间节点，从而达到接近 O(log n) 的时间复杂度。
- 层级结构对查找的优化
以一个简单的跳跃表为例，假设跳跃表有 4 层，包含 10 个节点，节点的分值依次为 1 - 10。
最高层（第 4 层）可能只有少数几个节点，形成了一个稀疏的索引。当查找分值为 7 的节点时，从最高层的第一个节点开始，通过
forward指针依次比较节点的分值。如果当前节点的分值小于 7 且下一个节点的分值大于 7，就下降到下一层继续查找。这样可以快速跳过大量无关节点，减少查找次数。
跳跃表的插入操作设计
-
插入操作的整体流程：
- 首先，通过查找操作找到插入位置。在查找过程中，记录下每一层需要更新的前驱节点（即当前层中分值小于要插入节点分值且距离要插入节点最近的节点）。
- 然后，随机生成要插入节点的层级数。
- 接着，根据生成的层级数，为新节点分配内存，并初始化节点的
ele、score等字段。 - 最后，更新前驱节点的
forward指针和跨度信息，将新节点插入到跳跃表中。
-
代码实现示例：
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--) {
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;
}
level = zslRandomLevel();
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);
for (i = 0; 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[0] - rank[i]);
update[i]->level[i].span = (rank[0] - rank[i]) + 1;
}
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;
}
在这段代码中，update 数组用于记录每一层的前驱节点，rank 数组用于记录从跳跃表头节点到当前节点的跨度。通过这些信息，可以准确地将新节点插入到合适的位置，并更新相关的指针和跨度。
跳跃表的删除操作设计
-
删除操作的整体流程：
- 首先，通过查找操作找到要删除的节点。在查找过程中，同样记录下每一层需要更新的前驱节点。
- 然后，从最低层开始，更新前驱节点的
forward指针，跳过要删除的节点，并相应地更新跨度信息。 - 最后，如果删除节点后，某一层只剩下头节点，那么需要降低跳跃表的层级。
-
代码实现示例：
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;
}
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele, ele) == 0) {
zslDeleteNode(zsl, x, update);
if (!node)
zslFreeNode(x);
return 1;
}
return 0;
}
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;
update[i]->level[i].forward = x->level[i].forward;
} else {
update[i]->level[i].span--;
}
}
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--;
}
在 zslDelete 函数中，先找到要删除的节点及其前驱节点，然后调用 zslDeleteNode 函数进行实际的删除操作。zslDeleteNode 函数更新指针和跨度，并在必要时降低跳跃表的层级。
跳跃表的查找操作设计
-
查找操作的流程： 从跳跃表的最高层开始，沿着
forward指针依次比较节点的分值。如果当前节点的分值小于目标分值，继续沿着forward指针前进；如果当前节点的分值大于目标分值，下降到下一层继续查找；如果当前节点的分值等于目标分值，再比较成员元素（ele）是否相等，如果相等则找到目标节点，否则继续查找。 -
代码实现示例：
zskiplistNode *zslSearch(zskiplist *zsl, double score, sds ele) {
zskiplistNode *x = zsl->header;
int i;
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;
}
}
x = x->level[0].forward;
if (x && score == x->score && sdscmp(x->ele, ele) == 0) {
return x;
}
return NULL;
}
这段代码通过多层遍历和比较，快速定位到目标节点，如果找不到则返回 NULL。
Redis 跳跃表设计的独特之处总结
- 随机层级生成：采用简单的随机算法来决定节点的层级数，通过概率控制使得跳跃表在平均情况下具有类似平衡树的结构，既保证了查找性能，又简化了实现，避免了像平衡树那样复杂的旋转等操作来维持平衡。
- 柔性数组实现层级指针：使用柔性数组来存储不同层级的指针和跨度信息，这种设计在内存使用上更加灵活和高效，不需要为每个节点预先分配固定大小的层级指针数组，减少了内存浪费。
- 双向链表特性：每个节点包含后退指针，使得跳跃表可以双向遍历，这在一些需要反向查找或获取前一个元素的场景中非常有用，增加了数据结构的灵活性。
- 跨度信息的使用：在节点的每个层级中记录跨度信息，这在插入和删除操作时可以方便地更新相关指针的跨度，保证了操作的高效性，同时在查找操作中也可以利用跨度信息快速定位到目标节点。
Redis 跳跃表通过这些独特的设计思路，在有序数据结构的实现上提供了一种高效且相对简单的解决方案，成为 Redis 有序集合底层存储的重要组成部分。