侧边栏壁纸
  • 累计撰写 244 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论
隐藏侧边栏

Redis 常见数据结构的底层实现系列(五):有序集合篇

kaixindeken
2021-04-28 / 0 评论 / 0 点赞 / 65 阅读 / 4,081 字

由于哈希表是无序的,而常规的 Redis 集合(非 IntSet 实现)底层是基于哈希表实现的,所以它也是无序的,为了让集合元素变得有序,Redis 专门提供了有序集合(Sorted Set)这种数据结构。

压缩列表

由于引入了排序逻辑,所以有序集合的实现要比集合复杂得多。

为了优化内存管理效率,提升性能,当集合元素数量小于 128 或者单个元素长度小于 64 时,Redis 会使用压缩列表来创建有序集合:

if (server.zset_max_ziplist_entries == 0 ||
    server.zset_max_ziplist_value < sdslen(c->argv[scoreidx+1]->ptr))
{
    zobj = createZsetObject();   // 使用字典+跳跃列表初始化
} else {
    zobj = createZsetZiplistObject();  // 使用压缩列表初始化
}
dbAdd(c->db,key,zobj);

和列表一样,这两个阈值条件是可以通过 Redis 配置文件配置项进行配置的:

zset-max-ziplist-entries 128   // 元素数量
zset-max-ziplist-value 64      // 元素值长度

你可以通过设置一个小规模的有序集合进行验证:

127.0.0.1:6379> zadd post.views 100 post-1
(integer) 1
127.0.0.1:6379> zadd post.views 80 post-2
(integer) 1
127.0.0.1:6379> zadd post.views 120 post-3
(integer) 1
127.0.0.1:6379> debug object post.views
Value at:0x7f86796c4d40 refcount:1 encoding:ziplist serializedlength:41 lru:511538 lru_seconds_idle:15

可以看到其编码类型正是 ziplist,即压缩列表。关于压缩列表的底层结构,前面介绍列表时已经演示过了,有序集合也是复用了对应的数据结构,不再赘述了,压缩列表本质上是基于数组构建的,然后再按照添加元素时传入的 score 值对其进行升序排序,当新增元素时,会将元素值和分值紧挨在一起存放:

1.jpeg

比如这里的 value 0 就是 post-2,score 0 就是 80,依次类推,所以最终呈现的是一个有序集合。

字典 + 跳跃列表

当集合元素数量超过 128 或者单个元素长度大于 64 时,会结合字典 + 跳跃列表来存储集合元素:

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

这里的字典(dict)和上篇教程介绍的集合内部使用的字典复用的是同一个数据结构,不同之处在于集合的字典键名为元素值,键值为 NULL,而有序集合的字典键名仍然为元素值,键值为 score 字段值,这样就可以在 O(1) 时间内获取指定元素的 score 值。

哈希表当然还是无序的,这也意味着 dict 内部维护的有序集合元素值排列也是无序的,因此 zset 又引入了一个跳跃列表(skiplist)通过 score 值对集合元素进行排序:

// 跳跃列表的节点
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;

跳跃列表的实现原理

跳跃列表也可以简称为跳表,其本质上是一个链表,但是普通的链表查询效率比较低,时间复杂度是 O(N),对于一个长链表而言,要定位到某个元素需要耗费的时间比较长,为此,我们可以引入跳表来优化这个查询效率。

简单来说,跳表就是在普通链表的基础上增加了索引,就像我们为数据库添加索引一样,通过这些索引可以极大提高链表元素的查询效率,实现数据的快速定位:

1.jpeg

如果是普通单链表,查找 33 这个元素需要顺序遍历所有节点,经历 6 次查询才能定位到,如果为单链表添加一层索引的话,可以将查询次数降低到 4 次,再加一层的话,可以将查询次数降到 3 次,查询效率降低了一半!对于这个规模不大的数据集而言,可能效果不是那么明显,但是对于大规模的成千上万的数据集而言,这个优化效果就很显著了。

我们也可以看到,索引级数越多,查询效率越高,不过这里有一个前提,就是链表元素本身是经过排序的,我们可以把跳表看作链表版的二分查找。

如果按照上一层索引是从下一层节点中二选一的方式构建索引,那么第 k 级索引的节点个数就是第 k-1 级索引节点个数的 1/2,假设链表中元素个数是 n,则第 k 级索引的节点数就是 n * 1/2 * 1/2 * ... = n * (1/2)k,相应地,对于 k 级索引而言,查询某个元素的时间复杂度是 O(logn),和二分查找一样,对于海量数据而言,这个查询效率是非常高的,并且和数组不同,跳表是基于链表的,所以新增、删除元素的时间复杂度也是 O(logn)。

当然了,和数据库索引一样,维护索引也需要额外的成本,并不是索引越多越好,需要在两者之间有一个平衡,这也是一种典型的空间换时间的优化策略。

跳表在 Redis 有序集合中的实现

我们再回头来看 Redis 有序集合中的跳表实现:

// 跳跃列表的节点
typedef struct zskiplistNode {
    sds ele;
    double score;
    struct zskiplistNode *backward;
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

ele 对应的是字符串格式元素值,可以通过它定位到存储在字典中的元素对象,score 是分值,backward 指针用于回溯前一个链表节点(Redis 有序集合支持逆序),核心是 level 结构体数组,这就是跳表结构的实现逻辑,其中的每个元素都代表着该元素的一个索引层级,forward 指针用于指向该层级索引链表中的下一个节点(平行,参照前面跳表示意图理解),整体全貌图示如下:

1.jpeg

Redis 中跳表的最高层级通过常量 ZSKIPLIST_MAXLEVEL 定义,目前默认值是 32,因此最多可以容纳 2^64 个元素,这个数量是个天文数字,非常庞大。

由于 zsl 跳表会按照 score 字段值进行升序排序,所以我们可以轻松实现 Redis 有序集合排序相关的功能,再根据跳表中返回的元素值去字典中查询对应元素的完整值对象。

新增元素到跳表时,首先需要通过查询定位插入位置,然后在该位置创建节点,在此之前需要给这个节点随机分配一个层数(Redis 通过随机层数算法分配新节点层数):

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。

再将搜索路径上的节点和这个新节点通过前向后向指针串起来,如果分配的新节点的高度高于当前跳表的最大高度,就使用最大高度。

有人可能会好奇 zskiplistLevel 结构体中的 span 字段有什么用,这个字段是用于计算跳表中某个元素的排名的,在新增元素时,Redis 会计算上一个 zskiplistLevel 节点通过 forward 指针跳到当前 zskiplistLevel 节点之间跳过的节点数,并将其存储到 span 字段中,这样一来,当查找元素时,只需要将期间经过的所有节点 span 值加起来,就是其排名值。

0

评论区