Apache HBase almacena el archivo utilizando el árbol LSM, pero que es un árbol LSM?
En ciencias de la computación, el árbol de combinación estructurado de registro (o árbol LSM) 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 los datos de registro transaccional. Los árboles LSM, al igual que otros árboles de búsqueda, mantienen pares clave-valor. Los árboles LSM mantienen los 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. Como lo describe Patrick O'Neil, un árbol LSM de dos niveles comprende dos estructuras en forma de árbol, llamadas C0 y C1. C0 es más pequeño y reside totalmente en la memoria, mientras que C1 reside en el disco. Los nuevos registros se insertan en el componente C0 residente en la memoria. Si la inserción hace que el componente C0 exceda un cierto umbral de tamaño, un segmento contiguo de entradas se elimina de C0 y se combina en C1 en el disco. Las características de rendimiento de los árboles LSM se derivan del hecho de que cada componente está sintonizado con las características de su medio de almacenamiento subyacente, y de que los datos se migran eficientemente a través de medios en lotes sucesivos, utilizando un algoritmo que recuerda el ordenamiento de fusión.
La mayoría de los árboles LSM utilizados en la práctica emplean múltiples niveles. El nivel 0 se mantiene en la memoria principal y puede representarse mediante un árbol. Los datos en el disco se organizan en series 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 como una colección de archivos con rangos de claves que no se superponen. Para realizar una consulta en una clave en particular para obtener su valor asociado, se debe buscar en el árbol de nivel 0 y cada ejecución.
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 más reciente de clave-valor con una clave dada. 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 las diferentes versiones de la fila pueden tener diferentes conjuntos de columnas.
Para mantener bajo el costo de las consultas, el sistema debe evitar una situación en la que haya demasiadas ejecuciones.
Volviendo a Hbase, Apache HBase almacena el archivo utilizando el árbol LSM, que mantiene los datos en dos partes separadas que están optimizadas para el almacenamiento subyacente. Este tipo de estructura de datos depende de dos estructuras, una actual y una más pequeña en la memoria y una más grande en el disco persistente, y una vez que la parte en la memoria se vuelve más grande que un cierto límite, se fusiona con la estructura más grande que se almacena en el disco que utiliza un algoritmo de clasificación de mezcla y un nuevo árbol en memoria se crea para las solicitudes de inserción más nuevas. Transforma el acceso aleatorio a los datos en un acceso secuencial a los datos, lo que mejora el rendimiento de lectura, y la fusión es un proceso en segundo plano, que no afecta el procesamiento en primer plano.
