Redis数据结构
Redis是一个Key-Value的存储系统,使用ANSI C语言编写
key的类型:字符串
value的类型:string字符串类型、list列表类型、set集合类型、sortedset(zset)有序集合类型、hash类型。bitmap位图类型、geo地理位置类型。
Redis缓存过期和淘汰策略
缓存过期
长期使用,key会不断增加,Redis作为缓存使用,物理内存也会满
内存与硬盘交换(swap) 虚拟内存 ,频繁IO 性能急剧下降
淘汰策略
expire原理
定时删除
- 在设置键的过期时间的同时,创建一个定时器,让定时器在键的过期时间来临时,立即执行对键的删除操作。
-
惰性删除
-
主动删除
LRU(Least recently used)最近最少使用
LRU 数据淘汰机制是这样的:在数据集中随机挑选几个键值对,取出其中 lru 最大的键值对淘汰。不可能遍历key 用当前时间-最近访问 越大 说明 访问间隔时间越长。
算法步骤:
1. 新数据插入到链表头部;
2. 每当缓存命中(即缓存数据被访问),则将数据移到链表头部;
3. 当链表满的时候,将链表尾部的数据丢弃。
4. 在Java中可以使用LinkHashMap(哈希链表)去实现LRU
volatile-lru
从已设置过期时间的数据集(server.db[i].expires)中挑选最近最少使用的数据淘汰
allkeys-lru
从数据集(server.db[i].dict)中挑选最近最少使用的数据淘汰LFU (Least frequently used) 最不经常使用LFU (Least frequently used) 最不经常使用
random
volatile-random
从已设置过期时间的数据集(server.db[i].expires)中任意选择数据淘汰
allkeys-random
从数据集(server.db[i].dict)中任意选择数据淘汰TTL(time to live)
volatile-ttl从已设置过期时间的数据集(server.db[i].expires)中挑选将要过期的数据淘汰
Redis数据集数据结构中保存了键值对过期时间的表,即 redisDb.expires。
TTL 数据淘汰机制:从过期时间的表中随机挑选几个键值对,取出其中 ttl 最小的键值对淘汰。noenviction
缓存淘汰策略的选择
allkeys-lru : 在不确定时一般采用策略。 冷热数据交换
volatile-lru : 比allkeys-lru性能差 存 : 过期时间
allkeys-random : 希望请求符合平均分布(每个元素以相同的概率被访问)
自己控制:volatile-ttl 缓存穿透
Redis持久化
RDB方式
RDB(Redis DataBase),是redis默认的存储方式,RDB方式是通过快照( snapshotting )完成的
RDB执行流程(原理)
RDB的优缺点
优点:
- RDB是二进制压缩文件,占用空间小,便于传输(传给slaver)
- 主进程fork子进程,可以最大化Redis性能,主进程不能太大,Redis的数据量不能太大,复制过程中主进程阻塞
缺点:
- 不保证数据完整性,会丢失最后一次快照以后更改的所有数据
AOF方式
AOF(append only file)是Redis的另一种持久化方式。Redis默认情况下是不开启的。
以日志的形式记录服务器所处理的每一个写、删除操作,查询操作不会记录。
Redis 将所有对数据库进行过写入的命令(及其参数)(RESP)记录到 AOF 文件, 以此达到记录数据库状态的目的,AOF会记录过程,RDB只管结果。
AOF原理
AOF文件中存储的是redis的命令,同步命令到 AOF 文件的整个过程可以分为三个阶段:
命令传播
Redis 将执行完的命令、命令的参数、命令的参数个数等信息发送到 AOF 程序中。
缓存追加
AOF 程序根据接收到的命令数据,将命令转换为网络通讯协议的格式,然后将协议内容追加到服务器的 AOF 缓存中。
文件写入和保存
AOF 缓存中的内容被写入到 AOF 文件末尾,如果设定的 AOF 保存条件被满足的话, fsync 函数或者 fdatasync 函数会被调用,将写入的内容真正地保存到磁盘中。
AOF保存模式
不保存
在这种模式下, 每次调用 flushAppendOnlyFile 函数, WRITE 都会被执行, 但 SAVE 会被略过
每一秒钟保存一次(推荐)
在这种模式中, SAVE 原则上每隔一秒钟就会执行一次, 因为 SAVE 操作是由后台子线程(fork)调用的, 所以它不会引起服务器主进程阻塞。
每执行一个命令保存一次
在这种模式下,每次执行完一个命令之后, WRITE 和 SAVE 都会被执行。
另外,因为 SAVE 是由 Redis 主进程执行的,所以在 SAVE 执行期间,主进程会被阻塞,不能接受命令请求。
AOF重写
Redis可以在 AOF体积变得过大时,自动地在后台(Fork子进程)对 AOF进行重写。重写后的新 AOF文件包含了恢复当前数据集所需的最小命令集合。
本质:只保留最新的命令,如图
(1)AOF 重写程序放到(后台)子进程里执行,不会造成服务器无法处理请求
- 子进程进行 AOF 重写期间,主进程可以继续处理命令请求
- 子进程带有主进程的数据副本,使用子进程而不是线程,可以在避免锁的情况下,保证数据的安全性
(2)子进程在进行 AOF 重写期间, 主进程还需要继续处理命令,新的命令可能对现有的数据进行修改, 这会让当前数据库的数据和重写后的 AOF 文件中的数据不一致
- 增加了一个 AOF 重写缓存, 这个缓存在 fork 出子进程之后开始启用,Redis 主进程在接到新的写命令之后, 除了会将这个写命令的协议内容追加到现有的 AOF 文件之外,还会追加到这个缓存中。
AOF 后台重写, 也即是 BGREWRITEAOF 命令(AOF重写)的工作原理:(详细见讲义)
RDB与AOF对比
- RDB存某个时刻的数据快照,采用二进制压缩存储,AOF存操作命令,采用文本存储(混合)
- RDB性能高、AOF性能较低
- RDB在配置触发状态会丢失最后一次快照以后更改的所有数据,AOF设置为每秒保存一次,则最多丢2秒的数据(AOF的数据完整性比较强)
- Redis以主服务器模式运行,RDB不会保存过期键值对数据,Redis以从服务器模式运行,RDB会保存过期键值对,当主服务器向从服务器同步时,再清空过期键值对。
AOF写入文件时,对过期的key会追加一条del命令,当执行AOF重写时,会忽略过期key和del命令。
Redis高级
发布与订阅
Redis提供了发布订阅功能,可以用于消息的传输。
发布者和订阅者都是Redis客户端,Channel则为Redis服务器端。
发布订阅的机制
- 当客户端向某个频道发送消息时,Redis首先在redisServer中的pubsub_channels中找出键为该频道的结点,遍历该结点的值,即遍历订阅了该频道的所有客户端,将消息发送给这些客户端。
- 然后,遍历结构体redisServer中的pubsub_patterns,找出包含该频道的模式的结点,将消息发送给订阅了该模式的客户端。
使用场景:哨兵模式,Redisson框架使用
- 在Redis哨兵模式中,哨兵通过发布与订阅的方式与Redis主服务器和Redis从服务器进行通信。这个我们将在后面的章节中详细讲解。
- Redisson是一个分布式锁框架,在Redisson分布式锁释放的时候,是使用发布与订阅的方式通知的,这个我们将在后面的章节中详细讲解。
事务
所谓事务(Transaction) ,是指作为单个逻辑工作单元执行的一系列操作。Redis的事务是比较弱的。
- Atomicity(原子性):构成事务的的所有操作必须是一个逻辑单元,要么全部执行,要么全部不执行。
- Redis:一个队列中的命令 执行或不执行
- Consistency(一致性):数据库在事务执行前后状态都必须是稳定的或者是一致的。
- Redis: 集群中不能保证时时的一致性,只能是最终一致性
- Isolation(隔离性):事务之间不会相互影响。
- Redis: 命令是顺序执行的,在一个事务中,有可能被执行其他客户端的命令的
- Durability(持久性):事务执行成功后必须全部写入磁盘。
- Redis有持久化但不保证 数据的完整性
Redis事务
Redis的事务是通过multi(开始)、exec(执行)、discard(清除)和watch(监视)这四个命令来完成的。
Redis的单个命令都是原子性的,所以这里需要确保事务性的对象是命令集合。
Redis将命令集合序列化并确保处于同一事务的命令集合连续且不被打断的执行
Redis不支持回滚操作
watch功能:
监视机制的触发
- 当所监视的key被修改数据后,监视这个数据的客户端的flags置为REDIS_DIRTY_CAS
事务执行
- RedisClient向服务器端发送exec命令,服务器判断RedisClient的flags,如果为REDIS_DIRTY_CAS,则清空事务队列(打断事务的执行)
Redis的弱事务性
事务执行情况分析:
- Redis语法错误
整个事务的命令在队列里都清除
- Redis运行错误
在队列里正确的命令可以执行 (弱事务性,非原子操作)
弱事务性 :
- 在队列里正确的命令可以执行 (非原子操作)
- 不支持回滚
Lua脚本
慢查询日志
监视器
Redis客户端通过执行MONITOR命令可以将自己变为一个监视器,实时地接受并打印出服务器当前处理的命令请求的相关信息。
Redis高可用方案
1.主从复制
- 主从复制过程大体可以分为3个阶段
- 建立连接阶段(即准备阶段)
- 数据同步阶段
- 命令传播阶段
特点
- 主对外从对内,主可写从不可写(主负责 写,从负责 读)
- 主挂了,从不可为主
利用哨兵可以实现主从切换,做到高可用(下一个方案)
主从同步
全量同步过程
- 同步快照阶段: Master 创建并发送快照RDB给 Slave , Slave 载入并解析快照。 Master 同时将此阶段所产生的新的写命令存储到缓冲区。
- 同步写缓冲阶段: Master 向 Slave 同步存储在缓冲区的写操作命令。
- 同步增量阶段: Master 向 Slave 同步写操作命令
增量同步过程
- Redis增量同步主要指Slave完成初始化后开始正常工作时, Master 发生的写操作同步到 Slave 的过程
- 通常情况下, Master 每执行一个写命令就会向 Slave 发送相同的写命令,然后 Slave 接收并执行。
触发时机:
- Redis 的主从同步,分为全量同步和增量同步。
- 只有从机第一次连接上主机是全量同步
- 断线重连有可能触发全量同步也有可能是增量同步( master 判断 runid 是否一致)
- 除此之外的情况都是增量同步
2.哨兵模式
哨兵(sentinel)是Redis的高可用性(High Availability)的解决方案:由一个或多个sentinel实例组成sentinel集群可以监视一个或多个主服务器和多个从服务器。当主服务器进入下线状态时,sentinel可以将该主服务器下的某一从服务器升级为主服务器继续提供服务,从而保证redis的高可用性。
Sentinel启动流程:
Sentinel实例启动后每个Sentinel会创建2个连向主服务器的网络连接
命令连接:用于向主服务器发送命令,并接收响应;
订阅连接:用于订阅主服务器的—sentinel—:hello频道。
Sentinel彼此之间只创建命令连接,而不创建订阅连接
哨兵检测:
- Sentinel每秒一次向所有与它建立了命令连接的实例(主服务器、从服务器和其他Sentinel)发送PING命令,如果没有回复(或者超时),就认为主观下线(SDown)。
- Sentinel继续询问集群中其他Sentinel。如果达到Sentinel配置中的quorum数量的Sentinel实例都判断主服务器为主观下线,则该主服务器就会被判定为客观下线(ODown)。
哨兵leader选举(Raft协议)
Raft协议是用来解决分布式系统一致性问题的协议。Raft协议描述的节点共有三种状态:Leader, Follower, Candidate。
在同一个term内,先转为Candidate的节点会先发起投票,从而获得多数票。
Sentinel的leader选举流程
- 某Sentinel认定master客观下线后,该Sentinel会先看看自己有没有投过票,如果自己已经投过票给其他Sentinel了,在一定时间内自己就不会成为Leader
- 如果该Sentinel还没投过票,那么它就成为Candidate。
- Sentinel需要完成几件事情:
- 更新故障转移状态为start
- 当前epoch加1,相当于进入一个新term,在Sentinel中epoch就是Raft协议中的term
- 向其他节点发送 is-master-down-by-addr 命令请求投票。命令会带上自己的epoch
- 给自己投一票(leader、leader_epoch)
- 当其它哨兵收到此命令时,可以同意或者拒绝它成为领导者;(通过判断epoch)大者胜出?
- Candidate会不断的统计自己的票数,直到他发现认同他成为Leader的票数超过一半而且超过它配置的quorum,这时它就成为了Leader
- 其他Sentinel等待Leader从slave选出master后,检测到新的master正常工作后,就会去掉客观下线的标识。
故障转移
- 失效master的一个slave升级为新的master,其他slave复制新的master
- 集群返回新的master地址
- 哨兵leader自动修改配置文件,实现master和slave的指向
主服务器的选择
哨兵leader根据以下规则从客观下线的主服务器的从服务器中选择出新的主服务器
- 过滤掉主观下线的节点
- 选择slave-priority最高的节点,如果由则返回没有就继续选择
- 选择出复制偏移量最大的节点,因为复制偏移量越大则数据复制的越完整,如果有就返回了,没有就继续
- 选择run_id最小的节点,因为run_id越小说明重启次数越少
3.集群与分区
分区方式
1)范围分区
优点:
实现简单,方便迁移和扩展
2)hash分区
优点:
支持任何类型的key
热点分布较均匀,性能较好
缺点:
迁移复杂,需要重新计算,扩展较差(利用一致性hash环解决)
一致性hash算法
一致性hash是对2^32(4 294 967 296)取模
被缓存对象的位置出发,沿顺时针方向遇到的第一个服务器,就是当前对象将要缓存于的服务器。
优点:
添加或移除节点时,数据只需要做部分的迁移,比如上图中把C服务器移除,则数据4迁移到服务器A中,而其他的数据保持不变。添加效果是一样的。
hash环偏移:采用虚拟节点的方式来解决,映射到环上。
官方cluster分区(完美解决方案)
去中心化
RedisCluster由多个Redis节点组构成,是一个P2P无中心节点的集群架构,依靠Gossip协议传播的集群。
Gossip协议
基本思想:
- 一个节点周期性(每秒)随机选择一些节点,并把信息传递给这些节点
- 这些收到信息的节点接下来会做同样的事情,即把这些信息传递给其他一些随机选择的节点。
- 信息会周期性的传递给N个目标节点。这个N被称为fanout(扇出)
哈希槽slot
redis-cluster把所有的物理节点映射到[0-16383]个slot上,基本上采用平均分配和连续分配的方式。
RedisCluster的优势
- 高性能
- 多主节点、负载均衡、读写分离
- 性能和单节点部署相同
- 高可用
- 支持标准的 主从复制配置来保障高可用和高可靠
- failover 容灾
- 实现了一个类似 Raft 的共识方式,来保障整个集群的可用性
- 易扩展
- 添加新节点,或者移除节点,都是透明的,不需要停机
- 水平、垂直方向都非常容易扩展
- 数据分区,海量数据,数据存储
- 原生
- 部署 Redis Cluster 不需要其他的代理或者工具,而且 Redis Cluster 和单机 Redis 几乎完全兼容
容灾(failover)
故障检测
- 集群中的每个节点都会定期地(每秒)向集群中的其他节点发送PING消息
- 如果在一定时间内(cluster-node-timeout),发送ping的节点A没有收到某节点B的pong回应,则A将B标识为pfail。A在后续发送ping时,会带上B的pfail信息, 通知给其他节点。
- 如果B被标记为pfail的个数大于集群主节点个数的一半(N/2 + 1)时,B会被标记为fail,A向整个集群广播,该节点已经下线。
- 其他节点收到广播,标记B为fail。
从节点选举
变更通知
主从切换
副本漂移
一主一从的情况下,如果主从同时挂了,那整个集群就挂了。
Redis提供了一种方法叫副本漂移,这种方法既能提高集群的可靠性又不用增加太多的从机。
Redis经典问题解析
缓存问题
1)缓存穿透
高并发下查询key不存在的数据,会穿过缓存查询数据库。导致数据库压力过大而宕机。
解决:
使用布隆过滤器。在缓存之前在加一层布隆过滤器,在查询的时候先去布隆过滤器查询 key 是否存在,如果不存在就直接返回,存在再查缓存和DB。
2)缓存雪崩
突然间大量(很多)的key失效了或redis重启,大量访问数据库,数据库崩溃。
解决:
- key的失效期分散开 不同的key设置不同的有效期
- 设置二级缓存(数据不一定一致)
- 高可用(脏读)—主要防止redis重启
3)缓存击穿
某些key可能会在某些时间点被超高并发地访问,是一种非常“热点”的数据。
区别于雪崩:
这里是针对某一“热点”的key,雪崩是很多key失效。
解决:
- 用分布式锁控制访问的线程
- 使用redis的setnx互斥锁先进行判断,这样其他线程就处于等待状态,保证不会有大并发操作去操作数据库。
- 不设超时时间,volatile-lru 但会造成写一致问题
- 当数据库数据发生更新时,缓存中的数据不会及时更新,这样会造成数据库中的数据与缓存中的数据的不一致,应用会从缓存中读取到脏数据。可采用延时双删策略处理。
4)数据不一致
根源: 数据源不一样
解决:强一致性很难,追求最终一致性(时间)
保证数据的最终一致性(延时双删)
- 先更新数据库同时删除缓存项(key)。此时可能有其他进程又来读,是的缓存中又出现删除的key。
- 2秒后再删除一次缓存项(key)
- 设置缓存过期时间 Expired Time 比如 10秒 或1小时
- 将缓存删除失败记录到日志中,利用脚本提取失败记录再次删除(缓存失效期过长 7*24)
5)数据并发竞争
这里的并发指的是多个redis的client同时set 同一个key引起的并发问题
解决:第一种方案:分布式锁+时间戳
准备一个分布式锁,大家去抢锁,抢到锁就做set操作。
加锁的目的实际上就是把并行读写改成串行读写的方式,从而来避免资源竞争。
第二种方案:利用消息队列
在并发量过大的情况下,可以通过消息中间件进行处理,把并行读写进行串行化。
把Redis的set操作放在队列中使其串行化,必须的一个一个执行。
6)Hot Key
当有大量的请求(几十万)访问某个Redis某个key时,由于流量集中达到网络上限,从而导致这个redis的服务器宕机。造成缓存击穿,接下来对这个key的访问将直接访问数据库造成数据库崩溃,或者访问数据库回填Redis再访问Redis,继续崩溃。
解决:
- 变分布式缓存为本地缓存
- 发现热key后,把缓存数据取出后,直接加载到本地缓存中。可以采用Ehcache、Guava Cache都可以,这样系统在访问热key数据时就可以直接访问自己的缓存了。(数据不要求时时一致)
- 在每个Redis主节点上备份热key数据,这样在读取时可以采用随机读取的方式,将访问压力负载到每个Redis上。
-
7) Big Key
大key指的是存储的值(Value)非常大
问题: 大key会大量占用内存,在集群中无法均衡
- Redis的性能下降,主从复制异常
- 在主动删除或过期删除时会操作时间过长而引起服务阻塞(del是阻塞命令)
解决:
- string类型的big key,尽量不要存入Redis中
- 单个简单的key存储的value很大,可以尝试将对象分拆成几个key-value, 使用mget获取值,这样分拆的意义在于分拆单次操作的压力,将操作压力平摊到多次操作中,降低对redis的IO影响。
- hash, set,zset,list 中存储过多的元素,可以将这些元素分拆。(常见)
- 删除大key时不要使用del,因为del是阻塞命令,删除时会影响性能。
- 使用 lazy delete (unlink命令)
- 删除指定的key(s),若key不存在则该key被跳过。但是,相比DEL会产生阻塞,该命令会在另一个线程中回收内存,因此它是非阻塞的。 这也是该命令名字的由来:仅将keys从key空间中删除,真正的数据删除会在后续异步操作。
分布式锁
Watch实现Redis乐观锁
乐观锁基于CAS(Compare And Swap)思想(比较并替换),是不具有互斥性,不会产生锁等待而消耗资源,但是需要反复的重试,但也是因为重试的机制,能比较快的响应。
实现步骤:
- 利用redis的watch功能,监控这个redisKey的状态值
- 获取redisKey的值
- 创建redis事务
- 给这个key的值+1
- 然后去执行这个事务,如果key的值被修改过则回滚,key不加1
setnx
实现原理:
- 共享资源互斥
- 共享资源串行化
- 利用Redis的单线程特性对共享资源进行串行化处理
Redisson分布式锁的实现原理
加锁机制
锁互斥机制
自动延时机制
只要客户端1一旦加锁成功,就会启动一个watch dog看门狗,他是一个后台线程,会每隔10秒检查一下,如果客户端1还持有锁key,那么就会不断的延长锁key的生存时间。
可重入锁机制
释放锁机制
逐层释放
分布式锁特性
- 互斥性
- 任意时刻,只能有一个客户端获取锁,不能同时有两个客户端获取到锁。
- Redis : setnx set key value NX 如果key存在就不设置
- 同一性
- 锁只能被持有该锁的客户端删除,不能由其它客户端删除。
- Redis : lua 实现原子性
- 可重入性
- 持有某个锁的客户端可继续对该锁加锁,实现锁的续租
- 容错性
- 锁失效后(超过生命周期)自动释放锁(key失效),其他客户端可以继续获得该锁,防止死锁
- expire 设置超时时间
- set key value NX PX
Redis底层数据结构
1、sorted-set
- 底层实现:跳跃表
- 将有序链表中的部分节点分层,每一层都是一个有序链表。
- 在查找时优先从最高层开始向后查找,当到达某个节点时,如果next节点值大于要查找的值或next指针指向null,则从当前节点下降一层继续向后查找。(类似二分查找的功能)
2、hash字典
Redis字典实现包括:字典(dict)、Hash表(dictht)、Hash表节点(dictEntry)。
友臣