Redis对象底层数据结构

Redis对象底层数据结构

编码常量 编码所对应的底层数据结构
REDIS_ENCODING_INT long 类型的整数
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表

Redis string类型转换

 我们可能以为Redis在内部存储string都是用sds的数据结构实现的,其实在整个Redis的数据存储过程中为了提高性能,内部做了很多优化。整体选择顺序应该是:

  • 整数,存储字符串长度小于21且能够转化为整数的字符串。

  • EmbeddedString,存储字符串长度小于39的字符串(REDIS_ENCODING_EMBSTR_SIZE_LIMIT)。

  • SDS,剩余情况使用sds进行存储。

embstr和sds的区别在于内存的申请和回收

  • embstr的创建只需分配一次内存,而raw为两次(一次为sds分配对象,另一次为RedisObject分配对象,embstr省去了第一次)。相对地,释放内存的次数也由两次变为一次。
  • embstr的RedisObject和sds放在一起,更好地利用缓存带来的优势
  • 缺点:Redis并未提供任何修改embstr的方式,即embstr是只读的形式。对embstr的修改实际上是先转换为raw再进行修改。

Redis list数据结构

 Redis list数据结构底层采用压缩列表ziplist或linkedlist两种数据结构进行存储,首先以ziplist进行存储,在不满足ziplist的存储要求后转换为linkedlist列表。

当列表对象同时满足以下两个条件时,列表对象使用ziplist进行存储,否则用linkedlist存储。

  • 列表对象保存的所有字符串元素的长度小于64字节
  • 列表对象保存的元素数量小于512个。

Redis hash底层存储结构

Redis的哈希对象的底层存储可以使用ziplist(压缩列表)和hashtable。当hash对象可以同时满足一下两个条件时,哈希对象使用ziplist编码。

  • 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
  • 哈希对象保存的键值对数量小于512个

Redis的hash架构就是标准的hashtab的结构,通过挂链解决冲突问题。

Redis set底层存储

Redis的集合对象set的底层存储结构特别神奇,底层使用了intset和hashtable两种数据结构存储的,intset我们可以理解为数组,hashtable就是普通的哈希表(key为set的值,value为null)。是不是觉得用hashtable存储set是一件很神奇的事情。

 set的底层存储intset和hashtable是存在编码转换的,使用intset存储必须满足下面两个条件,否则使用hashtable,条件如下:

  • 结合对象保存的所有元素都是整数值
  • 集合对象保存的元素数量不超过512个

zset底层存储结构

 zset底层的存储结构包括ziplist或skiplist,在同时满足以下两个条件的时候使用ziplist,其他时候使用skiplist,两个条件如下:

  • 有序集合保存的元素数量小于128个
  • 有序集合保存的所有元素的长度小于64字节

当ziplist作为zset的底层存储结构时候,每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员,第二个元素保存元素的分值。

当skiplist作为zset的底层存储结构的时候,使用skiplist按序保存元素及分值,使用dict来保存元素和分值的映射关系。

Redis为何要定义字符串为SDS

Redis是底层使用的是C语言,在C语言中没有字符串这种数据类型,字符串大都是通过字符数组实现的,但是使用字符数组有以下不足:

  1. 字符数组的长度都是固定,容易发生空指针异常
  2. 获取字符数组的长度的时候需要遍历数组,时间复杂度高
  3. 字符数组长度发生改变之后需要重新分配内存
  4. 使用\0表示结尾,在存储二进制会出现问题。
//动态字符串,数组的长度是可变的。
struct sdshdr {
    unsigned int len;//记录当前串的长度。
    unsigned int free;//记录剩余的有效长度。
    char buf[];//真正的字符串位置。
};

Redis就自己实现了SDS来解决上面的问题,SDS相对C字符串数组的优点:

  • 长度达到一定标准会有相应的扩容(小于1M,free增加len,大于1M,每次增加1M),从而解决内存溢出的问题。
  • 在SDS的内部定义了字符串的长度,使用时可以直接获取,复杂度O(1),解决获取长度时间复杂度高的问题。
  • SDS是空间预分配,惰性释放内存的,从而减少分配内存的次数
  • SDS根据长度判断结束的位置,从而解决二进制不安全的问题。

Redis对象底层数据结构
https://blog.puresai.com/2021/03/23/source/
作者
puresai
许可协议