在没有竞争的情况下在 ConcurrentMultimap 上实现删除

发布于 2024-09-25 09:22:24 字数 1669 浏览 5 评论 0原文

我一直在研究编写并发 Multimap，并且我有一个由 Google Guava< /a> AbstractSetMultimap 和 MapMaker 计算映射，根据需要创建值集合作为 ConcurrentHashMap 上的集合视图。通过对视图集合和各种包装器的一些关注，我认为这已经非常接近了。

这个大问题已经讨论过作者：其他已经尝试过这个，似乎是当值集合变空时从底层映射中删除值集合，而不需要引入竞争条件。

似乎存在几个选项。

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

问题：

有谁知道比这更好的实现吗？我们可以更好地组合 MapMaker 的位，还是需要从头开始编写专门的 ConcurrentHashMultimap？
如果在这方面很难做出很大的改进，那么这种泄漏在实践中可能会成为一个大问题吗？值得注意的集合（例如 java.util.HashMap、juc.ConcurrentHashMap 和 ArrayDeque）不会向下调整后备存储的大小，ArrayList 也不会自动这样做。只要我们把这些东西清理掉，我想这会不会太重要了。

谢谢

编辑：另请参阅此处的讨论< /a> 在番石榴邮件列表上。

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

下壹個目標 2024-10-02 09:22:24

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

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

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

回复收藏 0 原文

嗼ふ静 2024-10-02 09:22:24

作为后续内容，以下是我在之前的讨论中省略的一些细节（您链接到了有关我的并发多重映射实现的内容）。

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

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

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

As a follow-up, here are some details I omitted from the earlier discussions, which you linked to, about my concurrent multimap implementation.

That implementation followed your first suggestion: leaving empty collections in the backing map. The following live-view behavior complicates your other suggestions.

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

For a real-world application, as opposed to a collection library class, something less than a fully concurrent multimap would probably suffice. You could define your own class that implements a subset of the Multimap interface or a limited selection of concurrency guarantees. Or, your application logic could minimize contention of a synchronized multimap to avoid performance problems.

回复收藏 0 原文