redis设计与实现-总结

链表

实现

总结

链表在redis应用非常广泛，比如当列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串，redis就会使用链表作为列表键的底层实现

链表的实现总结如下

字典

结构

dict结构

该结构中的type定义了特定类型键值对的函数，trehash定义了是否正在rehash，因为redis的rehash是渐进式的，渐进式的hash要操作2个dictht结构

dictEntry

分键值对和(next)指向下一个节点的指针(用于解决键的冲突)

dictht

又dictEntry的数组，还有哈希表的大小，用于hash的sizemask,和节点数量

hash算法

哈希表的扩展和收缩

或者负载因子小于0.1系统会自动收缩

总结

跳跃表

跳跃表按照分值来进行排序，所以基本redis只有有序列表和内部数据采用这个结构

跳跃表节点

跳跃表

typedef struct zskiplist {
//指向跳跃表的表头和表尾
structs zkiplistNode *header, *tail;
//节点数量
unsigned long length;
//最大节点的基数
int level;
}

总结

整数集合

其中encoding表示其contents数组中保存的数据大小，而不是根据int8_t来代表数据大小，因为c中的数组本质就是一个指针，然后整数集合会自动触发升级，也就是将int8_t升级成int16_t，升级的好处就是可以很灵活，当想要大的数据就进行扩容然后再存入，然后就是节约内存，因为当要大的数据时候才会扩容，小数据的时候就使用小的数据结构

总结

压缩列表

www.cnblogs.com/hunternet/p…

总结

压缩列表就是类似数组，但是本身结构存储了自身的长度和其他信息，结尾有个0xff来表示结尾，然后中间的数据都有自己的长度标识，其中previous_entry_length用来标识前一个数据的长度，encoding用来标识本身数据的长度，其中以11开始标识是整数型，而01 00 10用来标识字节数组，后续的位用来表示长度，content用来表示内容

  • 压缩列表是Redis为节约内存自己设计的一种顺序型数据结构。

  • 压缩列表被用作列表键和哈希键的底层实现之一。

  • 压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值。

  • 添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高

对象

redis不是直接拿上面提到的数据结构来实现键值对数据库，而是创建了一个对象系统，用上面的数据结构来组成

类型

可以使用type命令查看其键的值的类型，比如type price

编码

可以使用object encoding命令查看键的值的编码，比如object encoding price

字符串对象

  1. 字符串对象可以用int, raw和embstr来编码，

  2. 当设置的key是number的时候就会使用int编码，但是当变为字符串的时候就会选择使用embstr或者raw来进行编码，字符串的长度大于32字节的时候会选择raw

  3. 而embstr和raw的区别是，raw是sds结构，内存分配的时候会分配2次，一次给redisObject另一次给sdshdr结构，而embstr分配一次将2个结构放在同一块内存中，embstr分配次数会少，释放对应也少，然后两个结构的内存有连续性可以更好的利用缓存

  4. 可以用long double类型标识浮点数作为redis的字符串的值来保存，一般再进行浮点数运算的时候，将字符串类型的浮点数和浮点数进行计算会自动转化位long duuble计算完了后又会存入字符串

  5. embstr一般都是只读的，在修改后会直接变成raw然后进行修改

列表对象

列表对象由ziplist或者linkedlist编码

ziplist

linkedlist

linkedlist会嵌套redis的StringObject对象

编码转化

同时满足一下两个条件的时候列表使用ziplist编码

  1. 列表对象的所有字符串元素的长度都小于64字节

  2. 列表对象保存的元素数量小于512个

    我们知道ziplist会有连锁更新问题，但是因为redis这里限制了数量和大小所以触发的连锁更新并不会消耗很多性能

hash对象

哈希对象使用ziplist或者hashtable来编码

ziplist

hashtable

编码转换

当满足两个条件时，哈希对象使用ziplist编码

  1. 哈希对象保存的所有键值对字符串长度都小于64字节

  2. 键值对数量小于512个

集合对象

集合对象的编码可以是intset或者hashtable

当集合对象都是整数值，而且数量小于512个就会使用intset编码

有序集合对象

有序集合编码可以是ziplist或者skiplist

ziplist

skiplist

当使用skiplist编码的时候是会使用zset结构，该结构包含了skiplist和字典来实现，因为字典可以很快定位成员的分值，但是做区间计算的时候无法进行只能进行排序后获取，而skiplist作为支持有序集合查找和范围操作尽可以快的执行，所以redis使用字典和跳跃表来实现有序集合

转换

当元素数量小于128个，且成员的长度都小于64字节的时候使用ziplist

垃圾回收

因为c语言不具备内存回收功能，所以redis自己实现了一套引用计数的回收机制

对象共享

在回收机制之外，因为引入了对象引用计数的机制，然后对象可以在2个键中进行共享，当他们的值相同的时候他们的值可以指向同一块内存

对象的空转市场

redisObject中除了上面提到的对象还有lru这个属性，该属性记录了最后一次命令访问的时间，该空转时长还有另外一项作用，就是服务器设定了某种内存回收机制，就是当内存超过了maxmemory，空转时长比较高的那部分会优先丢弃从而回收内存

以上是 redis设计与实现-总结 的全部内容， 来源链接： utcz.com/a/27241.html

回到顶部