Éliminer le "problème n+1"

Découvrons comment Gato GraphQL évite complètement le « problème n+1 » grâce à sa conception architecturale.

​

Qu'est-ce que le « problème n+1 »

Le « problème n+1 » signifie, en gros, que le nombre de requêtes exécutées contre la base de données peut être aussi grand que le nombre de nœuds dans le graphe.

Qu'est-ce que cela signifie ? Voyons cela avec un exemple : supposons que nous voulions récupérer une liste de réalisateurs, et pour chacun d'eux sa liste de films, via la requête suivante :

{
  query {
    directors(first: 10) {
      name
      films(first: 10) {
        title
      }
    }
  }
}Copy

Pour être efficaces, nous nous attendrions à exécuter seulement 2 requêtes pour récupérer les données de la base de données : 1 pour obtenir les données des réalisateurs, et 1 pour récupérer les données de tous les films de tous les réalisateurs.

Cependant, pour satisfaire cette requête, GraphQL devra exécuter « n+1 » requêtes contre la base de données : 1 d'abord pour récupérer la liste des N réalisateurs (10 dans ce cas), puis pour chacun des N réalisateurs, 1 requête pour récupérer sa liste de films. Dans notre cas, nous devons exécuter 1+10=11 requêtes.

Ce problème survient parce que les resolvers GraphQL ne traitent qu'un seul objet à la fois, et non tous les objets du même type en même temps. Dans notre cas, le resolver qui gère les objets du type Query (qui est le type racine) sera appelé une première fois pour obtenir la liste de tous les objets Director, puis le resolver qui gère le type Director sera appelé une fois pour chaque objet Director, afin de récupérer sa liste de films.

Autrement dit : les resolvers GraphQL voient l'arbre, pas la forêt.

Ce problème est en réalité pire qu'il n'y paraît au premier abord, car le nombre de nœuds dans un graphe croît de façon exponentielle avec le nombre de niveaux du graphe. Ainsi, le nom « n+1 » n'est valide que pour un graphe à 2 niveaux de profondeur. Pour un graphe à 3 niveaux de profondeur, on devrait l'appeler le problème « N²+n+1 » ! Et ainsi de suite...

Par exemple, en suivant notre exemple ci-dessus, ajoutons également la liste des acteurs/actrices de chaque film à la requête, comme ceci :

{
  query {
    directors(first: 10) {
      name
      films(first: 10) {
        title
        actors(first: 10) {
          name
        }
      }
    }
  }
}Copy

Alors, les requêtes exécutées contre la base de données sont : 1 d'abord pour récupérer la liste des 10 réalisateurs, puis 1 requête pour récupérer la liste de films de chaque réalisateur pour chacun des 10 réalisateurs, et enfin 1 requête pour récupérer chaque liste d'acteurs/actrices pour chacun des 10 films de chacun des 10 réalisateurs. Cela donne un total de 1+10+100=111 requêtes.

Après avoir observé ce comportement, le « problème n+1 » peut facilement être considéré comme le plus grand obstacle de performance de GraphQL : s'il n'est pas contrôlé, interroger des graphes de quelques niveaux de profondeur peut devenir si lent que GraphQL en deviendrait pratiquement inutile.

​

Solution générale au « problème n+1 »

La solution standard au « problème n+1 » a d'abord été fournie par l'utilitaire DataLoader. Sa stratégie est très simple : différer la résolution des segments de la requête jusqu'à une étape ultérieure, dans laquelle tous les objets du même type peuvent être résolus ensemble, en une seule requête. Cette stratégie, appelée « batching », résout efficacement le problème « n+1 ».

De plus, DataLoader met en cache les objets après les avoir récupérés, de sorte que si une requête ultérieure a besoin de charger un objet déjà chargé, elle peut éviter l'exécution et récupérer l'objet depuis le cache. Cette stratégie, appelée « caching », est surtout une optimisation en complément du « batching ».

​

Problèmes avec la solution « batching/différée »

D'un point de vue technique, il n'y a aucun problème avec la stratégie « batching » ou « différée » : elle fonctionne tout simplement.

(Dorénavant, référons-nous à la stratégie uniquement comme « différée ».)

Le problème, cependant, est que cette stratégie est une réflexion après coup : le développeur peut d'abord implémenter le serveur puis, constatant la lenteur de la résolution des requêtes, décider d'introduire le mécanisme de différement. Ainsi, l'implémentation des resolvers peut impliquer quelques faux pas, ajoutant des frictions au processus de développement. De plus, comme le développeur doit comprendre comment fonctionne le mécanisme « différé », son implémentation devient plus complexe qu'elle ne pourrait l'être autrement.

Ce problème ne réside pas dans la stratégie elle-même, mais dans le fait que le serveur GraphQL propose cette fonctionnalité comme un module complémentaire, alors que sans elle, les requêtes peuvent être si lentes qu'elles rendraient GraphQL pratiquement inutile.

La solution à ce problème est donc simple : la stratégie « différée » ne devrait pas être un module complémentaire, mais être intégrée dans le serveur GraphQL lui-même. Au lieu d'avoir 2 stratégies d'exécution des requêtes, « normale » et « différée », il ne devrait en exister qu'une seule, « différée ». Et le serveur GraphQL doit exécuter le mécanisme « différé » même si le développeur implémente le resolver de façon « normale » (autrement dit, le serveur GraphQL se charge de la complexité supplémentaire, pas le développeur).

Et c'est exactement ce que fait Gato GraphQL.

​

Faire de la stratégie « différée » la seule exécutée par le serveur GraphQL

Le problème avec la plupart des serveurs GraphQL est que la responsabilité de résoudre les types d'objet (object, union et interface) en tant qu'objets incombe aux resolvers eux-mêmes lors du traitement du nœud parent (par exemple : films => directors), au lieu de déléguer cette tâche au moteur de chargement des données.

Gato GraphQL transfère cette responsabilité hors du resolver et vers le moteur de chargement des données du serveur, comme suit :

1. Les resolvers retournent des IDs, et non des objets, lors de la résolution d'une relation entre les nœuds parent et enfant
2. Étant donné une liste d'IDs d'un type donné, une entité DataLoader obtient les objets correspondants de ce type
3. Le moteur de chargement des données du serveur est le lien entre ces 2 parties : il obtient d'abord les IDs des objets à partir des resolvers et, juste avant d'exécuter la requête imbriquée pour la relation (moment auquel il aura accumulé tous les IDs à résoudre pour le type spécifique), il récupère les objets pour ces IDs via le DataLoader (qui peut efficacement inclure tous les IDs dans une seule requête).

Cette approche peut être résumée ainsi : « Travaillez avec des IDs, pas avec des objets ».

Utilisons le même exemple qu'auparavant pour visualiser cette nouvelle approche. La requête ci-dessous récupère une liste de réalisateurs et leurs films :

{
  query {
    directors(first: 10) {
      name
      films(first: 10) {
        title
      }
    }
  }
}Copy

Faites attention aux 2 champs à récupérer pour chaque réalisateur, name et films, et à leurs différences actuelles :

Le champ name est de type scalaire. Il est immédiatement résolvable, car nous pouvons nous attendre à ce que l'objet de type Director contienne une propriété de type string appelée name, contenant le nom du réalisateur. Ainsi, une fois que nous avons l'objet Director, il n'est pas nécessaire d'exécuter une requête supplémentaire pour résoudre cette propriété.

Le champ films, en revanche, est une liste de type objet. Il n'est normalement pas immédiatement résolvable, car il fait référence à une liste d'objets, de type Film, qui doivent encore être récupérés de la base de données via 1 ou plusieurs requêtes supplémentaires. Ainsi, le développeur devrait implémenter le mécanisme « différé » pour ce champ.

Maintenant, considérons le comportement différent, et faisons en sorte que le champ films soit résolu comme une liste d'IDs (plutôt qu'une liste d'objets). Comme nous pouvons nous attendre à ce que l'objet Director contienne une propriété appelée filmIDs contenant les IDs de tous ses films, de type array of string (en supposant que l'ID est représenté sous forme de chaîne), ce champ peut également être résolu immédiatement, sans avoir à implémenter le mécanisme « différé ».

Enfin, en plus de l'ID, le resolver doit fournir une information supplémentaire : le type de l'objet attendu (dans notre exemple, cela pourrait être [(Film, 2), (Film, 5), (Film, 9)]). Cette information est cependant interne, transmise au moteur, et n'a pas besoin d'être incluse dans la réponse à la requête.

​

Implémentation de l'approche adaptée en code

Voyons comment Gato GraphQL implémente cette approche en code PHP. Le code ci-dessous illustre les différents resolvers (pour des raisons de clarté, tout le code ci-dessous a été édité).

​

FieldResolvers

Les FieldResolvers reçoivent un objet d'un type spécifique et résolvent ses champs. Pour les relations, ils doivent également indiquer le type de l'objet vers lequel ils se résolvent. Voici leur contrat :

interface FieldResolverInterface
{
  public function resolveValue($object, string $field, array $args = []);
  public function resolveFieldTypeResolverClass(string $field, array $args = []): ?string;
}Copy

Son implémentation ressemble à ceci :

class PostFieldResolver implements FieldResolverInterface
{
  public function resolveValue($object, string $field, array $args = [])
  {
    $post = $object;
    switch ($field) {
      case 'title':
        return $post->title;
      case 'author':
        return $post->authorID; // This is an ID, not an object!
    }
 
    return null;
  }
 
  public function resolveFieldTypeResolverClass(string $field, array $args = []): ?string
  {
    switch ($field) {
      case 'author':
        return UserTypeResolver::class;
    }
 
    return null;
  }
}Copy

Remarquez comment, en supprimant la logique gérant les promesses/objets différés, le code résolvant le champ author est devenu très simple et concis.

​

TypeResolvers

Les TypeResolvers sont des objets qui traitent un type spécifique : ils connaissent le nom du type et quel TypeDataLoader charge les objets de son type, entre autres.

Le moteur de chargement des données, lors de la résolution des champs, recevra des IDs d'une certaine classe TypeResolver. Puis, lors de la récupération des objets pour ces IDs, le moteur de chargement des données demandera au TypeResolver quel objet TypeDataLoader utiliser pour charger ces objets.

Leur contrat est défini ainsi :

interface TypeResolverInterface
{
  public function getTypeName(): string;
  public function getTypeDataLoaderClass(): string;
}Copy

Dans notre exemple, la classe UserTypeResolver définit que le type User doit avoir ses données chargées via la classe UserTypeDataLoader :

class UserTypeResolver implements TypeResolverInterface
{
  public function getTypeName(): string
  {
    return 'User';
  }
 
  public function getTypeDataLoaderClass(): string
  {
    return UserTypeDataLoader::class;
  }
}Copy

​

TypeDataLoaders

Les TypeDataLoaders reçoivent une liste d'IDs d'un type spécifique et retournent les objets correspondants de ce type. Voici leur contrat :

interface TypeDataLoaderInterface
{
  public function getObjects(array $ids): array;
}Copy

La récupération des utilisateurs se fait ainsi :

class UserTypeDataLoader implements TypeDataLoaderInterface
{
  public function getObjects(array $ids): array
  {
    $userAPI = UserAPIFacade::getInstance();
    return $userAPI->getUsers($ids);
  }
}Copy

​

Exécuter une (vraiment) grande requête

Testons que cette stratégie fonctionne. Rendez-vous dans le client GraphiQL de Gato GraphQL et exécutez la requête ci-dessous, qui implique un graphe à 10 niveaux de profondeur (posts => author => posts => tags => posts => comments => author => posts => comments => author) et qui ne pourrait pas être résolue dans un délai raisonnable si le « problème n+1 » se produisait.

query {
  posts(pagination:{ limit:10 }) {
    excerpt
    title
    url
    author {
      name
      url
      posts(pagination:{ limit:10 }) {
        title
        tags(pagination:{ limit:10 }) {
          slug
          url
          posts(pagination:{ limit:10 }) {
            title
            comments(pagination:{ limit:10 }) {
              content
              date
              author {
                name
                posts(pagination:{ limit:10 }) {
                  title
                  url
                  comments(pagination:{ limit:10 }) {
                    content
                    date
                    author {
                      name
                      username
                      url
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}Copy

En faisant défiler les résultats, vous verrez à quel point la réponse est volumineuse, combien d'entités elle implique et combien de niveaux elle a récupérés, et pourtant elle a été exécutée rapidement, sans aucune difficulté.