Redis Data Types - tenji/ks GitHub Wiki

Redis 数据结构及底层原理

一、String（字符串）

...

二、List（列表）

...

三、Hash（字典）

...

四、Set（集合）

底层原理

在 Redis7.2 之前，set 使用的是 intset 和 hashtable
在 Redis7.2 之后，set 使用的是 intset, listpack, hashtable

五、ZSet（有序集合）

Redis 中的 zset 是一种有序集合类型，它可以存储不重复的字符串元素，并且给每个元素赋予一个排序权重值（score）。Redis 通过权重值来为集合中的元素进行从小到大的排序。zset 的成员是唯一的，但权重值可以重复。一个 zset 类型的键最多可以存储 2^32 - 1 个元素。

这可能使 Redis 最具特色的一个数据结构了，它类似于 Java 中 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以为每个 value 赋予一个 score 值，用来代表排序的权重。

5.1 源码

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;

5.2 应用场景

zset 类型的应用场景主要是利用分数和排序的特性，比如：

排行榜，利用 zadd 和 zrange 命令实现分数的更新和排名的查询
延时队列，利用 zadd 和 zpopmin 命令实现任务的添加和执行，并且可以定期地获取已经到期的任务
访问统计，可以使用 zset 来存储网站或者文章的访问次数，并且可以按照访问量进行排序和筛选。

5.3 底层原理

Redis 在存储 zset 结构的数据，为了达到内存和性能的平衡，针对少量存储和大量存储分别设计了两种结构，分别为：

ziplist（redis7.0 之前使用）和 listpack（redis7.0 之后使用）
skiplist

当 zset 中的元素个数和元素值的长度比较小的时候，Redis 使用 ziplist/listpack 来节省内存空间。当 zset 中的元素个数和元素值的长度达到一定阈值时，Redis 会自动将 ziplist/listpack 转换为 skiplist，以提高操作效率。具体来说，当 zset 同时满足以下两个条件时，会使用 listpack 作为底层结构：

元素个数小于 zset_max_listpack_entries，默认值为 128
元素值的长度小于 zset_max_listpack_value，默认值为 64

当 zset 中不满足以上两个条件时，会使用 skiplist 作为底层结构。

5.4 基础操作

> ZADD books 9.0 "think in java"
> ZADD books 8.9 "java concurrency"
> ZADD books 8.6 "java cookbook"

> ZRANGE books 0 -1     # 按 score 排序列出，参数区间为排名范围
1) "java cookbook"
2) "java concurrency"
3) "think in java"

> ZREVRANGE books 0 -1  # 按 score 逆序列出，参数区间为排名范围
1) "think in java"
2) "java concurrency"
3) "java cookbook"

> ZCARD books           # 相当于 count()
(integer) 3

> ZSCORE books "java concurrency"   # 获取指定 value 的 score
"8.9000000000000004"                # 内部 score 使用 double 类型进行存储，所以存在小数点精度问题

> ZRANK books "java concurrency"    # 排名
(integer) 1

> ZRANGEBYSCORE books 0 8.91        # 根据分值区间遍历 zset
1) "java cookbook"
2) "java concurrency"

> ZRANGEBYSCORE books -inf 8.91 withscores  # 根据分值区间 (-∞, 8.91] 遍历 zset，同时返回分值。inf 代表 infinite，无穷大的意思。
1) "java cookbook"
2) "8.5999999999999996"
3) "java concurrency"
4) "8.9000000000000004"

> ZREM books "java concurrency"             # 删除 value
(integer) 1
> ZRANGE books 0 -1
1) "java cookbook"
2) "think in java

5.5 跳表

关于跳表，传送门

为什么用跳表而不用平衡树？

对于这个问题，Redis 的作者 @antirez 是怎么说的：

There are a few reasons:

1. They are not very memory intensive. It's up to you basically. Changing parameters about the probability of 
   a node to have a given number of levels will make then less memory intensive than btrees.

2. A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a 
   linked list. With this operation the cache locality of skip lists is at least as good as with other kind of 
   balanced trees.

3. They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received 
   a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little 
   changes to the code.

从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis 里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。

5.6 quicklist

...

5.7 listpack

...

六、Stream（流）

...

∞、参考资料

Redis 数据结构