京东面试官：讲讲Redis各个数据类型的底层数据结构 20220523

哈喽，大家好，我是指北君。

前段时间有朋友面试京东的时候，遇到这样的面试题。

讲讲Redis的数据类型以及其对应的底层数据结构

那么今天指北君带大家了解一下Redis基本数据类型对应的底层数据结构。

1. 前言

Redis的键值对中的常见数据类型有String （字符串）、List（列表）、Hash（哈希）、Set（集合）、Zset（有序集合）。那么其对应的底层数据结构有SDS(simple dynamic string)、链表、字典、跳跃表、压缩列表、快速列表，整数集合等。

下面我们以此来了解一下，其底层数据结构的精妙之处。

2. Redis底层数据结构

2.1 SDS

Redis自定义了一种简单动态字符串（simple dynamic string），将其作为Redis的默认字符串表示。

其主要结构如下：

len表示这个SDS字符串长度，如果buff字节数组中保存了5个字符那么长度就是5。同时也方便获取SDS的长度。
alloc表示分配的字符数组长度。其值一般是大于SDS字符串长度（len），由于Redis的设计场景就是会频繁的访问，修改数据，所以无论是数据增大或者是缩小都需要尽量减少重新分配内存的操作。所以SDS会预留一些空间，在下一次修改数据的时候可以直接使用原先预分配的内存，同时在每次数据操作的时候也会动态的增加或者减少预留内存空间，。Redis3.0的版本的SDS结构中使用free，表示未分配的空间，但也是同一个设计思想。
flags 标志位，低3位表示类型，其余5位未使用。
buf 实际存储数据的数组，可以保存字符，也可以保存二进制数据。

redis6.0中SDS定义如下 (越来越节约使用内存了，内存是省出来的！)

typedef char *sds;

/* 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[];
};

相对于C语言的字符串，SDS具有以下优点。

获取字符串的长度复杂度更低（常熟复杂度）（复杂度可见此文章）
更加节省内存（针对不同长度设置了不同的数据类型 sdshdr5、sdshdr8、sdshdr16等。）
杜绝缓冲区溢出
大大减少了修改字符串长度时所需要的内存分配次数
二进制安全

2.2 链表

链表是大家比较熟悉的数据结构了，链表提供了高效的节点重排能力，顺序访问，通过增删节点调整长度等特点。Redis List对象的底层实现之一就是链表。

每一个链表节点使用如下的结构来表示。

/* Node, List, and Iterator are the only data structures used currently. */

typedef struct listNode {
    struct listNode *prev;
    struct listNode *next;
    void *value;
} listNode;

二多了listNode可以通过prev 和 next 指针组成一个双端队列如下图：

多个节点可以组成一个链表，Redis使用了List结构来持有这些节点，操作更方便。其结构如下：

typedef struct list {
    listNode *head;  //链表头节点指针
    listNode *tail;  //链表尾节点指针
    void *(*dup)(void *ptr); // 用于复制链表节点所保存的值
    void (*free)(void *ptr); // 用于释放链表节点所保存的值
    int (*match)(void *ptr, void *key); //用于对比链表节点所保存的值和另一个输入值是否相等
    unsigned long len; // 链表所包含的节点数量
} list;

简单结构如下图：

Redis链表具有如下特性：

由于是双端链表，有prev和next指针，获取节点的前置节点和后置节点的复杂度为O(1)
头节点的prev和尾节点的next均指向NULL，为无环链表，可以以NULL为链表访问终点
链表本身提供了指针，可以快速获取链表的表头节点和表尾节点
自带链表长度计数器，可以快速获取链表长度
链表可以保存各种不同类型的值

2.3 字典

字典是一种用于保存键值对的抽象数据结构。

在字典中，一个键（key）可以和一个值（value）进行关联，称之为键值对。字典中每个键都是独一无二的，并且程序都是通过key来操作更新value或者删除数据等。

Redis的字典使用哈希表作为底层实现的，一个哈希表可以包含多个哈希表节点，而每个哈希表节点就保存了字典中的一个键值对。

下面再讲一下哈希表，哈希表节点，以及字典的实现。

哈希表及哈希表节点结构，字典结构如下：

//字典结构
typedef struct dict {
    dictType *type; // 类型特定的函数
    void *privdata;  //私有数据
    dictht ht[2]; //长度为2的哈希表数组， 一般情况下字典仅使用 ht[0]哈希表， ht[1]在rehash的时候会使用到。
    long rehashidx; /* 未进行rehash的时候 rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

//哈希表结构
typedef struct dictht {
    dictEntry **table; //哈希数组
    unsigned long size; //哈希表大小
    unsigned long sizemask; //哈希表掩码，用于计算索引值， 总是等于size-1
    unsigned long used; //表示已有节点数量
} dictht;

//哈希节点
typedef struct dictEntry {
    void *key; //键
    union { //value值，包含了多种类型的值，不同类型的值可以使用不同的数据结构存储，节省内存。
        void *val;  //其值可以是一个指针
        uint64_t u64; //其值也可以是一个uint64_t 整数
        int64_t s64; //其值可以是一个int64_t 整数
        double d; //其值可以是一个double 
    } v;
    struct dictEntry *next; //指向像一个哈希节点
} dictEntry;

普通状态下的字典结构示意图：

添加新建的机制是大家比较熟悉的思路啦。

使用字典设置的哈希函数计算key的哈希值，
哈希值与sizemask 进行 & 运算，计算出索引值。然后加入到数组中。

如果出现哈希冲突，那么会使用链地址法解决冲突，使用next指针指向下一个哈希节点。

哈希表保存的键值逐渐增多或者减少地过程中，程序会对哈希表进行扩展或者收缩，这个过程称之为rehash。

rehash过程中会使用上面的ht[0] ht[1]，具体过程这里就不详细说了，会另外专门写一篇来介绍。

2.4 跳跃表

跳跃表（skiplist ）是一种有序数据结构，它在每个节点中维护多个指向其他节点的指针，从而可以快速访问。其支持平均O(logN) 复杂度的节点查找。

Zset使用了跳跃表和字典作为其底层实现。其好处就是可以进行高效的范围查询，也可以进行高效的单点查询。

在源码中其结构如下：

typedef struct zskiplistNode { //跳跃表节点
    sds ele; //成员对象，各个节点中成员对象唯一的。
    double score; //分值
    struct zskiplistNode *backward; //后退指针
    struct zskiplistLevel { //层， 最大32层
        struct zskiplistNode *forward; //前进指针
        unsigned long span; //跨度
    } level[];
} zskiplistNode;

typedef struct zskiplist { //跳跃表
    struct zskiplistNode *header, *tail;//指向 跳跃表头 和表尾节点
    unsigned long length; // 节点数量
    int level; //跳跃表中层数最大的节点层数量
} zskiplist;

typedef struct zset { // zset的数据结构使用了 字典dict 和 zskiplist
    dict *dict;
    zskiplist *zsl;
} zset;

关于跳跃表节点的各参数解释如下：

层 level：跳跃表节点的level数组可以包含多个节点元素，每个元素都包含指向其他节点的指针，程序可以通过这些指针来加快访问其他节点的速度，层数越多访问效率越高。每创建一个新的跳跃表节点，程序会随机生成一个1-32之间层数的值，作为level数组的大小。表示节点的高度。
前进指针，forward ：每层有一个指向表尾方向的前进指针，可以通过表头向表尾访问节点。
跨度 span：记录两个节点之间的距离。
后退指针 backward：节点的后退指针，用于从表尾向表头访问节点，每个节点只有一个后退指针，所以每次只能后退一个节点。
分值 score：分值是一个浮点数，跳跃表中的节点按照分值来排序，
成员对象 ele：一个指针，指向一个SDS对象。

下面我们画一个跳跃表的示意图：

图中如果要访问节点3，则只需要通过头节点第四层的前进指针，就可以找到此节点。

如果需要增加元素的时候，会先使用高层前进指针去遍历，并对比score值，然后逐步缩小插入元素的位置范围，然后确定最终的位置。这样其平均时间复杂度为O(logN). 相比于链表的O(N)的时间复杂度来说，其效率大大提高。只不过其代价就是需要多一点的内存空间。

个人感觉和MySql的索引有点类似。

2.5压缩列表 ziplist

压缩列表是 Redis中list和 hash 对象的底层实现之一。压缩列表是为了节约内存而开发的，是由一系列连续编码的内存块组成。其结构示意如下：

其中各节点说明如下：

zlbytes ，4字节，记录压缩列表占用的内存字节数，对压缩列表仅进行内存重分配，或计算zlend尾节点位置时使用。
zltail ，4字节，记录压缩列表尾节点距离压缩列表的起始地址有多少个字节。可以快速计算得到尾节点的地址
zlen， 2字节，记录了压缩列表包含的节点数量
entry X 压缩列表中的节点，其长度取决于节点内容
zlend ， 1字节，特殊值OxFF (255) 标记压缩列表末端

其中每一个压缩列表节点entry由如下部分组成：

previous_entry_length 记录了压缩列表中前一个节点的长度，其属性可以是1或5个字节。如果前一个节点的长度小于254，那么其长度就是1字节，表示前一节点的长度。如果迁移节点的长度大于254字节，那么其属性长度则为5个字节，其中第一个字节会设置为OxFE(254) , 后面的4个字节用来表示前一节点的长度。
encoding 表示content 属性保存的数据类型以及长度。content保存字节数组时，encoding的值为1，2，5字节，最高前两位分别为00，01，10，最高前两位后面的其他位数则记录content的长度。 content保存整数编码时，最高2位为11，其余位记录整数类型及。
content 保存节点的内容，可以保存字节数组或者整数。

由于previous_entry_length 记录了前一个节点的长度，而且其可能为1个字节或者5个字节，如果前一个节点的长度从254之下增加到254之上，那么previous_entry_length 的值就要使用5个字节类表示。而如果后面的节点均存在同样的情况，那么压缩列表就会出现连锁更新，导致内存空间重新分配，从而导致压缩列表增加节点或者删除节点的最坏时间复杂度位O(N2).

新版本的redis中，引入了listpack。其目的是替换ziplist，整体结构类似。

其entry结构如下：

len保存了当前节点encoding及data的长度综合，从而可以避免连锁更新

2.6快速列表

快速列表（quicklist）可以看成是双向链表和压缩列表的一种组合。Redis3.2之后 list对象使用快速列表作为其底层实现。

快速列表使用了quickListNode节点组成双向链表，然后在每个快速列表节点内部使用压缩列表存储数据，从而可以控制压缩列表的长度，避免连锁更新带来的性能影响。

其中快速列表的源码结构如下：

typedef struct quicklist {
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* total count of all entries in all ziplists */
    unsigned long len;          /* number of quicklistNodes */
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

typedef struct quicklistBookmark {
    quicklistNode *node;
    char *name;
} quicklistBookmark;

typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;
    unsigned int sz;             /* ziplist size in bytes */
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

quickList 中维护了一个quicklistBookmark数组，并且有执行qulickListNode 头尾的指针。

每一个quicklistBookmark 中有一个quickListNode的指针，同时每一个quickListNode又有指向前一个后一个node的指针。

其结构示意图如下：

2.7 整数集合

整数集合（intset）是集合键底层实现之一，当一个集合只包含整数元素的时候，Redis会使用整数集合作为集合键的实现。

整数集合的源码如下：

typedef struct intset {
    uint32_t encoding;
    uint32_t length;
    int8_t contents[];
} intset;

整数集合底层是一个数组，如果每一个元素都在16位以内的整数类型(-32768 到 32767)，则数组的每个元素都为int16_t ，如果新加的整数超过这个范围，并且在32位以内的话，整个数组中的每一个元素都会升级成int32_t 表示的整数，如果新加入的是64 位才能表示的整数的话，所以的元素又会再一次升级。

但是整数集合不支持降级，及整数集合中如果有一个64位的整数，即使移除此元素，整个集合也不会降级。

这样做具有一定的灵活性，而且可以节省内存。当需要升级的时候才进行升级。

总结

通过以上 Redis 底层数据结构可以看出，其设计核心总是在节约内内存，提高访问速度。所以Redis快，这小巧妙的底层设计也是功不可没。同时我们也可以根据着些设计思想去优化我们自己的代码，优秀的设计总是值得去学习的。