La estructura de datos más adecuada para búsquedas basadas en prefijo

Tengo que mantener una estructura de datos en memoria del par clave-valor. Tengo las siguientes restricciones:

  1. Tanto la clave como los valores son cadenas de texto de longitud 256 y 1024 respectivamente. Cualquier clave generalmente se parece a k1k2k3k4k5, cada k (i) es una cadena de 4-8 bytes en sí misma.
  2. En la medida de lo posible, la estructura de datos en memoria debe tener memoria contigua. Tengo un par de Key-Value con un valor de 400 MB y se me permite una asignación del 120%. (20% adicional para metadatos, solo si es necesario).
  3. DS tendrá las siguientes operaciones:
  4. Agregar [operación poco void add_kv(void *ds, char *key, char *value); ]: la firma típica se ve como void add_kv(void *ds, char *key, char *value);
  5. Eliminar [operación infrecuente]: la firma típica parece void del_kv(void *ds, char *key);
  6. LookUp [OPERACIÓN MÁS FRECUENTE]: la firma típica se parece a char *lookup(void *ds, char *key);
  7. Iterar [OPERACIÓN MÁS FRECUENTE]: Esta operación se basa en el prefijo. Asigna un iterador, es decir, itera todo el DS y devuelve la lista de valores-clave que coinciden con prefix_key (por ejemplo, “k1k2k3. *”, K (i) definido como anteriormente). Cada iteración se repite en este iterador (lista). Liberar el iterador libera la lista. Por lo general, se espera que un iterador devuelva un par de valor-clave de 100 KB en 400 MB DS (100 KB: 400 MB :: 1: 4000). La firma típica se ve como void *iterate(void *ds, char *prefix_key);
  8. Bullet 6 y Bullet 7 son las operaciones más frecuentes y deben optimizarse.

Mi pregunta es ¿cuál es la estructura de datos más adecuada para las restricciones anteriores?

He considerado el hachís. Agregar / eliminar / buscar se puede hacer en o (1) ya que tengo suficiente memoria pero no es óptimo para la iteración. Se puede hacer un hash de hash (hash en k1, luego en k2, luego en k3 …) o en una matriz de hash, pero luego viola la viñeta 2. ¿Qué otras opciones tengo?

Probablemente usaría algo como un árbol B + para esto: https://en.wikipedia.org/wiki/B%2B_tree

Como la eficiencia de la memoria es importante para usted, cuando un bloque de hoja se llena, debe redistribuir las claves entre varios bloques, si es posible, para asegurarse de que los bloques estén siempre> = 85% llenos. El tamaño del bloque debe ser lo suficientemente grande como para que la sobrecarga de los nodos internos sea solo un pequeño%.

También puede optimizar el almacenamiento en los bloques de hojas, ya que la mayoría de las claves en un bloque tendrán un prefijo largo y común que puede averiguar a partir de los bloques en los niveles más altos. Por lo tanto, puede eliminar todas las copias del prefijo común de las claves en los bloques de hojas, y sus 400MB de pares clave-valor tomarán sustancialmente menos de 400MB de RAM. Esto complicará un poco el proceso de inserción.

Hay otras cosas que puede hacer para comprimir aún más esta estructura, pero eso se complica rápidamente y no suena como si lo necesitara.

Yo implementaría esto como una tabla hash para la búsqueda, y un índice invertido separado para su iteración. Creo que tratar de convertir esos segmentos clave separados en enteros, como pediste en Formas de convertir cadenas de purpoes especiales a enteros para que sean un montón de trabajo innecesario.

Hay muchas implementaciones de tabla hash buenas para C ya disponibles, así que no voy a entrar en eso.

Para crear el índice invertido para la iteración, cree N tablas hash, donde N es el número de segmentos clave. Luego, para cada clave, divídala en sus segmentos individuales y agregue una entrada para ese valor en la tabla hash apropiada. Así que si tienes la clave “abcxyzqgx”, donde:

 k1 = abc k2 = xyz k3 = qgx 

Luego, en la tabla hash k1 agrega una entrada “abc = abcxyzqgx”. En la tabla hash k2 agrega una entrada “xyz = abcxyzqgx”. En la tabla hash k3 agregas “qgx = abcxyzqgx”. (Los valores, por supuesto, no serían las claves de cadena en sí, sino las referencias a las claves de cadena. De lo contrario tendrías cadenas de 256 caracteres O (nk)).

Cuando haya terminado, sus tablas hash tienen como claves los valores únicos del segmento, y los valores son listas de claves en las que existen esos segmentos.

Cuando desee buscar todas las claves que tienen k1 = abc y k3 = qgx, consulte la tabla de hash k1 para obtener la lista de claves que contienen abc, consulte la tabla de hash k3 para obtener la lista de claves que contienen qgx. Luego haces una intersección de esas dos listas para obtener el resultado.

Crear las tablas hash individuales es un costo de una sola vez de O (nk), donde n es el número total de claves, y k es el número de segmentos clave. El requisito de memoria, también, es O (nk). De acuerdo, eso es un poco caro, pero solo estás hablando de 1,6 millones de teclas, en total.

El caso de iteración es O (m * x), donde m es el número promedio de claves a las que hace referencia un segmento de clave individual, yx es el número de segmentos de clave en la consulta.

Una optimización obvia es poner un caché LRU delante de esta búsqueda, para que las consultas frecuentes se sirvan desde el caché.

Otra posible optimización es crear índices adicionales que combinen claves. Por ejemplo, si las consultas frecuentemente solicitan k1 y k2, y las combinaciones posibles son razonablemente pequeñas, entonces tiene sentido tener un caché k1k2 combinado. Entonces, si alguien busca k1 = abc y k2 = xyz, tienes un caché k1k2 que contiene “abcxyz = [lista de claves]”.

Usaría cinco tablas hash paralelas, correspondientes a los cinco prefijos posibles que se podrían buscar. Cada ranura de tabla hash contendría cero o más referencias, y cada referencia contendría la longitud del prefijo para ese par clave-valor particular, el hash de ese prefijo clave y un puntero a la clave real y la estructura de datos.

Para la eliminación, la clave real y la estructura de datos contendrían las cinco longitudes de prefijo y los hashes correspondientes, más los datos de caracteres para la clave y el valor.

Por ejemplo:

 #define PARTS 5 struct hashitem { size_t hash[PARTS]; size_t hlen[PARTS]; char *data; char key[]; }; struct hashref { size_t hash; size_t hlen; struct hashitem *item; }; struct hashrefs { size_t size; size_t used; struct hashref ref[]; }; struct hashtable { size_t size[PARTS]; struct hashrefs **slot[PARTS]; }; 

En una struct hashitem , si la key es k1k2k3k4k5 , entonces hlen[0]=2 , hash[0]=hash("k1") , hlen[1]=4 , hash[1]=hash("k1k2") , y así sucesivamente, hasta que hlen[4]=10 , hash[4]=hash("k1k2k3k4k5") .

Cuando se inserta un nuevo par clave-valor, primero se averiguan las longitudes de los prefijos ( hlen[] ) y sus hashes correspondientes ( hash[] ), luego se llama una función auxiliar a lo largo de las líneas de

 static int insert_pair(struct hashtable *ht, const char *key, const size_t hash[PARTS], const size_t hlen[PARTS], const char *data, const size_t datalen) { struct hashitem *item; size_t p, i; /* Verify the key is not already in the hash table. */ /* Allocate 'item', and copy 'key', 'data', 'hash', and 'hlen' to it. */ for (p = 0; p < PARTS; p++) { i = hash[p] % ht->size[p]; if (!ht->entry[i]) { /* Allocate a new hashrefs array, with size=1 or greater, initialize used=0 */ } else if (ht->entry[i].used >= ht->entry[i].size) { /* Reallocate ht->entry[i] with size=used+1 or greater */ } ht->entry[i].ref[ht->entry[i].used].hash = hash[p]; ht->entry[i].ref[ht->entry[i].used].hlen = plen[p]; ht->entry[i].ref[ht->entry[i].used].item = item; ht->entry[i].used++; } return 0; /* Success, no errors */ } 

La búsqueda de prefijo sería la misma que la búsqueda de tabla hash usando la clave completa:

 int lookup_filter(struct hashtable *ht, const size_t hash, const size_t hashlen, const size_t parts, /* 0 to PARTS-1 */ const char *key, int (*func)(struct hashitem *, void *), void *custom) { const struct hashrefs *refs = ht->entry[parts][hash % ht->size[parts]]; int retval = -1; /* None found */ size_t i; if (!refs) return retval; for (i = 0; i < refs->used; i++) if (refs->ref[i].hash == hash && refs->ref[i].hlen == hashlen && !strncmp(refs->ref[i].item->key, key, hashlen)) { if (func) { retval = func(refs->ref[i].item, custom); if (retval) return retval; } else retval = 0; } return retval; } 

Tenga en cuenta el estilo de callback utilizado, para permitir que una sola búsqueda coincida con todos los prefijos. Una coincidencia de clave completa, asumiendo claves únicas, sería un poco más simple:

 struct hashitem *lookup(struct hashtable *ht, const size_t hash, const size_t hashlen, const char *key) { const struct hashrefs *refs = ht->entry[PARTS-1][hash % ht->size[PARTS-1]]; size_t i; if (!refs) return NULL; for (i = 0; i < refs->used; i++) if (refs->ref[i].hash == hash && refs->ref[i].hlen == hashlen && !strncmp(refs->ref[i].item->key, key, hashlen)) return refs->ref[i].item; return NULL; } 

La eliminación utilizaría la búsqueda, excepto que las coincidencias se pueden eliminar reemplazando la entrada coincidente con el elemento final en la misma matriz de referencia; o si el elemento es el único en la matriz de referencia, liberando la matriz completa por completo.

La razón por la que se acepta una matriz de referencia (varios elementos de datos por entrada de tabla hash) es porque los procesadores actuales almacenan en caché los datos en fragmentos (una línea de caché es el más pequeño almacenado en caché). Debido a que cada ranura de tabla hash contiene una o más coincidencias, con el hash completo y la longitud de hash del código, las colisiones reales en las que es necesario realizar una comparación byte por byte para determinar una coincidencia real son extremadamente raras, incluso para Funciones hash simples. (Esperaría algo así como 1,05 a 1,10 comparaciones de cadena por entrada coincidente, incluso con algo tan simple como un hash DJB2).

En otras palabras, este enfoque trata de minimizar el número de licenciados a los que se accede para encontrar el (los) par (es) deseado (s).

Dado que las partes iniciales tendrán muchos hashes duplicados (relativamente pocos hash de prefijos únicos) y longitudes de hash, puede ser más eficiente hacer que sus tablas de hash sean más pequeñas. (Las matrices de referencia serán más grandes). Debido a que los hashes y las longitudes de hash no cambian, en cualquier punto se puede cambiar el tamaño de cualquiera de las tablas hash, sin tener que recalcular ningún hash.

Tenga en cuenta que dado que todas las tablas hash de PARTS-1 se utilizan para escanear conjuntos de elementos, no es malo que sus matrices de referencia puedan llegar a ser bastante largas: estas matrices contendrán casi exclusivamente los elementos que uno está buscando de todos modos ! (En otras palabras, si una matriz de referencia crece hasta decir 10,000 entradas de largo, no es un problema, si se usa para encontrar las 9,750 entradas más o menos deseadas).

Personalmente también consideré una tabla de algún tipo, por ejemplo, con cada parte clave como un nivel adicional en la tabla. Sin embargo, buscar el conjunto de entradas con un prefijo dado implica entonces un recorrido de tabla y un acceso de memoria bastante dispersa. Creo, pero no he verificado (con un microbenchmark que compara los dos enfoques), que la tabla hash con matrices de referencia potencialmente grandes por espacio es más eficiente en tiempo de ejecución.