Classmethod Tupl Storage Backend for Titanを用いたグラフの保管と処理

グラフデータベースは、主体と主体（頂点・ノード）の関連性（辺・エッジ）を保管します。ここでは、グラフのごく簡単な例を提示します。

グラフDBとは

グラフは、SNS、ゲーム、マスター・データの一元管理、推薦エンジン、流通、遺伝学の研究、詐欺探知・予防、地理・経路計算、ネットワーク・IT管理、ワークフロー管理、Internet-of-Things (IoT)などへの応用が多岐に渡ります。頂点と辺には分類するためのラベルを附することができます。設例では、「人物」にあたる頂点があれば、人気のある品目に相当する頂点もあります。頂点同様、辺には友好関係を示すものもあれば、品目への「ライク」を示すものもあります。有向属性グラフを表現できるグラフ・データベースでは、属性名及び属性値からなる属性で頂点と辺を修飾することができます。一度グラフが作成されると、頂点間の辺を辿っていきます。上のグラフでは、JustinからAnnaから辿ることができ、さらに、AnnaからはBooksへと巡回することができます。

Titanは、数千億個もの頂点を持ち合わせるグラフを保管し処理できる分散型グラフデータベースです。トランザクション性を持ち、同時に大量のクエリに対応できます。

Classmethod Tupl Storage Backend for Titan

Titanはプラグイン型で、グラフの保管には幾つものNoSQLデータベースやKey Value Storeに対応しています。必要な機能と性能を持つデータベースが選択できると同時に、アプリケーションのソース・コードをほとんど変えずに移行できる利点があります。

本日、弊社のClassmethod Tupl Storage Backend for Titanの公開を発表します。データベース・クラスターの構築・運用・維持を単独にしなくても、アマゾンのEC2 やElastic Block Store (EBS)を使えば、どんなに大きなグラフにも対応できます。幾つものEBSボリュームを一つの論理的RAIDに結合することで、小さなグラフでも必要な可用性及びスループットを調整できます。迅速な開発・テストをするために、Classmethod Tupl Storage Backend for Titanは揮発モードも用意しています。裏でClassmethod Tupl Storage Backend for TitanはTupl: The Unnamed Persistence Libraryをグラフの保管に使用します。

Classmethod Tupl Storage Backend for TitanはTitan 1.0.0に対応しています。このバージョンは高速な巡回、有向辺のラベル、頂点分断、頂点のラベル、任意のトランザクション・ログの定義などを実装しています。今回のバックエンドは、Tuplを変えずに実装できました。Tuplを効率よくグラフを保管するのに使っているだけです。

Titan 1.0.0は、グラフ規格TinkerPopのバージョン3.0.1-incubatingに対応しています。TinkerPopは、「グラフ・データベース（OLTP）及びグラフ・アナリティクス（OLAP）のためのグラフ処理枠組み」です。

グラフの話のついでに、上述の概念をグラフに描いてみようと思います。

 

Classmethod Tupl Storage Backend for Titanを使った下記のGremlinスクリプトで、上記のグラフを作成できます。

[gist id="f83a422fec48c2adf7a6"]

ベンチマーク

本Storage Backendとその他のTitan-BerkeleyDB並びにNeo4Jを比較するために、Beis氏、Papadopoulos氏、及びKompatniaris氏の論文にある実験を再現しました。

まず、本Storage Backend、Titan-BerkeleyDB並びにNeo4Jの一括挿入試験（Massive Insertion Workload - MIW）を行いました。MIWでは、頂点と辺を作成した後に一度だけ、コミットを行います。一括挿入なので、施せる工夫はTitanでもNeo4Jでもしておきました。特にTitanでは、任意の頂点識別子を使い、一括処理モードを有効にし、トランザクションを無効にしました。すべてのデータベースでは、辺の作成の所要時間を短縮するために、頂点識別子をキーにした頂点キャッシュを使いました。

一括挿入試験はm4.10xlargeのEC2インスタンスの/dev/shmで行いました。 変数を列の数として、それぞれのデータベースの時間における性能を上記の図に提示しました。所要時間は列の数による線形モデルで近似できるようにみえたので、最小二乗法を用いてそれぞれの性能の線形近似も加えました。列（Column）とは、一つの頂点に関するもの（頂点本体、頂点の属性、辺、ラベル、Titanのインデックス・エントリー）です。TitanはすべてのバックエンドをKCV（Key Column Value）型にはめているので、列と呼びます。今回のスキーマでは、一つの頂点について、頂点本体の列と、頂点識別子を記した属性のカラムと、識別子の属性のインデックスのカラムの3つがあります。辺についても、意図した方向とその逆方向の辺が実際作成されるので、それぞれの辺について2つのコーラムが作成されるとして辺数と頂点数からコーラム数を算出します。一括挿入試験を行った結果、Classmethod Tupl Storage Backend for TitanがTitan-BerkeleyDBより1.5ほど、Neo４JがClassmethod Tupl Storage Backend for Titanよる2.5倍速いことがわかりました。

次に、それぞれのデータベースがMIWで使用する永続ストレージの領域を図りました。

永続ストレージの領域もコーラム数による線形関数であることが伺えます。100万個の列について、Neo4Jは18MiBを、Classmethod Tupl Storage Backend for Titanは27MiBを、Titan-BerkeleyDBは54MiBを要しました。一般論をすれば、Classmethod Tupl Storage Backend for Titanの書き込み性能はTitan BerkeleyDB JE より上がりますが、まだNeo4Jに及びません。

使用開始するには

Classmethod Tupl Storage Backend for TitanはMavenプロジェクトとしてGitHubで公開します。動作環境は、Windows、Mac OS X及びLinux上で稼働でき、Maven及びJava 1.8が必須です。取扱説明の他に、Marvel Universe Social Graphを使った設例を同梱しています。また、Classmethod Tupl Storage Backend for Titan使用のGremlinサーバーをEC2インスタンス上で立ち上げるCloudFormationテンプレートも含まれています。最後に、今回のグラフ・データベース及びその他のグラフ・データベースの性能の理解を深めるために、GitHubにあるgraphdb-benchmarksをTinkerPop 3.0に適格させ、本Classmethod Tupl Storage Backend for Titanを加えました。

-Alex;