redis 存储原理与数据模型

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: redis 存储原理与数据模型

一、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,把除法优化为二进制的运算,从而提高执行速度,这种优化的前提是 数组的长度必须是image.png


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 的 image.png

恰好的理解:假如此时数组存储元素个数为 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过程当中,发生两次缩容的时候,会发生数据重复。


218628a6ca5c44f00202f6d0e155bd8e_19552c6a56dc43558ea2e26d57c41bca.png


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 理想跳表

bbc78454c20651d92f5ca6c008c97662_421ae2d45c53465198ee0748439c84f6.png

理想跳表是多层级有序链表,采取空间换时间的方法,每隔一个节点生成一个层级节点,模拟二叉树结构,最底层包含所有的元素。


但是如果对理想跳表结构进行增删操作,很可能改变跳表结构。若重构链表,代价极大。考虑用概率的方法来优化。每次增加节点的时候,1/2 的概率增加一个层级,1/4 的概率增加两个层级,以此类推。经过证明,当数据量足够大(256)时,通过概率构造的跳表趋向于理想跳表,并且此时如果删除节点,无需重构跳表结构,此时依然趋向于理想跳表。时间复杂度为image.png

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。

82ee79c649a992856af3da9cc629fa79_a279f30a0231435281208c2bcabca3ac.png

#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;
相关实践学习
基于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
目录
相关文章
|
1月前
|
存储 监控 NoSQL
Redis处理大量数据主要依赖于其内存存储结构、高效的数据结构和算法,以及一系列的优化策略
【5月更文挑战第15天】Redis处理大量数据依赖内存存储、高效数据结构和优化策略。选择合适的数据结构、利用批量操作减少网络开销、控制批量大小、使用Redis Cluster进行分布式存储、优化内存使用及监控调优是关键。通过这些方法,Redis能有效处理大量数据并保持高性能。
48 1
|
9天前
|
消息中间件 NoSQL Linux
详解Redis的主从同步原理
只不过在主节点中叫做master_repl_offset; 从节点也有一个偏移量叫做slave_repl_offset,用来记录从节点已经从主节点的repl_backlog_buffer中同步到的最新写指令的位置;
159 0
|
10天前
|
存储 缓存 NoSQL
了解Redis,第一弹,什么是RedisRedis主要适用于分布式系统,用来用缓存,存储数据,在内存中存储那么为什么说是分布式呢?什么叫分布式什么是单机架构微服务架构微服务的本质
了解Redis,第一弹,什么是RedisRedis主要适用于分布式系统,用来用缓存,存储数据,在内存中存储那么为什么说是分布式呢?什么叫分布式什么是单机架构微服务架构微服务的本质
|
14天前
|
NoSQL Redis 数据库
【Redis从入门到入土】布隆过滤器简介、特点和原理
【6月更文挑战第1天】布隆过滤器是一种节省内存的不确定数据结构,用于判断元素是否可能在一个集合中。它由位数组和多个哈希函数组成,能快速插入和查询,但存在误判风险:可能存在假阳性(判断存在但实际不存在),但绝无假阴性(判断不存在则确实不存在)。适用于大规模数据的去重问题,如电话号码判断、安全网站链接检查、黑名单和白名单校验。其工作原理是通过多个哈希函数将元素映射到位数组中,添加时设置相应位置为1,查询时所有位置都为1则可能存在,有0则肯定不存在。由于哈希冲突,可能导致误判,且一旦添加元素无法删除,以避免影响其他元素。
27 4
|
28天前
|
存储 缓存 NoSQL
由菜鸟到大神,谈谈redis的概念、实战、原理、高级使用方法
【5月更文挑战第18天】Redis是一个开源的内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。它支持多种类型的数据结构,如字符串、哈希、列表、集合、有序集合等。
33 10
|
1月前
|
负载均衡 NoSQL 关系型数据库
深入浅出Redis(六):Redis的主从架构与主从复制原理
深入浅出Redis(六):Redis的主从架构与主从复制原理
|
1月前
|
存储 NoSQL 算法
深入浅出Redis(三):Redis数据的存储、删除以及淘汰
深入浅出Redis(三):Redis数据的存储、删除以及淘汰
|
1月前
|
监控 NoSQL 算法
深入剖析Redis哨兵模式的原理和应用
Redis的哨兵模式是实现高可用性和自动故障转移的机制,当主服务器故障时,哨兵能自动检测并进行故障转移,确保服务连续和稳定性。哨兵模式通过监控主从服务器状态、自动故障转移、防止数据不一致,提高容错能力和负载均衡,降低运维成本,实现高可用性。哨兵通过检测主观下线和客观下线状态,以及选举Leader Sentinel来协调故障转移。Raft算法在其中用于领导者选举和状态一致性。哨兵模式通过综合考虑多种因素选举新主服务器并执行故障转移,保障集群稳定运行。
187 0
深入剖析Redis哨兵模式的原理和应用
|
23天前
|
NoSQL Linux Redis
Redis -- 安装客户端redis-plus-plus
Redis -- 安装客户端redis-plus-plus
47 0