01-Redis 数据结构（重要）

官网保平安：https://redis.io/

Redis 常用的数据类型有哪些？

Redis 中比较常见的数据类型有下面这些：

  • 5 种基础数据类型：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。
  • 3 种特殊数据类型：HyperLogLog（基数统计）、Bitmap（位图）、Geospatial (地理位置)。

除了上面提到的之外，还有一些其他的比如 Bloom filter（布隆过滤器）、Bitfield（位域）。

Redis 的数据类型，以及每种数据类型的使用场景 ★★★★★

  • String（字符串）。String 是 Redis 中最简单同时也是最常用的一个数据类型。它是一种二进制安全的数据类型，可以用来存储任何类型的数据比如字符串、整数、浮点数。

    String 的常见场景：

    • 常规 key-value 缓存应用：比如 Session、Token、序列化后的对象(相比较于 Hash 存储更节省内存)、图片的路径；
    • 常规计数：微博数，粉丝数。
    • 计数比如用户单位时间的请求数（简单限流可以用到）、页面单位时间的访问数；
    • 分布式锁(利用 SETNX key value 命令可以实现一个最简易的分布式锁)；

    用法：

    • set(name, value, ex=None, px=None, nx=False, xx=False)
    • get(name)
    • setnx(name, value) 分布式锁
    • setex(name, value, time) 设置过期时间

  • hash（字典）。hash 的 value 存放的是结构化的对象，比较方便的就是操作其中的某个字段。

    常见场景：

    • 做单点登录的时候，可以用这种数据结构存储用户信息，以 cookieId 作为 key，设置 30 分钟为缓存过期时间，能很好的模拟出类似 session 的效果。
    • 存储用户信息，商品信息、文章信息、购物车信息。

    语法：

    • hset(name, key, value) name 对应的 hash 中设置一个键值对（不存在，则创建；否则，修改）
    • hmset(name, mapping) 在 name 对应的 hash 中批量设置键值对,如：r.hmset('xx', {'k1':'v1', 'k2': 'v2'})
    • hget(name,key) 在 name 对应的 hash 中获取根据 key 获取 value
    • hmget(name, keys, *args) 在 name 对应的 hash 中获取多个 key 的值

  • list（链表）。Redis 最重要的数据结构之一，list 的实现为一个双向链表，即可以支持反向查找和遍历，更方便操作，不过带来了部分额外的内存开销。

    常见场景：

    • 微博的关注列表，粉丝列表，消息列表等。
    • 最新文章、最新动态。
    • 可以通过 lrange 命令，从某个元素开始读取多少个元素，可以基于 list 实现分页查询，这个很棒的一个功能，基于 Redis 实现简单的高性能分页，可以做类似微博那种下拉不断分页的东西（一页一页的往下走），性能高。

    常见场景：

    • lpush(name, values) 在 name 对应的 list 中添加元素，每个新的元素都添加到列表的最左边
    • rpush(name, values) 在 name 对应的 list 中添加元素，每个新的元素都添加到列表的最右边
    • lpop(name) 在 name 对应的列表的左侧获取第一个元素并在列表中移除，返回值则是第一个元素
    • rpop(name) 在 nam e对应的列表的右侧获取第一个元素并在列表中移除，返回值则是第一个元素

  • set（集合）。就是不允许重复的列表。无序，有点类似于 Java 中的 HashSet。

    常见场景：

    • 需要存放的数据不能重复的场景：网站 UV 统计（数据量巨大的场景还是 HyperLogLog更适合一些）、文章点赞、动态点赞等等。
    • 需要获取多个数据源交集、并集和差集的场景：：共同好友(交集)、共同粉丝(交集)、共同关注(交集)、好友推荐（差集）、音乐推荐（差集）、订阅号推荐（差集+交集） 等等。
    • 需要随机获取数据源中的元素的场景：：抽奖系统、随机点名等等。

  • sorted set（有序集合）。在集合的基础上，为每元素排序；元素的排序需要根据另外一个值来进行比较，所以，对于有序集合，每一个元素有两个值，即：值和分数，分数专门用来做排序。zset 的成员是唯一的，但是分数（Score）却可以重复。

    可以做排行榜应用：

    • 比如在直播系统中，实时排行信息包含直播间在线用户列表，各种礼物排行榜，弹幕消息（可以理解为按消息维度的消息排行榜），取 TOP N 操作。
    • 学生成绩排名
    • 粉丝列表，根据关注的先后时间排序

    用法：

    • zadd myset 2 "two" 3 "three" 将一个或多个成员元素及其分数值加入到有序集当中。
    • zrange myset 0 -1 返回有序集中，指定区间内的成员

String 还是 Hash 存储对象数据更好呢？

  • String 存储的是序列化后的对象数据，存放的是整个对象。Hash 是对对象的每个字段单独存储，可以获取部分字段的信息，也可以修改或者添加部分字段，节省网络流量。如果对象中某些字段需要经常变动或者经常需要单独查询对象中的个别字段信息，Hash 就非常适合。
  • String 存储相对来说更加节省内存，缓存相同数量的对象数据，String 消耗的内存约是 Hash 的一半。并且，存储具有多层嵌套的对象时也方便很多。如果系统对性能和资源消耗非常敏感的话，String 就非常适合。

在绝大部分情况，我们建议使用 String 来存储对象数据即可！

购物车信息用 String 还是 Hash 存储更好呢?

由于购物车中的商品频繁修改和变动，购物车信息建议使用 Hash 存储：

  • 用户 id 为 key
  • 商品 id 为 field，商品数量为 value

Hash维护简单的购物车信息

那用户购物车信息的维护具体应该怎么操作呢？

  • 用户添加商品就是往 Hash 里面增加新的 field 与 value；
  • 查询购物车信息就是遍历对应的 Hash；
  • 更改商品数量直接修改对应的 value 值（直接 set 或者做运算皆可）；
  • 删除商品就是删除 Hash 中对应的 field；
  • 清空购物车直接删除对应的 key 即可。

这里只是以业务比较简单的购物车场景举例，实际电商场景下，field 只保存一个商品 id 是没办法满足需求的。

String 的底层实现是什么？

Redis 是基于 C 语言编写的，但 Redis 的 String 类型的底层实现并不是 C 语言中的字符串（即以空字符 \0 结尾的字符数组），而是自己编写了 SDS（Simple Dynamic String，简单动态字符串） 来作为底层实现。

SDS 最早是 Redis 作者为日常 C 语言开发而设计的 C 字符串，后来被应用到了 Redis 上，并经过了大量的修改完善以适合高性能操作。

Redis7.0 的 SDS 的部分源码如下（https://github.com/redis/redis/blob/7.0/src/sds.h）:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used */
    uint8_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

通过源码可以看出，SDS 共有五种实现方式 SDS_TYPE_5（并未用到）、SDS_TYPE_8、SDS_TYPE_16、SDS_TYPE_32、SDS_TYPE_64，其中只有后四种实际用到。Redis 会根据初始化的长度决定使用哪种类型，从而减少内存的使用。

类型 字节 位
sdshdr5 < 1 < 8
sdshdr8 1 8
sdshdr16 2 16
sdshdr32 4 32
sdshdr64 8 64

对于后四种实现都包含了下面这 4 个属性：

  • len：字符串的长度也就是已经使用的字节数
  • alloc：总共可用的字符空间大小，alloc-len 就是 SDS 剩余的空间大小
  • buf[]：实际存储字符串的数组
  • flags：低三位保存类型标志

SDS 相比于 C 语言中的字符串有如下提升：

  1. 可以避免缓冲区溢出：C 语言中的字符串被修改（比如拼接）时，一旦没有分配足够长度的内存空间，就会造成缓冲区溢出。SDS 被修改时，会先根据 len 属性检查空间大小是否满足要求，如果不满足，则先扩展至所需大小再进行修改操作。
  2. 获取字符串长度的复杂度较低：C 语言中的字符串的长度通常是经过遍历计数来实现的，时间复杂度为 O(n)。SDS 的长度获取直接读取 len 属性即可，时间复杂度为 O(1)。
  3. 减少内存分配次数：为了避免修改（增加/减少）字符串时，每次都需要重新分配内存（C 语言的字符串是这样的），SDS 实现了空间预分配和惰性空间释放两种优化策略。当 SDS 需要增加字符串时，Redis 会为 SDS 分配好内存，并且根据特定的算法分配多余的内存，这样可以减少连续执行字符串增长操作所需的内存重分配次数。当 SDS 需要减少字符串时，这部分内存不会立即被回收，会被记录下来，等待后续使用（支持手动释放，有对应的 API）。
  4. 二进制安全：C 语言中的字符串以空字符 \0 作为字符串结束的标识，这存在一些问题，像一些二进制文件（比如图片、视频、音频）就可能包括空字符，C 字符串无法正确保存。SDS 使用 len 属性判断字符串是否结束，不存在这个问题。

🤐 多提一嘴，很多文章里 SDS 的定义是下面这样的：

1
2
3
4
5
struct sdshdr {
    unsigned int len;
    unsigned int free;
    char buf[];
};

这个也没错，Redis 3.2 之前就是这样定义的。后来，由于这种方式的定义存在问题，len 和 free 的定义用了 4 个字节，造成了浪费。Redis 3.2 之后，Redis 改进了 SDS 的定义，将其划分为了现在的 5 种类型。

Redis 的有序集合底层为什么要用跳表，而不用平衡树、红黑树或者 B+树？

这道面试题很多大厂比较喜欢问，难度还是有点大的。

  • 平衡树 vs 跳表：平衡树的插入、删除和查询的时间复杂度和跳表一样都是 **O(log n)**。对于范围查询来说，平衡树也可以通过中序遍历的方式达到和跳表一样的效果。但是它的每一次插入或者删除操作都需要保证整颗树左右节点的绝对平衡，只要不平衡就要通过旋转操作来保持平衡，这个过程是比较耗时的。跳表诞生的初衷就是为了克服平衡树的一些缺点。跳表使用概率平衡而不是严格强制的平衡，因此，跳表中的插入和删除算法比平衡树的等效算法简单得多，速度也快得多。

  • 红黑树 vs 跳表：相比较于红黑树来说，跳表的实现也更简单一些，不需要通过旋转和染色（红黑变换）来保证黑平衡。并且，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

  • B+树 vs 跳表：B+树更适合作为数据库和文件系统中常用的索引结构之一，它的核心思想是通过可能少的 IO 定位到尽可能多的索引来获得查询数据。对于 Redis 这种内存数据库来说，它对这些并不感冒，因为 Redis 作为内存数据库它不可能存储大量的数据，所以对于索引不需要通过 B+树这种方式进行维护，只需按照概率进行随机维护即可，节约内存。而且使用跳表实现 zset 时相较前者来说更简单一些，在进行插入时只需通过索引将数据插入到链表中合适的位置再随机维护一定高度的索引即可，也不需要像 B+树那样插入时发现失衡时还需要对节点分裂与合并。

#面试 #Redis
01-Redis 数据结构（重要）
https://flepeng.github.io/interview-41-数据库-41-Redis-01-Redis-数据结构（重要）/
作者
Lepeng
发布于
2020年8月8日
许可协议