Redis 数据结构
总览
Redis 也是 K-V 型数据库，那么为了实现从键到值的快速访问，Redis 使用 hash 表来保存所有的键值对，哈希桶中的元素保存的并不是值本?，?是指向具体值的指针。这也就是说，不管值是String，还是集合类型，哈希桶中的元素都是指向它们的指针
hash 冲突解决
Redis会对哈希表做rehash操作。rehash 也就是增加现有的哈希桶数量，让逐渐增多的entry元素能在更多的桶之间分散保存，减少单个桶中的元素数量，从?减少单个桶中的冲突。
常规rehash
Redis默认使?了两个全局哈希表：哈希表1和哈希表2。?开始，当你刚插?数据时，默认使?哈希表1，此时的哈希表2并没有被分配空间。随着数据逐步增多，Redis开始执?
rehash，这个过程分为三步：
- 给哈希表2分配更?的空间，例如是当前哈希表1??的两倍；
- 把哈希表1中的数据重新映射并拷?到哈希表2中；
- 释放哈希表1的空间。到此，我们就可以从哈希表1切换到哈希表2，?增?的哈希表2保存更多数据，?原来的哈希表1留作下?次rehash扩容备?。
但是第?步涉及?量的数据拷?，如果?次性把哈希表1中的数据都迁移完，会造成 Redis线程阻塞，?法服务其他请求。此时，Redis就?法快速访问数据了
渐进式 rehash
在第?步拷?数据时，Redis仍然正常处理客?端请求，每处理?个请求时，从哈希表1中的第?个索引位置开始，顺带着将这个索引位置上的所有entries拷?到哈希表2中；等处理下?个请求时，再顺带拷?哈希表1中的下?个索引位置的entries。这样就巧妙地把?次性?量拷?的开销，分摊到了多次处理请求的过程中，避免了耗时操作，保证了数据的快速访问。
基础数据结构
1. string
底层结构是 SDS （Simple Dynamic String）的数据结构，
struct sds<T>{
//记录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 中的未使用的空间，所以惰性空间释放策略不会造成内存浪费。
2. list
list 列表数据结构使用的是 quicklist。quicklist 是 ziplist 和 linkedlist 的混合体，它将linkedlist 按段切分，每一段使用 ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串接起来。
为了进一步节约空间，redis 还会对 ziplist 进行压缩存储，使用 LZF 算法压缩，可以选择压缩深度。
3. hash（字典）
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; /* number of iterators currently running */
}
搬迁条件
在每一次的 hset / hdel 指令会进行搬迁，如果没有指令触发，则会在定时任务中对字典进行主动的搬迁
扩容条件
正常情况下，当 hash 表中的元素的个数等于第一维数组的长度时，就会开始扩容，扩容的新数组是旧数组的2倍。如果 redis 正在做 bgsave时，为了减少内存页的过多分离，redis 不进行扩容，除非当前的hash 表已经满了，元素的个数已经达到了第一维数组长度的5倍，会进行强制扩容。
缩容条件
元素的个数低于数组长度的 10%。
4. set
底层也是字典，只不过所有的 value 都是 null。
5. zset
zset 的内部实现是一个 hash 字典加一个跳跃列表 (skiplist)。
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 结构的所有键值对
}
ziplist（压缩列表）
struct ziplist<T> {
int32 zlbytes;//整个压缩列表占用字节数
int32 zltail_offset;//最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
int16 zllength; // 元素个数
T[] entries;// 元素内容列表，紧凑排列
int8 zlend; // 标志压缩列表的结束，值为 0xFF
}
struct entry {
int<var> prevlen; //前一个 entry 的字节长度
int<var> 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
}