源码实现

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根据长度判断结束的位置，从而解决二进制不安全的问题。

关注和赞赏都是对小欧莫大的支持！ 🤝 🤝 🤝
公众号

← 数据可靠性
动态负载 →