redis的底层原理

1. String：

　　C语言字符串的缺陷：在c语言中，对字符串操作时，char* 指针只是指向字符数组的起始位置，而字符数组的结尾位置就用/0表示，意思是指字符串的结束

　　1. 获取长度需要 O(n)         （SDS 是O(1)解决的）

　　2. 除了字符串的末尾之外，字符串里面不能有”/0“字符，不能保存像图片、音频、视频这样的二进制数据      （SDS除了最后末尾为/0,中间也可以有/0，因此是可以存储二进制的）

　　3. C语言标准库中字符串的操作函数是很不安全的，会导致缓冲区溢出： 怎么理解呢？

　　　　c语言的字符串是不会记录自身的缓冲区大小的，例如在执行strcat（dest，src）函数时假定程序员在执行这个函数时，假设已经为dest分配了足够多的内存，可以容纳被拼接的字符串中的所有内容，一旦这个假定不成立，就会发生缓冲区溢出。   （预分配机制解决的）

　　redis通过SDS来表示String字符串：　　

　　Redis的字符串对象： 一般包含两各对象，第一个对象是redisObject, 第二个对象是存放地址的对象

　　　　1. embstr：

　　　　2. raw： 原生格式

 　　　　3. INT类型：

2. List：

　　原本的数据结构为：双向链表

　　redis的双向链表是在其基础上添加了 头节点、尾节点以及节点数。  缺点也很明显（空间不连续，无法很好利用CPU缓存，能很好利用CPU缓存的数据结构就是数组。因此需要压缩列表来搞定）

　　ziplist：它被设计成一种内存紧凑型的数据结构，占用一块连续的内存空间，不仅可以利用CPU缓存，而且会针对不同长度的数据，进行相应的编码，这种方法可以有效节省开销。  

　　压缩列表的缺陷：

　　　　1. 不能保存过多的元素，否则查询效率降低

　　　　2. 新增或修改某个元素时，压缩列表占用的内存空间需要重新分配，甚至可能引发连锁更新的问题。

　　　　因此，Redis对象(List 对象，Hash对象，Zset对象)包含元素较少时，或者元素值不大情况才会使用压缩列表作为底层数据结构。

　　ziplist有一大缺陷： 连锁更新

　　　　一个Entry 分为三段  previous_entry_length (前面元素的长度)、 encoding(编码)、content(”内容“)  

　　　　长度是可变的，如果前面的长度为254的话，那么用一个字节来表示，如果大于254就用5个字节来表示，这就有可能造成连锁更新。

　　Redis针对压缩列表在设计上的不足，在后来的版本中，新增设计了两种数据结构： quicklist和listpack。这两种数据结构的设计目标，就是尽可能地保持压缩列表节省内存的优势，同时解决压缩列表的连锁更新的问题。

3. hash数据类型：

　　随着数据逐步增多，触发了rehash操作，这个过程分为三步：

　　　　1. 给哈希表2 分配空间，会比哈希表1 大两倍

　　　　2. 将哈希表1的数据迁移到哈希表2

　　　　3. 迁移完成后，哈希表1的空间会被释放，并把哈希表2设置为哈希表1，然后在哈希表2新创建一个空白的哈希表，为下次rehash做准备。

 　　　第二步有问题，如果哈希表1的数据量非常大，那么在迁移至哈希表2的时候，因为会涉及到大量的数据拷贝，此时可能会对redis造成阻塞，无法服务其他请求。

　　　渐进式rehash

　　　为了避免rehash在数据迁移过程中，因拷贝数据的耗时，影响Redis性能的情况，所以Redis采用了渐进式rehash，也就是将数据的工作不再是一次性迁移完成，而是多次迁移。

　　　渐进式rehash步骤：

　　　　1. 给哈希表2分配空间

　　　　2. 在rehash进行期间，每次哈希表进行新增、删除、查找或者更新操作时，Redis除了会执行对应的操作之外，还会顺序将哈希表1中索引位置上的所有key-value迁移到哈希表2上。  

　　　　随着处理客户端发起的哈希表请求数量越多，最终在某个时间点，会把哈希表1的所有key -value 迁移到哈希表2，从而完成rehash操作。

　　　　在进行渐进式rehash的过程中，会有两个哈希表，所以在渐进式rehash进行期间，哈希表元素的删、查、更新都会在这两个哈希表进行。

　　　　比如，查找一个key的值的话，先会在哈希表1里面进行查找，如果没找到，就会继续到哈希表2里面进行查找。

　　　　在渐进式rehash进行期间，新增一个k-v时，会被保存到哈希表2里面，而哈希表1不再进行任何添加操作，这样保证了哈希表1的k-v只会减少，随着rehash操作完成，最终哈希表会变成空表。

　　　　rehash触发条件：

　　　　rehash的触发条件跟负载因子有关系。

 　　　　触发rehash操作的条件，主要有两个：

　　　　 1. 当负载因子大于等于1，并且Redis没有在执行bgsave命令或者 bgrewriteof命令，也就是没有执行RDB快照或者AOF重写的时候，就会进行rehash操作

　　　　 2. 当负载因子大于等于5时，此时冲突非常严重了，不管有没有在执行RDB快照或者AOF重写，都会强制进行rehahs操作。

整数集合：

　　　　整数集合是set对象的底层实现之一。

 　　　　特点：1. 元素不重复

　　　　　　　 2. 元素有序

　　　　　只支持升级，不支持降级

跳跃表：

　　首先跳跃表是一个链表，链表最大的缺陷就是在查找元素的时候，需要顺序遍历，而跳跃表可以通过近似于二分查找的方式来解决这个问题。

　　跳表是在链表基础上改进过来的，实现了一种多层的有序链表，这样的好处是能快速读定位数据。

Zset 对象是唯一要给同时使用了两个数据结构来实现的Redis对象，这两个数据结构一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效的单点查询：

 　　其中 dict是哈希表，zskiplist 是跳跃表。

　　能支持范围查询，因为它的数据结构设计采用了跳表

　　常数复杂度获取元素权重，这时因为它同时采用了哈希表进行索引。

　　跳表的Entry元素： 这个node就是 一个元素对象，一个分数，一个level数组。

　　这个node指的是

 　　跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为2：1 的情况。

　　具体做法是： 跳表在创建节点的时候，会生成范围[0,1]的一个随机数，如果这个随机数小于0.25，那么层数就增加一层，然后继续生成下一个随机数，直到随机数的结果大于0.25结束。   这样的做法，相当于每增加一层的概率不超过25%，层数越高，概率越低。

接下来讲一讲quicklist：

　　quicklistNode结构体里包含了前一个节点和下一个节点指针，这样每个quicklistNode形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值，而是保存了一个压缩列表，所以quicklistNode结构有个压缩列表的指针。

　　在向quicklist添加一个元素的时候，不会像普通链表那样，直接新建一个链表节点，而是会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到quicklistNode结构里的压缩列表，不能容纳才新建一个新的quicklistNode结构。

　　quicklist会控制quicklistNode结构里的压缩列表的大小或者元素个数，来规避潜在连锁更新风险，但并没有完全解决连锁更新的问题。

listpack

　　quicklist虽然通过quicklistNode 结构里的压缩列表的大小或者元素个数，来减少连锁更新带来的性能影响，但是并没有完全解决连锁更新的问题。

　　因为quicklistNode 还是用了压缩列表来保存元素，压缩列表连锁更新问题，来源于其结构设计，所以要想彻底解决这个问题，需要设计一个新的数据结构。

　　于是，Redis在5.0 新设计一个数据结构叫listpack，目的是替代压缩列表，最大的特点是listpack中每个节点不在包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

　　listpark头包含两个属性，分别记录了listpack总字节数和元素数量，然后listpack末尾也有个结尾标识。

 　　图中的listpack entry就是listpack的节点了。

　　其中listpack entry：

 　　主要包含三个方面内容：

　　　encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码；

　　　data，实际存放的数据；

　　　len，encoding + data的总长度； 

　　　可以看到，listpack没有压缩列表中记录前一个节点长度的字段了，lsitpack只记录当前节点的长度，当我们像listpack加入一个新元素，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

Redis对象：

　　hash数据类型：

　　1. ziplist

　　2. hashtable

　　两个情况，哈希对象所有键值对字符串长度小于64个字节；

　　键值对的数据量小于512个

　　否则就会使用hashtable作为数据存储方式

2. zset有序集合：

　　1. skiplist： 通过分数查元素

　　2. dict          通过元素查分数

　　3. ziplist   当数量比较少的时候使用ziplist