redis 存储原理与数据模型

这篇具有很好参考价值的文章主要介绍了redis 存储原理与数据模型。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

一、redis的存储结构

1.1 存储结构

redis 存储原理与数据模型,# redis,redis,数据库,缓存

1.2 存储转换

redis 存储原理与数据模型,# redis,redis,数据库,缓存

二、字典(dict)实现

redis 数据库通过 dict 实现映射关系。key 的固定类型是 string,value 的类型有多种。

redis 中 KV 组织是通过字典来实现的;hash 结构当节点超过512 个或者单个字符串长度大于 64 时,hash 结构采用字典实现。

2.1 数据结构

redis 存储原理与数据模型,# redis,redis,数据库,缓存
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,把除法优化为二进制的运算,从而提高执行速度,这种优化的前提是 数组的长度必须是2的n次幂( 2 n 2^n 2n)。

2.2 哈希冲突

哈希冲突指的是不同的键在哈希表中计算得到相同的哈希值,但它们的实际存放位置并不相同。在哈希表中,每个键通过哈希函数映射到一个桶(bucket)或槽(slot),存储在对应的位置上。
redis 存储原理与数据模型,# redis,redis,数据库,缓存
由于哈希表的大小是有限的,而键的数量可能是无限的,所以哈希冲突是不可避免的。

我们通过负载因子 LoadFactor = used / size 来衡量哈希冲突的程度, used 是数组存储元素的个数,size 是数组的长度;
负载因子越小,冲突越小;负载因子越大,冲突越大;redis 的负载因子是 1 .

2.3 扩容

  • 如果负载因子 > 1 ,则会发生扩容;扩容的规则是翻倍;
  • 如果正在 fork (在 rdb、aof 复写以及 rdb-aof 混用情况下)时,会阻止扩容;
  • 但是此时若负载因子 > 5 ,索引效率大大降低, 则马上扩容;这里涉及到写时复制原理;
    redis 存储原理与数据模型,# redis,redis,数据库,缓存
    在写时复制中,当需要修改一个数据副本时,不会立即进行实际的复制操作,而是在修改发生时创建该数据的新副本。这样可以避免对原始数据进行修改,从而保持数据的一致性和完整性。
    写时复制核心思想:只有在不得不复制数据内容时才去复制数据内容;

redis 存储原理与数据模型,# redis,redis,数据库,缓存

2.4 缩容

如果负载因子 < 0.1 ,则会发生缩容;缩容的规则是恰好包含used 的 2 n 2^n 2n
恰好的理解:假如此时数组存储元素个数为 9,恰好包含该元素的就是 ,也就是 16;
redis 存储原理与数据模型,# redis,redis,数据库,缓存
为什么缩容的负载因子不是小于1?
因为缩容的负载因子是小于1的话会造成频繁的扩缩容,扩缩容都有分配内存的操作,内存操作变得频繁就会造成IO密集。

2.5 渐进式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过程当中,发生两次缩容的时候,会发生数据重复。

redis 存储原理与数据模型,# redis,redis,数据库,缓存

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

redis 存储原理与数据模型,# redis,redis,数据库,缓存

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

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

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。
redis 存储原理与数据模型,# redis,redis,数据库,缓存文章来源地址https://www.toymoban.com/news/detail-620457.html

#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 存储原理与数据模型的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • redis数据库缓存服务器

    redis比mysql访问数据快 非关系型数据库以键值对的方式存储数据 作用:加快访问速度,缓解数据库压力 redis最新版本7 特点 丰富的数据结构 list,set,hash等数据结构的存储 支持持久化 支持事务 “一个完整的动作,要么全部执行,要么什么也没有做” 支持主从支持高可用,支持

    2024年02月05日
    浏览(62)
  • Redis如何保证缓存和数据库一致性?

    现在我们在面向增删改查开发时,数据库数据量大时或者对响应要求较快,我们就需要用到Redis来拿取数据。 Redis:是一种高性能的内存数据库,它将数据以键值对的形式存储在内存中,具有读写速度快、支持多种数据类型、原子性操作、丰富的特性等优势。 优势: 性能极高

    2024年01月16日
    浏览(70)
  • Redis---数据库和缓存如何保证一致性?

    用「读 + 写」请求的并发的场景来分析: 假如某个用户数据在缓存中不存在,请求 A 读取数据时从数据库中查询到年龄为 20,在未写入缓存中时另一个请求 B 更新数据。它更新数据库中的年龄为 21,并且清空缓存。这时请求 A 把从数据库中读到的年龄为 20 的数据写入到缓存

    2024年01月24日
    浏览(57)
  • Redis如何保障缓存与数据库的数据一致性问题?

    目录 一.最经典的数据库加缓存的双写双删模式 二. 高并发场景下的缓存+数据库双写不一致问题分析与解决方案设计 三、上面高并发的场景下,该解决方案要注意的问题 1.1 Cache Aside Pattern概念以及读写逻辑 (1)读的时候,先读缓存,缓存没有的话,那么就读数据库,然后取

    2023年04月21日
    浏览(49)
  • redis的缓存更新策略以及如何保证redis与数据库的数据一致性

    redis的缓存更新策略有这么几种: 1、由应用直接和redis以及数据库相连接:         查询数据时,应用去redis中查询,查不到的话再由应用去数据库中查询,并将查询结果放在redis;         更新数据时,由应用去触发redis数据的删除以及数据库的update。 2、应用只跟redi

    2024年02月13日
    浏览(57)
  • 数据库缓存服务——NoSQL之Redis配置与优化

    目录 一、缓存概念 1.1 系统缓存 1.2 缓存保存位置及分层结构 1.2.1 DNS缓存 1.2.2 应用层缓存 1.2.3 数据层缓存 1.2.4 硬件缓存 二、关系型数据库与非关系型数据库 2.1 关系型数据库 2.2 非关系型数据库 2.3 关系型数据库和非关系型数据库区别: 2.4 非关系型数据库产生背景 2.5 总结

    2024年02月15日
    浏览(50)
  • Redis数据库 | 发布订阅、主从复制、哨兵模式、缓存雪崩

    💗wei_shuo的个人主页 💫wei_shuo的学习社区 🌐Hello World ! Redis 发布订阅 (pub/sub) 是一种消息通信模式:发送者 (pub) 发送消息,订阅者 (sub) 接收消息 Redis 客户端可以订阅任意数量的频道 Redis主从复制是指在Redis中设置一个主节点(Master)和一个或多个从节点(Slave),

    2024年02月15日
    浏览(57)
  • Springboot+Redis:实现缓存 减少对数据库的压力

    🎉🎉欢迎光临,终于等到你啦🎉🎉 🏅我是苏泽,一位对技术充满热情的探索者和分享者。🚀🚀 🌟持续更新的专栏 Redis实战与进阶 本专栏讲解Redis从原理到实践 这是苏泽的个人主页可以看到我其他的内容哦👇👇 努力的苏泽 http://suzee.blog.csdn.net/   目录 缓存如何实现?

    2024年03月24日
    浏览(59)
  • REDIS21_缓存双写一致方案、先更新数据库再删除缓存

    ①. 缓存双写一致性,谈谈你的理解 如果redis中有数据,需要和数据库中的值相同 如果redis中无数据,数据库中的值要是最新值 ②. 什么时候同步直写? 小数据,某条、某一小戳热点数据,要求立刻变更,可以前台服务降价一下,后台马上同步直写 ③. 什么时候异步缓写? 正常业务,马

    2023年04月08日
    浏览(47)
  • redis面试题目-如何保证数据库与缓存的数据一致性

    原视频:https://www.bilibili.com/video/BV1Km4y1r75f?p=62vd_source=fa75329ae3880aa55609265a0e9f5d34 由于缓存和数据库是分开的,无法做到原子性的同时进行数据修改,可能出现缓存更新失败,或者数据库更新失败的情况,这时候会出现数据不一致,影响前端业务 先更新数据库,再更新缓存。缓

    2024年02月05日
    浏览(64)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包