数据结构
一、动态字符串
redis通过定义一个动态的字符串类（SDS），用来存储数据。
字符串的属性如下：
- int len： 用来记录buf数组已经使用的字节数
- int free：用来记录buf数组未使用的字节数
- char buf[]：字节数组，用来保存数据
定义：SDS遵循C字符串以空字符结尾的管理，保留一个字节空间存储'\0'字符。这个字符不会占用len的长度，对于SDS来说是完全透明的
SDS相比C字符串的好处：
- SDS判断自身字符串的长度复杂度为O(1)，而由于C字符串不会记录自身的长度，所以复杂度为O(N)，每次都要进行计算。而且SDS能够杜绝缓冲区溢出，因为SDS能够判断已经使用和未被使用的空间大小，而C字符串如果在修改字符串的时候对字符串的内存空间分配不足，就会造成缓冲区溢出的问题。
- C字符串不能以空字符结尾，否则最先被程序读入的空字符被误认为是字符串结尾，而SDS不会出现这种问题，它通过长度来定位字符串的大小。所以对于C字符串来说，只能存储文本的数据，而对于SDS来说可以存储二进制的数据。只要数据经过序列化是可以存储到redis当中。
- C字符串并且由于不能获取到字符串的长度大小，容易造成修改字符串带来的多次内存重分配。而SDS不会
二、链表
redis使用的是C语言实现，但是C语言没有链表的数据结构，所以redis手动实现了链表。
redis链表的特性：
- 双端无环：双向链表，并且头结点head的prev（前一个节点）和尾结点tail的next（后一个节点）都指向null，不构成环形链表。
- 带有链表长度计数器：程序使用list结构的len属性对list持有的链表节点数量进行计数。
- 多态：链表节点使用void*指针来保存节点值。（类似java的泛型）
redis链表使用场景：
- 列表键
- 发布与订阅
- 慢查询
- 监视器
三、字典（映射map）
由于C语言也没有map数据结构，redis的字典，即map都是自己实现。实现的思想与java的hashMap类似
字典对象属性：
- *type：特定函数
- *privtata：私有数据
- ht[2]：hash表
- trehashidx：rehash的索引，当rehash不在进行时，值为-1
hash节点属性：
- *key：键
- union：值
- *next：下一个节点
type和privdata属性是针对不同类型的键值对，为创建多态字典而设置的。ht数组长度为2，ht[0]表示存储的实际数据，ht[1]只有在对ht[0]进行扩展的时候使用。
哈希表的扩容与缩容：
redis的hash计算是通过MurmurHash2算法来计算键的hash值，这种算法的优点在于，即使输入的键是有规律的，算法依然能给出一个很好的随机分布性，并且算法的计算速度也很快。
hash表的负载因子 ：ht[0].used / ht[0].size
hash表每次扩容的大小： 第一个大于等于ht[0].used * 2 的2n次方
hash表每次缩容的大小： 第一个大于等于ht[0].used的2n次方
扩容大小示例：当前size为4，used为4，即触发扩容，下次扩容的大小为：2^3（2的3次方）=8
扩容条件（满足其一）：
- 服务器目前没有执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于1。
- 服务器目前正在执行bgsave命令或者bgrewriteaof命令，并且哈希表的负载因子大于等于5。
缩容条件：当哈希表的负载因子小于0.1的时候，程序自动开始对hash表执行缩容
哈希表为了保证在rehash的过程当中保证哈希表可用。因为rehash是渐进式的执行，即不会一下子把所有的数据直接从ht[0]移动到ht[1]，所以在rehash的过程当中，新增操作则仍是在ht[0]上进行，并且trehashidx+1，而字典的删除、查找、更新的操作会在两个hash表上进行。直到最后rehash完成trehashidx变成-1，ht[0]指向ht[1]
四、跳跃表（skiplist）
为什么redis对有序集合使用的是跳跃表而不是红黑树，单论查询效率红黑树的效率与跳表相差不大，但是在并发环境的情况下却截然不同，所以redis使用了跳表。如果要更新数据，跳跃表需要更新的部分就比较少，锁的东西也就比较少，所以不同线程争锁的代价就相对少了，而红黑树有个平衡的过程，牵涉到大量的节点，争锁的代价也就相对较高了。性能也就不如前者了。在并发环境下skiplist有另外一个优势，红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，锁需要盯住的节点更少，因此在这样的情况下性能好一些。
五、压缩列表（ziplist）
压缩链表是redis为了节省内存而开发，由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点（entry），每个节点可以保存一个字节数组或一个整数值。
组成：
| 属性 | 类型 | 长度 | 用途 |
|---|---|---|---|
| zlbytes | uint32_t | 4字节 | 记录整个压缩列表所占用的内存大小 |
| zltail | uint32_t | 4字节 | 记录压缩列表尾节点距离起始节点地址有多少字节，通过偏移量确定尾节点地址 |
| zllen | uint16_t | 2字节 | 记录压缩列表节点个数 |
| entryX | 列表节点 | 不定 | 压缩列表包含的各个节点，节点长度由节点内容决定 |
| zlend | uint8_t | 1字节 | 特殊值，用于标记压缩列表末端 |
连锁更新：
压缩列表从表尾向表头遍历操作通过以下方式实现：压缩列表每个节点都会存储前一个节点的长度，通过previous_entry_length属性记录
这时候会有以下两种情况：
- 如果前一个节点的长度小于254字节，那么previous_entry_length属性需要用1字节长的空间来保存这个值
- 如果前一个节点的长度大于等于254字节，那么previous_entry_length属性需要用5字节长的空间来保存这个长度值
假设有多个连续的长度介于250-253字节之间的节点，这时候头部插入一个大于253字节的节点。后面的节点会占用5字节来存储前一个节点的长度，这时候程序需要再次对压缩列表执行空间重新分配操作。这一系列连续的节点都执行这样的操作，这个过程redis叫做连锁更新
尽管连锁更新的复杂度很高是O（N^2），但是它造成的性能影响的几率很低
- 压缩列表必须有好几个连续的、长度介于250-253之间的节点连锁更新才能被引发，实际中这种情况很少见
- 即使出现连锁更新，但只要更新的节点数量不多，就不会对性能造成任何影响