グラフデータベース紹介 - Amazon Neptune と Gremlin を使用したつながりのトラバーサル

グラフデータベース紹介 - Amazon Neptune と Gremlin を使用したつながりのトラバーサル

Takahiro Iwasa
(岩佐 孝浩)
Takahiro Iwasa (岩佐 孝浩)
15 min read
Graph Database Neptune

AWS のグラフデータベースを紹介する勉強会を開催しました。「雲勉@オンライン【勉強会】Graph Database 入門 ~Amazon Neptune によるデータの「つながり」探索~【開発エンジニア向け】」

プレゼンテーションの内容を紹介し、グラフデータベースと Amazon Neptune を知るきっかけになれば幸いです。この投稿のサンプルは、 GitHub リポジトリから取得できます。

前提条件

参加者は以下が期待されます:

  • グラフデータベースと Amazon Neptune に興味を持っていること
  • RDB と AWS の基本知識

この投稿の目標:

  • グラフデータベースと Amazon Neptune の概要把握
  • Apache TinkerPop Gremlin を使用したトラバーサルのデモ

グラフデータベース概要

概念と技術用語

グラフデータベースは、データ内の関係を保存およびクエリすることに最適化されています。リレーショナルデータベース (RDB) や NoSQL データベースも関係の保存とクエリは可能ですが、特定のユースケースにおいて性能と拡張性の点でグラフデータベースのほうが適しています。グラフデータベースは数学的なグラフ理論の原則に基づいており、それに対してリレーショナルデータベースは集合論に基づいています。

グラフデータベースでは、データは頂点 (vertices) またはノード (nodes) として表現され、それらの間の関係はエッジ (edges) として表現されます。頂点とエッジにはラベルが付けられることがあります。エッジには有向無向の2種類があります。頂点とエッジがキーと値のペアを持つことができるグラフは、プロパティグラフ (property graph) と呼ばれます。

代表的なグラフ

Social Network グラフ

グラフデータベースは、 Facebook, LinkedIn などの SNS に見られるような人との関係を表現するためによく使用されます。

ナレッジグラフ

データを文脈で理解することにより、検索エンジンは同じ名前を共有する異なる概念を区別できます。たとえば、「りんご」という果物とテクノロジー企業の「Apple Inc.」などです。ナレッジグラフの用語は、 “Introducing the Knowledge Graph: things, not strings” の公開以来、一般的になりました。

Identity グラフ

グラフデータベースは、異なる ID 間の関係を表現するためにも使用できます。たとえば、複数のサイトやデバイスでのユーザーの行動を単一のユーザーに関連付けるなどがあります。これにより、ユーザーの行動分析が可能になります。これに関連するよく知られたユースケースの一例が Customer 360 です。

Fraud グラフ

不正活動に共同参加する Fraud Rings を構成し、一部に合法的な取引を含めることで、詐欺行為を検出するのを難しくすることがあります。グラフデータベースは、クレジットカード番号、電話番号、社会保障番号などの共通の属性のような Fraud Rings で共有されるパターンを特定することにより、詐欺行為を容易に視覚化するのに役立つことがあります。

パナマ文書

最近では、グラフデータベースの多くのユースケースがありますが、その中でも最も有名なものの一つがパナマ文書です。2016年に、パナマの法律事務所から大量の内部文書が流出しました。国際調査ジャーナリスト連合 (ICIJ) は、データの分析にグラフデータベースを使用しました。

RDB および NoSQL との比較

ユースケースに応じて異なるデータベースを使用することは非常に重要です。基本的に、単一のタイプのデータベースに頼るべきではありません。

ItemGraph DBRDBNoSQL
データ構造GraphTable様々
(Document, Key-Value, etc.)
スキーマ定義緩い厳格緩い
目的エンティティ間の関係保存エンティティの保存様々
(Primary data storage, caching, etc.)
関連データのクエリTraversalJoin/Sub Query様々
パフォーマンス非常に高い平均
(他と比べて)
非常に高い
言語Gremlin
SPARQL
openCypher
Cypher (Neo4j)
GQL
SQL-

RDB のパフォーマンスは、 Amazon Redshift のような列指向データベースを使用することで向上する可能性があります。

Amazon Neptune は現在、プロダクション環境で openCypher をサポートしています。 Cypher と GQL はサポートされていないことに留意してください。

Starting with engine release 1.1.1.0, openCypher is available for production use in Neptune.

RDB におけるツリー構造

以下のモデルを使用して、 RDB でツリーを表現できます。一部のケースでは、グラフデータベースは必要ないかもしれません。ただし、 Naive Tree は多くの場合、最適でないことに注意が必要です。これに関する詳細は “SQL Antipatterns” に記載されています。

ModelDescriptionProsCons
ナイーブツリーt1.id = t2.parent_idシンプルな実装 (隣接リスト)
  • 直近のノード以外の抽出が困難
  • 複雑な SQL
  • 低パフォーマンス
  • パス列挙path LIKE ‘1/2%’直近のノード以外の抽出が容易
  • INSERT/UPDATE/DELETE が複雑
  • カラム最大長の制約を受ける
  • 入れ子集合Left > 1 AND right < 6直近のノード以外の抽出が容易
  • INSERT/UPDATE が複雑
  • カラム最大長の制約を受ける
  • 直感的とは言えないデータ構造
  • 閉包テーブルツリーのためのテーブル
  • 直近のノード以外の抽出が容易
  • INSERT/UPDATE/DELETE が容易
  • データ増大の可能性
  • INSERT/UPDATE/DELETE の低パフォーマンス
  • Amazon Neptune 概要

    Amazon Neptune は、フルマネージドのグラフデータベースサービスで、ミリ秒単位で数十億のリレーションシップをクエリできます。 Aurora と同様に高い可用性、耐久性、低遅延を提供します。価格については、公式ページをご参照ください。

    クラスターの機能は次のとおりです。

    FeatureDescription
    プライマリインスタンス1
    リードレプリカインスタンス最大15
    レプリケーション遅延大抵の場合において 100ms 未満
    フェイルオーバーリードレプリカ昇格

    ストレージの機能は次のとおりです。

    FeatureDescription
    ボリュームクラスターを跨いで一つの論理ボリューム
    冗長性3AZ に 6つのコピー
    サイズ64TiB まで自動でスケール

    クエリ環境

    様々な SDK を使用して、グラフをクエリできます。例えば、 Gremlin-Java, Gremlin-Python, Gremlin-JavaScript などがあります。また、 REST API も利用可能です。

    AWS は、 Neptune Workbench というフルマネージドの環境を提供しています。 これには、 Graph Notebook が事前にインストールされており、 Gremlin クエリを実行しグラフを可視化できます。また、自分のローカル環境でグラフノートブックを起動することもできます。

    トランザクション

    Dirty Read

    Tx1 が行を更新し、 Tx2 がその行を読み取り、 Tx1 が失敗またはロールバックした場合、 Tx2 は反映されていないデータを読み取ったことになります。

    Non-repeatable Read

    Tx1 が行を読み取り、 Tx2 がその行を更新または削除してコミット、 Tx1 がその行を読み取ると、 Tx1 は以前の結果と異なるコミットされたデータを読み取ります。

    Phantom Read

    Tx1 が複数行を読み取り、 Tx2 がいくつかの行を挿入または削除してコミット、 Tx1 が再度複数行を読み取ると、 Tx1 は以前の結果と異なる行を読み取ります。

    分離レベル

    LevelDirtyNon-repeatablePhantom
    READ UNCOMMITTEDありえるありえるありえる
    READ COMMITTEDありえないありえるありえる
    REPEATABLE READありえないありえないありえる
    SERIALIZABLEありえないありえないありえない

    Neptune におけるトランザクション

    Neptune は、読み取り専用クエリとミューテーションクエリで、異なるトランザクション分離レベルを使用します。

    読み取り専用クエリに関して、 Neptune は MultiVersion Concurrency Control (MVCC) でスナップショット分離を採用しています。これにより、トランザクションの開始時にスナップショットを取得して、 Dirty read, Non-repeatable read, Phantom read を防ぎます。

    ミューテーションクエリに関して、 Neptune は Dirty read を防ぐために READ COMMITTED 分離を採用しています。さらに、 Neptune はデータの読み取り時にレコードセットをロックして、 Non-repeatable read と Phantom read を防ぎます。

    Gremlin による Traversal

    Gremlin は、 Apache TinkerPop が提供するグラフトラバーサル言語で、 TinkerPop はグラフデータベースのためのオープンソースフレームワークです。

    Gremlin は Start Steps に続いて Traversal Steps を経てトラバースします。 Traversal Steps は、 General StepsTerminal Steps の2つのステップで構成されています。

    サンプルデータ

    この投稿では、以下のデータをサンプルとして使用しています。頂点には age プロパティが含まれ、エッジには頂点間の親密さを表す weight プロパティを含みます。

    もしデータが RDB に格納されている場合、関係データのクエリは難しくなる可能性があります。 SQL クエリは複雑になりがちで、行列のテーブルで関係を表現することは直感的でないかもしれません。

    上記のサンプルデータを以下のコマンドで入力してください。 %%gremlin は、 Neptune Workbench が提供する Jupyter Notebook のマジックコマンドです。

    %%gremlin
    // Drop existing data
    g.V().drop()
    
    %%gremlin
    // Add Vertices
    g.addV('person').property(id, 'A').property('age', 30)
     .addV('person').property(id, 'B').property('age', 25)
     .addV('person').property(id, 'C').property('age', 35)
     .addV('person').property(id, 'D').property('age', 20)
     .addV('person').property(id, 'E').property('age', 18)
     .addV('person').property(id, 'F').property('age', 25)
     .addV('person').property(id, 'G').property('age', 10)
     .addV('person').property(id, 'H').property('age', 15)
    
    %%gremlin
    // Add Edges
    g.V('A').addE('know').to(g.V('B')).property('weight', 1.0)
     .V('A').addE('know').to(g.V('C')).property('weight', 0.9)
     .V('A').addE('know').to(g.V('H')).property('weight', 0.5)
     .V('B').addE('know').to(g.V('D')).property('weight', 0.8)
     .V('B').addE('know').to(g.V('E')).property('weight', 0.4)
     .V('C').addE('know').to(g.V('F')).property('weight', 0.5)
     .V('C').addE('know').to(g.V('G')).property('weight', 0.6)
     .V('D').addE('know').to(g.V('E')).property('weight', 0.7)
     .V('H').addE('know').to(g.V('E')).property('weight', 1.0)
     .V('H').addE('know').to(g.V('G')).property('weight', 1.0)
    

    探索例1

    以下のコマンドで全ての人を探索してみましょう。

    %%gremlin
    // Extract Vertices
    g.V()
     .project(‘id’, ‘properties’) // Projection
     .by(id()).by(valueMap()) // valueMap returns properties of vertices.
    
    RowData
    1{'id': 'A', 'properties': {'age': [30]}}
    2{'id': 'B', 'properties': {'age': [25]}}
    3{'id': 'C', 'properties': {'age': [35]}}
    4{'id': 'D', 'properties': {'age': [20]}}
    5{'id': 'E', 'properties': {'age': [18]}}
    6{'id': 'F', 'properties': {'age': [25]}}
    7{'id': 'G', 'properties': {'age': [10]}}
    8{'id': 'H', 'properties': {'age': [15]}}

    探索例2

    25歳以上で A から2番目までの人を探索してみましょう。

    %%gremlin
    // Extract persons (entities) which are older than 25 years old and connected from A up to 2nd.
    g.V('A’)
     .repeat(outE().inV()).times(2).emit() // Repeat traversal of adjacent vertices twice
     .has(‘age’, gte(25)) // Greater than or equal 25 years old
     .project('id', 'age’)
     .by(id()).by(values('age'))
    
    RowData
    1{'id': 'B', 'age': 25}
    2{'id': 'C', 'age': 35}
    3{'id': 'F', 'age': 25}

    探索例3

    重みの合計が 0.5 よりも大きい人を探索してみましょう。

    %%gremlin
    // Start traversal at A which extracts vertices that have a multiplied weight value greater than 0.5
    g.withSack(1.0f).V(‘A’) // Sack can be used to store temporary data
     // Multiply a weight value of an out-directed edge by a sack value, and traverse all in-directed vertices
     .repeat(outE().sack(mult).by(‘weight’).inV().simplePath()).emit()
     .where(sack().is(gt(0.5))) // A sack value greater than 0.5
     .dedup() // deduplication
     .project('id', 'weight’)
     .by(id).by(sack())
    
    RowData
    1{'id': 'B', 'weight': 1.0}
    2{'id': 'C', 'weight': 0.9}
    3{'id': 'D', 'weight': 0.8}
    4{'id': 'G', 'weight': 0.54}
    5{'id': 'E', 'weight': 0.5599…}

    グラフ可視化

    Neptune Workbench でグラフを可視化できます。

    次のコマンドでグラフを可視化してみましょう。

    %%gremlin -d T.id -de weight
    // -d means that a property to be displayed in vertices
    // -de means that a property to be displayed in edges
    
    // Execute the traversal example 3
    g.withSack(1.0f).V(‘A’) // Sack can be used to store temporary data
     // Multiply a weight value of an out-directed edge by a sack value, and traverse all in-directed vertices
     .repeat(outE().sack(mult).by(‘weight’).inV().simplePath()).emit()
     .where(sack().is(gt(0.5))) // A sack value greater than 0.5
     .dedup() // deduplication
     .path() // Extract path data
     .by(elementMap())
    
    RowData
    1path[{<T.id: 1>: 'A', <T.label: 4>: 'person', 'age': 30}, {<T.id: 1>: '8ebe47fa-901b-c6d3-a11f-0a9bf0ce8aa2', <T.label: 4>: 'know', <Direction.IN: 2>: {<T.id: 1>: 'B', <T.label: 4>: 'person'}, <Direction.OUT: 3>: {<T.id: 1>: 'A', <T.label: 4>: 'person'}, 'weight': 1.0}, {<T.id: 1>: 'B', <T.label: 4>: 'person', 'age': 25}]
    2path[{<T.id: 1>: 'A', <T.label: 4>: 'person', 'age': 30}, {<T.id: 1>: '7abe47fa-901c-c394-4bed-6dce7defa3f9', <T.label: 4>: 'know', <Direction.IN: 2>: {<T.id: 1>: 'C', <T.label: 4>: 'person'}, <Direction.OUT: 3>: {<T.id: 1>: 'A', <T.label: 4>: 'person'}, 'weight': 0.9}, {<T.id: 1>: 'C', <T.label: 4>: 'person', 'age': 35}]

    Graph タブでグラフを表示でき、ドラッグ、ズームイン、ズームアウトで、グラフをすぐに理解できるようになっています。

    Takahiro Iwasa
(岩佐 孝浩)

    Takahiro Iwasa (岩佐 孝浩)

    Software Developer at KAKEHASHI Inc.
    処方箋データ収集基盤の設計・開発・運用に携わっています。