implementando eliminar en un ConcurrentMultimap sin carreras

Question

He estado buscando el problema de escribir un Multimap concurrente, y tengo una implementación respaldada por el Google Guava AbstractSetMultimap y un mapa informático MapMaker que crea a demanda los conjuntos de valores como un conjunto ver sobre un ConcurrentHashMap. Con un poco de cuidado sobre las colecciones de vistas y varias envolturas, creo que esto se acerca bastante.

El gran problema, que ya ha sido discussed por others que have intentaron esto, parece ser que la eliminación de los valores-colecciones desde el mapa subyacente cuando se convierten en vacío, sin introducir condiciones de carrera.

Parece que existen un par de opciones.

• Deje las colecciones vacías allí. Esto filtrará algunos CHM, pero creo que al menos es correcto.
• intente de manera optimista eliminar la colección cuando esté vacía y compensar si aparece algo más en ella. Esto está lleno de razas y parece intrínsecamente imposible de arreglar.
• sincronizar todo en la colección de valores, que al menos permitiría esta eliminación, pero a costa de cualquier concurrencia después de la búsqueda inicial por clave.
• para una multa menor (tal vez, dependiendo de los patrones de uso?), Tal vez sincronizar en la creación y eliminación de colecciones de valores, es necesario verificar si eso cubre todo.

Preguntas:

• ¿Alguien sabe de cualquier aplicación mejor que esto? ¿Podemos componer mejor fragmentos de MapMaker, o necesita un ConcurrentHashMultimap especializado escrito desde cero?
• Si es difícil mejorar mucho en esto, ¿es probable que esta fuga sea un gran problema en la práctica? Las colecciones notables como java.util.HashMap, juc.ConcurrentHashMap y ArrayDeque no cambian el tamaño del almacén de respaldo hacia abajo, y ArrayList no lo hace automáticamente. Mientras limpiemos los objetos, me pregunto si esto importará demasiado.

Gracias

---

Editar: véase también the discussion here en la lista de correo de guayaba.

---

Edición 2: desde entonces he escrito esto. Por favor, consulte this Google code area para una implementación. Agradecería cualquier comentario de cualquier persona que lo intente, allí en lugar de aquí.

Answer 1

Como seguimiento, aquí hay algunos detalles que omité de las discusiones anteriores, con las que se vinculó, sobre mi implementación concurrente de multimap.

Esa implementación siguió a su primera sugerencia: dejar colecciones vacías en el mapa de respaldo. El siguiente comportamiento de visualización en vivo complica tus otras sugerencias.

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

Para una aplicación en el mundo real, en contraposición a una clase de biblioteca de colección, algo menos que una multimap totalmente concurrente probablemente sería suficiente. Podría definir su propia clase que implemente un subconjunto de la interfaz Multimap o una selección limitada de garantías de concurrencia. O bien, su lógica de aplicación podría minimizar la contención de una multimapa sincronizada para evitar problemas de rendimiento.

Answer 2

Si realmente no desea filtrar la colección vacía, podría intentar reemplazarla atómicamente con un marcador de posición por clave futuro. De esta forma, agregar/eliminar o agregar/agregar al mismo tiempo debería ser capaz de alcanzar un estado consistente al expandir nuevamente.

Answer 3

El uso de colecciones inmutables como valores es la mejor manera de resolver/simplificar los problemas de simultaneidad básicos que luego puede eliminar con el método de reemplazo atómico. Desafortunadamente, no hay colecciones inmutables con perfiles de copia/actualización rápida de uso general, por lo que generalmente es necesario copiar todo lo costoso.

Answer 4

Hice la misma pregunta anteriormente, y terminé implementando 4 implementaciones diferentes.

La pregunta: High-performance Concurrent MultiMap Java/Scala

El impl (lo llamo Índice) http://github.com/jboner/akka/blob/master/akka-actor/src/main/scala/actor/ActorRegistry.scala#L314