Redlock 算法-主从redis分布式锁主节点宕机锁丢失的问题

本文涉及的产品
云数据库 Redis 版,社区版 2GB
推荐场景:
搭建游戏排行榜
简介: Redlock 算法-主从redis分布式锁主节点宕机锁丢失的问题


先介绍两个概念

Safety Properties, 在程序运行中不会进入非预期的状态(如非法调用参数, 数组下标越界等运行错误) Liveness Properties, 在程序运行中预期状态一定会到达(如停机, 获取资源请求一定有返回结果等等)

保证分布式锁有效的三个属性

  1. Safety Properties:安全性,此处也就是互斥性,任意时刻只能有一个客户端可以持有锁
  2. Liveness Property A:无死锁,即使持有锁的客户端崩溃或被分区,也可以获得锁
  3. Liveness Property B:容错性,只要大多数 Redis 节点正常,客户端就能获取和释放锁

为什么基于故障转移(failover-based)的实现还不够

我们先来看看现有大多数 Redis 分布式锁的实现

最简单的方案是在一个实例中创建一个 key,并给这个 key 设置过期时间,保证这个锁最终一定能够释放,当客户端释放锁的时候,删除这个 key

看上去可能不错,但是有个问题:当我们的 Redis 主节点挂掉时会发生什么?好,那我们增加一个从节点,当主节点不可用时自动切换到从节点。但不幸地是这不行,因为 Redis 复制是异步的,所以不能保证互斥性

在这个方案下有一个明显的竞态条件:

  1. 客户端 A 在 master 节点获取锁
  2. 在写 key 操作被传输到 slave 节点前 master 节点挂了
  3. slave 晋升为 master
  4. 客户端 B 获取 A 其实刚刚已经获取到的锁 SAFETY VIOLATION 违反了文章开头提到的安全属性

虽然有上述缺陷,但在一些特殊场景下,这种方案还是可以使用的。比如故障发生的时候,多个客户端同时持有锁对于系统运行或者业务逻辑没有太大影响,那么就可以使用这种基于复制的解决方案。否则最好还是使用本文后续将会提到的 Redlock 算法

单实例情况下正确的实现

在解决单实例单点故障的限制前,我们先来看看如何正确地执行它

获取一个锁的方式: set resource_name my_random_value NX PX 30000

解释:

  • 在 resource_name 不存在(NX 选项)的时候创建它,并设置过期时间为 30000 毫秒
  • 值是一个随机值,而且这个值在每个客户端和每个锁请求中都是唯一的,这样做的目的是为了能够安全地释放锁,不会出现 A 客户端获取的锁被 B 客户端删除的情况。使用一段简单的 lua 代码告诉 Redis,只有 key 存在而且值与当前客户端持有的值相等时才删除这个 key
if redis.call("get", KEYS[1]) == ARGV[1] then
  return redis.call("del", KEYS[1])
else
  return 0
end
复制代码

防止由其他客户端创建的锁被错误删除非常重要

举个例子,当一个客户端获取了锁,并因一些长时间的操作,阻塞时间超过了锁的可用时间(key 过期时间)导致 key 被删除,然后该 key 又被其它客户端创建(也就是其它客户端获得锁)

如果前一个客户端在后一个客户端用完锁前进行了释放锁的操作,就导致了实际上现在属于后一个客户端的锁被删除

所以必须使用上面的脚本保证客户端释放的一定是自己持有的锁,而且随机值的生成很重要,必须是全局唯一

接下来我们把上述的算法扩展到分布式的情况

Redlock 算法

在算法的分布式版本中,假设有 N 个 Redis 节点。而且这些节点全都是相互独立的,都是 master 节点,且不使用分布式协调方案。假设 N=5 ,即部署 5 个 Redis master 节点在不同的机器(或虚拟机)上

客户端需要进行如下的操作来获取锁:

  1. 获取当前时间(毫秒)
  2. 尝试按顺序在 N 个节点获取锁(set 相同的 key value)。客户端在每个节点请求锁时,使用一个相对总的锁过期时间而言非常小的请求超时时间。例如锁过期时间为 10s,那么请求超时时间应该设置在大约 5~50ms 之间。这可以防止客户端在一个挂掉的节点上长时间阻塞:如果实例不可用,我们应该尝试尽快与下一个实例
  3. 客户端计算获取锁所花的时间(当前时间减去第一步中的时间)。当且仅当客户端在大多数节点上(至少三个)都成功获得了锁,而且总时间消耗小于锁有效时间,锁被认为获取成功
  4. 如果锁获取成功了,那么它的有效时间就是最初的锁有效时间减去之前获取锁所消耗的时间
  5. 如果因为某些原因,锁获取失败了(无论是不能在大部分节点成功获取锁,还是锁有效时间小于 0),将会尝试释放所有节点的锁(即使是那些没有获取成功的节点)

这个算法是异步的吗

这个算法依赖于一个假设:即使在没有同步时钟机制的两个进程中,每个进程的本地时间仍然以相同的速率前进,即使有误差,这个误差时间相对于锁自动释放时间也是极小到可以忽略的。这个假设非常像现实世界中的计算机:每台计算机都有一个本地时钟,我们经常相信不同的计算机的时间差是很小的 在这一点上需要再细化一下互斥锁的规则:必须确保客户端在 锁过期时间-跨进程的时间差(clock drift) 时间内做完自己所有的工作 更多相关信息可以阅读这篇有趣的文章:Leases: an efficient fault-tolerant mechanism for distributed file cache consistency

错误重试

当一个客户端不能获得锁时,它应该在随机延迟后再次尝试,避免大量客户端同时获取锁的情况出现,这种情况下可能发生脑裂(split brain condition),导致大家都获取不了锁。另外,客户端越快尝试在大多数节点中获取锁,出现脑裂情况的时间窗口就越小。所以理想的情况下,客户端应该并行同时向全部节点发起获取锁请求 这里有必要强调一下,客户端在没有成功获取锁时,一定要尽快并行在全部节点上释放锁,这样就没有必要等到 key 超时后才能重新获取这个锁(但是如果网络分区的情况发生,客户端无法连接到 Redis 节点时,会损失锁自动过期释放这段时间内的系统可用性)

释放锁

释放锁比较简单,因为只需要所有节点都释放锁都行,不管之前有没有在该节点获取成功锁

安全性论证

这个算法到底是不是安全的,我们可以观察一些不同情况下的表现

我们假设客户端可以在全部节点上获取成功锁,所有的节点将会有一个相同存活时间的 key。但要注意,这个 key 是在不同时间设置的,所以 key 也会在不同时间超时。如果在最坏情况下,第一个 key 在 T1 时间设置(在发起请求前采样),最后一个 key 在 T2 时间设置(在服务器响应后采样),我们可以确认最早超时的 key 至少也会至少存在 MIN_VALIDITY=TTL-(T2-T1)-CLOCK_DRIFT 时间。所有其他的 key 超时都会大于这个时间,所以我们可以确定至少在这个时间点前这些 key 都是同时存在的

在大部分节点都设置了 key 的时候,其他客户端无法抢占这个锁,因为 N/2+1 SET NX 操作在 N/2+1 个 key 存在的情况下无法成功。所以如果一个锁被获取成功了,就不可能重新在同一时间获取它(违反了安全属性)

此外我们还需要确保多个客户端同时获取锁时不会同时成功

如果一个客户端获取大多数节点的锁的耗时接近甚至超过锁的最大有效时间,那么系统就会认为这个锁是无效的,并全部解锁。所以我们只需要考虑在大多数节点获取锁的耗时小于锁有效时间的情况。在前面讨论的案例中可知,在 MIN_VALIDITY 时间内,没有客户端能成功重新获取锁。所以多个客户端只可能在在大多数节点上获取锁的时间大于 TTL 时才可以,这会导致锁失效

可用性(liveness)论证

系统可用性基于三个特性:

  1. 自动释放锁(基于 key 过期):最终锁一定能够再次被获取
  2. 现实情况下客户端一般都会主动释放锁,所以我们不需要等到 key 过期才能再去获取锁
  3. 当客户端发起重试获取锁的请求时,它会等待一段比去大多数节点获取锁的时间更长的时间,这会降低多个客户端同时请求锁而发生脑裂状态的概率

然而,我们在网络分区发生的时候会损失 TTL 时间的系统可用性,所以如果分区连续发生,不可用也会持续。这种情况在每次客户端获得锁并在释放锁前遇到了网络分区的情况时都会发生

基本上,如果持续的网络分区的话,系统也会持续不可用

性能、故障后恢复和 fsync

很多用户使用 Redis 做分布式锁服务时,不但要求加解锁要低延迟,还要求高吞吐量(每秒能够执行加/解锁操作的次数)。为了达到这个需求,可以通过多路复用并行和 N 个服务器通信,或者也可以将 socket 设置为非阻塞模式,一次性发送全部的命令,之后再一次性处理全部返回的命令,假设客户端和不同 Redis 服务节点的网络延迟不大的话

为了能够实现故障恢复,我们需要考虑关于持久化的问题 假设有一个客户端成功得获取了锁(至少 3/5 个节点成功),而已经成功获得锁的其中一个节点重启了,那么我们就又有了 3 个可以分配锁的节点,这样其它客户端就又可以成功获得锁了,违反了互斥锁的安全性原则

如果启用了 AOF 持久化,情况会好很多。例如我们可以发起 SHUTDOWN 请求并重启服务器,因为 Redis 超时时间是语义层面的,所以在服务器关掉期间超时还是存在的,所以过期策略仍然存在 但如果是意外停机呢?如果 Redis 被配置为每秒同步数据到磁盘一次(默认),可能在重启的时候丢失一些 key。理论上,如果我们要确保锁在任何重启的情况下都安全,就必须设置 fsync=always。但这样会完全牺牲性能,使其和传统的 CP 系统的分布式锁方案没有区别

但事情往往不像第一眼看上去这么糟糕,基本上,只要一个服务节点挂了重启后不去管系统中现有活跃的锁,这样当节点重启时,整个系统中活跃的锁必然是由正在已获得锁的客户端使用的,而不是新加入系统的

为了确保这一点,只需让崩溃重启的实例,在最大锁有效时间内不可用,令该节点的旧锁信息全部过期释放

使用延迟重启基本上可以解决安全性问题,但要注意,这可能会造成可用性的下降:当系统内的大多数节点都挂了,那么在 TTL 时间内整个系统都处于不可用状态(无法获得锁)

使算法更可靠:扩展锁

如果客户端执行的工作由小的步骤组成,那么可以使用比较小的 TTL 时间来设置锁,并在锁快过期时刷新锁有效时间(续约)。但在技术上不会改变算法本质,因此应该限制重新获取锁尝试的最大次数,不然会违反可用性


相关实践学习
基于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
目录
相关文章
|
7天前
|
存储 监控 NoSQL
【Redis】分布式锁及其他常见问题
【Redis】分布式锁及其他常见问题
34 0
|
7天前
|
NoSQL Java Redis
【Redis】Redis实现分布式锁
【Redis】Redis实现分布式锁
8 0
|
7天前
|
算法 调度 决策智能
基于元模型优化算法的主从博弈多虚拟电厂动态定价和能量管理(matlab代码)
基于元模型优化算法的主从博弈多虚拟电厂动态定价和能量管理(matlab代码)
|
7天前
|
监控 NoSQL 算法
探秘Redis分布式锁:实战与注意事项
本文介绍了Redis分区容错中的分布式锁概念,包括利用Watch实现乐观锁和使用setnx防止库存超卖。乐观锁通过Watch命令监控键值变化,在事务中执行修改,若键值被改变则事务失败。Java代码示例展示了具体实现。setnx命令用于库存操作,确保无超卖,通过设置锁并检查库存来更新。文章还讨论了分布式锁存在的问题,如客户端阻塞、时钟漂移和单点故障,并提出了RedLock算法来提高可靠性。Redisson作为生产环境的分布式锁实现,提供了可重入锁、读写锁等高级功能。最后,文章对比了Redis、Zookeeper和etcd的分布式锁特性。
145 16
探秘Redis分布式锁:实战与注意事项
|
7天前
|
NoSQL Java 大数据
介绍redis分布式锁
分布式锁是解决多进程在分布式环境中争夺资源的问题,与本地锁相似但适用于不同进程。以Redis为例,通过`setIfAbsent`实现占锁,加锁同时设置过期时间避免死锁。然而,获取锁与设置过期时间非原子性可能导致并发问题,解决方案是使用`setIfAbsent`的超时参数。此外,释放锁前需验证归属,防止误删他人锁,可借助Lua脚本确保原子性。实际应用中还有锁续期、重试机制等复杂问题,现成解决方案如RedisLockRegistry和Redisson。
|
7天前
|
负载均衡 监控 NoSQL
Redis的几种主要集群方案
【5月更文挑战第15天】Redis集群方案包括主从复制(基础,读写分离,手动故障恢复)、哨兵模式(自动高可用,自动故障转移)和Redis Cluster(官方分布式解决方案,自动分片、容错和扩展)。此外,还有Codis、Redisson和Twemproxy等工具用于代理分片和负载均衡。选择方案需考虑应用场景、数据量和并发需求,权衡可用性、性能和扩展性。
152 2
|
7天前
|
存储 监控 负载均衡
保证Redis的高可用性是一个涉及多个层面的任务,主要包括数据持久化、复制与故障转移、集群化部署等方面
【5月更文挑战第15天】保证Redis高可用性涉及数据持久化、复制与故障转移、集群化及优化策略。RDB和AOF是数据持久化方法,哨兵模式确保故障自动恢复。Redis Cluster实现分布式部署,提高负载均衡和容错性。其他措施包括身份认证、多线程、数据压缩和监控报警,以增强安全性和稳定性。通过综合配置与监控,可确保Redis服务的高效、可靠运行。
151 2
|
7天前
|
存储 NoSQL Redis
Redis源码、面试指南(5)多机数据库、复制、哨兵、集群(下)
Redis源码、面试指南(5)多机数据库、复制、哨兵、集群
178 1
|
7天前
|
监控 NoSQL Redis
Redis源码、面试指南(5)多机数据库、复制、哨兵、集群(上)
Redis源码、面试指南(5)多机数据库、复制、哨兵、集群
225 0
|
7天前
|
存储 监控 NoSQL
Redis哨兵&分片集群
Redis哨兵&分片集群
27 0