数据结构

Redis字符串 （SDS）

​ 相比C字符串区别

• 通过len属性，获取字符串长度复杂度为O(1)

• 避免C字符串修改时忘记修改字符串长度导致的内存溢出（SDS本身有len属性，修改时会先判断是否有足够空间）

• 减少修改修改字符串带来的内存重新分配次数

• 二进制安全

• 兼容部分字符串函数

  链表

• 双向链表，获取表头和表尾的复杂度都是O(1)

• 节点本身有prev和next指针，获取前置节点和后置节点的复杂度都是O(1)

• 无环链表：表头节点的prev指针和表尾节点的next指针都是NULL，遍历链表遇到NULL值便结束，不会导致环链

• 有链表计数器：通过list结构的len属性对list持有的节点计数，程序获取链表长度复杂度为O(1)

• 多态：链表使用void*指针保存节点的值，可以通过list的dup、free、match设置类型

字典 （dict）

• 广泛运用于实现Redis的各种功能，包括数据库和哈希键
• Redis的字典使用哈希表作为底层数据结构，每个字典有两个哈希表，一个平时用，另一个仅在rehash时使用
• 字典使用MurmurHash2算法来计算键的hash值，MurmurHash2的优点：速度快，即使键有规律，也能分布均匀
• 字典使用地址法解决键冲突，被分配到同一个索引上的多个键值对会连成链表，且新加入的键值对放在头部，因为哈希表节点entry不保存尾部节点，为了保证效率，将新加入的键值对放在链表头
• 当对字典进行一段时间的新增、修改、删除操作后，为了保证哈希表的负载因子维持在一个相对较合理的水平，需对哈希表进行扩容或收缩，当进行扩展或收缩时，程序需要将现有哈希表的所有键值对rehash到新的哈希表里，并且这个rehash并不是一次性完成的，而是渐进式的。

跳跃表

• 一种有序的数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问其他节点的目的。
• 跳跃表有多个索引层

整数集合（intset）

• 整数集合是集合键的底层实现之一
• 整数集合的底层实现为数组，这个数已有序、无重复的方式保存集合元素
• 升级操作作为整数集合带来了操作上的灵活性，节约了内存
• 整数集合只支持升级，不支持降级

压缩列表（ziplist）

• 压缩列表是为了节约内存而开发的顺序性数据结构
• 压缩列表被用作列表键及哈希键的底层实现之一
• 压缩列表可以保存多个节点，每个节点可以保存一个整数值或者字节数组
• 添加新节点或删除节点可能导致连锁更新，但是这种几率不高

Redis对象

Redis并没有直接使用SDS、双端链表、字典、整数集合等来实现键值对数据库，而是构造了一个对象系统。
好处：

• 可以根据对象类型判断是否可以执行指定的命令
• 可以根据不同的场景底层使用不同的数据结构，从而优化对象在不同场景下的使用效率
• 依赖对象实现引用计数系统，从而实现内存回收
• 方便记录对象的访问时间，从而计算空转时长

字符串对象

• 字符串对象的编码可以是int、raw或者embstr
• 当字符串对象保存的是一个整数值，且这个整数值可以用long标识，那么字符串会使用int类型编码，并且整数值会保存在redis对象的ptr属性内
• 当字符串对象保存的是一个字符串值，并且这个字符串长度小于等于32字符，那么字符串对象将使用embstr编码方式来保存字符串
• 当字符串对象保存的是一个字符串值，并且这个字符串长度大于32字节，那么字符串对象使用SDS来保存这个字符串值，并且编码格式是raw
• 编码转换：当int编码的字符串对象进行追加非数字字符串时或者embstr编码的字符串进行修改时，会先转换成raw编码的字符串对象再进行修改。

列表对象

• 列表对象的编码可以是ziplist或者linkedlist
• ziplist编码的列表对象使用压缩列表作为底层实现，压缩列表的entry保存了 列表对象的元素
• linkedlist编码的列表对象使用双端链表作为底层实现，链表中的节点都保存了一个字符串对象，字符串对象内保存了一个列表元素
• 编码转换：当列表对象的所有字符串元素的长度都小于64字节，而且元素数量小于512个时使用ziplist编码，当两者其中一个条件不满足时，变回转换成linkedlist编码

哈希对象

• 哈希对象的编码可以是ziplist或者是hashtable
• ziplist编码的哈希对象，每当有新的键值对加入到哈希对象时，程序会先将包含了键的ziplist节点压入到压缩列表的尾结点，然后再将包含了值的ziplist节点压入到压缩列表的表尾。
• ziplist编码的哈希对象，键值对所在的两个节点是紧挨在一起的，保存键的节点在前，保存值的节点在后。先添加到压缩列表的键值对会被放在压缩列表的表头方向，后添加到压缩列表的键值对会被放在压缩列表的表尾方向。
• hashtable编码的哈希对象使用字典作为底层实现，哈希对象的每一个键值对都对应字典的键值对。字典的每一个键都是一个字符串对象，对象中保存了键值对的键，字典的每一个值都是一个字符串帝乡，对象中保存了键值对的值。
• 编码转换：当哈希对象的所有键值对的键和值的字符串长度都小于64字节，并且哈希对象保存的键值对数量小于512个时，使用ziplist进行编码。否则使用hashtable进行编码。

集合对象

• 集合对象的编码可以是intset或者hashtable
• intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合中
• hashtable编码的集合对象使用字典作为底层实现，字典的每一个键都是一个字符串对象，每个字符串对象都包含了一个集合元素，字典的值全被设置为NULL
• 当集合对象所有的元素都是整数值，且保存的数量不超过512个时，使用intset编码集合对象，否则使用hashtable编码集合对象。

有序集合对象

• 有序集合对象的编码可以是ziplist或者skiplist
• ziplist编码的有序集合对象底层实现是压缩列表，每个有序集合的元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存有序集合的元素，第二个节点保存元素的分值。压缩列表的集合元素按照分值从小到大开始排序，分值较小的节点靠近压缩列表的表头方向，分值较大的节点靠近压缩列表的表尾方向
• skiplist编码的有序集合对象使用zset作为底层实现，一个zset结构同时包含一个字典和一个跳跃表。zset结构中的zsl跳跃表按照分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素，跳跃表节点的object属性保存了元素的成员，score属性保存了元素的分支，通过跳跃表，程序可以对有序集合进行范围型操作，如ZRANK、ZRANGE等命令。zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典的每一个键值对都保存了一个集合元素，字典的键保存了元素的成员，字典的值保存了元素的分值，通过这个字典，程序可以以O(1)复杂度查找给定成员的分值，ZSCORE命令就是根据这一特性实现的。
• 有序集合对象的每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。值得一提的是：虽然zset结构同时使用跳跃表和字典来保存集合对象元素，但是这两种数据结构会通过指针来共享相同元素的成员和分支，所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员和分支，也不会因此浪费内存。
• 为什么有序集合要同时使用跳跃表和字典来实现？理论上来讲，无论有序集合单独使用跳跃表和字典来实现有序集合，性能都会比同时使用跳跃表和字典有所降低。例如，如只使用字典来实现有序集合，那么在使用有序集合的ZRANK、ZRANGE命令时，程序都需要对字典保存的所有元素进行排序，完成这种排序的复杂度为O(nlog(n)),以及额外的O(N)的空间（创建数组保存排序后的元素）；如只使用跳跃表实现有序集合，那么在根据指定成员查询分值时，复杂度就会变成O(log(n))，而不是字典的O(1)。综合以上原因，为了让有序集合同事拥有字典和跳跃表的所有特点，Redis选择同时使用跳跃表和字典来实现有序集合。

类型检查与多态

Redis命令主要分为两类，一类是针对所有Redis对象都可以执行的，如EXPIRE、DEL、RENAME、TYPE、OBJECT等，依赖是只针对指定Redis对象可以执行的。

• 字符串键：SET、GET、APPEND、STRLEN
• 列表键：RPUSH、LPOP、LINSERT、LLEN
• 哈希键：HSET、HGET、HDEL、HLEN
• 集合键：SADD、SCARD、SINSERT、SPOP
• 有序集合键：ZADD、ZCARD、ZRANK、ZSCORE

类型检查实现：Redis在执行命令前，会先检查输入的键对应的值对象是否为执行命令所支持的类型，通过reidsObject的type属性实现，如果是，则对键执行指定的命令，否则，向客户端返回类型错误。

多态命令：Redis对象有不同的编码实现，不同的编码实现要实现同一个命令的效果，所以对于不同的编码，Redis需要调用底层实现不同的API来实现。

内存回收

C语言不具备自动内存回收功能，Redis在自己的对象系统中构建了一个基于引用计数实现的内存回收机制，通过这一机制，程序可以通过追踪对象的引用计数信息，在适当的时候自动释放对象，并进行内存回收。

每个对象的引用计数由RedisObject的refCount属性记录。

对象的引用计数变化：

• 创建一个新对象时，对象的引用计数被初始化为1
• 当对象被新程序引用时，它的引用计数值会增一
• 当对象不再被新程序引用时，它的引用技术值会减一
• 当对象的引用技术值为零时，Redis会回收对象占用的内存

引用计数的内存回收：

• 优点
  • 代码逻辑清晰
  • 不会有几种清理数据造成的假死现象
• 缺点
  • 无法解决循环引用问题
  • 增加/减少引用计数时的函数要对称，不能漏掉