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

在分布式计算中，并发控制有两种方法，分别是 乐观的和悲观的。悲观的并发控制往往带有上锁过程。但假如上锁的一方没有释放锁（比如进程挂掉了，或者程序有 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 官方博客写的实现。