- Les structures de données clé-valeur sont un composant central des systèmes fondés sur les données, et leurs performances peuvent varier fortement selon la charge de travail et les conditions matérielles
- La structure physique se divise en agencement des données, métadonnées de recherche et algorithmes de stockage et de récupération ; on les appelle aussi méthodes d’accès (access methods), conteneurs de données ou structures de recherche
- Les charges de travail s’expriment comme une combinaison de requêtes ponctuelles, de requêtes par plage, d’insertions, de suppressions et de modifications ; la capacité et le coût de la mémoire et du stockage persistant font aussi partie des exigences de conception
- Le B+-tree est performant en lecture et pour les requêtes par plage, mais lorsque les insertions et modifications augmentent, la réorganisation des nœuds feuilles devient coûteuse ; le LSM-tree traite de nombreuses insertions par mise en tampon et fusion
- Dans les environnements où le déplacement des données devient un goulot d’étranglement, il faut choisir des structures existantes ou en concevoir de nouvelles en fonction des nouvelles applications, des évolutions matérielles et de la croissance des données
Les problèmes résolus par les structures de données clé-valeur
- Les structures de données clé-valeur sont largement utilisées dans les applications intensives en données et, grâce à la polyvalence du modèle clé-valeur, servent de base à de nombreux systèmes
- Une clé correspond à une seule valeur, mais une même valeur peut être associée à plusieurs clés
- Le sens d’une valeur dépend de l’application
- Il peut s’agir d’un enregistrement dans une base de données relationnelle
- Il peut s’agir d’un Pandas DataFrame
- Il peut s’agir d’un ensemble de champs qu’une application analyse et utilise dans un système NoSQL
- Dans un système traitant des données de réseaux sociaux, cela peut inclure des références à de grands objets comme des images ou des vidéos
Composition physique et champ d’application
- Physiquement, une structure de données clé-valeur se compose de trois éléments
- Les données stockées selon une disposition donnée
- Des métadonnées optionnelles qui facilitent la recherche dans les données
- Des algorithmes qui prennent en charge les opérations de stockage et de recherche
- Les structures de données sont utilisées sous diverses formes dans les systèmes de données, les systèmes d’exploitation, les systèmes de fichiers, les compilateurs et les systèmes réseau
- Les exemples du livre portent surtout sur les systèmes de données à grande échelle et le stockage secondaire, mais les méthodes d’analyse et de conception s’appliquent aussi aux systèmes en mémoire
- Cette analyse est adaptée aux environnements comportant au moins deux niveaux dans la hiérarchie mémoire-stockage
Les charges de travail et les coûts orientent la conception
- Une application ou une charge de travail peut être représentée par une combinaison d’opérations clé-valeur
-
Requête ponctuelle
-
Requête par plage
- Insertion
- Suppression
- Modification
- La capacité nécessaire et le coût de la mémoire et du stockage persistant font aussi partie des exigences applicatives
- Le type de système détermine la structure de données à optimiser
- Les systèmes de fichiers gèrent les métadonnées et le contenu des fichiers avec des structures de données optimisées pour les mises à jour fréquentes
- Les compilateurs gèrent les variables avec une hash map pendant leur cycle de vie et représentent la forme globale du programme sous forme d’abstract syntax tree
- Les équipements réseau ont besoin de structures de données spécialisées pour stocker les tables de routage et y accéder efficacement
-
Les choix opposés du B+-tree et du LSM-tree
- Le B+-tree est souvent utilisé pour équilibrer les coûts de lecture et d’écriture dans les charges de travail comportant peu d’insertions et de mises à jour, mais beaucoup de requêtes ponctuelles et par plage
- Son fanout élevé réduit le nombre d’accès à la mémoire secondaire nécessaires pour aller de la racine aux feuilles, et les niveaux supérieurs sont mis en cache dans des niveaux de mémoire plus rapides
- Il maintient toutes les clés triées dans les nœuds feuilles et relie ces nœuds par une liste chaînée afin de prendre en charge les requêtes par plage
- Lorsque les insertions et mises à jour augmentent, la réorganisation ou la division des nœuds feuilles devient nécessaire, ce qui peut créer un goulot d’étranglement en performance
- Le LSM-tree adopte une autre approche pour les charges de travail comportant beaucoup d’insertions
- Toutes les mises à jour sont placées dans un tampon mémoire commun
- Lorsque le tampon est plein, il est vidé sur disque
- Lorsque les tampons s’accumulent, ils sont fusionnés en collections de données triées plus volumineuses
- Les modifications sont traitées selon une politique out-of-place, et plusieurs paires clé-valeur ayant la même clé peuvent exister dans la structure
- La valeur actuelle d’une clé donnée est celle de la paire clé-valeur insérée le plus récemment
Structures de données adaptatives
- Le document traite non seulement de la conception de structures de données à partir d’une charge de travail anticipée, mais aussi de structures qui se rapprochent progressivement d’une forme idéale pendant l’exécution
- Dans leur conception d’origine, les B+-tree et LSM-tree imposent un ordre de tri dans les nœuds résidant sur disque afin de répondre à toutes les requêtes ponctuelles ou par plage
- Les structures de données adaptatives peuvent partir d’un ou de plusieurs nœuds non triés, puis les trier progressivement lorsque l’occasion se présente
- Le database cracking utilise les schémas d’accès des requêtes entrantes pour réorganiser physiquement les données sous-jacentes de manière continue et incrémentale
- L’objectif est d’améliorer les performances des requêtes futures
Hiérarchie matérielle et mur de la mémoire
- Les progrès matériels créent de nouveaux défis et de nouvelles opportunités pour la conception de structures de données
- Dans la hiérarchie de stockage, les niveaux inférieurs offrent davantage d’espace à moindre prix, mais avec une latence d’accès plus élevée, tandis que les niveaux supérieurs, plus proches du processeur, sont plus rapides, mais plus petits et plus coûteux par octet
- Le niveau qui constitue le goulot d’étranglement pour une application donnée dépend de la taille de ses données et de la capacité de stockage de chaque niveau
- Le B+-tree visait à l’origine à maximiser le fanout pour réduire les accès disque, mais avec l’augmentation de la taille de la mémoire et le fait que les données tiennent en RAM ou en mémoire secondaire non volatile, les compromis ont fortement changé
- Un B+-tree en mémoire atteint ses meilleures performances avec un faible fanout
- Le mur de la mémoire (memory wall) désigne la tendance à l’élargissement de l’écart entre la vitesse des processeurs et celle de la mémoire hors puce
- Depuis le début des années 2000, les systèmes d’exploitation et les systèmes de gestion de données ont été repensés pour optimiser l’utilisation de la mémoire cache
Espace de conception et lignes directrices
- Le document organise l’espace des choix de conception des structures de données et explique comment choisir une structure adaptée aux objectifs applicatifs et aux charges de travail
- Comme le matériel et les propriétés des données évoluent constamment, la conception de structures de données nécessite elle aussi une innovation continue
- L’espace de conception structuré et les lignes directrices servent à choisir la structure la plus adaptée parmi les structures existantes, ou à concevoir une nouvelle structure de données pour une charge de travail spécifique
1 commentaires
Commentaires Hacker News
Je ne l’ai encore que parcouru, mais ce texte est une enquête remarquablement solide sur un domaine immense
Il ne se contente pas d’énumérer des structures de données : il aide aussi à organiser mentalement les éléments à prendre en compte lorsqu’on conçoit ou utilise des structures de données dans une application
L’un des auteurs de ce livre dirige un laboratoire de recherche dans ce domaine
Il existe aussi un outil très sympa pour aider à concevoir la structure de données optimale : http://daslab.seas.harvard.edu/datacalculator/
Je serais curieux d’avoir d’autres recommandations sur ce sujet
L’article est excellent, et je connais aussi Designing Data-Intensive Applications de Martin Klepmann, mais ce livre est plus orienté bases de données que structures de données
Si l’on conçoit une structure pour stocker certains types de données analytiques, il manque une comparaison très importante entre array of structs et struct of arrays
Donc le sujet est bien abordé, mais pas expliqué avec les termes array of structs / struct of arrays
J’aimerais en acheter un exemplaire, mais il est à 100 dollars sur Amazon
C’est un système cassé où les auteurs y perdent et les lecteurs aussi
Il faudrait une table des matières
Même en lui disant d’ignorer les en-têtes et pieds de page, c’était pareil, alors que je pensais que l’état de l’art récent s’était nettement amélioré