Redis底层数据结构
Redis 底层数据结构一共6种
- SDS
- Linked List
- Dict
- Skip List
- 整数集合
- 压缩列表
SDS 简单动态字符串
数据结构
- len 已使用字节
- free 未使用字节
- buf 字节数组
对比C字符串，SDS的优点
获取字符串长度为 O(1) 复杂度；通过len即可获取。
杜绝缓冲区溢出
减少修改字符串带来的内存重分配次数
二进制安全；SDS对存放在buf数组的数据，不会做任何限制、过滤、或者假设，数据在写入时是什么样，它被读取时就是 什么样。
针对缓冲区溢出和内存重分配的问题，Redis为SDS设计了两种内存分配策略。
1. 空间预分配；对SDS修改后的长度小于1MB，那么分配free = len，如果长度大于等于1MB，free = 1MB 2. 惰性空间释放；用于优化SDS的字符串缩短操作，当缩短SDS保存的字符串时，并补立即回收多出来的字节，而是放到free记录下来，等待使用
双端链表
listNode 链表节点数据结构
- prev 前置节点
- next 后置节点
- value 节点的值
list 链表数据结构
- head 表头节点 listNode 对象
- tail 表尾节点 listNode 对象
- len 链表包含的节点数量
- dup 节点值复制函数
- free 节点值释放函数
- match 节点值对比函数
特性总结
- 双端
- 无环：表头节点的prev指针和表尾节点的next指针都指向null，对链表的访问以null为终点
- 带表头指针和表尾指针，通过list的head和tail指针，程序获取链表的表头节点和表尾节点复杂度为O(1)
- 多态：链表可保存各种不同类型的值
广泛应用于实现Redis的各种功能，比如列表键、发布与订阅、满查询、监视器等。
字典
由哈希表作为底层实现。
哈希表数据结构
- table 哈希表数组 由哈希表节点组成
- size 哈希表大小
- sizemask 哈希表大小掩码，用于计算索引值
- used 该哈希表已有节点的数量
哈希表节点数据结构
- key 键
- value 值
- next 指向下一个哈希表节点，形成链表
字典数据结构
- type 类型特定函数
- privdate 私有数据
- ht[2] 哈希表 包含两个哈希表，ht[0]是字典使用的，ht[1]是rehash时使用
- rehashidx rehash 索引，当没有进行rehash时，=-1
rehash
随着操作的不断执行，哈希表需要维护负载因子在一个合理的范围，因此需要对哈希表的大小进行相应的扩展或者收缩。
步骤
简单来说就是由ht[0]向ht[1]迁移，释放ht[0]，再将ht[1]设置为ht[0]，同时重新为ht[1]创建一个空白哈希表，为下一次rehash做准备。
rehash时机
当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
（1）服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1；
（2）服务器目前正在执行BGSAVE命令或则BGREWRITEAOF命令，并且哈希表的负载因子大于等于5；
负载因子的计算公式：
load_factor = ht[0].used / ht[0].size
另外，
当负载因子小于0.1时，程序开始自动对哈希表执行收缩操作。
渐进式rehash
在上述rehash的过程中，迁移并不是一次性、集中式完成的，而是分多次、渐进式地完成的。
- 为 ht[1] 分配空间，让字典同时持有 ht[0] 和 ht[1] 两个哈希表；
- 在字典中维持一个索引计数器变量 rehashidx，并将它的值设置为0，表示 rehash 工作正式开始；
- 在 rehash 进行期间，每次对字典执行天假、删除、查找或者更新操作时，程序出了执行指定的操作以外，还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1]，当 rehash 工作完成之后，程序将rehashidx 属性的值+1；
- 随着字典操作的不断执行，最终在某个时间点上，ht[0] 的所有键值对都会被 rehash 至 ht[1]，这时程序将 rehashidx 属性的值设置为 -1，表示 rehash 操作已完成。
跳表
它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。平均查找O(logN)
用途
- 实现有序集合键
- 集群节点中用作内部数据结构
跳表数据结构
- header 表头节点
- tail 表尾节点
- level 目前跳表内，层数最大的节点层数（不包含表头节点）
- length 跳表长度，包含的节点数量（不包含表头节点）
跳表节点数据结构
- level 代表节点层次，有两个属性：前进指针和跨度。前进指针用于访问位于尾表方向的其他节点，跨度记录了前进指针所指向节点和当前节点的距离
- backward 后退节点，程序从表尾向表头遍历时使用
- score 节点按分值从小到大排列
- obj 节点保存的成员对象
层
跳表节点的level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针
前进指针
用于表头向表尾访问
跨度
- 两个节点之间的跨度越大，他们相距的就越远
- 指向null的所有前进指针的跨度都为0
跨度是用来计算排位的，在查找某个节点的过程中，将沿途访问过的所有层的跨度累加起来，得到的结果就是目标节点在跳表中的排位
后退指针
用于从表尾向表头方向访问节点，每次只能后退至前一个节点
分值和成员
节点的分值是一个double类型的浮点数，跳表中的所有节点都按分值从小到达排序
节点的成员对象是一个指针，指向一个字符串对象，而字符串对象保存一个SDS值
同一个跳表中，对象必须是唯一的，但多个节点保存的分值是可以相同的。
整数集合
整数结合是集合键的底层实现之一，当一个集合只包含整数值元素，并且这个集合元素数量不多时，Redis就会使用整数集合作为集合键的底层实现。
数据结构
- encoding 编码方式
- length 集合包含的元素数量
- contents 保存元素的数组
contents数组是整数集合的底层实现：整数集合的每个元素都是contents数组的一个数组项，各个项在数组中按值的大小从小到大有序排列，并且数组中不包含任何重复项
升级
每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到整数集合里面
升级步骤：
- 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
- 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
- 将新元素添加到底层数组里面。
所以添加新元素的复杂度为O(N)
升级的好处
- 提升整数集合的灵活性；C语言是静态类型，不同类型的值通常不会放在同一个数据结构里
- 尽可能的节约内存；
降级
不支持！
压缩列表
是列表键和哈希键的底层实现之一。
- 当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现
- 当一个哈希键只包含量少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现
压缩列表数据结构
- zlbytes 记录占用的内存字节数，在对压缩列表进行内存重分配，或者计算zlend的位置时使用
- zltail 记录表尾节点距离起始节点的地址有多少个字节
- zllen 记录包含的节点数量；<UINT16_MAX（65535）时，这个属性的值就是压缩列表的节点数量，当这个值=UINT16_MAX时，需要遍历整个压缩列表才能计算得出
- entryX 各个节点，节点的长度由节点保存的内容决定
- zlend 特殊值 0xFF（十进制255），用于标记压缩列表的末端
压缩列表节点的数据结构
previous_entry_length 记录压缩列表中前一个节点的长度，它的长度可以是1字节或者5字节；
- 如果前一个节点的长度小于254字节，那么该属性长度为1字节：前一节点的长度就保存在这里；
- 如果前一个节点的长度大于等于254字节，那么该属性的长度为5字节：其中属性的第一字节会设置为0xFE（十进制值254），而之后的四个字节则用于保存前一节点的长度
encoding 记录节点的content属性所保存数据的类型以及长度
- 1字节、2字节或则5字节长，值的最高位为00、01、10的时字节数组编码
- 1字节长，值的最高位以11开头的时整数编码
content 保存节点的值，值得类型和长度由节点的encoding属性决定
每个压缩列表节点可以保存一个字节数组或者一个整数值