Les fondamentaux des bases de données

• En partant d’un simple magasin clé-valeur en Bash, l’article montre progressivement pourquoi une vraie base de données doit traiter séparément la durabilité, l’atomicité, l’isolation et les performances comme des problèmes de conception
• fsync/fdatasync, flock et le WAL sont des outils de base pour protéger les données en cas de panne et de concurrence, mais plus le niveau de garantie augmente, plus le coût en performances est élevé
• Les moteurs de stockage utilisent des structures comme les B-tree et les LSM tree pour réduire les E/S disque et les coûts de recherche, avec en contrepartie des opérations de maintenance comme le vacuum ou la compaction
• Les bases de données distribuées gagnent en disponibilité et en montée en charge horizontale, mais au prix de la complexité des systèmes distribués : théorème CAP, partitionnement réseau, arbitrage de la cohérence et résolution de conflits
• Lors du choix ou de l’implémentation d’une base de données, il faut adapter les garanties ACID, le niveau d’isolation, la structure de stockage, le mode de réplication et les exigences de cohérence à la charge de travail

---

Les problèmes fondamentaux des bases de données révélés par bashdb

• bashdb est un magasin clé-valeur minimaliste construit avec deux fonctions Bash
  • db_set ajoute au fichier des entrées au format key,value
  • db_get lit la dernière valeur en combinant grep, sed et tail
• C’est simple pour l’apprentissage, mais cette seule implémentation met déjà en évidence les problèmes qu’une base de données de production doit résoudre
  • Durability : si la machine plante après le succès de db_set, les données non flushées sur le disque peuvent être perdues
  • Atomicity : si un crash survient pendant l’écriture, les données peuvent n’être enregistrées qu’en partie et être corrompues
  • Isolation : si une lecture et une écriture accèdent en même temps au même élément, la lecture peut ne voir qu’une partie des données
  • Performance : db_get parcourt tout le fichier ligne par ligne, donc sa complexité est en O(n)

ACID et tentatives d’amélioration de bashdb

• ACID est un acronyme qui regroupe les propriétés que de nombreuses bases de données cherchent à garantir
  • Atomicity : en cas de panne pendant une écriture, la transaction entière est annulée ou restaurée afin de ne pas laisser d’état partiellement écrit
  • Consistency : une transaction invalide ne doit pas corrompre la base de données
  • Isolation : les accès concurrents aux mêmes données ne doivent pas provoquer de race condition
  • Durability : une écriture validée doit subsister même après une coupure de courant ou un incident similaire
• Toutes les transactions de base de données ne doivent pas nécessairement garantir ACID, et certains cas d’usage peuvent réduire ces garanties pour gagner en performances

• Durabilité et fsync

  • L’appel système write écrit un tampon dans un fichier, mais cela ne signifie pas que les données sont immédiatement enregistrées sur un support non volatil
  • Le noyau peut stocker ce tampon comme dirty page dans le page cache, puis le flusher plus tard sur le disque
  • Un périphérique de disque ou un système RAID peut aussi disposer de son propre write cache
  • fsync et fdatasync sont des appels système destinés à flusher les dirty pages vers un support de stockage permanent
  • fdatasync flush le raw buffer transmis par write
  • fsync flush non seulement les données, mais aussi les métadonnées du fichier comme mtime
  • Ajouter sync -d database après db_set peut améliorer la durabilité avec un comportement proche de fdatasync, mais en général sync est plus lent que l’écriture elle-même, ce qui dégrade les performances
  • Le succès de fsync() signifie que « toutes les écritures depuis le dernier fsync ont atteint le disque », et non pas seulement « les écritures effectuées après le dernier fsync réussi »
  • PostgreSQL a rencontré ce problème en 2018 et a modifié son comportement pour passer en panic lors d’un échec de fsync au lieu de réessayer
  • Cet incident est connu sous le nom de fsyncgate, avec en ressource associée l’article fsync failures
  • MongoDB ne synchronise par défaut les écritures que toutes les 100 ms, et n’est donc pas 100 % durable

• Isolation et flock

  • Dans bashdb, la manière la plus simple d’obtenir une isolation entre plusieurs processus consiste à verrouiller le fichier de stockage avant lecture ou écriture
  • Sous Linux, flock verrouille un fichier, et l’option -s permet un shared lock afin que plusieurs lecteurs puissent lire en même temps
  • La version améliorée de bashdb utilise un exclusive lock pour les écritures et un shared lock pour les lectures
  • Son inconvénient est de verrouiller toute la base de données à chaque écriture
  • Il est difficile de garantir simplement l’atomicité en Bash seul ; on pourrait envisager mv -T ou rename, mais cette partie n’est pas menée à terme
  • bashdb ne résout toujours pas le problème des recherches en O(n)

Rôle du moteur de stockage et goulets d’étranglement

• Le moteur de stockage fournit une abstraction pour lire et écrire des données sur un stockage persistant, avec pour objectif principal un débit élevé et une faible latence
• La plus grande contrainte vient des écarts de vitesse du disque lui-même
  • Dans le tableau d’exemple des latences, un accès au cache L1 est d’environ 0.5ns, une lecture aléatoire de 4 KB sur SSD de 150,000ns, et un seek disque de 10,000,000ns
  • Si l’on assimile un accès au cache L1 à un battement de cœur d’environ 0,5 seconde, une lecture séquentielle de 1 MB sur SSD correspond à environ 12 jours, et une lecture séquentielle de 1 MB sur disque à environ 8 mois
• C’est pourquoi la conception des moteurs de stockage a évolué pour réduire autant que possible les E/S disque et les seeks disque
• Les éléments habituels de conception d’un moteur de stockage sont les suivants
  • la structure de données de base utilisée pour stocker les éléments sur disque
  • les transactions ACID
  • un cache pour réduire les lectures disque
  • une couche d’API telle que SQL, document ou graphe
• Les structures de données des moteurs de stockage se divisent grosso modo entre structures modifiables et structures immuables
  • Une structure modifiable peut écraser plus tard les données déjà écrites dans un fichier
  • Une structure immuable ne fait ensuite que relire les données écrites dans le fichier

B-tree modifiables

• Pour conserver de bonnes performances à mesure que les données augmentent, il faut pouvoir trouver un élément en temps au plus logarithmique, et non par recherche linéaire comme avec bashdb
• Un BST permet des recherches en O(log n), mais si les nœuds sont très éloignés les uns des autres sur le disque, la traversée peut provoquer de nombreux seeks disque
• Un B-tree est une généralisation du BST dans laquelle un nœud peut avoir plus de deux enfants, et il exploite la localité spatiale
  • On lit généralement une page disque de 4 KB ou 8 KB, puis on compare séquentiellement plusieurs nœuds qu’elle contient en mémoire et dans le cache CPU
  • Comme l’accès à la mémoire et au cache CPU est de plusieurs ordres de grandeur plus rapide que l’accès disque, il est essentiel d’exploiter au maximum les octets déjà lus depuis le disque
• Les accès mémoire séquentiels peuvent être très efficaces grâce au SIMD, à l’instruction pipelining et au prefetching
• Le B+ tree ne stocke les valeurs que dans les leaf nodes et ne conserve que les clés dans les autres nœuds, ce qui permet de comparer davantage de clés dans une seule page disque

• Récupération d’espace et vacuum

  • Les B-tree doivent récupérer l’espace libre créé par la fragmentation des données pour optimiser l’utilisation de l’espace
  • Lorsqu’une mise à jour vers une valeur plus grande risque d’écraser les données du nœud suivant, l’élément est déplacé ailleurs et laisse un trou dans la page d’origine
  • Lorsqu’une mise à jour vers une valeur plus petite intervient, un trou peut rester en fin de page
  • Une suppression crée un trou à l’emplacement de la valeur supprimée
  • Ce processus de récupération d’espace et de réécriture des pages peut être appelé vacuum, compaction, défragmentation de page ou maintenance
  • Il est généralement exécuté en arrière-plan pour éviter des pics de latence sur les requêtes utilisateur
  • PostgreSQL permet de configurer l’auto vacuum daemon
  • Les B-tree sont couramment utilisés comme structure de base des index, par exemple l’index par défaut de PostgreSQL, et DynamoDB a déjà été surnommé pour plaisanter un « distributed B-tree »

LSM tree immuable

• Le LSM tree est une structure de données append-only conçue à partir du constat que les seeks disque sont coûteux.
• Si l’on ajoute les données uniquement à la fin du fichier, la tête de lecture/écriture du disque a moins besoin de se déplacer jusqu’au prochain emplacement d’écriture, ce qui est avantageux pour les workloads riches en écritures.
• Le Log Structured Merge tree, abrégé en LSM tree, est utilisé dans les moteurs de stockage de bases de données modernes comme RocksDB, Cassandra et ScyllaDB.
• Le fonctionnement de base est le suivant :
  • les écritures sont mises en tampon dans une structure de données triable en mémoire ;
  • parmi les exemples figurent AVL tree, Red Black tree et Skip List ;
  • lorsqu’une certaine capacité est atteinte, elles sont flushées vers un fichier trié appelé Sorted String Table, ou SSTable.
• Une SSTable stocke les données triées, ce qui permet de réduire les E/S disque grâce à la binary search et à un sparse index.
• Pour garantir la durabilité, les opérations écrites en mémoire sont enregistrées dans un Write-Ahead Log, ou WAL.
  • Au démarrage du programme, le WAL est relu pour restaurer l’état avant l’arrêt ou le crash.
• Les suppressions sont elles aussi appendées comme des écritures normales, en stockant un tombstone à la place de la valeur.
  • Le tombstone est supprimé lors du processus de compaction.

• Lecture et compaction d’un LSM tree

  • La lecture dans un LSM tree commence par la recherche dans la structure de données en mémoire ; si la clé n’y est pas, les SSTable sur disque sont parcourues de la plus récente à la plus ancienne.
  • Plus le volume d’écritures augmente, plus le nombre de SSTable à vérifier augmente.
  • Même si chaque fichier est trié, parcourir de nombreux petits fichiers peut être plus lent que consulter un seul gros fichier.
  • L’inégalité de comparaison est log(num_files * table_size) < num_files * log(table_size).
  • La compaction est une tâche de fond qui fusionne plusieurs petites SSTable en une grande SSTable et supprime les tombstones.
  • RocksDB implémente la Leveled Compaction.
  • Les SSTable nouvellement flushées sont placées au niveau 0.
  • Lorsqu’un nombre configuré de fichiers s’accumule dans un niveau, une compaction est effectuée puis le nouveau fichier est promu au niveau suivant.
  • La suppression des tombstones doit être gérée avec prudence.
  • Un problème de data resurrection peut survenir, où des éléments supprimés réapparaissent lors d’une compaction avec des fichiers plus anciens.
  • RocksDB conserve les tombstones jusqu’à la compaction qui les promeut vers le dernier niveau.
  • Un exemple réel en Rust est disponible dans le code LSM tree de dbeel.

• Bloom filter

  • Un Bloom filter est une structure de données probabiliste de type ensemble qui permet de vérifier efficacement qu’un élément n’appartient pas à un ensemble.
  • Le résultat d’une requête prend deux formes :
    • false : l’élément n’est certainement pas dans l’ensemble ;
    • true : l’élément est peut-être dans l’ensemble.
  • Un Bloom filter mappe les résultats de plusieurs hash functions sur des positions de bits dans un bitmap, puis les définit à 1.
  • Sa complexité spatiale est présentée comme O(log n), contrairement au O(n) d’un ensemble classique.
  • On peut ajuster la « probabilité de pouvoir affirmer qu’un élément est absent » en allouant plus de mémoire au bitmap et en augmentant le nombre de hash functions ; il existe aussi un calculateur.
  • Les LSM tree stockent un Bloom filter pour chaque SSTable, ce qui permet d’ignorer la recherche dans les SSTable dont on a vérifié qu’elles ne contiennent pas une clé donnée.

WAL et garanties transactionnelles

• Le WAL est une méthode qui consiste à enregistrer toutes les opérations transactionnelles dans un fichier spécial afin de survivre à un crash brutal.
• Au démarrage du processus de base de données, le fichier WAL est relu pour reconstruire l’état des données.
  • Les transactions sans commit log sont ignorées, ce qui apporte l’atomicité.
• Si les données d’une requête d’écriture sont enregistrées et flushées dans le WAL avant de répondre à l’utilisateur, elles seront forcément relues au démarrage, ce qui garantit la durabilité.
• Le WAL peut être vu comme une forme d’event sourcing appliquée aux événements transactionnels.

Niveaux d’isolation et contrôle de concurrence

• Il existe trois grandes approches pour atteindre l’isolation :
  • verrouillage pessimiste : empêche l’accès aux données en cours d’écriture ;
  • verrouillage optimiste : modifie une copie des données, puis ne commit que si l’original n’a pas changé pendant la transaction, sinon effectue un retry ;
  • MVCC : au lieu d’écraser les données, crée une nouvelle version afin que chaque utilisateur voie un snapshot à un instant donné.
• Toutes les applications n’ont pas besoin d’une isolation complète, c’est-à-dire d’une serializable isolation.
• ANSI/ISO SQL 92 classe en trois catégories les effets pouvant se produire lorsqu’une autre transaction modifie les mêmes données pendant une transaction.
  • Dirty read : lecture d’une mise à jour d’une autre transaction qui n’a pas encore été commitée ;
  • Non-repeatable read : entre deux lectures de la même row, une autre transaction commit et la valeur change ;
  • Phantom read : entre deux lectures d’un ensemble de rows correspondant à la même condition, des rows sont ajoutées ou supprimées.
• Les niveaux d’isolation ANSI/SQL 92, du plus élevé au plus faible, sont les suivants :
  • Serializable : ne lit que des données commitées et évite les phantom reads, y compris pour les écritures multi-rows basées sur des plages ;
  • Repeatable reads : les phantom reads sont autorisés ;
  • Read committed : les non-repeatable reads sont autorisés ;
  • Read uncommitted : les dirty reads sont autorisés.
• Des niveaux d’isolation plus élevés impliquent généralement un sacrifice en performances.
• Les niveaux d’isolation ANSI/SQL 92 sont critiqués comme incomplets.
  • De nombreuses implémentations MVCC fournissent non pas une serializable isolation, mais une snapshot isolation.
  • HyPer est recommandé comme algorithme MVCC serializable rapide.

Pourquoi les systèmes distribués sont nécessaires, et CAP

• Les systèmes distribués ajoutent beaucoup de complexité et doivent donc être évités lorsqu’une solution non distribuée suffit.
• Il y a généralement deux raisons de répartir les données sur plusieurs machines :
  • Availability : même si la machine de base de données crash ou si la connexion avec l’utilisateur est interrompue, les requêtes peuvent être envoyées à une autre machine ;
  • Horizontal Scaling : au lieu du vertical scaling consistant à passer à une machine unique plus puissante, plusieurs machines reliées par réseau fonctionnent comme une seule.
• Les systèmes distribués introduisent une complexité opérationnelle et des problèmes de partition réseau.
• Le théorème CAP affirme qu’un système ne peut garantir que deux des trois propriétés suivantes :
  • Consistency : une lecture obtient l’écriture la plus récente ;
  • Availability : toutes les requêtes réussissent indépendamment des pannes ;
  • Partition Tolerance : le système continue à fonctionner même s’il y a perte ou retard de messages entre les nœuds.
• Une base de données sur une seule machine n’a pas de partition réseau et reste cohérente, mais en cas de panne de la machine, les nouvelles requêtes échouent, ce qui viole l’availability.
• Lorsque deux machines disposant de CPU, mémoire et disque séparés sont reliées par câble, le choix diverge en situation de panne.
  • Annuler les requêtes sacrifie l’availability mais préserve la consistency.
  • Continuer à traiter les requêtes uniquement sur la machine encore en fonctionnement sacrifie la consistency mais préserve l’availability.
• Les systèmes qui sacrifient la consistency pour se resynchroniser plus tard sont dits eventually consistent.
• Les partitions réseau compliquent aussi les JOIN efficaces, car il faut rassembler des données dispersées dans le cluster ; le camp NoSQL recommande donc la denormalization pour atténuer ce problème.

Réplication et le cas d’Amazon Dynamo

• Le papier original sur Dynamo d’Amazon est présenté comme un cas où la disponibilité était jugée plus importante que la cohérence pour le panier d’achat sur amazon.com
  • Si un utilisateur voit deux fois le même article dans son panier, il peut simplement en supprimer un
  • Cela a été considéré comme préférable à une situation où l’achat lui-même devient impossible
• Pour obtenir de la disponibilité, il ne suffit pas que plusieurs nœuds se partagent les données : il faut aussi au moins une copie de chaque élément
• Un nœud qui stocke une copie d’un élément est une replica, et le processus de copie est la replication
• Augmenter le nombre de replicas améliore la disponibilité, mais demande davantage de ressources pour stocker ces copies
• Les copies de données peuvent aussi être découpées via l’erasure coding et réparties sur plusieurs nœuds au lieu d’être stockées intégralement, avec des caractéristiques de latence décrites dans cet article sur l’erasure coding

Consistent Hashing et placement des données

• Lorsqu’il y a plusieurs nœuds, il faut un mécanisme de load balancing ou de partitionnement des données pour décider quel nœud traite une requête de stockage
• Une méthode simple consiste à hasher la clé primaire puis à faire un modulo par le nombre de nœuds
  • Si un nœud est ajouté ou supprimé, len(nodes) change et une même clé pointe alors vers un autre nœud
  • Dans ce cas, il faut migrer presque tous les éléments, ce qui coûte cher
• Le Consistent Hashing place les nœuds sur un anneau plutôt que dans un tableau, afin de réduire le nombre d’éléments à déplacer quand des nœuds sont ajoutés ou retirés
  • Il est utilisé dans des bases de données comme Dynamo et Cassandra
• En consistent hashing, le hash du nom du nœud est placé sur l’anneau, et le nœud rencontré après le hash de la clé de la requête en devient le propriétaire
• Le choix des replicas peut se faire en parcourant l’anneau dans le sens antihoraire et en stockant les copies sur les nœuds suivants
  • Si le nœud propriétaire tombe en panne, un nœud replica peut traiter la requête pour maintenir la disponibilité
  • Cette approche est appelée Leaderless Replication et est utilisée dans des bases de données de style Dynamo comme Cassandra
• Le nombre de clés à déplacer lors de l’ajout d’un nœud est en moyenne de num_keys / num_nodes
• Un virtual node consiste à placer plusieurs fois un même nœud physique sur l’anneau pour réduire la probabilité que certains nœuds possèdent beaucoup plus d’éléments que d’autres
  • L’exemple consiste à ajouter un suffixe d’index au nom du nœud, comme "half-0", "half-1"
• Il existe d’autres méthodes pour choisir un leader node et des replica nodes, comme la leader election, mais elles ne sont pas abordées ici

Leaderless Replication et ajustement de la cohérence

• Une configuration leaderless obtient une forte disponibilité au prix de la cohérence
• Si le nœud propriétaire est down au moment d’une requête d’écriture, l’écriture est faite sur les replicas, et le nœud propriétaire peut ensuite renvoyer des données obsolètes lors d’une requête de lecture après son retour
• Lorsqu’une requête donnée exige de la cohérence, la requête de lecture peut être envoyée en parallèle à plusieurs replicas et au nœud propriétaire, puis le client choisit la donnée la plus récente
• Les requêtes d’écriture sont généralement envoyées en parallèle à tous les replicas, mais on n’attend l’acknowledgement que d’une partie des nœuds
• Pour ajuster la cohérence au niveau de la requête, on vérifie R + W > N/2 + 1
  • N : nombre de nœuds qui possèdent une copie des données
  • W : nombre de nœuds devant envoyer un acknowledgement pour que l’écriture réussisse
  • R : nombre de nœuds devant répondre pour que la lecture réussisse
• Une requête adressée à une majorité de nœuds, quand W ou R vaut N/2 + 1, est appelée un quorum

• Résolution des conflits

  • Le processus consistant à choisir l’écriture la plus récente est la Conflict Resolution
  • Comparer simplement les timestamps n’est pas très fiable dans un système distribué
  • Chaque machine possède sa propre hardware clock, et une horloge n’est jamais parfaitement exacte, ce qui entraîne du drift
  • NTP récupère l’heure depuis une source plus précise, mais comme la requête elle-même traverse le réseau, il est impossible de connaître exactement le temps pris avant la réponse
  • Cassandra utilise des timestamps, et la documentation correspondante est disponible ici : Cassandra data versioning
  • Google Spanner a obtenu des garanties de cohérence basées sur l’horloge grâce à un matériel temporel spécialisé de très haute précision et à une API exposant une plage d’incertitude sur les timestamps ; le papier associé est le papier sur Spanner
  • Les systèmes de type Dynamo réduisent certains conflits grâce aux Version Vectors
  • À chaque version d’un élément est associé un couple (node, counter) pour retrouver les relations de causalité entre versions
  • Cela permet d’identifier les versions qui sont clairement plus récentes et d’éliminer certaines anciennes valeurs
  • Pour aller plus loin, voir Dotted Version Vectors
  • Comme dans Riak KV, on peut aussi renvoyer toutes les valeurs en conflit à l’application, qui les résout en s’appuyant sur sa connaissance des données
  • Dans les systèmes eventually consistent, les différentes techniques visant à réduire les conflits sont généralement regroupées sous le terme Anti Entropy

Techniques d’Anti Entropy

• Read Repair

  • Le client choisit la valeur la plus récente parmi les résultats de lecture renvoyés par plusieurs nœuds, puis la renvoie aux nœuds qui ne la stockent pas encore afin de les réparer

• Hinted Handoff

  • Si une requête d’écriture n’atteint pas le nœud cible, elle est stockée comme hint sur un autre nœud
  • Lorsque le nœud cible redevient available, le hint stocké lui est transmis
  • Dans les écritures en quorum, cette méthode est aussi appelée Sloppy Quorum et améliore encore la disponibilité des requêtes en quorum

• Merkle Trees

  • Le read repair ne corrige que les données consultées, si bien qu’un grand volume de données peut rester longtemps dans un état incohérent
  • Faire une synchronisation entre nœuds pour retrouver toutes les différences coûte O(n) quand le volume de données est important
  • Un Merkle tree est une structure hiérarchique où les hash de plages de données sont stockés dans les feuilles, et où chaque parent stocke un hash combinant ceux de ses enfants
  • Si le hash racine est identique, les données des deux nœuds sont identiques ; sinon, on compare récursivement les hash inférieurs pour trouver les données divergentes, ce qui permet de rendre la synchronisation plus rapide en O(log n)

• Gossip Dissemination

  • C’est une méthode simple et fiable pour propager des événements à l’ensemble du cluster
  • Un nœud envoie un message à un nombre configuré de nœuds aléatoires, appelé fanout, et chaque nœud qui le reçoit le renvoie ensuite à N nœuds aléatoires
  • Lorsqu’un même message de gossip a été vu un certain nombre de fois configuré, il n’est plus broadcast
  • Un simulateur permettant de visualiser la convergence des données est proposé en lien
  • Les messages de gossip sont généralement transmis en UDP

Domaines à approfondir

• Les bases de données couvrent bien d’autres sujets que ceux abordés ici
  • l’utilisation de O_DIRECT sous Linux et l’implémentation d’un page cache maison
  • la failure detection dans les systèmes distribués
  • les algorithmes de consensus comme Raft
  • les distributed transactions
  • la leader election
• Lorsqu’on choisit ou qu’on implémente une base de données, il faut aussi examiner comment le moteur de stockage, l’ACID, les niveaux d’isolation, la réplication distribuée et les mécanismes de résolution de conflits correspondent aux besoins réels

[GN⁺]

Commentaires Hacker News

• Il y a un bug dans la méthode compact : les tombstones ne devraient être ignorées que lors de la compaction du dernier niveau, c’est-à-dire le plus grand, et ne devraient pas être supprimées entre tous les niveaux
  Sinon, les tombstones des niveaux supérieurs disparaissent pendant la compaction, ce qui fait réapparaître des entrées qui se trouvaient dans les niveaux inférieurs
  Dans les bases de données fondées sur des LSM, le fait que les enregistrements de suppression/tombstones restent longtemps est l’une de leurs caractéristiques, et certaines bases de données comme RocksDB ajoutent des optimisations pour l’éviter

  • Exact, l’article l’a volontairement omis par souci de concision, et dbeel le prend bien en charge
  • Je me demande quelles optimisations fait RocksDB
    Je connais les fonctionnalités côté suppressions de plages, mais je ne me souviens pas avoir beaucoup lu sur la suppression d’une clé unique

• Beaucoup de gens apprennent les bases de données en apprenant SQL, mais je recommande de suivre ce genre de cours et de les aborder en comprenant les B-trees
  La plupart des avantages et inconvénients des RDBMS se comprennent en connaissant les B-trees et leur effet sur l’insertion, la recherche et le tri des clés
  Beaucoup de gens essaient d’accélérer une base de données en ajoutant des index, mais au final cela revient seulement à empiler un autre arbre sur l’arbre, ce qui masque le problème de fond
  Certains problèmes se prêtent bien aux B-trees, mais beaucoup d’autres non
  SQL n’est qu’une interface de requête pour un système distant de B-trees

  • C’est beaucoup trop réducteur
    Les B-trees ne sont pas la seule stratégie d’indexation, et il est aussi bien connu que les index sont un mécanisme qui améliore les performances en lecture au prix des performances en écriture
    C’est parce qu’en général les bases de données traitent bien plus de lectures que d’écritures
    Je me demande quel problème exact est masqué par « empiler un autre arbre sur l’arbre », et comment on le résoudrait sans toucher aux index
    Pour des tables d’une taille raisonnable, les index sont pratiquement indispensables
  • Je suis d’accord avec ça
    Il faut apprendre des choses comme les B-trees et les index de hachage, les couches d’E/S et les modèles de processus
    Aujourd’hui, les stratégies générales des bases de données orientées colonnes valent aussi la peine d’être apprises : matérialisation tardive des tuples, exécution différée, scans linéaires et recherche binaire, pipelining des instructions, etc.
    Une fois familiarisé avec tout cela, on comprend qu’en pratique, il arrive qu’un simple fichier plat ou une base de données embarquée comme RocksDB suffise, plutôt qu’un SGBD
  • Cela peut être un B-tree, un LSM-tree, un trie ou une autre structure d’index adaptée à la situation
    Bien sûr, il peut aussi y avoir des index couvrants
  • Ce serait bien d’expliquer par un exemple concret la partie disant que « cela masque le problème parce que c’est empiler un autre arbre sur l’arbre »

• Au conseil « évitez les systèmes distribués si une solution non distribuée suffit », j’ai envie de répondre l’inverse
  Tout système de production non trivial est un système distribué
  Au minimum, si la base de données est un ensemble répliqué, c’est déjà un système distribué ; ne pas apprendre les systèmes distribués, c’est donc prendre un risque
  https://jepsen.io/ et https://raft.github.io/ valent le détour

  • Certaines parties d’un système ne peuvent pas éviter les appels réseau ou les aspects distribués
    Cela ne veut pas dire pour autant qu’on peut les introduire partout sans problème ; le faire augmente considérablement la complexité au-delà du nécessaire
  • Il faut d’abord définir ce qu’est un « système de production non trivial »
    Formulé ainsi, cela ne réfute pas le conseil d’éviter la complexité inutile. Le point essentiel n’est pas de savoir si c’est techniquement distribué, mais si c’est réellement nécessaire
    Apprendre les systèmes distribués et les utiliser sont deux choses différentes
    Ce qui compte, c’est de savoir si, après les avoir appris, on est capable de se limiter à les appliquer seulement là où ils conviennent
    Aujourd’hui, on voit souvent beaucoup d’efforts investis pour déplacer des systèmes simples qui fonctionnent bien vers un modèle distribué plus fort, comme si cela n’avait quasiment aucun coût
    Pourtant, au vu du problème à résoudre et de l’échelle, il est évident que, dans certains cas, une seule instance Postgres et un monolithe auraient suffi
    Le conseil du texte original semble aller dans ce sens
  • C’est peut-être vrai dans la bulle HN, mais du point de vue d’une entreprise moyenne, pas du tout
    En tout cas, ce n’est pas nécessairement le cas
  • Les systèmes distribués/redondants ne sont pas des sauvegardes
    Je continuerais à conseiller de choisir des solutions simples
    Les systèmes échouent souvent à stocker, sauvegarder et restaurer correctement leur état persistant même avec un « stockage trivial et simple »
    Restaurer l’état d’un stockage distribué en situation de reprise après sinistre est encore plus difficile
    On peut d’abord se doter d’une solution de sauvegarde qui fonctionne, puis adopter une solution distribuée
  • Il est difficile d’appeler le basculement de réplicas un système distribué
    Une configuration maître avec des réplicas en lecture seule n’est pas non plus ce que les gens appellent généralement « distribué », car les écritures ne sont pas distribuées
    En pratique, distribué signifie le plus souvent que les données sont shardées, et c’est précisément ce qu’on veut absolument éviter si ce n’est pas vraiment nécessaire

• J’ai trouvé la lecture intéressante, car cela passe bien en revue plusieurs concepts liés à la création d’une base de données
  Cela va de SIMD, pour tirer des performances d’une seule machine, jusqu’aux algorithmes de consensus
  Puisqu’il est question de bases de données, de fiabilité et de systèmes distribués, les méthodes formelles applicables à ce type de situation et aux implémentations internes de bases de données valent aussi la peine d’être lues
  Il existe un article intéressant où l’équipe S3 modélise avec TLA+
  [0] Use of Formal Methods at Amazon Web Services
  https://lamport.azurewebsites.net/tla/formal-methods-amazon....
  [1] How Amazon Web Services uses formal methods
  https://www.amazon.science/publications/how-amazon-web-servi...

• Il y a la cohérence des bases de données et la cohérence applicative
  Par exemple, on peut garantir l’atomicité, l’isolation et la durabilité au niveau d’une table, mais échouer sur des écritures portant sur plusieurs tables
  La cohérence devient importante dès qu’on commence à traiter des transactions qui mettent à jour plusieurs tables à la fois
  Toutes les tables doivent être mises à jour en même temps, ou aucune ne doit l’être

  • C’est un bon exemple, je vais l’intégrer à l’article

• La conception qui combine « une API documentaire comme MongoDB, une réplication sans leader comme Cassandra et une architecture à un thread par cœur comme ScyllaDB » est vraiment chouette
  Et en plus, tout est en Rust

• L’étape où « les livres ont éveillé ma curiosité et m’ont poussé à créer moi-même une petite base de données » est, je crois, un passage que beaucoup de développeurs traversent au moins une fois.
  Je n’essaierais pas forcément de les en empêcher. En le faisant soi-même, on apprend énormément sur ce qui ne fonctionne pas.
  Si l’on peut y consacrer du temps, c’est une leçon extrêmement précieuse.
  Le fait d’avoir construit moi-même une base de données est ce qui m’a le plus fait respecter les solutions existantes.
  Écrire et lire rapidement des octets sur disque n’est pas la partie difficile.
  Le vrai défi, c’est de faire fonctionner le système de façon fiable pendant des années, tout en prenant en charge des cas d’usage qu’on n’aurait jamais imaginés.

  • Je me demande souvent quelle part de la complexité des DBMS modernes vient de contraintes imposées par des cas d’usage propres à certains domaines métier.
    Quelle efficacité pourrait-on obtenir en concevant un DBMS spécialisé par domaine, en partant du principe que les cas d’usage hors domaine sont interdits et peuvent être ignorés ?
    Par exemple, aujourd’hui, on utilise des bases de données généralistes même pour des jeux de données qui sont, par nature, essentiellement append-only.
    À quoi ressemblerait une base de données où il n’existe tout simplement pas de notion de mise à jour ou de suppression de lignes existantes, mais seulement des insertions et la suppression complète de tables/jeux de données ?
    Une telle base pourrait-elle se passer d’implémenter des transactions MVCC ? Chaque table étant en quelque sorte son propre journal d’écriture anticipée, pourrait-on éviter un journal d’écriture anticipée séparé ? Pourrait-on stocker les données plus efficacement ? Pourrait-on réduire les verrous en rendant l’indexation atomique au niveau des chunks plutôt qu’au niveau de la table entière ?

• L’atomicité de la version Bash ne peut-elle pas être obtenue « simplement » en copiant le fichier vers un fichier temporaire, en le modifiant, puis en utilisant sync; mv; sync ?

  • Pendant la copie, on pourrait aussi éviter les doublons avec un filtre grep inversé.
    On pourrait même garantir le tri au passage, mais faire cela uniquement avec « bash » et les utilitaires de base ne me semble pas très pertinent.
    Pour ce genre d’usage, il existe le CDB de DJB, c’est-à-dire cdbget, cdbmake, etc. :
    https://cr.yp.to/cdb.html
  • Exact, je l’ajouterai plus tard.

• Excellent article.
  Le livre Database Internals a l’air très bon ; existe-t-il d’autres livres similaires qui explorent en profondeur les implémentations internes ?

  • Ce n’est pas un livre, mais je recommande les cours sur les bases de données mis en ligne par le groupe @apavlo de CMU.
    https://www.youtube.com/c/cmudatabasegroup
    Les cours d’introduction et avancés sont tous deux disponibles en ligne, ainsi que des présentations et conférences sur des produits du secteur.
    C’est très utile.
    Pour une ressource plus théorique, plus proche de l’informatique théorique et moins centrée sur l’implémentation physique, le livre « Alice », c’est-à-dire « Foundations of Databases », est excellent.
    Il est très dense et mathématique, mais traite de l’algèbre relationnelle, de Datalog et de la transformation de Datalog en algèbre relationnelle.
    Le livre papier est désormais difficile à trouver, et l’exemplaire d’occasion que j’ai acheté est arrivé avec une reliure abîmée et des pages qui se détachaient, mais l’intégralité du livre est en ligne : http://webdam.inria.fr/Alice/
  • Il existe aussi une ressource connue centrée sur Postgres : https://www.interdb.jp/pg/
  • Pour une vue d’ensemble du même genre, cet article est très bon :
    https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
  • Le livre Database Management Systems de Raghu Ramakrishnan m’a aussi été très utile.
    Cela dit, Database Internals est plus moderne.

• J’aime le fait que l’article ne mystifie pas les « bases de données » et commence par montrer une implémentation triviale en une ligne de Bash.
  C’est une excellente introduction.