高效的并发树

Question

我正在寻找一种高效的方法来实现并发树形结构。如果有帮助的话，可以假设我需要对该结构进行更多的读取操作而非更改操作。

该树应支持以下操作：

• 添加和删除节点
• 每次插入新节点时都要排序分支
• 遍历所有节点（不会出现 ConcurrentModificationException）
• 按路径查找元素

- Aaron Digulla

Answer 1

请查看：Google code上的Concurrent-Trees，以了解一种在不锁定的情况下修改树形结构的方式。

该项目提供了Java的并发基数树和后缀树。它们支持并发读写，而读取是无锁状态的。它通过原子方式向树应用补丁来实现。虽然这些类型的树可能不完全符合您的要求，但在TreeDesign中描述的使用“打补丁”方法对于任何类型的类似树形结构都很有用。

这些树适用于高并发读多写少的情况，其中（例如）后台线程可能会插入或删除树中的条目，而许多前台线程将继续自由遍历树，不受修改的影响。

- npgall

---

这很有趣，但在我的使用情况下没有用。我的树是真正的树（父子结构），而不是键值映射。 - Aaron Digulla

我建议避免使用“无用”的词语。这个答案是出于自愿帮助你的贡献。如果你正在寻找只读并发树，无锁算法可能是一个不错的选择。基数树可能不完全符合你的要求，但如我所提到的，我链接的原子修补方法可以应用于任何类型的树以进行无锁读取，即使你计划编写自己的自定义树。顺便说一句，基数树显然是具有父子结构的树。 - npgall

新的措辞看起来不错。我还删除了最后一段关于文档的内容，因为我已经完成了对网站剩余文档的添加。 - npgall

这是我们最终采用的解决方案。主要缺点是：由于每次需要复制树，所以内存消耗和更改操作相当昂贵。但是优点远远超过它们：代码结构简单，没有死锁，没有读取锁，非常容易将多个树更改合并为一个操作（因此我只需要一份副本），实现不会泄漏，保证线程安全，没有边角情况。 - Aaron Digulla

根据树的类型，可能不需要为每个修改复制整个（子）树。一些树（例如基数树）具有引用局部性（LOR），因此分支中间的修改可能仅需要为补丁分配少量节点，并且要替换的节点的后代通常可以直接附加到未修改的补丁上。在没有LOR的树中，写入肯定会更昂贵。由于客户可以修改您的树，请尝试礼貌地要求他们遵守引用局部性！我很高兴这有所帮助，祝您的项目好运。 - npgall

优化是可能的，但并非必要——这正是我喜欢这种方法的原因。如果发现树太慢，我可以将简单的5行递归复制替换为更复杂的东西——但我不必须这样做 :-) - Aaron Digulla

Answer 2

在Java中，与您可能需要的最接近的结构是ConcurrentSkipListSet（或者可能是ConcurrentSkipListMap）。

---

如果您需要更自定义的方法，可以实现一个自定义树形结构，如果您有一个分层的读写锁。以下是类似问题的答案，介绍如何实现可重入的读写锁：https://dev59.com/WlfUa4cB1Zd3GeqPJ6a2#6154873

- Kru

---

CSLM并不是非常接近。它是一个排序映射（sorted map），与树结构几乎没有关系。因此，它只与TreeMap共享一个通用属性，那就是它是一个排序映射 - 这在这里并不相关。 - Marko Topolnik

这就是为什么答案有第二部分的原因，因为我不知道Java中是否包含支持所有这些操作的树结构。此外，对于一些类似的情况，CSLM可能已经足够了。 - Kru

Kru仍然是正确的：它是官方运行时中最接近我的问题的唯一数据结构。我可以使用嵌套的ConcurrentSkipListMaps +锁构建树。 - Aaron Digulla

有必要使用树结构吗？嗯，一种并发（无锁）的treemap是一个研究课题。是的，我们有COW B-Tree，但它们很疯狂。 - J-16 SDiZ

@AaronDigulla 一个ConcurrentSkipListSet不是更好的工具来实现单个节点的子容器吗？ - Marko Topolnik

@AaronDigulla 我又想了一下——CSLS 实际上会涵盖所有必要的锁定，因此您的代码不需要任何显式的锁定机制吗？所有插入和删除都归结为在子列表中插入/删除。 - Marko Topolnik

Answer 3

您可以在您的结构中使用读写锁，以便多个线程可以并发读取，但一次只能有一个线程进行修改。 如果某个线程尝试修改结构，则必须等到所有读者完成读取后才能执行修改操作。 如果一个线程想要读取，只有在没有写入器正在工作或它已经按计划做了一些修改时才能读取。 也许查看这个链接可以帮助：http://docs.oracle.com/javase/1.5.0/docs/api/java/util/concurrent/locks/ReentrantReadWriteLock.html

- giocarmine

Answer 4

读写锁的基本概念

对于所有写入方法，请使用以下习语：

someWriteMethod(){
  writeLock.lock();
  // logic
  writeLock.unlock();
}

对于所有的读取方法，请使用相似的代码：

someReadMethod(){
  readLock.lock();
  // logic
  readLock.unlock();
}

• 如果至少有一个方法执行写操作，则没有人可以获得读或写锁。
• 如果至少有一个方法执行读操作，则任意数量的线程都可以获得读锁。
• 如果至少有一个方法执行读操作，则没有人可以获得写锁。

请注意，如果您的代码（替换上面的逻辑注释）可能会抛出异常，请确保在finally部分中退出方法之前释放锁定。

- mishadoff

---

读写锁有一个缺点：您无法将读锁升级为写锁，因此您需要事先知道您的操作是否会修改树。这将需要两个迭代器，其中一个可能会锁定太多。 - Aaron Digulla

我假设使用树形结构时，您事先知道哪些操作会修改您的树，对吧？ - mishadoff

当我向树请求一个迭代器时，创建迭代器的方法无法知道我是否会调用remove()。 - Aaron Digulla

你的树很大吗？考虑返回副本如何？ - mishadoff

我自己也在想。我的树通常不是很大，但它们没有人为限制，因此客户可以按照他们的意愿将它们做得尽可能大 :-/ - Aaron Digulla