Notions fondamentales sur les bases de données

Les bases de bashdb

• bashdb, le programme de base de données le plus simple, se compose de deux fonctions bash.
• La fonction db_set ajoute des données à un fichier, et la fonction db_get recherche les données.
• Parmi les problèmes de bashdb, on trouve la durabilité, l’atomicité, l’isolation et les performances.

Améliorer bashdb pour le rendre ACID

• ACID désigne les propriétés des transactions de base de données : atomicité, cohérence, isolation et durabilité.
• Pour améliorer la durabilité de bashdb, on ajoute la commande sync à db_set.
• Pour l’isolation, on ajoute un verrouillage de fichier à l’aide du programme flock.

Durabilité

• fsync et fdatasync sont des appels système qui vident les tampons d’écriture sur le disque.
• La commande sync vide toutes les pages « sales » sur le disque, et l’option -d appelle fdatasync.

Isolation

• flock permet d’apporter une isolation multi-processus à bashdb.
• flock est un programme Linux de verrouillage de fichiers, et l’option -s permet les lectures simultanées.

La mauvaise nouvelle

• Il n’existe pas de méthode simple pour garantir l’atomicité avec bashdb.
• Pour améliorer les performances, il faut optimiser l’algorithme en O(n).

Moteur de stockage

• Le rôle d’un moteur de stockage est de fournir une abstraction pour lire et écrire des données dans un stockage persistant.
• La conception d’un moteur de stockage vise à minimiser les E/S disque et les recherches sur disque.

B-arbre mutable

• Un B-arbre est une variante du BST dotée d’une localité spatiale, qui minimise les E/S disque et les recherches.
• Un B-arbre est un BST généralisé dans lequel les nœuds peuvent avoir davantage d’enfants.

Arbre LSM immuable

• Un arbre LSM est une structure de données immuable écrite séquentiellement, avantageuse pour les charges de travail orientées écriture.
• L’arbre LSM met les données en tampon en mémoire, puis les vide en SSTable triées lorsqu’une certaine capacité est atteinte.

Filtre de Bloom

• Un filtre de Bloom est une structure de données probabiliste qui permet de vérifier efficacement qu’un élément n’est pas présent dans un ensemble.
• Les filtres de Bloom fonctionnent à l’aide de fonctions de hachage et ont une complexité spatiale en O(log n).

Write Ahead Log

• Le WAL est un fichier spécial qui journalise toutes les opérations de transaction et permet de reconstruire l’état au démarrage du processus de base de données.

Isolation

• Pour atteindre l’isolation, on peut utiliser le verrouillage pessimiste, le verrouillage optimiste ou le MVCC.
• La norme ANSI/ISO SQL 92 définit différents niveaux d’isolation de lecture.

Systèmes distribués

• Les systèmes distribués ajoutent de la complexité et peuvent répartir les données sur plusieurs machines pour la disponibilité et la montée en charge horizontale.
• Selon le théorème CAP, un système ne peut garantir que deux propriétés parmi la cohérence, la disponibilité et la tolérance au partitionnement.

Hachage cohérent

• Le hachage cohérent est une méthode de partitionnement des données qui réduit la quantité d’éléments migrés lors de l’ajout ou de la suppression de nœuds.

Avis de GN⁺ :

• Comprendre les problèmes fondamentaux des bases de données et les propriétés ACID est au cœur de l’ingénierie des bases de données.
• L’exemple de bashdb aide à comprendre les problèmes qui se posent dans les systèmes de bases de données réels.
• La conception des moteurs de stockage et des systèmes distribués est un facteur clé qui détermine les performances et la fiabilité d’une base de données.

[GN⁺]

Avis sur Hacker News

• Résumé du premier commentaire :

  • L’une des caractéristiques des bases de données fondées sur les LSM est que les enregistrements supprimés ou les tombstones peuvent rester longtemps.
  • Il ne faut ignorer les tombstones qu’au niveau final, et non à tous les niveaux.
  • Sinon, les tombstones des niveaux supérieurs peuvent être supprimés et des éléments des niveaux inférieurs peuvent réapparaître.
  • Des bases de données comme RocksDB essaient de résoudre ce problème par des optimisations.

• Résumé du deuxième commentaire :

  • Éviter d’apprendre les systèmes distribués peut être risqué.
  • En pratique, tout système de production non trivial est un système distribué.
  • Si la base de données est un ensemble de réplication, alors c’est un système distribué.
  • Si vous voulez en apprendre davantage sur les systèmes distribués, consultez jepsen.io et raft.github.io.

• Résumé du troisième commentaire :

  • En matière de cohérence, il y a la cohérence de la base de données et la cohérence de l’application.
  • On peut atteindre l’ACID (atomicité, cohérence, isolation, durabilité) sur une table, mais échouer lors d’écritures sur plusieurs tables.
  • Lorsqu’on traite des transactions qui mettent à jour plusieurs tables en même temps, toutes les tables doivent être mises à jour simultanément ou ne pas l’être du tout.

• Résumé du quatrième commentaire :

  • C’est un excellent article qui offre une vue d’ensemble de nombreux concepts liés à la construction d’une base de données.
  • Il couvre aussi bien l’extraction de performances sur une seule machine avec SIMD que les algorithmes de consensus.
  • Il mentionne également les méthodes formelles appliquées à la fiabilité des bases de données et aux systèmes distribués.
  • Il existe un article intéressant sur la manière dont l’équipe d’Amazon S3 utilise TLA+ pour la modélisation.

• Résumé du cinquième commentaire :

  • Beaucoup de gens apprennent les bases de données en apprenant SQL, mais comprendre les B-trees permet de mieux saisir les forces et les faiblesses des SGBDR.
  • On essaie d’accélérer la base de données en ajoutant des index, mais cela ne fait souvent que masquer le problème.
  • Certains problèmes se prêtent bien aux B-trees, mais beaucoup d’autres non.
  • SQL n’est qu’une interface de requête vers un système distant fondé sur des B-trees.

• Résumé du sixième commentaire :

  • Beaucoup de développeurs passent à un moment donné par l’étape où ils essaient de construire leur propre petite base de données.
  • Ce processus permet d’apprendre énormément sur ce qui ne fonctionne pas.
  • Construire sa propre base de données aide à mieux apprécier les solutions existantes.
  • Transférer rapidement et de manière fiable des données depuis le disque est une tâche difficile.

• Résumé du septième commentaire :

  • Dans la version Bash, l’atomicité peut être obtenue en copiant le fichier vers un fichier temporaire, en le modifiant, puis en utilisant sync; mv; sync.

• Résumé du huitième commentaire :

  • C’est une conception très élégante, avec une API de documents similaire à MongoDB, une réplication sans leader similaire à Cassandra, et une architecture un cœur par thread similaire à ScyllaDB.
  • Le tout est implémenté en Rust.

• Résumé du neuvième commentaire :

  • Le livre 'Database Internals' est étonnamment excellent et propose une exploration approfondie des mécanismes internes.
  • Le commentaire demande s’il existe d’autres livres similaires.

• Résumé du dixième commentaire :

  • Le livre 'Database Design and Implementation' est lui aussi une excellente lecture, avec de nombreux exemples écrits en Java.
  • Pour la recherche proprement dite, les travaux de Andy (Pavlo), Viktor Leis, Thorsten Grust et Thomas Neumann sont recommandés.