内容来源


RedLock 算法

这里只简单的叙述下算法流程,相关的安全可靠性分析、性能、持久化与故障恢复等其他原理要点详见原文

流程

graph TB
a("获取当前时间<br>(单位毫秒)") --> b("轮流用相同的key和随机值在<br>N个节点上请求锁")
b --> f("Master节点不可用")
f --> |<br>尝试下一个Master|b
b --> c("1.多数节点获得锁<br>2.总消耗时间不超过锁释放时间")
c --> |成功|d("锁释放时间=最初锁释放时间-消耗时间")
c --> |失败|e("客户端到每个master节点上释放锁<br>(包括认为没有获取成功的锁)")
e --> g("获取锁失败的节点要等待<br>一定时间后才可重新尝试获取锁")

争议及反争议

这里提取一下 Martin 提出的争议点,给出部分相关英文原文,并试着分析官方原作者的回复

以效率为目的使用RedLock算法过于繁复,成本过高

it is unnecessary to incur the cost and complexity of Redlock, running 5 Redis servers and checking for a majority to acquire your lock.

这个其实不是 Martin 的主要争议点所以原作者 antirez 回复的并不多

超时机制问题及没有任何生成栅栏令牌(fencing token)的机制

it does not have any facility for generating fencing tokens

Martin 认为由于故障导致超时、后又恢复的情况存在,获取锁的客户端会不知道自己的锁已超时,从而破坏锁的唯一性,导致持有新锁客户端的锁被误释放掉等,因此需要单调递增保证的栅栏令牌的存在保证锁只能由最新持有它的客户端释放掉(PS:其实这的意思就是 CAS 算法了)

antirez 认为这种说法是很奇怪的,因为如果能够生成全局唯一的单调递增的token,说明锁保证的共享存储系统是线性化(linearizable)的,而既然是线性化的,那其本身应该就带有生成全局唯一自增ID的能力,没有栅栏令牌的问题迎刃而解

事实上共享资源写入的存储系统往往并不是线性化的存储系统,所以没有全局唯一自增ID保证。但这并不重要,因为靠现有的随机机制(如:从/dev/urandom中取几十字节)生成一个大的随机令牌完全可以解决这个问题,虽然没有单调递增,但哈希碰撞基本可以忽略

antirez 指出了这个问题本身蕴含的前提是非常奇怪的,就是他似乎总有办法在互斥锁的唯一性已经被破坏之后解决唯一性问题。然而事实上如果真的存在这样的方法,为了正确性而要求的强一致性保证互斥锁本身就不需要了

I want to mention again that, what is strange about all this, is that it is assumed that you always must have a way to handle the fact that mutual exclusion is violated.

时间估测在解决共识问题上的不可靠性

The only purpose for which algorithms may use clocks is to generate timeouts, to avoid waiting forever if a node is down.

Redlock assumes that delays, pauses and drift are all small relative to the time-to-live of a lock; if the timing issues become as large as the time-to-live, the algorithm fails.

关于这个问题,按照 Martin 的论证思路大概如下 ↓

  • 时间估测只适用于处理超时,而 RedLock 超时以外利用了还大量的估测了时间

    • 使用了gettimeofday这一非原子钟的系统函数
    • 锁机制因为时间估计被破坏的两个例子
  • 对系统模型的同步性假设过于严格,包括对有界的网络延迟/进程暂停/时钟错误等的假设

(PS:其实本质上都是同样的系统时钟不同步问题)

antirez 认可关于gettimeofday的说法,RedLock 的实现确实应该使用操作系统提供的原子时间函数,并表示下面几周立刻修改算法实现(……),然而这并不是重点,即使是gettimeofday在没有人工修改系统时间(人工破坏不能算数否则根本没有能运行的协议了)的情况下也是可以良好的计算相对时间的,因为在实际工程环境上误差并不会总有 Martin 描述的夸张的随机性,大多数时候还是可以知道一个固定的最大误差百分比,然后在此条件下运行的

而 Martin 举的两个例子取其核心思想概括一下,一个是在获得锁的过程中超时,另一个则是获得锁后超时

关于第一个,这里需要再审视一下上面提到的流程,可以发现有如下内容↓

graph LR
a(获取当前时间) --> b(获取锁)
b --> c("再次获取当前时间<br>检查是否超时")
c --> d("相关操作")

很明显可以看到获取锁过程中如果超时,获取锁后会检测出来,视为失败(这里估计是 Martin 没细看?),并不影响

而至于获取锁后超时的过程,antirez 再次强调这个问题是宽泛的,因为获取锁后的每一步都有可能遭遇进程暂停、网络延迟等等等等,而我们不可能每一步操作都检测一遍锁是否超时


总结

第一次读到 RedLock 算法是在 JavaQ 公众号的分布式锁方案(之前的博文里有提到)那篇文章里,里面提到了我非常关心却又没明白的所谓解决主从复制存在问题的 RedLock 算法,但对原理引用的比较粗略,单从引用的原理部分并没看出如何解决了主从复制的问题。

刚好过些日子又在 Qix 里看到了原文、对原文算法的争议以及作者对争议的回复,遂抽时间出来仔细读了读。

我自己真正开始学习分布式的时间还非常短,对很多核心问题、相关算法的论述基本都停留在照葫芦画瓢,能理解却还不能深入思考形成自己见解的学习程度上。在地铁上看完 Martin 的分析时就隐约觉得表面上看分析很完整,提出的缺陷也确实都是存在的,但——

基本上这并不只是 RedLock 算法,而是每个分布式锁方案都存在的问题。有些讨论本身已经跨出了算法层面

作者 Martin 提到(或者说引用)的核心观点之一:不能用时间作为解决一致性正确的标准,理由是网络延迟、进程暂停、系统时钟跳跃都会造成分布式系统时间的误差

上述时间问题可能发生在两个阶段:获得锁的过程中(如等待Redis实例的响应时),获得锁之后。作者举的坏时机(bad timings)示例(具体见上文)明显是属于获得锁之后的问题。而获得锁之后遇到的网络延迟、进程暂停、系统时钟跳跃、持久化失效重启导致的锁失效破坏问题是任何一种分布式算法都存在的、普遍性的问题

FLP 不可能原理告诉我们,即使是网络可靠的情况下,只要存在节点失效(即便只有一个),就不存在一个可以解决一致性问题的确定性算法。而两军对垒问题又告诉我们在使用不可靠通信的情况下,不存在能完成信道两侧同一方绝对达成一致这一任务的协议。

graph LR
a(蓝军1号) --> |通信|b["必经之地<br>(白军驻守)"]
b --> |通信|c(蓝军2号)
c --> |通信|b
b --> |通信|a

分布式系统兼具网络不可靠节点会失效两大特点,任何场景下绝对一致的算法自然是不存在的,而上述的普遍性问题自然也无法被彻底的解决

↑基本上,看完争议分析篇我是这么认为的,等看到原作者的反分析后惊喜的发现我想的没错 ~(≧▽≦)/~,这确实是个重要的反驳点↓

O(∩_∩)O哈哈~

嘿嘿嘿

看到自己的想法跟官方一致,感觉非常开心,这至少说明这回独立的形成了有价值的想法和理解,之前杂七杂八塞得知识多多少少也转化成自己的东西了。

快扶我起来,我的分布式学习还可以再抢救一下


其他参考

Written with StackEdit.