talk about consensus algorithm and distributed lock


关于一致性协议, 分布式锁以及如何使用分布式锁

最近看antirez 和 Martin 关于redlock 的分布式锁是否安全的问题的争吵, 非常有意思

http://martin.kleppmann.com/2016/02/08/how-to-do-distributed-locking.html

http://antirez.com/news/101

https://news.ycombinator.com/item?id=11065933

https://news.ycombinator.com/item?id=11059738

背景

关于分布式锁其实这里面是包含3个问题, 每一个都是独立的不相关的问题

  1. 一致性协议的问题
  2. 如何通过一致性协议实现分布式锁的问题
  3. 如何结合业务场景使用分布式锁

问题1和问题2 容易混淆, 其实实现一个分布式锁只是需要一个key-value store 就可以了, 但是因为需要这个key-value store 高可用, 那么就必然需要这个key-value store 多副本, 多副本又需要强一致, 那么就必然引入一致性协议了

chubby 的论文里面讲的就是如何基于一致性协议paxos 实现一个分布式锁服务, 跟一致性协议一点关系都没有. 里面很重要的一个观点是为什么要实现一个锁服务, 用户使用一个锁服务相比于直接提供一个一致性协议的库有哪些地方更方便

  1. lock 提供的高可用性肯定比直接提供一致性协议的库要来的低, 相当于通过lock 实现强一致和直接通过一致性协议提供强一致的业务逻辑
  2. 有些场景很难改成通过一致性协议的场景
  3. 分布式锁的使用方式和之前单机是使用Lock 的方式一样的直观, 对使用人员的要求无成本
  4. 有时候用户只有少量的机器, 比如只有两个机器, 就无法通过一致性协议提供强一致, 但是通过外部的锁服务可以

在分布式锁里面有两个要求

  1. safety

    任意时刻只能有一个 node 去获得这个lock

  2. liveness

    这个lock 是在某一个时刻是会终止的

其实这两点是互相矛盾的, 存在这个问题的本质原因是因为在分布式系统里面我们无法判断一个节点真的挂掉还是只是网络分区一会这个网络又会恢复

所有的distribute lock 的实现都存在的一个问题是, 在获得这个锁以后, 如果拿了这个锁的节点死掉了, 或者网络永久断开了, 那么这个锁也就死锁了. 就违背了 liveness 的问题, 为了解决这个问题, 几乎所有的distribute lock 都会加上一个时间的限制, 但是这个时间的限制又会有一个问题就是如果获得这个锁的节点, 在拿到锁以后, 执行的操作的时候超过了这个时间的限制, 那么我们改怎么办? 那么这个时候就有可能被其他的节点也获得这个锁, 那么就违背了 safety 的限制.

因此在我们操作系统的lock 里面选择的是死锁, 所以操作系统有liveness 的问题, 而大部分的distribute lock 的实现选择的是给这个lock 加上lease, 如果超过了这个lease, 依然返回, 我认为你这个lock 已经失效了, 可以把这个lock 给其他的节点. 因此在使用distribute lock 的时候需要注意的是尽可能在锁区间的操作应该是可预期的, 尽可能时间短的.

观点

主要喷antirez 有问题的地方在于两个:

  1. 这种auto release lock 会存在的问题是, 用户获得lock 操作以后, redlock 的做法有一个lease, 如果在这个lease 里面不执行unlock 操作, 系统只能认为你已经挂掉. 那么在过了lease 时间以后, 另外一个node 获得了这个Lock, 那么有可能第一个节点并没有挂掉(这里是java gc 黑的最惨的地方哈哈哈), 那么这个时候系统就无法保证只有一个leader, 这个lock 也就没用了
  2. 第二个就比较直接了, 就是通过时间戳来保证底下的强一致. 这个是被喷的最惨的, 这个就没什么好解释的了

那么Martin 提供的带递增Token 的方法是不是解决了这个问题呢?

Imgur

其实我觉得Martin 说的带fencing Token 的方法是通过拿到锁的系统必须能够保证提供一个支持cas 操作检查的系统才行, 能够检查写入的Token 是否比之前的token 都大, zk 使用的也是类似的方法. 但是不解决刚才我们说的safety 的问题, 因为在使用带Token 的方法里面也是无法保证某一个时刻只能有一个节点获得这个lock, 只是通过额外的一个系统里面写入的时候检查这个Token 来避免这个问题. 所以从整体上来看是解决了这个问题, 但是其实是需要使用lock 的服务提供 cas 操作才行.

所以我认为从整体上看, 除非你底下获得Lock 操作以后, 需要做的事情非常简单, 那么可以通过fencing token 来做保证, 但是更多的工程里面获得lock 以后的操作比较复杂, 所以很难想Martin 说的那样能够实现这个cas 操作. 所以floyd 提供的lock 基本就是基于一致性协议raft + lease 实现的auto release lock

结论

回头开头的3个问题, 如果实现一致性协议就不说了.

如何实现分布式锁呢?

那么大体的实现就是给在节点lock 的时候, 对于这个lock 操作有一个lease的时候, 如果在这个租约的时间内, 这个节点没有来续租, 那么就认为这个操作是超时的, 一般情况为了实现的可靠性保证, 会在这个租约失效前就提前续租, 比如租约的时间是 10s, 我在0s 的时候就获得这个lock, 那么我在6s 的时候就必须去做这个续租操作, 如果没有执行成功的话, 那么我就认为你这个lease 失效了, 其他的节点可以在6s 时刻就获得这个lock, 但是只能在10s以后提供服务, 新的节点的租约时间是10s~20s. 那么从6s~10s 这段时间即使新节点获得了lock, 但是也无法提供服务的, 这个是典型的CAP 场景里面系统availability 换取consistenty 的例子.

那么如何使用分布式锁呢?

在pika_hub 的场景里面, 有一个专门的线程每3s去获得这个lock, 在获得这个lock 以后, 就认为自己是 pika_hub 的leader, 然后建立与所有的pika 节点的连接. 如果在某一个时刻其他的pika_hub 节点抢到了这个lock, 那么就说明之前的pika_hub 节点已经挂掉, 或者超时. 那么如何Pika_hub 节点在6s的时刻发现自己获得这个lock 失败, 那么该如何操作呢? 这个时刻 pika_hub 将与 pika 建立连接的线程都杀死, 这个时候其实有6s~10s 这一段4s 的时间, 我们认为在工程实现里面4s 可以完成这个操作. 那么其他节点就算在6s的时候执行Lock() 操作依然是获得不了这个lock(), 因为这个lock() 虽然没有被更新lease, 但是lease 依然在有效期内的. 那么等到10s 以后才有一个新的节点抢到这个lock(). 这个时候新的节点成为leader 与其他的Pika 节点建立连接, 所以系统中可能存在最多13s的没有leader 的时间

在zeppelin 里面, 也一样有专门的线程去获得这个lock, 在获得这个lock 以后, 将自己是leader 的信息写入到floyd 里面, 然后做leader 该做的事情. 和pika_hub 的处理方式一样, 如果发现无法和floyd 交互了, 那么就把自己改成follower 的信息. 不一样的地方在于因为这里使用floyd 作为storage, 那么其实可以通过类似Martin 提供的方式进行类似cas 的操作来更新. 这里也可以看出就像 antirez 喷 Martin 一样, 并不是所有的获得锁以后的操作都可以改成cas 的操作, 比如pika_hub 就不可以

最后, 看到最后的肯定是真爱, 欢迎关注我们的项目 floyd https://github.com/Qihoo360/floyd