浅谈Redis之底层数据结构

浅谈Redis之底层数据结构

Tans 1,901 2022-04-04

Redis底层数据结构

1.SDS

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

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

1.1 定义

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

image-20220404143608719

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 定义

image-20220404143626432

每个链表节点由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;
}

image-20220404143646307

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*22n2^n
  2. 如果是删除操作,那么应该是第一个大于等于ht[0].used2n2 ^ n

问题二:rehash期间的哈希表操作?

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

4.跳跃表

跳跃表由redis.h/zsiplistNoderedis.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; //最大层数  
}

image-20220404111306337

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

当查找的时候,会按照下述步骤进行查找:

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

5.压缩链表

5.1 压缩列表组成

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

image-20220404123158075

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

5.1 压缩列表节点Entry组成

image-20220404124031431

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

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

image-20220404123831927

encoding编码格式:

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

image-20220404123240702

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)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 对象类型

image-2022040413412646

7.1.2 对象编码

image-20220404134347975

image-20220404134423447

7.1.3 常用API

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

7.2 字符串对象

7.2.1 int 编码

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

image-20220404135248550

7.2.2 raw 编码

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

image-20220404135405490

7.2.3 embstr 编码

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

image-20220404140607362

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

7.3 列表对象

7.3.1 ziplist 编码

image-20220404140700099

7.3.2 linkedlist 编码

image-20220404140714253

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

7.4 哈希对象

7.4.1 ziplist编码

image-20220404141304686

7.4.2 hashtable编码

image-20220404141327597

7.5 集合对象

7.5.1 intset编码

image-20220404141501717

7.5.2 hahstable编码

image-20220404141512460

7.6 有序集合

7.6.1 ziplist编码

image-20220404141756600

7.6.2 skiplist编码

image-20220404141828174

7.7 内存共享

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

重要总结

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