Redis源码阅读（二）底层数据结构

Redis对于底层数据结构的极致封装，是Redis高效运行的原因之一。我们结合Redis源码对其进行分析。

一、Value的数据类型封装

Redis中的对象结构体：redisObject结构

代码语言：javascript复制

typedef struct redisObject {
    unsigned type:4;            // 对象的类型，字符串/列表/集合/有序集合/哈希表
    unsigned encoding:4;        // 编码的方式，Redis 为了节省空间，提供多种方式来保存数据
    unsigned lru:LRU_BITS;      // 缓存淘汰使用；淘汰的标准为：oversize & overtime
    int refcount;               // 引用计数；为优化内存，对数字字符串进行共享内存，引用计数方式管理
    void *ptr;                  // 数据指针，指向实际存储的某一种数据结构
} robj;

type：数据类型

代码语言：javascript复制

#define OBJ_STRING 0  /* 字符串对象*/
#define OBJ_LIST 1    /* 列表对象 */
#define OBJ_SET 2     /* 集合对象 */
#define OBJ_ZSET 3    /* 有序集合对象 */
#define OBJ_HASH 4    /* 散列表对象 */
#define OBJ_MODULE 5  /* 模块对象 */
#define OBJ_STREAM 6  /* 流对象 */

encoding：为优化内存，对每种type类型都至少会有两种底层实现方式

代码语言：javascript复制

#define OBJ_ENCODING_RAW 0        /* Raw representation */
#define OBJ_ENCODING_INT 1        /* 编码为整数 */
#define OBJ_ENCODING_HT 2         /* 编码为散列表 */
#define OBJ_ENCODING_ZIPMAP 3     /* 编码为zipmap */
#define OBJ_ENCODING_LINKEDLIST 4 /* 不再使用：旧列表编码*/
#define OBJ_ENCODING_ZIPLIST 5    /* 编码为压缩列表 */
#define OBJ_ENCODING_INTSET 6     /* 编码为整数集合*/
#define OBJ_ENCODING_SKIPLIST 7   /* 编码为跳表*/
#define OBJ_ENCODING_EMBSTR 8     /* 编码为简短字符串*/
#define OBJ_ENCODING_Quicklist 9  /* 编码为快速链表*/
#define OBJ_ENCODING_STREAM 10    /* 编码为listpacks的基数树*/

refcount：为优化内存，对数字字符串进行共享内存，引用计数方式管理注：Redis单线程，引用计数的增加和减少不必保证原子性
lru：与数据淘汰有关 Redis对数据集占用内存的大小由周期性的计算，当超出限制时，会淘汰超时的数据。即淘汰的标准为：oversize & overtime。
ptr：指向实际存储的某一种数据结构

Encoding：即不同数据类型在Redis内部的存储方式

OBJECT ENCODING	编码常量	底层数据结构
int	OBJ_ENCODING_INT	整数
embstr	OBJ_ENCODING_EMBSTR	embstr编码的简单动态字符串（SDS）
raw	OBJ_ENCODING_RAW	简单动态字符串（SDS）
ht (hashtable)	OBJ_ENCODING_HT	字典
linkedlist	OBJ_ENCODING_LINKEDLIST	双端链表
ziplist	OBJ_ENCODING_ZIPLIST	压缩列表
intset	OBJ_ENCODING_INTSET	整数集合
skiplist	OBJ_ENCODING_SKIPLIST	跳跃表和字典
zipmap	OBJ_ENCODING_ZIPMAP	压缩映射表
quicklist	OBJ_ENCODING_QUICKLIST	快速链表
listpack	OBJ_ENCODING_STREAM	紧凑列表

数据类型与编码对象的对应关系：

数据类型	编码	底层数据结构
OBJ_STRING	OBJ_ENCODING_INT	使用整数值实现的字符串对象
OBJ_STRING	OBJ_ENCODING_EMBSTR	使用embstr编码的简单动态字符串实现的字符串对象
OBJ_STRING	OBJ_ENCODING_RAW	使用简单动态字符串实现的字符串对象
OBJ_LIST	OBJ_ENCODING_LINKEDLIST	使用双端链表实现的列表对象
OBJ_LIST	OBJ_ENCODING_ZIPLIST	使用压缩列表实现的列表对象
OBJ_HASH	OBJ_ENCODING_ZIPLIST	使用压缩列表实现的哈希对象
OBJ_HASH	OBJ_ENCODING_HT	使用字典实现的哈希对象
OBJ_SET	OBJ_ENCODING_INTSET	使用整数集合实现的集合对象
OBJ_SET	OBJ_ENCODING_HT	使用字典实现的集合对象
OBJ_ZSET	OBJ_ENCODING_ZIPLIST	使用压缩列表实现的有序集合对象
OBJ_ZSET	OBJ_ENCODING_SKIPLIST	使用跳跃表和字典实现的有序集合对象
OBJ_STREAM	OBJ_ENCODING_STREAM	使用紧凑列表和rax树实现的有序集合对象

（1）字符串类型（t_string.c）

使用SDS类型替换C语言中的char*类型：

为了高效实现追加和长度计算
为了保证二进制安全

encoding：

int 编码：保存long 型的64位有符号整数；数据直接存储在ptr字段
embstr 编码：保存长度小于44字节的字符串；只分配一次内存，robj与sds连续存储，以此提升内存分配效率与数据访问效率
raw 编码：保存长度大于44字节的字符串

Redis 内部会根据用户给的不同键值而使用不同的编码格式，而这一切对用户完全透明

（2）列表类型（t_list.c）

ziplist：列表对象所有字符串元素数量小于512，所有元素长度小于64字节（Redis 3.2之前）
linkedlist：不满足ziplist条件的其他情况（Redis 3.2之前）
quicklist：由adlist和ziplist结合而成；综合考虑了时间效率与空间效率引入的新型数据结构

（3）哈希表类型（t_hash.c）

ziplist：列表对象所有字符串元素数量小于512，所有元素长度小于64字节
ht：不满足ziplist条件的其他情况

（4）集合类型（t_set.c）

intset：所有的元素都是整数，元素数量小于512
ht：不满足ziplist条件的其他情况

（5）有序集合类型（t_zset.c）

Redis的配置文件中关于有序集合底层实现的两个配置：

代码语言：javascript复制

# zset采用压缩列表时，元素个数最大值。默认值为128。
zset-max-ziplist-entries 128
# zset采用压缩列表时，每个元素的字符串长度最大值。默认值为64。
zset-max-ziplist-value 64

ziplist：元素数量小于128，元素长度小于64
skiplist：不满足ziplist条件的其他情况

（6）数据流类型（t_stream.c）

Redis Stream的底层实现主要使用了listpack以及Rax树

listpack：用于存储具体的消息
Rax树：用于快速索引

由消息、生产者、消费者、消费组4部分组成

Redis Stream本质上是在Redis内核上实现的一个消息发布订阅功能组件。相比于现有的PUB/SUB、BLOCKED LIST，其虽然也可以在简单的场景下作为消息队列来使用，但是Redis Stream无疑要完善很多。Redis Stream提供了消息的持久化和主备复制功能、新的RadixTree数据结构来支持更高效的内存使用和消息读取、甚至是类似于Kafka的Consumer Group功能。

二、底层数据结构

（1）简单动态字符串（sds.c）

SDS结构体（5种，字段数据类型不同，sdshdr5例外），以sdshdr8为例：

代码语言：javascript复制

struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len;           // 字符串的实际使用长度
    uint8_t alloc;         // 总长度；5.0之前使用的是free，用于标识buff中剩余可用字节数
    unsigned char flags;   // 标志位，低三位表示类型，其余五位未使用
    char buf[];            // 字符数组，柔性数组，存放实际内容
};

柔性数组成员（flexible array member），也叫伸缩性数组成员，只能被放在结构体的末尾。包含柔性数组成员的结构体，通过malloc函数为柔性数组动态分配内存。之所以用柔性数组存放字符串，是因为柔性数组的地址和结构体是连续的，这样查找内存更快（因为不需要额外通过指针找到字符串的位置）；可以很方便地通过柔性数组的首地址偏移得到结构体首地址，进而能很方便地获取其余变量。

SDS返回给上层的，不是结构体首地址，而是指向内容的buf指针，故上层可像读取C字符串一样读取SDS的内容，兼容C语言处理字符串的各种函数。

由于有长度统计变量len的存在，读写字符串时不依赖“”终止符，保证了二进制安全。

Redis 3.2后的SDS结构由1种增至5种，且对于sdshdr5类型，在创建空字符串时会强制转换为sdshdr8。原因可能是创建空字符串后，其内容可能会频繁更新而引发扩容，故创建时直接创建为sdshdr8。

基本操作：

函数名	说明
sdsnewlen	创建字符串，会根据字符串长度选择合适的类型
sdsfree/sdsclear	直接释放字符串；不直接释放内存，通过重置统计值达到清空目的
sdscatsds	拼接字符串，可能会导致扩容
sdsnew	根据给定的C字符串创建SDS
sdssplitlen	按指定的分隔符对SDS进行切分

拼接字符串可能会导致扩容，扩容策略：

1）若sds中剩余空闲长度avail大于新增内容的长度addlen，直接在柔性数组buf末尾追加即可，无须扩容。

2）若sds中剩余空闲长度avail小于或等于新增内容的长度addlen，则分情况讨论：新增后总长度len addlen<1MB的，按新长度的2倍扩容；新增后总长度len addlen>1MB的，按新长度加上1MB扩容。

3）最后根据新长度重新选取存储类型，并分配空间。此处若无须更改类型，通过realloc扩大柔性数组即可；否则需要重新开辟内存，并将原字符串的buf内容移动到新位置。

（2）字典（dict.c）

字典又称散列表，是用来存储键值（key-value）对的一种数据结构。

对Redis数据库进行任何增、删、改、查操作，实际就是对字典中的数据进行增、删、改、查操作。

字典本质：数组 Hash函数 Hash冲突

数据结构：Hash表(dictht)、Hash表节点(dictEntry)、字典(dict)

A. Hash表-结构体：

代码语言：javascript复制

typedef struct dictht {
    dictEntry **table;            // 指针数组，数组中的元素指向的是dictEntry的结构体
    unsigned long size;           // table数组的大小
    unsigned long sizemask;       // 掩码 = size - 1 
    unsigned long used;           // table数组已存元素个数，包含next单链表的数据
} dictht;

sizemask字段用来计算键的索引值，sizemask的值恒等于size–1。

索引值=Hash值&掩码值，对应Redis源码为：

代码语言：javascript复制

idx = hash & d->ht[table].sizemask；

其计算结果等同Hash值与Hash表容量取余，而计算机的位运算要比取余运算快很多。

B. Hash表节点-结构体：

Hash表中的元素是用dictEntry结构体来封装的，主要作用是存储键值对

代码语言：javascript复制

typedef struct dictEntry {
    void *key;                      // 存储键 key
    union {
        void *val;                  // db.dict中的val
        uint64_t u64;
        int64_t s64;                // db.expires中存储过期时间*/
        double d;
    } v;                            // 值value，是个联合体;在不同场景下使用不同字段
    struct dictEntry *next;         // 当Hash冲突时，指向冲突的元素，形成单链表
} dictEntry;

C. 字典-结构体：

在最外面层封装了一个叫字典的数据结构，其主要作用是对Hash表dictht再进行一层封装

代码语言：javascript复制

typedef struct dict {
    dictType *type;             // 该字典对应的特定操作函数
    void *privdata;             // 该字典依赖的数据 
    dictht ht[2];               // Hash表，键值对存储在此
    long rehashidx;             // rehash标识，默认值为-1，代表没进行rehash操作
                                // 否则，该值表示Hash表ht[0]的rehash操作进行到了哪个索引值
    unsigned long iterators;  // 当前运行的安全迭代器数，当有安全迭代器绑定到该字典时，会暂停rehash
} dict;

type：指向dictType结构体，为了实现各种形态的字典而抽象出来的一组操作函数
privdata：私有数据，配合type字段指向的函数一起使用
ht：是个大小为2的数组，该数组存储的元素类型为dictht，虽然有两个元素，但一般情况下只会使用ht[0]，只有当该字典扩容、缩容需要进行rehash时，才会用到ht[1]
rehashidx：用来标记该字典是否在进行rehash，没进行rehash时，值为-1，否则，该值用来表示Hash表ht[0]执行rehash到了哪个元素，并记录该元素的数组下标值
iterators：用来记录当前运行的安全迭代器数，当有安全迭代器绑定到该字典时，会暂停rehash操作

基本操作：

函数名	说明
dictCreate	初始化一个空字典
dictAdd	添加元素；先查找该键是否存在，存在则执行修改，否则添加键值对
dictFind	查找元素
dbOverwrite	修改元素；修改节点键值对中的值为新值，释放旧值内存
tryResizeHashTables	删除元素；释放该节点对应的key、value及节点本身占用的内存

添加元素可能会导致扩容：

可用空间不够时，导致扩容。扩容时空间大小为当前容量*2，即d->ht[0].used*2

删除元素可能会导致缩容：

当使用量不到总空间10%时，则进行缩容；缩容时空间大小则为能恰好包含d->ht[0].used个节点的2^N次方幂整数，并把字典中字段rehashidx标识为0

1）字典初始化：dictCreate

代码语言：javascript复制

/* 创建一个新的Hash表 */
dict *dictCreate(dictType *type, void *privDataPtr){
    dict *d = zmalloc(sizeof(*d));  //96字节
    _dictInit(d,type,privDataPtr);  //结构体初始化值
    return d;
}
/* Initialize the hash table */
int _ dictInit (dict *d, dictType *type, void *privDataPtr){
    _dictReset(&d->ht[0]);
    _dictReset(&d->ht[1]);
    d->type = type;
    d->privdata = privDataPtr;
    d->rehashidx = -1;
    d->iterators = 0;
    return DICT_OK;
}

主要步骤为：申请空间、调用_dictInit函数，给字典的各个字段赋予初始值。

2）添加元素：dictAdd

Server端收到命令后，会执行setKey(redisDbdb,robjkey,robj*val)函数

第一步：调用dictFind函数，查询键是否存在，是则调用dbOverwrite函数修改键值对，否则调用dbAdd函数添加元素；

第二步：dbAdd最终调用dict.h文件中的dictAdd函数插入键值对。

代码语言：javascript复制

/*调用前会查找key存在与否，不存在则调用dictAdd 函数*/
int dictAdd(dict *d, void *key, void *val){  
    dictEntry *entry = dictAddRaw(d,key,NULL); /*添加键，字典中键已存在则返回NULL，否则添加键至新节点中，返回新节点*/
    if (!entry) return DICT_ERR;               /*键存在则返回错误*/
    dictSetVal(d, entry, val);                 /*设置值*/
    return DICT_OK;
}

dictAddRaw添加键与查找键，添加成功返回新节点，查找成功返回NULL并把老节点存入existing字段：

代码语言：javascript复制

dictEntry *dictAddRaw(dict *d, void *key, dictEntry **existing)/*入参字典、键、Hash表节点地址*/
{
    if (dictIsRehashing(d)) _dictRehashStep(d);  /*该字典是否在进行rehash操作中,是则执行一次rehash*/
    if ((index = _dictKeyIndex(d, key, dictHashKey(d,key), existing)) == -1) 
/*查找键，找到则直接返回-1, 并把老节点存入existing字段，否则把新节点的索引值返回。如果遇到Hash表容量不足，则进行扩容*/
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0]; /*是否进行rehash操作中,是则插入至散列表ht[1]中，否则插入散列表ht[0] */
    /*申请新节点内存，插入散列表中，给新节点存入键信息*/
    entry = zmalloc(sizeof(*entry));
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used  ;
    dictSetKey(d, entry, key);
    return entry;
}

_dictKeyIndex函数：得到健的索引值。

代码语言：javascript复制

dictHashKey(d,key)                  //第1步：调用该字典的Hash函数得到键的Hash值
idx = hash & d->ht[table].sizemask; //第2步：用键的Hash值与字典掩码取与，得到索引值

3）扩容：dictExpand

代码语言：javascript复制

int dictExpand(dict *d, unsigned long size){//传入size = d->ht[0].used*2
    dictht n;
    unsigned long realsize = _dictNextPower(size); /*重新计算扩容后的值，必须为2的N次方幂*/
    n.size = realsize;
    n.sizemask = realsize-1;
    n.table = zcalloc(realsize*sizeof(dictEntry*));
    n.used = 0;
    d->ht[1] = n;         /*扩容后的新内存放入ht[1]中*/
    d->rehashidx = 0;       /*非默认的-1,表示需进行rehash*/
    return DICT_OK;
}

rehash除了扩容时会触发，缩容时也会触发。

扩容时空间大小为当前容量*2，即d->ht[0].used*2；当使用量不到总空间10%时，则进行缩容；缩容时空间大小则为能恰好包含d->ht[0].used个节点的2^N次方幂整数，并把字典中字段rehashidx标识为0。

当数据库中键值对数量达到了百万、千万、亿级别时，整个rehash过程将非常缓慢。Redis利用分而治之的思想了进行rehash操作

执行插入、删除、查找、修改等操作前，都先判断当前字典rehash操作是否在进行中，进行中则调用dictRehashStep函数进行rehash操作（每次只对1个节点进行rehash操作，共执行1次）。

当服务空闲时，如果当前字典也需要进行rehsh操作，则会调用incrementallyRehash函数进行批量rehash操作（每次对100个节点进行rehash操作，共执行1毫秒）。

在经历N次rehash操作后，整个ht[0]的数据都会迁移到ht[1]中，这样做的好处就把是本应集中处理的时间分散到了上百万、千万、亿次操作中，所以其耗时可忽略不计。

4）查找元素：dictFind

代码语言：javascript复制

dictEntry *dictFind(dict *d, const void *key){
    // ...
    h = dictHashKey(ht, key) & ht->sizemask;        //根据Hash值获取到对应的索引值
    he = ht->table[h];
    while(he) {                                     //如果存在值则遍历该值中的单链表
        if (dictCompareHashKeys(ht, key, he->key))
            return he;                              //找到与键相等的值,返回该节点
        he = he->next;
    }
    // ...
}

5）修改元素：dbOverwrite

代码语言：javascript复制

void dbOverwrite(redisDb *db, robj *key, robj *val) {
    dictEntry *de = dictFind(db->dict,key->ptr); //查找键存在与否，返回存在的节点
    serverAssertWithInfo(NULL,key,de != NULL);   //不存在则中断执行
    dictEntry auxentry = *de;
    robj *old = dictGetVal(de);                  //获取老节点的val字段值
    dictSetVal(db->dict, de, val);               //给节点设置新的值
        dictFreeVal(db->dict, &auxentry);        //释放节点中旧val内存
}

6）删除元素：dictDelete函数

注：字典中的遍历

全遍历：一次命令执行就遍历完整个数据库（耗时长，会造成短暂的Redis不可用）
间断遍历：每次命令执行只取部分数据，分多次遍历（2.8.0版本后增加）

（3）链表（adlist.h）

双向非循环列表：

代码语言：javascript复制

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

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;

（4）跳跃表（server.h/skiplist）

跳跃表是基于有序链表改进的，skiplist 将有序链表中的部分节点分层，每一层都是一个有序链表。

有这张图可以看出，skiplist 由多个节点构成，每个节点由很多层构成，每层都有指向本层下个节点的指针。

A. 跳跃表-结构体：

代码语言：javascript复制

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;         // 跳跃表的首尾节点
    unsigned long length;        // 跳跃表长度（不含头节点）
    int level;                   // 跳跃表的高度
} zskiplist;

header头节点的level数组元素个数为64，forward都指向NULL，span值都为0。在有序集合中，ele值为NULL，score值为0；也不计入跳跃表的总长度。

在查找时优先从最高层开始向后查找，当到达某节点时，如果next节点值大于要查找的值或next指针指向NULL，则从当前节点下降一层继续向后查找

跳跃表每个节点维护了多个指向其他节点的指针，可以跳过一些节点，快速找到操作需要的节点。归根结底，跳跃表是以牺牲空间的形式来达到快速查找的目的。

B. 跳跃表节点-结构体：

代码语言：javascript复制

typedef struct zskiplistNode {
    sds ele;           // 用于存储字符串类型的数据
    double score;      // 用于存储排序的分值  
    struct zskiplistNode *backward;       // 后退指针，只能指向当前节点最底层的前一个节点
    struct zskiplistLevel {
        struct zskiplistNode *forward;    // 指向本层下一个节点
        unsigned long span;               // forward指向的节点与本节点之间的元素个数
    } level[];      // 生成跳跃表节点时，随机生成一个1～64的值
} zskiplistNode;

ele：用于存储字符串类型的数据
score：用于存储排序的分值
backward：后退指针，只能指向当前节点最底层的前一个节点；头节点和第一个节点指向NULL，在从后向前遍历跳跃表时使用
level：为柔性数组。每个节点的数组长度不一样，在生成跳跃表节点时，随机生成一个1～64的值，值越大出现的概率越低。
- forward：指向本层下一个节点，尾节点的forward指向NULL
- span：forward指向的节点与本节点之间的元素个数。span值越大，跳过的节点个数越多。

zset中，ele存储zset成员member值，score存储zset的score值

基本操作：

函数名	说明
zslCreateNode	创建节点
zslCreate	创建跳跃表
zslInsert	插入节点
zslDeleteNode, zslDelete, zslDeleteByScore, zslDeleteByRank	删除节点
zslFree	删除跳跃表

1）创建跳跃表

①创建跳跃表结构体对象zsl；②将zsl的头节点指针指向新创建的头节点；③跳跃表层高初始化为1，长度初始化为0，尾节点指向NULL。

插入节点：

①查找要插入的位置；②调整跳跃表高度；③插入节点；④调整backward

删除节点

①查找需要更新的节点；②设置span和forward。

2）删除跳跃表

获取到跳跃表对象之后，从头节点的第0层开始，通过forward指针逐步向后遍历，每遇到一个节点便将释放其内存。当所有节点的内存都被释放之后，释放跳跃表对象，即完成了跳跃表的删除操作。

（5）整数集合（intset.h）

整数集合（intset）是一个有序的（从小到大）、存储整型数据的结构。

结构体：

代码语言：javascript复制

typedef struct intset {
    uint32_t encoding;   //编码类型，决定每个元素占用几个字节
    uint32_t length;     //元素个数
    int8_t contents[];   //柔性数组，存储具体元素；根据encoding字段决定几个字节表示一个元素
} intset;

但在两种情况下，底层编码会发生转换。

当整型元素个数超过一定数量之后（默认值为512），将编码转换为hashtable
当增加非整型变量时，例如在集合中增加元素'a'后，testSet的底层编码从intset转换为hashtable

基本操作：

函数名	说明
intsetFind	查询元素；通过防御性判断之后使用二分法进行元素的查找
intsetAdd, intsetUpgradeAndAdd	添加元素；根据插入值的编码类型，决定是直接插入还是进行升级插入
intsetRemove	删除元素；通过内存地址的移动直接将该元素覆盖掉
intsetNew	初始化一个intset；编码为INTSET_ENC_INT16，长度为0，content未分配空间
intsetRandom	随机返回一个元素

1）查询元素

a.首先判断待查找的值需要的编码格式，如果编码大于该intset的编码，则肯定不存在该值，直接返回，否则调用intsetSearch函数;

b.intsetSearch函数中首先判断该intset中是否有值，无值直接返回0；如果有值再判断待插入的值是否介于此intset的最大值与最小值之间，如果不在此范围内也返回0。

c.用二分查找法寻找该值（intset为有序数组），找到返回1，未找到返回0。

2）添加元素

代码语言：javascript复制

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value); //获取添加元素的编码值
    uint32_t pos;
    if (success) *success = 1;
    if (valenc > intrev32ifbe(is->encoding)) {  //如果大于当前intset的编码，说明需要进行升级
        return intsetUpgradeAndAdd(is,value); //调用intsetUpgradeAndAdd进行升级后添加
    } else {
        if (intsetSearch(is,value,&pos)) {  //否则先进行查重,如果已经存在该元素，直接返回
            if (success) *success = 0;
            return is;
        }
        //如果元素不存在，则添加元素
        is = intsetResize(is,intrev32ifbe(is->length) 1); //首先将intset占用内存扩容
        //如果插入元素在intset中间位置，调用intsetMoveTail给元素挪出空间
        if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos 1);
    }
    _intsetSet(is,pos,value); //保存元素
    is->length = intrev32ifbe(intrev32ifbe(is->length) 1);  //修改intset的长度，将其加1
    return is;
}

其中，intsetUpgradeAndAdd的流程为：

a.根据新的编码方式调用intsetResize重新申请空间；

b.移动并扩容原来的元素；

c.根据新插入值是正数还是负数，将值插入相应的位置。

3）删除元素

代码语言：javascript复制

intset *intsetRemove（intset *is, int64_t value, int *success）

1）首先判断编码是否小于等于当前编码，若不是，直接返回。

2）调用intsetSearch查找该值是否存在，不存在则直接返回；存在则获取该值所在位置position。

3）如果要删除的数据不是该intset的最后一个值，则通过将position 1和之后位置的数据移动到position来覆盖掉position位置的值。

当集合元素都是整型并且元素不多时使用intset保存。并且元素按从小到大顺序保存。

（6）压缩列表（ziplist.c）

压缩列表ziplist本质上就是一个字节数组。Redis的ZSet、Hash和List都直接或者间接使用了压缩列表。

当ZSet或Hash的元素个数比较少，且元素都是短字符串时，Redis便使用压缩列表作为其底层数据存储结构。

结构图（字节数组，没有具体的结构体）：

代码语言：javascript复制

//zl指向zlbytes字段
#define ZIPLIST_BYTES(zl)       (*((uint32_t*)(zl)))

//zl 4指向zltail字段
#define ZIPLIST_TAIL_OFFSET(zl) (*((uint32_t*)((zl) sizeof(uint32_t))))

//zl zltail指向尾元素首地址；intrev32ifbe使得数据存取统一采用小端法
#define ZIPLIST_ENTRY_TAIL(zl)                                               ((zl) intrev32ifbe(ZIPLIST_TAIL_OFFSET(zl))) 

//zl 8指向zllen字段
#define ZIPLIST_LENGTH(zl)      (*((uint16_t*)((zl) sizeof(uint32_t)*2)))

//压缩列表最后一个字节即为zlend字段
#define ZIPLIST_ENTRY_END(zl)   ((zl) intrev32ifbe(ZIPLIST_BYTES(zl))-1)

压缩列表entry的编码结构：

previous_entry_length：表示前一个元素的字节长度，占1个或者5个字节，当前一个元素的长度小于254字节时，用1个字节表示；当前一个元素的长度大于或等于254字节时，用5个字节来表示。
encoding：表示当前元素的编码，即content字段存储的数据类型（整数或者字节数组），数据内容存储在content字段。

解码后的压缩列表元素使用结构体zlentry表示。

zlentry-结构体：

代码语言：javascript复制

typedef struct zlentry {
    unsigned int prevrawlensize;     // previous_entry_length字段的长度
    unsigned int prevrawlen;         // previous_entry_length字段存储的内容
    unsigned int lensize;            // encoding字段的长度
    unsigned int len;                // 元素数据内容的长度
    unsigned int headersize;         // 当前元素的首部长度
    unsigned char encoding;          // 数据类型
    unsigned char *p;                // 当前元素首地址
} zlentry;

基本操作：

函数名	说明
ziplistNew	创建压缩列表
ziplistInsert	插入元素；编码 -> 重新分配空间 -> 复制数据
ziplistDelete	删除元素；计算待删除元素的总长度 -> 数据复制 -> 重新分配空间
ziplistNext, ziplistPrev	遍历压缩列表，可后向遍历或前向遍历

当删除元素和插入元素时，可能会导致元素所需的存储长度发生变化，导致长度扩展，而每次扩展都将重新分配内存及数据复制，效率很低，这就是连锁更新问题。

1）创建压缩列表

代码语言：javascript复制

unsigned char *ziplistNew(void);

只需要分配初始存储空间11(4 4 2 1)个字节，并对zlbytes、zltail、zllen和zlend字段初始化即可

2）插入元素

代码语言：javascript复制

unsigned char *ziplistInsert(unsigned char *zl, unsigned char *p, unsigned char *s, unsigned int slen);

zl：压缩列表首地址；p：指向元素插入位置；s：数据内容；slen：数据长度

返回参数为压缩列表首地址

步骤：①将元素内容编码；②重新分配空间；③复制数据。

3）删除元素

代码语言：javascript复制

unsigned char *ziplistDelete(unsigned char *zl, unsigned char **p);

zl：指向压缩列表首地址；
*p：指向待删除元素的首地址（参数p同时可以作为输出参数）；

返回参数为压缩列表首地址。

步骤：①计算待删除元素的总长度；②数据复制；③重新分配空间。

4）遍历压缩列表

从头到尾（后向遍历）或者从尾到头（前向遍历）访问压缩列表中的每个元素。

代码语言：javascript复制

//后向遍历
unsigned char *ziplistNext(unsigned char *zl, unsigned char *p);
//前向遍历
unsigned char *ziplistPrev(unsigned char *zl, unsigned char *p);

会出现连锁更新，连锁更新实现逻辑：

（7）快速链表（quicklist.c）

在Redis 3.2 之前，Redis采用压缩列表（ziplist）以及双向链表（adlist）作为List的底层实现。当元素个数比较少并且元素长度比较小时，Redis采用ziplist作为其底层存储；当任意一个条件不满足时，Redis采用adlist作为底层存储结构。

在Redis 3.2 引入quicklist作为List的底层存储结构，是adlist与ziplist的组合。

quicklist是一个双向链表，链表中的每个节点是一个ziplist结构。

quicklist-结构体：

代码语言：javascript复制

typedef struct quicklist {
    quicklistNode *head;        // 指向quicklist的头节点
    quicklistNode *tail;        // 指向quicklist的尾节点
    unsigned long count;        // 元素的总数
    unsigned long len;          // 节点的个数
    int fill : 16;              // 每个quicklistNode中ziplist长度
    unsigned int compress : 16; // 两端各有compress个节点不压缩
} quicklist;

compress：当quicklistNode节点个数较多时，但经常需要访问的是两端的数据，为了进一步节省空间，Redis允许对中间的quicklistNode节点进行压缩。通过修改参数compress参数，可以指定两端各有compress个节点不压缩，即中间的 (len-compress) 个节点会进行压缩。

quicklistNode节点-结构体：

代码语言：javascript复制

typedef struct quicklistNode {
    struct quicklistNode *prev;   // 指向前一个节点
    struct quicklistNode *next;   // 指向后一个节点
    unsigned char *zl;        // 该节点对应的ziplist结构
    unsigned int sz;              // ziplist结构的大小
    unsigned int count : 16;      // ziplist的元素大小
    unsigned int encoding : 2;    // 采用的编码方式
    unsigned int container : 2;   // zl指向的容器类型：1代表none，2代表使用ziplist存储数据
    unsigned int recompress : 1;  // 代表这个节点之前是否是压缩节点
    unsigned int attempted_compress : 1;  // 测试时使用
    unsigned int extra : 10;    // 预留
} quicklistNode;

为了进一步降低ziplist所占用的空间，Redis允许对ziplist进一步压缩，Redis采用的压缩算法是LZF，压缩过后的数据可以分成多个片段，每个片段有2部分：一部分是解释字段，另一部分是存放具体的数据字段。

LZF数据压缩的基本思想是：数据与前面重复的，记录重复位置以及重复长度，否则直接记录原始数据内容。

但是，使用时需要对数据进行解压缩。

基本操作：

函数名	说明
quicklistCreate	初始化
quicklistPushHead, quicklistPushTail	在头部或者尾部进行插入
quicklistDelIndex, quicklistDelRange	删除指定位置, 指定区间的元素
quicklistReplaceAtIndex	更改元素；先删除原有元素，之后插入新的元素
quicklistIndex, quicklistGetIteratorAtIdx	查找指定位置元素；迭代器遍历查找

1）初始化

初始化是构建quicklist结构的第一步，由quicklistCreate函数完成，该函数的主要功能就是初始化quicklist结构

代码语言：javascript复制

quicklist *quicklistCreate(void) {
    struct quicklist *quicklist;               //声明quicklist变量
    quicklist = zmalloc(sizeof(*quicklist));   //为quicklist申请空间
    quicklist->head = quicklist->tail = NULL;  //初始化quicklist结构体变量
    quicklist->len = 0;
    quicklist->count = 0;
    quicklist->compress = 0;
    quicklist->fill = -2;                      //从表7-1中可知, ziplist大小限制是8KB
    return quicklist;
}

2）添加元素

添加元素是数据结构操作的第一步。quicklist提供了push操作，对外接口为quicklistPush，可以在头部或者尾部进行插入，具体的操作函数为quicklistPushHead与quicklistPushTail。

3）删除元素

quicklist对于元素删除提供了删除单一元素以及删除区间元素2种方案。

对于删除单一元素，我们可以使用quicklist对外的接口quicklistDelEntry实现，也可以通过quicklistPop将头部或者尾部元素弹出。

对于删除区间元素，quicklist提供了quicklistDelRange接口，该函数可以从指定位置删除指定数量的元素。

4）更改元素

quicklist更改元素是基于index，主要的处理函数为quicklistReplaceAtIndex。其基本思路是先删除原有元素，之后插入新的元素。quicklist不适合直接改变原有元素，主要由于其内部是ziplist结构，ziplist在内存中是连续存储的，当改变其中一个元素时，可能会影响后续元素。故而，quicklist采用先删除后插入的方案。

5）查找元素

quicklist查找元素主要是针对index，即通过元素在链表中的下标查找对应元素。基本思路是，首先找到index对应的数据所在的quicklistNode节点，之后调用ziplist的接口函数ziplistGet得到index对应的数据

（8）紧凑列表（listpack.c）

Redis 设计 listpack 的目的就是取代 ziplist。因为ziplist 在极小的概率下有可能发生级联更新，当连续规模较大的级联更新发生时，对 Redis 的性能有比较大的影响。

结构图（字节数组，没有具体的结构体）：

Total Bytes：整个listpack的空间大小，占用4个字节，每个listpack最多占用4294967295Bytes。
Num Elem：listpack中的元素个数，即Entry的个数，占用2个字节。
End为listpack：结束标志，占用1个字节，内容为0xFF。
Entry：每个具体的元素。

代码语言：javascript复制

// Total Bytes，整个listpack的空间大小
#define LP_HDR_SIZE 6
// Num Elem，listpack中的元素个数
#define LP_HDR_NUMELE_UNKNOWN UINT16_MAX

// Entry中的标志
#define LP_MAX_INT_ENCODING_LEN 9
#define LP_MAX_BACKLEN_SIZE 5
#define LP_MAX_ENTRY_BACKLEN 34359738367ULL
#define LP_ENCODING_INT 0
...

// End，结束标志
#define LP_EOF 0xFF

相比于 ziplist 的定义，它有两点改动：

记录的长度不再是前一个节点的长度，而是自己的长度。
将记录自己的长度放到了节点的尾部。

优点：

不再需要 zltail_offset 属性也可以快速定位到最后一个节点。用listpac 的总长度-最后一个节点的长度.
每个节点记录自己的长度，当本节点的值发生了改变，只需要更改自己的长度即可。不再需要更改别的节点的属性，也就彻底的解决掉了级联更新问题。

listpack 在 5.0 版本引入，但是由于 ziplist 在 Reids 内部的使用太过于广泛，有一些兼容问题，但在5.0 版本引入的 Stream 数据结构中，就使用了 listpack 而不是 ziplist。

虽然该结构查询效率低，并且只适合于末尾增删，但消息流中，通常只需要向其末尾增加消息，故而可以采用该结构。

基本操作：

函数名	说明
lpNew	初始化
lpInsert	增删改操作；增-任意位置插入; 删-空元素替换; 改-替换操作
lpFirst, lpLast, lpNext, lpPrev	遍历相关操作
lpGet	读取元素

（8）基数树（rax.c）

radix tree(基数树)（也叫基数特里树或压缩前缀树）是一种数据结构，是一种更节省空间的Trie（前缀树）。

rax 是基数树的一种实现，rax中不仅可以存储字符串，同时还可以为这个字符串设置一个值，也就是key-value。

如果一个中间节点有多个子节点，那么路由键就只是一个字符。如果只有一个子节点，那么路由键就是一个字符串。后者就是所谓的「压缩」形式，多个字符压在一起的字符串。

A. Rax树-结构体：

代码语言：javascript复制

typedef struct rax {
    raxNode *head;
    uint64_t numele;
    uint64_t numnodes;
} rax;

B. raxNode节点-结构体：

代码语言：javascript复制

typedef struct raxNode {
    uint32_t iskey:1;     // 该节点是否包含key
    uint32_t isnull:1;    // 是否存储value
    uint32_t iscompr:1;   // 是否压缩
    uint32_t size:29;     // 孩子节点数量，或压缩字符串的长度
    unsigned char data[];
} raxNode;

基本操作：

函数名	说明
raxNew	初始化
raxFind	查找长度为len的字符串s(key) 对应的value
raxInsert, raxTryInsert	向rax中插入key-value对，覆盖或者不覆盖原有的value
raxRemove, raxFree, raxFreeWithCallback	删除rax中的某个key，或释放整个rax，可设置释放回调
raxStart, raxSeek, raxNext, raxPrev, raxStop, raxEOF	遍历相关的操作

初始化：raxNew

代码语言：javascript复制

rax *raxNew(void) {
    rax *rax = rax_malloc(sizeof(*rax)); //申请空间
    rax->numele = 0;                     //当前元素个数为0
    rax->numnodes = 1;                   //当前节点个数为1
    rax->head = raxNewNode(0,0);         //构造头节点
    return rax;
}

云数据库Redis® 数据结构存储

0 人点赞