大纲
一.Redis的数据结构
二.Redis的数据库原理
三.Redis的复制原理
四.Redis的哨兵原理
五.Redis的集群原理
深入了解其数据结构、数据库、复制、哨兵、集群的实现原理，对其在不同场景下的应用和相关问题的解决方案有丰富经验。
一.Redis的数据结构
1.Redis的数据结构
2.Redis的SDS
3.Redis的链表
4.Redis的字典
5.Redis的跳跃表
6.Redis的整数集合
7.Redis的压缩列表
8.Redis的对象
9.Redis的单线程为什么这么快
1.Redis的数据结构
数据结构有：简单动态字符串SDS、链表、字典、跳跃表、整数集合、压缩列表。
2.Redis的SDS
SDS除了用来保存Redis的字符串值外，AOF缓冲区、客户端状态中的输入缓冲区都是由SDS实现的。SDS会通过空间预分配和惰性空间释放，减少修改字符串带来的内存重分配次数。
//sdshdr的结构
int len;//SDS保存字符串的长度，占4个字节
int alloc;//数组中未使用的字节数，占4个字节
char buf[];//保存字符串的字节数组 + 分割符"\0"占一个字节空间预分配用于优化SDS增长操作，具体来说就是扩展SDS时，分配额外的未使用空间。如果SDS长度小于1MB，则分配和len属性同样大小的未使用空间，即buf数组长变为：2len + 1。如果SDS长度大于1MB，则分配1MB的未使用空间。通过空间预分配，在扩展SDS空间之前，如果未使用空间足够，则无需执行内存空间重分配。这样SDS将连续增长N次字符串所需的内存重分配次数从N次降为最多N次。
惰性空间释放就是缩短SDS时，不立即使用内存重分配来回收多出的字节，而是使用alloc属性记录起来将来使用。
3.Redis的链表
发布与订阅、慢查询 、监视器、保存多个客户端状态(redisClient)、构建客户端输出缓冲区、列表键，都用到了链表。
//listNode的结构如下：listNode *prev; //前置结点
listNode *next; //后置结点
void *value; //结点值//list的结构如下：listNode *head; //表头结点
listNode *tail; //表尾结点
long len; //链表包含结点数量每个链表结点由一个listNode结构表示。每个结点都有一个指向前置结点和后置结点的指针，所以Redis的链表是双端链表。每个链表使用一个list结构表示，这个结构带有表头指针、表尾指针以及链表长度等信息。因为链表表头结点的前置结点和表尾结点的后置结点都指向NULL，所以是无环链表。
4.Redis的字典
Redis的数据库就是使用字典作为底层实现的，Redis的哈希键也使用了字典作为底层实现，其中Redis的字典是使用哈希表作为底层实现的。
(1)哈希的结构和算法
//dict字典的结构如下：dictht ht[2]; //哈希表数组
int rehashidx; //rehash索引//dictht哈希表的结构如下：dictEntry **table; //哈希结点数组
long size; //哈希表大小
long used; //哈希结点数量
long sizemask; //哈希表大小掩码，用于计算索引值//dictEntry哈希结点的结构如下：void *key; //键，8字节
union v; //值，8字节
dictEntry *next; //下一个结点，8字节说明一：ht属性通常使用ht[0]，rehash时使用ht[1]
说明二：rehashidx属性用来实现渐进式rehash
说明三：next属性是指向另一个哈希表结点的指针，这个指针可以将多个哈希值相同的键值对连接在一起，以此来解决哈希冲突的问题
Redis使用MurmurHash2算法来计算键的哈希值，该算法速度快，而且有很好的随机分布性。Redis的哈希表使用链地址法来解决键冲突。每个哈希表结点都有一个next指针，多个哈希表结点可以用next指针构成一个单向链表。被分配到同一个索引上的多个结点，可以用单向链表连接起来，并且会使用头插法将新结点加到链表中，以更快完成插入。
(2)rehash的步骤
步骤一：为字典的ht[1]哈希表分配空间
如果是扩展操作，那么ht[1]大小等于ht[0].used * 2^n，如果是收缩操作，那么ht[1]大小等于ht[0].used * 2^n。
步骤二：将保存在ht[0]中的所有键值对rehash到ht[1]上
步骤三：ht[0]所有键值对迁移到ht[1]后释放ht[0]
然后将ht[1]设为ht[0]，在ht[1]新建空哈希表。
(3)渐进式rehash
为避免rehash对服务器性能造成影响，服务器不是一次性将ht[0]里所有的键值对全部rehash到ht[1]上，而是分多次、渐进式、分而治之地将ht[0]里面的键值对慢慢rehash到ht[1]。
将rehash键值对所需的工作均摊到对字典的每个添加、删除、查找和更新操作上，从而避免集中式rehash而带来的庞大计算量。
字典中维持的索引计数器变量rehashidx，记录了正在rehash到的索引。在rehash被触发后，即使没有收到新请求，Redis也会有定时任务触发rehash操作，而且每次不超过1ms。
在渐进式rehash进行期间，字典会同时使用ht[0]和ht[1]两个哈希表。字典的删除、查找、更新操作会在两个哈希表上进行，而新增操作会在ht[1]进行。
5.Redis的跳跃表
跳跃表通过在每个结点中维持多个指向其他结点的指针，达到快速访问结点的目的。Redis只有两个地方用到跳跃表，一个是实现有序集合键，另一个是集群节点中根据槽批量获取键。
(1)跳跃表的结构
//zskiplist跳跃表的结构如下：header: 指向跳表的表头结点
tail: 指向跳表的表尾结点
level: 层数最大的结点的层数(表头结点不算)
length: 跳表长度，即结点数量//zskiplistNode跳跃表结点的结构如下：*backward: 后退指针
score: 分值
obj: 成员对象
zskiplistLevel: 层数组//zskiplistLevel的结构如下：*forward: 前进指针
span: 跨度(2)跳跃表的图示
(3)跳跃表的说明
遍历操作只用前进指针就可以了。比如从跳跃表的表头结点的第一层出发L1，表头L1会指向第一个结点的指针，到第一个结点的L1会指向第二个结点的指针，定位到第二个结点后，从其L1又可以获取第三个结点的指针，依此类推。
节点的后退指针用于从表尾开始向表头方向访问结点。跳跃表中所有结点都按分值从小到大排序，多个结点包含相同分值，每个跳跃表节点的层高都是1~32之间的随机数。
6.Redis的整数集合
整数集合的底层实现为数组，这个数组以有序、无重复方式保存集合元素。在有需要的时候，程序会根据新添加元素类型，改变这个数组的类型。
整数集合的升级操作为整数集合带来了操作上的灵活性，并且尽可能节约内存。
//intset的结构如下：encoding; //编码
length; //数量
contents[]; //元素7.Redis的压缩列表
压缩列表是Redis为了节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型数据结构。一个压缩列表可以包含任意多个节点，每个节点可以保存一个字节数组或者一个整数值。
(1)压缩列表的结构
//压缩列表的结构如下：zlbytes: 整个压缩列表内存字节数，4字节，可以理解为列表长度
zltail: 压缩列表尾结点距离起始地址有多少字节，4字节，可以理解为列表尾偏移量
zlen: 压缩列表结点数量，2字节，可以理解为列表结点个数
entryx: 压缩列表的结点
zlend: 标记压缩列表末端，1字节//压缩列表结点的结构如下：previous_entry_length: 前一个节点长度，实现表尾到表头的遍历，占1或5个字节
encoding: 记录数据类型和长度，占1字节
content: 保存结点的值(2)压缩列表产生连锁更新的原因
若前一节点的长度小于254字节，那么previous_entry_length属性占一个字节长。若前一节点的长度大于等于254字节，那么previous_entry_length属性占5个字节长。所以添加新节点或者删除节点可能会引起连锁更新，也就是引发多个结点更新。
连锁更新最坏的情况要对压缩列表进行N次空间重分配操作，而每次空间重分配最坏的时间复杂度为O(N)，所以连锁更新最坏的时间复杂度为O(N^2)。
实际上尽管连锁更新复杂度高，但真正造成性能问题的几率很低。原因一是：压缩列表恰好有多个连续、且长度介于250～253字节的结点，连锁更新才可能被引发。原因二是：即便出现连锁更新，只要被更新的结点数量不多，也不影响性能。Redis的List、Hash、Sorted Set使用压缩列表作为底层实现时，会要求其元素大小要小于64字节及元素个数小于512。
(4)压缩列表总结
它是一种为节约内存而开发的顺序型数据结构。它会被用作List、Hash和Sorted Set的底层实现。它可以包含多个结点，每个结点可以保存一个字节数组或整数值。添加新结点或删除结点，可能会引发连锁更新操作，但几率不高。
整数数组和压缩列表在查找时间复杂度并没有很大优势，为什么Redis还用？
因为这体现了Redis"又快又省"中的省，即节省内存空间。两者都是在
