Logo
Arquitetura
ArquiteturaEliminando o "problema n+1"

Eliminando o "problema n+1"

Vamos aprender como o Gato GraphQL evita completamente o «problema n+1» já pelo seu design arquitetural.

O que é o «problema n+1»

O «problema n+1» significa, basicamente, que a quantidade de queries executadas contra o banco de dados pode ser tão grande quanto o número de nós no grafo.

O que isso quer dizer? Vamos ver com um exemplo: suponha que queremos recuperar uma lista de diretores e, para cada um deles, a sua lista de filmes, por meio da seguinte query:

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

Para ser eficiente, esperaríamos executar apenas 2 queries para recuperar os dados do banco de dados: 1 para buscar os dados dos diretores e 1 para recuperar os dados de todos os filmes de todos os diretores.

No entanto, para satisfazer essa query, o GraphQL precisará executar «n+1» queries contra o banco de dados: 1 primeiro para recuperar a lista dos N diretores (10 neste caso) e depois, para cada um dos N diretores, 1 query para recuperar a sua lista de filmes. No nosso caso, precisamos executar 1+10=11 queries.

Esse problema ocorre porque os resolvers do GraphQL lidam com apenas 1 objeto por vez, e não com todos os objetos do mesmo tipo ao mesmo tempo. No nosso caso, o resolver que lida com objetos do tipo Query (que é o tipo raiz) será chamado uma primeira vez para obter a lista de todos os objetos Director e depois, o resolver que lida com o tipo Director será chamado uma vez para cada objeto Director, para recuperar a sua lista de filmes.

Em outras palavras: os resolvers do GraphQL veem a árvore, não a floresta.

Esse problema é, na verdade, pior do que parece inicialmente, porque o número de nós em um grafo cresce exponencialmente em relação ao número de níveis do grafo. Portanto, o nome «n+1» é válido apenas para um grafo com 2 níveis de profundidade. Para um grafo com 3 níveis de profundidade, deveria ser chamado de problema «N2+n+1»! E assim por diante...

Por exemplo, seguindo o nosso exemplo acima, vamos também adicionar à query a lista de atores/atrizes de cada filme, assim:

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

Então, as queries executadas contra o banco de dados são: 1 primeiro para recuperar a lista dos 10 diretores, depois 1 query para recuperar a lista de filmes de cada diretor para cada um dos 10 diretores, e finalmente 1 query para recuperar cada lista de atores/atrizes para cada um dos 10 filmes de cada um dos 10 diretores. Isso resulta em um total de 1+10+100=111 queries.

Após observar esse comportamento, o «problema n+1» pode facilmente ser considerado o maior obstáculo de desempenho do GraphQL: se não for controlado, consultar grafos com alguns níveis de profundidade pode se tornar tão lento a ponto de tornar o GraphQL praticamente inútil.

Solução geral para o «problema n+1»

A solução padrão para o «problema n+1» foi fornecida pela primeira vez pelo utilitário DataLoader. Sua estratégia é muito simples: adiar a resolução de segmentos da query para uma etapa posterior, na qual todos os objetos do mesmo tipo possam ser resolvidos juntos, em uma única query. Essa estratégia, chamada de «batching», resolve efetivamente o problema «n+1».

Além disso, o DataLoader armazena os objetos em cache após recuperá-los, de modo que, se uma query subsequente precisar carregar um objeto já carregado, pode pular a execução e recuperar o objeto do cache. Essa estratégia, chamada de «caching», é principalmente uma otimização sobre o «batching».

Problemas com a solução «batching/adiada»

Tecnicamente falando, não há nenhum problema com a estratégia «batching» ou «adiada»: ela simplesmente funciona.

(A partir de agora, vamos nos referir à estratégia apenas como «adiada».)

O problema, porém, é que essa estratégia é uma reflexão tardia: o desenvolvedor pode primeiro implementar o servidor e depois, ao perceber o quão lento está sendo resolver as queries, decidir introduzir o mecanismo de adiamento. Portanto, implementar os resolvers pode envolver alguns passos equivocados, adicionando fricção ao processo de desenvolvimento. Além disso, como o desenvolvedor precisa entender como o mecanismo «adiado» funciona, sua implementação se torna mais complexa do que poderia ser de outra forma.

Esse problema não está na estratégia em si, mas no fato de o servidor GraphQL oferecer essa funcionalidade como um complemento, mesmo que, sem ela, a consulta possa ser tão lenta a ponto de tornar o GraphQL praticamente inútil.

A solução para esse problema é, portanto, direta: a estratégia «adiada» não deveria ser um complemento, mas estar integrada ao próprio servidor GraphQL. Em vez de ter 2 estratégias de execução de queries, «normal» e «adiada», deveria existir apenas 1, «adiada». E o servidor GraphQL deve executar o mecanismo «adiado» mesmo que o desenvolvedor implemente o resolver de forma «normal» (em outras palavras, o servidor GraphQL cuida da complexidade adicional, não o desenvolvedor).

E é exatamente isso que o Gato GraphQL faz.

Tornando a estratégia «adiada» a única executada pelo servidor GraphQL

O problema com a maioria dos servidores GraphQL é que a responsabilidade de resolver os tipos de objeto (object, union e interface) como objetos recai sobre os próprios resolvers ao processar o nó pai (por exemplo: films => directors), em vez de delegar essa tarefa ao mecanismo de carregamento de dados.

O Gato GraphQL transfere essa responsabilidade do resolver para o mecanismo de carregamento de dados do servidor, da seguinte forma:

  1. Os resolvers retornam IDs, e não objetos, ao resolver um relacionamento entre os nós pai e filho
  2. Dada uma lista de IDs de um determinado tipo, uma entidade DataLoader obtém os objetos correspondentes desse tipo
  3. O mecanismo de carregamento de dados do servidor é a cola entre essas 2 partes: ele primeiro obtém os IDs dos objetos a partir dos resolvers e, logo antes de executar a query aninhada para o relacionamento (momento em que terá acumulado todos os IDs a serem resolvidos para o tipo específico), recupera os objetos para esses IDs por meio do DataLoader (que pode incluir eficientemente todos os IDs em uma única query).

Essa abordagem pode ser resumida como: «Trabalhe com IDs, não com objetos».

Vamos usar o mesmo exemplo de antes para visualizar essa nova abordagem. A query abaixo recupera uma lista de diretores e seus filmes:

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

Preste atenção nos 2 campos a serem recuperados para cada diretor, name e films, e em como eles são diferentes atualmente:

O campo name é do tipo escalar. É imediatamente resolvível, pois podemos esperar que o objeto do tipo Director contenha uma propriedade do tipo string chamada name, contendo o nome do diretor. Portanto, uma vez que temos o objeto Director, não há necessidade de executar uma query adicional para resolver essa propriedade.

O campo films, porém, é uma lista de tipo objeto. Normalmente não é imediatamente resolvível, pois faz referência a uma lista de objetos, do tipo Film, que ainda precisam ser recuperados do banco de dados por meio de 1 ou mais queries adicionais. Portanto, o desenvolvedor precisaria implementar o mecanismo «adiado» para ele.

Agora, vamos considerar o comportamento diferente e fazer com que o campo films seja resolvido como uma lista de IDs (em vez de uma lista de objetos). Como podemos esperar que o objeto Director contenha uma propriedade chamada filmIDs com os IDs de todos os seus filmes, do tipo array of string (assumindo que o ID é representado como uma string), então esse campo também pode ser resolvido imediatamente, sem precisar implementar o mecanismo «adiado».

Por fim, além do ID, o resolver deve fornecer uma informação extra: o tipo do objeto esperado (em nosso exemplo, poderia ser [(Film, 2), (Film, 5), (Film, 9)]). Essa informação é interna, porém, passada ao mecanismo, e não precisa ser incluída na resposta à query.

Implementando a abordagem adaptada em código

Vamos ver como o Gato GraphQL implementa essa abordagem em código PHP. O código abaixo demonstra os diferentes resolvers (para fins de clareza, todo o código abaixo foi editado).

FieldResolvers

Os FieldResolvers recebem um objeto de um tipo específico e resolvem seus campos. Para relacionamentos, também devem indicar o tipo do objeto para o qual resolvem. Este é o seu contrato:

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

Sua implementação é assim:

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;
  }
}

Repare como, ao remover a lógica que lida com promises/objetos adiados, o código que resolve o campo author se tornou muito simples e conciso.

TypeResolvers

Os TypeResolvers são objetos que lidam com um tipo específico: eles conhecem o nome do tipo e qual TypeDataLoader carrega os objetos do seu tipo, entre outras coisas.

O mecanismo de carregamento de dados, ao resolver campos, receberá IDs de uma determinada classe TypeResolver. Então, ao recuperar os objetos para esses IDs, o mecanismo de carregamento de dados perguntará ao TypeResolver qual objeto TypeDataLoader usar para carregar esses objetos.

Seu contrato é definido assim:

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

Em nosso exemplo, a classe UserTypeResolver define que o tipo User deve ter seus dados carregados por meio da classe UserTypeDataLoader:

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

TypeDataLoaders

Os TypeDataLoaders recebem uma lista de IDs de um tipo específico e retornam os objetos correspondentes desse tipo. Este é o seu contrato:

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

A recuperação de usuários é feita assim:

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

Executando uma query (realmente) grande

Vamos testar se essa estratégia funciona. Acesse o cliente GraphiQL no Gato GraphQL e execute a query abaixo, que envolve um grafo com 10 níveis de profundidade (posts => author => posts => tags => posts => comments => author => posts => comments => author) e que não poderia ser resolvida em um tempo razoável se o «problema n+1» estivesse ocorrendo.

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
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

Ao rolar pelos resultados, veremos o quão grande é a resposta, quantas entidades ela envolve e quantos níveis foram recuperados, e ainda assim foi executada prontamente, sem nenhuma dificuldade.