Neptune、Neo4jの性能検証

AI.RL.LYsのcursheyです。
今回は[Amazon Neptune](https://aws.amazon.com/jp/neptune/)と[Neo4j](https://neo4j.com/)の性能検証をしてみました。
Neptuneはフルマネージドなグラフデータベースサービスです。AWSの公式ドキュメントによれば、

>数十億のリレーションシップの保存とミリ秒台のレイテンシーでのグラフのクエリに最適化された、専用の高パフォーマンスグラフデータベースエンジンです。

とあります。
一方Neo4jは特に人気のあるGraphDBで、処理性能、柔軟性、スケーラビリティに優れています。また、関連性に基づいたレコメンデーションなど、様々な場面に活用されています。
この２つのGraphDBが、実際にどのくらいのパフォーマンスを出すことができるのかを比較検証してみました。
なお、今回の検証では、Neptuneは以下の設定です。

- DBエンジンのバージョン: 1.0.1.0
- インスタンスタイプ: db.r5.large

gremlinはApache TinkerPop 3.4.1、Pythonは3.6.5で検証をしました。

Neo4jは以下のバージョンとEC2インスタンスに環境を構築しました。

- バージョン: Neo4j Community Edition 3.5.8
- AMI: amzn2-ami-hvm-2.0.20190618-x86_64-gp2
- インスタンスタイプ: r5.xlarge

この環境下でgremlinを動かしたかったのですが、今回構築したNeo4jにApache TinkerPopが最新のバージョンでも対応しておらず、gremlinでNeo4jを動かせなかったので、cypherとPython3.6.5で検証しました。
NeptuneとNeo4jで扱うデータの構造が違うのと、Neptuneはgremlin、Neo4jはcypherで動かしているため、適切な性能比較とはいえませんが、同じ検索結果になるものに対して、それぞれに考察をしたいと思います。


## ノードの取得の検証
オブジェクトの取得と、取得件数のカウントをして比較をしてみました。
また、ここでは検証用のダミーデータとして、ノードを1300個、エッジを300個作成しました。

### 1300個のノードの全取得
gremlin、cypherのオブジェクト取得、カウントはそれぞれ以下で実行しました。

```gremlin:gremlin_get_all_node
g.V().toList()
``` 

```cypher:cypher_get_all_node
MATCH (n) RETURN n AS list
```

```gremlin:gremlin_count_all_node
g.V().count().toList()
``` 

```cypher:cypher_count_all_node
MATCH (n) RETURN COUNT(n) AS list
```

|  |Neptune + gremlin  |Neo4j + cypher  |
|---|---|---|
|オブジェクトの取得時間  |0.11050109863s  | 0.11929879869s  |
|カウントの時間  | 0.00768570899s  | 0.00426340103  |

### Id = 1となるノードのみを取得

gremlin、cypherのオブジェクト取得、カウントはそれぞれ以下で実行しました。

```gremlin:gremlin_get_one_node
g.V('1').toList()
``` 

```cypher:cypher_get_one_node
MATCH (n) WHERE n.id='1' RETURN n AS list
```

```gremlin:gremlin_count_one_node
g.V('1').count().toList()
``` 

```cypher:cypher_count_one_node
MATCH (n) WHERE n.id='1' RETURN COUNT(n) AS list
```

|  |Neptune + gremlin  |Neo4j + cypher  |
|---|---|---|
|オブジェクトの取得時間  | 0.0072423458s  | 0.00723013877s  |
|カウントの時間  | 0.00582981109 s  | 0.00484523773s  |

### 考察
表を見ると、ノードを取得する場合はNeo4j + cypherの方がほんの僅かですが時間がかかっています。Neo4j + cypherの場合、そのノードにひもづくエッジの情報まで取得してしまい、そのために時間がかかってしまっていると考えられます。
一方、取得件数のカウントの場合はNeo4j + cypherの方が早いといえます。これは取得する情報が少なかったためだと考えられます。

## ホップ先のノードの検索
エッジに重みをつけ、それを利用してホップ先のノード検索をした場合の性能検証をしました。
また、ここでは検証用のダミーデータとして、ノードを200000個、エッジは9784個作成しました。
今回の検証ではノードのidが4807となるものに検証をしています。このノードの[次数](https://ja.wikipedia.org/wiki/%E6%AC%A1%E6%95%B0_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96))は249となります。グラフ全体で最大の[次数](https://ja.wikipedia.org/wiki/%E6%AC%A1%E6%95%B0_(%E3%82%B0%E3%83%A9%E3%83%95%E7%90%86%E8%AB%96))は578となります。
この時の次数分布は下記の画像のようになります。x軸は次数、y軸はノード数で、見やすさのため共に対数にしています。

![Degree Distribution.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/287466/c3226083-f0b2-f338-12a4-220eb3621375.png)

### weightを利用した1ホップ先の検索

gremlin、cypherで、それぞれ以下で実行しました。この時の取得件数は229件です。

```gremlin:gremlin_get_one_hop_node
g.V('4807').aggregate('x').outE().filter(__.has('weight',P.gt(0.1))).inV().valueMap().toList()
``` 

```cypher:cypher_get_one_hop_node
MATCH (n)-[r]->(m) WHERE n.id='4807' WITH m, r WHERE r.weight > 0.1 RETURN m AS list
```

|  |Neptune + gremlin  |Neo4j + cypher  |
|---|---|---|
|229件の取得時間 | 0.07600698471s  | 0.10408554077 s  |

### weightを利用した2ホップ先の検索

gremlin、cypherで、それぞれ以下で実行しました。この時の取得件数は1822件です。

```gremlin:gremlin_get_two_hop_node
g.V('4807').aggregate('x').outE().filter(__.has('weight',P.gt(0.1))).inV().aggregate('y').inE().filter(__.has('weight',P.gt(0.3))).outV().valueMap().toList()
``` 

```cypher:cypher_get_two_hop_node
MATCH (n)-[r]->(m)<-[s]-(o) WHERE n.id='4807' WITH r,s,o  WHERE r.weight > 0.1 WITH s,o WHERE s.weight > 0.3 RETURN o AS list
```

|  |Neptune + gremlin  |Neo4j + cypher  |
|---|---|---|
|1822件の取得時間  | 0.58442277908s  | 0.18594036102s  |

### weightを利用した3ホップ先の検索

gremlin、cypherで、それぞれ以下で実行しました。この時の取得件数は220367件です。

```gremlin:gremlin_get_two_hop_node
g.V('4807').aggregate('x').outE().filter(__.has('weight',P.gt(0.1))).inV().aggregate('y').inE().filter(__.has('weight',P.gt(0.3))).outV().aggregate('z').outE().filter(__.has('weight',P.gt(0.5))).inV().valueMap().toList()
``` 

```cypher:cypher_get_two_hop_node
MATCH (n)-[r]->(m)<-[s]-(o)-[t]->(l) WHERE n.id='4807' WITH  r,s,t,l  WHERE r.weight > 0.1 WITH s,t,l WHERE s.weight > 0.3 WITH t,l WHERE t.weight > 0.5 RETURN l AS list
```

|  |Neptune + gremlin  |Neo4j + cypher  |
|---|---|---|
| 220367の取得時間  | 10.8621526241s  | 15.452856493 s  |

### 考察
上記の表を見ると1ホップ先、２ホップ先のノードの取得には大きな時間差はありませんが、３ホップ先になると、Neo4j + cypherの方が大きく時間がかかってしまっています。これは、WITH構文を使うことで取得したノード、エッジ情報の引き継ぎをしていますが、３ホップ先まで引き継ごうとすると、大きなオーバーヘッドを生じているのではないかと考えられます。
また、Neo4jに限らずGraphDBはグラフの複雑が大きくなると、関連するノードの取得にかかる時間が爆発的に大きくなります。一方Neptuneは特定の関連情報を取得することに重点を置いているため、このような性能差が出たと考えられます。

## まとめ
今回の検証ではNeptuneの方が性能が良いと結果が得られました。NeptuneはGraphDBではありますが、大規模なグラフを持つことに特化しており、その中からある特定の関連情報を引き出すところに重点を置いているとのことなので、この結果は妥当だと思います。
NeptuneとNeo4jの使い分けとして、Neptuneはグラフアルゴリズムとして扱うことは想定されていませんが、Neo4jの方はsparkと連携ができるため、Neo4jの方がグラフアルゴリズムには向いています。今回の検証ではグラフアルゴリズムまでは検証していませんが、目的に応じて使い分ける必要があると思います。

## 補足
Neo4jはインデックスが追加でき、Neptuneはインデックスが追加できません。Neo4jの方でインデックスを追加してみましたが、性能に改善がみられなかったため、今回の検証ではスキップしました。

- Neo4j: https://neo4j.com/docs/cypher-manual/current/schema/index/
- Neptune: https://aws.amazon.com/jp/neptune/faqs/

また、Neo4jにはシャーディング機能がありますが、この機能はエンタープライズ版のみで使うことができ、今回はコミュニティ版で検証しましたので、その性能の確認はできませんでした。

- https://neo4j.com/business-edge/whats-in-neo4j-enterprise-edition/