深入 Redis 基础数据结构

Redis 也是 K-V 型数据库，那么为了实现从键到值的快速访问，Redis 使用 hash 表来保存所有的键值对，哈希桶中的元素保存的并不是值本⾝，⽽是指向具体值的指针。这也就是说，不管值是String，还是集合类型，哈希桶中的元素都是指向它们的指针

Redis会对哈希表做rehash操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从⽽减少单个桶中的冲突。

常规rehash

Redis默认使⽤了两个全局哈希表：哈希表1和哈希表2。⼀开始，当你刚插⼊数据时，默认使⽤哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，Redis开始执⾏
rehash，这个过程分为三步：

1. 给哈希表2分配更⼤的空间，例如是当前哈希表1⼤⼩的两倍；
2. 把哈希表1中的数据重新映射并拷⻉到哈希表2中；
3. 释放哈希表1的空间。到此，我们就可以从哈希表1切换到哈希表2，⽤增⼤的哈希表2保存更多数据，⽽原来的哈希表1留作下⼀次rehash扩容备⽤。

但是第⼆步涉及⼤量的数据拷⻉，如果⼀次性把哈希表1中的数据都迁移完，会造成 Redis线程阻塞，⽆法服务其他请求。此时，Redis就⽆法快速访问数据了

渐进式 rehash

在第⼆步拷⻉数据时，Redis仍然正常处理客⼾端请求，每处理⼀个请求时，从哈希表1中的第⼀个索引位置开始，顺带着将这个索引位置上的所有entries拷⻉到哈希表2中；等处理下⼀个请求时，再顺带拷⻉哈希表1中的下⼀个索引位置的entries。这样就巧妙地把⼀次性⼤量拷⻉的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。

底层结构是 SDS （Simple Dynamic String）的数据结构，

struct sds{
    //记录buf数组中已使用字节的数量
    //等于 SDS 保存字符串的长度
    T len;
    //记录 buf 数组中未使用字节的数量
    T allocate;
    //字节数组，用于保存字符串
    char buf[];
}

为什么使用泛型呢，因为当字符串比较短时， len 和 allocate 可以使用 int、short、byte来表示，减少内存的占用 。Redis规定字符串的长度不能超过512M，创建字符串时，len 和 capacity 一样长，不会多分配冗余空间，这是因为大多数场景下，不会使用 append 操作修改字符串。

因为一般需要使用 redis 的场景，redis 中的数据，都会频繁修改，并且对于 redis 这种，追求速度的中间件，一定会尽量减少扩容的次数，因为内存重分配，会极大的占用时间，所以才会通过空间预分配和惰性空间释放这两种优化策略。

字符串在长度（len 值）小于1M之前，扩容空间采用加倍策略，此时 free 和 len 值相同。当长度超过1M之后，为了避免加倍后的冗余空间过大而导致浪费，每次扩容只会多分配1M大小的冗余空间。

当字符串缩短时，redis 并不会立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录下来，并等待将来使用。例如以前的 sds = “hello”，len=5，free 的值为 0, 后面修改为 sds = “he”, 那么 free=3。同样，redis 也会在真正需要内存时，释放 sds 中的未使用的空间，所以惰性空间释放策略不会造成内存浪费。

list 列表数据结构使用的是 quicklist。quicklist 是 ziplist 和 linkedlist 的混合体，它将linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。

为了进一步节约空间，redis 还会对 ziplist 进行压缩存储，使用 LZF 算法压缩，可以选择压缩深度。

dict （字典）结构中包含了两个 hashtable，通常情况下只有一个 hashtable是有值的，但是在 dict 扩容缩容的时，需要分配新的 hashtable，然后进行“渐进式搬迁”，这个时候两个hashtable 存储的分别就是旧的 hashtable 和 新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable成为被使用的。一直反复交替，有点类似与垃圾回收的 survivor 区。

struct dictEntry {
    void* key;
    void* val;
    dictEntry* next;// 链接下一个entry
}

typedef struct dictht {
       // 哈希表数组
       dictEntry ** table;
       // 哈希表大小
       unsigned long size;
       // 哈希表大小掩码，用于计算索引值，总是等于 size - 1
       unsigned long sizemask;
       // 该哈希表已有节点的数量
       unsigned long used;
} dictht;

typedef struct dict {
       dictType *type;
       void *privdata;
       // 内部有两个 dictht 结构
       dictht ht[2];
       long rehashidx; // rehashing not in progress if rehashidx == -1 
       unsigned long iterators; 
   }

在每一次的 hset / hdel 指令会进行搬迁，如果没有指令触发，则会在定时任务中对字典进行主动的搬迁

正常情况下，当 hash 表中的元素的个数等于第一维数组的长度时，就会开始扩容，扩容的新数组是旧数组的2倍。如果 redis 正在做 bgsave时，为了减少内存页的过多分离，redis 不进行扩容，除非当前的hash 表已经满了，元素的个数已经达到了第一维数组长度的5倍，会进行强制扩容。

元素的个数低于数组长度的 10%。

底层也是字典，只不过所有的 value 都是 null。

zset 的内部实现是一个 hash 字典加一个跳跃列表 (skiplist)。

图中只画了四层，Redis 的跳跃表共有 64 层，意 味着最多可以容纳 2^64 次方个元素。每一个 kv 块对应的结构如下面的代码中 的 zslnode 结构，kv header 也是这个结构，只不过 value 字段是 null 值——无效的，score 是 Double.MIN_VALUE，用来垫底的。kv 之间使用指针串起来形成了双向链表结构，它们是有序排列的，从小到大。不同的 kv 层高可能不一样，层数越高的 kv 越少。同一层的 kv 会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。

struct zslnode { 
    string value; 
    double score; 
    zslnode*[] forwards; // 多层连接指针 
    zslnode* backward; // 回溯指针 
} 
struct zsl { 
    zslnode* header; // 跳跃列表头指针 
    int maxLevel; // 跳跃列表当前的最高层 
    map ht; // hash 结构的所有键值对 
}

struct ziplist {
    int32 zlbytes;//整个压缩列表占用字节数
    int32 zltail_offset;//最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
    int16 zllength; // 元素个数
    T[] entries;// 元素内容列表，紧凑排列
    int8 zlend; // 标志压缩列表的结束，值为 0xFF
}

struct entry {
    int prevlen; //前一个 entry 的字节长度
    int encoding;//元素类型编码
    optional byte[] content; //元素内容
}

存在 zltail_offset ，方便支持双向遍历时能够快速定位到最后一个元素，entry 结构中，存在 prevlen 倒序遍历，能够快速定位到上一个元素位置。

因为 ziplist 都是紧凑存储，没有冗余空间，意味着插入一个元素就需要调用 realloc 扩展内存，取决于内存分配器算法和当前的 ziplist 内存大小， realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址，当 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。

struct intset { 
    int32 encoding; // 决定整数位宽是 16 位、32 位还是 64 位 
    int32 length; // 元素个数 
    int contents; // 整数数组，可以是 16 位、32 位和 64 位 
}

当 set 集合容纳的元素都是整数并且元素个数较小，redis 会使用 inset 存储结合元素。是紧凑的数组结构，同时也是整数。

对 ziplist 结构的改进，节省了存储空间。但是还未进行替换，只是增加了。首先这个 listpack 跟 ziplist 的结构几乎一摸一样，只是少了一个 zltail_offset 字段。ziplist 通过这个字段来定位出最后一个元素的位置，用于 逆序遍历。不过 listpack 可以通过其它方式来定位出最后一个元素的位置，所以 zltail_offset 字段就省掉了。

struct listpack { 
    int32 total_bytes; // 占用的总字节数 
    int16 size; // 元素个数 
    T[] entries; // 紧凑排列的元素列表 
    int8 end; // 同 zlend 一样，恒为 0xFF 
}