Redis存储原理与数据模型

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: 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/sizeused是数字元素个数,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
相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
2月前
|
NoSQL Redis
Redis 执行 Lua保证原子性原理
Redis 执行 Lua 保证原子性原理
139 1
|
12天前
|
缓存 NoSQL Linux
redis的原理(三)
redis的原理(三)
redis的原理(三)
|
26天前
|
消息中间件 存储 NoSQL
剖析 Redis List 消息队列的三种消费线程模型
Redis 列表(List)是一种简单的字符串列表,它的底层实现是一个双向链表。 生产环境,很多公司都将 Redis 列表应用于轻量级消息队列 。这篇文章,我们聊聊如何使用 List 命令实现消息队列的功能以及剖析消费者线程模型 。
72 20
剖析 Redis List 消息队列的三种消费线程模型
|
12天前
|
存储 缓存 NoSQL
redis的原理(四)
redis的原理(四)
|
12天前
|
存储 缓存 NoSQL
redis的原理(二)
redis的原理(二)
|
12天前
|
缓存 NoSQL 安全
Redis的原理(一)
Redis的原理(一)
|
12天前
|
JSON 缓存 NoSQL
redis序列化数据时,如何包含clsss类型信息?
通过配置 `com.fasterxml.jackson.databind.ObjectMapper` 的 `enableDefaultTyping` 方法,可以使序列化后的 JSON 包含类信息。
34 2
|
6天前
|
消息中间件 存储 NoSQL
18)Redis 的发布订阅模型
18)Redis 的发布订阅模型
13 0
|
6天前
|
缓存 NoSQL 算法
14)Redis 在内存用完时会怎么办?如何处理已过期的数据?
14)Redis 在内存用完时会怎么办?如何处理已过期的数据?
14 0
|
6天前
|
存储 NoSQL 安全
8)详解 Redis 的配置文件以及数据持久化
8)详解 Redis 的配置文件以及数据持久化
13 0
下一篇
无影云桌面