【从入门到放弃-Redis】redis底层数据结构和对象

简单动态字符串SDS

Redis 的默认字符串 替代C字符串

区别:

  • 通过len属性直接获取到长度
  • 杜绝缓冲区溢出,字符串拼接时会先检查sds的长度
  • 减少修改字符串时带来的内存冲分配次数,即空间预分配和惰性空间释放策略
    1、空间预分配:当sds被修改并需要扩容时,若len将小于1M(扩容后),扩展和len相同的free空间,若将大于1M 则扩展1M的free空间
    2、惰性空间释放:当sds被修改需求缩短时,并不回收多出来的内存,而是记在free属性中等待将来使用
    
  • 是二进制安全的,可以存空字符等
  • 兼容部分C字符串函数

    链表

    双向无环链表、带头尾指针、带长度计数器、每个节点支持多种数据类型
    由一个list结构和多个listNode结构组成

    字典

    使用哈希表作为底层实现,一个哈希表里可以有多个哈希节点,每一个哈希节点保存了字典中的一个键值对

rehash:当哈希表中的键值对太多或太少时,为了使哈希表的负载因子在一个合理的范围,会调整负载因子、表空间后进行重新散列

rehash条件

  • 服务器当前没执行BGSAVE或BGREWRITEAOF命令且哈希表的负载因子大于等于1
  • 服务器正在执行BGSAVE或BGREWRITEAOF命令且哈希表的负载因子大于等于5
    负载因子 = 哈希表已保存节点数量/哈希表大小
    load_factor = ht[0].used / ht[0].size

    渐进式rehash

    避免一次性、集中式的产生大量的运算对服务造成影响,每次在对字典进行增删改查时,会执行一个键值对的rehash工作。 新增的都会加在h1,查询会先查h0再查h1

    跳跃表

    只在两个地方用到,有序集合和集群节点中做内部数据结构
    由zskiplist和zskiplistNode两个结构组成,zskiplist用于保存跳跃表信息,而zskiplistNode用于表示跳跃表节点
    每个跳跃表节点的层高都是1~32直接的随机数
    同一个跳跃表中 多个节点可以包含相同的分值,但是每个几点的成员对象必须是唯一的
    跳跃表中的节点按照分支大小排序,当分值相同时,按照成员对象的大小排序

    整数集合

    用于保存整数值的集合,从小到大有序排列且不包含重复项

    升级

    当添加新元素时,新元素的类型比整数集合的现有元素的类型都长时,整数集合需要先升级 才能将新元素添加到整数集合里
  • 根据新元素类型,扩展整数集合底层数组的空间大小,并为新元素分配空间
  • 将底层数组现有的所有元素都转换成与新元素相同的类型,并将转换后的元素放到正确的位置
  • 将新元素添加到底层数组中
    升级的好处:提高灵活性可以适配多种整数类型,节约内存只在必要的时候升级
    整数集合不支持降级操作

    压缩列表

    当一个列表只包含少量列表项,且每个列表项不是小整数就是短字符串,则会使用压缩列表做列表的底层实现
    当一个哈希结构只包含少量键值对且键值对的键和值都是小整数或短字符串,也会使用压缩列表来做底层实现
    压缩列表是为了节约内存而开发的顺序型数据结构
    压缩列表可以包含多个节点,每个节点可以保存一个字节数组或整数值
    添加或删除节点可能会引发连锁更新,但出现的机率不高

    对象

    type属性表示redis的五种属性之一
    encoding属性表示底层对象实现所用的数据结构

    字符串对象

    编码可以是int、raw、embstr
    embstr专门用于保存短字符串的优化编码方式
    Int在修改为非int时,会变为raw
    embstr在修改时 会变为raw

    列表对象

    列表对象的编码可以是ziplist或linkedlist
    列表对象同时满足两个条件时,使用ziplist编码:
  • 列表对象保存的所有字符串元素都小于64字节
  • 列表对象保存的元素数量小于512个
    其它条件使用linkedlist编码
    可以使用list-max-ziplist-value和list-max-ziplist-entries选项修改

    哈希对象

    哈希对象的编码可以是ziplist或hashtable
    哈希对象同时满足两个条件时,使用ziplist编码:
  • 哈希对象保存的所有键值对的键和值的字符串都小于64字节
  • 哈希对象保存的键值对数量小于512个
    其它条件使用hashtable编码
    可以使用hash-max-ziplist-value和hash-max-ziplist-entries选项修改

    集合对象

    集合对象的编码可以是intset或hashtable
    intset编码的集合对象是使用整数集合作为底层实现,集合对象包含的所有元素都被保存在整数集合里
    Hashtable 编码的集合对象使用字典作为底层实现,每个字典的每个键都是一个字符串对象,每个字符串对象包含了一个集合元素,字典的值全被设为null
    当集合对象可以同时满足以上两个条件时,对象使用intset编码
  • 集合对象保存的所有元素都是整数值
  • 集合对象保存的元素数量不超过512个
    其它情况使用hashtable
    可以使用set-max-intset-entires选项设置

    有序集合对象

    有序集合使用ziplist或skiplist
    ziplist编码的有序集合底层使用压缩列表作为底层实现,每个集合元素使用两个紧挨着的压缩列表节点保存,第一个节点保存元素的成员,第二个节点保存元素的分值
    压缩列表内的集合按分值从小到大排列
    skiplist编码的有序集合使用zset结构作为底层实现,一个zset结构包含一个字典和一个跳跃表
    zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素,每个跳跃表节点都保存了一个集合元素,跳跃表节点的object属性保存了元素的成员,score属性保存了元素的分值
    。通过这个跳跃表,程序可以对有序集合进行范围查找
    此外,zset结构中的dict字典还保存了一个从成员到分值的映射,字典的键保存元素的成员,值使用double类型保存分值
    当有序集合对象同时满足以下两个条件时,使用ziplist编码:
  • 有序集合保存的元素数量小于128个
  • 有序集合保存的所有元素成员长度都小于64字节
    其它条件使用skiplist编码
    可以使用zset-max-ziplist-entires和zest-max-ziplist-value选项设置

    类型检查与命令多态

    reids中用于操作键的命令基本可以分为两种:
  • 可以对任何类型的键执行,如DEL,EXPIRE,RENAME,TYPE,OBJECT
  • 只能对特定类型的键执行,如SET,GET,APPEND,STRLEN等只能对字符串键执行

    类型检查的实现

    在执行一个命令之前,redis会对输入键的类型做检查,通过redisObject结构的type属性来实现

    多态命令的实现

    redis会根据值对象的类型来判断键是否能执行指定命令之外,还会根据值对象的编码方式,选择正确的命令实现代码来执行命令
    DEL,EXPIRE和LLEN等命令的区别在于前者是基于类型的多态-一个命令可以同时用于处理多种不同类型的键,后者是基于编码的多态-一个命令可以同时处理多种不同编码

    内存回收

    通过引用计数的方式
  • 创建一个新对象时:饮用计数的值会被初始化为1
  • 当对象被一个新程序使用时,引用计数的值加一
  • 对象不再被一个程序使用时,引用计数的值减一
  • 对象的引用计数值为0时,对象所占用的内存会被释放

    对象共享