Redis 数据类型源码
字符串 SDS
Redis 的字符串叫着“ SDS ”，也就是 Simple Dynamic String 。它的结构是一个带长度信息的字节数组。
struct SDS<T> {
T capacity; //数组容量
T len; // 数组长度
byte flags; //特殊标志位
byte[] content; //数组内容
}
capacity 表示所分配数组的长度，len 表示字符串的实际长度。
SDS 结构使用了范型 。**为什么不直接用 int 呢？**因为当字符串比较短时，len 和 capacity 可以使用 byte short 来表示， Redis 为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。
embstr & raw
Redis 的字符串有两种存储方式，在长度特别短时，使用 embstr 形式存储(embeded ），而当长度超过 44 字节时，使用 raw 形式存储。
首先来了解一下 Redis 对象头结构 所有的 Redi 对象都有下面的这个头结构。
struct RedisObject {
int4 type ;
int4 encoding ;
int24 lru ;
int32 refcount ;
void *ptr;
} robj ;
这样一个 RedisO ect 对象头结构需要占据 16 字节的存储空间。
struct SDS<T> {
int8 capacity; //数组容量 1byte
int8 len; // 数组长度 1byte
int8 flags; //特殊标志位 1byte
byte[] content; //数组内容 长度为capacity
}
在字符串比较小时， SDS 对象头结构的大小是 capacity+3 ，至少是3字节。意昧着分配 个字符串的最小空间占用为 19 （即16+3 ）字节。
embstr 存储形式是这样 种存储形式，它将 RedisObject 对象头结构和 SDS (字符串)对象连续存在一起， 使用 malloc 方法一次分配。
而 raw 存储形式不一样，它需要使用两次 malloc 方法，两个对象头在内存地址上一般是不连续的。
内存分配器 分配内存大小的单位都是 2/4/8/ 16节等，为了能容纳一个完整的 embstr 对象 jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长 点，那就是64字节的空间。如果字符串总体超出了 64 字节，redis 认为它是个大字符串，不再适合使用 emdstr 形式存储，而该使用 raw 形式。
当内存分配器分配了64字节空间时，那这个字符串的长度最大可以 多少呢？
这个长度就是 44 字节
SDS 结构体中的 conte 中的字符串是以字节 NULL 结尾的字符串，之所以多出这样一个字节，是为了便于直接使用字符串处理函数，以及为了便于字符串的调试打印输出。
由上图可以算出，留给 content 的长度最多只有 45 （即 64-19 ）字节了。字符串又 NULL 结尾 所以 embstr 形式最大能容纳 字符串长度就是44字节。
字典
字典结构内部包含两个 hashtable ，通常情况下只有一个 hashtable 是有值的，但是在字典扩容时，需要分配新的 hashtable ，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable 。待搬迁结束后，旧的 hashtable 被删除，新的 hashtable 取而代之。
hashtable 的结构和Java HashMap 几乎是一样的，都是通过分桶的方式解决 hash 冲突。第一维是数组，第二维是链表。
struct dictEntry {
void* key ;
void* val ;
dictEntry* next; ／／链接下一个 entr
}
struct dictht {
dictEntry ** table;
long size ; // 第一维数组长度
long used; // hash表中元素个数
...
}
渐进式hash
大字典的扩容是比较耗时间的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个 O(n）级别的操作，作为单线程的Red is很难承受这样耗时的过程，所以 Redis 使用渐进式 rehash 小步搬迁。虽然慢点，但是肯定可以搬完。
压缩列表 ziplist
Red is 为了节约内存空间使用， zset hash 容器对象在元素个数较少的时候，采用压缩列表（ ziplist ）进行存储。压缩列表是一块连续的内存空间，元素之间紧接着存储，没有任何冗余空隙。
struct ziplist<T> {
int32 zlbytes; ／／整个压缩列表占用字节数
int32 zltail_offset; ／／最后一个元素距离压缩列表起始位直的偏移量，用
于快速定位到最后一个节点
int16 zllength ; ／／元素个数
T [] entr es ／／元素内容列表，依次紧凑存储
int8 zlend; ／／标志压缩列表的结束，值恒为 OxFF
}
因为 ziplist 都是紧凑存储，没有冗余空间（对比一下 Redis 的字符串结构〉，意昧着插入一个新的元素就需要调用 realloc 扩展内存。
如果 ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗，所以zip list 不适合存储大型字符串，存储的元素也不直过多。
快速列表（quicklist）
Redis 早期版本存储 list 列表数据结构使用的是压缩列表 zip list 和普通的双向链
表linkedlist ，也就是说当元素少时用 zip list ，当元素多时用 linkedlist。
后来的 Redis 新版本对列表数据结构进行了改造，使用quicklist 代替了 ziplist linkedlist。
跳表（skiplist）
Redis zset 是一个复合结构，一方面它需要一个 hash 结构来存储 value和 score 的对应关系，另一方面需要提供按照 score 排序的功能，还需要能够指定 score 的范围来获取 value 列表的功能。所以需要跳表来帮忙实现
Redis 的跳跃列表共有64 层，可容纳 2 ^ 64 个元素。
kv 之间使用指针串起来形成了双向链表结构，它们是有序排列的，从小到大。不同的 kv 层高可能不 样，层数越高的 kv 越少。同一层的 kv 会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。
struct zslnode {
string value;
double score;
zslnode*[] forwards; ／／多层连接指针
zslnode* backward; ／／回溯指针
}
struct zsl {
zslnode* header; ／／跳跃列表头指针
int maxLevel; ／／跳跃列表当前的最高层
map<string, zslnode*> ht; // hash 结构的所有键值对
}
查找
跳跃列表有了多层结构之后，定位算法复杂度将会降到 O( lg(n））
紧凑列表 listpack
Redis 5.0 引入了一个新的数据结构 listpack。它是对 ziplist 结构的改进版。在存储空间上会更加节省，而且结构上也比 ziplist 更精筒.
struct listpack<T> {
int32 total bytes; ／／ 占用的总字节
intl6 size ／／ 素个数
T[] entries; //紧凑排列的元素列表
int8 end; ／／同 zlend 样，恒为0xff
}
listpack和ziplist 结构几乎一模一样，只是少了一个 zltail_offset 字段。
ziplist 通过这个字段来定位出最后一个元素的位置，用于逆序遍历，不过 listpack以通过其他方式来定位出最后一个元素的位置，所以 zltail_offset 字段就被省掉了。
基数树 rax
rax是Redis 中比较特殊的一个数据结构。它是一个有序字典树（基数树 Radix Tree ）。按照 key 的字典序排列，支持快速地定位、插入和删除操作。
zset 是按照 sc ore 进行排序的。 rax 和 zset 的不同在于它是按照 key 进行排序的。
懒惰删除的巨大牺牲
异步线程在 Redis 内部有一个特别的名称，就是“BIO”，全称是 Background IO ，意思是在背后默默干活的 IO 线程。不过内存回收本身并不是什么 IO 操作，是CPU 的计算消耗可能会比较大而已。
异步线程相对简单，释放内存不用为每种数据结构适配 套渐进式释放策略，也不用搞个自适应算法来 仔细控制回收频率，只是将对象从全局字典中摘掉，然后往队列里一扔，主线程就干别的去了。异步线程从队列里取出对象，直接走正常的同步释放逻辑就可以了。
不过使用异步线程也是有代价的，主线程和异步线程之间在内存回收器（ jemalloc ）的使用上存在竞争。
深入字典遍历
Red is 对象树的主干是一个字典，如果对象很多，这个主干字典也会很大。当我们使用 keys 命令搜寻指定模式的 key 时，它会遍历整个主干字典。值得注意的是，在遍历的过程中，如果满足模式匹配条件的 key 被找到了，还需要判key 指向的对象是否已经过期，如果过期了就需要从主干字典中将该 key 删除。
Red is 为字典的遍历提供了两种迭代器 一种是安全迭代器， 一种 不安全迭代器。
迭代器的“安全”指的是在遍历过程中可以对字典进行查找和修改，不用感到担心，因为查找和修改会触发过期判断，会删除内部元素。 “安全”的另一层意思是迭代过程中不会出现元素重复。为了保证不重复，就会禁止 rehashStep。
“不安全”的迭代器是指，在遍历过程中，字典是只读的，不可以修改，只能调用 dictNext 对字典进行持续遍历，不得调用任何可能触发过期判断的函数。好处是不影响 rehash ，代价就是遍历的元素可能会出现重复。
安全迭代器在刚开始遍历时，会给字典打上一个标记，有了这个标记，rehashStep 就不会执行，遍历时元素就不会出现重复
参考
https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
Redis 深度历险：核心原理与应用实践