c++ - Diseño concurrente de estructura de datos
data-structures concurrency (11)
Estoy tratando de encontrar la mejor estructura de datos para usar en un servidor C ++ de alto rendimiento. La estructura de datos se usará para almacenar de unos pocos a varios millones de objetos, y no se requiere clasificación (aunque se puede proporcionar una clave de clasificación única de forma muy económica).
Los requisitos son que puede admitir insertos eficientes, idealmente O (1), extracción moderadamente eficiente y recorrido eficiente. No necesita admitir una operación de búsqueda (que no sea necesaria para la eliminación).
El giro es que debe ser seguro para subprocesos con respecto a las modificaciones mientras que otros subprocesos enumeran la estructura de datos. Esto significa que un árbol rojo-negro simple no funciona, ya que un hilo no puede insertar un elemento (y realizar las rotaciones de árbol necesarias) sin estropear ningún cursor sostenido por otros hilos.
No es aceptable utilizar un bloqueo de lectura / escritura y diferir las operaciones de escritura hasta que todos los lectores hayan terminado, ya que las operaciones de lectura pueden durar mucho tiempo. No importa si las inserciones que ocurren mientras hay un lector son visibles para ese lector o no.
La huella de memoria también es muy importante, ¡y lo pequeño es obviamente mejor!
¿Qué sugerencias hay?
Respuesta a los comentarios:
Gracias por las respuestas.
No, las inserciones no pueden invalidar los iteradores existentes. Los iteradores pueden ver o no el nuevo inserto, pero deben ver todo lo que habrían visto si el inserto no se hubiera producido.
Se requiere la eliminación, sin embargo, debido a las reglas de nivel más alto, puedo garantizar que nunca se detendrá un iterador en un elemento que está disponible para su eliminación.
El bloqueo por nodo de un cursor tendría un impacto demasiado grande en el rendimiento. Puede haber una cantidad de subprocesos que se leen a la vez, y cualquier tipo de zona activa de memoria que utilizan varios subprocesos en un bloqueo mata el ancho de banda de la memoria (¡como descubrimos de la manera más difícil!). Incluso un simple recuento de lectores con múltiples hilos llamando a InterlockedIncrement no logra escalar limpiamente.
Estoy de acuerdo en que una lista vinculada es probablemente el mejor enfoque. Las eliminaciones son raras, por lo que pagar la penalización de la memoria de los punteros reverso para admitir la eliminación O (1) es costoso y podemos calcularlos por separado a pedido y dado que las eliminaciones tienden a ser operaciones por lotes.
Afortunadamente, la inserción en una lista vinculada no requiere ningún bloqueo para los lectores, siempre que los punteros se actualicen en el nodo insertado antes de que se cambie el puntero de la cabeza.
La idea de bloquear y copiar-desbloquear es interesante. La cantidad de datos involucrados es demasiado grande para que esto funcione como el valor predeterminado para los lectores, pero podría usarse para los escritores cuando colisionan con los lectores. Un bloqueo de lectura / escritura protegería toda la estructura y la escritura clonaría la estructura de datos si colisiona con un lector. Las escrituras son mucho más raras que las lecturas.
Bueno, para estar seguro de los hilos vas a tener que bloquear algo en algún momento. Una cosa clave es asegurarse de que los objetos en su repositorio puedan bloquearse por separado de la estructura del repositorio en sí: es decir, no tienen un _next link ni nada por el estilo dentro de los datos que está almacenando. De esta forma, las operaciones de lectura pueden bloquear el contenido de los objetos sin bloquear la estructura del repositorio.
La inserción eficiente es fácil: la lista vinculada, las matrices no ordenadas, las tablas hash funcionan bien. La eliminación eficiente es más difícil ya que implica encontrar lo eliminado en el repositorio. Howerver, por simple simplicidad y velocidad, una lista vinculada es una buena opción. ¿Se pueden posponer las eliminaciones para las horas no ocupadas y las que acaban de marcarse como "inactivas"? Entonces el costo de encontrar / eliminar no es tan limitante.
Sin embargo, todavía vas a tener problemas con el cruce. Todo lo que puede hacer es bloquear y tomar una instantánea de lo que debe atravesarse, luego verifique cualquier cambio después de ver la instantánea. Difícil problema ...
Creo que la lista vinculada debe responder a sus requisitos. Tenga en cuenta que puede bloquear solo los nodos que se están modificando (es decir, eliminados / añadidos) para que los lectores la mayor parte del tiempo puedan trabajar en total paralelismo con los escritores. Este enfoque requiere un bloqueo por nodo de lista vinculada, sin embargo, no es obligatorio. Puede tener una cantidad limitada de bloqueos y luego varios nodos se asignarán al mismo bloqueo. Es decir, que tiene un conjunto de N bloqueos y nodos numerados 0..M puede usar el bloqueo (NodeId% N) para bloquear este nodo. Esos pueden ser bloqueos de lectura y escritura, y controlando la cantidad de bloqueos puede controlar la cantidad de paralelismo.
Disculpas por la doble respuesta ...
Dado que las escrituras son bastante raras, debería considerar el uso de STM en lugar de bloquear. STM es una forma de bloqueo optimista, lo que significa que tiene un gran sesgo en el rendimiento hacia sistemas libres de colisiones (es decir, menos escrituras). Por el contrario, el bloqueo pesimista (bloqueo-escritura-desbloqueo) está optimizado para sistemas de colisión pesada (también conocido como muchas escrituras). La única pega con STM es que casi exige que utilice estructuras de datos inmutables dentro de las celdas de TVar, de lo contrario, todo el sistema se descompone. Personalmente, no creo que esto sea un problema, ya que una estructura de datos inmutable decente será tan rápida como una mutable (vea mi otra respuesta), pero vale la pena considerarla.
Personalmente, soy bastante aficionado a las estructuras de datos permanentes e inmutables en situaciones altamente concurrentes. No conozco ninguno específicamente para C ++, pero Rich Hickey ha creado algunas estructuras de datos inmutables excelentes (y increíblemente rápidas) en Java para Clojure . Específicamente: vector, hashtable y hashset. No son demasiado difíciles de transportar, por lo que es posible que desee considerar uno de esos.
Para elaborar un poco más, las estructuras de datos permanentes e inmutables realmente resuelven una gran cantidad de problemas asociados con la concurrencia. Debido a que la estructura de datos en sí misma es inmutable, no hay un problema con múltiples hilos que leen / iteran simultáneamente (siempre que sea un constante iterador). "Escribir" también puede ser asincrónico porque no está realmente escribiendo en la estructura existente, sino más bien creando una nueva versión de esa estructura que incluye el nuevo elemento. Esta operación se hace eficiente ( O (1) en todas las estructuras de Hickey) por el hecho de que en realidad no está copiando todo. Cada nueva versión comparte la mayor parte de su estructura con la versión anterior. Esto hace que las cosas sean más eficientes en cuanto a la memoria, así como también mejora dramáticamente el rendimiento sobre la simple técnica de copiar y escribir.
Con las estructuras de datos inmutables, el único momento en el que realmente necesita sincronizarse es escribir en una celda de referencia. Como el acceso a la memoria es atómico, incluso esto generalmente puede estar libre de bloqueos. La única advertencia aquí es que puede perder datos entre hilos (condiciones de carrera). La estructura de datos nunca se corromperá debido a la concurrencia, pero eso no significa que los resultados incoherentes sean imposibles en situaciones en las que dos subprocesos crean una nueva versión de la estructura basada en un solo antiguo e intentan escribir sus resultados (uno de ellos será "ganar" y los cambios del otro se perderán). Para resolver este problema, debe tener un candado para "escribir operaciones" o usar algún tipo de STM . Me gusta el segundo enfoque para la facilidad de uso y el rendimiento en sistemas de baja colisión (las escrituras son idealmente no bloqueantes y las lecturas nunca se bloquean), pero cualquiera de las dos funcionará.
Hiciste una pregunta difícil, una para la cual no hay realmente una buena respuesta. Las estructuras de datos seguras a la concurrencia son difíciles de escribir, especialmente cuando necesitan ser mutables. Es probable que las arquitecturas completamente libres de bloqueos sean imposibles en presencia de estado compartido, por lo que es posible que desee renunciar a ese requisito. Lo mejor que puede hacer es minimizar el bloqueo requerido, de ahí las estructuras de datos inmutables.
Si no necesita un orden de clasificación, no utilice un árbol rojo / negro o cualquier otra cosa que inherentemente ordena.
Su pregunta no está suficientemente especificada suficientemente para interactuar entre lecturas y escrituras. ¿Estaría bien si se implementa una "lectura" mediante un bloqueo + copiar + desbloquear y luego usar la nueva copia?
Si lo desea, puede leer sobre los bloqueos en http://en.wikipedia.org/wiki/Seqlock , y en los procesos de "bloqueo libre" en general, aunque es posible que desee relajar sus requisitos tanto como sea posible: un bloqueo la implementación gratuita de la tabla hash es una gran tarea.
Tienes 3 tipos de tareas:
- iteración (lenta)
- inserción (rápido)
- eliminación (rápido)
Si la coherencia cercana es lo suficientemente buena, realice un seguimiento del número de tareas de iteración activas.
Si las tareas de iteración están activas y se ingresan nuevas tareas de inserción o eliminación, ponga en cola esas tareas para su posterior procesamiento (pero puede devolverlas a la persona que llama de inmediato).
Tan pronto como la última iteración finalice el proceso, el proceso se insertará y eliminará.
Si aparece una solicitud de iteración mientras las inserciones o las eliminaciones están pendientes, póngalas en cola.
Si aparece una solicitud de iteración mientras solo hay iteraciones en ejecución, solo tiene que ir e iterar.
Todavía debe escribir la iteración para que sea lo más rápida posible haciendo una copia de los datos que está iterando y luego procese esos datos en el cliente si el procesamiento de datos real requiere mucho más tiempo que la iteración misma.
Implementaría la colección principal con una tabla hash o stl: el mapa podría ser lo suficientemente rápido. Las solicitudes de inserción / eliminación se pueden poner en cola en una lista.
Las listas enlazadas son definitivamente la respuesta aquí. Inserción y eliminación en O (1), iteración de un nodo a otro en O (1) y estabilidad en todas las operaciones. std::list garantiza todos estos, incluyendo que todos los iteradores son válidos a menos que el elemento se elimine de la lista (esto incluye punteros y referencias a elementos). Para el bloqueo, podría simplemente ajustar la lista en una clase de bloqueo, o podría escribir su propia clase de lista (no podría usar std::list en este caso que admita bloqueo basado en nodo, por ejemplo, puede bloquearlo ciertas áreas de la lista para su uso mientras que otras secuencias realizan operaciones en diferentes áreas. La que utilice dependerá en gran medida del tipo de acceso concurrente que espere; si múltiples operaciones en diferentes partes de la lista serán realmente comunes, escriba la suya propia, pero recuerde que va a poner un objeto mutex en cada nodo, que no es eficiente en el uso del espacio.
La única forma en que creo que esto es posible es a través de algo similar al protocolo de concurrencia multiversión utilizado en bases de datos tales como oracle / postgresql, etc. Esto garantiza que los lectores no bloqueen a los lectores, los escritores no bloqueen a los lectores, pero los escritores bloquean solo aquellos escritores que actualizar la misma información. Esta propiedad de los escritores que bloquean el / los escritor / es que actualizan la misma información es importante en el mundo de la programación concurrente; de lo contrario, las incoherencias entre datos / sistema son posibles. Para cada operación de escritura en la estructura de datos, toma una instantánea de la estructura de datos o al menos la parte de los nodos de estructura de datos afectados por la operación de escritura en una ubicación diferente en la memoria antes de escribir. Entonces, cuando la escritura está en progreso, un hilo lector solicita leer una parte de los datos de la parte del escritor, siempre se refiere a la última instantánea e itera sobre esa instantánea, proporcionando una vista consistente de los datos a todos los lectores. Las instantáneas son costosas ya que consumen más memoria, pero sí para su requisito dado, esta técnica es la correcta. Y sí, use bloqueos (mutex / semáforo / spinlock) para proteger la operación de escritura de otros hilos / procesos de escritor que necesiten actualizar la misma información.
FWIW, esto es trivial de resolver si tienes un recolector de basura. En F #, por ejemplo, puede usar una referencia mutable a una lista vinculada o un mapa puramente funcional (árbol binario equilibrado) sin bloqueos. Esto funciona porque las estructuras de datos son inmutables y la escritura de una referencia (para actualizar después de una escritura) es atómica, por lo que los lectores simultáneos tienen la garantía de ver la estructura de datos anterior o nueva, pero nunca la corrupción. Si tienes varios escritores, puedes serializarlos.
Sin embargo, esto es mucho más difícil de resolver en C ++ ...
No estoy seguro de que alguien haya mencionado esto, pero me inspiraría en el ConcurrentHashMap de Java. Ofrece recorrido, recuperación e inserción sin bloqueo o espera. El único bloqueo ocurre una vez que has encontrado un cubo de datos correspondiente a la tecla hash y estás atravesando ese cubo (es decir, SOLO bloqueas el cubo, no el mapa hash real). "En lugar de un solo bloqueo de recopilación, ConcurrentHashMap usa un conjunto fijo de bloqueos que forman una partición sobre la colección de segmentos".
Puede encontrar más detalles sobre la implementación real aquí . Creo que todas las cosas que se muestran en la implementación se pueden hacer tan fácilmente con C ++.
Así que revisemos su lista de requisitos:
1. High throughput. CHECK
2. Thread safe. CHECK
3. Efficient inserts happen in O(1). CHECK
4. Efficient removal (with no data races or locks). CHECK
5. VERY efficient traversal. CHECK
6. Does not lock or wait. CHECK
7. Easy on the memory. CHECK
8. It is scalable (just increase the lock pool). CHECK
Aquí hay un ejemplo de una entrada de mapa:
protected static class Entry implements Map.Entry {
protected final Object key;
protected volatile Object value;
protected final int hash;
protected final Entry next;
...
}
Tenga en cuenta que el valor es volátil, por lo tanto, cuando eliminemos una entrada, estableceremos el valor en NULL, que es automáticamente visible para cualquier otro hilo que intente leer el valor.
Llego un poco tarde a la fiesta. Pero si alguien todavía está buscando una solución práctica a este problema y aún no se han decidido por un servidor, permítanme sugerir el motor de aplicaciones de Google . Su Datastore está optimizado para este tipo de requisitos.