Redis设计与实现-1.数据结构（1）

简单动态字符串SDS

SDS属性

• free：表示SDS分配空间中没有使用的数量
• len：表示SDS保存的字符串的长度
• buf：char类型的数组，存储具体字符，最后一个字节保存了空字符‘\0‘。

SDS的字符串以空字符结尾，保存空字符的1字节空间空间不计算在SDS的len属性中。在分配字符串SDS空间的时候，会把1字节的空间算进去。

SDS特性

　　1.获取时间复杂度O(1)

SDS字符串中len保存了字符串的长度，所以获取SDS的时间复杂度是O(1)。如果不知道长度，那么获取字符串就要找到字符串的结尾，来获取字符串数据。

　　2.杜绝缓冲区溢出

SDS在修改前，先会判断字符串空间是否满足修改所需要的要求，如果不满足的话，会先将空间拓展至执行修改所需要的大小，然后进行修改操作。

　　3.减少修改字符串带来的内存重新分配次数

1）空间预分配：优化SDS字符串增长操作，不光对SDS修改内容进行内存分配，也会给SDS额外的内存空间。

• 如果SDS修改后，SDS长度将小于1MB，那么程序会分配和len属性同样大小的未使用空间，这时候SDS的len属性和free属性的值相同。SDS修改后的空间大小为 len+free+1。（free=len）
• 如果SDS修改之后，SDS长度大于等于1MB，那么程序会直接分配1MB的未使用空间。举例当SDS修改后的len为20MB，那么程序分配后的长度为 20MB+1MB+1byte。
  

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需要的内存重分配次数。

2）惰性空间释放：优化SDS字符串缩短操作，当SDS需要缩短SDS保存的字符串时候，程序并不会立即使用内存重新分配来回收缩短后的字节，而是使用free属性将这些字节数量记录下来。与此同时，SDS提供了相应API，让我们在需要的时候，真正的释放未使用空间，所以不需要担心惰性空间释放策略会造成内存浪费。

　　4.二进制安全

SDS的API都是以处理二进制的方式来处理SDS存放在buf数组里面的数据，不会对数据进行限制和过滤。二进制安全的SDS，使Redis不仅可以保存文本数据，还可以保存任意二进制数据。

　　5.兼容部分C字符串函数

链表

每个链表节点都是一个listNode结构，多个ListNode节点通过前后指针组成了双端链表。listNode结构如下：

• listNode prev：前指针
• listNode next：后指针
• value：节点的值

字典

字典是一种保存键值对的抽象数据结构。Redis的字典使用哈希表作为底层实现，一个哈希表里面有多个哈希表节点，而每个哈希表节点就保存了字段中的一个键值对。

哈希表

• dictht代表一个字典，
• table属性是一个数组，
• size为属性记录了哈希表大小（table数组大小），
• used记录了目前已有节点的数量，s
• izemask属性的值总是为size-1。

sizemask和哈希值一起决定一个键应该被放到table数组的那个索引上面。

哈希表节点

• key属性保存着键值对中的键
• v属性保存这键值对中的值，值可以是一个指针，或者是一个uint64_t的整数，或者是一个int64_t的整数。
• next属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的简直对连接在一起，以此来解决键冲突的问题。

字典

• type属性是一个指向dictType结构的指针
• privdata属性保存了需要传给那些类型特定函数的可选参数
• ht属性是一个包含两个项的数组，数组的每个项都是一个dictht哈希表，一般只使用ht[0]，ht[1]是在对ht[0]进行rehash的时候使用。
• rehashidx属性记录了rehash目前的进度，没有进行rehash的时候值为-1。

解决键冲突

Redis的哈希表使用链地址法解决键冲突。

Rehash

随着操作不断执行，哈希表保存的键值对会慢慢增多或者减少，为了让哈希表的负载因子维持在一个合理的范围内，当哈希表的键值对数量太多或者太少时，程序会对哈希表的大小进行相应的扩展和收缩。扩展和收缩哈希表的工作可以通过rehash操作完成。步骤如下：

1. 为字典ht[1]分配空间，分配空间大小取决于扩展操作还是收缩操作。扩展操作ht[1]大小为第一个大于等于ht[0].userd*2的2的n次幂。收缩操作ht[1]的大小为第一个大于等于ht[0].used的2的n次幂。
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上。rehash指的是重新计算键的哈希值和索引值，然后将键值对放在ht[1]哈希表的指定位置上。
   
3. 当ht[0]包含的所有值都迁移之后，释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新创建一个空白哈希表，为下一次rehash作准备。

渐进式rehash

 rehash动作不是一次性、集中式地完成，而是分多次、渐进式地完成的。具体过程如下：

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表。
2. 在字典中维持一个索引计数器变量rehashidx，并将他的值设置为0，表示rehash工作正式开始。
3. 在rehash期间，每次对字典进行添加、删除、查询或者更新操作时，程序除了执行指定操作外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1]，当rehash工作完成后，程序会将rehashidx属性的值增1。
4. 随着不断执行操作，在某一个时间，ht[0]的所有键值对都会被rehash到ht[1]，这是程序将rehashidx属性的值设为-1，表示rehash操作完成。

渐进式rehash执行期间的哈希表操作

字典里面查询一个键，先从ht[0]里面进行查询，如果没有，就会继续到ht[1]进行查询。

字典里面添加一个键值对一律会保存到ht[1]里面，而ht[0]则不再进行任何添加操作。保证了ht[0]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。