redis数据结构

redis 数据结构

1 SDS 简单动态字符串

  • len 字段，O(1)获取长度，二进制安全
  • alloc 字段，分配的空间长度
  • flags sds类型
    • sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64，五种类型结构体灵活保存不同长度字符串
    • 取消内存对齐，进一步节省内存
  • buf数组，字节数组，不仅可以保存字符串，还能保存二进制数据

扩容规则

  • 新长度 < alloc - len: 无需扩容
  • 新长度 > alloc - len && 新长度 < 1MB: len=新长度 && alloc = 2*新长度
  • 新长度 > alloc - len && 新长度 < 1MB: len=新长度 && alloc = 1MB

2 ZipList 压缩列表

ZipList

  • zlbytes: 整个压缩列表占用内存字节数
  • zltail: 记录尾部节点距离起始地址字节数，即尾节点偏移量
  • zllen: entry节点数量
  • zlend: 尾部节点，固定值0xFF(255)
  • entry: 节点
    • prevLen: 前一个节点长度，便于从后往前遍历
      • 如果前一个entry节点长度小于254字节，则用一个字节保存
      • 如果前一个entry节点超过254字节，则当前节点的prevlen使用5个字节保存
    • encoding: 用于区分entry值的类型和长度，针对不同类型分配对应数据结构，节约内存
    • data: 节点实际存储数据，长度和类型由encoding字段控制

查找原理

  • 查找头尾节点：根据ziplist的头部zllen等即可O(1)得到
  • 查找非头尾节点：顺序遍历查找，O(n)

因此，ziplist适合在数据量较少时使用，不适合保存过多的元素。

连锁更新问题
ziplist在更新或新增节点时，如果空间不够是需要重新分配的，当新增的元素过大时，后导致后续节点的prevlen变动，
如果后续节点新的prevlen阈值大于254时会扩充为5个字节，极端情况下可能会导致后续元素的 prevlen 占用空间都发生变化，
从而导致连锁更新问题，导致每个元素都会重新分配空间，造成性能下降。

因此，ziplist不适合在大规模数据下使用，数据较少时即使是发生了连锁更新也是可以接受的

3 哈希表

渐进式rehash
为避免hash冲突过多导致哈系统中数据过多性能下降问题，哈希表会在满足特定条件时执行扩容，扩为原来的两倍大小。
为避免数据copy带来的巨大开销，redis采用了渐进式哈希思想，即在后续的增删改查时把相关的数据存储到新hash表中。

rehash触发条件
factor = 节点数量/hashTable大小

  • 当factor大于1等于，并且redis没有在执行bgsave或berewriteaof命令，即redis没有在执行RDB快照或AOF重写时
  • 当factor大于等于5，hash冲突过于严重，不管有没有在进行RDB快照或AOF重写都会强制执行rehash

4 SkipList跳表

跳表

查询过程

  • 先比较权重，如果目标节点权重比当前节点权重大，则访问该层下一节点
  • 如果目标节点权重与当前节点权重相等，则比较sds值，如果目标节点的sds值大于当前节点的sds值，则访问该层下一节点

新增节点层级

  • 创建节点时会生成一个0~1的随机数，当小于0.25时，则层数就会加一，直到大于0.25。因此有25%的概率升级层级
  • 新节点在第二层的概率为25%，第三层为25% * 25%，以此类推

为什么用跳表而不是红黑树等平衡树

  • 实现简单，跳表是链表+多级索引，插入删除只需要修改局部指针，不会像平衡树那样进行复杂的自旋
  • 性能和平衡树相近，可达O(log n)，代码实现更轻量
  • 更好的范围查询，多级索引+水平指针，不需要进行中序遍历
  • 内存占用更少，相对于红黑树要存储父节点、颜色、左右指针等额外信息，跳过整体内存可控

5 QuickList

QuickList

quicklist是一个双向链表，里面存储的是ziplist或listpack(高版本)，它结合了链表和ziplist 的优点：

  • ziplist连续，节省内存，但ziplist过大会带来性能问题如连锁更新
  • 双向链表使用非连续的内存，提高内存利用率

因此quicklist其实是把大的ziplist分割为多段小的ziplist，并通过双向链表连接，这样在内存利用与效率之间做了很好的平衡

6 ListPack

ListPack

  • 废除了prevlen，而是使用len字段保存自身节点的长度(encoding+data)，只要知道节点首尾指针就可得到完整节点
  • 彻底解决了连锁更新问题，因为每个节点的len都是自包含的，某个节点更新不会影响到其他节点

7 总结

总结

hash使用listpack和哈希表触发条件

  • hash-max-listpack-entries: 如果Hash中的字段数量 小于或等于 这个值, Redis会尝试使用Listpack作为编码,默认512
  • hash-max-listpack-value: 如果Hash中所有字段和值的长度都小于或等于这个值，Redis才会使用Listpack,默认64字节

set使用整数集合和哈希表触发条件

  • 存储值是整数
  • set-max-intset-entries, 最大元素数量小于此配置，默认512

不满足上述两个条件的都会使用哈希表,而且从Hash Table无法逆转回IntSet

zset使用listpack和skiplist触发条件

  • zset-max-listpack-entries: 如果Zset中的元素数量 小于或等于 这个值，Redis会尝试使用Listpack作为编码, 默认128
  • zset-max-listpack-value: 如果Zset中所有成员的长度都小于或等于这个值，Redis才会使用Listpack，默认64字节