在分布式系统中，通常会采用分布式锁来解决共享资源的互斥访问问题，而分布式读写锁则可以进一步提高读请求的并发。阿里云存储团队自研的分布式锁服务——女娲，凭借在性能、可扩展性和可运维性上的技术优势，使得阿里云存储在稳定、可靠、高性能等方面不断突破，进而为客户业务的永续运营提供了有力保障。在业界中，类似女娲的软件包括有 Apache ZooKeeper，Kubernetes Etcd，以及 Google Chubby，“他山之石，可以攻玉”，女娲的技术演进也在持续参考并吸收业界的最佳实践。本文，我们将介绍女娲对社区 ZooKeeper 在分布式读写锁实践细节上的思考，希望帮助大家理解分布式读写锁背后的原理。

1. 读写锁问题由来

Apache ZooKeeper （下文简称 ZK）是开源社区一款比较知名的分布式协同软件，通过提供基础原语语义，开发者可以较为容易地开发出分布式锁、服务发现、元数据存储等关键的分布式管控功能。作为 Hadoop 生态圈早期成员，ZK 对业界的影响不可谓不深远。

除了常见的常规文件（Normal File）与临时文件（Ephemeral File），ZK 还提供了一种特别的顺序文件（Sequential File），业界知名的开源库 - Apache Curaor在 ZK 的顺序文件语义之上封装出读写锁、公平锁、分布式队列、分布式 Barrier 等诸多优雅功能。那么 ZK 的顺序文件是怎样实现的呢？ZK 顺序文件的创建依赖于其父目录节点的 cversion 属性。每个目录节点都会记录其子节点的创建和删除次数，此即为 cversion，当 ZK 收到创建顺序文件请求的时候，其会使用该文件父目录的 cversion 作为文件名的后缀，那么就可以保证先后创建的顺序文件后缀值是单调增加的。所谓无心插柳柳成荫，当初为订阅目录下节点增删事件所设计的属性，今后居然演变成了 ZK 场景下某种逻辑时间戳 ，孵化出了类似读写锁这样重要的功能特性。

如下图所示，譬如我们发送路径为“/vm/vsp-xxxxx/_READ_”的顺序文件的创建请求，后端实际创建的文件节点名为“/vm/vsp-xxxxx/_READ_0000000001”，之后再创建名为“/vm/vsp-xxxxx/_WRIT_”的顺序文件，后端实际创建的文件节点名为“/vm/vsp-xxxxx/_WRIT_0000000002”。如果我们把前者认为是读锁，那么就订阅“/vm/vsp-xxxxx/”目录下所有的节点，并且把子节点按照最后 10 位的后缀排序。如果发现不存在序号小于自身的写锁，那么自己就算是持锁成功了；如果我们把后者认为是写锁，那么就订阅“/vm/vsp-xxxxx/”目录下所有的节点，并且把子节点按照最后 10 位的后缀排序。如果发现不存在序号小于自身的读锁，也不存在序号小于自身的写锁，那么自己就算是持锁成功了。这样就实现了简单且优雅的分布式读写锁。类比单机系统中使用的读写锁，分布式读写锁对于业务运行性能上提升的意义，同样是不言而喻的。

行文至此，大家应该也意识到，基于 ZK 实现的分布式读写锁，关键之处在于顺序文件（Sequential File）的后缀序号顺序性必须得到保障，即使在 failover 等场景下该序号顺序性也依旧严格维持。想象一下，ZK 系统当前认为“/vm/vsp-xxxxx”目录节点对应的 cversion 值为 5，然后 failover 之后，新当选的 Leader 认为 cversion 值为 4，那就糟糕了，可能就有新旧两个客户端自认为自己创建的顺序文件的序号都是 5，那么基于此特性实现的选主、抢锁等功能属性就会陷入「双主」、「一锁多占」等极其危险的境地，分布式存储的应用场景下，甚至会导致数据被写坏。

这个也正是本文要探讨的重点，ZK 顺序节点的后缀序号的顺序性是如何得到保障的，特别是在 failover 等场景下是如何实现的？“谁能书阁下，白首太玄经”，通过对这个精巧案例的分析，也希望大家能够体会到女娲在分布式协调领域可谓“补天”般的苦心经营。



2. Failover 的隐患

2.1 幂等的陷阱

ZK 是一个复制状态机模型，如下图所示，不同于存储 I/O 依赖链路上的 LSM-Tree 模型，ZK 的复制状态机是完全的内存模型，这样提供了最佳的访问性能（当然，这个也限制了 ZK 的存储容量，不过其定位即为状态管理，容量很难成为其瓶颈）。此外，复制状态机系统在使用共识协议保证事务日志一致性的基础上，工程实现时通常引入快照机制对事务日志进行必要的垃圾回收，以此加速 failover 恢复速度。对于 ZK 而言，为了不影响前台业务访问，其打快照过程必然得是异步的，即递归地遍历内存中 DataTree 的数据结构并持久化到磁盘上的快照文件。在打快照过程中，ZK 继续处理事务请求并更新到内存的 DataTree。换言之，实际持久化到磁盘上的快照文件，记录的是一个“混合”的系统状态，其并不真实存在于任何一个历史时刻。

再以下图为例，在 ZK 打快照过程中，实际上系统也在处理 op1、op2、op3 事务日志，这个带来了一个问题，当我们快照持久化了某个父目录节点（包括其 cversion 值），其下面的子节点在后续的持久化时刻，可能已经处理了新的 CREATE 或者 DELETE 等事务请求，导致快照中该父目录下实际孩子节点状态并非其记录父目录 cversion 所对应时刻的状态。相应地，在回放事务日志时候，状态机会先加载最新的快照文件到内存中作为初始版本的 datatree，而后根据快照中维护的开始打快照时刻对应的事务日志序号，往后一条一条地回放事务日志，对应图中即为从 op1 开始，逐条日志回放。所以，即使持久化的快照中可能已经包含了执行完 op1、op2、op3 之后的状态，在回放的时候仍然会重新再执行一遍这些事务日志。这是大部分异步打快照的系统普遍面临的问题，对于 ZK 来说，需要在回放事务日志重建内存状态过程中合理应对。

因为 ZK 是个幂等的系统设计，因此 failover 场景下在回放事务日志时候，即使存在部分重合的日志应用（APPLY）至状态机，这里是没有数据正确性风险的。但是对于 failover 场景下重新计算出最新的 cversion 值则存在大挑战。考虑如下图的这种情况，快照在 index:2 执行完才开始序列化父目录，此时记录的父目录 cversion 值为 2，后继时刻 3 开始持久化子节点，此时快照记录的子节点只有“/root/B”。

那么这个例子下 failover 恢复的步骤是怎么样的呢？请看下表，最终恢复出来的目录 cversion 值正确，并且孩子节点信息也是正确的。实际上，按照这个步骤最终恢复回来的 cversion 不会小于 failover 之前的 cversion，因为无论如何 cversion 总是会在快照的起始 index 之后才被写入的快照文件，而后继回放事务日志时，每次创建和删除也都使 cversion 递增，所以最终的 cversion 值一定大于等于 failover 之前内存所维护的 cversion 值。

2.2 顺序不顺序

在 ZK 早期的 及其之前的版本，由于回放事务日志的逻辑没有与正常处理事务日志的逻辑分离开，所以遇到删除节点 A 而 A 不存在的这种场景（即图中标红的步骤），会按照事务执行失败进行处理，不再更新 cversion，由此会导致 cversion 值相比 failover 之前会有回退。

这个问题当然不难修复。这个算是社区里面第一次意识到了这个问题，并正式揭开了“ failover 场景下目录 cversion 值一致性的保卫战”。下图即为当初社区针对这个问题的讨论。

3. 社区的一次出手

在 ZK 开源版本 之前的版本，都是使用的上面表 1 中的修复方案。即将「正常处理事务请求」 和 「failover 后回放事务请求」这两种场景区分开，回放过程处理删除事务请求遇到上面所说的 NoNodeException，同样更新父目录的 cversion 即可。

可以看到另开一路实现了回放事务日志的逻辑，「已存在的节点再次被创建」，以及「不存在的节点再次被删除」，这两种情形都可以触发目录 cversion 的更新，使得 cversion 一定比 failover 之前大。总算可以松一口气，不担心顺序文件序号回退触犯「双主」或者「双锁」的天条了，但这种修复方案可能会令读者很自然地生起疑问，这样做单调性是可以保证了，但是幂等性呢？failover 前执行时更新的 cversion 是不是在回放过程中会被再更新一次？这样不优美的修复会遗留潜在风险吗？

4. 社区的二次出手

社区的开发者们当然也有这些顾虑，既然处理事务日志的同时更新、维护 cversion 的过程不是幂等的，这就可能会导致 ZK 后端不同节点上，关于同一个目录文件的 cversion 值可能不一致，所以终极版本的修复需要将目录 cversion 值直接跟着事务日志一起持久化，即应该在创建和删除的事务日志中记录父目录的 cversion 值。

比如下图这种情况，由于打快照是异步的过程，不同节点（这里的节点指的是 ZK 服务器）上快照的状态并不相同。有相同起始 index 的「可能状态 1 」 和「可能状态 2 」的快照 ，都回放了全部事务日志之后，由于「可能状态 2」的起始 cversion 更大，所以最终计算出的 cversion 也更大。节点间对同一个目录 cversion 的值判断不一致，不发生重新选举的时候还好，总归 Quorum Leader 来分配顺序节点的序号能保证单调，一旦切主就会面临切到一个 cversion 更小的 ZK 节点的困扰，归根结底各个节点依赖自己打异步快照不可靠，快照无法在节点间达成一致。

因此自然的解决方法有两种，一种是想办法使得 snapshot 在节点间标准一致；另一种是改为依赖本身各个节点间就一致的事务日志，靠一致性协议来保证。调整打 snapshot 方式的改动会比较大，核心点在于 snapshot 本身能与某一个时刻的事务日志 index 保持严格的一对一映射，但这样势必需要引入像是 LSM-Tree 模型的本地存储引擎，替换掉内存中的 datatree 才可以做到，不然必须停服等待内存 dump 到磁盘。

所以社区最终采用了更轻量的改动，按照使用事务日志的思路进行的修复，在具体实现上，ZK 之父 Flavio 提了一个建议，即不需要在创建和删除的事务日志中都维护 cversion 字段，只在创建中维护即可，因为 cversion 为目录下所有创建删除操作调用的次数，用创建事务日志记录的 parentCVersion 减去当前目录下子节点数便可以间接计算出删除操作的次数，这样可以进一步减少改动量。

只在 CreateTxn 中增加了 parentCVersion 的字段，回放事务日志过程遇到 CREATE 事务便计算，作为最终重建内存 DataTree 的 cversion 来确保涵盖所有删除操作。

5. 纸上得来终觉浅

自 2009 年飞天建立之初，女娲便在分布式协调领域不断躬行摸索，相较于基于异步复制的分布式系统（如 mysql，tair，redis），基于 Paxos/Raft/ZAB 等共识协议的分布式协调系统可以更严格地保证数据安全，而在上述一致性系统的基础之上结合 Lease 机制便可以提供安全的粗粒度锁（这种提法，首见于 Google Chubby 的经典论文），女娲提供的分布式锁的机理也不外如是。

对于女娲这类最基础的服务而言，由于服务着大量的业务，支持着丰富的场景，最是需要切磋琢磨的功夫，在寻常处见功力，细微处见真章。比如支持分布式读写锁功能的过程中，针对 cversion 这样很小的一个细节，如果没有从社区踩坑记录中汲取经验，没有完善的测试进行检查，那就会在线上惹出大祸。

来源  |  阿里云开发者公众号
作者  |  僧泉、云锋