6

私は並行マルチマップを作成する問題を検討してきましたが、 Google Guava AbstractSetMultimapと、ConcurrentHashMap上のセットビューとして値コレクションをオンデマンドで作成するMapMakerコンピューティングマップに裏打ちされた実装があります。ビューコレクションとさまざまなラッパーに注意を払うと、これはかなり近くなると思います。

これを試した他の人によってすでに議論されている大きな問題は、競合状態を導入せずに、値コレクションが空になったときに、基になるマップから値コレクションを削除することであるように見えます。

いくつかのオプションが存在するようです。

  • 空のコレクションはそのままにしておきます。これにより一部のCHMがリークしますが、少なくとも正しいと思います。
  • 空のときにコレクションを削除し、他に何かが表示されている場合は補正するように楽観的に試してください。これは人種でいっぱいで、修正することは本質的に不可能のようです。
  • 値コレクションのすべてを同期します。これにより、少なくともこの削除が可能になりますが、キーによる最初のルックアップ後の同時実行が犠牲になります。
  • より小さなペナルティ（おそらく、使用パターンに応じて？）の場合、おそらく値コレクションの作成と削除で同期し、それがすべてをカバーしているかどうかを確認する必要があります。

質問：

  • これよりも優れた実装を知っている人はいますか？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

コレクションライブラリクラスとは対照的に、実際のアプリケーションの場合、完全同時マルチマップよりも少ないものでおそらく十分です。マルチマップインターフェイスのサブセットまたは同時実行性保証の限定された選択を実装する独自のクラスを定義できます。または、アプリケーションロジックで、同期されたマルチマップの競合を最小限に抑えて、パフォーマンスの問題を回避することもできます。

于 2010-10-01T12:49:34.473 に答える