Maîtriser les données liées en PHP : graphes et algorithmes

Transcription de la vidéo

Nous avons utilisé ChatGPT pour améliorer la grammaire et la syntaxe de la transcription.

Bonjour et bienvenue à tous pour ce presque dernier créneau de la journée. Aujourd'hui, nous allons parler de graphiques. Et pour être précis une dernière fois, pas le genre de graphiques qui sont colorés, mais le genre de graphiques ennuyeux qui considèrent simplement les points et la façon dont ils sont connectés.

Je m'appelle Christian et je travaille actuellement chez Shopware où je suis le fou résident qui fait toutes sortes d'expériences folles et travaille avec n'importe quelle technologie qui pourrait être intéressante pour l'avenir ou qui n'a pas encore été explorée, comme par exemple, les graphes. Je suis également actif sur Mastodon, alors n'hésitez pas à vous connecter avec moi si vous le souhaitez.

Aujourd'hui, il est question d'enchevêtrements - comment les choses sont connectées lorsque vous les mettez ensemble, et comment vous pouvez ensuite les retirer. Il existe différents types de connexions. Comme l'indique le titre de l'exposé, "Pris dans une toile", nous parlons de toiles - elles sont enchevêtrées -, de villes vues d'en haut et de cartes. Tous ces éléments ont un point commun : ils sont visuellement chargés et fortement connectés. Nous allons approfondir ce point.

Démêler des structures comme celles-ci n'est pas un problème nouveau. Il existe depuis des centaines d'années. Par exemple, le premier problème de ce type est celui des sept ponts de Königsberg, aujourd'hui Kaliningrad, qui est apparu en 1736. La question était la suivante : "Comment puis-je me déplacer à travers la ville en ne traversant chaque pont qu'une seule fois ?"

Ce qui n'était au départ qu'une question posée à l'occasion d'une soirée arrosée s'est avéré d'une grande profondeur mathématique, car il n'existe pas de solution facile ou élégante à ce problème avec les outils habituels tels que la géométrie ou l'algèbre. Le mathématicien Leonard Euler, que vous connaissez peut-être parce qu'il a résolu des tas de choses, a eu l'idée de réfléchir aux parties de ce problème. Les parties sont des endroits où l'on peut se trouver - dans ce cas, la petite île, la grande île et les deux rives de la rivière. Les ponts qui les relient deviennent des connexions.

Ce problème n'est plus lié à un modèle géométrique. Il s'agissait simplement de points reliés par des arêtes. Euler a compris que pour aller d'un endroit à un autre, il fallait entrer dans un nœud, en sortir et entrer dans un autre. Cela signifie que chaque nœud a besoin d'un nombre pair de connexions, car il faut une connexion pour entrer et une autre pour sortir. Si un nœud a un nombre impair de connexions, vous ne pouvez pas vous déplacer à travers tous les nœuds sans utiliser une arête deux fois.

Euler a prouvé qu'il n'est pas mathématiquement possible de trouver un chemin qui traverse chaque pont une fois. Mais comment les mathématiciens décrivent-ils aujourd'hui les graphes ? En théorie, c'est assez simple : une fonction de sommets, d'arêtes et de correspondances. Mais ce n'est pas si simple en pratique, c'est pourquoi je vais faire une brève introduction.

Le mot "V" signifie "vertices" (sommets). Les sommets sont les points que vous connectez - juste des points avec un ID, un seul nombre. Par exemple, vous avez le sommet un, le sommet deux, le sommet trois, etc. Ensuite, il y a les arêtes. Les arêtes sont également des identités, mais elles relient deux sommets. "F" fait correspondre l'identité des arêtes aux deux sommets, de sorte que vous pouvez relier deux sommets en les décrivant par une arête.

Une arête relie deux parties. Par exemple, vous avez le sommet un et le sommet deux, et les sommets proviennent de l'ensemble de tous les sommets de votre graphe. C'est encore facile ? Pas vraiment, mais il y a une façon humaine de voir les choses, une façon non mathématique. Les sommets sont des points, et les arêtes montrent comment ces points sont connectés. Les graphiques ne concernent que la façon dont les points de données sont connectés. Ils n'ont pas de coordonnées comme on pourrait s'y attendre en graphisme ou en infographie. Les coordonnées sont arbitraires, et la façon dont elles sont placées dans l'espace ne sert qu'à faciliter la compréhension de l'homme.

C'est ce qui unit les réseaux, les villes et les cartes : ils peuvent tous être affichés et transformés en graphiques. Chaque fois que deux routes se rencontrent, on peut le décrire comme un point, les routes étant les bords. C'est ainsi que des outils comme Google Maps peuvent utiliser des algorithmes de graphes pour tracer votre chemin de A à B et vous donner des indications.

Nous voyons donc que les graphes impliquent une certaine forme de navigation. Mais il ne s'agit pas seulement de navigation physique. En tant que développeurs web, nous pensons rarement aux routes que nous devons emprunter pour aller d'un endroit à l'autre. Mais ce que nous traitons en permanence, ce sont des données. Et c'est là que je veux faire le lien avec un outil appelé JQ.

Combien d'entre vous connaissent JQ ? D'accord, je vois beaucoup de mains, mais pas toutes. L'explication rapide est la suivante : JQ est un outil en ligne de commande qui permet d'éditer, de lire et de modifier facilement des données JSON. Il possède sa propre syntaxe pour accéder aux données des objets JSON et les modifier. Ce que je veux vous montrer, c'est que cette syntaxe n'est rien d'autre que la navigation dans un morceau de JSON.

À gauche, vous voyez une réponse API aléatoire. Elle contient deux entités, chacune avec un nom et une adresse. Le script JQ accède à ces données et, à droite, vous voyez les données que nous voulons extraire. Les flèches rouges indiquent où nous nous trouvons dans les données. Jouons donc à JQ - je suis l'ordinateur.

Nous commençons par accéder à l'élément racine, l'objet JSON de premier niveau. Nous accédons ensuite au premier attribut nommé, "data", qui contient un tableau. Nous accédons au premier élément du tableau, qui est un objet JSON contenant un champ d'adresse, qui contient à son tour la rue. À la fin de notre script JQ, la valeur renvoyée est "Test Street".

Voici à quoi cela ressemble en tant que graphique. C'est la vue "Google Maps" de cette structure de données. Vous pouvez donner des noms significatifs aux arêtes de connexion et tracer un chemin à travers les données en transformant votre déclaration JQ en cette structure abstraite - un chemin de structure. C'est ce que je voulais démontrer : la structure des données n'a rien à voir avec les données elles-mêmes. Vous pouvez complètement séparer les deux et opérer uniquement sur la structure.

Pourquoi est-ce si puissant ? Parce que vous pouvez utiliser des sous-éléments de ces chemins. Par exemple, vous pouvez dire : "Je veux juste obtenir la rue de chaque adresse". Vous naviguez jusqu'au champ de l'adresse, vous obtenez le champ de la rue et vous utilisez ce sous-graphe pour interroger des ensembles de données encore plus vastes. Vous ne vous souciez pas de ce qui n'est pas sur le chemin rouge.

Mais avant d'aller trop loin et de nous perdre dans la théorie, revenons à un sujet que nous traitons plus souvent : les objets par rapport aux tables. Il s'agit d'un problème courant pour les développeurs, qui porte même un nom : les tables de correspondance objet-relation (ORM). Ne vous inquiétez pas, cet exposé ne porte pas sur les ORM, mais sur les personnes qui doivent les maintenir, dont je fais partie.

Le problème est que les objets n'existent souvent que dans la mémoire. Nous ne pensons généralement pas à l'ordre dans lequel ils ont été créés. Mais lorsque nous voulons transformer ces objets en tables de base de données, nous avons déjà tous les objets que nous voulons, et nous devons alors trouver comment les introduire dans la base de données. Pourquoi ? Parce que la base de données a un modèle relationnel et que ce modèle utilise des clés étrangères. Les clés étrangères signifient que vous ne pouvez pas référencer un élément de données que la base de données ne connaît pas déjà.

Chez Shopware, nous avons rencontré un problème particulier lorsque nous avons voulu écrire une API permettant aux développeurs d'insérer des données dans un format convivial, comme l'objet JSON suivant, dans notre base de données. Par exemple, vous souhaitez insérer un "produit génial" avec quelques catégories dans la base de données de Shopware. L'objectif du développeur était de fournir des données d'inventaire dans ce format convivial.

Cependant, nous nous sommes rapidement rendu compte qu'il n'était pas possible de créer un produit avec des catégories si celles-ci n'existaient pas déjà dans la base de données. Vous devez connaître les identifiants de ces catégories, car sans identifiant, vous ne pouvez effectuer aucune insertion dans la base de données. Les clés étrangères doivent exister.

Cette situation m'a fait penser à un graphe orienté. J'ai commencé à considérer cette situation comme un problème de graphe orienté, ce qui nous a amenés à trier les données de manière logique. Mais tout d'abord, définissons ce qu'est un graphe orienté.

Un graphe orienté est un graphe dans lequel la direction des connexions est importante. Par exemple, dans une base de données, une table peut connaître une autre table par le biais d'une clé étrangère, mais l'inverse n'est pas toujours vrai. Dans le cas contraire, vous créeriez un cycle. Un graphe orienté signifie que la connexion d'un nœud A à un nœud B n'est pas la même que la connexion de B à A. En revanche, un graphe non orienté ne se préoccupe pas de la direction - les connexions sont mutuelles.

Maintenant que nous savons que nous avons affaire à un graphe orienté et que nous devons résoudre les dépendances, nous pouvons réfléchir à la manière d'ordonner le graphe. Heureusement, il existe des algorithmes pour cela. Vous pouvez consulter"topological sorting" sur Wikipedia. C'est également ce que les outils tels que les conteneurs d'injection de dépendances utilisent pour déterminer l'ordre dans lequel les objets doivent être instanciés pour l'injection de dépendances.

Je vais vous montrer un algorithme appelé Algorithme de Kahn, qui détermine l'ordre d'insertion des données à partir du format JSON que je vous ai montré plus tôt. Pour le faire efficacement, nous devons assigner une valeur à chaque nœud qui indique le nombre de connexions entrantes (ou d'arêtes).

Qu'est-ce qu'une connexion entrante ? C'est l'endroit où la flèche pointe vers un nœud. Attribuons des valeurs à notre graphique. Pour le "Produit génial" à la racine du document, il y a zéro nœud entrant - aucune connexion entrante. Quant à nos catégories "Choses géniales" et "Produits", elles ont chacune une connexion entrante, ce qui leur donne une valeur de un.

Nous pouvons maintenant appliquer l'algorithme de Kahn. Tout d'abord, nous sélectionnons un nœud avec zéro connexion entrante. Si un tel nœud n'existe pas, vous avez un cycle, ce dont nous nous occuperons plus tard. Pour l'instant, supposons que l'entrée de l'utilisateur est correcte. Nous avons un ou plusieurs nœuds avec zéro arête entrante. Nous sélectionnons le premier - ce sera le dernier que nous devrons insérer dans la base de données.

Nous supprimons ensuite ses arêtes du graphe et décrémentons le nombre d'arêtes entrantes pour les nœuds connectés. En conséquence, deux autres nœuds n'ont plus aucune connexion entrante. Nous répétons le processus, en sélectionnant un nœud dont les arêtes entrantes sont nulles, en le plaçant dans la pile et en décrémentant les arêtes entrantes des nœuds connectés.

Nous finissons par obtenir un ordre d'insertion. De gauche à droite : "Racine", "Produits", "Choses géniales" et enfin "Produit génial". Avec cet ordre, vous pouvez insérer les données dans la base de données sans violer les contraintes de clé étrangère, car c'est l'ordre dans lequel les entités dépendent les unes des autres.

Mais qu'en est-il des cycles ? Comment les traiter ? Ma réponse est la suivante : vous pouvez chercher sur Google. Maintenant que nous savons comment modéliser notre problème sous la forme d'un graphe, nous pouvons chercher comment traiter les cycles dans un graphe. Si vous tapez "détection de cycle dans un graphe" sur Google, vous trouverez des algorithmes tels que la recherche en profondeur d'abord(DFS).

Prenons un exemple de diagramme. J'ai intentionnellement intégré une boucle pour voir comment nous pouvons détecter ce cycle à l'aide de la recherche en profondeur d'abord. Nous choisissons un nœud de départ - disons que notre nœud actuel est "Panier à poignée". Sur le côté gauche, nous avons notre pile d'insertion. Nous examinons le nœud et l'ajoutons à la pile. Nous vérifions également ses voisins, qui sont les nœuds suivants à examiner.

Notre nœud "Produits" est connecté au nœud "Racine", nous ajoutons donc "Produits" à la pile et déplaçons "Racine" dans la liste "Prochain nœud à examiner". Nous procédons de la même manière, puis nous arrivons à "Awesome Things" (Choses géniales). Lorsque nous examinons les voisins de "Awesome Things", nous constatons qu'il renvoie à "Products", créant ainsi un cycle.

Pourquoi est-il utile de détecter les cycles ? Parce que vous pouvez maintenant décider ce qu'il faut faire du cycle. Dans certains domaines, il peut être judicieux d'examiner les données et de décider que l'un des nœuds doit être traité en premier. Ou, en fonction de votre objectif, vous pouvez choisir d'interrompre temporairement la connexion et de la rétablir plus tard. Dans notre exemple, cependant, il s'agit de données interrompues - vous ne pouvez pas les introduire dans une base de données. Vous devez connaître les identifiants des lignes avant même qu'elles n'existent. Dans ce cas, vous pouvez donc informer l'utilisateur qu'il existe un cycle reliant "Products", "Root" et "Awesome Things", ce qui empêche l'insertion des données.

Avec cette approche, vous disposez de tous les outils nécessaires pour prendre des données JSON d'une source externe et les injecter dans une base de données de manière correcte et ordonnée.

Mais nous ne sommes pas au bout de nos peines. Il existe un autre graphe que nous connaissons tous - certains d'entre nous peut-être un peu trop bien - et c'est Git. Git est en fait un arbre, et un arbre est un graphe. Git est un arbre dirigé car il travaille du futur vers le passé.

Voici un exemple d'arbre Git. Au sommet, nous avons notre commit principal, c'est-à-dire l'endroit où nous nous trouvons actuellement. Il y a une branche en haut, marquant un point où quelqu'un a fait des changements. Nous avons un commit de fusion qui a deux parents, et tout en bas se trouve la racine. Tout est connecté depuis le présent jusqu'au passé.

Ce qui est intéressant, c'est que nous pouvons utiliser ces informations, cet historique de notre projet, pour optimiser notre architecture. Vous vous demandez peut-être pourquoi nous parlons maintenant d'architecture, mais la réponse est la suivante : il s'agit également d'un problème de graphe. Si vous connaissez certains algorithmes, vous pouvez extraire des informations utiles.

Comment procédons-nous ? En transformant nos données Git en un réseau social. Dans ce contexte, un réseau social signifie que nous avons des tonnes de fichiers et que ces fichiers "parlent" entre eux. "Parler" signifie qu'ils sont modifiés ensemble. Un commit est une modification significative de la base de code. Par exemple, une validation peut créer ou modifier les fichiers A, B et C.

Voici comment nos validations sont liées aux fichiers : la validation de la racine a créé nos deux premiers fichiers, A et B. La validation suivante a ajouté le fichier C, et ainsi de suite. Ces validations connectent les fichiers, et ces connexions signifient quelque chose - par exemple, si le fichier D est un nouveau service dans votre architecture, le fichier A peut avoir besoin d'être modifié parce qu'un test est en train d'échouer.

Ces modifications créent une connexion entre les fichiers, et nous pouvons la transformer en un graphique montrant comment les fichiers sont connectés. C'est ainsi que Git voit les choses - c'est utile pour revenir à un commit particulier et restaurer le code dans cet état. Mais nous pouvons également l'examiner d'un point de vue différent, en voyant quels fichiers ont été modifiés ensemble. Par exemple, le fichier A est étroitement lié au fichier D, mais pas du tout au fichier C. Il n'y a pas de livraison où A et C apparaissent ensemble, donc ils ne sont pas étroitement liés.

Nous pouvons ensuite utiliser ces informations pour tracer un chemin dans le graphe. Les chiffres que vous voyez à côté des connexions s'appellent des poids. Un poids représente la fréquence à laquelle deux fichiers sont engagés ensemble. Vous pouvez ajouter des données supplémentaires aux nœuds et aux arêtes d'un graphe, et ces données, qui n'ont pas de schéma inhérent, sont appelées "poids". Dans notre cas, les poids sont simplement des nombres entiers représentant le nombre de fois où deux fichiers ont été livrés ensemble.

Cela semble facile pour un petit graphe comme celui-ci, mais lorsque vous l'exécutez sur une grande base de code avec des milliers de fichiers, vous vous retrouvez rapidement avec un graphe contenant des centaines de milliers d'arêtes, ce qui peut être difficile à travailler.

En calculant les chemins à travers le graphe, nous pouvons appliquer une métrique appelée "betweenness centrality". Cette mesure a été inventée à l'origine pour les réseaux sociaux, et est utilisée par des entreprises comme Facebook et Twitter pour déterminer quelles personnes sont importantes, ou centrales, au sein du réseau. Dans notre cas, nous l'utilisons pour déterminer quels fichiers sont centraux dans notre base de code - ceux qui relient les différents composants de notre architecture.

Certains d'entre vous ont peut-être déjà remarqué que les fichiers A et D semblent assez importants. Comment cela se fait-il ? Parce que si vous devez passer des fichiers G, E ou F aux fichiers A, J, B ou C, vous devez passer par le fichier D. D est comme le seul pont qui relie deux parties de la base de code.

Comment cela se passe-t-il en pratique ? J'ai écrit un outil qui calcule le degré de centralité de chaque fichier de notre système et j'ai effectué une analyse de données. Le résultat est une visualisation colorée appelée "diagramme Sunburst". Ce diagramme montre la contribution de chaque dossier de notre projet à la centralité d'interdépendance.

Par exemple, notre dossier "Snippet" contribue à 25 % de la centralité. Pourquoi ? Parce que, comme vous pouvez le voir dans l'anneau intérieur bleu, notre "Administration" (couche d'interface utilisateur) est assez importante. Lorsque vous modifiez quelque chose dans l'interface utilisateur, vous devez souvent mettre à jour les snippets, car les nouveaux éléments de l'interface utilisateur nécessitent de nouvelles chaînes de caractères pour décrire ce qu'ils font. Cela crée de nombreuses connexions entre le code de l'interface utilisateur et les extraits.

De même, nos tests de bout en bout (E2E), bien qu'ils ne soient pas aussi connectés, ont longtemps été assez fragiles. Chaque fois que quelqu'un modifiait un peu de JavaScript ou de CSS, les tests E2E s'interrompaient. Nous savions donc que toute modification de l'interface utilisateur nécessitait de toucher aux tests E2E. C'est quelque chose que beaucoup d'entre vous savent probablement - des tests E2E mal exécutés peuvent être plus fragiles que des tests unitaires.

Mais cela n'excuse pas nos tests unitaires. J'ai également exécuté l'analyse sur notre base de code PHP et vérifié les tests. Le score de centralité d'interdépendance m'a indiqué la probabilité qu'un test se casse lorsqu'une modification aléatoire est apportée à la base de code.

Le test le plus fragile était notre test API-aware. Lorsque je l'ai examiné, j'ai constaté qu'il était conçu pour comparer l'ensemble du schéma de l'API à un fichier JSON validé afin de vérifier les annotations des champs. Cela rendait le test volontairement très fragile. Chaque fois qu'une modification était apportée au schéma de l'API, le test échouait et les développeurs devaient le corriger.

J'ai pu identifier ce test fragile rien qu'en analysant l'historique Git. Nous avons abordé de nombreux sujets - des cartes, de l'histoire et des mathématiques à l'informatique, aux bases de données et aux graphiques. Mais qu'avons-nous à y gagner ? Pourquoi faisons-nous tout cela ?

C'est là l'essentiel. Il existe des méthodes standard pour traiter les données - nous avons des modèles tels que les usines et les modèles de commande pour décrire le comportement d'un système. Ces modèles sont bien compris. Mais qu'en est-il de la structure ? Nous n'y pensons pas aussi souvent qu'aux données.

Nous disposons de modèles de structure, comme les graphes. L'utilisation d'algorithmes qui analysent la disposition des données peut nous aider à dériver certains attributs et à vérifier certaines choses. Nous pouvons également calculer de nouvelles données à partir de la structure, en examinant par exemple l'historique des livraisons d'un projet ou le graphe de dépendance des classes. Nous pouvons utiliser des algorithmes standard, dont beaucoup sont déjà bien établis et faciles à trouver.

J'espère que cet exposé vous a inspiré. Comme je l'ai déjà dit, les graphes sont partout. Passez une bonne soirée et profitez du dernier créneau de la journée !

Q&R

Question: Quelles sont les bonnes raisons d'utiliser des graphiques ? Quelles sont les bonnes raisons d'utiliser des structures de graphes plutôt que des structures plus traditionnelles, en dehors des exemples que vous avez montrés ? Avez-vous d'autres exemples à nous proposer ?
Christian: Oui, absolument. Un exemple est l'utilisation d'un outil comme DepthTrack, qui analyse la façon dont les classes dépendent les unes des autres. J'ai utilisé les informations de DepthTrack pour afficher les dépendances sous forme de graphique. Ensuite, j'ai appliqué des algorithmes de mise en page pour organiser le graphique dans l'espace, ce qui nous a permis de voir quelles parties de notre système étaient fortement couplées.

Nous avons coloré les nœuds en fonction du dossier auquel ils appartenaient, ce qui nous a permis d'identifier les cas où deux dossiers qui n'étaient pas censés dépendre l'un de l'autre étaient étroitement liés. Par exemple, nous avons pu voir à quel point notre système de caisse était lié à notre couche de base de données, ou comment notre logique d'expédition était connectée à nos services de paiement. Les algorithmes de mise en page peuvent aider à rendre ces relations visibles dans un graphe de dépendance.

Question: Y a-t-il un ensemble d'outils que vous utilisez pour analyser vos référentiels et générer les graphiques montrant les relations entre vos classes ?
Christian: La réponse standard serait d'utiliser Python avec la bibliothèque NetworkX. Cependant, NetworkX peut être lent pour de très grands graphes comme un référentiel entier. Dans ce cas, j'ai donc réécrit l'algorithme Python en Rust et je l'ai exécuté en parallèle. Cela a permis de réduire le temps de traitement de 20 heures à seulement 2 minutes.

C'est un outil inachevé que j'ai sur mon GitHub. Il produit un fichier CSV, et vous pouvez utiliser Excel ou d'autres outils pour le visualiser. Dans ce cas, j'ai utilisé une bibliothèque graphique du langage statistique R pour générer les diagrammes Sunburst.

Question: Avez-vous le code dans lequel vous avez calculé la centralité pour certains fichiers ? Est-il disponible quelque part ?
Christian: Oui, il est sur mon GitHub, et le projet s'appelle "Rawal" - il porte le nom d'une baleine pour une raison quelconque. Si vous êtes intéressés, je peux partager le lien dans le Slack Symfony.