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