「n+1問題」の抑制

Gato GraphQLがアーキテクチャ設計によって「n+1問題」を完全に回避している仕組みを学びましょう。

​

「n+1問題」とは何か

「n+1問題」とは、基本的に、データベースに対して実行されるクエリの数がグラフのノード数と同じくらい大きくなり得る、という問題です。

どういう意味でしょうか？例を使って確認してみましょう。監督の一覧を取得し、それぞれの監督の映画を以下のクエリで取得したいとします。

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

効率的に処理するためには、データベースからデータを取得するクエリを2回だけ実行することが期待されます。1回目は監督のデータを取得し、2回目はすべての監督のすべての映画のデータを取得します。

しかし、このクエリを満たすために、GraphQLはデータベースに対して「n+1」回のクエリを実行する必要があります。最初にN人の監督（この場合は10人）のリストを取得するために1回、そしてN人の監督それぞれに対して映画のリストを取得するために1回ずつクエリを実行します。この例では、合計1+10=11回のクエリを実行しなければなりません。

この問題が発生するのは、GraphQLのリゾルバーが同じ種類のすべてのオブジェクトをまとめてではなく、1度に1つのオブジェクトしか処理しないためです。この例では、（ルートタイプである）Queryタイプのオブジェクトを処理するリゾルバーがすべてのDirectorオブジェクトのリストを取得するために最初に1回呼び出され、その後Directorタイプを処理するリゾルバーが各Directorオブジェクトに対して1回ずつ呼び出され、それぞれの映画リストを取得します。

つまり、GraphQLのリゾルバーは木を見て森を見ない、ということです。

この問題は最初に見えるよりも実際には深刻です。グラフのノード数はグラフのレベル数に対して指数関数的に増加するからです。したがって、「n+1」という名前は2レベルの深さのグラフにのみ有効です。3レベルの深さのグラフでは、「N²+n+1問題」と呼ぶべきでしょう！そしてそれ以降も同様です。

たとえば、上記の例に続いて、各映画の俳優・女優のリストもクエリに追加してみましょう。

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

この場合、データベースに対して実行されるクエリは次のようになります。まず10人の監督のリストを取得するために1回、次に10人の監督それぞれの映画リストを取得するために1回ずつ、最後に10人の監督それぞれの10本の映画ごとに俳優・女優のリストを取得するために1回ずつ実行されます。これで合計1+10+100=111回のクエリになります。

この動作に気づいた後、「n+1問題」はGraphQLの最大のパフォーマンス上の障害と見なされます。放置すると、数レベルの深さのグラフへのクエリが非常に遅くなり、GraphQLが事実上使い物にならなくなる可能性があります。

​

「n+1問題」の一般的な解決策

「n+1問題」の標準的な解決策は、最初にユーティリティDataLoaderによって提供されました。その戦略は非常にシンプルです。クエリのセグメントの解決を後の段階まで遅延させ、同じ種類のすべてのオブジェクトを1つのクエリでまとめて解決するというものです。この戦略は「バッチ処理」と呼ばれ、「n+1」問題を効果的に解決します。

さらに、DataLoaderはオブジェクトを取得後にキャッシュするため、後続のクエリがすでに読み込まれたオブジェクトを読み込む必要がある場合、実行をスキップしてキャッシュからオブジェクトを取得できます。この戦略は「キャッシング」と呼ばれ、主に「バッチ処理」の上に乗せる最適化です。

​

「バッチ処理/遅延」解決策の問題点

技術的に言えば、「バッチ処理」や「遅延」戦略には何の問題もありません。単純に機能します。

（以降、この戦略を「遅延」とのみ呼びます。）

しかし問題は、この戦略が後付けであるという点です。開発者はまずサーバーを実装し、その後クエリの解決が遅いことに気づいて、遅延メカニズムの導入を決定することがあります。そのため、リゾルバーの実装に余分なステップが生じ、開発プロセスに摩擦が生まれます。さらに、開発者は「遅延」メカニズムの仕組みを理解する必要があるため、実装が本来より複雑になります。

この問題は戦略自体にあるのではなく、GraphQLサーバーがこの機能をアドオンとして提供しているという点にあります。それがなければクエリが非常に遅くなり、GraphQLが事実上使い物にならなくなるにもかかわらずです。

この問題の解決策は明確です。「遅延」戦略はアドオンではなく、GraphQLサーバー自体に組み込まれるべきです。「通常」と「遅延」という2つのクエリ実行戦略を持つのではなく、「遅延」の1つだけにすべきです。そして、開発者が「通常」の方法でリゾルバーを実装していても、GraphQLサーバーが「遅延」メカニズムを実行する必要があります（つまり、余分な複雑さはGraphQLサーバーが担い、開発者は担わない）。

それがまさにGato GraphQLが行っていることです。

​

「遅延」をGraphQLサーバーが実行する唯一の戦略にする

ほとんどのGraphQLサーバーの問題は、オブジェクトタイプ（object、union、interface）をオブジェクトとして解決する責任が、このタスクをデータローディングエンジンに委ねるのではなく、親ノードを処理する際にリゾルバー自身が負っていることです（例：films => directors）。

Gato GraphQLはこの責任をリゾルバーからサーバーのデータローディングエンジンに移し替えます。

1. リゾルバーは親ノードと子ノードの関係を解決する際に、オブジェクトではなくIDを返します
2. 特定のタイプのIDのリストが与えられると、DataLoaderエンティティがそのタイプの対応するオブジェクトを取得します
3. サーバーのデータローディングエンジンがこの2つの部分をつなぐ役割を果たします。最初にリゾルバーからオブジェクトIDを取得し、関係のネストされたクエリを実行する直前（その時点で特定のタイプに対して解決するすべてのIDが蓄積されています）に、DataLoaderを通じてそれらのIDのオブジェクトを取得します（これにより、すべてのIDを1つのクエリに効率的に含めることができます）。

このアプローチは次のように要約できます。「オブジェクトではなくIDで処理する」。

この新しいアプローチを視覚化するために、先ほどの例を使いましょう。以下のクエリは監督とその映画のリストを取得します。

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

各監督から取得する2つのフィールドnameとfilmsに注目し、それらがどのように異なるかを確認してください。

フィールドnameはスカラー型です。Directorタイプのオブジェクトがnameというstring型のプロパティを含んでいることが期待できるため、即座に解決可能です。したがって、Directorオブジェクトを取得したら、このプロパティを解決するために余分なクエリを実行する必要はありません。

一方、フィールドfilmsはオブジェクト型のリストです。通常は即座に解決できません。Filmタイプのオブジェクトのリストを参照しており、1回以上の余分なクエリを通じてデータベースから取得する必要があるためです。そのため、開発者はこのために「遅延」メカニズムを実装する必要があります。

では、別の動作を考えてみましょう。フィールドfilmsをオブジェクトのリストではなくIDのリストとして解決します。Directorオブジェクトがすべての映画のIDを含むfilmIDsというプロパティを持つことが期待できるため（IDが文字列として表現されると仮定して、array of string型）、このフィールドも「遅延」メカニズムを実装することなく即座に解決できます。

最後に、IDに加えて、リゾルバーは期待するオブジェクトのタイプという追加情報を提供する必要があります（この例では[(Film, 2), (Film, 5), (Film, 9)]のようになります）。ただし、この情報は内部的なものであり、エンジンに渡されるだけで、クエリへのレスポンスに出力される必要はありません。

​

適応されたアプローチのコード実装

Gato GraphQLがPHPコードでこのアプローチをどのように実装しているか見てみましょう。以下のコードは異なるリゾルバーを示しています（わかりやすくするため、以下のコードはすべて編集されています）。

​

FieldResolvers

FieldResolversは特定のタイプのオブジェクトを受け取り、そのフィールドを解決します。関係については、解決先のオブジェクトのタイプも示す必要があります。これがそのコントラクトです。

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

実装は次のようになります。

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

プロミス/遅延オブジェクトを処理するロジックを取り除くことで、フィールドauthorを解決するコードがいかにシンプルで簡潔になったかに注目してください。

​

TypeResolvers

TypeResolversは特定のタイプを扱うオブジェクトです。タイプの名前と、そのタイプのオブジェクトを読み込むTypeDataLoaderなどを知っています。

データローディングエンジンはフィールドを解決する際に、特定のTypeResolverクラスからIDを受け取ります。次に、それらのIDのオブジェクトを取得する際に、データローディングエンジンはそれらのオブジェクトを読み込むためにどのTypeDataLoaderオブジェクトを使用するかをTypeResolverに問い合わせます。

コントラクトは次のように定義されています。

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

この例では、クラスUserTypeResolverがUserタイプのデータをクラスUserTypeDataLoaderを通じて読み込む必要があると定義しています。

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

​

TypeDataLoaders

TypeDataLoadersは特定のタイプのIDのリストを受け取り、そのタイプの対応するオブジェクトを返します。これがそのコントラクトです。

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

ユーザーの取得は次のように行われます。

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

​

（本当に）大きなクエリの実行

この戦略が機能することを確認してみましょう。Gato GraphQLのGraphiQLクライアントに移動し、以下のクエリを実行してください。このクエリは10レベルの深さのグラフ（posts => author => posts => tags => posts => comments => author => posts => comments => author）を含んでおり、「n+1問題」が発生していたら適切な時間内に解決できなかったものです。

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

結果をスクロールすると、レスポンスがいかに大きく、どれだけ多くのエンティティを含み、何レベルも取得しているかがわかります。それでも迅速に、何の支障もなく実行されました。