Ctrie
Un hash-trie concurrente o Ctrie [1] [2] es una implementación simultánea sin bloqueo seguro para subprocesos de un trie mapeado de matriz hash . Se utiliza para implementar la abstracción del mapa concurrente. Tiene operaciones de inserción y eliminación concurrentes particularmente escalables y es eficiente en memoria. [3] Es la primera estructura de datos concurrente conocida que admite instantáneas atómicas sin bloqueo O (1) . [2] [4]
La estructura de datos de Ctrie es una matriz hash concurrente sin bloqueo mapeada trie basada en instrucciones de comparación e intercambio de una sola palabra en un sistema de memoria compartida. Admite operaciones simultáneas de búsqueda, inserción y eliminación. Al igual que la matriz hash mapeada trie , utiliza todo el espacio de 32 bits para los valores hash, por lo que tiene un bajo riesgo de colisiones de códigos hash. Cada nodo puede ramificarse hasta 32 sub-intentos. Para conservar memoria, cada nodo contiene un mapa de bits de 32 bits donde cada bit indica la presencia de una rama seguida de una matriz de longitud igual al peso de Hamming del mapa de bits.
Las claves se insertan realizando una operación atómica de comparación e intercambio en el nodo que debe modificarse. Para garantizar que las actualizaciones se realicen de forma independiente y en el orden adecuado, se inserta un nodo de direccionamiento indirecto especial (un nodo I) entre cada nodo regular y sus subintentos.
La figura anterior ilustra la operación de inserción de Ctrie. Trie A está vacío: se usa una instrucción CAS atómica para intercambiar el antiguo nodo C1 con la nueva versión de C1 que tiene la nueva clave k1 . Si el CAS no tiene éxito, se reinicia la operación. Si el CAS tiene éxito, obtenemos el trie B. Este procedimiento se repite cuando se agrega una nueva clave k2 (trie C). Si dos códigos hash de las teclas en Ctrie chocan como es el caso con k2 y k3, Ctrie debe extenderse con al menos un nivel más - el trie D tiene un nuevo nodo de direccionamiento indirecto I2 con un nuevo nodo C2 que contiene ambas teclas en colisión. Se realizan más instrucciones CAS en el contenido de los nodos de indirección I1 e I2; dichas instrucciones CAS se pueden realizar de forma independiente entre sí, lo que permite actualizaciones simultáneas con menos contención.
Ctrie se define mediante el puntero al nodo raíz de direccionamiento indirecto (o un nodo I raíz). Los siguientes tipos de nodos están definidos para Ctrie:
Un nodo C es un nodo de ramificación. Por lo general, contiene hasta 32 ramas, por lo que W anterior es 5. Cada rama puede ser un par clave-valor (representado con un nodo S) u otro nodo I. Para evitar desperdiciar 32 entradas en la matriz de bifurcaciones cuando algunas bifurcaciones pueden estar vacías, se utiliza un mapa de bits entero para indicar qué bits están llenos y cuáles vacíos. El método auxiliar flagpos se usa para inspeccionar los bits de código hash relevantes para un nivel dado y extraer el valor del bit en el mapa de bits para ver si está establecido o no, lo que indica si hay una rama en esa posición o no. Si hay un bit, también calcula su posición en la matriz de ramas. La fórmula utilizada para hacer esto es:
