GoConference 2018 Spring で分散グラフデータベース Dgraph について話をしました

こんにちは、インフラエンジニアの齋藤 (@munisystem) です。先日行われた GoConference 2018 Spring にて、Wantedly People で採用している分散グラフデータベースである Dgraph について紹介をさせていただきました。

また弊社からはもうひとり、私の隣の席で働いている泉 (@izumin5210) が最近社内で導入している gRPC と grpc-gateway による高速な microservice 開発の為のツールである grapi の話をさせていただいています。

なぜ Dgraph について発表したのか

ソーシャルグラフを代表とするグラフは Facebook や Twitter のような人と人の間の関係だけにとどまりません。GitHub のリポジトリと依存パッケージ、Medium のストーリーとタグ、Amazon の商品と購入履歴、これらもすべてグラフで表すことができます。現代の Web アプリケーションにおいてデータ間の関係にフォーカスする機会は決して少なくはなく、またサービスに大きな価値を与える重要なファクターでもあるため、これをどうやって保存し活用するのかが鍵となっています。

個々のつながりにフォーカスを当てたデータストアであるグラフデータベースはその解のひとつであるのにも関わらず、プロダクションでの利用の事例をあまり見かけません。その理由として恒常的な書き込みを行うユースケースでのパフォーマンスや、サービスの成長に応じたスケーリングなどの運用上の問題が少なからずあるのではないかと私は考えています。

今回紹介した Dgraph はそれを解決しているプロダクトであり、一種の例として提示したかったというのが大きな理由です。

発表の補足: Dgraph は分散環境でどのようにクエリを処理しているのか

既存のグラフデータベースが抱えていたパフォーマンスの問題を Dgraph はどうやって解決したのかをアーキテクチャから解説する、というのが今回の発表のテーマでした。しかし時間の都合もあり「Dgraph は分散環境でどのようにクエリを処理しているのか」というアーキテクチャを語る上で重要なポイントについて触れることが出来ませんでした。なのでそれについて軽く説明をしたいと思います。

例として以下のようなフレンドグラフを用意しました。

このグラフから「Alice の友達の名前の一覧を取得する」ケースを考えてみましょう。これを Dgraph のクエリ言語である Graph QL+- で表すとこのようになります。

{
  Q(func: uid("0x01")) {
    friend {
      named
    }
  }
}

このクエリに対して Dgraph はおおよそ以下のようなフローを取ります。

1. クエリをパースする
2. friend が割り当てられている Group に対して 0x01 と共に friend をフェッチする命令を送る
3. 命令を受け取った Group のノードは friend と 0x01 から Posting List を取得、Posting をトラバーサルして uid のリストを返す
4. named が割り当てられている Group に対して uid のリストと共に named をフェッチする命令を送る
5. 命令を受け取った Group のノードは named と uid のリストを用いて Posting List のリストを取得、それぞれの Posting をトラバーサルして named の value のリストを返す
6. 結果を join して返す

ここでは重要なポイントであるデータのフェッチに絞って説明します。

friend のフェッチ

スライドでも説明しましたが、データ間の関係を表す Predicate は Group と呼ばれるノードの論理集合に割り当てられます。同種の Predicate は必ず同じ Group に属し、また同じ Group に属するノードは全て同じデータを持つという仕様から、friend の情報はある Group のノードから必ず取得できることが保証されます。
そのためクエリを受け取ったノードは Alice の友達の uid の一覧を取得するべく、friend をホスティングしている Group に対して Alice の uid である 0x01 の friend を返すよう命令を送ります。

命令を受け取った friend をホスティングしている Group のノードは、friend と 0x01 の情報から Posting List を取得します。Posting List は KVS に

(Predicate, Subject) => Posting List

の形で保存されているため、(friend, 0x01) をキーとして Posting List を探します。また Posting List は Subject と Predicate に対応する Posting のリストで、Posting は Predicate とそれに紐づく Subject と Object を内包する…つまり「XはYと友達である」というデータでした。
それによりこの一回のクエリで全ての Alice の友達の uid を取得することができます。

あとは Posting List の全ての Posting をトラバーサルして uid のリスト[0x02, 0x03, 0x04] を作り、呼び出し元のノードに返します。

named のフェッチ

Alice の友達の uid のリストが手に入ったので、今度はこれに紐づく名前を取得します。named をホスティングしている Group に対して今度は uid のリスト [0x02, 0x03, 0x04] と一緒に named を返すように命令を送ります。

命令を受け取ったノードは受け取った uid のリストを使い、

• (named, 0x02)
• (named, 0x03)
• (named, 0x04)

をキーにして KVS からそれぞれの Posting List を取得します。そしたら先ほどと同じようにそれぞれの Posting List の Posting をトラバーサルして、[Bob, Carol, Dave] のリストを作って呼び出し元のノードに返します。

実は Dgraph がデータシャーディングの単位を Predicate にした理由はこの named のフェッチを最適化することにありました。
同種の Predicate が全て単一のノードから手に入る構造にすることで、ネットワークコールを最小限にしているのです。

おわりに

高いスループットを求められる Web アプリケーションで使えるグラフデータベースとして Dgraph を紹介しました。
また、なぜ Wantedly People で Dgraph を採用したのかについては今週末に開催される技術書展4で配布予定の Wantedly Tech Book 4 に詳しく記事を書いています。ぜひお買い求めください。