首页 > 《InterviewGuide》第十三弹Redis万字总结
头像
拱白菜的阿秀
编辑于 2021-05-17 17:07
+ 关注

《InterviewGuide》第十三弹Redis万字总结

大家好,我是阿秀。
大家五一过的怎么样啊?有没有出去玩,哦不,有没有被堵在路上...
机智的我选择呆在实验室里看B站技术视频和《计算机程序的构造和解释》。

图片说明
阿秀五一期间除了疯狂卷肝视频之外也没闲着,还把以前自己做的 Redis 笔记好好整理了一遍,大概整理出 25 道高频面试题。由于篇幅原因,一次性更新 25 道题导致整体太过冗长,很多人可能根本看不过来,所以 Redis 篇打算分为两期更新。
另外,C++、操作系统、计算机网络、MySQL 的硬核面试资料均已更新完毕,如果有还没看过的可以先去看看啦。

1、听说过Redis吗?它是什么?

Redis是一个数据库,不过与传统数据库不同的是Redis的数据库是存在内存中,所以读写速度非常快,因此 Redis被广泛应用于缓存方向。

除此之外,Redis也经常用来做分布式锁,Redis提供了多种数据类型来支持不同的业务场景。除此之外,Redis 支持事务持久化、LUA脚本、LRU驱动事件、多种集群方案。

2、Redis的五种数据结构整理

简单动态字符串(Simple Dynamic String,SDS)

Redis没有直接使用C语言传统的字符串,而是自己构建了一种名为简单动态字符串(Simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。

其实SDS等同于C语言中的char * ,但它可以存储任意二进制数据,不能像C语言字符串那样以字符’\0’来标识字符串的结 束,因此它必然有个长度字段。

定义
struct sdshdr {
    // 记录buf数组中已使用字节的数量
    // 等于sds所保存字符串的长度
    int len;

    // 记录buf数组中未使用字节的数量
    int free;

    // 字节数组,用于保存字符串
    char buf[];
}
优点
  1. 获取字符串长度的复杂度为O(1)。
  2. 杜绝缓冲区溢出。
  3. 减少修改字符串长度时所需要的内存重分配次数。
  4. 二进制安全。
  5. 兼容部分C字符串函数。

它具有很常规的 set/get 操作,value 可以是String也可以是数字,一般做一些复杂的计数功能的缓存。

链表

当有一个列表键包含了数量比较多的元素,又或者列表中包含的元素都是比较长的额字符串时,Redis就会使用链表作为列表建的底层实现。

节点底层结构
typedef struct listNode {
    // 前置节点
    struct listNode *prev;
    // 后置节点
    struct listNode *next;
    // 节点的值
    void *value;
} listNode;
list底层结构
typedef struct list {
    // 表头节点
    listNode *head;
    // 表尾节点
    listNode *tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值是放过函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int(*match)(void *ptr, void *key);
} list;
特性
  1. 链表被广泛用于实现Redis的各种功能,比如列表建、发布与订阅、慢查询、监视器等。
  2. 每个链表节点由一个listNode结构来表示,每个节点都有一个指向前置节点和后置节点的指针,所以Redis的链表实现是双端链表。
  3. 每个链表使用一个list结构表示,这个结构带有表头节点指针、表尾节点指针,以及链表长度等信息。
  4. 因为链表表头的前置节点和表尾节点的后置节点都指向NULL,所以Redis的链表实现是无环链表。
  5. 通过为链表设置不同的类型特定函数,Redis的链表可以用于保存各种不同类型的值。
字典

字典的底层是哈希表,类似 C++中的 map ,也就是键值对。

哈希表
typedef struct dictht {
    // 哈希表数组
    dictEntry **table;
    // 哈希表大小
    unsigned long size;
    // 哈希表大小掩码,用于计算索引值
    // 总是等于size-1
    unsigned long sizemark;
    // 该哈希表已有节点的数量
    unsigned long used;
} dichht;
哈希算法

当字典被用作数据库的底层实现,或者哈希键的底层实现时,Redis使用MurmurHash算法。这种算法的优点在于即使输入的键是规律的,算法仍能给出一个个很好的随机分布性,并且算法的计算速度非常快。

哈希冲突的解决方式

Redis的哈希表使用链地址法来解决键冲突,每个哈希表节点都有一个next指针,多个哈希表节点可以用这个单向链表连接起来,这就解决了键冲突的问题。

特性
  1. 字典被广泛用于实现Redis的各种功能,其中包括数据库和哈希键。
  2. Redis中的字典使用哈希表作为底层结构实现,每个字典带有两个哈希表,一个平时使用,另一个仅在进行rehash时使用。
  3. Redis使用MurmurHash2算法来计算键的哈希值。
  4. 哈希表使用链地址法来解决键冲突。
跳跃表

先看这样一张图:

如上图,我们要查找一个元素,就需要从头节点开始遍历,直到找到对应的节点或者是第一个大于要查找的元素的节点(没找到)。时间复杂度为O(N)。

这个查找效率是比较低的,但如果我们把列表的某些节点拔高一层,如下图,例如把每两个节点中有一个节点变成两层。那么第二层的节点只有第一层的一半,查找效率也就会提高。

查找的步骤是从头节点的顶层开始,查到第一个大于指定元素的节点时,退回上一节点,在下一层继续查找。

比如我们要查找16:

  1. 从头节点的最顶层开始,先到节点7。
  2. 7的下一个节点是39,大于16,因此我们退回到7
  3. 从7开始,在下一层继续查找,就可以找到16。

这个例子中遍历的节点不比一维列表少,但是当节点更多,查找的数字更大时,这种做法的优势就体现出来了。还是上面的例子,如果我们要查找的是39,那么只需要访问两个节点(7、39)就可以找到了。这比一维列表要减少一半的数量。

为了避免插入操作的时间复杂度是O(N),skiplist每层的数量不会严格按照2:1的比例,而是对每个要插入的元素随机一个层数。

随机层数的计算过程如下:

  1. 每个节点都有第一层
  2. 那么它有第二层的概率是p,有第三层的概率是p*p
  3. 不能超过最大层数
zskiplistNode
typedef struct zskiplistNode {
    // 后退指针
    struct zskiplistNode *backward;
    // 分值 权重
    double score;
    // 成员对象
    robj *obj;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } leval[];
} zskiplistNode;

一般来说,层的数量越多,访问其他节点的速度越快。

zskipList
typedef struct zskiplist {
    // 表头节点和表尾节点
    struct zskiplistNode *header, *tail;
    // 表中节点的数量
    unsigned long length;
    // 表中层数最大的节点的层数
    int leval;
} zskiplist;
特性
  1. 跳跃表是有序集合的底层实现之一
  2. Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistNode则用于表示跳跃表节点
  3. 每个跳跃表节点的层高都是1至32之间的随机数
  4. 在同一个跳跃表中,多个节点可以包含相同的分值,但每个节点的成员对象必须是唯一的。
  5. 跳跃表中的节点按照分值大小进行排序,当分值相同时,节点按照成员对象的大小进行排序。
  6. 跳表是一种实现起来很简单,单层多指针的链表,它查找效率很高,堪比优化过的二叉平衡树,且比平衡树的实现。
压缩列表

压缩列表(ziplist)是列表键和哈希键的底层实现之一。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。

特性

看他的名字就能看出来,是为了节省内存造的列表结构。

3、Redis常见数据结构以及使用场景分别是什么?

String

String数据结构是简单的key-value类型,value其实不仅可以是String,也可以是数字。 常规key-value缓存应用; 常规计数:微博数,粉丝数等。

Hash

Hash 是一个 string 类型的 field 和 value 的映射表,hash 特别适合用于存储对象,后续操作的时候,你可以直接仅 仅修改这个对象中的某个字段的值。 比如我们可以Hash数据结构来存储用户信息,商品信息等。

List

list 就是链表,Redis list 的应用场景非常多,也是Redis最重要的数据结构之一,比如微博的关注列表,粉丝列表, 消息列表等功能都可以用Redis的 list 结构来实现。

Redis list 的实现为一个双向链表,即可以支持反向查找和遍历,更方便操作,不过带来了部分额外的内存开销。

另外可以通过 lrange 命令,就是从某个元素开始读取多少个元素,可以基于 list 实现分页查询,这个很棒的一个功 能,基于 Redis 实现简单的高性能分页,可以做类似微博那种下拉不断分页的东西(一页一页的往下走),性能高。

Set

set 对外提供的功能与list类似是一个列表的功能,特殊之处在于 set 是可以自动排重的。

当你需要存储一个列表数据,又不希望出现重复数据时,set是一个很好的选择,并且set提供了判断某个成员是否在 一个set集合内的重要接口,这个也是list所不能提供的。可以基于 set 轻易实现交集、并集、差集的操作。

比如:在微博应用中,可以将一个用户所有的关注人存在一个集合中,将其所有粉丝存在一个集合。Redis可以非常 方便的实现如共同关注、共同粉丝、共同喜好等功能。这个过程也就是求交集的过程,具体命令如下:sinterstore key1 key2 key3将交集存在key1内。

Sorted Set

和set相比,sorted set增加了一个权重参数score,使得集合中的元素能够按score进行有序排列。

举例: 在直播系统中,实时排行信息包含直播间在线用户列表,各种礼物排行榜,弹幕消息(可以理解为按消息维 度的消息排行榜)等信息,适合使用 Redis 中的 SortedSet 结构进行存储。

4、有MySQL不就够用了吗?为什么要用Redis这种

全部评论

(4) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期热帖

近期精华帖

热门推荐