Redis存储原理

前言

        我们从redis服务谈起,redis是单reactor,命令在redis-server线程处理。还有若干读写IO线程负责IO操作(redis6.0之后,Redis之pipeline与事务)。此外还有一个内存池线程负责内存管理、一个后台文件线程负责大文件的关闭、一个异步刷盘线程负责持久化。这就使得redis在设计方面对高效的贡献。

        从io密集型的角度来看,redis的磁盘IO是fork子进程异步刷盘,不占用主线程。网络IO如果有多个连接,并且发送了大量的请求,才会考虑IO多线程;从cpu密集型的角度来看,redis有高效的数据结构,加之kv原理,避免了cpu密集。那redis为什么不采用多线程呢?硬伤就是redis的多种数据类型由多种不同的数据结构实现,加锁复杂,锁的粒度不易控制。此外频繁的上下文切换会降低整体性能。那除了单reactor,redis还在什么方面对高效做出来贡献呢?hash表。

存储原理

        redis使用哈希表来组织所有数据,这次我们直接杀到源码。在redisDb中我们可以看到四个dict(散列表)类型的成员(英文这里就不翻译了,原汁原味)。

typedef struct redisDb {kvstore *keys;              /* The keyspace for this DB */kvstore *expires;           /* Timeout of keys with a timeout set */ebuckets hexpires;          /* Hash expiration DS. Single TTL per hash (of next min field to expire) */dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP)*/dict *blocking_keys_unblock_on_nokey;   /* Keys with clients waiting for* data, and should be unblocked if key is deleted (XREADEDGROUP).* This is a subset of blocking_keys*/dict *ready_keys;           /* Blocked keys that received a PUSH */dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */int id;                     /* Database ID */long long avg_ttl;          /* Average TTL, just for stats */unsigned long expires_cursor; /* Cursor of the active expire cycle. */list *defrag_later;         /* List of key names to attempt to defrag one by one, gradually. */
} redisDb;

        可见我们需要对dict下手了,因为数据就存储在dict中。这其实类似c++类的封装,dictType中存放了所有成员函数,其中dictEntry指针数组就是元素存储的地方了。

struct dict {dictType *type;dictEntry **ht_table[2];//哈希表unsigned long ht_used[2];//实际存储的元素个数long rehashidx; /* rehashing not in progress if rehashidx == -1 *//* Keep small vars at end for optimal (minimal) struct padding */unsigned pauserehash : 15; /* If >0 rehashing is paused */unsigned useStoredKeyApi : 1; /* See comment of storedHashFunction above */signed char ht_size_exp[2]; /* exponent of size. (size = 1<<exp) */int16_t pauseAutoResize;  /* If >0 automatic resizing is disallowed (<0 indicates coding error) */void *metadata[];
};

        我们来看dictEntry,也就是存储元素的结构。

/* -------------------------- types ----------------------------------------- */
struct dictEntry {void *key;union {void *val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;     /* Next entry in the same hash bucket. */
};typedef struct {void *key;dictEntry *next;
} dictEntryNoValue;

        源码我们找到了,现在就可以来讨论一下哈希表了。哈希表通过hash运算得出index,如果这个地方有元素,就通过链表组织。这就对应了dictEntry **ht_table[2]。

        我们知道,通过链表组织就是一种应对hash冲突的策略,hash冲突会使索引效率降低,然鹅从源码可以看到有一个负载因子,也就是已有元素与数组长度之比(used/size),负载因子越大表示hash冲突就越大,而我们知道hash时间复杂度是O(1),hash冲突到后面会使时间复杂度增加到O(n)。当负载因子大于1的时候就要进行扩容操作,也就是将数组长度翻倍,增大分母减小负载因子。而当负载因子小于0.1(恰好大于used的2^n)的时候就要进行缩容,因为这是占着茅坑不拉屎,浪费空间。不管扩容还是缩容,数组长度都会改变,这时候hash算法就变了,就要对原来的元素重新hash。

        蛋是!redis是个数据库啊,rehash时就有可能有数据操作,所以它就不能像STL中的unordered_map一样直接rehash(CPU密集型的)。redis是采取渐进式rehash策略。Redis的渐进式rehash是一种在数据量增加时对哈希表进行动态扩容的机制,它能够保证数据的均匀分布和快速访问,同时避免了传统rehash操作可能带来的性能下降问题。在Redis中,渐进式rehash的实现原理和步骤如下:

  1. 触发条件:当哈希表中的节点数与哈希表大小的比例超过一定阈值(默认为1:1,或者在执行RDB或AOF操作时为5:1)时,就会触发rehash操作。
  2. 创建新的哈希表:Redis会创建一个新的哈希表,其大小是原哈希表的两倍,以容纳更多的键值对。
  3. 渐进式迁移:Redis不会一次性将所有键值对迁移到新哈希表,而是将迁移过程分散到后续的字典操作中。每次字典操作时,会顺便迁移一部分键值对到新哈希表,这个过程称为渐进式rehash。
  4. 迁移过程:在迁移过程中,Redis会维护一个rehashidx索引,用于记录迁移的进度。每次字典操作时,会迁移rehashidx索引对应的桶中的所有键值对到新哈希表,然后rehashidx递增。
  5. 读写操作在渐进式rehash进行期间,查找操作会在两个哈希表中进行,以确保不会遗漏任何键值对。而新增操作则只会在新的哈希表中进行。
  6. 完成rehash:当所有键值对都迁移到新哈希表后,Redis会将旧哈希表的空间释放,并将rehashidx重置为-1,表示rehash操作完成。
  7. 缩容操作:除了扩容,Redis在数据量减少时也会进行缩容操作,其过程与扩容类似,也是通过渐进式rehash来完成。

        渐进式rehash的优点在于它能够平滑地处理数据迁移,避免了一次性迁移可能导致的性能抖动,确保了Redis在扩容或缩容过程中的稳定性和性能。然而,它也会占用额外的内存空间,因为需要同时维护两个哈希表,并且在迁移过程中可能会导致一定程度的数据不一致。尽管如此,渐进式rehash是Redis中一个非常重要的特性,它使得Redis能够有效地处理动态数据集的变化。rehash源码如下,这里就不逐行解释了,扔给AI便可。

int dictRehash(dict *d, int n) {int empty_visits = n*10; /* Max number of empty buckets to visit. */unsigned long s0 = DICTHT_SIZE(d->ht_size_exp[0]);unsigned long s1 = DICTHT_SIZE(d->ht_size_exp[1]);if (dict_can_resize == DICT_RESIZE_FORBID || !dictIsRehashing(d)) return 0;/* If dict_can_resize is DICT_RESIZE_AVOID, we want to avoid rehashing. * - If expanding, the threshold is dict_force_resize_ratio which is 4.* - If shrinking, the threshold is 1 / (HASHTABLE_MIN_FILL * dict_force_resize_ratio) which is 1/32. */if (dict_can_resize == DICT_RESIZE_AVOID && ((s1 > s0 && s1 < dict_force_resize_ratio * s0) ||(s1 < s0 && s0 < HASHTABLE_MIN_FILL * dict_force_resize_ratio * s1))){return 0;}while(n-- && d->ht_used[0] != 0) {/* Note that rehashidx can't overflow as we are sure there are more* elements because ht[0].used != 0 */assert(DICTHT_SIZE(d->ht_size_exp[0]) > (unsigned long)d->rehashidx);while(d->ht_table[0][d->rehashidx] == NULL) {//旧数据为空就找下一个d->rehashidx++;if (--empty_visits == 0) return 1;}/* Move all the keys in this bucket from the old to the new hash HT */rehashEntriesInBucketAtIndex(d, d->rehashidx);d->rehashidx++;}return !dictCheckRehashingCompleted(d);
}static void rehashEntriesInBucketAtIndex(dict *d, uint64_t idx) {dictEntry *de = d->ht_table[0][idx];uint64_t h;dictEntry *nextde;while (de) {nextde = dictGetNext(de);void *key = dictGetKey(de);/* Get the index in the new hash table */if (d->ht_size_exp[1] > d->ht_size_exp[0]) {h = dictHashKey(d, key, 1) & DICTHT_SIZE_MASK(d->ht_size_exp[1]);} else {/* We're shrinking the table. The tables sizes are powers of* two, so we simply mask the bucket index in the larger table* to get the bucket index in the smaller table. */h = idx & DICTHT_SIZE_MASK(d->ht_size_exp[1]);}if (d->type->no_value) {if (d->type->keys_are_odd && !d->ht_table[1][h]) {/* Destination bucket is empty and we can store the key* directly without an allocated entry. Free the old entry* if it's an allocated entry.** TODO: Add a flag 'keys_are_even' and if set, we can use* this optimization for these dicts too. We can set the LSB* bit when stored as a dict entry and clear it again when* we need the key back. */assert(entryIsKey(key));if (!entryIsKey(de)) zfree(decodeMaskedPtr(de));de = key;} else if (entryIsKey(de)) {/* We don't have an allocated entry but we need one. */de = createEntryNoValue(key, d->ht_table[1][h]);} else {/* Just move the existing entry to the destination table and* update the 'next' field. */assert(entryIsNoValue(de));dictSetNext(de, d->ht_table[1][h]);}} else {dictSetNext(de, d->ht_table[1][h]);}d->ht_table[1][h] = de;d->ht_used[0]--;d->ht_used[1]++;de = nextde;}d->ht_table[0][idx] = NULL;
}

        那我们怎么访问元素?用keys命令吗?非也。当执行 KEYS 命令时,Redis 会锁定数据库,然后检索所有匹配给定模式的键。如果键的数量非常多,这个操作可能会花费很长时间,在此期间,服务器不能响应其他客户端的请求,从而导致服务器阻塞。这是因为 KEYS 命令在执行期间会阻止其他操作,包括但不限于写操作,直到命令执行完成。我们可以使用scan命令。Redis 的 SCAN 命令是一个基于游标的迭代器,用于逐个元素地访问(或迭代)集合类型的元素,如列表(list)、集合(set)、有序集合(sorted set)和哈希(hash)。这个命令非常有用,因为它提供了一种方式来逐步检索大数据集,而不会像使用传统的 KEYS 命令那样对服务器性能造成严重影响。SCAN 命令的基本用法如下:

SCAN cursor [MATCH pattern] [COUNT count]
  • cursor:游标,每次调用 SCAN 命令时,都会返回一个新的游标,用于下一次迭代。
  • MATCH pattern:可选参数,用于过滤返回的元素,只返回符合给定模式的元素。
  • COUNT count:可选参数,建议 Redis 返回的元素数量,实际返回的数量可能会更多或更少。

SCAN 命令的优点包括:

  • 性能:相比于 KEYS 命令,SCAN 命令不会阻塞服务器,因为它是迭代地返回元素,而不是一次性返回所有匹配的元素。
  • 大数据集:对于包含大量元素的集合类型,SCAN 命令可以有效地进行分批处理,这对于处理大数据集非常有用。
  • 模式匹配:通过 MATCH 选项,可以只返回符合特定模式的元素,这在处理具有特定前缀或模式的键时非常有用。
  • 分页:在分页应用中,SCAN 可以用于实现服务器端的分页功能,通过游标来控制返回的数据范围。
  • 灵活性COUNT 参数允许你建议 Redis 返回的元素数量,这有助于控制每次迭代的负载。

        需要注意的是,SCAN 命令返回的元素可能会有重复,因为 Redis 并不保证每次迭代都是从上一次停止的地方开始。因此,客户端需要准备好处理可能的重复数据。此外,SCAN 命令提供的迭代器只能保证在迭代过程中添加的新元素会被返回,但不保证它们的顺序。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1538692.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

大数据Flink(一百一十八):Flink SQL水印操作(Watermark)

文章目录 Flink SQL水印操作&#xff08;Watermark&#xff09; 一、为什么要有WaterMark 二、​​​​​​​​​​​​​​Watermark解决的问题 三、​​​​​​​​​​​​​​代码演示 Flink SQL水印操作&#xff08;Watermark&#xff09; 一、​​​​​​​为什么…

《黑神话悟空》黄眉打法技巧图文攻略详解

​黄眉是黑神话悟空第三章的关底的boss&#xff0c;很多的玩家都非常的好奇这个boss到底要怎么打&#xff0c;这里小编就为大家带来了黄眉这个boss的打法&#xff0c;我们不要使用法术&#xff0c;只使用禁字诀就可以击败这个boss&#xff0c;详细的内容可以在这里进行了解和查…

DevEco Profiler调优工具(二)

一、Profiler调优模板 3、Snapshot Insight 4、CPU Insight 5、Frame Insight 6、Launch Insight

硬件(驱动开发)

一、OSC基本架构&#xff08;片上系统&#xff09; OSC&#xff08;On-chip System Control&#xff0c;片上系统控制&#xff09;基本架构通常涉及片上系统中的各个组件如何进行协调与控制&#xff0c;以实现高效的处理、通信和管理。OSC架构在现代微处理器和系统单芯片&…

WebApi开发中依赖注入和RESTful 详解

Web API 开发中的依赖注入和 RESTful 详解 在现代 Web API 开发中&#xff0c;依赖注入&#xff08;Dependency Injection, DI&#xff09;和 RESTful 架构 是两个极为重要的概念。本文将详细探讨它们的定义、应用场景及在 Web API 开发中的最佳实践。 一、依赖注入 (Depende…

[PICO VR眼镜]眼动追踪串流Unity开发与使用方法,眼动追踪打包报错问题解决(Eye Tracking/手势跟踪)

前言 最近在做一个工作需要用到PICO4 Enterprise VR头盔里的眼动追踪功能&#xff0c;但是遇到了如下问题&#xff1a; 在Unity里面没法串流调试眼动追踪功能&#xff0c;根本获取不到Device&#xff0c;只能将整个场景build成APK&#xff0c;安装到头盔里&#xff0c;才能在…

【java面向对象二】static(一)

文章目录 前言一、static修饰成员变量二、static修饰成员变量的应用场景三、static修饰成员方法四、搞懂main方法总结 前言 学习static修饰类变量&#xff0c;类方法&#xff0c;以及main方法的使用。 一、static修饰成员变量 static 叫静态&#xff0c;可以修饰成员变量&…

高密原型验证系统解决方案(下篇)

0 引言 我们在上篇中和大家探讨了用户在进行大规模 复杂 SoC 设计原型验证时在全局时钟及复位同步&#xff0c; 大规模设计分割以及高速接口与先进 Memory 控制 器 IP 验证等方面遇到的关键困难&#xff0c;并提出了相应的 解决方案帮助用户来克服这些困难。接下来我们会 和用户…

Django ORM(多表)

文章目录 前言一、关联关系模型二、一对多写入数据二、多对多写入数据二、跨表查询1.查找test 标签的文章2.查找作者名为 test 的文章及标签 三、跨表删除 前言 表与表之间的关系可分为以下三种&#xff1a; 一对一: 一对一关系表示一个模型的每个实例与另一个模型的每个实例…

华为OD机试 - 字符串划分(Java 2024 E卷 100分)

华为OD机试 2024E卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;E卷D卷A卷B卷C卷&#xff09;》。 刷的越多&#xff0c;抽中的概率越大&#xff0c;私信哪吒&#xff0c;备注华为OD&#xff0c;加…

Python | Leetcode Python题解之第416题分割等和子集

题目&#xff1a; 题解&#xff1a; class Solution:def canPartition(self, nums: List[int]) -> bool:n len(nums)if n < 2:return Falsetotal sum(nums)if total % 2 ! 0:return Falsetarget total // 2dp [True] [False] * targetfor i, num in enumerate(nums…

最低成本的游戏串流方案分享 如何自己打造云电脑?

今天教大家如何最低成本实现串流 出门在外也可以随时随地游玩端游大作 硬件准备&#xff1a;一台电脑 手机/平板一台 软件&#xff1a;Gameviewer远程 为啥不用moonlight等其他软件呢 因为设置公网穿透等复杂操作对小白来说不太友好 而GameViewer从安装到使用仅需一键 对比同类…

MATLAB系列07:输入/输入函数

MATLAB系列07&#xff1a;输入/输入函数 8. 输入/输入函数8.1 函数textread8.2 关于load和save命令的进一步说明8.3 MATLAB文件过程简介8.4 文件的打开和关闭8.4.1 fopen函数8.4.2 fclose函数 8.5 二进制 I/O 函数8.5.1 fwrite 函数8.5.2 fread函数 8.6 格式化 I/O 函数8.6.1 f…

【C++ 差分数组 前后缀分解】P7404家庭菜园

本文涉及知识点 C差分数组 C前后缀分解 P7404家庭菜园 出自洛谷&#xff0c;我简述一下。 已知数组a&#xff0c;长度为n(1<n<2e5),1 <a[i] <1e9。一次操作如下&#xff1a;将a[i…j]全1。问最少操作多少次&#xff0c;使得a成为山形数组&#xff0c;即存在k&am…

力扣题解2332

大家好&#xff0c;欢迎来到无限大的频道。 今日继续给大家带来力扣题解。 题目描述&#xff08;中等&#xff09;​&#xff1a; 坐上公交的最晚时间 给你一个下标从 0 开始长度为 n 的整数数组 buses &#xff0c;其中 buses[i] 表示第 i 辆公交车的出发时间。同时给你一…

算法题——最小会议室数量

题目1: 1.假定会议时间从凌晨零点开始&#xff0c;即 0<si<ei<1440&#xff0c;si和ei代表当天某一时刻从零点开始计算的开始和结束分钟数&#xff0c;如[90,360]&#xff0c;表示会议时间从1:30到6:00。 2.不考虑房间的容量问题&#xff0c;并且公司为了提升大家的体…

计算机组成原理-存储系统(二)半导体存储器

2.1DAM芯片 分类&#xff1a; DRAM芯片&#xff1a;使用栅极电容存储信息SRAM芯片&#xff1a;使用双稳态触发器存储信息 核心区别&#xff1a;储存元不一样 2.2DRAM和SRAM的比较 对于DRAM中&#xff1a; 1&#xff1a;电容内存储了电荷0&#xff1a;电容内未存储电荷 DR…

HTML讲解(一)body部分

目录 1.什么是HTML 2.HTML基本框架 3.标题声明 4.修改标题位置 5.段落声明 6.修改段落位置 7.超链接访问 8.图像访问 9.改变网页背景及文本颜色 10.添加网页背景图 11.超链接改变颜色 12.设置网页边距 小心&#xff01;VS2022不可直接接触&#xff0c;否则&#xff…

Qt窗口——QMenuBar

文章目录 QMenuBar示例演示给菜单栏设置快捷键给菜单项设置快捷键添加子菜单添加分割线添加图标 QMenuBar Qt中采用QMenuBar来创建菜单栏&#xff0c;一个主窗口&#xff0c;只允许有一个菜单栏&#xff0c;位于主窗口的顶部、主窗口标题栏下面&#xff1b;一个菜单栏里面有多…

【技术解析】消息中间件MQ:从原理到RabbitMQ实战(深入浅出)

文章目录 【技术解析】消息中间件MQ&#xff1a;从原理到RabbitMQ实战(深入浅出)1.简介1.1 什么是消息中间件1.2 传统的http请求存在那些缺点1.3 Mq应用场景有那些1.4 为什么需要使用mq1.5 Mq与多线程之间区别1.6 Mq消息中间件名词1.7主流mq区别对比1.8 Mq设计基础知识 2.Rabbi…