Fundamentos de bases de datos

Fundamentos de bashdb

• bashdb, el programa de base de datos más simple, está compuesto por dos funciones de bash.
• La función db_set agrega datos a un archivo y la función db_get busca los datos.
• Entre los problemas de bashdb están la durabilidad, la atomicidad, el aislamiento y el rendimiento.

Mejorar bashdb para que sea ACID

• ACID se refiere a las propiedades de las transacciones de base de datos: atomicidad, consistencia, aislamiento y durabilidad.
• Para mejorar la durabilidad de bashdb, se agrega el comando sync a db_set.
• Para el aislamiento, se añade bloqueo de archivos usando el programa flock.

Durabilidad

• fsync y fdatasync son llamadas al sistema que vacían el búfer de escritura al disco.
• El comando sync vacía al disco todas las páginas “sucias”, y la bandera -d llama a fdatasync.

Aislamiento

• Se usa flock para proporcionar aislamiento entre múltiples procesos en bashdb.
• flock es un programa de Linux para bloqueo de archivos, y la bandera -s permite lecturas concurrentes.

Malas noticias

• No se encuentra una forma sencilla de garantizar la atomicidad con bashdb.
• Para mejorar el rendimiento, es necesario optimizar el algoritmo O(n).

Motor de almacenamiento

• El propósito de un motor de almacenamiento es proporcionar una abstracción para leer y escribir datos en almacenamiento persistente.
• El diseño de un motor de almacenamiento busca minimizar la E/S de disco y las búsquedas en disco.

Árbol B mutable

• Un árbol B es una variante del BST con localidad espacial, lo que minimiza la E/S de disco y las búsquedas.
• Un árbol B es un BST generalizado en el que los nodos pueden tener más hijos.

Árbol LSM inmutable

• Un árbol LSM es una estructura de datos inmutable escrita secuencialmente, favorable para cargas de trabajo centradas en escritura.
• Un árbol LSM almacena temporalmente datos en memoria y, al llegar a cierta capacidad, los vacía como SSTables ordenadas.

Filtro de Bloom

• Un filtro de Bloom es una estructura de datos probabilística que permite verificar eficientemente si un elemento no existe en un conjunto.
• Un filtro de Bloom funciona usando funciones hash y tiene complejidad espacial O(log n).

Write Ahead Log

• WAL es un archivo especial que registra todas las operaciones de transacción y reconstruye el estado cuando se inicia el proceso de la base de datos.

Aislamiento

• Para lograr aislamiento, se puede usar bloqueo pesimista, bloqueo optimista o MVCC.
• El estándar ANSI/ISO SQL 92 define varios niveles de aislamiento de lectura.

Sistemas distribuidos

• Los sistemas distribuidos agregan complejidad, y los datos pueden distribuirse entre varias máquinas para lograr disponibilidad y escalado horizontal.
• Según el teorema CAP, un sistema solo puede garantizar dos de tres propiedades: consistencia, disponibilidad y tolerancia a particiones.

Hashing consistente

• El hashing consistente es un método de partición de datos que reduce la cantidad de elementos que deben migrarse cuando se agregan o eliminan nodos.

Opinión de GN⁺:

• Entender los problemas básicos de las bases de datos y las propiedades ACID es clave en la ingeniería de bases de datos.
• El ejemplo de bashdb ayuda a comprender los problemas que ocurren en sistemas de bases de datos reales.
• El diseño de motores de almacenamiento y sistemas distribuidos es un factor importante para determinar el rendimiento y la confiabilidad de una base de datos.

[GN⁺]

Comentarios de Hacker News

• Resumen del primer comentario:

  • Una de las características de las bases de datos basadas en LSM es que los registros eliminados o los tombstones pueden permanecer durante mucho tiempo.
  • Los tombstones solo deben omitirse en el nivel final, y no en todos los niveles.
  • De lo contrario, un tombstone de un nivel superior podría eliminarse y hacer que reaparezcan elementos de niveles inferiores.
  • Bases de datos como RocksDB intentan resolver este problema mediante optimizaciones.

• Resumen del segundo comentario:

  • Evitar aprender sobre sistemas distribuidos puede ser riesgoso.
  • En la práctica, todo sistema de producción no trivial es un sistema distribuido.
  • Si una base de datos es un conjunto de réplicas, entonces es un sistema distribuido.
  • Si quieres aprender sobre sistemas distribuidos, revisa jepsen.io y raft.github.io.

• Resumen del tercer comentario:

  • En cuanto a consistencia, existe la consistencia de la base de datos y la consistencia de la aplicación.
  • Puedes lograr ACID (atomicidad, consistencia, aislamiento, durabilidad) en una sola tabla, pero fallar en escrituras que abarcan varias tablas.
  • Al manejar transacciones que actualizan varias tablas al mismo tiempo, todas las tablas deben actualizarse a la vez o no actualizarse en absoluto.

• Resumen del cuarto comentario:

  • Es un texto que ofrece una excelente visión general de varios conceptos involucrados en la construcción de una base de datos.
  • Abarca desde extraer rendimiento en una sola máquina usando SIMD hasta algoritmos de consenso.
  • Incluye una mención de métodos formales aplicados a la confiabilidad de bases de datos y sistemas distribuidos.
  • Hay un artículo interesante sobre cómo el equipo de Amazon S3 hace modelado con TLA+.

• Resumen del quinto comentario:

  • Muchas personas aprenden bases de datos aprendiendo SQL, pero entender los B-trees ayuda a comprender mejor las fortalezas y debilidades de los RDBMS.
  • A menudo se intenta acelerar la base de datos agregando índices, pero en realidad eso solo oculta el problema.
  • Algunos problemas encajan bien con los B-trees, pero muchos no.
  • SQL no es más que una interfaz de consulta para un sistema remoto de B-trees.

• Resumen del sexto comentario:

  • Muchos desarrolladores pasan en algún momento por la etapa de intentar construir su propia pequeña base de datos.
  • A través de ese proceso se puede aprender mucho sobre lo que no funciona.
  • Crear tu propia base de datos ayuda a aumentar el respeto por las soluciones existentes.
  • Transferir datos desde disco de forma rápida y confiable es una tarea difícil.

• Resumen del séptimo comentario:

  • En la versión con Bash, la atomicidad puede lograrse copiando el archivo a un archivo temporal, modificándolo y luego usando sync; mv; sync.

• Resumen del octavo comentario:

  • Es un diseño muy interesante, con una API de documentos similar a MongoDB, replicación sin líder similar a Cassandra y una arquitectura de un núcleo por hilo similar a ScyllaDB.
  • Todo esto está implementado en Rust.

• Resumen del noveno comentario:

  • El libro 'Database Internals' es sorprendentemente excelente y ofrece una exploración profunda de los aspectos internos.
  • Pregunta si existe algún otro libro parecido.

• Resumen del décimo comentario:

  • El libro 'Database Design and Implementation' también es una lectura excelente, con muchos ejemplos escritos en Java.
  • Para investigación real, recomienda el trabajo de Andy (Pavlo), Viktor Leis, Thorsten Grust y Thomas Neumann.