Créer sa propre base de données

• Expose les principes de base d’une base de données clé-valeur et son processus de mise en œuvre
• Part du stockage persistant et de la recherche via le système de fichiers
• Souligne les problèmes d’inefficacité qui surviennent lors de l’ajout, de la modification et de la suppression des données
• Évolue progressivement vers des structures plus efficaces avec des fichiers append-only, des index, le tri, la compression de segments, etc.
• Mène vers des structures modernes comme l’arbre LSM, aujourd’hui utilisées dans des systèmes à grande échelle

---

Introduction : le point de départ pour créer sa propre base de données

En supposant qu’il n’existe pas de concept de base de données, on explore étape par étape comment créer sa propre base de données. On examine le processus de mise en œuvre d’une base de données clé-valeur la plus simple possible.

Idée de base : stockage persistant avec des fichiers

• Le rôle d’une base de données est de conserver les données de manière persistante et de les rechercher efficacement ensuite.
• La méthode la plus courante est d’enregistrer chaque couple clé-valeur dans un fichier via un système de fichiers.
• Lors de l’ajout de données, on écrit le contenu dans un fichier sous une forme du type $ db set 1 "Lorem ipsum".
• Pour rechercher des données, on parcourt séquentiellement toutes les paires clé-valeur du fichier afin de trouver la clé souhaitée.
• Pour une mise à jour, on remplace directement la valeur associée à la clé dans le fichier ; pour une suppression, on supprime l’enregistrement correspondant.

Problème : mise à jour (in-place) inefficace

• Modifier ou supprimer des données directement dans le fichier est très inefficace.
• Un fichier n’étant qu’un flux d’octets, changer une donnée au milieu impose le déplacement de toutes les données suivantes.
• Par exemple, lorsqu’un enregistrement est remplacé par une nouvelle valeur de longueur différente, on doit décaler tout le contenu qui suit.
• Plus le volume de données augmente, plus l’impact sur la vitesse et l’efficacité devient important.

Amélioration 1 : structure de fichier append-only

• On applique une approche où, lors des mises à jour et suppressions, les données existantes ne sont pas modifiées : on ajoute uniquement de nouveaux enregistrements à la fin du fichier.
• À chaque changement, un nouvel enregistrement est ajouté, et l’algorithme est adapté pour rechercher la dernière valeur de la clé.
• Les suppressions sont marquées avec une valeur spéciale de type « tombstone » (par ex. null).
• Avantage : écritures efficaces sans déplacer les données déjà présentes.
• Inconvénient : le fichier grossit progressivement avec les doublons et les marqueurs de suppression.
• La recherche reste lente car un parcours complet peut encore être nécessaire.

Amélioration 2 : gestion de la taille des fichiers et compaction

• Pour limiter la croissance infinie du fichier, lorsque sa taille dépasse un seuil, on bascule vers un nouveau fichier (segment), puis on enlève les données inutiles (doublons / supprimées) du fichier précédent pour réduire la taille : c’est la compaction.
• Lors de la compaction, on ne conserve que les données réellement nécessaires, en supprimant les anciennes versions périmées et les marqueurs de suppression seuls.
• Cela évolue vers une gestion à base de plusieurs fichiers de segment, avec un mécanisme de fusion (merge) au besoin.

Amélioration 3 : recherche plus rapide grâce à un index

• On construit un index en mémoire (table de hachage) contenant pour chaque clé l’offset de position dans le fichier, permettant une recherche plus rapide.
• En phase de lecture, on consulte d’abord l’index, puis on lit directement la position correspondante dans le fichier.
• Trade-off : la recherche est rapide, mais l’index en mémoire peut atteindre ses limites quand le nombre de clés est élevé.
• La gestion de l’index peut aussi dégrader légèrement les performances en écriture.

Amélioration 4 : tri (Sorted String Tables) et index creux (sparse index)

• En stockant toujours les données triées par clé, on obtient une meilleure efficacité pour les requêtes de plage (range query).
• Grâce au tri, il n’est pas nécessaire de stocker un index pour chaque clé : un index creux suffit.
• En ajustant la densité de l’index, on peut arbitrer entre consommation mémoire et performance de recherche.

Mise en œuvre : combinaison mémoire/disque et durabilité

• Les nouvelles données sont d’abord enregistrées dans une liste en mémoire triée, et en parallèle dans un fichier append-only qui sert de sauvegarde.
• Quand la liste en mémoire grossit, on la trie et on l’écrit sur disque dans un fichier (SST), puis on met l’index à jour.
• Lors d’une consultation, on vérifie d’abord la mémoire ; si la donnée n’y est pas, on la recherche sur disque via l’index.
• Les fichiers disque sont gérés en mode immutable : les mises à jour et suppressions sont toujours traitées par ajout de nouvelles données.
• Les données redondantes ou supprimées sont régulièrement compactées pour contrôler la taille des fichiers.

L’apparition du LSM Tree (Log-Structured Merge Tree)

• Les structures précédentes sont couramment connues sous le nom de LSM Tree.
• C’est une architecture combinant memtable (mémoire) et SST (sorted string table) sur disque, adaptée aux opérations rapides et aux environnements à grande échelle.
• Elle constitue la structure centrale de grandes bases de données clé-valeur comme LevelDB, Amazon DynamoDB, etc.
• Il existe certes des limites et des différences avec d’autres structures (par ex. les bases relationnelles basées sur les B-Tree), mais elle a montré d’excellentes performances en montée en charge.

Conclusion

• Partant d’un stockage simple basé sur fichiers, puis via append-only, index, tri, compaction par segments et combinaison mémoire/disque, on aboutit à des conceptions de base de données plus performantes.
• Comprendre le fonctionnement interne d’une base de données et ses choix structurels devient possible en suivant son implémentation concrètement.
• L’architecture LSM Tree joue un rôle structurant dans les systèmes modernes à grande échelle.
• Reste ouverte l’exploration d’autres approches, comme la structure B-Tree des bases relationnelles.

[GN⁺]

Commentaires Hacker News

• J’aime beaucoup le design et les exemples de cet article : la structure facile à lire m’a fait une bonne impression. Cet exercice en lui-même est aussi une expérience très amusante. En partant de rien, on peut vraiment vérifier jusqu’où va sa propre connaissance.
  • J’étais moi aussi, par le passé, tombé dans l’attitude précipitée du genre « ne crée pas ta propre base de données, n’utilise pas non plus de base KV, utilise simplement SQL ». Cette idée a d’ailleurs été battue en brèche quand j’ai essayé de concevoir une base de données moi-même, ou de me limiter au KV en fuyant SQL, et que j’ai fini par recréer SQL de manière assez bancale. La valeur d’apprendre en pratiquant directement est indéniable.
  • Un seul regret est qu’il utilise du lorem ipsum comme exemple, ce qui permet de le survoler sans vraiment se concentrer. Des exemples avec des données réelles auraient attiré bien plus l’attention. Pour le reste, c’est vraiment un super article.
• Quand il est écrit que « l’arbre LSM est la structure de données utilisée par défaut dans DynamoDB et autres, et qu’il offre d’excellentes performances à grande échelle… avec jusqu’à 80 millions de requêtes par seconde », il y a une légère ambiguïté. Le LSM s’emploie au niveau du moteur de stockage d’un nœud, mais l’article n’explique pas comment le système distribué entier pourrait évoluer à 80 M RPS. De mémoire, le papier Dynamo utilisait BerkeleyDB (B-tree ou LSM), puis a basculé vers un moteur entièrement basé sur LSM dans une publication de 2012.
• J’ai cliqué sur quelques articles de la liste, et je dois avouer que la conception et les animations sont vraiment magnifiques.
• Il semble que le premier exemple de la section « Sorting in Practice » soit cassé. Le texte dit qu’après tri en mémoire, les données doivent être écrites sur disque dans l’ordre trié, mais dans l’exemple réel, cet ordre est perdu à l’écriture disque. C’est pareil pour l’exemple de flush (2e) dans la partie recap : le texte indique que le fichier est écrit dans l’ordre trié.
• C’était un article intéressant. Je suis en train de modéliser l’activité des développeurs comme un système clé-valeur orienté séries temporelles, avec chaque développeur en clé et les commits en valeur. Je me heurte aux mêmes problèmes : le journal grossit vite, l’index devient lourd, les requêtes de plage deviennent lentes. Je me demande comment décider quelles données éliminer lors de la compaction des segments, l’équilibre entre fraîcheur et durée de rétention paraît difficile à calibrer.
• Cela fait 4 semaines que je me concentre sur l’implémentation d’un triple store. J’ai senti qu’un peu plus tôt, cet article m’aurait donné quelques idées pour comprendre plus vite.
• Si l’auteur voit ce commentaire, je me demande s’il pourrait ajouter un flux RSS au site, afin de pouvoir l’ajouter à Feedly pour le lire.
• Si vous voulez créer votre propre base de données, je recommande vivement ce livre en ligne gratuit.
  • Je me souviens d’un article qui expliquait les concepts de base d’une base de données avec des exemples Bash (par ex. « Créer une base de données avec Bash ») présenté ici, mais je n’arrive pas à le retrouver. Si quelqu’un connaît ce lien, je serais ravi qu’il le partage.
• Le trafic est déjà tellement élevé que le site est inaccessible.
  • Il aura besoin d’une base de données plus rapide.
• J’aime vraiment cette façon d’expliquer patiemment à partir des premiers principes. En suivant l’article, on comprend clairement à chaque étape quel problème surgit et quels problèmes supplémentaires apparaissent en le résolvant, ce qui permet d’aboutir à une solution vraiment satisfaisante.