Redis底层数据结构

1.SDS

简单动态字符串，是Redis所构建的一个抽象类型，主要有两个作用

• 默认的字符串保存方式
• 缓冲区（AOF的AOF缓冲区就使用它）

1.1 定义

struct sdshdr{
   int len; //记录buf数组中已使用字节的数量，是SDS的长度
   int free; //记录buf中未使用的字符串数量
   char buf[]; //用来保存字符串
}

1.2 SDS与C字符串区别

1. O(1)时间复杂度获取长度，也就是使用sdshdr->len属性获取
2. 杜绝缓冲区溢出，当进行字符串修改的时候，会先判断SDS的空间是否满足修改所需的要求，如果不满足，API自动将SDS的空间扩展至所需的大小，然后进行修改。
3. 减少了修改字符串重分配次数，使用了空间预分配和惰性空间释放两种优化策略。
4. 二进制安全，C字符串只能保存符合ASCII编码的文本数据，对字符串结尾的识别只有‘\0’，也就是说如果字符串buf数组包含'\0',那么而SDS是通过sdshdr->len来获取字符串长度。

空间预分配：当对SDS进行扩展的时候，程序不仅会为SDS分配所必须的空间，还会为SDS分配未使用的空间。

• 对SDS修改后，如果长度小于1MB,那么就会free属性就会分配和len属性同样大小的长度
• 对SDS修改后，如果长度大于1MB，那么会额外分配1MB的空间。

惰性空间释放：当需要缩点SDS字符长度的时候，不会立即释放空闲的字符串，而是会使用free记录起来。

2.链表

2.1 定义

每个链表节点由adlist.h/listNode定义

type struct listNode{
     struct listNode *prev;
     struct listNode *tail;
     void *value;
}listNode;

使用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) //节点值比对函数 
}

• 双端无环
• 获取长度是O(1)的
• 获取表头结点和表尾节点是O(1)的
• 多态：使用void*指针来保存节点值，并通过list结构的dup、free、match来保存不同的值。

3.字典

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

3.1 定义

//哈希表
typedef struct dicht{
     //用来保存 Entry 指针的数组
     dictEntry **table;
     //哈希表的大小
     unsigned long size;
     //哈希表的大小掩码，用于计算索引值, 总是等于size-1
     unsigned long sizemark;
     //该hash表的已有节点的数量
     unsigned long used;
}dicht 

typedef struct dictEntry{
     void *key;
     //val
     union{
          void *val;
          uint64_tu64;
          int64_ts64;
     } v;
     //hash冲突的时候，指向下个节点的指针
     struct dictEntry *next;
}

typedef struct dict{
     //类型特定函数，type包含了该类型的一些api
     dictType *type;
     //保存了穿给特定函数的可选参数
     void *privdata;
     //hash表的个数，ht[1]只有在ht[0] rehash的时候才会使用
     dictht ht[2];
     //rehash索引， 初始值为 -1
    	int hashidx;
}

3.2 哈希算法

通过哈希值和掩码来确定索引值。具体使用MurmurHash2算法来确定。

hash = dict->type->hashFunction(key); //获取key对应的hash值
index = hash & (dict->ht[x].sizemask); //获取索引值

3.3 哈希冲突

使用拉链发来存储，通过头插法来实现

3-4 rehash

在重新散列过程中，将ht[0]的数据rehash到ht[1]，在rehash过程是渐进式的，具体步骤如下：

• 为ht[1]分配空间
• 首先将hashidx=0，代表rehash开始
• 对于每个哈希表的hashidx位置，将其重新hash到ht[1]
• 全部rehash完成

问题一：为ht[1]分配多少空间？

1. 如果是扩展操作，那么应该是第一个大于等于ht[0].used*2的$2^n$
2. 如果是删除操作，那么应该是第一个大于等于ht[0].used的$2 ^ n$

问题二：rehash期间的哈希表操作？

增删改查操作会首先去ht[0]寻找，如果未找到那么去ht[1]寻找。新增的键值对都会保存到ht[1]里面，而ht[0]不再进行任何添加操作。

4.跳跃表

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

typedef struct zskiplistNode {
     struct zskiplistLevel{
          struct zskiplistNode *forward;
          unsigned int span;
     }level[];//节点的层
     double score;//节点的权重
     struct zskiplistNode *backward; //回退指针
     robj *obj;//成员对象
}zskiplistNode;

//用于管理节点
typedef struct zskiplist{
     struct zskiplistNode *head, *tail;
     unsigned long length;//节点的数量
     int level; //最大层数  
}

在生成节点的时候，会根据幂次定律随机生成一个介于1~31之间的值作为level层的大小，这也是层的高度。

当查找的时候，会按照下述步骤进行查找：

1. 首先从最高level的第一节点出发
2. 遍历该层的所有节点，该level节点的forward也就是下一节点大于target，那么就会下降一层
3. 下降完成后，继续操作2，直到找到为止

5.压缩链表

5.1 压缩列表组成

压缩列表是列表键和哈希键的底层实现之一。

zlbytes	zltail	zllen	entry1	entry2	….	zlend
记录整个压缩链表的所占字节数	记录链表表尾节点距离压缩链表的起始位置由多少字节	记录压缩链表的节点数量	节点1	节点2		标记压缩列表的末端

5.1 压缩列表节点Entry组成

previous_entry_length	encoding	content
记录压缩列表前一个节点的长度大小	此节点记录content属所保存的类型和长度	存放字节数组或者整数

previous_entry_length：我们可以通过zltail拿到尾部节点，然后尾节点地址减去前一个长度得到前一个节点的首部地址，以此类推，可以遍历整个列表。

encoding编码格式：

• 如果content存放的是节点数组，那么编码前两位为00,01,10
• 如果content存放的是整数，那么编码是以开头为11的整数编码

6.整数集合

6.1 内部结构

整数集合是集合键的底层实现之一，当一个集合只包含数值元素的时候，并且这个集合的元素数量不多时，才会使用整数集合存储。

typedef struct intset{
     //编码方式
     uint32_t encoding;
     //集合包含的元素数量
     uint32_t legth;
     //保存元素的数组，保存的元素真正取决于encoding属性的值
     int8_t contents[];
}

1. contents数组是整数集合的底层实现，整数集合的每个元素都是一个数组项，并且在数组中是按照从小到大的顺序有序排列

2. encoding主要是表示content数组所表示的值，主要有以下几种

3. INTSET_ENC_INT16 : 代表存储类型是int16_t

4. INTSET_ENC_INT32：代表存储类型是in32_t

5. INTSET_ENC_INT64：代表存储类型是int64_t

6.2 升级

如果当前的encoding编码的格式所支持的范围不能满足待插入元素大小，这个时候需要进行元素格式升级。

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2. 将底层数组现有元素换成新元素相同的类型，并将其放入到新的位置上。维持有序性
3. 将新元素添加到底层数组里面。（添加到哪里？

有趣的是，当发生升级时候，待插入元素的大小一定是大于所有现有元素或者小于所有元素的，所以第三步中新元素只能放在起始或者末尾位置，因此可以最后处理待插入元素。

还有就是注意到先整数集合添加元素的最坏时间复杂度为 $O(N)$

6.3 降级

不支持降级，一旦对数组进行升级，那么编码就会一直保持升级后的状态。

7.对象

上面几种介绍的底层数据结构是redis大部分的实现，但是真正和程序员打交道的是我们要说的对象，对象可以理解成对底层数据结构的再封装，Redis提供对象的一个好处就是，在不同的场景下为对象设置多种不同的数据结构实现，优化不同场景下的使用效率。

因此我们在set key value操作的时候，创建了两个对象： 键对象 和 值对象 。 键对象一般是字符串对象，而值对象主要包括物种常见对象。

7.1 对象结构

typedef struct redisObject{
     //类型
     unsigned type;
     //编码
     unsigned encoding;
     //指向底层数据结构的指针
     void *ptr;
     //引用计数
     int refcount;
     //对象空转时长:记录了对象最后一次命令程序访问的时间
     //可以配合回收算法进行allkeys-lru volatile-lru使用
     unsigned lru;
     //....
}robj;

7.1.1 对象类型

7.1.2 对象编码

7.1.3 常用API

type key //返回对象类型
object encoding key //返回对象编码类型

7.2 字符串对象

7.2.1 int 编码

如果保存的数值类型并且可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr。

7.2.2 raw 编码

如果保存的是字符串值，并且字符串长度大于32字节。那么需要一个SDS来保存。

7.2.3 embstr 编码

如果保存的是字符串值，并且字符串长度小于32字节。那么需要一个SDS来保存。

需要注意的是，raw和embstr的区别在于，在创建字符串对象的时候，raw格式需要调用两次内存分配空间函数，而embstr仅仅需要调用一次内存空间分配函数。释放也是如此。

7.3 列表对象

7.3.1 ziplist 编码

7.3.2 linkedlist 编码

注意到，字符串对象是 Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

7.4 哈希对象

7.4.1 ziplist编码

7.4.2 hashtable编码

7.5 集合对象

7.5.1 intset编码

7.5.2 hahstable编码

7.6 有序集合

7.6.1 ziplist编码

7.6.2 skiplist编码

7.7 内存共享

目前来说，Redis会在初始化服务器的时候，创建0-9999所有整数值的字符串对象，当需要使用的时候，服务器就会共享这些对象，而不是新建对象。

重要总结

1. Redis数据库中的每个键值对的键和值都是一个对象。
2. Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，对象所占用内存就会自动释放。
3. Redis会共享值为 0-9999的字符串对象
4. 对象会记录自己最后一次被访问的时间，可以用来计算空转时长。

---