6

我一直在研究编写并发Multimap的问题，并且我有一个由Google Guava AbstractSetMultimap 和 MapMaker 计算地图支持的实现，它可以按需创建值集合作为 ConcurrentHashMap 上的集合视图。通过对视图集合和各种包装器的一些关注，我认为这非常接近。

其他尝试过这个的人已经讨论过的大问题似乎是当它们为空时从底层映射中删除值集合，而不引入竞争条件。

似乎存在几个选项。

  • 将空集合留在那里。这会泄漏一些 CHM，但我相信它至少是正确的。
  • 尝试乐观地在空时删除集合，并在其中出现任何其他内容时进行补偿。这充满了种族，似乎本质上是不可能解决的。
  • 同步 values-collection 上的所有内容，这至少允许删除，但代价是在键初始查找后的任何并发性。
  • 对于较小的惩罚（也许，取决于使用模式？），也许在值集合创建和删除时同步，需要检查是否涵盖了所有内容。

问题：

  • 有谁知道比这更好的实现？我们可以更好地组合 MapMaker 的部分，还是需要从头开始编写专门的 ConcurrentHashMultimap？
  • 如果很难在这方面做出很大改进，那么这种泄漏在实践中是否可能是一个很大的问题？java.util.HashMap、juc.ConcurrentHashMap 和 ArrayDeque 等著名的集合不会向下调整后备存储的大小，而 ArrayList 也不会自动这样做。只要我们清除对象，我想这会不会太重要。

谢谢

编辑：另请参阅番石榴邮件列表上的讨论。

编辑2：我已经写了这个。请参阅此 Google 代码区以了解实现。我将非常感谢任何尝试它的人的反馈，那里而不是这里。

4

4 回答 4

1

我之前问过同样的问题，最终实现了 4 种不同的实现。

问题： 高性能并发 MultiMap Java/Scala

impl（我称之为索引） http://github.com/jboner/akka/blob/master/akka-actor/src/main/scala/actor/ActorRegistry.scala#L314

于 2010-10-03T21:00:26.070 回答
0

如果您真的不想泄漏空集合，您可以尝试用每个键的占位符 Future 原子地替换它。这样并发添加/删除或添加/添加应该能够在再次扩展时达到一致状态。

于 2010-09-28T14:02:18.880 回答
0

使用不可变集合作为值是解决/简化基本并发问题的最佳方法，因为您可以使用原子替换方法删除。不幸的是，一般使用中没有具有快速复制/更新配置文件的不可变集合，因此您通常需要进行非常昂贵的复制所有内容。

于 2010-09-29T03:05:23.983 回答
0

作为后续，这里有一些我在你之前链接到的讨论中省略的关于我的并发多图实现的细节。

该实现遵循您的第一个建议：在支持映射中保留空集合。以下实时查看行为会使您的其他建议复杂化。

Multimap<String, Integer> multimap = HashMultimap.create();
Set<Integer> set = multimap.get("foo");
multimap.put("foo", 1);
int count = set.size();   // equals 1

对于真实世界的应用程序，与集合库类相反，少于完全并发的 multimap 的东西可能就足够了。您可以定义自己的类来实现 Multimap 接口的子集或有限的并发保证选择。或者，您的应用程序逻辑可以最小化同步多图的争用以避免性能问题。

于 2010-10-01T12:49:34.473 回答