redis

redis数据类型底层编码原理

Posted by CHuiL on March 27, 2019

redisObject

对象：redis中使用对象来表示键值对，底层结构都是redisObject

typedef struct redisObject {
    unsigned type:4; //对象类型，有五种
    unsigned encoding:4; //对应的编码方式
    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
                            * LFU data (least significant 8 bits frequency
                            * and most significant 16 bits access time). */
    int refcount; 
    void *ptr; //底层数据指针
} robj;

type有五种

  • REDIS_STRING 字符串对象
  • REDIS_LIST 列表对象
  • REDIS_HASH 哈希对象
  • REDIS_SET 集合对象
  • REDIS_ZSET 有序集合对象

encoding有8种

  • 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 跳跃表和字典

每种type都有至少两种不同的encoding； 键值对中个建总是字符串对象；

字符串对象

字符串对象的编码可以是 int 、 raw 或者 embstr 。

int

当字符为整数值时，使用int；如果使用浮点数会自动转为字符串；

embstr

当字符串长度小于等于44时，使用embstr；一次性申请redisObject和sdshdr结构的内存空间，并且是连续的，如下图； image

Raw

当字符串长度大于44时，使用raw；分别申请redisObject和sdshdr，内存上不连续；
image

两者的区别：

  • raw和embstr都是redisObject结构并且ptr指向一个sdshdr结构；但是具体的内存空间有区别
  • embstr申请和释放内存都只需要操作一次，而raw需要两次；
  • embstr字符串只是一个只读字符串,一个embstr字符串一旦被修改（如append)时,则会先转换为raw类型,然后再修改,之后也都一直是raw字符串.

列表对象

列表对象的编码可以是ziplist或者linkedlist.

ziplist

image

linkedlist

image
其中的stringObject表示的是一个字符串对象

压缩列表条件,以下两个条件必须同时满足:

  1. 列表对象保存的所有字符串元素的长度都小于64字节;
  2. 列表对象元素的数量小于512;

    这两个参数是可以修改的:list-max-ziplist-value和list-max-ziplist-entries

当两个添加其中之一不能满足时,则会发生编码转换,将ziplist转换为linkedlist

哈希对象

哈希对象的编码可以是ziplist和hashtable

ziplist

image

image

如上图，键总是在值得前面；查询也是遍历得到目标值

hashtable（底层就是字典）

image

键和值都是字符串对象；

压缩字典条件,两个条件必须同时满足

  1. 哈希对象保存的键值对字符串长度都小于64字节;
  2. 哈希对象保存的键值对总数小于512个.

这两个参数是可以修改的:hash-max-ziplist-value和hash-max-ziplist-entries

集合对象

集合对象编码使用intset和hashtable

intset

只包含整数的集合，底层为元素数组+数量+编码类型，对应不同范围的整数有不同的编码，如int16_t，32,64 ;

hashtable

如下图，使用哈希表，只存放键，值为NULL；

image

intset集合条件,必须两个同时满足

  1. 集合对象保存的都是整数值
  2. 集合对象保存的元素数量不超过512个.

这两个参数是可以修改的:set-max-ziplist-value和set-max-ziplist-entries

有序集合对象

编码使用ziplist和skiplist+dict

ziplist

image

压缩列表的目的就是为了节省内存，所以在数据量小的情况下是牺牲时间来换取内存空间的。

skiplist+dict

typedef struct zset{
    zskiplist *zsl;
    dict *dict;
}zset;

为什么要使用skiplist和dict ？ 如果考虑只使用skiplist，那么查询就会是O(logN); 如果只使用dict，那么zrank，zrange等命令就需要先取出所有元素排行在筛选，时间复杂度为O(NlogN) ，空间复杂度为O(N) dict中存放键和分数，skiplist中的节点有分值和sds;
image

ziplist编码的有序集合条件,必须两个同时满足

  1. 有序集合对象保存的元素的长度都小于64字节.
  2. 有序集合对象保存的元素数量不超过128个.

这两个参数是可以修改的:zset-max-ziplist-value和zset-max-ziplist-entries