Distributed Locking

25th May 2021 at 8:47pm
Distributed Computing: Problem

并发控制的过程中经常需要上分布式锁。分布式锁相较于单机锁,可以在跨多台机器、多个进程的场景下上锁。

在分布式计算中,并发控制有两种方法,分别是 乐观的和悲观的。悲观的并发控制往往带有上锁过程。但假如上锁的一方没有释放锁(比如进程挂掉了,或者程序有 bug),会造成死锁。因此需要有 自动释放锁 的机制。但假如上锁方在它的临界区操作未完成时,锁就已经被释放了,这时候就会造成混乱。此时需要有 fencing token 的机制。Fencing token 是一个单调递增的 token,在下文中会讲到。。

Redlock

Redlock 是 Redis 作者提出的一种分布式锁实现。我对该博客文章做了 annotation:

电脑上如果 PDF 不展示或者展示不正常,使用 Chrome 并安装 PDF Viewer 插件。其他情况请下载文件查看:redlock.pdf

总的来说,它的机制是在单实例的 SET KEY + TTL + 随机 value 的基础上,扩充到多实例。要求给定 N 个互不关联的 Redis 节点,当 client 对其中的大多数(N/2+1)个节点上锁成功时,才算获取到了这个锁。文章里面给出了具体的实现细节和安全上的论述。

How to do distributed locking

这是一篇由 Designing Data-intensive Applications 作者 Martin Kleppmann 所写的 文章。我对它做了标记:

电脑上如果 PDF 不展示或者展示不正常,使用 Chrome 并安装 PDF Viewer 插件。其他情况请下载文件查看:how-to-do-distributed-locking.pdf

里面 Martin 批评了 Redlock 的实现,提出了它自己的看法,我觉得讲得很在理。文末推荐的 ZooKeeper 书curator recipes 感觉非常值得一看。

这篇文章中提到 fence token 的机制。但 fence token 的具体实现我还没深入。

Martin 在文中提到的 asynchronous model with unreliable failure detectors,表示这类算法不应该持有 timing assumption:

  • 你的进程可能在任意时刻被中断任意长的时间(比如 pause-the-world GC,或 CPU 调度问题等)
  • 网络包的延迟可以非常大(比如 GitHub 就曾经有过事故,包延迟了 90s 才到达)
  • 时钟(gettimeofday 这类)可能是错的(比如管理员手动调整了时间,或者 NTP 同步等,可以造成本地时间来回跳)

这是很多分布式算法实现正确性的前提。如有兴趣,看 Martin 推荐的阅读材料再深入。

Is Redlock safe?

Is Redlock safe? 是 Redis 作者对 Martin 的文章的回复。我没有仔细看,因为 Salvatour 的英语真的是很难理解。大的论点大概是:

  • 如果你的存储服务支持 fence token,它就是 linearizable 的了,也就没有引入一个额外的分布式锁的必要
  • Redlock 也可以通过 compare-and-set 来实现类似 fence token 的能力
  • Client 长时间 pause 引起的问题,在设计中已经避免了

参考材料

Everything I know about distributed locks 讲了一些概念:

  • 乐观 / 悲观的并发控制
  • 锁的自动释放、fencing token 机制(比较简略)
  • Lock manager(比如 Redis)的部署方式比较:单 leader 带 followers,还是多 leader

Distributed Locks with Redis:Redis 官方博客写的实现。