面试题】Redis常用数据类型，以及底层实现

2021/12/28 2:07:19

编程Tag： 面试题数据类型列表 Redis int 节点 unsigned ziplist void

本文主要是介绍面试题】Redis常用数据类型，以及底层实现，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

一、Redis的常用数据类型

字符串（string），队列（list），哈希（hash），集合（sets），有序集合（sorted sets）。

二、底层实现

1、字符串

Redis中的字符串都是由动态字符串(simple dynamic string SDS)实现的

所有非数字的key。例如set msg "hello world" 中的key msg.
字符串数据类型的值。例如`` set msg "hello world"中的msg的值"hello wolrd"
非字符串数据类型中的“字符串值”。例如RPUSH fruits "apple" "banana" "cherry"中的"apple" "banana" "cherry"。

SDS数据结构定义：

struct sdshdr {
  int len;// buf 中已占用字节数
  int free;// buf 中剩余可用字节数
  char buf[];// 数据空间
};

Redis 3.2之前的SDS这样设计的有点：

1）有单独的统计变量len和free（称为头部）。可以很方便地得到字符串长度。
2）内容存放在柔性数组buf中，SDS对上层暴露的指针不是指向结构体SDS的指针，而是直接指向柔性数组buf的指针。上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。
3）由于有长度统计变量len的存在，读写字符串时不依赖“\0”终止符，保证了二进制安全。

2、队列（list）

list的底层数据结构时链表。Redis 3.2之前的版本（包含3.2）使用的时ziplist或者linkedlist，Redis 3.2之后版本使用的quicklist。

ziplist

压缩列表是为了节约内存而开发的，是存储在连续内存块上的顺序数据结构。一个压缩列表可以包含任意多的 entry 节点，每个节点包含一个字节数组或整数。redis 中并没有显式定义 ziplist 的数据结构，仅仅提供了一个描述结构 zlentry 用于操作数据。

typedef struct zlentry {
    unsigned int prevrawlensize;// 用于记录前一个 entry 长度的字节数
    unsigned int prevrawlen;    // 前一个 entry 的长度
    unsigned int lensize        // 用于记录当前 entry 类型/长度的字节数
    unsigned int len;           // 实际用于存储数据的字节数
    unsigned int headersize;    // prevrawlensize + lensize
    unsigned char encoding;     // 用于指示 entry 数据的实际编码类型
    unsigned char *p;           // 指向 entry 的开头
} zlentry;

各字段含义如下：

1、zlbytes：压缩列表的字节长度，占4个字节，因此压缩列表最长(2^32)-1字节；
2、zltail：压缩列表尾元素相对于压缩列表起始地址的偏移量，占4个字节；
3、zllen：压缩列表的元素数目，占两个字节；那么当压缩列表的元素数目超过(2^16)-1怎么处理呢？此时通过zllen字段无法获得压缩列表的元素数目，必须遍历整个压缩列表才能获取到元素数目；
4、entryX：压缩列表存储的若干个元素，可以为字节数组或者整数；entry的编码结构后面详述；
5、zlend：压缩列表的结尾，占一个字节，恒为0xFF。

该数据结构具有以下特征：

结构紧凑：一整块连续内存，没有多余的内存碎片，更新会导致内存 realloc 与内存复制，平均时间复杂度为 O(N)
逆向遍历：从表尾开始向表头进行遍历
连锁更新：对前一条数据的更新，可能导致后一条数据的 prev_entry_length 与 encoding 所需长度变化，产生连锁反应，更新操作最坏时间为 O(N2)

quicklist

在较早版本的 redis 中，list 有两种底层实现：

当列表对象中元素的长度比较小或者数量比较少的时候，采用压缩列表 ziplist 来存储
当列表对象中元素的长度比较大或者数量比较多的时候，则会转而使用双向列表 linkedlist 来存储

两者各有优缺点：

ziplist 的优点是内存紧凑，访问效率高，缺点是更新效率低，并且数据量较大时，可能导致大量的内存复制
linkedlist 的优点是节点修改的效率高，但是需要额外的内存开销，并且节点较多时，会产生大量的内存碎片.

为了结合两者的优点，在 redis 3.2 之后，list 的底层实现变为快速列表 quicklist。
快速列表是 linkedlist 与 ziplist 的结合: quicklist 包含多个内存不连续的节点，但每个节点本身就是一个 ziplist。

typedef struct quicklistNode {
    struct quicklistNode *prev;  // 上一个 ziplist 
    struct quicklistNode *next;  // 下一个 ziplist 
    unsigned char *zl;           // 数据指针，指向 ziplist 结构，或者 quicklistLZF 结构
    unsigned int sz;             // ziplist 占用内存长度（未压缩）
    unsigned int count : 16;     // ziplist 记录数量
    unsigned int encoding : 2;   // 编码方式，1 表示 ziplist ，2 表示 quicklistLZF
    unsigned int container : 2;  // 
    unsigned int recompress : 1;         // 临时解压，1 表示该节点临时解压用于访问
    unsigned int attempted_compress : 1; // 测试字段
    unsigned int extra : 10;             // 预留空间
} quicklistNode;

typedef struct quicklistLZF {
    unsigned int sz;    // 压缩数据长度
    char compressed[];  // 压缩数据
} quicklistLZF;

typedef struct quicklist {
    quicklistNode *head;  // 列表头部
    quicklistNode *tail;  // 列表尾部
    unsigned long count;  // 记录总数
    unsigned long len;    // ziplist 数量
    int fill : 16; // ziplist 长度限制，每个 ziplist 节点的长度（记录数量/内存占用）不能超过这个值
    unsigned int compress : 16; // 压缩深度，表示 quicklist 两端不压缩的 ziplist 节点的个数，为 0 表示所有 ziplist 节点都不压缩
} quicklist;

该数据结构有以下特征：

无缝切换：结合了 linkedlist 与 ziplist 的优点，无需在两种结构之间进行切换
中间压缩：作为队列使用的场景下，list 中间的数据被访问的频率比较低，可以选择进行压缩以减少内存占用。

3、哈希（hash）

hash 类型是 Redis 常用数据类型之一，其底层存储结构有两种实现方式。

当存储的数据量较少的时，hash 采用 ziplist 作为底层存储结构，此时要求符合以下两个条件：

哈希对象保存的所有键值对（键和值）的字符串长度总和小于 64 个字节。
哈希对象保存的键值对数量要小于 512 个。

当无法满足上述条件时，hash 就会采用 dict（字典结构）来存储数据，数据结构如下：

typedef struct dictEntry {
    void* key;  // 键
    union {     // 值，可以为指针、有符号长整，无符号长整，双精度浮点
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

typedef struct dictht {
    dictEntry **table;      // 哈希表数组，数组中的每个元素是一个单向链表
    unsigned long size;     // 哈希表数组大小
    unsigned long sizemask; // 哈希掩码，用于计算索引
    unsigned long used;     // 已有节点数量
} dictht;

typedef struct dictType {
    unsigned int (*hashFunction) (const void *key);             // 哈希函数，用于计算哈希值
    int (*keyCompare)(void *privdata, const void *key1, const void *key2); // 键比较函数
    void *(*keyDup)(void *privdata, const void *key);           // 键复制函数
    void *(*valDup)(void *privdata, const void *obj);           // 值复制函数
    void *(*keyDestructor)(void *privdata, const void *key);    // 键销毁函数
    void *(*valDestructor)(void *privdata, const void *obj);    // 值销毁函数
} dictType;

typedef struct dict {
    dictType *type;     // 类型函数，用于实现多态
    void *privdata;     // 私有数据，用于实现多态
    dictht ht[2];       // 哈希表，字典使用 ht[0] 作为哈希表，ht[1] 用于进行 rehash
    int rehashidx;      // rehash索引，当没有执行 rehash 时，其值为 -1
} dict;

数据结构有以下特征：

哈希算法：使用 murmurhash2 作为哈希函数，时间复杂度为O(1)
冲突解决：使用链地址法解决冲突，新增元素会被放到表头，时间复杂度为O(1)

4、集合（sets）

Redis set 采用了两种方式相结合的底层存储结构，分别是 intset（整型数组）与 hash table（哈希表），当 set 存储的数据满足以下要求时，使用 intset 结构：

集合内保存的所有成员都是整数值；
集合内保存的成员数量不超过 512 个。

当不满足上述要求时，则使用 hash table 结构。

intset 的结构体定义如下:

typedf struct inset{
    uint32_t encoding;//指定编码方式，默认为INSET_ENC_INT16
    uint32_t length;//集合内成员的总个数
    int8_t contents[];//实际存储成员的数组，并且数组中的数值从小到大依次排列
}inset;

encoding：用来指定编码格式，共有三种，分别是 INTSET_ENC_INT16、INSET_ENC_INT32 和 INSET_ENC_INT64，它们对应不同的数值范围。Redis 为了尽可能地节省内存，它会根据插入数据的大小来选择不同的编码格式。
length：集合内成员的数量，记录 contents 数组中共有多少个成员。
contents：存储成员的数组，数组中的成员从小到大依次排列，且不允许重复。

有序整型集合，具有紧凑的存储空间，添加操作的时间复杂度为O(N)

5、有序集合（sorted sets)

有序集合（zset）同样使用了两种不同的存储结构，分别是 zipList（压缩列表）和 skipList（跳跃列表），当 zset 满足以下条件时使用压缩列表：

成员的数量小于128 个；
每个 member （成员）的字符串长度都小于 64 个字节。

当有序结合不满足使用压缩列表的条件时，就会使用 skipList 结构来存储数据。

跳跃列表（skipList）又称“跳表”是一种基于链表实现的随机化数据结构，其插入、删除、查找的时间复杂度均为 O(logN)。从名字可以看出“跳跃列表”，并不同于一般的普通链表，它的结构较为复杂，本节只对它做浅显的介绍，如有兴趣可自行研究。

在 Redis 中一个 skipList 节点最高可以达到 64 层，一个“跳表”中最多可以存储 2^64 个元素，每个节点都是一个 skiplistNode（跳表节点）。skipList 的结构体定义如下：

typedf struct zskiplist{
    //头节点
    struct zskiplistNode *header;
    //尾节点
    struct zskiplistNode *tail;
    // 跳表中的元素个数
    unsigned long length;
    //表内节点的最大层数
    int level;
}zskiplist;

header：指向 skiplist 的头节点指针，通过它可以直接找到跳表的头节点，时间复杂度为 O(1)；
tail：指向 skiplist 的尾节点指针，通过它可以直接找到跳表的尾节点，时间复杂度为 O(1)；
length：记录 skiplist 的长度，也就跳表中有多少个元素，但不包括头节点；
level：记录当前跳表内所有节点中的最大层数（level）；

跳跃列表的每一层都是一个有序的链表，链表中每个节点都包含两个指针，一个指向同一层的下了一个节点，另一个指向下一层的同一个节点。最低层的链表将包含 zset 中的所有元素。如果说一个元素出现在了某一层，那么低于该层的所有层都将包含这个元素，也就说高层是底层的子集。