读书笔记-Redis设计与实现-数据结构

1.SDS（Simple Dynamic String，简单动态字符串）

• SDS获取字符串长度复杂度为O(1)，C字符串为O(N)
  • SDS额外保存了一个len字段用于记录字符串长度，因此可以直接获取
  • C字符串需要遍历整个字符串，直到遇到空字符为止
• SDS可以防止字符串缓冲区溢出，C字符串不能
  • C由于不记录自身长度，因此每次增加字符串长度时，会假设内存已经分配，如果假设不成立，就会溢出
  • SDS额外保存了一个free字段用于记录剩余内存空间，不足时会先进行空间扩展
• SDS可以减少修改字符串时带来的内存重分配次数
  • SDS的free字段帮助实现了空间预分配和惰性空间释放两种优化策略
• SDS可以处理二进制数据，C字符串不能
  • 原因是C字符串的最后一位是空字符，且C语言通过空字符判断字符串的结束，导致某些包含空字符格式的数据无法正确处理
  • SDS虽然也保留了最后一位空字符的特性，但是通过len属性判断字符是否结束，因此可以保存各种数据
• SDS保留最后一位空字符特性的好处是可以直接调用某些C字符串函数

2.链表

• 链表被广泛用于实现Redis的各种功能，比如列表键、发布与订阅、慢查询、监视器等
• 每个链表节点由一个listNode结构来表示，每个节点都有一个指向前置节点和后置节点的指针，所以Redis的链表实现是双端链表
• 每个链表使用一个list结构来表示，这个结构带有表头节点指针、表尾节点指针，以及链表长度等信息
• 因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL，所以Redis的链表实现是无环链表
• 通过为链表设置不同的类型特定函数，Redis的链表可以用于保存各种不同类型的值

3.字典

• Redis底层数据库由字典实现
• 也可作为redis哈希键的实现
• 字典被广泛用于实现Redis的各种功能，其中包括数据库和哈希键。
• Redis中的字典使用哈希表作为底层实现，每个字典带有两个哈希表，一个平时使用，另一个仅在进行rehash时使用。
• 当字典被用作数据库的底层实现，或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。
• 哈希表使用链地址法来解决键冲突，被分配到同一个索引上的多个键值对会连接成一个单向链表。
• 在对哈希表进行扩展或者收缩操作时，程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面，并且这个rehash过程并不是一次性地完成的，而是渐进式地完成的。

4.跳跃表（skiplist）

• Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构
• Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成，其中zskiplist用于保存跳跃表信息（比如表头节点、表尾节点、长度），而zskiplistNode则用于表示跳跃表节点
• 每个跳跃表节点的层高都是1至32之间的随机数
• 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的成员对象必须是唯一的
• 跳跃表中的节点按照分值大小进行排序，当分值相同时，节点按照成员对象的大小进行排序

5.整数（intset）

• 整数集合是集合键的底层实现之一
• 整数集合的底层实现为数组，这个数组以有序、无重复的方式保存集合元素，在有需要时，程序会根据新添加元素的类型，改变这个数组的类型
• 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存
  • 类型为int16_t、int32_t或者int64_t的整数值，默认按照能存下当前数组的最小类型存储
  • 当新的元素比当前存储的整数类型要大时，进行类型升级，同时将数组内的所有数也升级，然后内存空间再进行重排
• 整数集合只支持升级操作，不支持降级操作

6.压缩列表（ziplist）

• 压缩列表是一种为节约内存而开发的顺序型数据结构。
• 压缩列表被用作列表键和哈希键的底层实现之一。
• 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
• 添加新节点到压缩列表，或者从压缩列表中删除节点，可能会引发连锁更新操作，但这种操作出现的几率并不高。

7.对象

• Redis数据库中的每个键值对的键和值都是一个对象。
• Redis共有字符串、列表、哈希、集合、有序集合五种类型的对象，每种类型的对象至少都有两种或以上的编码方式，不同的编码可以在不同的使用场景上优化对象的使用效率。
• 服务器在执行某些命令之前，会先检查给定键的类型能否执行指定的命令，而检查一个键的类型就是检查键的值对象的类型。
• Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，该对象所占用的内存就会被自动释放。
• Redis会共享值为0到9999的字符串对象。
• 对象会记录自己的最后一次被访问的时间，这个时间可以用于计算对象的空转时间。