《Redis设计与实现》学习。
Redis(Remote Dictionary Server)远程字典服务，基于内存的、可持久化的kv数据库。Redis相比Memcached支持的value数据类型更多，包括：string、list、set、zset、hash。
首先看一下Redis支持的底层数据结构。
1、SDS
SDS(Simple Dynamic String，简单动态字符串)是字符串的底层存储结构。定义在sds.c和sds.h文件中，如下结构。
struct sdshdr{// 记录buf数组中已经使用的字节数量，等于SDS保存的字符串长度int len;// 记录buf数组中未使用的字节数量int free;// 字节数组，用于保存字符串char buf[];}
Redis的字符串是可修改的。
free=0，表示SDS没有分配任何未使用的空间
len=5，表示这个SDS保存了5字节长的字符串
buf是char类型数组，前5个字节保存Redis字符，最后一个字节保存空字符'\0'
SDS遵循C中字符串以空字符结尾的惯例，保存空字符的1字节不计算在len内。这样做的好处是SDS可以直接重用一部分C字符串函数库的函数。
SDS和C字符串的区别？
C语言使用长度为N+1的字符数组来表示长度为N的字符串，并在最后元素设为'\0'，这种简单的字符串并不能满足Redis对字符串在安全性、效率以及功能方面的需求：
Redis有长度复杂度(O(1))的获取字符串长度。C并不记录字符串自身长度，程序需要遍历整个字符串对象对每个字符进行计数直到遇到'\0'，复杂度O(n)。设置和更新SDS长度的工作由SDS的API在执行时自动完成，无需手动修改。这样Redis将获取字符串长度的复杂度降到O(1)，确保获取字符串长度的工作不会成为Redis的性能瓶颈。
Redis字符串没有缓冲区溢出问题。C字符串不记录自身长度容易造成缓冲区溢出(buffer overflow)。例如strcat函数可以将两个字符串进行拼接，如果没有为拼接后的字符串分配足够的内存就会导致内存溢出；SDS API进行修改时会先检查SDS的空间是否足够，不满足的情况下会进行扩展至所需大小，然后再执行修改操作。如何进行扩展？
Redis减少字符串修改时的内存重分配次数。什么是内存重分配？C语言不记录字符串长度，每次增长或者缩短C字符串时，程序需要对保存这个C字符串的数组进行内存分配：增长->扩展底层数组空间大小；缩短->释放不再使用的内存空间。
内存重分配涉及复杂算法和系统调用是比较耗时的操作。SDS使用free字段实现了空间预分配和惰性空间释放两种优化策略。
空间预分配：减少连续执行字符串增长操作所需的内存重分配次数
优化SDS的字符串增长操作，当SDS需要进行空间扩展时，程序除了给SDS分配修改需要的空间外，还会分配额外的未使用空间（free的值就表示未使用的空间，下次如果在需要扩的时候可以直接用这个未使用空间），分配策略是如果扩展后的SDS长度小于1M，那么SDS的length多大就分多大的free；如果超过1M，那么free就分1M。
惰性空间释放：避免缩短字符串需要的内存重分配
优化SDS的缩短操作，当SDS要回收缩短后多出的字节时，不执行回收，用free将这部分多出的字节记录下来，留着后面使用。SDS提供实际删除空间的API。
2、链表
链表提供了高效的节点重排能力以及顺序性的节点访问方式，并可以通过增删节点灵活调整链表长度。
链表的实现listNode结构是一个双向链表：prev和next两个指针。如下。
Redis的链表特性：
双端
无环
表头指针和表尾指针，有size计数器
多态：可以为节点设置类型特定的函数，可以保存不同类型的值
3、字典
字典又称符号表(symbol table)、关联数组(associative array)、映射(mapping)，是一种k-v存储的抽象数据结构。
Redis数据库的底层就是用字典来实现的。
字典的底层使用哈希表实现。
1）Redis的哈希表
typedef struct dicht {// 数组dictEntry **table;// lengthunsigned long size;// 掩码，用于计算索引值，=size-1unsigned long sizemask;// 哈希表已有节点数量unsigned long used;}
逻辑结构如下所示。
2）键冲突
将新值添加到字典时需要计算出存放的位置（与HashMap差不多）
Redis的哈希表使用链地址法来解决键冲突，每个hash表的节点有一个next指针，是一个单向链表。采用的是头插法(最近的数据可能下次被访问到，一些考量)
3）rehash
类比于HashMap的resize操作。
当前使用的字典是ht[0]，现在负载因子达到阈值要进行rehash操作了：
新建一个ht[1]字典并初始化大小
扩容操作，h[1]大小为第一个≥ht[0].used*2的2的n次幂(h[1]初始化大小是老字典中大于等于已用长度2倍的第一个2的n次幂，used=3，h[1]的大小为8)
缩容操作，h[1]大小为第一个≥ht[0].used的2的n次幂(used=3，h[1]的大小为4)
ht[0]的键值rehash到ht[1]上
这个动作不是阻塞一直执行的操作，是渐进式的rehash
Redis中存在ht[0]和ht[1]两个字典
生成索引计数器rehashidx=0，记录rehash进展
对字典增、删、改、查，程序从ht[0]上操作，顺便将ht[0]对应的reindexidx索引上的所有键值rehash到ht[1]，reindexidx++
随着时间推移...分而治之、均摊，避免集中处理计算量大
ht[0]空了后，释放，将ht[1]设置为ht[0]
4、跳表
跳表是有序数据结构，每个节点中维护了多个指向其他节点的指针来实现快速访问节点的目的。跳表支持平均O(logN)、最坏O(N)的时间复杂度。结构如下：
zskipList：header头结点、trail尾节点、level层数(最大层数，表头节点层不算在内，也就是不算低一层的高度吧)、length长度(表结点的数量，表头不算在内，也就是上图3个统计节点)
zskipListNode是存储数据的节点，类比链表的节点。
typedef struct zskiplistNode {//层struct zskiplistLevel {//前进指针struct zskiplistNode *forward;//跨度unsigned int span;} level[];//后退指针struct zskiplistNode *backward;//分值double score;//成员对象robj *obj;} zskiplistNode
层：前进指针(指向哪个节点)+跨度(跨了多少节点)
一般来说层越多，访问越快，但维护就越复杂。每次创建新节点，程序根据幂次定律(越大的数出现的概率越小)随机生成1-32之间的值作为level数组的大小。
跨度越大隔得越远，跨度用来计算排位(rank)：查找某个节点过程中，将沿途访问过的所有层的跨度累计起来就是目标节点在跳表中的排位。
后退指针：BW标记的。倒着遍历用的
分值(score)：节点的分值，节点按各自保存的分值从小到大排列(这就是有序性说的)
obj：保存的对象
5、整数集合(intset)
intset是集合键的底层实现之一。
当集合只包含整数值元素，并且集合的元素数量不多时，Redis就是用整数集合作为集合键的底层实现。
例如，设置numbers集合1,3,5,7,9
redis> SADD numbers 1 3 5 7 9redis> OBJECT ENCODING numbers"intset"
升级：将一个比整数集合中所有元素类型都长的新元素加入集合时，intset需要先进行升级。
扩展整数集合底层数组的空间大小，并为新元素分配空间
将现有元素转成与新元素相同类型，并放到对应位置(保持有序性)
将新元素添加
不支持降级。（我这么理解，升级小->大空间扩展，数值不变；大->小可能出现溢出）
6、压缩列表(ziplist)
ziplist是列表键和哈希键的底层实现之一。ziplist是Redis为节约内存开发的、由特殊编码的、连续内存块组成的(存的少、存的小)、顺序型数据结构。可以包含多个节点，每个节点保存一字节数组或者一个整数值。
列表键就是列表的意思！！！
> 一个列表包含少量元素并且元素要么是小整数、要么短字符串，用ziplist实现
> 哈希表包含少量键值并且键值小整数、小字符串时，用ziplist实现
7、对象
Redis主要的数据结构：SDS、双端链表、字典、ziplist、intset。这些都是底层的数据结构，其实现的Redis的对象包括：字符串、列表、哈希、集合、有序集合五种类型。
Redis可以在执行命令前根据对象类型判断命令是否能执行
Redis实现了基于引用计数的内存回收机制
Redis通过引用计数还实现了对象共享机制
Redis对象带有访问时间可用于计算数据库键的空转时长
1）对象类型与编码
Redis使用对象来表示数据库中的键和值，每当创建一个新的键值对时，Redis至少创建两个对象：键对象、值对象。
typedef struct redisObject {// 类型unsigned type:4;// 编码unsigned encoding:4;// 底层实现数据结构指针void *ptr;// ...}
类型：5个常量 -> 5种对象类型（键总是一个字符串对象，值可多个）
编码：记录对象使用的编码，即这个对象的底层实现数据结构，如下。
2）各种对象类型
字符串对象
字符串对象的编码可以是int(字符串保存是整数且可以用long表示时)、raw(长度>32的+SDS存储的)或者embstr(<32)。
embstr编码专门用于保存短字符串的一种优化编码方式，和raw编码一样都是用RedisObject和sdshdr结构来表示字符串，raw编码会调用2次内存分配函数分别创建redisObject结构和sdshdr结构，embstr调用1次内存分配一块连续空间，空间内依次包含redisObject和sdshdr两个结构。
列表对象
编码可以是ziplist(底层采用压缩列表实现)或者linkedlist(采用双端链表实现)。
列表对象保存的所有字符串长度都小于64字节，并且数量小于512时用ziplist编码；否则，LinkedList。
哈希对象
哈希对象的编码可以是ziplist或者hashtable。
ziplist实现：程序先将键节点放到压缩列表尾部，紧接着放入值节点(这样遍历是否耗时长啊？连续内存、内存访问，并且还有限制数量，还行吧) ---> 所有键和值的长度都小于64字节，并且键值对数量小于512时使用ziplist；不满足时，对象编码转换操作执行，键值转移保存到字典里面。
集合对象
集合对象的编码可以是intset(元素都是整数,个数<512)或者HashTable。
有序集合对象
有序集合对象的编码可以是ziplist或者skiplist。
ziplist：还是两个紧挨的节点表示，第一个表示元素成员，第二个表示元素分值，并且集合元素按照分值从小到大排序。元素数量<128并且所有元素长度<64字节时，使用ziplist。
skiplist编码使用zset作为底层结构，zset=字典+跳表。跳表按分值从小到大保存所有集合元素，字典是成员到分值的映射。
zset采用跳表和字典保存有序集合的元素，但这两种数据结构都会通过指针共享相同的元素和分值，不会产生重复的元素和分值，即不会造成额外的内存浪费。为什么要这两个数据结构一块实现zset呢？
使用2个是性能的考量，单独使用一个也可以实现，但不如意。使用字典可以保证O(1)复杂度找到分值，使用跳表是有序+快速查找元素。
3）引用计数
内存回收
每个对象的引用计数信息由redisObject结构的refcount属性记录：
typedef struct redisObject {// 引用计数int refcount;}
创建新对象时refcount++
对象被新程序引用时refcount++
不被一个程序引用时refcount--
refcount=0时对象释放所占用内存
对象共享
例如，(A,"100")，注：这个2个redisObject啊！如果再要创建(B,"100")，有两种选择：① 创建一个一样的对象；② 键A和B共享100对象。
将键B的值指针指向一个现有的值对象(100)
值对象(100)的引用计数器++
注意：尽管共享更复杂的对象可以节约内存，但是收到CPU时间的限制，Redis只对包含整数值的字符串(这种验证复杂度O(1))对象进行共享。
4）对象的空转时长
前面提到RedisObject的结构，有一个lru属性：记录对象最后一次被命令程序访问的时间。
空转时长=当前时间 - lru时间。
为什么要有这个lru啊？
服务器设置maxmemory(见名知意，最大内存限制)时，并且内存回收算法为volatile-lru或者allkeys-lru时，那么当服务器占用内存超过maxmemory时，空转时间较高的键会优先被服务器释放。
