从应用到底层:36张图带你进入Redis世界(上)

Redis/缓存系统
271
0
0
2023-06-01
标签   Redis

以下文章来源于sowhat1412 ,作者sowhat1412

总感觉哪里不对,但是又说不上来

1、基本类型及底层实现

1.1、String

用途:

底层 :C语言中String用 char []数组表示,源码中用 SDS (simple dynamic string)封装char[],这是是 Redis 存储的 最小单元 ,一个SDS最大可以存储512M信息。

 struct sdshdr{
  unsigned int len; // 标记char[]的长度
  unsigned int free; //标记char[]中未使用的元素个数
  char buf[]; // 存放元素的坑
} 

Redis对SDS再次封装生成了 RedisObject ,核心有两个作用:

说明是5种类型哪一种。
里面有指针用来指向 SDS。

当你执行 set name sowhat 的时候,其实Redis会创建两个RedisObject对象, 的RedisObject 和 值的RedisOjbect 其中它们type = REDIS_STRING,而SDS分别存储的就是 name 跟 sowhat 字符串咯。

并且Redis底层对SDS有如下优化:

SDS修改后大小 > 1M时 系统会多分配空间来进行空间预分配。
SDS是惰性释放空间的,你free了空间,可是系统把数据记录下来下次想用时候可直接使用。不用新申请空间。

1.2、List

从应用到底层:36张图带你进入Redis世界(上)

查看源码底层 adlist.h 会发现底层就是个 双端链表 ,该链表最大长度为2^32-1。常用就这几个组合。

lpush + lpop = stack 先进后出的栈
lpush + rpop = queue 先进先出的队列
lpush + ltrim = capped collection 有限集合
lpush + brpop = message queue 消息队列

一般可以用来做简单的消息队列,并且当数据量小的时候可能用到独有的压缩列表来提升性能。当然专业点还是要 RabbitMQ、ActiveMQ等

1.3、Hash

散列非常适用于将一些相关的数据存储在一起,比如用户的购物车。该类型在日常用途还是挺多的。

这里需要明确一点:Redis中只有一个K,一个V。其中 K 绝对是字符串对象,而 V 可以是String、List、Hash、Set、ZSet任意一种。

hash的底层主要是采用字典dict的结构,整体呈现层层封装。从小到大如下:

1.3.1、dictEntry

真正的数据节点,包括key、value 和 next 节点。

从应用到底层:36张图带你进入Redis世界(上)

1.3.2、dictht

1、数据 dictEntry 类型的数组,每个数组的item可能都指向一个链表。
2、数组长度 size。
3、sizemask 等于 size – 1。
4、当前 dictEntry 数组中包含总共多少节点。

从应用到底层:36张图带你进入Redis世界(上)

1.3.3、dict

1、dictType 类型,包括一些自定义函数,这些函数使得key和value能够存储
2、rehashidx 其实是一个标志量,如果为 -1 说明当前没有扩容,如果 不为 -1 则记录扩容位置。
3、dictht数组,两个Hash表。
4、iterators 记录了当前字典正在进行中的迭代器

从应用到底层:36张图带你进入Redis世界(上)

组合后结构就是如下

从应用到底层:36张图带你进入Redis世界(上)

1.3.4、渐进式扩容

为什么 dictht ht[2]是两个呢? 目的是在扩容的同时不影响前端的CURD ,慢慢的把数据从ht[0]转移到ht[1]中,同时 rehashindex 来记录转移的情况,当全部转移完成,将ht[1]改成ht[0]使用。

rehashidx = -1说明当前没有扩容,rehashidx != -1则表示扩容到数组中的第几个了。

扩容之后的数组大小为大于used*2的 2的n次方 的最小值,跟 HashMap 类似。然后挨个遍历数组同时调整rehashidx的值,对每个dictEntry[i] 再挨个遍历链表将数据 Hash 后重新映射到 dictht[1]里面。并且 dictht[0].use dictht[1].use 是动态变化的。

从应用到底层:36张图带你进入Redis世界(上)

整个过程的重点在于 rehashidx ,其为第一个数组正在移动的下标位置,如果当前内存不够,或者操作系统繁忙,扩容的过程可以随时停止。

停止之后如果对该对象进行操作,那是什么样子的呢?

1、如果是新增,则直接新增后第二个数组,因为如果新增到第一个数组,以后还是要移过来,没必要浪费时间
2、如果是删除,更新,查询,则先查找第一个数组,如果没找到,则再查询第二个数组。

从应用到底层:36张图带你进入Redis世界(上)


1.4、Set

如果你明白Java中HashSet是HashMap的简化版那么这个Set应该也理解了。都是一样的套路而已。这里你可以认为是没有Value的Dict。看源码 t.set.c 就可以了解本质了。

 int setTypeAdd(robj *subject, robj *value) {
    long long llval;
    if (subject->encoding == REDIS_ENCODING_HT) {
         // 看到底层调用的还是dictAdd,只不过第三个参数= NULL
         if (dictAdd(subject->ptr,value,NULL) == DICT_OK) {
            incrRefCount(value);
            return 1;
        }
        .... 

1.5、ZSet

范围查找 的天敌就是 有序集合,看底层 redis.h 后就会发现 Zset用的就是可以跟二叉树媲美的 跳跃表 来实现有序。跳表就是多层 链表 的结合体,跳表分为许多层(level),每一层都可以看作是数据的 索引 这些索引的意义就是加快跳表查找数据速度

每一层的数据都是有序的,上一层数据是下一层数据的子集,并且第一层(level 1)包含了全部的数据;层次越高,跳跃性越大,包含的数据越少。并且随便插入一个数据该数据是否会是跳表索引完全随机的跟玩骰子一样。

跳表包含一个表头,它查找数据时,是 从上往下,从左往右 进行查找。现在找出值为37的节点为例,来对比说明跳表和普遍的链表。

  1. 没有跳表查询 比如我查询数据37,如果没有上面的索引时候路线如下图:
  2. 有跳表查询 有跳表查询37的时候路线如下图:应用场景:
积分排行榜、时间排序新闻、延时队列。

1.6、Redis Geo

以前写过Redis Geo核心原理解析,想看的直接跳转即可。他的核心思想就是将地球近似为球体来看待,然后 GEO利用 GeoHash 将二维的经纬度转换成字符串,来实现位置的划分跟指定距离的查询。

从应用到底层:36张图带你进入Redis世界(上)

1.7、HyperLogLog

HyperLogLog :是一种 概率 数据结构,它使用概率算法来统计集合的近似基数。而它算法的最本源则是 伯努利过程 + 分桶 + 调和平均数 。具体实现可看 HyperLogLog 讲解。

功能 :误差允许范围内做基数统计 (基数就是指一个集合中不同值的个数) 的时候非常有用,每个HyperLogLog的键可以计算接近 2^64 不同元素的基数,而大小只需要12KB。错误率大概在0.81%。所以如果用作 UV 统计很合适。

HyperLogLog底层 一共分了 2^14 个桶,也就是 16384 个桶。每个(registers)桶中是一个 6 bit 的数组,这里有个骚操作就是一般人可能直接用一个字节当桶浪费2个bit空间,但是Redis底层只用6个然后通过前后拼接实现对内存用到了极致,最终就是 16384*6/8/1024 = 12KB。

1.8、bitmap

BitMap 原本的含义是用一个比特位来映射某个元素的状态。由于一个比特位只能表示 0 和 1 两种状态,所以 BitMap 能映射的状态有限,但是使用比特位的优势是能大量的节省内存空间。

在 Redis 中BitMap 底层是基于字符串类型实现的,可以把 Bitmaps 想象成一个以比特位为单位的数组,数组的每个单元只能存储0和1,数组的下标在 Bitmaps 中叫做偏移量,BitMap 的 offset 值上限 2^32 – 1

从应用到底层:36张图带你进入Redis世界(上)

  1. 用户签到
key = 年份:用户id offset = (今天是一年中的第几天) % (今年的天数)
  1. 统计活跃用户
使用日期作为 key,然后用户 id 为 offset 设置不同offset为0 1 即可。

PS : Redis 它的通讯协议是基于TCP的应用层协议 RESP(REdis Serialization Protocol)。

1.9、Bloom Filter

使用布隆过滤器得到的判断结果: 不存在的一定不存在,存在的不一定存在

布隆过滤器 原理:

当一个元素被加入集合时,通过K个散列函数将这个元素映射成一个位数组中的K个点(有效降低冲突概率),把它们置为1。检索时,我们只要看看这些点是不是都是1就知道集合中有没有它了:如果这些点有任何一个为0,则被检元素一定不在;如果都是1,则被检元素很可能在。这就是布隆过滤器的基本思想。

想玩的话可以用Google的 guava 包玩耍一番。

从应用到底层:36张图带你进入Redis世界(上)

1.10 发布订阅

redis提供了 发布、订阅 模式的消息机制,其中消息订阅者与发布者不直接通信,发布者向指定的频道(channel)发布消息,订阅该频道的每个客户端都可以接收到消息。不过比专业的MQ(RabbitMQ RocketMQ ActiveMQ Kafka)相比不值一提,这个功能就算球了。

从应用到底层:36张图带你进入Redis世界(上)

2、持久化

因为Redis数据在内存,断电既丢,因此持久化到磁盘是必须得有的,Redis提供了RDB跟AOF两种模式。

2.1、RDB

RDB 持久化机制,是对 Redis 中的数据执行周期性的持久化。更适合做冷备。优点:

1、压缩后的二进制文,适用于备份、全量复制,用于灾难恢复加载RDB恢复数据远快于AOF方式,适合大规模的数据恢复。
2、如果业务对数据完整性和一致性要求不高,RDB是很好的选择。数据恢复比AOF快。

缺点:

1、RDB是 周期间隔性的快照文件 ,数据的完整性和一致性不高,因为RDB可能在最后一次备份时宕机了。
2、备份时占用内存,因为Redis 在备份时会独立fork一个 子进程 ,将数据写入到一个临时文件(此时内存中的数据是原来的两倍哦),最后再将临时文件替换之前的备份文件。所以要考虑到大概两倍的数据膨胀性。

注意手动触发及COW:

1、 SAVE 直接调用 rdbSave , 阻塞 Redis 主进程,导致无法提供服务。2、 BGSAVE 则 fork 出一个子进程,子进程负责调用 rdbSave ,在保存完成后向主进程发送信号告知完成。在BGSAVE 执行期间 仍可以继续处理客户端的请求
3、Copy On Write 机制,备份的是开始那个时刻内存中的数据,只复制被修改内存页数据,不是全部内存数据。
4、Copy On Write 时如果父子进程大量写操作会导致分页错误。

从应用到底层:36张图带你进入Redis世界(上)


2.2、AOF

AOF 机制对每条写入命令作为日志,以 append-only 的模式写入一个日志文件中,因为这个模式是 只追加 的方式,所以没有任何磁盘寻址的开销,所以很快,有点像 Mysql 中的binlog。AOF更适合做 热备

优点:

AOF是一秒一次去通过一个后台的线程fsync操作,数据丢失不用怕。

缺点:

1、对于相同数量的数据集而言,AOF文件通常要大于RDB文件。RDB 在 恢复 大数据集时的速度比 AOF 的恢复速度要快。
2、根据同步策略的不同,AOF在运行效率上往往会慢于RDB。总之,每秒同步策略的效率是比较高的。

AOF整个流程分两步 :第一步是命令的实时写入,不同级别可能有1秒数据损失。命令先追加到 aof_buf 然后再同步到AO磁盘, 如果实时写入磁盘会带来非常高的磁盘IO,影响整体性能

第二步是对aof文件的 重写 ,目的是为了减少AOF文件的大小,可以自动触发或者手动触发( BGREWRITEAOF ),是Fork出子进程操作,期间Redis服务仍可用。

从应用到底层:36张图带你进入Redis世界(上)

1、在重写期间,由于主进程依然在响应命令,为了保证最终备份的完整性;它 依然会写入旧 的AOF中,如果重写失败,能够保证数据不丢失。
2、为了把重写期间 响应 的写入信息也写入到新的文件中,因此也会 为子进程保留一个buf ,防止新写的file丢失数据。
3、重写是直接把 当前内存的数据生成对应命令 ,并不需要读取老的AOF文件进行分析、命令合并。
4、 无论是 RDB 还是 AOF 都是先写入一个临时文件,然后通过 rename 完成文件的替换工作

关于Fork的建议:

1、降低fork的频率,比如可以手动来触发RDB生成快照、与AOF重写;
2、控制Redis最大使用内存,防止fork耗时过长;
3、配置牛逼点,合理配置Linux的内存分配策略,避免因为物理内存不足导致fork失败。
4、Redis在执行 BGSAVE BGREWRITEAOF 命令时,哈希表的负载因子>=5,而未执行这两个命令时>=1。目的是 尽量减少写操作 ,避免不必要的内存写入操作。
5、 哈希表的扩展因子 :哈希表已保存节点数量 / 哈希表大小。因子决定了是否扩展哈希表。

2.3、恢复

启动时会先检查AOF(数据更完整)文件是否存在,如果不存在就尝试加载RDB。

从应用到底层:36张图带你进入Redis世界(上)

2.4、建议

既然单独用RDB会丢失很多数据。单独用AOF,数据恢复没RDB来的快,所以出现问题了第一时间用RDB恢复,然后AOF做数据补全才说王道。

3、Redis为什么那么快

3.1、 基于内存实现:

数据都存储在内存里,相比磁盘IO操作快百倍,操作速率很快。

3.2、高效的数据结构:

Redis底层多种数据结构支持不同的数据类型,比如HyperLogLog它连2个字节都不想浪费。

3.3、丰富而合理的编码:

Redis底层提供了 丰富而合理的编码 ,五种数据类型根据长度及元素的个数适配不同的编码格式。

1、String:自动存储int类型,非int类型用raw编码。
2、List:字符串长度且元素个数小于一定范围使用 ziplist 编码,否则转化为 linkedlist 编码。
3、Hash:hash 对象保存的键值对内的键和值字符串长度小于一定值及键值对。
4、Set:保存元素为整数及元素个数小于一定范围使用 intset 编码,任意条件不满足,则使用 hashtable 编码。
5、Zset:保存的元素个数小于定值且成员长度小于定值使用 ziplist 编码,任意条件不满足,则使用 skiplist 编码。

3.4、合适的线程模型:

I/O 多路复用 模型同时监听客户端连接,多线程是需要上下文切换的,对于内存数据库来说这点很致命。

从应用到底层:36张图带你进入Redis世界(上)

3.5、 Redis6.0后引入多线程提速:

要知道 读写网络的read/write系统耗时 >> Redis运行执行耗时,Redis的瓶颈主要在于 网络的 IO 消耗 , 优化主要有两个方向:

1、提高网络 IO 性能,典型的实现比如使用 DPDK 来替代内核网络栈的方式
2、使用多线程充分利用多核,典型的实现比如 Memcached。

协议栈优化的这种方式跟 Redis 关系不大,支持多线程是一种最有效最便捷的操作方式。所以Redis支持多线程主要就是两个原因:

1、可以充分利用服务器 CPU 资源,目前主线程只能利用一个核
2、多线程任务可以分摊 Redis 同步 IO 读写负荷

关于多线程须知:

Redis 6.0 版本 默认多线程是关闭的 io-threads-do-reads no
Redis 6.0 版本 开启多线程后 线程数也要 谨慎设置。
多线程可以使得性能翻倍,但是多线程只是用来处理网络数据的读写和协议解析, 执行命令仍然是单线程顺序执行

4、常见问题

4.1、缓存雪崩

从应用到底层:36张图带你进入Redis世界(上)

雪崩定义:

Redis中大批量key在同一时间同时失效导致所有请求都打到了MySQL。而MySQL扛不住导致大面积崩塌。

雪崩解决方案:

1、缓存数据的过期时间加上个随机值,防止同一时间大量数据过期现象发生。
2、如果缓存数据库是分布式部署,将热点数据均匀分布在不同 得缓存数据库中。
3、设置热点数据永远不过期。

4.2、缓存穿透

穿透定义:

缓存穿透 是 指缓存和数据库中 都没有 的数据,比如ID默认>0,黑客一直 请求ID= -12的数据那么就会导致数据库压力过大,严重会击垮数据库。

穿透解决方案:

1、后端接口层增加 用户 鉴权校验 参数做校验 等。
2、单个IP每秒访问次数超过阈值 直接拉黑IP ,关进小黑屋1天,在获取IP代理池的时候我就被拉黑过。
3、从缓存取不到的数据,在数据库中也没有取到,这时也可以将key-value对写为key-null 失效时间可以为15秒 防止恶意攻击
4、用Redis提供的 Bloom Filter 特性也OK。

4.3、缓存击穿

从应用到底层:36张图带你进入Redis世界(上)

击穿定义:

现象:大并发集中对这一个热点key进行访问,当这个Key在失效的瞬间,持续的大并发就穿破缓存,直接请求数据库。

击穿解决:

设置热点数据永远不过期 加上互斥锁也能搞定了

4.4、双写一致性

双写: 缓存 数据库 均更新数据,如何保证数据一致性?

1、先更新数据库,再更新缓存

安全问题:线程A更新数据库->线程B更新数据库->线程B更新缓存->线程A更新缓存。 导致脏读
业务场景:读多写少场景,频繁更新数据库而缓存根本没用。更何况如果缓存是叠加计算后结果更 浪费性能

2、先删缓存,再更新数据库

A 请求 来更新缓存。
B 发现缓存不在去数据查询旧值后写入缓存。
A 将数据写入数据库,此时缓存跟数据库 不一致

因此 FackBook 提出了 Cache Aside Pattern

失效:应用程序先从cache取数据,没有得到,则从数据库中取数据,成功后,放到缓存中。
命中:应用程序从cache中取数据,取到后返回。
更新: 先把数据存到数据库中,成功后,再让缓存失效

4.5、脑裂

脑裂是指因为网络原因,导致master节点、slave节点 和 sentinel集群处于不用的网络分区,此时因为sentinel集群 无法感知 到master的存在,所以将slave节点提升为master节点 此时存在两个不同的master节点就像一个大脑分裂成了两个。其实在 Hadoop Spark 集群中都会出现这样的情况,只是解决方法不同而已(用ZK配合强制杀死)。

集群脑裂问题中,如果客户端还在基于原来的master节点继续写入数据那么新的master节点将无法同步这些数据,当网络问题解决后sentinel集群将原先的master节点降为slave节点,此时再从新的master中同步数据将造成大量的数据丢失。

Redis处理方案是redis的配置文件中存在两个参数

 min-replicas-to-write 3  表示连接到master的最少slave数量
min-replicas-max-lag 10  表示slave连接到master的最大延迟时间 

如果连接到master的slave数量 < 第一个参数 且 ping的延迟时间 <= 第二个参数那么master就会拒绝写请求,配置了这两个参数后如果发生了集群脑裂则原先的master节点接收到客户端的写入请求会拒绝就可以减少数据同步之后的数据丢失。