redis数据结构原理
简单字符串SDS(叫Simple dynamic string)
struct sdshdr{
//记录buf数组中已使用字节的数量
//等于 SDS 保存字符串的长度
int len;
//记录 buf 数组中未使用字节的数量,提前多分配点空间,防止反复重复分配内存空间
int free;
//字节数组,用于保存字符串
char buf[];
}
- len:获取长度时无需再遍历,时间复杂度O(1)
- free:提前多分配点空间,防止反复重复分配内存空间
链表
Redis的链表实际为增强版双向链表,添加了头、尾节点,以及长度。
typedef struct list{
//表头节点
listNode *head;
//表尾节点
listNode *tail;
//链表所包含的节点数量
unsigned long len;
//节点值复制函数
...
//节点值释放函数
...
//节点值对比函数
...
}list;
- *head、*tail: 可以很方便的直接获取链表的头、尾节点
- len: 可以直接获取链表长度
字典
Redis字典采用的是数组+链表实现,没有使用红黑树优化
字典定义:
typedef struct dictht{
//哈希表数组
dictEntry **table;
//哈希表大小
unsigned long size;
//哈希表大小掩码,用于计算索引值
//总是等于 size-1
unsigned long sizemask;
//该哈希表已有节点的数量
unsigned long used;
}dictht
其中最关键的就是table字段,这是一个dictEntry,存放键值对。
typedef struct dictEntry{
//键
void *key;
//值
union{
void *val;
uint64_tu64;
int64_ts64;
}v;
//指向下一个哈希表节点,形成链表
struct dictEntry *next;
}dictEntry
- key 用来保存键,val 属性用来保存值,值可以是一个指针,也可以是uint64_t整数,也可以是int64_t整数。
- 注意这里还有一个指向下一个哈希表节点的指针,我们知道哈希表最大的问题是存在哈希冲突,采用的是链地址法,通过next这个指针可以将多个哈希值相同的键值对连接在一起
- 如何解决hash冲突?
字典里面的 *next 指针指向下一个具有相同索引值的哈希表节点
- 扩容和收缩
公式: ht[0].used*2n。 每次扩展都是根据原哈希表已使用的空间扩大一倍创建另一个哈希表,相反如果执行的是收缩操作,每次收缩是根据已使用空间缩小一倍创建一个新的哈希表。
利用上面的哈希算法,计算索引值,然后将键值对放到新的哈希表位置上,释放老表内存。
- 触发扩容缩容条件:
负载因子决定:负载因子 = 哈希表已保存节点数量 / 哈希表大小。
- 渐进式rehash技术
扩容和收缩操作不是一次性、集中式完成的,而是分多次、渐进式完成的。
渐进式rehash期间,字典的删除查找更新等操作可能会在两个哈希表上进行,第一个哈希表没有找到,就会去第二个哈希表上进行查找。但是进行增加操作,一定是在新的哈希表上进行。
跳跃表
redis持久化
RDB持久化
- 执行流程
- 父进程执行fork操作创建子进程,这个过程中父进程是阻塞的,Redis不能执行来自客户端的任何命令。
- 子进程创建RDB文件,根据父进程内存快照生成临时快照文件,完成后对原有文件进行原子替换,替换后子进程信号通知主进程
- rdb自动持久化配置:
时间策略要按照实际情况配置多条,数据的存储时不均匀的,高峰期短时间间隔要存一次,低峰期长时间间隔要存一次。
# 文件名称
dbfilename dump.rdb
# 时间策略
save 900 1
save 300 10
save 60 10000
# 文件保存路径
dir /etc/redis/data/
# 如果持久化出错,主进程是否停止写入
stop-writes-on-bgsave-error yes
# 是否压缩
rdbcompression yes
# 导入时是否检查
rdbchecksum yes
- rdb策略将内存中的数据生成快照保存到磁盘,是全量存储,内存大的话会比较耗时,大量磁盘io。
- 持久化的触发方式:
- save命令:client向server发送save命令,同步阻塞。
- bgsave命令:server中执行命令,异步子进程执行。
- 自动持久化,通过save配置项完成。
- rdb文件恢复:如果开启了aof,则不生效。如果没开启aof,则寻找dir配置下的rdb文件。
AOF持久化
- aof同步步骤:
- Redis收到写命令后首先会追加到AOF缓冲区aof_buf(write)
- 通过一定时机(配置决定),调用系统函数 fsync() 把AOF缓冲区的数据刷到磁盘
- 落盘时机配置(fsync):
always: 命令写入aof缓冲区后立即调用系统fsync操作同步到AOF文件,数据绝对安全。
no:有操作系统决定何时调用fsync()
everysec:每秒调fsync()一次。 若损失数据只损失1秒,对于大多数系统来说足够了。
- 文件重写rewrite
- 由父进程fork子进程进行重写
- 使用写时重写技术,在重写完成期间,Redis的写命令同时追加到aof_buf和aof_rewirte_buf两个缓冲区。
- 重写文件完成后,将aof_rewirte_buf数据输入新文件
- 用新aof文件替换老aof文件。
redis集群三种模式
主从模式(实现主从分离,提高吞吐,多机备份)
从数据库一般都是只读的,并且接收主数据库同步过来的数据
要点:
- 主从复制还是哨兵和集群能够实施的基础,主从复制是Redis高可用的基础。
- 再看CAP,由于redis复制是异步复制,会导致短时的数据不一致,所以无法满足一致性C,但可以保证当网络分区发生时,各个节点依旧可用。redis主从模式是AP,而不是CP。redis会使用最终一致性策略,保证主从同步数据一致。
- 主从复制实现原理:
- 6大步骤: 1. 设置主节点ip及端口、2. 建立套接字socket、 3. 发送ping命令、 4. 权限验证 、 5. 同步 6. 命令传播
- 设置主节点ip及端口: 使用slaveof命令,可配置文件使用、可命令行使用
- 复制阶段:从节点向主节点发送psync或sync命令(2.8版本之前),可以实现全量复制与增量复制
- 命令传播:当通过复制阶段后,主从节点进入命令传播阶段,主节点将自己执行的写命令发送给从节点,从节点接收命令并执行,从而保证主从节点数据的一致性。命令传播是异步的,主节点并不会等从节点同步执行完命令,这样会导致“延迟不一致”现象。
- 延迟不一致现象:网络波动、写命令频率过高,会导致数据延迟不一致。同时,repl-disable-tcp-nodelay配置也会影响,设置为yes,会将代发数据合并发送,延迟大概40ms(取决于系统),如果设置为no,写命令实时发送同步。
- 全量复制和部分复制
- 全量复制:用于初次复制或其他无法进行部分复制的情况,将主节点中的所有数据都发送给从节点,是一个非常重型的操作
- 部分复制:用于网络中断等情况后的复制,只同步网络断开期间的缓存写数据,如果网络中断时间过长,导致主节点没有能够完整地保存中断期间执行的写命令,则无法进行部分复制,仍使用全量复制。
- 全量复制原理剖析:
fork子进程,开始执行bgsave,生成RDB文件,同时开辟缓冲区记录从现在开始的写命令。2. 将rdb文件传输给从服务器,从服务器执行完毕后,主节点将缓冲区写数据同步到从节点,保证最终一致性。3. 如果从节点开启了AOF,会触发bgrewriteof,从而保证从节点的aof文件最新。
- 部分复制原理剖析:
- 复制偏移量:与mysql类似,主从节点各自维护offset字段,不一致则复制
- 复制积压缓冲区:底层结构是定长、先进先出FIFO的队列,可以repl-backlog-size参数设置大小。 当主从节点offset的差距过大超过缓冲区长度时,将无法执行部分复制,只能执行全量复制。
- 服务器运行id(runid):每个从节点都存储着主节点同步下来的runid,当网络分区发生时,重连后slave节点会判断同步的runid是否存在,如果存在优先考虑增量复制,如果不存在,则全量复制。
- psync命令复制原理:主节点收到psync命令后,进行判断,如果命令为psync命令,则执行全量复制。如果收到的为psync {runid} {offset}命令,则执行增量复制。执行增量复制过程中如果offset差超过了buffer,则执行全量复制。
- 心跳检测机制及其作用:1. 检测主从链接 2. 辅助实现min-slaves选项 3. 检测命令丢失,保证数据一致
- 通过判断在线的从节点数量,实现min-slaves。
min-slaves概念,保证高可用:
未达到下面两个条件时,写操作就不会被执行
min-slaves-to-write 3 #最少包含的从服务器
min-slaves-max-lag 10 #延迟值
- 心跳会返回offset信息,通过offset判断从节点的数据同步是否及时,不及时则通过offset补发数据
- 主从复制超时原理:断开连接后会尝试重连。
- 主节点判断超时:每秒1次调用复制定时函数replicationCron(),如果时间大于到上次REPLCONF ACK的时长,则断开连接,释放资源(缓冲器、连接、带宽),超时时间由参数repl-timeout值控制。
- 从节点判断超时:主要也是由repl-timeout参数控制。1. 连接建立阶段,若大于时间则断开连接。 2. 全量复制阶段:如果收到rdb的时间超时,则断开连接。 3. 命令传播阶段:如果收到主节点ping的时间过长,超过timeout,则断开连接。
- 如果rdb文件过大,会导致一直同步失败,会无线重连,应适当调大timeout值
- 主库挂了发生什么?
不影响slave的读,但redis不再提供写服务,master重启后redis将重新对外提供写服务。
如果slave-serve-stale-data参数设置为yes,主节点挂掉后从节点可以继续提供服务,如果设置为no,主节点挂掉后从节点不再提供读数据服务,仅提供info、slaveof等少量命令。在强一致场景需要考虑设置为no,如分布式锁,如果主节点挂掉,数据没来得及同步从节点,会导致从节点读不到,锁失效。
重启master节点需要保证rdb文件或者aof文件是最新。
- redis如何保证主从服务器连接正常且数据最终一致?
命令传播阶段,从服务器会利用心跳检测机制定时的向主服务发送消息。
- 如果提高数据实时一致性?
优化主从节点之间的网络环境(如在同机房部署);监控主从节点延迟(通过offset)判断,如果从节点延迟过大,通知应用不再通过该从节点读取数据;
- java客户端连接redis如何实现读写分离,读负载均衡?
常见的客户端有jredis,lettuce,redission。以lettuce为例,可以使用
StatefulRedisMasterSlaveConnection connection = MasterSlave.connect(redisClient, new Utf8StringCodec(), redisURI);
connection.setReadFrom(ReadFrom.NEAREST);
// MASTER 主读
// SLAVE 从读
// MASTER_PREFERRED 优先master -> slave
// SLAVE_PREFERRED 优先slave -> master
// NEAREST 最近节点读
// 实现很简单,重写ReadFrom的select方法,自带的方法均无法实现负载均衡
static final class ReadFromSlavePreferred extends ReadFrom {
@Override
public List<RedisNodeDescription> select(Nodes nodes) {
List<RedisNodeDescription> result = new ArrayList<>(nodes.getNodes().size());
//优先添加slave节点
for (RedisNodeDescription node : nodes) {
if (node.getRole() == RedisInstance.Role.SLAVE) {
result.add(node);
}
}
//最后添加master节点
for (RedisNodeDescription node : nodes) {
if (node.getRole() == RedisInstance.Role.MASTER) {
result.add(node);
}
}
return result;
}
// 自定义负载均衡
@Bean(destroyMethod = "close")
StatefulRedisMasterSlaveConnection<String, String> statefulRedisMasterSlaveConnection(RedisClient redisClient, RedisURI redisURI) {
StatefulRedisMasterSlaveConnection connection = MasterSlave.connect(redisClient, new Utf8StringCodec(), redisURI);
connection.setReadFrom(new ReadFrom() {
@Override
public List<RedisNodeDescription> select(Nodes nodes) {
List<RedisNodeDescription> list = nodes.getNodes();
Collections.shuffle(list);
return list;
}
});
return connection;
}
哨兵模式(主从高可用,自动化修复)
- 高可用架构一般将sentinel与redis实例部署在不同的服务器上。
- 工作机制:每个sentinel以每秒钟一次的频率向它所知的master,slave以及其他sentinel实例发送一个 PING 命令 。如果响应超过 down-after-milliseconds,则标记为主观下线。其它sentinel以每秒钟一次的频率ping主观下线的实例,如果足够多的(通过配置指定)sentinel确认该实例的主观下线状态,则置为客观下线。Sentinel 和其他 Sentinel 协商 主节点 的状态,如果 主节点 处于 SDOWN 状态,则投票自动选出新的 主节点。将剩余的 从节点 指向 新的主节点 进行 数据复制
- 当使用sentinel模式的时候,客户端就不要直接连接Redis,而是连接sentinel的ip和port,由luttuce自动获取redis集群拓扑,从而获取master节点与slave节点的信息。并通过监听redis事件更新拓扑信息。
- 哨兵模式切换主节点导致数据不一致,“脑裂问题”的解决方案:
- 当网络分区发生时,会导致master下线,实际master没有挂,选举出新的master后会出现两个master,当网络分区修好后,旧master会变为slave同步新master的数据,导致数据丢失。
配置:
min-slaves-to-write 1 # 必须至少要有1个slave
min-slaves-max-lag 10 # 数据复制和同步延迟不能超过10秒
不符合以上情况,master将拒绝接受请求。将数据丢失控制在10秒。
从业务上看,及其重要的数据,可以进行处理:
进redis前可以在其它地方临时存储。
可以加网关,降低流入速度,防止瞬间进入过多数据。
集群模式(数据分片,解决了写操作无法负载均衡,单机容量存储、并发问题)
- 一致性hash与hash槽
- 简单hash算法,通过计算hash值 % 机器数量,得到数据的实际对应节点。当增加或删除节点时,会导致大量的缓存失效,甚至导致雪崩。
- 一致性哈希算法中,整个哈希空间是一个虚拟圆环,共计2^32 - 1 个节点。将每个redis节点的ip地址进行hash计算后落位虚拟节点。每条数据通过计算hash值后顺时针落位对应节点。当某个节点增、删、不可用时,只会影响下一个节点,而不会影响所有节点。
一致性hash算法的问题是会导致数据倾斜,如果节点数过少,在盘中的分布又不均匀,可能会导致所有数据都落在极少的节点上。
- 哈希槽,redis包含了16384个哈希槽,每个 key 通过计算后都会落在具体一个槽位上,而这个槽位是属于哪个存储节点的,则由用户自己定义分配。
对于槽位的转移和分派,redis 集群是不会自动进行的,而是需要人工配置的。所以 redis 集群的高可用是依赖于节点的主从复制与主从间的自动故障转移。
- redis-cluster是redis集群的官方实现版,具有投票、容错性等特点。
- 集群中可以有多个master节点,需要保证所有master节点恰好覆盖所有hash槽,否则集群不能启动。添加、删除节点,只需要更改对应的哈希槽范围。
node1 : [1,15000]
node2 : [15001,20000]
…
- 何时master节点算挂掉?
半数以上master节点与master节点通信超时(cluster-node-timeout),认为当前master节点挂掉,如果此时该master节点由slave节点,则集群依旧正常运行,对应挂掉的节点不再提供写入服务。
- 何时集群挂掉?
1.只要某个槽段失效,集群就会进入不可用状态。主、从都挂。
2.超过半数的master节点挂掉,不管slave是否正常,集群不可用。
- 一般情况,各个槽段的主、从redis节点可以交叉部署,部署在不同的服务器上。
数据淘汰机制
redis线程模型与IO模型
redis应用场景
分布式锁
- 单机版分布式锁:
- 加锁终极版:set nx px + 事务id
- 解锁终极版:使用lua脚本实现。
if redis.call(“get”,KEYS[1]) == ARGV[1] then
return redis.call(“del”,KEYS[1])
else
return 0
end
- 为何解锁需要用lua,而加锁不需要?
加锁过程,set命令的 nx 参数 = set if not exist,get value->判断不存在->set value。set 命令的 px参数,设置过期时间。相当于三条命令保持原子性。
解锁过程,get获取键值,判断value是否相等,如果此时JVM
分布式限流:RedisRateLimiter原理与实现
原理是使用redis setnx ex + lua 实现令牌桶,完成限流。
原理:
- redis中存两个健,一个键是存储当前令牌桶中的令牌数,一个键存储的是最新操作的时间戳。
- 给令牌桶中加令牌的触发机制是由调用方调用,每次调用通过存储的时间戳与当前时间,得出增加的令牌数 = 时间间隔 * 速率
总令牌数 = min (令牌桶容量,计算得到的令牌数)
- 使用过后,将剩余的令牌数与最新操作时间set回去
注意点:
- 键过期时间 = 填充时间*2,防止填充时间还没满,就过期消失了。
在每一次调用时,会续时长。
如果很长时间没用调用,则键消失,此时认为桶容量为capacity,并且上一次更新时间为0。
但是如果正在使用中键过期了,会导致桶容量为capacity,导致限流失败(漏过去的多了)
- 如果当前令牌桶中的令牌不够,则返回失败,直接set两个键完成数据更新即可。
- 此种模式可以保证redis单机模式下的数据绝对安全,不会出现超过限流的流量,但是主从模式、集群模式下本质都会出现主节点过掉,键同步丢失,导致限流超流现象,但不影响业务使用,马上即可恢复正常。
以下代码是springcloud-apigateway中的redis限流原理源码,为lua脚本
// redis的对应key
local tokens_key = KEYS[1]
//
local timestamp_key = KEYS[2]
// 每秒放行个数
local rate = tonumber(ARGV[1])
// 桶容量
local capacity = tonumber(ARGV[2])
// 每次请求消耗数
local now = tonumber(ARGV[3])
// 当前时间微妙
local requested = tonumber(ARGV[4])
// 容量/多少个每秒 = 填充时间
local fill_time = capacity/rate
/*
* lua 中的math.floor函数是向下取整函数。
math.floor(5.123) -- 5
math.floor(5.523) -- 5
填充时间好毫秒*2 向下取整 = ttl
键过期时间 = 填充时间*2,防止填充时间还没满,就过期消失了。
在每一次调用时,会续时长。
如果很长时间没用调用,则键消失,此时认为桶容量为capacity,并且上一次更新时间为0。
但是如果正在使用中键过期了,会导致桶容量为capacity,导致限流失败(漏过去的多了)
*
*/
local ttl = math.floor(fill_time*2)
// 上一个token
local last_tokens = tonumber(redis.call("get", tokens_key))
// 如果上一个token不存在,则上一个token初始化为桶容量
if last_tokens == nil then
last_tokens = capacity
end
// 上一个刷新时间戳
local last_refreshed = tonumber(redis.call("get", timestamp_key))
// 如果上一个刷新时间戳不存在,则置为0
if last_refreshed == nil then
last_refreshed = 0
end
// 时间间隔
local delta = math.max(0, now-last_refreshed)
// 已填充的token数量 = 取最小值(容量,上一次的token数 + 系统闲置时长*每秒放行个数)
local filled_tokens = math.min(capacity, last_tokens+(delta*rate))
// 如果token总数 >= 本次请求需要的token数量,则请求通过
local allowed = filled_tokens >= requested
local new_tokens = filled_tokens
local allowed_num = 0
// 如果请求通过,则剩余token = 总token - 本次请求token数量
if allowed then
new_tokens = filled_tokens - requested
allowed_num = 1
end
// 设置当前令牌桶中的总token数
redis.call("setex", tokens_key, ttl, new_tokens)
// 设置本次操作时间
redis.call("setex", timestamp_key, ttl, now)
// 如果本次获取锁成功,则返回allowed_num = 1,剩余token数 = 总token数filled_tokens - 本次获取token数requested
// 如果本次获取锁失败,则返回allowed_num = 0,剩余token数 = 总token数filled_tokens
return { allowed_num, new_tokens }
保存token应用
主要利用到了redis的expire过期时间的性质。
获取token:
... 获取新的token ...
// 将token存放入redis中
operations.set(token, tokenInfo, 7200, TimeUnit.SECONDS);
在后续接口中使用token,可在拦截器中实现。
// 校验Token是否存在,必须加token
ValueOperations<String, TokenInfo> tokenRedis = redisTemplate.opsForValue();
// 其中redis的键token是uuid字符串,用来获取tokenInfo的
TokenInfo tokenInfo = tokenRedis.get(token);
Assert.notNull(tokenInfo, "token错误");
防重复点击应用
- 可以自定义一个注解
// 防重复提交注解
@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface NotRepeatSubmit {
// 过期时间,单位毫秒,默认1秒
long value() default 1000;
}
- 在拦截器中实现。 判断是否有此注解。
如果有此注解,先将接口的数字签名存入redis,并设置过期时间为expireTime。
第二次调用时判断该redis key是否存在,如果仍然存在,则不能再次调用。并重新设置
ValueOperations<String, Integer> signRedis = redisTemplate.opsForValue();
// 第二次调用判断是否存在
boolean exists = redisTemplate.hasKey(sign);
Assert.isTrue(!exists, "请勿重复提交");
// 第一次调用存入key
signRedis.set(sign, 0, expireTime, TimeUnit.MILLISECONDS);
redis架构思维
如何保证缓存与数据库数据一致性?
- 淘汰缓存(有一次缓存miss):
- 失效:应用程序先从cache取数据,没有得到,则从数据库中取数据,成功后,放到缓存中。
- 命中:应用程序从cache中取数据,取到后返回。
- 更新:先把数据存到数据库中,成功后,再让缓存失效。
- 总结:此种缓存是用的最多的一种缓存,由于先更新数据库,再删除缓存,高并发下有可能读到脏数据,并且如果缓存删除失败,会一直是脏数据。要保证缓存key有过期时间。但过期时间设置要随机,否则会同时失效大量缓存导致缓存雪崩。
- 更新缓存,加了一次更新DB后自动更新缓存操作。可以防止大量缓存一起失效。
- 缓存和DB一致性的解决方案
上面的淘汰缓存,还是更新缓存,都可能产生脏数据(因为是先更新的数据库),为保证缓存一致性,总结下列方案
- 先淘汰缓存,再写数据库。这是非常必要的!先删掉缓存,去除脏数据。
但是以上在高并发下又有一种可能的问题出现
(1)请求A进行写操作,删除缓存;
(2)请求B查询发现缓存不存在;
(3)请求B去数据库查询得到旧值;
(4)请求B将旧值写入缓存;
(5)请求A将新值写入数据库;
此时A缓存中的数据是脏数据
- 终极解决方案:缓存双删:
redis.delKey(X)
db.update(X)
Thread.sleep(N)
redis.delKey(X)
其中第二次删除key,可以使用异步方式(mq)实现,这样就能解决脏数据问题,但是延迟删除的时间需要调整,一般1秒,过小也有可能导致缓存失效。
缓存雪崩、缓存穿透 、缓存击穿
- 缓存雪崩
缓存雪崩,由于缓存中有大量数据同时过期失效或者缓存出现宕机,大量的应用请求无法在 Redis 缓存中进行处理,进而发送到数据库层导致数据库层的压力激增,严重的会造成数据库宕机。
解决方案:
- 数据预热
- 设置不同的过期时间,让缓存失效的时间点尽量均匀
- 服务降级,非核心数据直接返回预定义信息
- 缓存穿透
缓存穿透,数据在数据库和缓存中都不存在,这样就导致查询数据,在缓存中找不到对应key的value,都要去数据库再查询一遍,然后返回空(相当于进行了两次无用的查询)。
当有大量访问请求,且其绕过缓存直接查数据库,导致数据库层的压力激增,严重的会造成数据库宕机。
解决方案:
- 缓存空值或缺省值,当一个查询返回的数据为空时, 空结果也将进行缓存,并将它的过期时间设置比较短
- 布隆过滤器( BloomFilter ),将所有可能查询数据key哈希到一个足够大的bitmap中 , 在查询的时候先去BloomFilter去查询key是否存在,如果不存在就直接返回,存在再去查询缓存,缓存中没有再去查询数据库 ,从而避免了数据库层的压力激增出现宕机
- 缓存击穿
缓存击穿,针对某个访问非常频繁的热点数据过期失效,导致访问无法在缓存中进行处理,进而会有导致大量的直接请求数据库。
解决方式:
- 不设置过期时间,对于访问特别频繁的热点数据,不设置过期时间
Redis性能高的原因