一、理论与实践之个人思考
最近金三银四跳槽季，八股文成了大家口中噩梦一般的存在，有的人也会疑惑学习理论知识有什么用，还不是面试造火箭，入职拧螺丝。
个人觉得只有掌握了原理，才能知道在什么时候使用什么技术。
比如下面我们要讲基本数据结构的底层实现，有的人可能会觉得在日常开发中这些根本用不上，但我并不这么觉得。比如只有我们了解List底层是使用链表这种数据结构，才能知道它适合两端的操作（时间复杂度为O(1)），POP/PUSH的效率很高，可以用于FIFO队列场景，也能知道它查找的效率低下（时间复杂度O(n)），不适合随机读取的场景，此外，根据底层数据结构是链表，我们知道List遍历的时间复杂度是O(n)，为了提高效率，我们会采取渐进式遍历命令SCAN（时间复杂度O(1)）。而这些可以提高程序效率的操作，都是在我们了解底层实现的前提下做出来的决定。
二、Rdis底层数据结构
Redis基本数据类型的底层数据结构如下图所示：
Redis基本数据类型的底层结构示意图
1、ziplist（压缩列表）
(1)、简单介绍
ziplist是list、hash、sorted set的底层数据结构，当list、hash、sorted set中包含的元素数量较少、并且每个元素要么是小整数要么是长度较短的字符串时，Redis将会用ziplist作为其底层实现。
ziplist是Redis为了节约内存空间而开发的。
ziplist由一系列特殊编码的连续内存块组成的顺序存储结构，类似于数组，不同的是数组中叫元素，ziplist中叫节点entry。ziplist的节点在内存中是连续存储的，每个节点所占的内存大小可以是不同的（即ziplist每个entry的长度可以是不一样的），每个节点可以用来存储一个整数或者一个字符串。
(2)、基本结构
ziplist结构如下所示：
struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 记录压缩列表表尾节点距离压缩列表的起始地址有多少个字节，用于快速定位到最后一个节点，反向遍历ziplist或者pop尾部节点的时候有用
int16 zllength; // 记录了压缩列表包含的节点数量
T[] entries; // 节点数组，挨个挨个紧凑存储
int8 zlend; // 值为0xFF，标志压缩列表的结束
}
ziplist结构示意图
压缩列表为了支持双向遍历，所以才会有ztail_offset这个字段，用来快速定位到最后一个元素，然后倒着遍历。
entry节点的结构如下所示：
struct entry {
int<var> prevlen; // 前一个 entry 的字节长度
int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
prevlen属性以字节为单位,记录了压缩列表中前一个节点的长度，当压缩列表倒着遍历时，需要通过这个字段来快速定位到下一个元素的位置。
encoding属性记录了节点的content属性所保存数据的类型以及长度，ziplist通过这个字段来决定后面的content内容的形式。
ziplist的encoding
content属性负责保存节点的值，节点值可以是一个整数或者字符串，值的类型和长度由节点的encoding属性决定。
ziplist保存字符串的节点
(3)、ziplist的操作
(a)、插入元素
因为ziplist在内存中是紧凑存储，没有冗余空间的，所以插入一个新的元素就需要扩展内存大小。如何扩展内存取决于当前ziplist的内存大小，可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。
ziplist插入操作图示1
ziplist插入操作图示2
见图1，如果当前ziplist占据内存太大，重新分配的内存和拷贝旧内容的内存就会很大，会造成很大的消耗。所以ziplist不适合存储大型字符串，存储的元素也不宜过多。
(b)、连锁更新（级联更新）
每个entry都会有一个prevlen字段存储前一个entry的长度。如果前一节点的长度小于254字节，那么prevlen需要用1个字节存储，如果前一节点的长度大于等于254字节，那么prevlen需要用5个字节存储。
这意味着如果某个entry经过修改操作从253字节变成了254字节，那么它的下一个 entry的prevlen字段就要更新，从1个字节扩展到5个字节；如果这个entry的长度本来也是253字节，那么后面entry的prevlen字段还得继续更新。如果ziplist里面每个entry恰好都存储了253字节的内容，那么第一个entry内容的修改就会导致后续所有entry的级联更新，这就是一个比较耗费计算资源的操作，要尽量避免这种情况的发生。
ziplist级联更新图示
2、linkedlist（双向链表）
(1)、简单介绍
因为C语言没有内置链表这种数据结构，所以Redis构建了自己的链表实现，即双向链表linkedlist。当列表List包含了数量比较多的元素，又或者包含的元素都是比较长的字符串时，Redis就会使用linkedlist作为List的底层实现。
(2)、基本结构
双向链表数据结构：
typedef struct list{
listNode *head;// 表头节点
listNode *tail;// 表尾节点
unsigned long len;// 链表所包含的节点数量
void (*dup) (void *ptr);// 复制链表结点所保存的值
void (*free) (void *ptr);// 释放链表结点所保存的值
int (*match) (void *ptr,void *key);// 用于对比链表结点所保存的值和另一个输入值是否相等
}list;
双向链表结点数据结构:
typedef struct listNode{
struct listNode *prev;// 前置节点
struct listNode *next;// 后置节点
void *value;// 节点存储的值
}listNode
双向链表linkedlist图示
(3)、linkedlist性能分析
(1)、list拥有head头指针和tail为指针，所以在链表的头部或尾部进行插入操作的时间复杂度为O(1)。
(2)、list自带保存链表长度的字段len，使得获取链表长度的时间复杂度为O(1)。
(3)、listNode拥有prev前驱指针和next后继指针，因此通过迭代器可以很方便的对链表从从头至尾或从尾至头遍历；
3、quicklist（快速列表）
(1)、简单介绍
Redis 3.2版本之前，List列表数据结构底层使用的是压缩列表ziplist和双向链表linkedlist，元素小并且少时用ziplist，元素大并且多时用linkedlist。
考虑到链表的附加空间相对太高，prev和next指针就要占去16个字节 (64bit 系统的指针是8个字节)，造成内存不必要的浪费，另外每个节点的内存都是单独分配，会加剧内存的碎片化。在版本3.2之后对LIst列表数据结构进行了改造，使用quicklist代替了ziplist和linkedlist。
(2)、基本结构
quicklist是ziplist和linkedlist的混合体，它将linkedlist按段切分，每一段使用ziplist来紧凑存储，多个ziplist之间使用双向指针串接起来。
struct quicklist {
quicklistNode* head;// 头节点
quicklistNode* tail;// 尾节点
long count; // quicklist存储元素的总数，即所有ziplist的entry个数之和，total count of all entries in all ziplists
int nodes; // quicklist节点的个数，即ziplist的个数
int compressDepth; // LZF算法压缩深度
...
}
struct quicklistNode {
quicklistNode* prev;// 前置节点
quicklistNode* next;// 后置节点
ziplist* zl; // 如果当前节点的数据没有压缩，那么它指向一个ziplist结构，否则，它指向一个quicklistLZF结构
int32 size; // ziplist占用的字节总数
int16 count; // ziplist中的元素数量
int2 encoding; // 表示ziplist是否压缩了，目前有两种取值，2表示被压缩了（用的是LZF压缩算法），1表示没有压缩
...
}
// quicklistLZF结构表示一个被压缩过的ziplist。
typedef struct quicklistLZF {
unsigned int sz; // 表示压缩后的ziplist大小
char compressed[];
} quicklistLZF;
struct ziplist {
...
}
4、hashtable（哈希表）
(1)、简单介绍
dict（就是我们讲的hashtable）是Redis服务器中出现最为频繁的复合型数据结构，除了hash基本数据结构会将其作为底层实现，整个 Redis 数据库的所有 key和value也组成了一个全局字典，还有带过期时间的key 集合也是一个字典。zset集合中存储value和score值的映射关系也是通过dict结构实现的。
它和Java中HashMap比较相似，却又另有不同。
(2)、基本结构
// 字典的主操作类，对dictht结构再次包装
typedef struct dict {
dictType *type;// 字典类型
void *privdata;// 私有数据
dictht ht[2];// 一个字典中有两个哈希表，ht[0]和ht[1]，类型是dictht
long rehashidx;// ehash的标记，rehashidx==-1，表示没在进行rehash
int iterators;// 当前正在使用的迭代器的数量
} dict;
// 哈希表结构
typedef struct dictht {
dictEntry **table;// 散列数组，类似Java中的HashMap，由数组+Entry链表组成
unsigned long size; // 散列数组的长度
unsigned long sizemask;// sizemask等于size减1
unsigned long used;// 散列数组中已经被使用的节点数量
} dictht;
// 存键值（key - value）对的结构体，类似于Java中HashMap的Entry
typedef struct dictEntry {
void *key;// 键key
// 值value
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;// 指向下一个dictEntry的指针
} dictEntry;
// 定义了字典操作的公共方法，将对节点的公共操作方法统一定义
typedef struct dictType {
unsigned int (*hashFunction)(const void *key);// hash方法，根据关键字计算哈希值
void *(*keyDup)(void *privdata, const void *key);// 复制key方法
void *(*valDup)(void *privdata, const void *obj);// 复制value方法
int (*keyCompare)(void *privdata, const void *key1, const void *key2);// 关键字比较方法
void (*keyDestructor)(void *privdata, void *key);// 销毁key方法
void (*valDestructor)(void *privdata, void *obj);// 销毁value方法
} dictType;
上面用代码演示了字典的结构，你可能看的头昏脑胀，下面用示意图进行描述，可能会好一些。
(3)、渐进式rehash
当字典容量不够的时候，需要对其进行扩容，扩容就涉及到rehash操作。
rehash操作步骤如下：
1.扩展备用的ht[1]，例如将它的容量扩张到ht[0]大小的两倍。2.将ht[0]中的值重新经过hash之后迁移到ht[1]上。3.释放ht[0]，将ht[1]设为ht[0]，创建新的空表ht[1]。
这个过程看似简单，但是第二步涉及大量的数据拷贝，如果一次性把ht[0]中的数据都迁移完，这是一个 O(n)级别的操作，作为单线程的Redis很难承受这样耗时的过程，会造成Redis线程阻塞，无法服务其他请求，此时，Redis就无法快速访问数据了。
为了避免这个问题，Redis 采用了渐进式 rehash。
渐进式rehash过程：简单来说就是在第二步拷贝数据时，Redis仍然正常处理客户端请求，每处理一个请求时，从ht[0]中的第一个索引位置开始，顺带着将这个索引位置上的所有entries拷贝到ht[1]中；等处理下一个请求时，再顺带拷贝ht[0]中的下一个索引位置的entries。如下图所示：
在rehash期间，所有新增字段添加在ht[1]中，而删除、更新操作会在两个表上同时进行，查找时先找ht[0]，再找ht[1]。
(4)、set集合使用字典作为底层实现
Redis里面set集合数据结构，当底层实现无法满足intset的条件时，Redis会使用字典作为set集合的内部实现，只不过所有的value都是 NULL，其它的特性和字典一模一样。
5、intset（整数集合/整数数组）
(1)、简单介绍
intset整数集合是Redis用于保存整数值的底层数据结构，它可以保存类型为int16_t、int32_t或者int64_t的整数值，并且保证集合中不出现重复值。
(2)、基本结构
typedef struct intset{
uint32_t encoding;//编码方式
uint32_t length;// intset(整数集合)包含的元素的数量
int8_t contents[];// 保存元素的数组
}intset;
encoding：contents数组中元素的类型，有INTSET_ENC_INT16、INTSET_ENC_INT32和INTSET_ENC_INT64三种，分别表示contents数组中元素类型为 int16_t（16位二进制）、int32_t 和 int64_t 类型。 length：记录了intset(整数集合)包含的元素数量，也即contents数组的大小。 contents：intset整数集合的每个元素都是contents数组的一个数组项，各个数据项在数组中按值的大小从小到大有序地排列，数组中不包含重复项。
(3)、intset整数集合的升级和降级
(a)、升级
如果我们想要添加一个新元素到intset整数集合里面，但是新元素的类型比整数集合原有的元素类型都要长时，我们就要对整数集合进行升级，然后才能将新元素添加到整数集合里面。
升级整数集合并添加新元素共分为三步进行：
1.根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间。
2.将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素继续维持底层数组的有序性质不变。
3.将新元素添加到底层数组里面。
intset整数集合升级图示
(b)、降级
整数集合不支持降级操作，一旦对数组进行了升级，编码就会一直保持升级后的状态。
6.skiplist（跳跃表）
(1)、简单介绍
Redis的zset是一个复合结构，内部实现是一个hash字典(类似于 Java 语言中的 HashMap 结构)加一个跳跃列表(skiplist)。
使用hash字典存储value和score的映射关系。 使用跳跃表提供按照score进行排序的功能，以及指定score的范围来获取value列表的功能。
zset底层数据结构
(2)、基本结构
typedef struct zskiplist {
struct zskiplistNode *header;// 头节点
struct zskiplistNode *tail;// 尾节点
unsigned long length;// 跳跃表目前包含节点的数量（表头节点不计算在内）
int level;// 层数最大的那个节点的层数（表头的层数不计算在内）
} zskiplist;
// 跳跃表节点
typedef struct zskiplistNode {
sds ele;// 见下图各个节点中的o1、o2、o3，是节点保存的成员对象
double score;// 见下图各个节点中1.0、2.0、3.0，是节点保存的分值，在跳跃表中节点按照各自保存的分值从小到大排列
struct zskiplistNode *backward;// 后退指针，使得跳表第一层组成一个双向链表，后退指针在从表尾向表头遍历时使用
// 每一个结点的层级
struct zskiplistLevel {
struct zskiplistNode *forward;// 前进指针
unsigned int span;// 当前节点距离下一个节点(forward指向的节点)之间跨过的节点数量
} level[];
} zskiplistNode;
上图为ziplist跳跃表的示意图，图中只画了3层(1、2、3)，实际上，Redis 的跳跃表共有 64 层，意味着最多可以容纳 2^64 次方个元素。
节点使用指针串起来形成了双向链表结构，它们是有序排列的，从小到大，score值小的排在前面，score值大的排在后面。
(3)、skiplist的操作
(a)、查找操作
跳跃列表主要是为了解决链表，插入删除操作效率低下的问题，为什么这么说呢？
链表的查找、插入和删除操作，需要从头节点开始遍历，遍历到指定的节点（插入节点的位置、要删除的节点），时间复杂度是O(n)。也许你会想到二分查找，但是二分查找的结构只能是有序数组。
链表查找操作示意图
有了跳跃列表这个多层结构之后，这个定位的算法时间复杂度将会降到O(lg(n))。
skiplist查找操作示意图
如图所示，我们要定位到那个紫色的节点，需要从header开始遍历找到层数比header较低的节点（所有比header低的节点中最高的那个节点，图中3层那个节点），然后从这个节点开始降一层再遍历找到第二个节点（图中2层那个节点），然后一直降到最底层进行遍历就找到了期望的节点（图中的紫色节点）。
我们将中间经过的一系列节点称之为“搜索路径”，它是从最高层一直遍历到最底层。
(b)、插入操作
插入新节点时，首先需要找到合适的插入点，类似于查找过程把这个“搜索路径”找出来。找到合适节点之后就可以开始创建新的节点，创建时需要为节点随机分配一个层数，再将搜索路径上的节点和新节点通过前后指针进行串接。
如果分配的新的节点比当前跳跃表最大高度高的话，需要更新一下跳跃表的最大高度，即zskiplist的level属性。
(c)、删除操作
删除操作和插入操作类似，需要先找到要删除的节点，类似于查找过程把这个“搜索路径”找出来。然后对于每一个层的相关节点，都需要重排一下前后指针，同时注意更新一下最高层数level。
(d)、更新操作
当我们调用zadd方法时，如果对应的value不存在，那就是插入操作。如果这个
value已经存在了，只是调整一下score的值，需要进行更新操作。
如果这个新的score值不会带来节点排序位置上的改变（节点是根据score值进行排序的），那么就不需要调整位置，直接修改节点的score值就可以了。但是如果排序位置改变了，那就要调整该节点的位置。
如何调整节点的位置呢？Redis在更新节点位置时，采用先删除这个节点，再插入这个节点的方法，这样就不需要判断是否需要调整位置，只需要进行两次路径搜索即可。
(e)、计算元素排名
zset可以使用rank获取元素排名，主要是因为Redis在skiplist的forward指针上进行了优化，给每一个forward指针都增加了span属性，span是“跨度”的意思，表示从前一个节点沿着当前层的forward指针跳到当前这个节点中间会跳过多少个节点。Redis 在插入删除操作时会小心翼翼地更新span值的大小。
这样当我们要计算一个元素的排名时，只需要将“搜索路径”上的经过的所有节点的跨度span值进行叠加就可以算出元素的最终rank值。
