这是我参与8月更文挑战的第7天，活动详情查看：8月更文挑战

string的替身-sds

内存申请和释放

我们知道内存都是一小块一小块拼在一起的，当我们要给一个变量赋值的时候，得先申请一块容的下变量的内存。

假设我们现在要var db=redis，前提我们得先malloc(5)个字节的空间，当我们申请到了5个空间后，我们就可以给db赋值了。

现在情况有变，我要把db=redis 改成 db=memcache，这时我们可以发现还需要3个空间，所以我们只要申请3个空间？计算机可没这么智能，这时我还是得申请8个空间malloc(8)。

当我们的db变量变成了memcache后，还得回收原来redis空间。

总结：一整套下来，我们大概的流程是 先malloc(5)给redis，然后malloc(8)给memcache，最后还要free(5)回收redis，总共两次申请内存。当我们的变量变了n次，那么对应的就要申请n次 同时释放n-1次

登场

由于上面的流程导致不停的malloc和free，于是redis的开发者发明了sds，当我们执行 set key value的时候， key对应一个sds结构， value也对应一个sds结构。它的结构大致如下：

struct sdshdr {
    int len;
    int free;
    char buf[];
};

• free：sds还剩多少空间
• len：字符串长度
• buf：真正存储的值 看个例子：

多分配空间

假设现在有个key=redis，且此时它正好用完空间free=0，len=5。

每个字符串的结尾都是\0结束的，这样就知道读到哪该停止了，所以sds真正的占用空间，是字符串占用的空间加上1个字节。 现在执行set key memcache，我们知道key已经没有空间了，于是要去申请更多的内存，但是这里并不是只要申请8个字节的空间，而是申请16个字节的空间，并且此时free=8 和 len=8。这就是redis sds的策略，当空间不够时，申请空间时会是扩容后的2倍，但是当扩容后的空间大于1M后，那么会固定过申请1M的额外空间，这一点是需要注意的。 现在又执行set key memcacheGood，发现free还有8个字节的空间，说明空间够用，那么就不用去申请空间了，sds的好处就体现出来了。

保留多余空间

当memcacheGood又改成memcache时，多出来的4个字节，redis也不会把它还回去，而是会保存起来。

总结

redis sds就是通过这种冗余空间来减少内存的申请和释放过程，从而提升速度，但是缺点就是耗内存。

压缩列表-ziplist

我们知道对于一个数组来说，它们在内存中是连续的，这种设计可以很好的利用cpu缓存，访问快速。但是数组有一个缺点：每个元素的大小都是相同的，即使一些元素只需要很小的空间。

例如1，2，3，4其实用一个字节int8表示就行了，但是999很明显就不够用了，至少int16。于是因为999，1，2，3，4也得用int16类型，这样就造成了空间浪费。 但是如果每个元素都用最短长度，那么cpu就不知道怎么读了（每次读几个字节？）： 这样好办，我们可以为每个元素加一个长度，这样就知道每次读取多少长度了。

于是redis的压缩列表（ziplist）出现了。压缩列表是一种为节约内存而开发的顺序型数据结构，压缩列表被用作列表键和哈希键的底层实现之一，压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值，当列表或者哈希的元素数量不多且元素是小整数值或者短字符串，那么底层就会用ziplist来存储。ziplist结构如下：

其中每个entry都是由previous_entry_length、encoding、content三个组成。

• previous_entry_length：前一个节点的长度，可以是1个字节或者5个字节，如果前一个节点长度小于254字节，就为1，否则为5。通过previous_entry_length可以知道前一个节点的地址（当前地址减去previous_entry_length）。
• encoding：节点的encoding属性记录了节点的content属性所保存数据的类型以及长度。

1. encoding是一字节、两字节或者五字节长时，值的最高位为00、01或者10的是字节数组编码：这种编码表示节点的content属性保存着字节数组，数组的长度由编码除去最高两位之后的其他位记录；
2. encoding是一字节长时，值的最高位以11开头的是整数编码：这种编码表示节点的content属性保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他位记录。

• content：节点的值。

1. 高位00表示 content是一个字节数据，后6位010011等于11，表示content的长度
2. 11表示是个数字

总结

压缩列表是一种为节约内存而开发的顺序型数据结构，压缩列表被用作列表键和哈希键的底层实现之一，压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值，当列表或者哈希的元素数量不多且元素是小整数值或者短字符串底层就会使用ziplist。

hash表

在redis中不仅仅是数据类型为hash的才用到hash结构，redis本身所有的k、v就是一个大hash。例如我们经常用的set key value，key就是hash的键，value就是hash的值。

当添加一个新key的时候，会根据hash函数先算出应该落在哪个桶中，当发现要存放桶中已经有元素了，那么这就是hash冲突，对于hash冲突，redis也是用链表的方式来解决的，但是redis解决hash冲突的链表并不存在指向表尾的指针，那么如果将新加的元素添加在表尾，获取它的时间复杂度将是O(N)，一般新添加的元素在接下来将会被访问的概率还是比较大的，于是对于冲突，新加的元素会被添加到表头。 当hash表元素越来越多，会出现冲突越来越多，那么查询效率会降低。当hash表元素越来越少，会出现hash表中有的桶没数据，造成浪费。这就涉及到hash表的扩容和缩容。

1. 0号桶元素太多，这样当查找kn的时候，时间复杂度将趋近O(N)
2. 0和2号桶是空桶，那么它们就是多余的 对redis本身来说，其实它在一开始就有两个hash表（h1和h2），只不过只有h1是对外工作的，h2是随时准备rehash的。在没有发生rehash的时候，h2是空的。当发生rehash的时候，h2的空间大小取决于h1中键值对的数量。

rehash的依赖：负载因子=哈希表已保存节点数量/哈希表大小

• 扩容：当服务此时没有执行bgsave或bgrewriteaof时，负载因子大于等于1，就扩容。当服务此时正在进行bgsave或bgrewriteaof时，负载因子大于等于5，就扩容。且h2的大小等于第一个大于等于h1键值对数量2倍的2^n。

• 缩容：当负载因子小于0.1时就开始缩容，且h2的大小等于第一个大于等于h1键值对数量的2^n。 触发时机：serverCron周期性检测或每次新增k、v的时候，重新计算将h1的键值对慢慢迁移到h2上，当迁移完毕后，h1就是空的了，这时会把h2变成h1，h1变成h2。

为啥执行bgsave或bgrewriteaof的时候，要提高负载因子？ 我们知道bgsave或bgrewriteaof本身是一个耗时的工作，不能卡主线程，所以redis的做法是fork一个子进程来做，子进程这时不是复制一份新的数据内存，而是和父进程共享一份内存，这就是现代操作系统支持的cow（copy-on-write）机制，这种机制的好处就是节约内存，既然大家都一样的，为什么要复制内存？杜绝浪费。但是当主进程在fork后，发生了写的操作，这时候子进程该怎么办？复制整块内存？当然也不是，计算机的内存也是页式存储，内存是由一块一块的页组成，当主进程发生了写的时候，我们只需要把变更的那一页复制一下，其余页不变是不是就可以了，这样可以达到节约内存的目的。cow主要依赖页异常中断来做的，当父进程fork子进程后，会把所有的页设置成只读，那么当新的写到来时就会触发页异常中断，这时候就会对这个页进行单独的复制。hash扩容的时候，肯定是会发生写的，这样就会造成大量的页复制，所以要提高负载因子，尽量不同时操作。

渐进式的rehash 当redis的k、v比较少的时候，可能一次性rehash没什么问题。但是当redis包含大量的k、v时，cpu的计算量就上去了，那么此时一次性rehash是不现实的。为了避免rehash对服务本身造成影响，rehash并不是一次性完成的而是多次的执行rehash的。

• hash的更新、查找、删除可能会在两个hash表中都执行一次，比如查找的时候，先查找h1，如果没找到，那么会接着找h2。对于新增的操作，会直接在h2上操作。
• serverCron执行的时候，每次会给永久的kv分配1ms的时间来rehash，给带过期时间的kv也分配1ms的时间来rehash。 rehash过程移动的是指针，所以移动1kb和1mb的value是没什么区别的

总结

hash是redis中用的比较多的数据结构，渐进式rehash是redis的一种高性能体现。

跳跃表

redis的有序集合zset，在某些场景下非常好用，比如学生成绩排序，最近活跃用户等等。它的底层实现就是跳跃表，跳跃表的好处就是可以加速访问某些节点。

1. 当没有跳跃表的时候，我们要访问7的话，必须是1->2->3->4->5->6->7，一共7步
2. 当我们在1、4、7上再加一层，那么访问7的话，可以是1->4->7，一共3步 跳跃表的实现就是和上图的2一样的，每个节点有不同的层，通过层来加速访问其他节点，实现了跳跃。层越高，理论访问的越快，但是占用的空间越大，典型的空间换时间。

跳跃表的特点

我们看看跳跃表是如何找到20这个节点的，首先从最高层开始检索，20大于1继续向后找，20大于12，但是20小于38，于是从12往下找，发现右边还是38，于是12接着往下找，发现右边就是20，结束。

• 每个节点至少都有1层
• 每层都是一个有序链表
• 最底层的有序链表保存所有数据
• 如果一个节点出现在第x层，那么x-1层也会出现
• 每个节点包含两个指针，一个指向右边，一个指向下边

redis的跳跃表 我们来看看redis的zset结构：

1. header：指向表头节点，redis zset在初始化的时候会创建一个层数为 32，分数为 0，没有 value值的跳跃表头节点
2. tail指向表尾节点
3. level：层高，除表头节点外，最高的那一层
4. length：数量，除表头节点外，节点的数量
5. 跨度：可以用于表示一个节点在集合中的排位
6. 后退指针：每个节点都有一个后退指针
7. 分值：即权重，决定排序
8. 成员：指向每个节点对象的指针，对象保存的是一个SDS值

总结

每当新加一个节点的时候，redis会随机一个层高。相比链表查询的时间O(N),跳跃表最坏的时间复杂度是O(N)，支持平均的时间复杂度O(logN)。