Implementierung entfernen auf einer ConcurrentMultimap ohne Rennen

Question

Ich habe das Problem des Schreibens einer gleichzeitigen Multimap untersucht, und ich habe eine Implementierung durch die Google Guava AbstractSetMultimap und eine MapMaker Computing-Karte, die bei Bedarf erstellt die Werte-Sammlungen als eine Reihe Ansicht über eine ConcurrentHashMap. Mit ein wenig Sorgfalt über die View-Sammlungen und verschiedene Wrapper denke ich, dass das ziemlich nah ist.

Das große Problem, das bereits discussed von others war die have dies versuchten, den Anschein, dass die Entfernung die Werte-Sammlungen aus der zugrunde liegenden Karte sein, wenn sie leer werden, ohne Rennbedingungen einzuführen.

Ein paar Optionen scheinen zu existieren.

• die leeren Sammlungen dort lassen. Dies wird einige CHMs verlieren, aber ich glaube, dass es zumindest korrekt ist.
• versuchen Sie optimistisch, die Sammlung zu entfernen, wenn sie leer ist, und kompensieren Sie, wenn etwas anderes darin erscheint. Dies ist voller Rassen und scheint unmöglich zu beheben.
• synchronisieren Sie alles auf der Werte-Sammlung, die zumindest diese Entfernung erlauben würde, aber auf Kosten von Nebenläufigkeit nach der anfänglichen Suche nach Schlüssel.
• für eine kleinere Strafe (vielleicht abhängig von Nutzungsmuster?), Vielleicht synchronisieren auf Werte-Sammlung erstellen und entfernen, müssen überprüfen, ob das alles abdeckt.

Fragen:

• jemand eine bessere Umsetzung als dies weiß es? Können wir besser Teile von MapMaker zusammensetzen, oder braucht es eine spezielle ConcurrentHashMultimap, die von Grund auf neu geschrieben wurde?
• Wenn es schwierig ist, viel zu verbessern, ist dieses Leck in der Praxis wahrscheinlich ein großes Problem? Bemerkenswerte Auflistungen wie java.util.HashMap, juc.ConcurrentHashMap und ArrayDeque ändern die Größe des Sicherungsspeichers nicht nach unten, und ArrayList führt dies nicht automatisch aus. Solange wir die Objekte ausräumen, frage ich mich, ob das zu wichtig ist.

Dank

---

Edit: siehe auch the discussion here auf der Guave-Mailingliste.

---

Edit 2: Ich habe dies seit geschrieben. Eine Implementierung finden Sie unter this Google code area. Ich würde jedes Feedback von jedem, der es versucht, sehr begrüßen, eher dort als hier.

Answer 1

Als Follow-up, hier sind einige Details, die ich aus den früheren Diskussionen, die Sie verlinkt, über meine gleichzeitige Multimap-Implementierung weggelassen.

Diese Implementierung folgte Ihrem ersten Vorschlag: Lassen Sie leere Sammlungen in der Backing Map. Das folgende Live-View-Verhalten erschwert Ihre anderen Vorschläge.

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

Für eine reale Anwendung, wie eine Sammlung Bibliotheksklasse im Gegensatz etwas weniger als ein völlig gleichzeitiger multimap würde wahrscheinlich ausreichen. Sie könnten Ihre eigene Klasse definieren, die eine Teilmenge der Multimap-Schnittstelle oder eine begrenzte Auswahl an Parallelitätsgarantien implementiert. Oder Ihre Anwendungslogik könnte Konflikte einer synchronisierten Multimap minimieren, um Leistungsprobleme zu vermeiden.

Answer 2

Wenn Sie die leere Sammlung wirklich nicht verlieren möchten, können Sie versuchen, sie durch einen pro-key Platzhalter Future zu ersetzen. Auf diese Weise sollte das gleichzeitige Hinzufügen/Entfernen oder Hinzufügen/Hinzufügen beim erneuten Erweitern einen konsistenten Zustand erreichen können.

Answer 3

Die Verwendung unveränderlicher Sammlungen als Werte ist der beste Weg zur Lösung/Vereinfachung grundlegender Nebenläufigkeitsprobleme, die Sie dann mit der atomaren Ersetzungsmethode entfernen können. Leider gibt es keine unveränderlichen Sammlungen mit schnellen Kopier-/Update-Profilen im allgemeinen Einsatz, so dass man in der Regel ziemlich teuer alles kopieren muss.

Answer 4

Ich habe die gleiche Frage früher gestellt und endete damit, 4 verschiedene Implementierungen zu implementieren.

Die Frage: High-performance Concurrent MultiMap Java/Scala

Die impl (Ich nenne es Index) http://github.com/jboner/akka/blob/master/akka-actor/src/main/scala/actor/ActorRegistry.scala#L314