面试官问我Redis底层数据结构

Redis简单介绍一下

Redis是一个开源的、使用C语言编写的、支持网络交互的、可基于内存也可持久化的Key-Value数据库。

有哪些数据结构

说起Redis数据结构，肯定先想到Redis的5 种基本数据结构：String（字符串）、List（列表）、Set（集合）、Hash（散列）、Zset（有序集合）。

但是Redis用C语言封装了一些底层数据结构：

SDS、Linked List、Dict、Skip List、整数集合、压缩列表。

要把基本数据结构和底层数据结构区分开来，基本数据结构是由底层数据结构实现。

SDS

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

SDS定义源码(源码位置：src/sds.h/sdshdr)

Redis3.0版本源码
struct sdshdr{
	int len;//buf数组已使用的字节数量
	int free;//buf数组未使用的字节数量
	char buf[];//char数组，保存字符串
}

Redis6.0版本源码
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; // 已使用长度 
    uint8_t alloc; // 总长度，用1字节存储 
    unsigned char flags; // 低三位存储，高五位预留 
    char buf[]; //char数组，保存字符串
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; // 已使用长度 
    uint16_t alloc; // 总长度，用2字节存储 
    unsigned char flags; // 低三位存储，高五位预留 
    char buf[];//char数组，保存字符串
};
.... //省略 32和64

因为Redis源码是C语言写的，所以源码看一下简单了解就可以。主要看看SDS的数据结构，这里以Redis3.0为例

• int len：记录了buf数组已使用的字节数量
• int free：记录了buf数组未使用的字节数量
• char buf[]：定义了一个char数组，用于保存字符串

举例：

存储一个Redis的String基本数据类型，其中一个String包含一个Key和一个Value，如下

但是Redis用C语言封装了一些底层数据结构：SDS

为什么不直接用C字符串，而要封装一个SDS：

• Redis很注重性能，通过SDS的len可以以O(1)复杂度获取字符串长度
• SDS封装了API，方便字符串操作使用
• SDS空间分配策略在每次对SDS修改的时候会检查SDS空间是否满足需求，不满足会对空间进行扩展，而C字符串需要在修改前对空间进行手动扩展分配(不进行分配可能导致缓冲区溢出)
• C字符串使用空字符'\0'来判断结尾，SDS根据实际长度len判断字符结尾

Linked List

Linked List即我们比较熟悉的数据结构——链表，Linked List是Redis基本数据结构列表的底层实现之一，当列表对象的所有字符串元素长度都小于64字节，并且保存的元素数量小于512个时，列表采用另外一个底层数据结构“压缩列表”实现，后续会介绍。

Linked List节点源码(位置：src/adlist.h/listNode)

//Redis3.0~Redis6.0的Linked List源码实现一致
//listNode为链表节点
typedef struct listNode {
    //前置节点
    struct listNode * prev;
    //后置节点
    struct listNode * next;
    //节点的值
    void * value;
}listNode;

从源码的定义有前置节点和后置节点可以看出，Redis链表为双向链表，如下图所示

Redis Linked List源码(位置：src/adlist.h/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;

• list结构中的head、tail分别为头尾节点，head的prev和tail的next都指向NULL，即Linked List为无环的双向链表
• len保存了链表的节点个数量，通过len可以O(1)复杂度获取链表长度
• dup函数用于复制链表节点保存的值
• free函数用于释放链表节点保存的值
• match函数用于对比链表节点所保存的值和另外一个输入的值是否相等

Dict 字典

字典即我们熟知的Map，用来保存键值对的抽象数据结构。

字典是基本数据结构 Hash的底层实现之一。

字典源码比较多，涉及三个部分：哈希表、哈希表节点、字典

哈希表和哈希表节点源码如下（位置dict.h/dictht）

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

//每个dictEntry结构都保存着一个键值对
typedef struct dictEntry {
    //键
    void *key;
    //值
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    } v;
    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

字典源码（位置 src/dict.h/dict）

typedef struct dict {
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash 索引。当rehash 不在进行时，值为-1
    in trehashidx; /* rehashing not in progress if rehashidx == -1 */
} dict;
 
//为保证字典具有多态及泛型，dictType中提供了如哈希函数以及K-V的各种操作函数，使得字典适用于多重情景
typedef struct dictType {
    //计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    //复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    //复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    //对比键的函数
    int (*keyCompare)
    (void *privdata, const void *key1, const void *key2);
    //销毁键的函数
    void (*keyDestructor)(void *privdata, void *key);
    //销毁值的函数
    void (*valDestructor)(void *privdata, void *obj);
} dictType;
 

字典采用哈希实现，哈希就是通过哈希算法计算一个哈希值，哈希值作为存储在哈希表数组dictEntry **table的下标，所以会不可避免的出现两个数据计算出来同一个哈希值，即出现“哈希冲突”。

字典采用“链地址法”来解决哈希冲突，链地址法即在出现冲突的下标位置建一个链表，然后把后来的数据存储在当前下标的链表下，如下图所示：

（亲身经历：这里如果在面试中自己提到了哈希冲突，面试官会顺着往下挖，问你有哪些解决哈希冲突的方法或者问“你了解哪些计算哈希值的哈希算法”，这里不做更多补充，可以参考《大话数据结构》一书8.10、8.11章节）

Skip List

跳跃表 SkipList 是一种有序数据结构，通过在每个节点中维持多个指向其它节点的指针，达到快速访问节点的目的

平均时间复杂度 O（logN），在大部分情况下，跳跃表的效率与平衡树相近，由于跳跃表实现的简易性，所以 Redis 使用跳表代替平衡树。

Redis中的基本数据结构有序集合ZSet采用跳表和哈希表实现

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

Redis 跳跃表由 redis.h/zskiplistNode 和 redis.h/zskiplist 两个结构定义

typedef struct zskiplist {
    // 头节点，尾节点
    struct zskiplistNode *header, *tail;
    // 节点数量（不算表头）
    unsigned long length;
    // 目前表内节点的最大层数
    int level;
} zskiplist;

typedef struct zskiplistNode {
    // member 对象
    robj *obj;
    // 分值
    double score;
    // 后退指针，指向当前节点的前一个节点，用于表尾向表头遍历时使用
    struct zskiplistNode *backward;
    // 层，节点使用 L1、L2、L3 标记节点中的各个层，每个层里面又带有两个属性
    struct zskiplistLevel {
        // 前进指针，指向表尾方向的其它节点，当程序从表头向表尾遍历时，会沿着层的前进指针进行
        struct zskiplistNode *forward;
        // 这个层跨越的节点数量
        unsigned int span;
    } level[];

} zskiplistNode;

跳表查找过程

• 跳表的查找会从顶层链表的头部元素开始，然后遍历该链表，直到找到元素大于或等于目标元素的节点，如果当前元素正好等于目标，那么就直接返回它。
• 如果当前元素小于目标元素，那么就垂直下降到下一层继续搜索，如果当前元素大于目标或到达链表尾部，则移动到前一个节点的位置，然后垂直下降到下一层。

整数集合

整数集合（intset）是集合键的底层实现之一，当一个集合只包含整数值元素，并且这 个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。

整数集合的实现

整数集合（intset）是Redis用于保存整数值的集合抽象数据结构，它可以保存类型为 int16_t、int32_t或者int64_t的整数值，并且保证集合中不会出现重复元素。

源码：src/intset.h/intset结构表示一个整数集合∶

typedef struct intset (
    //编码方式 
    uint32_t encoding;
    // 集合包含的元素数量 ,即contents数组的长度
    uint32_t length:
    //保存元素的数组
    int8_t contents[]:
)intset;

一个包含五个int16 t类型整数值的整数集合 ：

contents 数组是整数集合的底层实现∶整数集合的每个元素都是contents 数组的 一个数组项（item），各个项在数组中按值的大小从小到大有序地排列，并且数组中不包含 任何重复项。

contents属性声明为int8 t类型的数组，但contents数组的真正类型取决于encoding属性的值：

• 如果 encoding 属性的值为INTSETENC_INT16，数组里的每个项都是一个int16类型的整数值（最小值 为-32768，最大值为32767）。
• 如果 encoding属性的值为 INTSETENC_INT32，数组里的每个项都是一个int32类型的整数值（最小值 为-2147483648，最大值为2147 483647）。
• 如果 encoding属性的值为INTSET ENC INT64，数组里的每个项都是一个int64类型的整数值（最小值为-9 223 372036854775808，最大值为9223 372 036854775807）。

升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有 元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数 集合里面。

升级的好处

• 提示灵活性，整数集合可以通过自动升级底层数组来适应新元素，所以我们可以随意地将 int16 t、int32 t或者int64t类型的整数添加到集合中，而不必担心出现类型错误， 这种做法非常灵活。
• 节约内存，整数集合升级的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操 作只会在有需要的时候进行，这可以尽量节省内存。

压缩列表

Ziplist 是由一系列特殊编码的内存块构成的列表，是为了节约内存而开发的顺序型数据结构， 一个 ziplist 可以包含多个节点（entry）， 每个节点可以保存一个长度受限的字符数组（不以 \0 结尾的 char 数组）或者整数

压缩列表的组成

ziplist 可以包含多个节点，每个节点可以划分为以下几个部分：

参考：

《Redis设计与实现》