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

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

Takahiro Iwasa
Takahiro Iwasa
16 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 タブでグラフを表示でき、ドラッグ、ズームイン、ズームアウトで、グラフをすぐに理解できるようになっています。

    まとめ

    AWS ユーザーは、 Amazon Neptune を利用することで、高可用でコスト効率の高いグラフデータベースを迅速に構築できます。

    この投稿が、お役に立てば幸いです。

    Takahiro Iwasa

    Takahiro Iwasa

    Software Developer at KAKEHASHI Inc.
    Involved in the requirements definition, design, and development of cloud-native applications using AWS. Now, building a new prescription data collection platform at KAKEHASHI Inc. Japan AWS Top Engineers 2020-2023.