En informática , el árbol de fusión estructurado en forma de registro (también conocido como árbol LSM o LSMT [1] ) es una estructura de datos con características de rendimiento que lo hacen atractivo para proporcionar acceso indexado a archivos con un alto volumen de inserción, como datos de registro transaccional . Los árboles LSM, al igual que otros árboles de búsqueda , mantienen pares clave-valor. Los árboles LSM mantienen datos en dos o más estructuras separadas, cada una de las cuales está optimizada para su respectivo medio de almacenamiento subyacente; los datos se sincronizan entre las dos estructuras de manera eficiente, en lotes.
Una versión simple del árbol LSM es un árbol LSM de dos niveles. [2] Como lo describe Patrick O'Neil , un árbol LSM de dos niveles comprende dos estructuras similares a árboles , llamadas C 0 y C 1. C 0 es más pequeño y reside completamente en la memoria, mientras que C 1 reside en el disco. Los nuevos registros se insertan en el componente C 0 residente en la memoria . Si la inserción hace que el componente C 0 exceda un cierto umbral de tamaño, se elimina un segmento contiguo de entradas de C 0 y se fusiona en C 1 en el disco. Las características de rendimiento de los árboles LSM se derivan del hecho de que cada componente está ajustado a las características de su medio de almacenamiento subyacente, y que los datos se migran de manera eficiente a través de los medios en lotes continuos, utilizando un algoritmo que recuerda al merge sort . Tal ajuste implica escribir datos de manera secuencial en lugar de como una serie de solicitudes de acceso aleatorio separadas. Esta optimización reduce el tiempo de búsqueda en unidades de disco duro (HDD) y la latencia en unidades de estado sólido (SSD).
La mayoría de los árboles LSM que se utilizan en la práctica emplean múltiples niveles. El nivel 0 se guarda en la memoria principal y se puede representar mediante un árbol. Los datos en el disco se organizan en ejecuciones ordenadas de datos. Cada ejecución contiene datos ordenados por la clave de índice. Una ejecución se puede representar en el disco como un solo archivo o, alternativamente, como una colección de archivos con rangos de claves que no se superponen. Para realizar una consulta sobre una clave particular para obtener su valor asociado, se debe buscar en el árbol de nivel 0 y también en cada ejecución. La versión Stepped-Merge del árbol LSM [3] es una variante del árbol LSM que admite múltiples niveles con múltiples estructuras de árbol en cada nivel.
Una clave en particular puede aparecer en varias ejecuciones, y lo que eso significa para una consulta depende de la aplicación. Algunas aplicaciones simplemente quieren el par clave-valor más reciente con una clave determinada. Algunas aplicaciones deben combinar los valores de alguna manera para obtener el valor agregado adecuado para devolver. Por ejemplo, en Apache Cassandra , cada valor representa una fila en una base de datos, y diferentes versiones de la fila pueden tener diferentes conjuntos de columnas. [4]
Para mantener bajo el costo de las consultas, el sistema debe evitar una situación en la que haya demasiadas ejecuciones.
Se han sugerido extensiones al método "nivelado" para incorporar estructuras de árbol B+ , por ejemplo, bLSM [5] y Diff-Index. [6] El árbol LSM se diseñó originalmente para cargas de trabajo de escritura intensiva. A medida que cada vez más cargas de trabajo de lectura y escritura coexisten bajo una estructura de almacenamiento de árbol LSM, los accesos a datos de lectura pueden experimentar una alta latencia y un bajo rendimiento debido a las frecuentes invalidaciones de datos almacenados en caché en cachés de búfer por operaciones de compactación del árbol LSM. Para volver a habilitar el almacenamiento en caché de búfer efectivo para accesos rápidos a datos, se propone e implementa un árbol de estructura de registro con búfer fusionado (LSbM-tree). [7]
En los árboles LSM, las operaciones de escritura están diseñadas para optimizar el rendimiento al reducir la E/S aleatoria y aprovechar las escrituras secuenciales en el disco. Cuando se inicia una operación de escritura, los datos se almacenan primero en un componente en memoria, que a menudo se implementa mediante una estructura de datos ordenada, como una lista de omisión o un árbol B+ .
Una vez que el búfer en memoria se llena, se vacía en el disco como un componente ordenado inmutable en el primer nivel (C1). Este vaciado se realiza de forma secuencial, lo que garantiza una alta eficiencia de E/S al evitar las costosas escrituras aleatorias típicas de los métodos de indexación tradicionales. Para mantener la durabilidad, el sistema puede utilizar un registro de escritura anticipada (WAL) que registra todas las escrituras entrantes antes de que se agreguen al búfer de memoria. Esto garantiza que no se pierdan datos en caso de que se produzca una falla durante una escritura.
A medida que los datos se acumulan en los distintos niveles del disco, los árboles LSM emplean un proceso de fusión similar a la ordenación por fusión para consolidar las entradas y mantener un orden de clasificación uniforme en todos los niveles. Este proceso también gestiona las actualizaciones y eliminaciones, eliminando las entradas redundantes u obsoletas. Las actualizaciones se tratan como nuevas escrituras, mientras que las eliminaciones se marcan con una entrada de lápida, que es un marcador de posición que indica que se ha eliminado la clave. Estas lápidas se eliminan posteriormente durante el proceso de fusión.
Dos políticas de fusión comunes rigen la forma en que los datos fluyen a través de los niveles: nivelación y estratificación. En la nivelación, solo existe un componente por nivel y la fusión se produce con mayor frecuencia, lo que reduce la cantidad total de componentes pero aumenta la amplificación de escritura. En la estratificación, pueden coexistir varios componentes dentro de un nivel y la fusión se produce con menor frecuencia, lo que reduce la amplificación de escritura pero aumenta los costos de lectura debido a que es necesario buscar más componentes.
Este diseño genera costos de escritura amortizados para políticas de fusión de nivelación, donde es la relación de tamaño entre niveles, es el número de niveles y es el número de entradas por página. [8]
Una operación de búsqueda de puntos recupera el valor vinculado a una clave específica. En los árboles LSM, debido a la estructura de múltiples niveles y la inmutabilidad de los componentes del disco, la búsqueda implica la comprobación de varios niveles para garantizar que se devuelva el valor más actualizado para la clave.
El proceso comienza con una búsqueda en el componente en memoria (C0), que contiene los datos más recientes. Como este componente está organizado como una estructura ordenada, la búsqueda es rápida y eficiente. Si se encuentra la clave aquí, se devuelve su valor de inmediato.
Si no se encuentra la clave en la memoria, la búsqueda se desplaza a los componentes del disco, comenzando por el primer nivel (C1) y continuando por los niveles más profundos (C2, C3, etc.). Cada nivel del disco también se ordena, lo que permite realizar búsquedas eficientes mediante métodos como la búsqueda binaria o la búsqueda en árbol . Los niveles más nuevos se comprueban primero porque contienen las actualizaciones y eliminaciones más recientes de la clave.
Para acelerar la búsqueda, los árboles LSM utilizan filtros Bloom con cada componente del disco. Estos filtros son estructuras probabilísticas que ayudan a determinar rápidamente si una clave está definitivamente ausente de un componente. Antes de acceder a cualquier componente del disco, el sistema verifica el filtro Bloom. Si el filtro indica que la clave no está presente, se omite el componente, lo que ahorra tiempo. Si el filtro sugiere que la clave podría estar allí, el sistema procede a buscar el componente.
La operación de búsqueda se detiene en cuanto se encuentra la clave, lo que garantiza que se devuelva la versión más reciente. Si la búsqueda llega al nivel final sin encontrar la clave, el sistema concluye que la clave no existe.
La complejidad de la búsqueda de puntos no se logra sin los filtros Bloom, ya que se debe buscar en cada nivel. Sin embargo, con los filtros Bloom, el costo de las búsquedas con cero resultados se reduce significativamente a , donde M es el tamaño total del filtro Bloom y N es la cantidad de claves. Para las búsquedas de claves existentes, el costo se debe a la presencia de filtros Bloom. [8]
Una consulta de rango recupera todos los pares clave-valor dentro de un rango especificado. La operación implica escanear varios componentes en la estructura jerárquica del árbol LSM y consolidar las entradas para garantizar resultados precisos y completos.
Una consulta de rango comienza buscando el componente en memoria (C0). Dado que este componente es normalmente una estructura de datos ordenada que admite consultas de rango, la consulta es eficiente y directa. Una vez que el componente en memoria finaliza, la consulta continúa con los componentes del disco, comenzando desde el primer nivel (C1) y continuando hacia niveles más profundos.
Cada componente del disco también se almacena como una estructura ordenada que permite realizar exploraciones de rango eficientes dentro de los componentes individuales. Para realizar la consulta de rango, el sistema ubica el punto de inicio en cada componente relevante y realiza exploraciones secuenciales hasta llegar al final del rango. Luego, los resultados de cada componente se combinan en una cola de prioridad para conciliar duplicados, actualizaciones y eliminaciones, lo que garantiza que el resultado final solo incluya la última versión.
Para lograr una mayor eficiencia, los árboles LSM suelen dividir los componentes del disco en rangos de claves más pequeños y disjuntos. De esta manera, al procesar una consulta de rango, el sistema puede buscar solo las particiones que tienen rangos superpuestos para reducir la cantidad de componentes a los que se accede. De manera similar a la búsqueda de puntos, a veces se utilizan filtros Bloom para decidir rápidamente si un componente del disco contiene alguna clave dentro del rango consultado, lo que permite que el sistema omita los componentes que se garantiza que son irrelevantes.
El rendimiento de una consulta de rango en árboles LSM depende de la selectividad de la consulta. Para consultas de rango corto, que acceden a menos claves que el doble del número de niveles, la consulta debe examinar componentes en todos los niveles, lo que genera un costo proporcional al número de niveles. Para consultas de rango largo, que acceden a muchas claves, el precio está dominado por el escaneo del nivel más grande, ya que contiene la mayoría de los datos. Por esta razón, el tiempo de ejecución para consultas de rango de ordenación es y para consultas de rango largo, donde es el número de claves en el rango. [8]
