[SPA] Indice inverso con Redis
Redis es una base de datos NoSQL de tipo clave valor. Cuando decimos esto, acude a nuestra cabeza el hecho de que al ser clave valor solo sirve para implementaciones de tipo Cache, pero por suerte no es así. Veremos cómo crear un índice inverso que sirve para las búsquedas de tipo full text search.
Pero primero de todo ¿qué es un índice inverso? Es un índice que se mantiene en un archivo aparte - por este motivo, al índice inverso también se lo conoce como archivo inverso - y que puede hacer referencia a más de una fuente.
Para dar un ejemplo práctico, en el libro Domain Driven Design, me encuentro con la palabra continuous en la página 15 cuando habla de continuous learning y en la página 341 cuando habla de continuous integration. Mientras que en el libro Continuous Delivery se encuentra en la página 36. Un índice inverso sería un documento donde solo se mantengan las referencias de la palabra continuous ordenadas por orden de importancia. Por ejemplo, puede creer que si alguien busca la palabra continuous seguramente estará buscando continuos integrations por lo tanto el libro de Continuous Delivery le servirá más, luego pondré la segunda referencia del libro Domain Driven Design y por último la referencia que habla de continuous learning.
| Documento | Orden | Capítulo | Página | Párrafo | Posición |
|---|---|---|---|---|---|
| Domain Driven Design | 3 | 1 | 15 | 4 | 1 |
| Domain Driven Design | 2 | 14 | 341 | 1 | 1 |
| Continuous Delivery | 1 | 2 | 36 | 4 | 5 |
El propósito es tener búsquedas de tipo full text search mucho más rápidas, y en contra tiene que se tomará mucho más tiempo al agregar un documento porque se tienen que analizar todas las palabras, descartar aquellas palabras que semánticamente no agregan valor (a, al, el, si, etc.) y crear archivos nuevos para las palabras nuevas o actualizar los índices si ya existiera.
¿Cómo lo hacemos con redis?
Por cada palabra creamos una lista ordenada siendo la palabra a buscar la clave de la lista. En la lista ordenada agregamos la posición del ranking que ocupará y una referencia o alias de la posición donde está.
ZADD continuous 3 refDDD1
ZADD continuous 2 refDDD2
ZADD continuous 1 refCD1
Nota: estoy usando los comandos de Redis directamente para que puedas reproducirlo con el redis-cli.exe que está en el directorio de instalación del propio Redis. No quiero limitar el ejemplo a una plataforma y un solo driver.
El resultado luego de procesar las entradas de continuous, integration y learning sería este
Para que se pueda hacer una búsqueda de tipo autocomplete, agregamos los n-gram necesarios. A modo de ejemplo, lo haré con la primer referencia
ZADD c 1 refCD1
ZADD co 1 refCD1
ZADD con 1 refCD1
ZADD cont 1 refCD1
ZADD conti 1 refCD1
ZADD contin 1 refCD1
ZADD continu 1 refCD1
ZADD continuo 1 refCD1
ZADD continuou 1 refCD1
ZADD continuous 1 refCD1
ZADD c 2 refDD2
ZADD co 2 refDD2
ZADD con 2 refDD2
....
Luego cada alias se coloca como clave de una estructura hash con el resto de valores que me interesa que estén de la búsqueda, como documento, capítulo y página.
HMSET refDDD1 documento “Domain Driven Design” capitulo 1 pagina 15 parrafo 4 posicion 1
HMSET refDDD2 documento “Domain Driven Design” capitulo 14 pagina 341 parrafo 1 posicion 1
HMSET refCD1 documento “Continuous Delivery” capitulo 2 pagina 36 parrafo 4 posicion 5
y ahora ¡¡a buscar!!
Cuando ya tenemos todas las palabras con sus n-grams, tenemos que hacer el algoritmo de búsqueda. Pongamos el ejemplo que la persona escribe "con" como palabra clave.
zrange con 0 4
Con este comando obtendremos las primeras cinco palabras (la posición de inicio y fin se incluyen) de la lista ordenada que tiene la clave "con". Como es una lista ordenado el resultado será:
refCD1
refDDD2
refDDD1
Tomamos estos valores y buscamos cada valor como un hash para obtener el nombre del documento
HGET refCD1 documento
El resultado de este ultimo comando será
Continuous Delivery
Performance
Según la documentación de redis, el comando zrange es una operación con un coste O(log(N)+M) donde N es la cantidad de registros que tiene la lista ordenada (es decir nuestro índice inverso) y M la cantidad de items que queremos que devuelva.
Mientras que el comando HGET tiene una complejidad O(1), es decir, tiene el mismo coste, sin importar cuan grande es el hash.
Si en el ejemplo tuviéramos que devolver no solo el nombre del documento, sino también el titulo, párrafo, etc.. tendríamos que usar el comando HGETALL, este comando tiene un coste de O(N), es decir, se incrementa cuanto mas propiedades del documento guardamos.
Si lo que te gustan son números de una aplicación en producción, te cuento... para un ranking de 150.000 posiciones, con un promedio de 16 palabras por posición que incluía el nombre del producto y palabras sinónimas, se hace un ZRANGE que trae 30 registros y luego 30 búsquedas de tipo HGET para obtener el título del producto, es decir 31 busquedas, y esta tardando 4 milisegundos en un i7 a 2.3 Ghz y no ocupo más de 400 Mb de RAM.