はじめに
開発部の tasaki です。 依存関係 (dependency) という言葉は「クラスの依存関係」「ライブラリの依存関係」「命令の依存関係」「タスクの依存関係」などなど、コンピュータを扱う上では分野を問わず頻出する用語です。 依存関係はグラフ構造 (dependency graph) として表すことができ、このデータをグラフデータベースである Neo4j に入力しておくことで効率よく関係性を検索できるようになります。
今回は例として jdeps と簡単な Python スクリプトを使って Java のパッケージの依存関係を Neo4j に登録し、クエリ言語である Cypher を用いて依存関係を解析してみます。
動作確認環境
- Debian 9.4 (Linux 4.9.88-1+deb9u1)
- OpenJDK 1.8.0_171
- Python 3.5.3
- Neo4j 3.4.4
- Neo4j Python Driver (neo4j-driver) 1.6.1
- Neo4j Graph Algorithms 3.4.0
Neo4j について
概要
Neo4j はグラフデータベースです。 ここで言う「グラフ」は「棒グラフ」「円グラフ」等の「グラフ」とは異なり、下図のような頂点（節点）と辺からなるデータ構造のことを表します。
図において円で表されているものが頂点、円と円を繋いでいる線（矢印）が辺です。 なお、頂点には vertex, node, point、辺には edge, line など英語での呼称が複数ありますが、Neo4j においては頂点は Node、辺は Relationship と呼ばれています。この記事でもその呼び方に統一します。
例えば Java のパッケージの依存関係を表すグラフを作る場合、パッケージを Node とし、パッケージからパッケージへの依存を Relationship とします。パッケージには依存する側（依存元）と依存される側（依存先）がありこれらを区別できるため、Relationship には方向が存在することになります。
Neo4j のインストール
公式ページの手順に従って Neo4j をインストールします。なお Neo4j には Community Edition と Enterprise Edition がありますが、今回は GPLv3 でライセンスされている Community Edition を使います。
Debian の場合のインストールの流れは以下のようになります。
sudo apt install apt-transport-https curl -L https://debian.neo4j.org/neotechnology.gpg.key | sudo apt-key add - echo 'deb https://debian.neo4j.org/repo stable/' | sudo tee /etc/apt/sources.list.d/neo4j.list sudo apt update sudo apt install neo4j
設定ファイルは /etc/neo4j/neo4j.conf に置かれています（Debian の場合）。例えば localhost 以外からのデータベースへのアクセスを許可したい場合は以下のように設定します。
dbms.connectors.default_listen_address=0.0.0.0
サービスを再起動して設定を反映させます。
sudo systemctl restart neo4j sudo systemctl status neo4j
neo4j が起動した状態で 7474 番ポートにブラウザから HTTP アクセスするとグラフィカルな Web インターフェースが表示されます。
コマンドラインインターフェースである cypher-shell や各プログラミング言語向けのドライバからは 7687 番ポートからアクセスします1。
cypher-shell -a bolt://localhost:7687 -u USERNAME -p PASSWORD
Cypher の基本的な使い方
リレーショナルデータベースを扱う際に SQL をクエリ言語として用いるのと同じく、グラフデータベースにも Cypher というクエリ言語が存在します。公式のドキュメントに Neo4j で使える Cypher 言語のチートシートが用意されています。
例えば、「foo というパッケージが bar というパッケージに依存している」という情報を Neo4j に登録するには以下のようなクエリを発行します。
CREATE (src:Package {name: "foo"})-[dep:PDEPENDS]->(dest:Package {name: "bar"})
RETURN src, dep, dest
cypher-shell やブラウザ上のインターフェースにこのクエリを打ち込むとデータベースにエンティティ（Node および Relationship）が作成されます。
neo4j> CREATE (src:Package {name: "foo"})-[dep:PDEPENDS]->(dest:Package {name: "bar"})
RETURN src, dep, dest;
+-------------------------------------------------------------------+
| src | dep | dest |
+-------------------------------------------------------------------+
| (:Package {name: "foo"}) | [:PDEPENDS] | (:Package {name: "bar"}) |
+-------------------------------------------------------------------+
1 row available after 5 ms, consumed after another 0 ms
Added 2 nodes, Created 1 relationships, Set 2 properties, Added 2 labels
このクエリはエンティティを作成する CREATE 節と結果を返す RETURN 節の 2 つの節（Clause）から構成されています。 CREATE 節で「Package というラベルの付いた Node」2 つと「PDEPENDS 型の Relationship」を作成して互いを関連付けています。 上記の src, dep, dest は変数名であり、名前を付けることでエンティティを同じクエリ内で参照することができます。
ただし、上のように CREATE 節を使ってしまうと同じ処理を複数回実行した際に複数の Node や Relationship が作成されてしまいます。 MERGE 節を使うとパターンにマッチするエンティティがまだ存在しない場合にのみ新しく Node / Relationship が作成されます（いわゆる UPSERT の働きをします）。
MERGE (src:Package {name: "foo"})
MERGE (dest:Package {name: "bar"})
MERGE (src)-[dep:PDEPENDS]->(dest)
RETURN src, dep, dest
Node や Relationship には {name: "foo"} のようにキーと値を持ったスキーマレスなプロパティを与えることができます。
作成したエンティティは MATCH 節によるパターンマッチを使って検索することができます。
neo4j> MATCH (pkg:Package {name: "foo"})
RETURN pkg;
+--------------------------+
| pkg |
+--------------------------+
| (:Package {name: "foo"}) |
+--------------------------+
1 row available after 13 ms, consumed after another 1 ms
Node や Relationship を削除するには DELETE 節を使います。DETACH DELETE で Node を削除すると関連する Relationship も削除されます。 Neo4j 上の全ての Node と Relationship を削除するには以下のクエリを発行します。
neo4j> MATCH (n)
DETACH DELETE n;
0 rows available after 2 ms, consumed after another 0 ms
Deleted 2 nodes, Deleted 1 relationships
Cypher のより詳細な使い方については公式のドキュメントをご参照ください。
Neo4j Python Driver の使い方
プログラムから Neo4j データベースに対してクエリを発行するには各言語用に用意されたドライバを使います。公式に Java, JavaScript, Python, .NET 向けのドライバが提供されており、この記事では Neo4j Python Driver (neo4j-driver) を使います。
pip3 install --user neo4j-driver
以下のようなプログラムを書くとクエリを発行でき、下図のようなグラフが構築されます。クエリ中では $src や $dest のようなプレースホルダを使うことができます。
from neo4j.v1 import GraphDatabase url = 'bolt://localhost:7687' username = 'neo4j' password = 'neo4j' mutation = """ MERGE (src:Package {name: $src}) MERGE (dest:Package {name: $dest}) MERGE (src)-[:PDEPENDS]->(dest) """ db = GraphDatabase.driver(url, auth=(username, password)) with db.session() as session: session.run(mutation, src="foo", dest="bar") session.run(mutation, src="bar", dest="baz") session.run(mutation, src="baz", dest="qux") session.run(mutation, src="bar", dest="foo") session.run(mutation, src="foo", dest="baz")
依存関係を解析する
実行例
ここからは実際に Java のパッケージの依存関係を解析してみます。
Java のパッケージやクラスの依存関係を出力するツールとして JDK 8 以降から付属するツールである jdeps を使います。まず、jdeps の出力を以下のような形式の JSON に変換します2。
{ "依存元1": ["依存先A", "依存先B", "依存先C", ...], "依存元2": ["依存先D", "依存先E", "依存先F", ...], "依存元3": ["依存先G", "依存先H", "依存先I", ...], ... }
この変換を行うスクリプトがこちらです。
その後、この形式の JSON を Neo4j にロードさせる以下のスクリプトを実行します。
例として、Apache Commons DBCP (org.apache.commons:commons-dbcp2:2.5.0) と Java EE 8 API (javax:javaee-api:8.0) の jar（およびその依存 jar）に対し、jdeps と上記の 2 つのスクリプト (jdeps_formatter.py, neo4j_dep.py) を使ってパッケージの依存関係を Neo4j に登録していきます。Java のパッケージを Neo4j の Package Node、依存を PDEPENDS Relationship として表しています。
find /path/to/java -name '*.jar' | while read line do jdeps -cp '/path/to/java/*' -f 'java\..+' "$line" \ | ./jdeps_formatter.py \ | ./neo4j_dep.py -n Package -r PDEPENDS done
指定したパッケージが直接依存しているパッケージの表示
指定したパッケージが依存しているパッケージを表示するには以下のようなクエリを発行します。 これは org.apache.commons.dbcp2 パッケージが直接的に依存しているパッケージを表示する例です。
neo4j> MATCH (src:Package {name:"org.apache.commons.dbcp2"})-[:PDEPENDS]->(dest: Package)
RETURN dest;
+----------------------------------------------------+
| dest |
+----------------------------------------------------+
| (:Package {name: "javax.management"}) |
| (:Package {name: "javax.naming.spi"}) |
| (:Package {name: "javax.naming"}) |
| (:Package {name: "org.apache.commons.logging"}) |
| (:Package {name: "javax.sql"}) |
| (:Package {name: "org.apache.commons.pool2.impl"}) |
| (:Package {name: "org.apache.commons.pool2"}) |
+----------------------------------------------------+
7 rows available after 12 ms, consumed after another 0 ms
指定したパッケージが間接的に依存しているパッケージの表示
* 記号による可変長パターンマッチを使うことで依存関係を再帰的に辿ることができます。
結果の重複を排除するために DISTINCT を使い、大量のパッケージが検索に引っ掛かるおそれがあるため LIMIT で表示する件数を制限しています。
neo4j> MATCH (src:Package {name:"org.apache.commons.dbcp2"})-[:PDEPENDS*]->(dest: Package)
RETURN DISTINCT dest LIMIT 100;
+---------------------------------------------------------+
| dest |
+---------------------------------------------------------+
| (:Package {name: "org.apache.commons.pool2"}) |
| (:Package {name: "org.apache.commons.pool2.impl"}) |
| (:Package {name: "javax.management"}) |
| (:Package {name: "javax.sql"}) |
| (:Package {name: "org.apache.commons.logging"}) |
| (:Package {name: "org.apache.commons.logging.impl"}) |
| (:Package {name: "javax.servlet"}) |
| (:Package {name: "javax.servlet.descriptor"}) |
| (:Package {name: "javax.servlet.annotation"}) |
| (:Package {name: "org.apache.log4j"}) |
| (:Package {name: "org.apache.log"}) |
| (:Package {name: "org.apache.avalon.framework.logger"}) |
| (:Package {name: "javax.naming"}) |
| (:Package {name: "javax.naming.spi"}) |
+---------------------------------------------------------+
14 rows available after 7 ms, consumed after another 3 ms
なお、[:PDEPANDS*1..2]のようにすることで探索の深さを指定することができます。無指定の場合クエリの結果が帰ってくるまで非常に時間がかかる場合があるため適切に深さを指定するとよいでしょう。
指定したパッケージに直接依存しているパッケージの表示
指定したパッケージに依存しているパッケージを表示するには以下のようなクエリを発行します これは javax.sql パッケージに直接的に依存しているパッケージを表示する例です。
neo4j> MATCH (src: Package)-[:PDEPENDS]->(dest: Package {name:"javax.sql"})
RETURN src;
+-----------------------------------------------------------+
| src |
+-----------------------------------------------------------+
| (:Package {name: "javax.persistence.spi"}) |
| (:Package {name: "org.apache.commons.dbcp2"}) |
| (:Package {name: "org.apache.commons.dbcp2.managed"}) |
| (:Package {name: "org.apache.commons.dbcp2.cpdsadapter"}) |
| (:Package {name: "org.apache.commons.dbcp2.datasources"}) |
+-----------------------------------------------------------+
5 rows available after 19 ms, consumed after another 0 ms
指定したパッケージに間接的に依存しているパッケージの表示
* を使って再帰的に依存関係を辿った場合は以下のようになります。
neo4j> MATCH (src: Package)-[:PDEPENDS*]->(dest: Package {name:"javax.sql"})
RETURN DISTINCT src LIMIT 100;
+-----------------------------------------------------------+
| src |
+-----------------------------------------------------------+
| (:Package {name: "org.apache.commons.dbcp2.datasources"}) |
| (:Package {name: "org.apache.commons.dbcp2.cpdsadapter"}) |
| (:Package {name: "org.apache.commons.dbcp2.managed"}) |
| (:Package {name: "org.apache.commons.dbcp2"}) |
| (:Package {name: "javax.persistence.spi"}) |
| (:Package {name: "javax.persistence"}) |
| (:Package {name: "javax.persistence.criteria"}) |
+-----------------------------------------------------------+
7 rows available after 34 ms, consumed after another 0 ms
count 集計関数による件数の取得
件数だけ出力させたい場合は count 集計関数を使います。ここでは重複を排除するために DISTINCT を使っています。
neo4j> MATCH (src:Package {name:"org.apache.commons.dbcp2"})-[:PDEPENDS*]->(dest: Package)
RETURN count(DISTINCT dest);
+----------------------+
| count(DISTINCT dest) |
+----------------------+
| 14 |
+----------------------+
1 row available after 38 ms, consumed after another 0 ms
WHERE による複雑な検索
MATCH 節において WHERE を使うことで正規表現などを使ったより複雑な検索ができます。
以下は正規表現 org\.apache\.commons\..+ にマッチするパッケージから javax\..+ にマッチするパッケージへの直接の依存を表示しています。
neo4j> MATCH (src: Package)-[:PDEPENDS]->(dest: Package)
WHERE src.name =~ 'org\\.apache\\.commons\\..+' AND dest.name =~ 'javax\\..+'
RETURN src, dest LIMIT 100;
+-------------------------------------------------------------------------------------------------------+
| src | dest |
+-------------------------------------------------------------------------------------------------------+
| (:Package {name: "org.apache.commons.logging.impl"}) | (:Package {name: "javax.servlet"}) |
| (:Package {name: "org.apache.commons.pool2.impl"}) | (:Package {name: "javax.management"}) |
| (:Package {name: "org.apache.commons.dbcp2"}) | (:Package {name: "javax.management"}) |
| (:Package {name: "org.apache.commons.dbcp2.managed"}) | (:Package {name: "javax.management"}) |
| (:Package {name: "org.apache.commons.dbcp2"}) | (:Package {name: "javax.naming"}) |
| (:Package {name: "org.apache.commons.dbcp2.cpdsadapter"}) | (:Package {name: "javax.naming"}) |
| (:Package {name: "org.apache.commons.dbcp2.datasources"}) | (:Package {name: "javax.naming"}) |
| (:Package {name: "org.apache.commons.dbcp2"}) | (:Package {name: "javax.naming.spi"}) |
| (:Package {name: "org.apache.commons.dbcp2.cpdsadapter"}) | (:Package {name: "javax.naming.spi"}) |
| (:Package {name: "org.apache.commons.dbcp2.datasources"}) | (:Package {name: "javax.naming.spi"}) |
| (:Package {name: "org.apache.commons.dbcp2"}) | (:Package {name: "javax.sql"}) |
| (:Package {name: "org.apache.commons.dbcp2.managed"}) | (:Package {name: "javax.sql"}) |
| (:Package {name: "org.apache.commons.dbcp2.cpdsadapter"}) | (:Package {name: "javax.sql"}) |
| (:Package {name: "org.apache.commons.dbcp2.datasources"}) | (:Package {name: "javax.sql"}) |
| (:Package {name: "org.apache.commons.dbcp2.managed"}) | (:Package {name: "javax.transaction"}) |
| (:Package {name: "org.apache.commons.dbcp2.managed"}) | (:Package {name: "javax.transaction.xa"}) |
+-------------------------------------------------------------------------------------------------------+
16 rows available after 22 ms, consumed after another 2 ms
指定パッケージから指定パッケージへの依存の最短経路の表示
shortestPath 関数を使うことでグラフ上の最短経路を調べることができます。
以下は org.apache.commons.dbcp2 から javax.servlet.annotation までの依存の経路を表示する例です。
neo4j> MATCH p=shortestPath((src:Package {name:"org.apache.commons.dbcp2"})-[:PDEPENDS*..7]->(dest: Package {name: "javax.servlet.annotation"}))
RETURN p;
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| p |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| (:Package {name: "org.apache.commons.dbcp2"})-[:PDEPENDS]->(:Package {name: "org.apache.commons.logging"})-[:PDEPENDS]->(:Package {name: "org.apache.commons.logging.impl"})-[:PDEPENDS]->(:Package {name: "javax.servlet"})-[:PDEPENDS]->(:Package {name: "javax.servlet.annotation"}) |
+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row available after 33 ms, consumed after another 3 ms
クラスタリング (Neo4j Graph Algorithms)
Neo4j はプラグインによって拡張できるように設計されており、Neo4j Contrib プロジェクトからグラフ構造の解析のためのより高度なアルゴリズムを実装した Neo4j Graph Algorithms というプラグインがリリースされています。
プラグインディレクトリ（neo4j.conf の dbms.directories.plugins で指定されているディレクトリ）にダウンロードした JAR ファイルを置くことでプラグインをインストールできます（以下 Debian の場合）。
sudo mv graph-algorithms-algo-3.4.0.0.jar /var/lib/neo4j/plugins/ sudo vim /etc/neo4j/neo4j.conf # dbms.security.procedures.unrestricted=algo.* を追記 sudo systemctl restart neo4j
例えば algo.louvain.stream プロシージャを呼ぶことによって Louvain アルゴリズムによるクラスタリングが行えます。
neo4j> CALL algo.louvain.stream('Package','PDEPENDS', {})
YIELD nodeId, community
MATCH (pkg:Package)
WHERE id(pkg) = nodeId
RETURN pkg, community ORDER BY community ASC LIMIT 20;
+------------------------------------------------------------------------------------------+
| pkg | community |
+------------------------------------------------------------------------------------------+
| (:Package {name: "org.apache.commons.pool2.proxy"}) | 1 |
| (:Package {name: "net.sf.cglib.proxy"}) | 1 |
| (:Package {name: "org.apache.commons.pool2"}) | 1 |
| (:Package {name: "org.apache.commons.pool2.impl"}) | 1 |
| (:Package {name: "javax.management"}) | 1 |
| (:Package {name: "org.apache.commons.dbcp2.managed"}) | 1 |
| (:Package {name: "org.apache.commons.dbcp2.cpdsadapter"}) | 1 |
| (:Package {name: "org.apache.commons.dbcp2.datasources"}) | 1 |
| (:Package {name: "javax.naming.spi"}) | 1 |
| (:Package {name: "org.apache.commons.dbcp2"}) | 1 |
| (:Package {name: "javax.security.enterprise"}) | 6 |
| (:Package {name: "javax.security.enterprise.authentication.mechanism.http"}) | 6 |
| (:Package {name: "javax.servlet.http"}) | 6 |
| (:Package {name: "javax.faces.webapp"}) | 6 |
| (:Package {name: "javax.el"}) | 6 |
| (:Package {name: "javax.faces"}) | 6 |
| (:Package {name: "javax.faces.application"}) | 6 |
| (:Package {name: "javax.faces.component"}) | 6 |
| (:Package {name: "javax.faces.context"}) | 6 |
| (:Package {name: "javax.faces.convert"}) | 6 |
+------------------------------------------------------------------------------------------+
20 rows available after 27 ms, consumed after another 0 ms
その他、Neo4j Graph Algorithms プラグインにはグラフの中心性やコミュニティの分析、経路探索を行うアルゴリズムが多数定義されています。
おわりに
今回はグラフデータベースである Neo4j を使ってソフトウェアの依存関係を解析してみました。
グラフデータベースについては、グラフ構造を扱うという性質上 Node や Relationship が多数存在する状態で探索の深さを増すと実行時間が爆発的に増加してしまうという難点があります。また Neo4j と Cypher 言語は非常に高機能であり、全てを理解するのはなかなか大変です。
幸い Neo4j のチュートリアルは非常に充実しており、グラフィカルなインターフェースやチートシートも用意されています。 是非試行錯誤しながらグラフデータベースの特性を理解して効率のよい検索ができるよううまく使いこなしてゆきましょう。
採用情報
朝日ネットでは新卒採用・キャリア採用を行っております。
-
Neo4j 独自のバイナリプロトコルである Bolt Protocol が使われているようです。↩
