一、redis的存储结构
1.1 存储结构
1.2 存储转换
二、字典(dict)实现
redis 数据库通过 dict 实现映射关系。key 的固定类型是 string，value 的类型有多种。
redis 中 KV 组织是通过字典来实现的；hash 结构当节点超过512 个或者单个字符串长度大于 64 时，hash 结构采用字典实现。
2.1 数据结构
dict 由哈希表 dictht + 哈希节点 dictEntry 组成。哈希表有两个，通常 ht[0] 使用，ht[1] 不使用；rehash 时，ht[0] 存储 rehash 之前的数据，ht[1] 存储新数据和 ht[0] 迁移来的数据。
// dict相当于C++的类的封装 typedef struct dict { dictType *type; // dict 类型，封装成员函数 void *privdata; // 私有数据，连接的上下文 dictht ht[2]; // 散列表，一个存储当前数据，另一个 rehash 时使用。 long rehashidx; // 指示rehash到哪个位置了，它是从0开始的，如果rehashidx == -1，则rehash未进行。 unsigned long iterators; /* number of iterators currently running */ } dict; // 哈希表 typedef struct dictht { dictEntry **table; // entry 指针数组，保存 entry 的指针 unsigned long size; // 哈希表大小，2的n次幂 unsigned long sizemask; // 哈希表掩码 size-1，hash 取余运算优化成位运算 unsigned long used; // 实际存储元素 entry 的个数 } dictht; // 哈希节点 typedef struct dictEntry { void *key; union { void *val; uint64_t u64; int64_t s64; double d; } v; struct dictEntry *next; } dictEntry;
1）字符串经过 hash 函数运算得到 64 位整数；
2）相同字符串多次通过 hash 函数得到相同的64位整数；
3）整数对 取余可以转化为位运算；sizemask是size-1，属于对字典的优化。因为散列表的存储是通过hash(key)%size=index确定索引，sizemask是对取余长度的优化，将hash(key)%size变成hash(key) &sizemask，把除法优化为二进制的运算，从而提高执行速度，这种优化的前提是 数组的长度必须是
2.2 哈希冲突
哈希冲突指的是不同的键在哈希表中计算得到相同的哈希值，但它们的实际存放位置并不相同。在哈希表中，每个键通过哈希函数映射到一个桶（bucket）或槽（slot），存储在对应的位置上。
由于哈希表的大小是有限的，而键的数量可能是无限的，所以哈希冲突是不可避免的。
我们通过负载因子 LoadFactor = used / size 来衡量哈希冲突的程度， used 是数组存储元素的个数，size 是数组的长度；
负载因子越小，冲突越小；负载因子越大，冲突越大；redis 的负载因子是 1 .
2.3 扩容
- 如果负载因子 > 1 ，则会发生扩容；扩容的规则是翻倍；
- 如果正在 fork （在 rdb、aof 复写以及 rdb-aof 混用情况下）时，会阻止扩容；
- 但是此时若负载因子 > 5 ，索引效率大大降低， 则马上扩容；这里涉及到写时复制原理；
在写时复制中，当需要修改一个数据副本时，不会立即进行实际的复制操作，而是在修改发生时创建该数据的新副本。这样可以避免对原始数据进行修改，从而保持数据的一致性和完整性。
写时复制核心思想：只有在不得不复制数据内容时才去复制数据内容；
2.4 缩容
如果负载因子 < 0.1 ，则会发生缩容；缩容的规则是恰好包含used 的 
；
恰好的理解：假如此时数组存储元素个数为 9，恰好包含该元素的就是 ，也就是 16；
为什么缩容的负载因子不是小于1？
因为缩容的负载因子是小于1的话会造成频繁的扩缩容，扩缩容都有分配内存的操作，内存操作变得频繁就会造成IO密集。
2.5 渐进式rehash
rehash扩容和缩容都会导致rehash，因为映射算法发生了改变。
当 hashtable 中的元素过多的时候，因为redis是一个数据库，里面存储的数据非常多，不能一次性 rehash 到ht[1]；这样会长期占用 redis，其他命令得不到响应；所以需要使用渐进式 rehash。
rehash步骤：
将 ht[0] 中的元素重新经过 hash 函数生成 64 位整数，再对ht[1] 长度进行取余，从而映射到 ht[1]。
渐进式规则：
1） 分治的思想，将 rehash 分到之后的每步增删改查的操作当中。
2）在定时器中，最大执行一毫秒 rehash ；每次步长 100 个数组槽位。
3）处理渐进式 rehash 的过程中，不会发生扩容和缩容。
2.6 scan 命令
SCAN命令的引入是为了解决，在某些情况下，需要对Redis数据库中的所有键进行遍历，以便进行某些操作或统计。然而，如果直接使用KEYS命令获取所有键，会对性能产生严重影响，因为KEYS命令会阻塞其他操作，并且在数据集较大时，返回所有键也会消耗大量内存。SCAN命令通过迭代方式，分批次逐步返回匹配的键，避免了一次性返回所有键的问题，从而减少了长时间阻塞的情况。
scan cursor [MATCH pattern] [COUNT count] [TYPE type]
redis在遍历数据期间，如果发生扩容或者缩容，造成映射算法发生改变，键的槽位可能会发生改变。那么继续遍历会发生错误。
因此 scan 采用高位进位加法的遍历顺序，这样 rehash 后的槽位在遍历顺序上是相邻的，对 sacn 那刻起已经存在的元素遍历不会出现重复和遗漏。例外：在scan过程当中，发生两次缩容的时候，会发生数据重复。
2.7 expire机制
redis的EXPIRE机制用于设置键的过期时间，即在指定时间后自动删除键。它是基于每个键的时间戳实现的。
1）EXPIRE key seconds：设置键 key 的过期时间为 seconds 秒。当键到达过期时间后，Redis会自动删除该键。
2）PEXPIRE key milliseconds：设置键 key 的过期时间为 milliseconds 毫秒。与 EXPIRE 命令类似，但时间单位为毫秒。
3）TTL key：获取键 key 的剩余过期时间（以秒为单位）。如果键不存在或键没有设置过期时间，返回 -1。如果键已过期，返回 -2。
4）PTTL key：获取键 key 的剩余过期时间（以毫秒为单位）。如果键不存在或键没有设置过期时间，返回 -1。如果键已过期，返回 -2。
redis有两种删除方式：
1）惰性删除：分布在每一个命令操作时检查 key 是否过期；若过期删除 key，再进行命令操作。
2）定时删除：在定时器中检查库中指定个数（25）个 key。
需要注意的对大对象（大key）的删除：
在 redis 实例中形成了很大的对象，比如一个很大的 hash 或很大的 zset，这样的对象在扩容的时候，会一次性申请更大的一块内存，这会导致卡顿；如果这个大 key 被删除，内存会一次性回收，卡顿现象会再次产生。
如果观察到 redis 的内存大起大落，极有可能因为大 key 导致的。
# 每隔0.1秒 执行100条scan命令 redis-cli -h 127.0.0.1 --bigkeys -i 0.1
三、跳表(skiplist)实现
跳表的特点
- 多层级有序链表
- 最底层包含所有的元素
- 支持二分查找，快速定位边界，然后在最底层找到范围内所有元素（区别红黑树）。
- 增删改查的时间复杂度都是 O(log2n)。
3.1 理想跳表
理想跳表是多层级有序链表，采取空间换时间的方法，每隔一个节点生成一个层级节点，模拟二叉树结构，最底层包含所有的元素。
但是如果对理想跳表结构进行增删操作，很可能改变跳表结构。若重构链表，代价极大。考虑用概率的方法来优化。每次增加节点的时候，1/2 的概率增加一个层级，1/4 的概率增加两个层级，以此类推。经过证明，当数据量足够大（256）时，通过概率构造的跳表趋向于理想跳表，并且此时如果删除节点，无需重构跳表结构，此时依然趋向于理想跳表。时间复杂度为
3.2 redis跳表
从节约内存角度出发，redis 考虑牺牲一些时间性能让跳表结构变得更加扁平。以循环双向链表结构实现，每次增加节点时，1/4 的概率增加一个层级，跳表的最高层级为 32。当节点数量大于 128 或者有一个字符串长度大于 64，则使用跳表结构。
比如插入17，先比较第 4 层：(6, nil)， 从 6 节点往下跳。比较第 3 层：(6, 25)，从 6 节点往下跳。比较第 2 层：(9, 25)，从 9 节点往下跳。比较第1层：(12, 19)，在 12 节点后插入 节点17。
#define ZSKIPLIST_MAXLEVEL 32 // 跳表的层级， #define ZSKIPLIST_P 0.25 // 每个节点增加层级的概率 typedef struct zskiplistNode { sds ele; // 节点存储的数据 double score; // 节点分数，排序使用 struct zskiplistNode *backward; // 前一个节点指针 struct zskiplistLevel { // 多级索引数组 struct zskiplistNode *forward; // 下一个节点指针 unsigned long span; // 索引跨度 } level[]; } zskiplistNode; typedef struct zskiplist { struct zskiplistNode *header, *tail; // 头尾节点指针 unsigned long length; // 节点数量 int level; // 最大的索引层，默认是1 } zskiplist;
