Organizing the graph of public software development for large-scale mining
Organisation du graphe de développement logiciel pour l'analyse à grande échelle
Résumé
The Software Heritage project is a software archive containing the largest
public collection of source code files along with their development history,
in the form of an immense graph of hundreds of billions of edges. In this
thesis, we present architectural techniques to make this graph available
for research. We first propose some utilities to access the data at a
micro-level in a way that is convenient for smaller-scale research.
To run analyses on the entire archive, we extract a property graph in a
relational format and evaluate the different ways this data can be
exploited using in-house and cloud processing services.
We find that while this approach is well suited to process large amounts of
flat data in parallel, it has inherent limitations for the highly recursive
graph structure of the archive. We propose the use of graph compression as
a way to considerably reduce the memory usage of the graph, allowing us to
load it entirely in physical memory. We develop a library to run arbitrary
algorithms on the compressed graph of public development, using various
mapping techniques to access properties at the node and edge levels.
Then, we leverage this infrastructure to study the topology of the entire
graph, looking at both its local properties and the way software projects
are organized in forks. The in-depth understanding of this structure then
allows us to discuss different approaches for distributed graph analysis.
Software Heritage est une archive de logiciels contenant la plus
grande collection publique de fichiers de code source ainsi que l'historique de
leur développement, sous la forme d'un immense graphe de centaines de milliards
d'arêtes. Dans cette thèse, nous présentons des techniques architecturales pour
rendre ce graphe disponible à des fins de recherche. Nous proposons d'abord
quelques utilitaires pour accéder aux données à un niveau local d'une manière
adaptée à la recherche à petite échelle. Pour effectuer des analyses sur
l'ensemble de l'archive, nous extrayons un graphe de propriétés dans un format
relationnel et évaluons différents systèmes de traitement pour exploiter ces
données. Cette approche est adaptée au traitement de grandes quantités de
données horizontales, mais elle présente des limites inhérentes à la structure
fortement récursive du graphe. Nous proposons d'utiliser la compression de
graphe comme moyen de réduire considérablement la taille du graphe, ce qui nous
permet de le charger en mémoire vive. Nous développons une bibliothèque pour
exécuter des algorithmes arbitraires sur le graphe compressé, en utilisant
des techniques de mise en correspondance de ses propriétés au
niveau des nœuds et des arêtes. Nous utilisons ensuite cette infrastructure
pour étudier la topologie locale du graphe ainsi que son organisation en forks
de projets logiciels. Comprendre cette structure nous permet ensuite de
discuter de différentes approches pour l'analyse distribuée.
Origine : Fichiers produits par l'(les) auteur(s)