MaxCompute:Vue d'ensemble de Graph

Fonctionnement

Les algorithmes de graphes sont intrinsèquement itératifs : la propriété d'un sommet dépend des propriétés de ses voisins, qui elles-mêmes dépendent de leurs propres voisins. MaxCompute Graph modélise ce processus en modifiant le graphe de manière répétée jusqu'à satisfaction d'une condition de convergence. Chaque itération est appelée une superstep.

Un programme de graphe s'exécute en trois phases :

1. Chargement du graphe — Un objet GraphLoader personnalisé lit les enregistrements d'une table d'entrée et les convertit en sommets et arêtes. Un objet Partitioner personnalisé répartit ensuite les sommets entre les workers. Par défaut, MaxCompute Graph partitionne les sommets en appliquant un hachage modulo le nombre de workers à l'ID de chaque sommet.

2. Calcul itératif — Chaque superstep parcourt tous les sommets non arrêtés ainsi que les sommets arrêtés ayant reçu des messages, puis appelle compute(ComputeContext context, Iterable messages) pour chacun d'eux. Dans la méthode compute(), chaque sommet peut :

   • Traiter les messages envoyés lors de la superstep précédente.

   • Modifier les valeurs des sommets ou des arêtes.

   • Envoyer des messages à d'autres sommets.

   • Ajouter ou supprimer des sommets ou des arêtes.

   • Utiliser un objet Aggregator pour collecter et mettre à jour des informations globales. Pour plus de détails, consultez le mécanisme d'implémentation de l'objet Aggregator.

   • Définir son état comme arrêté ou non arrêté.

   MaxCompute Graph envoie de manière asynchrone les messages aux workers concernés à chaque superstep. Ces messages sont ensuite traités lors de la superstep suivante.

3. Arrêt de l'itération — Le calcul s'arrête lorsque l'une des conditions suivantes est remplie :

   • Tous les sommets sont arrêtés (Halted = true) et aucun nouveau message n'a été généré.

   • Le nombre maximal d'itérations est atteint.

   • La méthode terminate() d'un agrégateur renvoie true.

Le pseudocode suivant illustre le flux d'exécution complet :

// 1. load
for each record in input_table {
  GraphLoader.load();
}
// 2. setup
WorkerComputer.setup();
for each aggr in aggregators {
  aggr.createStartupValue();
}
for each v in vertices {
  v.setup();
}
// 3. superstep
for (step = 0; step < max; step ++) {
  for each aggr in aggregators {
    aggr.createInitialValue();
  }
  for each v in vertices {
    v.compute();
  }
}
// 4. cleanup
for each v in vertices {
  v.cleanup();
}
WorkerComputer.cleanup();

Concepts clés

Structure de données des graphes

MaxCompute Graph traite les graphes orientés. Étant donné que MaxCompute utilise une structure de stockage tabulaire bidimensionnelle, vous devez convertir les données du graphe en tables bidimensionnelles avant de les stocker.

Lors du calcul, un objet GraphLoader personnalisé reconvertit les enregistrements de la table en sommets et arêtes.

Structure d'un sommet : <ID, Value, Halted, Edges>

Structure d'une arête : <DestVertexID, Value>

Le graphe ci-dessus correspond à la table bidimensionnelle suivante :

La figure suivante montre la répartition des sommets entre deux workers lors du chargement du graphe. Les ID des sommets sont hachés modulo 2 : v0 et v2 (ID modulo 2 = 0) sont attribués au Worker 0 ; v1, v3 et v5 (ID modulo 2 = 1) sont attribués au Worker 1.

Lorsque vous modifiez un sommet ou une arête, utilisez du code pour maintenir les relations entre les sommets et les arêtes.

Étapes suivantes

• PageRank

• Algorithme du plus court chemin à source unique (SSSP)

• Algorithme k-means

• Mécanisme d'implémentation de l'agrégateur