Una tabla hash concurrente o un mapa hash concurrente es una implementación de tablas hash que permite el acceso simultáneo por parte de múltiples subprocesos utilizando una función hash . [1] [2]
Las tablas hash concurrentes representan una estructura de datos concurrentes clave para su uso en computación concurrente que permite que múltiples subprocesos cooperen de manera más eficiente para un cálculo entre datos compartidos. [1]
Debido a los problemas naturales asociados con el acceso concurrente (es decir, la contención ), la forma y el alcance en que se puede acceder a la tabla de forma concurrente difieren según la implementación. Además, la aceleración resultante puede no ser lineal con la cantidad de subprocesos utilizados, ya que es necesario resolver la contención, lo que produce una sobrecarga de procesamiento . [1] Existen múltiples soluciones para mitigar los efectos de la contención, cada una de las cuales preserva la corrección de las operaciones en la tabla. [1] [2] [3] [4]
Al igual que con su contraparte secuencial, las tablas hash concurrentes se pueden generalizar y ampliar para adaptarse a aplicaciones más amplias, por ejemplo, permitiendo el uso de tipos de datos más complejos para claves y valores. Sin embargo, estas generalizaciones pueden afectar negativamente el rendimiento y, por lo tanto, deben elegirse de acuerdo con los requisitos de la aplicación. [1]
Al crear tablas hash concurrentes, las funciones que acceden a la tabla con el algoritmo hash elegido deben adaptarse para la concurrencia mediante la adición de una estrategia de resolución de conflictos. Dicha estrategia requiere gestionar los accesos de forma que los conflictos causados por ellos no resulten en datos corruptos, al tiempo que se aumenta idealmente su eficiencia cuando se utilizan en paralelo. Herlihy y Shavit [5] describen cómo los accesos a una tabla hash sin dicha estrategia (en su ejemplo basado en una implementación básica del algoritmo hash Cuckoo ) pueden adaptarse para su uso concurrente. Fan et al. [6] describen además un esquema de acceso a la tabla basado en el algoritmo hash Cuckoo que no solo es concurrente, sino que también mantiene la eficiencia espacial de su función hash al tiempo que mejora la localidad de la caché y el rendimiento de las inserciones.
Cuando las tablas hash no tienen un tamaño limitado y, por lo tanto, se les permite crecer o reducirse cuando sea necesario, el algoritmo hash debe adaptarse para permitir esta operación. Esto implica modificar la función hash utilizada para reflejar el nuevo espacio de claves de la tabla redimensionada. Maier et al. describen un algoritmo de crecimiento concurrente [1] .
Mega-KV [7] es un sistema de almacenamiento de clave-valor de alto rendimiento, donde se utiliza el algoritmo hash Cuckoo y la indexación de KV se paraleliza masivamente en modo por lotes mediante GPU. Con optimizaciones adicionales de la aceleración de GPU por parte de Nvidia y Oak Ridge National Lab , Mega-KV alcanzó otro récord de rendimiento en 2018 (hasta 888 millones de operaciones de clave-valor por segundo). [8]
Al igual que con cualquier estructura de datos concurrentes, las tablas hash concurrentes sufren una variedad de problemas conocidos en el campo de la computación concurrente como resultado de la contención. [3] Ejemplos de esto son el problema ABA , las condiciones de carrera y los bloqueos . El grado en que estos problemas se manifiestan o incluso ocurren depende de la implementación de la tabla hash concurrente; específicamente qué operaciones la tabla permite que se ejecuten simultáneamente, así como sus estrategias para mitigar los problemas asociados con la contención. Al manejar la contención, el objetivo principal es el mismo que con cualquier otra estructura de datos concurrentes, es decir, garantizar la corrección de cada operación en la tabla. Al mismo tiempo, naturalmente debe hacerse de tal manera que sea más eficiente que una solución secuencial cuando se usa simultáneamente. Esto también se conoce como control de concurrencia .
Mediante el uso de instrucciones atómicas como compare-and-swap o fetch-and-add , se pueden reducir los problemas causados por la contención al garantizar que un acceso se complete antes de que otro acceso tenga la oportunidad de interferir. Las operaciones como compare-and-swap a menudo presentan limitaciones en cuanto al tamaño de los datos que pueden manejar, lo que significa que los tipos de claves y valores de una tabla deben elegirse o convertirse en consecuencia. [1]
Al utilizar la denominada memoria transaccional de hardware (HTM), las operaciones de tabla pueden considerarse como transacciones de bases de datos , [3] lo que garantiza la atomicidad. Un ejemplo de HTM en la práctica son las extensiones de sincronización transaccional .
Con la ayuda de bloqueos , las operaciones que intentan acceder simultáneamente a la tabla o a los valores dentro de ella se pueden manejar de una manera que garantice un comportamiento correcto. Sin embargo, esto puede conducir a impactos negativos en el rendimiento, [1] [6] en particular cuando los bloqueos utilizados son demasiado restrictivos, bloqueando así accesos que de otra manera no competirían y podrían ejecutarse sin causar ningún problema. Se deben realizar consideraciones adicionales para evitar problemas aún más críticos que amenacen la corrección, como bloqueos activos, bloqueos mutuos o inanición . [3]
Una tabla hash concurrente de fases agrupa los accesos mediante la creación de fases en las que solo se permite un tipo de operación (es decir, una fase de escritura pura), seguida de una sincronización del estado de la tabla en todos los subprocesos. Shun y Blelloch ofrecen un algoritmo formalmente probado para esto. [2]
Ampliamente utilizado dentro del kernel de Linux , [3] la lectura-copia-actualización (RCU) es especialmente útil en casos donde el número de lecturas excede ampliamente el número de escrituras. [4]
Naturalmente, las tablas hash concurrentes encuentran aplicación allí donde las tablas hash secuenciales son útiles. La ventaja que ofrece la concurrencia en este caso radica en la posible aceleración de estos casos de uso, así como en la mayor escalabilidad. [1] Si se considera el hardware, como los procesadores multinúcleo , que cada vez tienen más capacidad de computación concurrente, la importancia de las estructuras de datos concurrentes dentro de estas aplicaciones crece de manera constante. [3]
Maier et al. [1] realizan un análisis exhaustivo de una variedad de implementaciones de tablas hash concurrentes, lo que permite comprender la eficacia de cada una en diferentes situaciones que pueden darse en casos de uso reales. Los hallazgos más importantes se pueden resumir de la siguiente manera:
Como era de esperar, una contención baja conduce a un comportamiento positivo en todas las operaciones, mientras que una contención alta se vuelve problemática cuando se trata de escritura. Sin embargo, este último es un problema de alta contención en general, en el que el beneficio del cálculo concurrente se niega debido al requisito natural de control de concurrencia que restringe los accesos concurrentes. La sobrecarga resultante causa un peor rendimiento que el de la versión secuencial ideal. A pesar de esto, las tablas hash concurrentes siguen demostrando ser invaluables incluso en escenarios de alta contención, al observar que una implementación bien diseñada aún puede lograr aceleraciones muy altas al aprovechar los beneficios de la concurrencia para leer datos simultáneamente.
Sin embargo, los casos de uso reales de las tablas hash concurrentes a menudo no son simplemente secuencias de la misma operación, sino más bien una mezcla de varios tipos. Por lo tanto, cuando se utiliza una mezcla de operaciones inserty find, la aceleración y la utilidad resultante de las tablas hash concurrentes se vuelven más obvias, especialmente cuando se observan findcargas de trabajo pesadas.
En última instancia, el rendimiento resultante de una tabla hash concurrente depende de una variedad de factores en función de su aplicación deseada. Al elegir la implementación, es importante determinar la cantidad necesaria de generalidad, las estrategias de manejo de contención y algunas consideraciones sobre si el tamaño de la tabla deseada se puede determinar de antemano o se debe utilizar un enfoque de crecimiento.
std::unordered_map . Se incluyen en ellos los mapas múltiples desordenados concurrentes, que permiten que existan múltiples valores para la misma clave en un mapa desordenado concurrente. [11] Además, se proporcionan mapas hash concurrentes que se basan en el mapa desordenado concurrente y permiten además el borrado simultáneo y contienen bloqueo integrado. [12]