分布式锁

技术 · 2019-05-29

锁
在单进程的系统中，当存在多个线程可以同时改变某个变量（可变共享变量）时，就需要对变量或代码块做同步，使其在修改这种变量时能够线性执行消除并发修改变量。
而同步的本质就是通过锁实现。如 Java 中 synchronize 是在对象头设置标记，Lock 接口的实现类基本上都只是某一个 volitile 修饰的 int 型变量，其保证每个线程都能拥有对该 int变量 的可见性和原子修改，linux 内核中也是利用互斥量或信号量等内存数据做标记。
Mutex互斥量
pthread中，mutex保护了临界区，一个时刻只有一个线程在临界区活动。
mutex分为两种，可重入（Reentrant）和非可重入。
Condition Variable条件变量
条件变量，顾名思义就是一个或多个线程等待某个布尔表达式为真。即等待别的线程“唤醒”它。
而这个管理临界区，并控制布尔表达式为真的进程，就叫做管程（Monitor）。
java的Synchronized、以及Object的wait() notify() notifyAll() 都是条件变量，都是管程。
通过java提供的Synchronized、ReentrantLock等，可以保证单个JVM进程中多线程请求的线程安全。所以分布式环境下呢？

分布式锁
要实现以下几点：

  1. 互斥性：多个客户端同一时间只能有一个访问
  2. 可重入：避免死锁
  3. 锁超时：避免由于单点故障或网络故障造成的死锁
  4. 支持公平锁与非公平锁

数据库
数据库悲观锁
实现方式：通过select for update在查询数据时增加排它锁，查询到数据的线程可以进行业务操作，执行后，通过commit方法释放锁。
InnoDB引擎在加锁时，通过索引检索的字段才会使用行级锁，否则使用表级锁。
（不建议使用）
数据库乐观锁
实现方式：基于MVCC机制，为相关表增加字段时间戳或者版本号，只有当前版本号大于等于数据库中版本号时方可进行更新。如果更新不成功，会重新读取数据，类似CAS机制。
唯一缺点是：对数据库表的侵入较大，需要增加一个字段，而且增加了数据库的访问次数，高并发情况下对数据库连接数的开销较大。
（建议灵活使用）
上述两种基于数据库的实现方式都很简单，但还有一些问题：

  1. 数据库的性能和可用性直接影响锁
  2. 无法可重入（增加一列，存放线程号、机器id等信息）
  3. 无法过期失效（增加一列失效时间，定时任务执行失效操作）
  4. 无阻塞队列，获取不到锁直接失败（增加一个额外的表，记录申请信息）
    Redis
    SETNX & expire & delete
    key不存在时，set一个key为val的字段，返回1；若key存在，直接返回0； 使用expire 为key设置一个超时时间，过期自动删除。同时也可以使用del命令手动删除key。
    使用步骤：
  5. setnx(key, 1)，如果返回0，说明获取锁失败；返回1，则说明获取锁成功
  6. expire() 对key设置超时时间，避免死锁
  7. 执行完业务代码后，执行delete命令，删除key，释放锁
    Q: 如果在delete前，发生了宕机，就会有死锁情况
    方法升级：（使用getset()方法）
    使用步骤：
  8. setnx(key, 当前时间+超时时间)，返回1，表示获取锁成功；返回0，就是获取锁失败，进行第二步
  9. get(key)， 获取oldExpireTime，将此值与当前系统时间比较，如果oldExpireTime < nowTime，则改锁已过期，可以重新获取，进行第三步
  10. getset(key, 当前时间+超时时间)，返回当前key的过期时间expireTime
  11. 如果expireTime = oldExpireTime，说明getset设置成功，获取到了锁；如果不相等，那就是没有获取到锁，可以返回失败，或重试
  12. 获取到锁之后，处理当前业务，处理完成后，比较当前时间和锁的超时时间，如果当前时间小于锁超时时间，执行delete释放锁；如果不小于，则不需要进行处理
    RedisLockRegistry
    使用本地可重入锁先进行加锁，本地加锁成功后，再使用Lua脚本对redis进行加锁操作。适用于单redis节点下不复杂的场景。
    （建议灵活使用）
    RedLock
    步骤如下：
  13. 客户端获取当前时间，以毫秒为单位。
  14. 客户端尝试获取N个节点的锁，N个节点以相同的key和value获取，设置接口超时时间，远小于锁超时时间。并且携带锁的过期时间，在某个节点获取锁失败后，应该立即获取下一个节点。
  15. 计算整个获取锁的过程，即用当前时间减去第一步的时间。如果客户端获取到了大多数的节点，且总耗时小于锁的有效时间，那么获取锁成功；反之，获取失败。
  16. 如果获取成功，那么该锁的有效时间为锁的总有效时间减去步骤三计算出的获取耗时。
  17. 如果获取锁失败了（获取到锁的节点数量小于N/2+1 或者 获取锁的耗时大于锁的有效时间），那么应该立即执行释放锁的操作。
    Martin Kleppmann在2016-02-08这一天发表了一篇blog，名字叫"How to do distributed locking"，对redLock方案进行分析

总体来说，假使锁本身没有问题，是由于客户端长时间的暂停或者网络延迟，造成了两个客户端同时访问共享资源，即打破了锁的一致性。
所Martin提出了一种方法：fencing token，使用一个单调递增的数字，避免延迟请求的冲突。

除了上面的问题，Martin还提出了另一个使得RedLock失效的情况：（假使有5个redis节点 ABCDE）

  1. 客户端1 从 redis节点ABC 处获取了锁（大多数），而DE由于网络问题失败
  2. 节点C上的时钟发生跳跃，导致C上的锁快速过期
  3. 客户端2从CDE获取到了锁（大多数）
  4. 客户端1和客户端2都认为自己持有该锁
    上面的时钟跳跃如果不会发生，然后Martin又给出了另一个RedLock失效的例子。
  5. 客户端1 向ABCDE发起锁的请求
  6. 各个redis节点都返回了结果给客户端1，但是客户端1在接收结果前就发生了pause（GC）
  7. 所以redis节点上，锁过期了
  8. 客户端2 从ABCDE上获取了锁
  9. 客户端1从pause中恢复，获取到了第二步的来自各个redis节点的请求结果
  10. 客户端1和客户端2都认为自己持有改锁
    以上两个例子简单说，都是锁在发给客户端的途中，就过期了，但是缺乏有效的机制让客户端明确知道锁已过期。所以Martin还有一个很有见地的间接---锁的用途：
  11. 为了效率。不会产生不良后果，只是带来了重复性的操作
  12. 为了正确性。任何情况下都不允许锁失效，不允许出现数据不一致的情况
    结论：
  13. 如果为了效率，那单redis节点足够了，redLock过重
  14. 如果为了正确性，redLock没有类似fencing token的机制，应该使用zk或其他支持事务的数据库
    antirez对上面的反驳
    主要是包括两个方面：
  15. 带有自动过期的分布式锁，需要有fencing机制，来对共享资源进行互斥保护
  16. redLock构建在不安全的系统模型之上，对系统的时间假设（timing assumption）有比较强的要求
    进行的反驳：
  17. fencing机制虽然redLock并没有，但是会生成随机的字符串（my_random_value），是唯一的，可以在使用时，采用CAS原理，确认有效时才会启用

  18. 算法在计时（timing）方面的模型假设，redLock失效有以下三种情况：

    • 时钟跳跃
    • 长时间的GC pause
    • 长时间的网络延迟

    第一个是最致命的，所以antirez表示通过恰当的运维，可以避免该情况。他举了两个可能发生时间跳跃的例子：

    • 系统管理员手动修改时间
    • 从NTP服务收到一个大的时间更新时间

    对于这两种情况：

    • 手动修改时间这种人为情况，可以完全被避免
    • 使用一个非“跳跃式”ntpd程序调整系统时钟，比如对时间的修改通过多次微小的调整完成

    而后两种情况，即GC pause和网络延迟，如果发生在1-3步，那么在第4步都会被检查出来。问题来了，如果发生在第4步，也就是redis客户端和资源服务器直接发生了延迟，其实这就不是redLock的问题了，而是所有分布式锁都有该问题。
    综上所述，antirez说的有两个重要的点：

  19. antirez同意大的系统时钟跳跃会造成RedLock失效，但是他认为实际系统中，这种情况可以通过基础设施和运维方式避免。
  20. antirez在设计RedLock时，充分考虑了网络延迟和程序停顿所带来的影响，但是redis客户端与资源服务器之间的延迟（算法第3步之后的延迟），antirez承认所有的分布式锁的实现，包括RedLock，都没有很好的解决方案。
    （建议灵活使用）
    优缺点---优点：性能高 。 缺点：失效时间设置多长没有明确标准
    Redission
    增加了watch dog，后台进程，会定期检查锁是否失效。解决上面的问题（失效时间应该设置多久）：每次获得锁，都设置很短的失效时间，然后在每次快到失效时间之前去重新校验锁的状态，然后刷新失效时间。
    （建议灵活使用）
    zookeeper
    zk相关基础知识：一般采用多个节点（单数）构成，采用ZAB一致性协议。数据以目录树的形式，即znode，每个znode可存储数据（一般小于1M），可以在znode上增加子节点。子节点有三种类型：序列化节点-每次该节点下增加一个节点都会给该节点的名称自增；临时节点-一旦创建该节点的客户端失去联系会被自动删除；普通节点。watch机制，client可以监控每个节点的变化（zk的watch机制可以防止阻塞，而是采用通知的方式）。
    zk基本锁：
    原理：利用临时节点与watch机制。每个锁占有一个普通节点：/lock，获取锁时，需要在/lock 下建立一个临时节点，如果创建失败则watch /lock节点。
    缺点也很明显：所有取锁失败的进程都需要watch父节点，很容易发生惊群效应（羊群效应 herd effect），即释放锁时会导致所有等待的进程一起尝试创建节点。
    zk优化锁：
    步骤：
  21. 在/lock 节点下串接一个有序的临时节点 EPHEMERAL_SEQUENTIAL
  22. 判断创建节点的序号是不是最小的，如果是则获取锁成功。如果不是，则要watch序号比本身小的前一个节点
  23. 等待watch事件到来后，继续判断是否是序号最小
  24. 获取锁且执行业务完成后，删除该节点，释放锁
    优点：
    有效解决单点问题、不可重入问题、非阻塞问题以及锁无法释放的问题，实现简单
    缺点：
    性能不高，每次都需要动态操作节点
    那么问题来了，基于zookeeper的分布式锁更安全么？
    zk如何检测客户端是否还在连接中呢，这就需要zk的某台服务器维护着一个session，这个session通过定期的心跳（heartbeat）来维持。如果zk长时间（session的过期时间）收不到心跳，那么通过该session所创建的所有ephemeral类型的znode节点都会被自动删除。
    因此，一旦有客户端发生GC pause导致了session过期，都会导致节点被删除，失去锁。而当pause恢复后，它会认为自己仍然持有锁。所以zk也并非绝对安全。
    consul
    go实现的一个轻量级服务发现、KV存储的工具。
    主要使用acquire和release操作，类似Check-And-Set。
  25. acquire只有在key不存在时，才会返回true，并设置value的值，同时操作的session会持有相同的key。如果key存在或保存不成功，则会返回false；
  26. release会使用指定的session来释放某个key，如果指定的session无效，会返回false。
    Chubby
    chubby是Google设计的提供粗粒度锁服务的文件系统，基于松耦合的分布式系统解决一致性问题。简单来说，chubby中的“锁”就是文件，加锁就是创建文件。

最后，
分布式锁，如果追求效率（efficiency），那么可以选择任何一种自己喜欢的形式做实现，当然，要明确的知道它会在哪些安全性上存在不足，以及会带来什么样的后果；如果是为了正确性（correctness），那么就请慎之又慎。

2022 - 2025 康叔的AI全栈工坊. All Rights Reserved.
Theme Jasmine by Kent Liao