底层实现
dict
dict类似于java里的hashmap，当发生冲突时，使用链地址法，把新加入的节点插入到链表的最前面。哈希算法使用Murmruhash2，这种算法即使输入的键是有规律的，算法仍能给出一个很好的随机分布性，计算速度非常快，使用简单。
dict的数据结构里包含两个哈希表。在重哈希期间，数据从第一个哈希表向第二个哈希表迁移。
增量式重哈希
在需要扩展内存时避免一次性对所有key进行重哈希，而是将重哈希操作分散到对于dict的各个增删改查的操作中去。这种方法能做到每次只对一小部分key进行重哈希，而每次重哈希之间不影响dict的操作。
以下是一次重哈希的过程：
sds
只有不变的string才会用c字符串，比如日志
简单动态字符串 simple dynamic string（相比于string可以动态调整）
free: 未使用空间，len：已使用长度，不包含结束符\0， buf：字节数组，保存二进制数据
- 当修改sds时，会先检查sds的空间是否够用，不够的话会先扩展空间，并且会分配额外的未使用空间（减少连续执行字符串增长操作所需的内存重分配次数）。分配规则如下：
- 如果修改后的sds长度小于1MB，那么free = len
- 反之，free = 1MB
- 惰性空间释放用于优化SDS的字符串缩短操作：缩短sds保存的字符串时，用free记录，而不是使用内存重分配。也提供了api可以真正地释放空间。
sds使用len而不是空字符串判断字符串是否结束，所以可以存储任意二进制数据。保留/0是因为可以重用一部分c库的函数
链表
例子：列表键的底层实现之一就是链表，当一个列表键包含了数量比较多的元素，又或者列表中包含的元素都是比较长的字符串时，就会使用链表作为底层实现
adlist.h/list持有多个listNode，listNode是双端队列，且无环。
可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值
跳表
跳表可以简单地认为是将二分查找运用到链表上，用空间换时间。下图是一个跳表的产生过程：
从上面skiplist的创建和插入过程可以看出，每一个节点的层数（level）是随机出来的，而且新插入一个节点不会影响其它节点的层数。因此，插入操作只需要修改插入节点前后的指针，而不需要对很多节点都进行调整。这就降低了插入操作的复杂度。实际上，这是skiplist的一个很重要的特性，这让它在插入性能上明显优于平衡树的方案。
Redis中的skiplist
sorted set是一个有序的数据集合，实现如下：
- 当数据较少时，sorted set是由一个ziplist来实现的。
- 当数据多的时候，sorted set是由一个dict + 一个skiplist来实现的。简单来讲，dict用来查询数据到分数的对应关系，而skiplist用来根据分数查询数据（可能是范围查找）。
sorted set与skiplist的关系：
- 为了支持排名(rank)，Redis里对skiplist做了扩展，使得根据排名能够快速查到数据，或者根据分数查到数据之后，也同时很容易获得排名。而且，根据排名的查找，时间复杂度也为O(log n)。
Redis中的skiplist跟前面介绍的经典的skiplist相比，有如下不同：
分数(score)允许重复，这在最开始介绍的经典skiplist中是不允许的。
在比较时，不仅比较分数，还比较数据本身。在Redis的skiplist实现中，数据本身的内容唯一标识这份数据，而不是由key来唯一标识。另外，当多个元素分数相同的时候，还需要根据数据内容来进字典排序。
第1层链表不是一个单向链表，而是一个双向链表。这是为了方便以倒序方式获取一个范围内的元素。
在skiplist中可以很方便地计算出每个元素的排名(rank)。
有个字段span，表示当前指针跨越了多少个节点，这个计数不包括指针的起点节点，但包括指针的终点节点。（前向指针括号上面的数字）
求排名只要累加span的值（从小到大），从大到小只要用skiplist长度-路径上的span累加值
整数集合（intset）
用于保存int的set
encoding是编码方式
升级
每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有所有元素的类型都要长时，整数集合需要先进行升级（upgrade），然后才能将新元素添加到整数集合里面。
- 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
- 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放置到正确的位上，而且在放置元素的过程中，需要继续维持底层数组的有序性质不变。
- 将新元素添加到底层数组里面。
上图原本是三个int16_t的整数，将类型为int32_t的整数值65535添加到整数集合里面，最终：
整数集合现在的做法既可以让集合能同时保存三种不同类型的值，又可以确保升级操作只会在有需要的时候进行，这可以尽量节省内存。 但是intset不支持降级。
压缩列表（ziplist)
压缩列表（ziplist）是列表和哈希的底层实现之一。当一个列表键只包含少量列表项，并且每个列表项要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做列表键的底层实现。另外，当一个哈希键只包含少量键值对，并且每个键值对的键和值要么就是小整数值，要么就是长度比较短的字符串，那么Redis就会使用压缩列表来做哈希键的底层实现。
压缩列表各个组成部分：
zlbytes：总长度
zltail：表尾节点到起始地址的距离
zllen：包含的节点数量，最大显示为INT16_MAX(65535)
entryX: 节点
zlend：标记末端
上图的60就是zltail
节点
每个压缩列表节点可以保存一个字节数组或者一个整数值
previous_entry_length
前一个节点的长度（该属性长度为1字节或者5字节，单位是字节），前一个节点长度<254字节时为1字节，反之为5字节
因为节点的previous_entry_length属性记录了前一个节点的长度，所以程序可以通过指针运算，根据当前节点的起始地址来计算出前一个节点的起始地址。可以从表尾向表头遍历。
encoding
记录了节点的content属性所保存数据的类型以及长度
表7-2 字节数组编码
content
负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的encoding属性决定。
连锁更新
在一个压缩列表中，有多个连续的、长度介于250字节到253字节之间的节点e1至eN时，新增加一个长度大于等于254字节的新节点new设置为压缩列表的表头节点，那么e1的previous_entry_length由长度1字节变为5字节，之后可能连锁反应，后面每个节点都要更新。
删除时也可能连锁更新。下图big长度>=254B，small长度<254B，删除small，e1的previous_entry_length由5字节变为1字节
连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作，而每次空间重分配的最坏复杂度为O（N），所以连锁更新的最坏复杂度为O（N 2）。尽管连锁更新的复杂度较高，但它真正造成性能问题的几率是很低的。
quicklist
是一个ziplist的双向链表：quicklist的每个节点都是一个ziplist，也是无环的。结合了双向链表和ziplist的优点
- 双向链表便于在表的两端进行push和pop操作，但是它的内存开销比较大。首先，它在每个节点上除了要保存数据之外，还要额外保存两个指针；其次，双向链表的各个节点是单独的内存块，地址不连续，节点多了容易产生内存碎片。
- ziplist由于是一整块连续内存，所以存储效率很高。但是，它不利于修改操作，每次数据变动都会引发一次内存的realloc。特别是当ziplist长度很长的时候，一次realloc可能会导致大批量的数据拷贝，进一步降低性能。
- 两端各有2个橙黄色的节点，是没有被压缩的。它们的数据指针zl指向真正的ziplist。中间的其它节点是被压缩过的，它们的数据指针zl指向被压缩后的ziplist结构，即一个quicklistLZF结构。
对象
Redis的对象系统还实现了基于引用计数技术的内存回收机制，还通过引用计数技术实现了对象共享机制，这一机制可以在适当的条件下，通过让多个数据库键共享同一个对象来节约内存。
Redis使用对象来表示数据库中的键和值，每次当我们在Redis的数据库中新创建一个键值对时，我们至少会创建两个对象，一个对象用作键值对的键（键对象），另一个对象用作键值对的值（值对象）。
1 | typedef struct redisObject { |
键总是一个字符串对象，而值则可以是字符串对象、列表对象、哈希对象、集合对象或者有序集合对象的其中一种
string
字符串对象的编码可以是int、raw或者embstr。
int：将整数值保存在字符串对象结构的ptr属性里面（将void*转换成long）
embstr即embedded string，“嵌入式的字符串，将SDS结构体嵌入RedisObject对象中”，是专门用于保存短字符串的一种编码方式，与raw的差别在于，raw会调用两次内存分配函数来创建redisObject结构和sdshdr结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间内一次包含了redisObject和sdshdr两个结构。
字符串长度<=32字节（redis 5.0为44字节），使用embstr。embstr减少一次内存分配次数和一次内存释放，而且连续的内存更好地利用缓存。
可以用long double类型表示的浮点数在Redis中也是作为字符串值来保存的。在有需要的时候，程序会将保存在字符串对象里面的字符串值转换回浮点数值，执行某些操作，然后再将执行操作所得的浮点数值转换回字符串值，并继续保存在字符串对象里面。
编码转换
int可以转成raw，embstr只读，修改后也会变成raw
list
列表对象的编码可以是ziplist或者linkedlist。（注：redis3.2之后，都是由quicklist实现，而quicklist是ziplist和linkedlist的结合体）
ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点（entry）保存了一个列表元素。
linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点（node）都保存了一个字符串对象，而每个字符串对象都保存了一个列表元素。字符串对象是Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。
StringObject仅是简略表示，完整表示如下
hash
哈希对象的编码可以是ziplist或者hashtable。
ziplist编码的哈希对象使用压缩列表作为底层实现，每当有新的键值对要加入到哈希对象时，程序会先将保存了键的压缩列表节点推入到压缩列表表尾，然后再将保存了值的压缩列表节点推入到压缩列表表尾，因此：
·保存了同一键值对的两个节点总是紧挨在一起，保存键的节点在前，保存值的节点在后；
·先添加到哈希对象中的键值对会被放在压缩列表的表头方向，而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
另一方面，hashtable编码的哈希对象使用字典作为底层实现，哈希对象中的每个键值对都使用一个字典键值对来保存：
·字典的每个键都是一个字符串对象，对象中保存了键值对的键；
·字典的每个值都是一个字符串对象，对象中保存了键值对的值。
编码转换
当哈希对象可以同时满足以下两个条件时，哈希对象使用ziplist编码：
哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
哈希对象保存的键值对数量小于512个；
不能满足这两个条件的哈希对象需要使用hashtable编码。
set
集合对象的编码可以是intset或者hashtable。
intset编码的集合对象使用整数集合作为底层实现，集合对象包含的所有元素都被保存在整数集合里面。
hashtable编码的集合对象使用字典作为底层实现，字典的每个键都是一个字符串对象，每个字符串对象 包含了一个集合元素，而字典的值则全部被设置为NULL。
编码转换
当集合对象可以同时满足以下两个条件时，对象使用intset编码：
集合对象保存的所有元素都是整数值；
集合对象保存的元素数量不超过512个。
不能满足这两个条件的集合对象需要使用hashtable编码。
sorted set
有序集合的编码可以是ziplist或者skiplist。
ziplist编码的压缩列表对象使用压缩列表作为底层实现，每个集合元素使用两个紧挨在一起的压缩列表节点来保存，第一个节点保存元素的成员（member），而第二个元素则保存元素的分值（score）。
压缩列表内的集合元素按分值从小到大进行排序，分值较小的元素被放置在靠近表头的方向，而分值较大的元素则被放置在靠近表尾的方向。
skiplist编码的有序集合对象使用zset结构作为底层实现，一个zset结构同时包含一个字典和一个跳跃表：
1 | typedef struct zset { |
zset结构中的dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素：字典的键保存了元素的成员，而字典的值则保存了元素的分值。通过这个字典，程序可以用O（1）复杂度查找给定成员的分值
zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素：跳跃表节点的object属性保存了元素的成员，而跳跃表节点的score属性则保存了元素的分值。
有序集合每个元素的成员都是一个字符串对象，而每个元素的分值都是一个double类型的浮点数。字典和跳跃表会通过指针来共享相同元素的成员和分值
为什么同时需要跳表和字典：
- 没有跳表: 范围操作时每次都需要排序，需要至少O（NlogN）时间复杂度，以及额外的O（N）内存空间（因为要创建一个数组来保存排序后的元素）
- 没有字典：根据成员查找分值这一操作的复杂度将从O（1）上升为O（logN）
注：字典和跳跃表实际会共享元素的成员和分值，图中重复展示了
参考链接
《Redis设计与实现（第二版）》
