Redis存储结构
存储转换
- redis-value编码
- string
- int：字符串长度小于等于20切能转成整数
- raw：字符串长度大于44
- embstr：字符串长度小于等于44
- list
- quicklist（双向链表）
- ziplist（压缩链表）
- hash
- dict（字典）：节点数量大于512或者字符串长度大于64
- ziplist（压缩链表）：节点数量小于等于512且字符串长度小于等于64
- set
- intset（整数数组）：元素都为整数且节点数量小于等于512
- dict（字典）：元素有一个不是整数或者数量大于512
- zset
- skiplist（跳表）：数量大于128或者有一个字符串长度大于64
- ziplist（压缩列表）：子节点数量小于等于128且字符串长度小于等于64
- string
字典实现
redis中的KV组织是通过字典实现的；hash结构当节点超过512个或者单个字符串长度大于64时，hash结构采用字典实现。
数据结构
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
typedef struct dictht {
dictEntry **table;
unsigned long size; // 数组长度
unsigned long sizemask; // size - 1
unsigned long used; // 当前数组中包含的元素
} dictht;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
int16_t pauserehash; /* If >0 rehashing is paused (<0 indicates coding error) 用于安全遍历*/
} dict;
- 字符串经过hash函数运算得到64位整数；
- 相同字符串多次通过hash函数得到相同的64位整数；
- 整数对2^n取余可以转化为位运算；
- 抽屉原理 n+1个苹果放在 n 个抽屉中，苹果最多的那个抽屉至少有 2 个苹果;64位整数远大于数组的长度，比如数组长 度为 4，那么 1、5、9、1+4n 都是映射到1号位数组;所以 大概率会发生冲突;
冲突
- 负载因子：负载因子=
used/size；used是数字元素个数，size是数组长度；负载因子越小，冲突越小；负载因子越大，冲突越大；redis的负载因子是1；
扩容
- 如果负载因子
>1，则会发生扩容；扩容的规则是翻倍； - 如果正在
fork(在rdb、aof复写以及rdb-aof混用的情况下)时，会阻止扩容；但是此时若负载因子>5，索引效率会大大下降，则马上扩容；这里涉及到写时复制原理
缩容
- 如果负载因子 < 0.1，则会发生缩容;缩容的规则是恰好包含 used 的 ;
- 恰好的理解:假如此时数组存储元素个数为 9，恰好包含该元素 的就是 ，也就是 16;
渐进式rehash
当hashtable中的元素过多的时候，不能一次性rehash到th[1]；这样会长期占用redis，其他命令得不到相应；所以需要使用渐进式rehash；
rehash步骤
将ht[0]中的元素重新hash成64位整数，再对ht[1]长度进行取余，从而映射到ht[1];
渐进式规则
- 分治的思想，将
rehash分到之后的每步增删改查的操作当中； - 再定时器中，最大执行一毫秒
rehash；每次步长100个数组槽位； - rehash阶段，不会发生扩容和缩容。
scan
scan cursor [MATCH pattern] [COUNT count] [TYPE type]
- 采用高位进位加法的遍历顺序，rehash 后的槽位在遍历顺序上 是相邻的;
- 遍历目标是:不重复，不遗漏 ;
- 会出现一种重复的情况:在 scan 过程当中，发生两次缩容的时候，会发生数据重复;
expire机制
expire key seconds
pexpire key milliseconds
ttl key
pttl key
惰性删除
分布在每一个命令操作时检查key是否过期；若过期删除key，再进行命令操作；
定时删除
在定时器中检查库中指定个数（25）个key；
#define ACTIVE_EXPIRE_CYCLE_KEYS_PER_LOOP 20 /* Keys for each DB loop.
/* Keys for each DB loop. */
/*The default effort is 1, and the maximum configurable effort is 10. */
config_keys_per_loop =
ACTIVE_EXPIRE_CYCLE_KEYS_LOOP + ACTIVE_EXPIRE_CYCLE_KEYS_LOOP/4*effort,
int activeExpireCycleTryExpire(redisDb *db, dictEntry *de, long long now);
大KEY
在 redis 实例中形成了很大的对象，比如一个很大的 hash 或很 大的 zset，这样的对象在扩容的时候，会一次性申请更大的一块 内存，这会导致卡顿;如果这个大 key 被删除，内存会一次性 回收，卡顿现象会再次产生;
如果观察到redis内存大起大落，极有可能是大key导致的；
# 每隔0.1秒，执行100条scan命令
redis-cli -h 127.0.0.1 --bigkeys -i 0.1
