根锁、子锁和多个锁

Question

我所拥有的简化结构是：

• 一些单根
• 每个根都有许多(例如，10秒)的儿童。

用户可以更新根信息，不应该允许对子用户进行任何其他操作(因为根更改可能会影响到所有的根信息)。

此外，用户也可以对子用户进行操作(当然，如果根没有使用)。例如，用户可以在同一时间更改2个子级，这是允许的，因为每个子节点都是独立的。

为了确保没有腐败，我需要这个结构中的锁：

• 当孩子们在使用时，把孩子们锁起来。这将不允许在同一时间对相同的孩子执行两个操作。
• 当根用户正在使用时，锁定root和所有子用户。这将禁止在根更新时对任何子节点进行操作。

这里困扰我的是需要锁定所有的子级--在一个分布式系统中，这意味着发送那么多请求到分布式锁定。

有什么更好的解决办法吗？

Answer 1

你错过了两件事。首先，多个线程同时从节点读取是安全的，只要没有人向它写入。第二，子节点可以看作是较小树的根，因此，除了叶节点之外，同样的算法/解决方案也可以应用于所有节点。第一个是最重要的。以下是你如何做到的：

在树中的所有节点上使用读/写互斥。允许任意数量的进程并发读取，或者允许单个进程在任何时候写入节点。

阅读：

1. 读锁节点和所有父节点一直到根。
2. 朗读。
3. 释放所有的读锁。

编写：

1. 写入-锁定要修改的节点的最小上限。如果您正在修改一个节点(可能是它的任何一个子节点)，那么写锁该节点。
2. 你的修改
3. 释放写锁

这意味着两个兄弟姐妹可以并发修改，任意数量的读取都可以并发执行。然而，阅读的成本是你需要抓取O(log100(tree_height))读锁，对于每层都有大约100个子树的树。这不太可能是一个真正的问题，除非您的树很大，有非常多的读和写到同一个叶节点。

这假定任何子级都不能修改其父级。