Redis存储原理与数据模型

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

字典实现

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];

渐进式规则

1. 分治的思想，将rehash分到之后的每步增删改查的操作当中；
2. 再定时器中，最大执行一毫秒rehash；每次步长100个数组槽位；
3. 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