Haz tu propia base de datos
(nan.fyi)- Se explican los principios básicos y el proceso de implementación de una base de datos clave-valor.
- Comienza con el almacenamiento persistente y la búsqueda a través de un sistema de archivos.
- Al agregar datos, se registra el contenido en un archivo con un comando como
$ db set 1 "Lorem ipsum". - Para buscar datos, se verifica secuencialmente cada par clave-valor dentro del archivo hasta encontrar la clave buscada.
- En actualizaciones, se reemplaza directamente el valor de la clave en el archivo, y en eliminaciones se elimina ese registro del archivo.
Introducción: El inicio para construir una base de datos propia
Si partimos del supuesto de que no existe el concepto de base de datos, se explora paso a paso cómo podrías crear la tuya propia.
Aquí se revisa el proceso de implementar la forma más simple de una base de datos clave-valor.
Idea base: almacenamiento persistente usando archivos
- El propósito de una base de datos es almacenar datos de forma persistente y, más tarde, buscar de forma eficiente.
- El método más común es utilizar un sistema de archivos para registrar cada par clave-valor en un archivo.
- Cuando se guardan datos, se añade el contenido al archivo con el formato
$ db set 1 "Lorem ipsum". - Para buscar, se recorre de forma secuencial todo el archivo de pares clave-valor hasta encontrar la clave deseada.
- En actualizaciones, se sobrescribe el valor de la clave directamente en el archivo; en eliminaciones, se elimina ese registro del archivo.
Problema: actualizaciones in-place ineficientes
- Modificar y eliminar datos directamente dentro del archivo es muy ineficiente.
- Un archivo es un flujo simple de bytes, así que si cambias datos intermedios, hay que mover todos los datos posteriores.
- Por ejemplo, al cambiar una fila por un nuevo valor, si la longitud cambia, surge la carga de mover todo lo que sigue.
- Cuantos más datos haya, mayor impacto tiene esto en la velocidad y la eficiencia.
Mejora 1: estructura de archivo append-only
- Se aplica un método donde los datos existentes se dejan intactos y solo se agregan nuevos registros al final del archivo al modificar o eliminar.
- Cada vez que cambian los datos, se añade un nuevo registro y la búsqueda pasa a usar siempre el último valor de cada clave.
- La eliminación se marca con un valor especial llamado "tombstone" (como
null, por ejemplo). - Ventaja: permite registrar cambios de forma eficiente sin mover datos existentes.
- Desventaja: el archivo crece con el tiempo por duplicados y marcas de borrado.
- La búsqueda sigue siendo lenta porque aún requiere escanear todo el archivo.
Mejora 2: gestión del tamaño de archivo y compaction (compresión)
- Para resolver el problema de archivos que crecen sin límite, cuando el archivo supera cierto tamaño se crea uno nuevo (segmento) y en el archivo anterior se eliminan datos innecesarios (duplicados o borrados), reduciendo su tamaño mediante compaction.
- Durante la compaction, se conserva solo la data realmente necesaria y se descartan registros antiguos o que solo contienen marcas de eliminación.
- Se evoluciona a una estructura de múltiples archivos segmento, y cuando hace falta se fusionan (merge).
Mejora 3: búsqueda rápida con índice (Index)
- Se construye un índice en memoria (tabla hash) con la posición (offset) de cada clave dentro del archivo para permitir búsquedas rápidas.
- Al consultar, se consulta primero el índice y se lee directamente la posición correspondiente en el archivo.
- Trade-off: la lectura mejora, pero como el índice vive en memoria, con muchas claves puede llegar al límite de RAM.
- Mantener el índice puede degradar un poco el rendimiento de escritura.
Mejora 4: Sorted String Tables y Sparse Index
- Si los datos se guardan siempre ordenados por clave, se obtiene alta eficiencia en consultas por rango (range query).
- Al aprovechar el orden, basta con guardar en el índice solo algunas claves (índice disperso o sparse index), no todas.
- Al ajustar la densidad del índice, se puede balancear el compromiso entre uso de memoria y eficiencia de búsqueda.
Implementación: combinación en memoria y disco para persistencia
- Los datos nuevos se escriben primero en una lista ordenada en memoria y además se registran en un archivo append-only como respaldo.
- Cuando la lista en memoria crece, se vuelca a un archivo en disco (SST) ordenado y se actualiza el índice.
- En consultas, primero se revisa la memoria y, si no está, se usa el índice para buscar en disco.
- Los archivos en disco se gestionan como inmutables y las actualizaciones/eliminaciones siguen tratándose como nuevos registros añadidos.
- Los datos duplicados o borrados se eliminan periódicamente mediante compaction para controlar el tamaño de los archivos.
Aparición de LSM Tree (Log-Structured Merge Tree)
- La estructura evolucionada se conoce y usa ampliamente hoy en día como LSM Tree.
- Es una combinación de memtable en memoria y sorted string table (SST) en disco, adecuada para entornos de gran velocidad y escala.
- Es la estructura central en sistemas de bases de datos clave-valor a gran escala como LevelDB y Amazon DynamoDB.
- Aunque tiene desventajas y diferencias frente a otras estructuras (como BD relacionales basadas en B-Tree), demuestra un excelente desempeño en escenarios de alto tráfico y escalabilidad.
Conclusión
- Se evoluciona desde un almacenamiento simple basado en archivos hacia arquitecturas más eficientes con append-only, índices, ordenamiento, segmentación-compaction y combinación memoria-disco.
- Es posible aprender el funcionamiento interno y la arquitectura de una base de datos al estudiar su construcción paso a paso.
- La estructura LSM Tree cumple un rol estándar en los sistemas modernos de gran escala.
- Queda abierta la exploración de otras alternativas, como la estructura B-Tree de bases de datos relacionales.
1 comentarios
Comentario de Hacker News
lorem ipsumcomo ejemplo; eso hace que uno lo pase por alto sin concentrarse mucho. Un ejemplo con datos reales habría llamado mucho más la atención. Por lo demás, es un artículo realmente genial.