Redis(三)存储原理与数据模型(hash冲突、渐进式rehash)

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redis(三)存储原理与数据模型(hash冲突、渐进式rehash)



一、redis 存储结构

Redis是key-value的结构,其中value包含:字典,双向链表,压缩列表,跳表,整数数组,动态字符串。

存储转换

其中redis中各value的数据结构根据不同的情况有不同的自动存储转换。

键值存储实现

redis 中 K-V 组织是通过字典来实现的,也就是hash表。key字符串经过 hash 函数运算得到 64 位整数;

hash冲突

redis采用hash表存储key-value就会遇到hash冲突的情况。常见的hash冲突解决方式有:

  • 开链法:将hash冲突的value值用链表连接,每个hash结果的key值下面都连接一个链表。如果链表过长还可以将链表转化为红黑树来优化。
  • rehash:即增加hash桶的大小。redis有两个hash表,当hash表1冲突了,就会采用hash表2,而hash表2的hash桶大小通常是hash表1的2倍。

但是rehash时,将hash表1的数据复制到hash表2是一个庞大的工程,可能会造成redis线程阻塞,影响redis性能。因此redis有渐进式rehash的机制来解决这个问题。

渐进式rehash

渐进式rehash和rehash一样,同样需要将hash表1的数据复制到hash表2,但是这个复制过程不是一次性的,而是一步一步分块转移。

redis的渐进式有两种规则:

  1. 分治的思想,将 rehash 分到之后的每步增删改查的操作当中,即每次处理redis时,复制一个key;
  2. 在定时器中,最大执行一毫秒 rehash ;每次复制100 个数组key槽位;

rehash 过程中如果入到增删查改时会怎么做?

  • 查:查找数据时,会先在hash表1中查找数据,如果没找到就会在hash表2中去找。
  • 增:新增数据时,只会增加到hash表2中,不会在hash表1做任何操作。
  • 删&改:在两个表上都会操作。

redis除了扩容会有渐进式rehash,其实缩容时也会采用rehash。

但是在rehash阶段,不会再发生扩容和缩容。必须等rehash结束。

大KEY

在 redis 实例中假如形成了很大的对象,比如一个很大的 hash 或很大的 zset,这样的对象在扩容的时候,会一次性申请更大的一块内存,这会导致卡顿;如果这个大 key 被删除,内存会一次性回收,卡顿现象会再次产生;如果观察到 redis 的内存大起大落,极有可能因为大 key 导致的;

解决方法:

  • 拆分value
  • 压缩value
  • 删除非热点大key(可使用redis异步机制删除)

跳表

Redis 中的有序集合(Sorted Set)是用跳表(Skip list)来实现的。跳表就是解决链表在有序节点场景下的查询时间复杂度高问题。时间复杂度能达到O(logn)。

详细内容参考Redis跳表

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore     ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库 ECS 实例和一台目标数据库 RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&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
|
11天前
|
存储 JSON NoSQL
Redis第五弹-HASH结构相关指令和介绍,计数功能Hash-哈希(Redis本来就是键值对结构,哈希,就相当于键值对嵌套了一个键值对)的多种指令Hset key field value-
Redis第五弹-HASH结构相关指令和介绍,计数功能Hash-哈希(Redis本来就是键值对结构,哈希,就相当于键值对嵌套了一个键值对)的多种指令Hset key field value-
|
11天前
|
存储 缓存 NoSQL
了解Redis,第一弹,什么是RedisRedis主要适用于分布式系统,用来用缓存,存储数据,在内存中存储那么为什么说是分布式呢?什么叫分布式什么是单机架构微服务架构微服务的本质
了解Redis,第一弹,什么是RedisRedis主要适用于分布式系统,用来用缓存,存储数据,在内存中存储那么为什么说是分布式呢?什么叫分布式什么是单机架构微服务架构微服务的本质
|
14天前
|
NoSQL Redis 数据库
【Redis从入门到入土】布隆过滤器简介、特点和原理
【6月更文挑战第1天】布隆过滤器是一种节省内存的不确定数据结构,用于判断元素是否可能在一个集合中。它由位数组和多个哈希函数组成,能快速插入和查询,但存在误判风险:可能存在假阳性(判断存在但实际不存在),但绝无假阴性(判断不存在则确实不存在)。适用于大规模数据的去重问题,如电话号码判断、安全网站链接检查、黑名单和白名单校验。其工作原理是通过多个哈希函数将元素映射到位数组中,添加时设置相应位置为1,查询时所有位置都为1则可能存在,有0则肯定不存在。由于哈希冲突,可能导致误判,且一旦添加元素无法删除,以避免影响其他元素。
27 4
|
23天前
|
Java Redis
redis-学习笔记(Jedis hash简单命令)
redis-学习笔记(Jedis hash简单命令)
23 1
|
23天前
|
NoSQL Redis
redis-学习笔记(hash)
redis-学习笔记(hash)
20 0
|
23天前
|
NoSQL Java Redis
redis-学习笔记(string , hash , list , set , zset 前置知识)
redis-学习笔记(string , hash , list , set , zset 前置知识)
7 0
redis-学习笔记(string , hash , list , set , zset 前置知识)
|
24天前
|
机器学习/深度学习 NoSQL Redis
Redis -- hash哈希
Redis -- hash哈希
22 0
|
29天前
|
存储 缓存 NoSQL
由菜鸟到大神,谈谈redis的概念、实战、原理、高级使用方法
【5月更文挑战第18天】Redis是一个开源的内存中的数据结构存储系统,它可以用作数据库、缓存和消息中间件。它支持多种类型的数据结构,如字符串、哈希、列表、集合、有序集合等。
33 10