Graph Database 101

本記事では、グラフデータベースとはそもそも何なのかについて、ソフトウェアエンジニアリングを習いたての人や、他業種からきた人にも伝わる説明を目指してみます。

データベースとは

そもそも、データベースとは何でしょうか。

Web エンジニアであれば、MySQL や PostgreSQL などのリレーショナルデータベース(以下:RDBMS)をよく利用しているでしょう。Memcached や Redis のようなキーバリューストア(以下:KVS)を利用することも多いでしょう。ユースケースによっては、MongoDB や DynamoDB のようなドキュメント指向データベースや、カラム指向データベース、中にはすでに Neo4j などのグラフデータベースを使っているかもしれません。

データベースとは、一言で言うと「データを保存・管理・分析するのに優れたソフトウェア」です。C や C++ や Java で書かれたアプリケーションです。

入力としては、そのデータベースがサポートするあらゆる型のデータです。文字列や数値の他、JSON 型や Blob 型などデータベースによってサポートする型は異なりますが、基本的にはバイト文字列をディスク上に保存します。そして、そのデータに対して、作成や更新、削除といった操作ができる「だけ」のソフトウェアです。

最も単純なデータベース

データを保存するだけであれば、自分で一つの長大なテキストファイルを作成すれば、それは「データベース」と言っても過言では無いでしょう。例えば、ID と文字列で表現した簡単な TODO リストを、一つのテキストファイルで表現したデータベースはこちらです。

$ cat mytodo.db
1,buy milk
2,clean up desk
3,read books

mytodo.db が、ここで作成した「データベース」にあたります。この「データベース」にデータを追加したい場合は、以下のようにすれば良いでしょう。

$ echo "4,go to the gym" >> mytodo.db

データを追加するだけでは物足りないですね。Key が 4 のデータをこちらの「データベース」から取得したい場合は、以下のようにすれば良いでしょう。

$ grep "^4," mytodo.db | cut -d, -f2
go to the gym

これで、データの作成と読み取りができる「データベース」が作成できました。簡単ですね。

なぜデータベースが必要なのか

では、この「データベース」で決済アプリや分析プラットフォーム、自動運転システムや機械学習システムは作れるでしょうか。

実際問題としてアプリケーションを作り始めると、単なるテキストファイルではほとんどのビジネスニーズを満たすことができないことがわかります。なぜなら、世の中のほとんどのサービスでは、まず第一に、「大量のデータ」を分析しないといけないからです。

先ほどの単純なファイルシステムでは、せいぜい数万件のデータまで管理するだけで手一杯でしょう。特定の Key でデータを検索するのにも全てのデータを一つ一つ(計算量 O(N))見ていかなくてはいけないので、検索の時間はデータに伴って線形に増大していきます。リアルタイムで結果を返すどころか、いつまで経っても結果を返さない使えないソフトウェアとして誰も使ってくれません。

データベースに求められること

そこで、まずデータベースは、大量のデータを効率的に検索し作成できるように、データ構造とアルゴリズムを最適化する必要があります。そして、この過程は研究の積み重ねと泥臭い地道なコーディングの積み重ねによって実現されています。インデックスと呼ばれる副次的なデータ構造を作ったり、木構造で表現してみたり、ディスクだけでなくメモリをうまく活用したり、ハードウェアレイヤーで最適化を図ったり。

さらに、大量のデータを保存するとなると、それだけデータの保存場所が必要となってきます。そして、保存場所が増えるほど、お金がかかります。データを保存するコストを最適化する必要もあります。

それだけでなく、開発効率も重要でしょう。検索コストが最適化されており、格安で保存できるような天才的なディスクレイアウトが発明されたとしても、可視化ツールや柔軟なクエリ言語、デバッグ機能がないと誰もそのデータベースを使ってくれないでしょう。

そこで話は終わりません。社会は進展します。ビジネスは拡大します。アプリケーションはその成長と拡大に伴って、スケールしていく必要があります。どんなに開発効率が良くてディベロッパーに人気でも、スケールするための機能に欠けていると、どんどんユーザーは離れていくでしょう。

世の中の大抵のビジネス課題を解決するアプリケーションを作成する場合、「データベース」というアプリケーションには、最適な実行性能からスケール性能、コスト最適化や開発効率など、あらゆる観点で「データを扱う」と言う一点において優れている必要があります。そして、それを実現するためには、研究の成果の応用と、地道なコーディングの積み重ねによる、集合体としての「データベース」が実装され保守されていく必要があるのです。

地上最強のデータベース

では、誰よりも速くデータの検索と作成と更新ができて、ビッグデータをデータ量をものともせず簡単に保存できて、コストパフォーマンスがよく、ビジネスの成長に伴ってよくスケールし、運用保守に手間も暇もかからない、そんな素敵な地上最強のデータベースはあるのでしょうか。

あったら嬉しいですね。でも、私の知る限り、そんな素敵なデータベースは存在しません。そんなものがあったら、データベース業界が崩壊してます。

そこまで人類の叡智は発展していないだけなのか、はたまた世の中のビジネスニーズが複雑すぎるのか、それともその両方かはわかりませんが、全方面において最強のデータベースなんてものは作れません。

そこで、特定の領域に特化して強みを活かしていくことで、百花繚乱なデータベース業界の地図が塗り替えられ続けているのです。

  • 誰よりも速く「検索」できるようことを目指す一方で、「作成・更新」はそれほど速くないデータベース。
  • 誰よりも速く「作成・更新」ができる一方で、「検索」クエリが非常に遅いデータベース。
  • データのモデリングや正規化に時間をかける一方で、一度整合性をとったモデリングをしてしまえば堅牢性の高いアプリケーションが作れるデータベース。
  • スキーマレスを謳い、深く考えずにデータを作成し始められる一方で、データの不均質性(heterogeneity)が増大するにつれてデータの運用が難しくなっていくようなデータベース。
  • いとも簡単に何千台にも水平にスケールする一方で、強い整合性を犠牲にしたデータベース。
  • バッチ処理を苦手とする一方で、データの関係性や相関性を元にしたユースケースを解くことに特化したデータベース。

あらゆる人が、解きたいビジネスニーズや技術上の課題に適したデータベースを開発しているのです。

現実というのは、トレードオフの選択の連続です。データベースの開発においても、同じことが言えます。

どんなデータベースがあるのか

それでは、データベースを分類すると、どのような種類が今まで開発されてきたのでしょうか。

Relational Database

今日、おそらく最も使われている、そして研究上の歴史も長いデータベースは、1970 年に Edgar "Ted" Codd が提唱した リレーショナルデータモデルに基づくデータベースでしょう。まず初めに理論としてのデータモデルが提唱され、その後続々とデータベースが開発されていきました。

データは、リレーション (relation) と呼ばれるタプルの集合体で表現されます。データモデルの表現性が高く、その汎用性に優れ、当時代替案として提唱されたネットワークモデル階層型データモデル などの他のモデル手法を上回り、クエリ言語である SQL の人気も相まって、広く普及しました。

Document Database

その後、2007 年に MongoDB が世の中に出てから、ドキュメント指向データベースが開発され始めました。NoSQL と言うキャッチーなフレーズにも助けられ、それまでの RDBMS に代わる新しい技術としての模索が、アカデミズムでも現場のソフトウェアエンジニアリングでも続けられてきました。

2010 年前後になると、データ量の拡大に伴ってスケール性も重要視されるようになってきており、その時代にもマッチしたのではないでしょうか。ドキュメント指向データベースでは、データの単位である「ドキュメント」が、データ自身とスキーマの両方を表現しています。したがって、一つのデータベースを複数の物理サーバーに水平に分割してスケールさせるアーキテクチャを実現できます。

リレーショナルデータモデルにおけるスキーマの制約が、あらゆる現場のニーズや課題に迅速に機敏に対応していかなくてはいけないスタートアップにとってはむしろ弊害であり、リレーショナルモデルより少ない労力でより簡単にスケールさせられるドキュメント指向データベースの性質が、時代に適っていたのかもしれません。

もちろんドキュメント指向データベースも普及されるにつれて限界や制約が明らかになっていきますが、リレーショナルデータモデル一択ではない価値観と選択肢が提供されたのは、多様化するビジネスニーズを実装していかなくてはいけないソフトウェア産業にとっては僥倖だったのではないでしょうか。

Relational DB v.s. Document DB (?)

リレーショナルデータモデルもドキュメント指向データベースも、どちらが優れているという類のものではありません。解きたい課題によって、求められる要件によって、適切なデータベースを選択していくべきです。

確かに、リレーショナルデータモデルで実装できるアプリケーションは、原理上ドキュメント指向データベースでも実装できるでしょう。その逆もまた然りです。ただし、アプリケーションの応答時間、スケール性能、運用と保守の人的コストを考慮していくと、ケースバイケースで最適解は異なっていきます。

また、現場のメンバーのスキルセットも重要です。リレーショナルデータモデルに詳しい人がいるかどうかは、保守・運用を考えると重要な観点です。

繰り返しになりますが、どちらのデータベースが優れているかという話ではありません。

これは個人の意見ですが、ソフトウェアエンジニアとして、武器は一つでも多い方が実装できるアプリケーションの幅が広がって楽しいでしょう。その意味で、違う種類のデータベースに精通していることは、知的好奇心を満たすだけでなく、キャリアの幅や新しい成果につながるかもしれません。

では、リレーショナルデータモデルとドキュメント指向データベースについて知っていれば十分でしょうか。列指向データベースストリーミングデータベースについてはどうでしょうか。話を広げると時間がつきないので、そろそろグラフデータベースについて話していきます。

グラフデータベース

それでは、漸く本記事の本題に入っていきましょう。

グラフデータベースとは、どんなデータベースでしょうか。

一言で言うと、グラフ理論で表現できる問題を解くのに最適化されたデータベース」 です。

グラフ理論とは、レオンハルト・オイラー が 18 世紀に体系化した数学理論です。「ケーニヒスベルクの7つの橋問題」を証明するために研究を開始したと言われています。

18世紀の初め頃にプロイセン王国の東部、東プロイセンの首都であるケーニヒスベルク(現・ロシア連邦カリーニングラード)という大きな町があった。この町の中央には、プレーゲル川という大きな川が流れており、七つの橋が架けられていた。あるとき町の人が、次のように言った。

「このプレーゲル川に架かっている7つの橋を2度通らずに、全て渡って、元の所に帰ってくることができるか。ただし、どこから出発してもよい」 今までグラフというデータ構造に馴染みの少ない人もいるかもしれませんが、実は世の中の意外と多くの問題・課題は、グラフで表現することができるのです。

代表的なものを挙げてみます。

  • セマンティック Web
    • Web ページを「頂点」、リンクを「辺」として表現すると、Web ページ同士の類似性や相関性、人気のあるページの分析や不正にリンクが貼られたサイトの分析ができる
  • ソーシャルネットワーク
    • Twitter/Facebook で代表される SNS においては、アカウントを「頂点」、フォローを「辺」として表現すると、人間関係や人気の高い有名アカウントの分析ができる
  • 金融トランザクション
    • 銀行や個人の口座を「頂点」、お金の流れを「辺」として表現すると、どこからどこにどのようにお金が流れたか、どれくらいの金額が送金されたかが分析できる。クレジットカードやオンライン決済に応用すると、不正送金や不正アカウントの検出もできる
  • 推薦エンジン
    • EC サイトにおける商品やカテゴリーそしてユーザーを「頂点」、購入履歴のトランザクションを「辺」として表現すると、同じような商品を買うユーザーのクラスタリングや、意外な商品同士を同時に買う相関性の分析ができ、マーケティングや推薦システムに応用できる
  • 地図アプリケーション
    • 地図上の店舗や住居を「頂点」、それらをつなぐ道を「辺」として表現すると、デリバリーサービスの最短経路を導出したり、地域間の人口動態を分析したり、災害マップにおけるシミュレーションに活用できる

そのほかにも、最近ですと ML/AI の文脈で Knowledge GraphContext AI にも応用されていたりと、幅広いビジネスで活用されています。

グラフデータベースを使うと何が嬉しいのか

したがって、「グラフデータベースを何が嬉しいのか」と言う質問に対しては、皆さんが解こうとしているビジネスニーズ、実装しようとしている仕様が「グラフ理論で表現できる問題」であればグラフデータベースが最も適している、と言うことになります。

ソーシャルネットワークの例で考えてみる

一番分かりやすい例ですと、ソーシャルネットワークの設計をイメージしてみましょう。

タイムラインを実装してみると言う課題を与えられた時、どのようなユースケースが思いつきますか?

Twitter を想像してみれば、ユーザー同士の Follower/Followee の関係性であったり、投稿に対する Like であったり、といったビジネス要件に落とし込めるでしょう。それを実現するような仕様を実装していくことになります。

データモデリングに関しては、例えば User テーブルを作って、Follow テーブルにフォローする関係・フォローされる関係を外部キーで表現して、Tweet テーブルにツイートの内容を記録して、といったモデルが思い浮かぶでしょう。

リレーショナルでもモデリングは可能、だが...

正直、リレーショナルデータモデルでモデリングするのは、そこまで難しくありません。特にリレーショナルデータモデルは、モデリング手法に優れているので、基礎さえ知っていればグラフが適した課題でも巧みにモデリングすることができます。

しかし、問題が露見してくるのは実運用が始まってからです

リレーショナルデータモデルで実装したソーシャルネットワークのタイムラインを想像してみましょう。自分のアカウントでログインした時、どのようなタイムラインを見せますか?自分が Follow しているアカウント一覧の、最新の人気のツイートでしょうか。

どのようにモデリングしたかによりますが、まずは User テーブルから自分のアカウント ID で WHERE 句で絞り込んで、次にフォローしているユーザーの一覧を Follow テーブルと JOIN させて、次に Tweet テーブルとフォローしているアカウントの ID を また JOIN させて... どれくらいお気に入りされているかの件数を表示させるために Like テーブルとも JOIN させて...

ここで気づかれたかと思いますが、関連するデータを取得しようとすればするほど、いとも簡単にJOIN が幾重にも重なった複雑なクエリを問い合わせていることに気づくでしょう。

スケール性能に乏しい

クエリを思いつくだけならまだ簡単です。問題は、このクエリをユーザーが満足する時間内に応用しないといけない点です。また、ユーザーが増えていくにしたがってスケールする必要があります。

複数の JOIN を組み合わせた SQL クエリは、往々にして計算コストが高いです。なぜなら、別々のテーブルを取得するために Disk I/O が何度も発生するからです。Disk I/O はメモリアクセスと比較して非常に遅い処理です。JOIN の数が増えれば増えるほど、クエリの応答時間は増大していきます。

フォロワー数が多くなればなるほど、グラフの深度は深くなっていきます。クエリの応答結果が指数関数的に増大してしまっては、ソーシャルネットワークのタイムラインは半永久的にローディング画面を表示させていることでしょう。そうなってしまうと、ユーザーは離れていってしまいます。

グラフデータベースはどう解決するのか

グラフデータベース(ただしグラフネイティブな実装のデータベースの場合)を使うと、一般的にこのような問題はモデリングしやすいだけでなく、データ量の増大に伴ったクエリの応答速度の伸長も高々線形的で済みます。

それはなぜか。

別に魔法があるわけではありません。ディスク上のレイアウトが連結リストのようになっており、関連するデータを高速に探索できるからです。(そしてその他にも、クエリを最適化させるような地道なクエリ実行計画の作成、データを高速に探索するだけでなく書き込めるようにするためのメモリを活用した副次的データ構造の保持、それでいて Fault Tolerancy を失わないためのクラスター構成、などなど...)

ディスク上のレイアウトはデータベースの実装によって異なってきますが、グラフネイティブな実装の場合、「辺と頂点の関係性をディスク上で表現」しており、結果として関連性のあるデータの作成・更新・検索のパフォーマンスが高くなります。

別記事 "Index-free Adjacency Explained" も参考にしてください

グラフデータベースは最強のデータベースか

グラフデータベースは、地上最強のデータベースでしょうか。

そんなことはありません。先に述べた通り、それぞれのデータベースには強みと弱みがあります。それらを適切に理解した上で、ぜひアプリケーションに組み込んでみてください。

一つ言えるのは、グラフデータベースには、RDBMS にも NoSQL にも性質上持つことのできない強みがあります。そして、グラフ理論を適用できる箇所であれば、各段違いのパフォーマンスを発揮できるでしょう。

最後に

最後に、ポジショントークです。

私が所属しているチームで開発している Neo4j AuraDB は、クラウドネイティブなグラフデータベースを運用しています。

Neo4j AuraDB を使ってもらえば、自分達で運用するコストも減らせるし、クラウドで容易にスケールもしますし、アプリケーションの開発に専念することができます。分析ツールとしての Neo4j Browser や可視化ツールとしての Neo4j Broom も利用できますし、neo4j-graphql を利用するとバックエンドの Resolver を書くことなく Neo4j に格納しているデータにアクセスできる GraphQL アプリケーションを素早く実装することができます。

ぜひ使ってみてください。感想お待ちしております。

2022-03-21