Elasticsearch desde cero, parte 1

Introducción

La motivación es comprender mejor cómo Elasticsearch, Lucene y, en cierta medida, los motores de búsqueda en general funcionan por dentro. Si bien puedes conducir un automóvil con solo girar el volante y pisar algunos pedales, los conductores altamente capacitados comprender, al menos, algo de la mecánica del vehículo. Lo mismo sucede con los motores de búsqueda. Elasticsearch proporciona API que son muy fáciles de usar, y te permitirá comenzar y avanzar sin mucho esfuerzo. Sin embargo, para aprovecharlo al máximo, resulta útil tener conocimientos sobre las estructuras de datos y los algoritmos subyacentes. Este entendimiento te permite usar por completo su conjunto esencial de características, de modo que puedes mejorar las experiencias de búsqueda de tus usuarios y, al mismo tiempo, mantener los sistemas con buen rendimiento, confiables y actualizados (casi) en tiempo real.

Comenzaremos por la estructura de índice básica, el índice invertido. Es una estructura de datos muy versátil. Al mismo tiempo, es fácil de usar y comprender. Dicho esto, la implementación de Lucene es una prueba de ingeniería impresionante y sumamente optimizada. No nos adentraremos en los detalles de implementación de Lucene, sino que nos enfocaremos en cómo se usa y se crea el índice invertido. Eso es lo que influye en cómo podemos buscar e indexar.

Habiendo introducido el índice invertido como el punto "cero" de los niveles de abstracción, veremos lo siguiente:

• Cómo se realizan las búsquedas simples.
• Qué tipos de búsquedas pueden (y no pueden) hacerse de forma efectiva y por qué, con un índice invertido, transformamos los problemas hasta que parecen problemas de prefijo de cadena.
• Por qué es importante el procesamiento de texto.
• Cómo se crean en "segmentos" los índices y cómo afecta eso la búsqueda y la actualización.
• Qué constituye un índice de Lucene.
• El shard y el índice de Elasticsearch.

En ese punto, sabremos mucho sobre lo que sucede dentro de un solo nodo de Elasticsearch al buscar y al indexar. En el segundo artículo de la serie veremos los aspectos relacionados con la distribución de Elasticsearch.

Índices invertidos y términos de índices

Supongamos que tenemos estos tres documentos simples: "Winter is coming.", "Ours is the fury." y "The choice is yours.". Luego de un procesamiento de texto simple (cambio a minúsculas, eliminación de la puntuación y división de palabras), podemos construir el "índice invertido" que se muestra en la imagen.

El índice invertido mapea los términos con los documentos (y posiblemente con las posiciones en los documentos) que contienen el término. Como los términos en el diccionario están ordenados, podemos encontrar rápidamente un término y, luego, sus instancias en la estructura de posteos. Esto es lo opuesto a un "índice de avance", que enumera términos relacionados con un documento específico.

Luego se realiza una búsqueda simple con varios términos mediante la búsqueda de todos los términos y sus instancias, y se toma la intersección (para las búsquedas AND) o la unión (para las búsquedas OR) de los conjuntos de instancias a fin de obtener la lista resultante de documentos. Por supuesto, los tipos de búsqueda más complejos son más elaborados, pero el enfoque es el mismo: operar primero sobre el diccionario para encontrar términos candidatos, luego sobre las instancias correspondientes, las posiciones, etc.

En consecuencia, un término de índice es la unidad de búsqueda. Los términos que generamos establecen los tipos de búsqueda que podemos (y no podemos) realizar de forma eficiente. Por ejemplo, con el diccionario de la imagen anterior, podemos encontrar de forma eficiente todos los términos que comienzan con "c". Sin embargo, no podemos realizar con eficiencia una búsqueda sobre todo lo que contenga "ours". Para hacerlo, deberíamos recorrer todos los términos para descubrir que "yours" también contiene la subcadena. Esto resulta prohibitivamente costoso cuando el índice no es ridículamente pequeño. En términos de complejidad, buscar términos por su prefijo es \(\mathcal{O}\left(\mathrm{log}\left(n\right)\right)\), mientras que encontrar términos con una subcadena arbitraria es \(\mathcal{O}\left(n\right)\).

En otras palabras, podemos encontrar cosas de manera eficiente dados prefijos de términos. Cuando todo lo que tenemos es un índice invertido, queremos que todo se vea como un problema de prefijo de cadena. Estos son algunos ejemplos de tales transformaciones. Algunos son simples, el último es casi mágico.

• Para encontrar todo lo que termine con "tastic", podemos indexar al revés (por ejemplo "fantastic" → "citsatnaf") y buscar todo lo que comience con "citsat".
• Encontrar subcadenas suele involucrar la división de los términos en términos más pequeños denominados "n-grama". Por ejemplo, "yours" puede dividirse en "^yo", "you", "our", "urs", "rs$", lo que significa que obtendríamos instancias de "ours" si buscamos "our" y "urs".
• En el caso de idiomas con palabras compuestas, como el noruego y el alemán, debemos "descomponer" palabras como "Donaudampfschiff" en, por ejemplo, {"donau", "dampf", "schiff"} para encontrarlas cuando buscamos "schiff".
• Los puntos de coordenadas geográficas, como (60.6384, 6.5017), pueden convertirse en "hashes geográficos", en este caso "u4u8gyykk". Cuanto más larga sea la cadena, mayor será la precisión.
• A fin de permitir la correspondencia fonética, que resulta muy útil para los nombres de las personas, por ejemplo, existen algoritmos como Metaphone que convierten "Smith" a {"SM0", "XMT"} y "Schmidt" a {"XMT", "SMT"}.
• En el caso de datos numéricos (y marcas de tiempo), Lucene genera automáticamente varios términos con distinta precisión tipo trie, por lo que las búsquedas de rango pueden hacerse con eficiencia¹. En palabras simples, el número 123 puede almacenarse como "1" centena, "12" decenas y "123". Por lo tanto, buscar todo en el rango [100, 199] significa todo lo que coincide con el término "1" centena. Esto no es lo mismo que buscar todo lo que comienza con "1", por supuesto, porque eso también incluiría "1234", etc.
• Para realizar búsquedas del tipo "¿Quieres decir?" y encontrar palabras con ortografía similar a la de la entrada, se puede crear una automatización "Levenshtein" que recorra de manera efectiva el diccionario. Esto es excepcionalmente complejo, esta es una historia fascinante sobre cómo terminó en Lucene.

Un análisis técnico profundo sobre el procesamiento de texto es material para muchos artículos futuros, pero resaltamos por qué es importante ser meticuloso en la generación de términos de indexación: para obtener búsquedas que puedan tener un rendimiento eficiente.

Creación de índices

Al crear índices invertidos, debemos priorizar ciertas cuestiones: la velocidad de búsqueda, la compactación del índice, la velocidad de indexación y el tiempo necesario para que los cambios sean visibles.

La velocidad de búsqueda y la compactación del índice están relacionadas: cuando se busca en un índice pequeño, se necesitan procesar menos datos, y cabrán más de ellos en la memoria. Ambas, en especial la compactación, se logran a costa de la velocidad de indexación, como veremos.

A fin de minimizar los tamaños de los índices, se utilizan varias técnicas de compresión. Por ejemplo, al almacenar los posteos (que pueden ser bastantes grandes), Lucene recurre a artimañas, como el codificado delta (por ejemplo, [42, 100, 666] se almacena como [42, 58, 566]), usando un número variable de bytes (para que los números pequeños puedan guardarse con un solo byte), etc.

Mantener las estructuras de datos pequeñas y compactas significa sacrificar la posibilidad de actualizarlas de forma efectiva. De hecho, Lucene no las actualiza para nada: los archivos de índice que escribe Lucene son inmutables, es decir que no se actualizan nunca. Esto es bastante distinto a los árboles B, por ejemplo, que pueden actualizarse y con frecuencia te permiten especificar un factor de llenado para indicar el grado de actualización que esperas.

La excepción son las eliminaciones. Cuando eliminas un documento de un índice, el documento se marca como tal en un archivo de eliminación especial, que es un bitmap, cuya actualización es económica. Las estructuras del índice en sí no se actualizan.

En consecuencia, actualizar un documento previamente indexado es una eliminación seguida de una reinserción del documento. Ten en cuenta que esto significa que actualizar un documento es incluso más costoso que agregarlo en primer lugar. Por lo tanto, almacenar elementos como contadores que cambian rápidamente en un índice de Lucene no suele ser una buena idea; no hay actualización de los valores.

Cuando se agregan documentos nuevos (quizás a través de una actualización), los cambios en el índice primero se almacenan en búfer en la memoria. Eventualmente, los archivos de índice en su totalidad, se vacían al disco. Ten en cuenta que esto hace referencia al sentido que Lucene le da a "vaciar". La operación de vaciado de Elasticsearch incluye una confirmación de Lucene y más, lo que se abarca en la sección de log de transacciones.

Cuándo realizar el vaciado puede depender de varios factores: con qué rapidez los cambios deben ser visibles, la memoria disponible para almacenar en búfer, la saturación de E/S, etc. Por lo general, para la velocidad de indexación, los búferes más grandes son mejores, siempre que sean lo suficientemente pequeños para que la E/S pueda mantenerse al nivel². Veremos más detalles al respecto en la próxima sección.

Los archivos escritos conforman un segmento del índice.

Segmentos de índice

Un índice de Lucene está compuesto de uno o más segmentos de índice inmutables, que son básicamente "miniíndices". Cuando realizas una búsqueda, Lucene busca en cada segmento, filtra las eliminaciones y combina los resultados de todos los segmentos. Por supuesto, esto se vuelve cada vez más tedioso a medida que aumenta la cantidad de segmentos. A fin de que la cantidad de segmentos pueda manejarse, Lucene ocasionalmente combina los segmentos conforme a alguna política de combinación a medida que se agregan segmentos nuevos. Michael McCandless, hacker de Lucene, tiene un blog excelente en el que explica y muestra la combinación de segmentos.³ Cuando los segmentos se combinan, los documentos marcados como eliminados finalmente se desechan. Es por esto que agregar más documentos puede dar como resultado un tamaño de índice menor: puede desencadenar una combinación.

Elasticsearch y Lucene, por lo general, hacen un buen trabajo respecto a cuándo combinar segmentos. Las políticas de Elasticsearch pueden modificarse con el ajuste de la configuración de combinación. También puedes usar la API de optimización para forzar combinaciones.

Antes de que los segmentos se vacíen al disco, los cambios se almacenan en búfer en la memoria. Previamente (Lucene

A medida que se crean segmentos nuevos (debido al vaciado o a una combinación), también provocan la invalidación de ciertas memorias caché, lo que puede afectar de forma negativa el rendimiento de búsqueda. Las memorias caché, como la de campo y filtro, son por segmento. Elasticsearch tiene una API de "entibiado"⁵, para que puedan "entibiarse" las memorias caché necesarias antes de que el nuevo segmento se ponga a disposición para la búsqueda.

La causa más común de vaciados con Elasticsearch es probablemente la actualización continua de índices, que sucede una vez por segundo, de forma predeterminada. A medida que se vacían nuevos segmentos, se ponen a disposición para la búsqueda, lo que habilita la búsqueda en tiempo (casi) real. Si bien un vaciado no es tan costoso como una confirmación (dado que no necesita esperar una escritura confirmada), sí provoca la creación de un nuevo segmento, lo que invalida algunas memorias caché y, posiblemente, desencadena una combinación.

Cuando indexar el rendimiento es importante, por ejemplo, al (re)indexar un batch, no resulta productivo dedicar mucho tiempo a vaciar y combinar segmentos pequeños. Por lo tanto, en estos casos suele ser una buena idea aumentar temporalmente la configuración de refresh_interval o incluso deshabilitar la actualización automática por completo. Siempre se puede actualizar manualmente o cuando haya terminado la indexación.

Índices de Elasticsearch

"Cualquier problema en ciencias de la computación puede ser solucionado con otra capa de indirección" – David J. Wheeler

Un índice de Elasticsearch está compuesto por uno o más shards, que puede tener cero o más réplicas. Estos son todos índices individuales de Lucene. Es decir, un índice de Elasticsearch está compuesto por muchos índices de Lucene, que a su vez están compuestos por segmentos de índices. Cuando buscas en un índice de Elasticsearch, la búsqueda se ejecuta en todos los shards (y, por lo tanto, en todos los segmentos) y se combina. Lo mismo sucede cuando buscas en varios índices de Elasticsearch. En realidad, buscar en dos índices de Elasticsearch con un shard cada uno es prácticamente lo mismo que buscar en un índice con dos shards. En ambos casos, se busca en dos índices de Lucene subyacentes.

A partir de aquí en este artículo, cuando hagamos referencia a un "índice" sin especificar, nos referiremos a un índice de Elasticsearch.

Un "shard" es la unidad de escalado básica de Elasticsearch. A medida que se agregan documentos al índice, se enrutan a un shard. De forma predeterminada, esto se realiza de manera rotativa, según el hash de la ID del documento. En la segunda parte de esta serie, veremos en más detalle cómo se acomodan los shards. Es importante saber, sin embargo, que la cantidad de shards se especifica al momento de la creación del índice y no puede modificarse luego. En una presentación temprana de Elasticsearch que realizó Shay se abarca muy bien por qué un shard es en realidad un índice de Lucene completo, además de los varios beneficios y compensaciones en comparación con otros métodos.

Los índices de Elasticsearch, y los shards (además de las réplicas), a los que se envían las solicitudes de búsqueda pueden personalizarse de varias formas. Al combinar patrones de índices, alias de índices y enrutamientos de documentos y búsqueda, pueden implementarse muchas estrategias diferentes de flujos de datos y particionamiento. No entraremos en detalle aquí, pero podemos recomendar el artículo de Zachary Tong sobre personalización del enrutamiento de documentos y la presentación de Shay Banon sobre big data, búsqueda y analíticas. Para darte algunas ideas, estos son algunos ejemplos:

• Muchos datos se basan en el tiempo, por ejemplo, logs, tweets, etc. Al crear un índice por día (o semana, mes, etc.), podemos limitar con eficiencia las búsquedas a ciertos períodos, y suprimir datos antiguos. Recuerda, no podemos eliminar de forma eficiente algo en un índice existente, pero eliminar un índice completo es económico.
• Cuando las búsquedas deben limitarse a un cierto usuario (por ejemplo, "buscar en tus mensajes"), puede resultar útil enrutar todos los documentos de ese usuario al mismo shard, a fin de reducir la cantidad de índices en los que se debe buscar.

Transacciones

Mientras que Lucene tiene el concepto de transacciones, Elasticsearch no. Todas las operaciones en Elasticsearch se agregan a la misma línea de tiempo, lo que no necesariamente es consistente por completo en todos los nodos, dado que el vaciado depende del tiempo.

Gestionar el aislamiento y la visibilidad de distintos segmentos, memorias caché y demás en todos los índices de todos los nodos en un sistema distribuido es muy difícil. En lugar de intentar hacer esto, se prioriza la velocidad.

Elasticsearch tiene un "log de transacciones" al que se adjuntan los documentos que se indexarán. Adjuntar a un archivo de logs es mucho más económico que crear segmentos, por lo que Elasticsearch puede escribir los documentos que se indexarán en algún lugar durable, además de hacerlo en el búfer en la memoria, que se pierde cuando hay fallas. También puedes especificar el nivel de consistencia necesario al indexar. Por ejemplo, puedes requerir que todas las réplicas hayan indexado el documento antes de devolver la operación del índice.

Resumen

A modo de resumen, estas son las propiedades importantes que debes tener en cuenta en relación con cómo Lucene crea y actualiza índices en un solo nodo, y busca en ellos:

• Cómo procesamos el texto que indexamos determina cómo podemos realizar la búsqueda. El análisis adecuado del texto es importante.
• Los índices se crean primero en la memoria y luego, ocasionalmente, se vacían en segmentos al disco.
• Los segmentos de índices son inmutables. Los documentos eliminados se marcan como tales.
• Un índice está compuesto de varios segmentos. Una búsqueda se realiza en todos los segmentos, y los resultados se combinan.
• Los segmentos se combinan ocasionalmente.
• Las memorias caché de campo y filtro son por segmento.
• Elasticsearch no tiene transacciones.

En el siguiente artículo de esta serie, veremos cómo se realizan la búsqueda y la indexación en todo el cluster.