適切なパスを見つける問題を解決するための JanusGraph グラフ DBMS の適用性をテストする実験

こんにちは、みんな。 私たちはオフライントラフィック分析のための製品を開発しています。 このプロジェクトには、地域間の訪問者のルートの統計分析に関連するタスクがあります。

このタスクの一環として、ユーザーは次のタイプのシステム クエリを実行できます。

• エリア「A」からエリア「B」に通過した訪問者の数。
• エリア「A」からエリア「C」を経由し、エリア「D」を経由してエリア「B」に移動した訪問者の数。
• 特定のタイプの訪問者がエリア「A」からエリア「B」に移動するのにどれくらい時間がかかりましたか。

および同様の分析クエリが多数あります。

エリア間の訪問者の移動は有向グラフです。 インターネットを読んでいると、グラフ DBMS は分析レポートにも使用されていることがわかりました。 私は、グラフ DBMS がそのようなクエリにどのように対処するかを知りたいと思っていました (TL; DR; 不完全に）。

DBMS を使用することにしました ヤヌスグラフは、グラフ オープンソース DBMS の傑出した代表として、成熟したテクノロジのスタックに依存しており、(私の意見では) まともな操作特性を提供するはずです。

• BerkeleyDB ストレージ バックエンド、Apache Cassandra、Scylla。
• 複雑なインデックスは Lucene、Elasticsearch、Solr に保存できます。

JanusGraph の作成者は、JanusGraph が OLTP と OLAP の両方に適していると書いています。

私は BerkeleyDB、Apache Cassandra、Scylla、ES を使ってきました。これらの製品は私たちのシステムでよく使用されているため、このグラフ DBMS のテストについては楽観的でした。 RocksDB ではなく BerkeleyDB を選択するのは奇妙に感じましたが、おそらくトランザクション要件によるものです。 いずれの場合でも、スケーラブルな製品の使用のためには、Cassandra または Scylla のバックエンドを使用することをお勧めします。

Neo4j は考慮しませんでした。クラスタリングには商用バージョンが必要です。つまり、この製品はオープンソースではないからです。

グラフ DBMS は、「グラフに見える場合は、グラフのように扱います。」と言います。 - 美しさ！

まず、グラフ DBMS の規範に従って正確に作成されたグラフを描きました。

本質はあるよ Zone, エリアの責任者です。 もし ZoneStep これに属します Zone、そして彼はそれを参照します。 本質について Area, ZoneTrack, Person 注意しないでください。これらはドメインに属しており、テストの一部とはみなされません。 このようなグラフ構造のチェーン検索クエリは、全体として次のようになります。

g.V().hasLabel('Zone').has('id',0).in_()
       .repeat(__.out()).until(__.out().hasLabel('Zone').has('id',19)).count().next()

ロシア語では次のようになります。ID=0 のゾーンを見つけ、エッジがそこに向かうすべての頂点 (ZoneStep) を取得し、ゾーンへのエッジがある ZoneStep が見つかるまで戻らずに踏みつけます。 ID=19、そのようなチェーンの数を数えます。

私はグラフ検索の複雑さをすべて知っているつもりはありませんが、このクエリはこの本に基づいて生成されました (https://kelvinlawrence.net/book/Gremlin-Graph-Guide.html).

BerkeleyDB バックエンドを使用して、長さ 50 ～ 3 ポイントの 20 トラックを JanusGraph グラフ データベースにロードし、次に従ってインデックスを作成しました。 管理.

Python ダウンロード スクリプト:

from random import random
from time import time

from init import g, graph

if __name__ == '__main__':

    points = []
    max_zones = 19
    zcache = dict()
    for i in range(0, max_zones + 1):
        zcache[i] = g.addV('Zone').property('id', i).next()

    startZ = zcache[0]
    endZ = zcache[max_zones]

    for i in range(0, 10000):

        if not i % 100:
            print(i)

        start = g.addV('ZoneStep').property('time', int(time())).next()
        g.V(start).addE('belongs').to(startZ).iterate()

        while True:
            pt = g.addV('ZoneStep').property('time', int(time())).next()
            end_chain = random()
            if end_chain < 0.3:
                g.V(pt).addE('belongs').to(endZ).iterate()
                g.V(start).addE('goes').to(pt).iterate()
                break
            else:
                zone_id = int(random() * max_zones)
                g.V(pt).addE('belongs').to(zcache[zone_id]).iterate()
                g.V(start).addE('goes').to(pt).iterate()

            start = pt

    count = g.V().count().next()
    print(count)

SSD 上に 4 コアと 16 GB RAM を搭載した VM を使用しました。 JanusGraph は次のコマンドを使用してデプロイされました。

docker run --name janusgraph -p8182:8182 janusgraph/janusgraph:latest

この場合、完全一致検索に使用されるデータとインデックスは BerkeleyDB に保存されます。 先ほどのリクエストを実行すると、数十秒の時間を受け取りました。

上記の 4 つのスクリプトを並行して実行することで、Docker ログに Java スタックトレース (そして私たちは皆、Java スタックトレースを読むのが大好きです) の陽気なストリームを備えたカボチャに DBMS を変えることができました。

少し考えた結果、グラフ図を次のように単純化することにしました。

エンティティ属性による検索の方が、エッジによる検索よりも高速であると判断します。 その結果、私のリクエストは次のようになりました。

g.V().hasLabel('ZoneStep').has('id',0).repeat(__.out().simplePath()).until(__.hasLabel('ZoneStep').has('id',19)).count().next()

ロシア語では次のようになります。ID=0 の ZoneStep を見つけて、ID=19 の ZoneStep が見つかるまで戻らずに踏み続け、そのようなチェーンの数を数えます。

また、不要な接続を作成しないように、属性に限定して上記の読み込みスクリプトを簡素化しました。

リクエストが完了するまでにまだ数秒かかりましたが、いかなる種類のアドホック リクエストの目的にもまったく適していないため、これは私たちのタスクとしてはまったく受け入れられませんでした。

最速の Cassandra 実装として Scylla を使用して JanusGraph をデプロイしようとしましたが、これも大きなパフォーマンスの変化にはつながりませんでした。

そのため、「グラフのように見える」にもかかわらず、グラフ DBMS に高速に処理させることができませんでした。 何かわからないことがあり、JanusGraph を使えばほんの一瞬でこの検索を実行できるだろうと十分に想定していましたが、私にはそれができませんでした。

この問題はまだ解決する必要があるため、テーブルの JOIN とピボットについて考え始めました。これは、優雅さの点で楽観的な見方を刺激するものではありませんでしたが、実際には完全に実行可能なオプションである可能性があります。

私たちのプロジェクトではすでに Apache ClickHouse を使用しているため、この分析 DBMS で研究をテストすることにしました。

簡単なレシピを使用して ClickHouse をデプロイします。

sudo docker run -d --name clickhouse_1 
     --ulimit nofile=262144:262144 
     -v /opt/clickhouse/log:/var/log/clickhouse-server 
     -v /opt/clickhouse/data:/var/lib/clickhouse 
     yandex/clickhouse-server

次のようにデータベースとその中にテーブルを作成しました。

CREATE TABLE 
db.steps (`area` Int64, `when` DateTime64(1, 'Europe/Moscow') DEFAULT now64(), `zone` Int64, `person` Int64) 
ENGINE = MergeTree() ORDER BY (area, zone, person) SETTINGS index_granularity = 8192

次のスクリプトを使用してデータを入力しました。

from time import time

from clickhouse_driver import Client
from random import random

client = Client('vm-12c2c34c-df68-4a98-b1e5-a4d1cef1acff.domain',
                database='db',
                password='secret')

max = 20

for r in range(0, 100000):

    if r % 1000 == 0:
        print("CNT: {}, TS: {}".format(r, time()))

    data = [{
            'area': 0,
            'zone': 0,
            'person': r
        }]

    while True:
        if random() < 0.3:
            break

        data.append({
                'area': 0,
                'zone': int(random() * (max - 2)) + 1,
                'person': r
            })

    data.append({
            'area': 0,
            'zone': max - 1,
            'person': r
        })

    client.execute(
        'INSERT INTO steps (area, zone, person) VALUES',
        data
    )

挿入はバッチで行われるため、入力は JanusGraph よりもはるかに高速でした。

JOIN を使用して XNUMX つのクエリを作成しました。 ポイント A からポイント B に移動するには:

SELECT s1.person AS person,
       s1.zone,
       s1.when,
       s2.zone,
       s2.when
FROM
  (SELECT *
   FROM steps
   WHERE (area = 0)
     AND (zone = 0)) AS s1 ANY INNER JOIN
  (SELECT *
   FROM steps AS s2
   WHERE (area = 0)
     AND (zone = 19)) AS s2 USING person
WHERE s1.when <= s2.when

3 つのポイントを確認するには:

SELECT s3.person,
       s1z,
       s1w,
       s2z,
       s2w,
       s3.zone,
       s3.when
FROM
  (SELECT s1.person AS person,
          s1.zone AS s1z,
          s1.when AS s1w,
          s2.zone AS s2z,
          s2.when AS s2w
   FROM
     (SELECT *
      FROM steps
      WHERE (area = 0)
        AND (zone = 0)) AS s1 ANY INNER JOIN
     (SELECT *
      FROM steps AS s2
      WHERE (area = 0)
        AND (zone = 3)) AS s2 USING person
   WHERE s1.when <= s2.when) p ANY INNER JOIN
  (SELECT *
   FROM steps
   WHERE (area = 0)
     AND (zone = 19)) AS s3 USING person
WHERE p.s2w <= s3.when

もちろん、このリクエストは非常に恐ろしいものに見えますが、実際に使用するには、ソフトウェア ジェネレーター ハーネスを作成する必要があります。 しかし、彼らは仕事をしており、素早く仕事をします。 最初と 0.1 番目のリクエストは両方とも 3 秒未満で完了します。 以下は、XNUMX つのポイントを通過する count(*) のクエリ実行時間の例です。

SELECT count(*)
FROM 
(
    SELECT 
        s1.person AS person, 
        s1.zone AS s1z, 
        s1.when AS s1w, 
        s2.zone AS s2z, 
        s2.when AS s2w
    FROM 
    (
        SELECT *
        FROM steps
        WHERE (area = 0) AND (zone = 0)
    ) AS s1
    ANY INNER JOIN 
    (
        SELECT *
        FROM steps AS s2
        WHERE (area = 0) AND (zone = 3)
    ) AS s2 USING (person)
    WHERE s1.when <= s2.when
) AS p
ANY INNER JOIN 
(
    SELECT *
    FROM steps
    WHERE (area = 0) AND (zone = 19)
) AS s3 USING (person)
WHERE p.s2w <= s3.when

┌─count()─┐
│   11592 │
└─────────┘

1 rows in set. Elapsed: 0.068 sec. Processed 250.03 thousand rows, 8.00 MB (3.69 million rows/s., 117.98 MB/s.)

IOPS に関する注意事項。 データを取り込むとき、JanusGraph はかなり高い IOPS (1000 つのデータ取り込みスレッドで 1300 ～ XNUMX) を生成し、IOWAIT はかなり高かった。 同時に、ClickHouse はディスク サブシステムに最小限の負荷を生成しました。

まとめ

このタイプのリクエストには ClickHouse を使用することにしました。 ClickHouse にロードする前に Apache Flink を使用してイベント ストリームを前処理することで、マテリアライズド ビューと並列化を使用してクエリをさらに最適化することができます。

パフォーマンスが非常に優れているため、プログラムによるテーブルのピボットについて考える必要すらなくなるでしょう。 以前は、Apache Parquet へのアップロードを介して Vertica から取得したデータのピボットを行う必要がありました。

残念ながら、グラフ DBMS を使用する別の試みは失敗しました。 JanusGraph には、この製品を簡単に理解できるフレンドリーなエコシステムがあるとは思えませんでした。 同時に、サーバーの設定には従来の Java の方法が使用されるため、Java に詳しくない人は血の涙を流すことになります。

host: 0.0.0.0
port: 8182
threadPoolWorker: 1
gremlinPool: 8
scriptEvaluationTimeout: 30000
channelizer: org.janusgraph.channelizers.JanusGraphWsAndHttpChannelizer

graphManager: org.janusgraph.graphdb.management.JanusGraphManager
graphs: {
  ConfigurationManagementGraph: conf/janusgraph-cql-configurationgraph.properties,
  airlines: conf/airlines.properties
}

scriptEngines: {
  gremlin-groovy: {
    plugins: { org.janusgraph.graphdb.tinkerpop.plugin.JanusGraphGremlinPlugin: {},
               org.apache.tinkerpop.gremlin.server.jsr223.GremlinServerGremlinPlugin: {},
               org.apache.tinkerpop.gremlin.tinkergraph.jsr223.TinkerGraphGremlinPlugin: {},
               org.apache.tinkerpop.gremlin.jsr223.ImportGremlinPlugin: {classImports: [java.lang.Math], methodImports: [java.lang.Math#*]},
               org.apache.tinkerpop.gremlin.jsr223.ScriptFileGremlinPlugin: {files: [scripts/airline-sample.groovy]}}}}

serializers:
# GraphBinary is here to replace Gryo and Graphson
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GraphBinaryMessageSerializerV1, config: { ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistry] }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GraphBinaryMessageSerializerV1, config: { serializeResultToString: true }}
  # Gryo and Graphson, latest versions
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GryoMessageSerializerV3d0, config: { ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistry] }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GryoMessageSerializerV3d0, config: { serializeResultToString: true }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GraphSONMessageSerializerV3d0, config: { ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistry] }}
  # Older serialization versions for backwards compatibility:
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GryoMessageSerializerV1d0, config: { ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistry] }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GryoMessageSerializerV1d0, config: { serializeResultToString: true }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GryoLiteMessageSerializerV1d0, config: {ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistry] }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GraphSONMessageSerializerGremlinV2d0, config: { ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistry] }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GraphSONMessageSerializerGremlinV1d0, config: { ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistryV1d0] }}
  - { className: org.apache.tinkerpop.gremlin.driver.ser.GraphSONMessageSerializerV1d0, config: { ioRegistries: [org.janusgraph.graphdb.tinkerpop.JanusGraphIoRegistryV1d0] }}

processors:
  - { className: org.apache.tinkerpop.gremlin.server.op.session.SessionOpProcessor, config: { sessionTimeout: 28800000 }}
  - { className: org.apache.tinkerpop.gremlin.server.op.traversal.TraversalOpProcessor, config: { cacheExpirationTime: 600000, cacheMaxSize: 1000 }}

metrics: {
  consoleReporter: {enabled: false, interval: 180000},
  csvReporter: {enabled: false, interval: 180000, fileName: /tmp/gremlin-server-metrics.csv},
  jmxReporter: {enabled: false},
  slf4jReporter: {enabled: true, interval: 180000},
  gangliaReporter: {enabled: false, interval: 180000, addressingMode: MULTICAST},
  graphiteReporter: {enabled: false, interval: 180000}}
threadPoolBoss: 1
maxInitialLineLength: 4096
maxHeaderSize: 8192
maxChunkSize: 8192
maxContentLength: 65536
maxAccumulationBufferComponents: 1024
resultIterationBatchSize: 64
writeBufferHighWaterMark: 32768
writeBufferHighWaterMark: 65536
ssl: {
  enabled: false}

私は誤って JanusGraph の BerkeleyDB バージョンを「置く」ことに成功しました。

インデックスを管理するには、Groovy でかなり奇妙なシャーマニズムを実行する必要があるため、ドキュメントはインデックスに関してかなり歪んでいます。 たとえば、インデックスの作成は、Gremlin コンソールでコードを記述して行う必要があります (ちなみに、これはそのままでは機能しません)。 JanusGraph の公式ドキュメントから:

graph.tx().rollback() //Never create new indexes while a transaction is active
mgmt = graph.openManagement()
name = mgmt.getPropertyKey('name')
age = mgmt.getPropertyKey('age')
mgmt.buildIndex('byNameComposite', Vertex.class).addKey(name).buildCompositeIndex()
mgmt.buildIndex('byNameAndAgeComposite', Vertex.class).addKey(name).addKey(age).buildCompositeIndex()
mgmt.commit()

//Wait for the index to become available
ManagementSystem.awaitGraphIndexStatus(graph, 'byNameComposite').call()
ManagementSystem.awaitGraphIndexStatus(graph, 'byNameAndAgeComposite').call()
//Reindex the existing data
mgmt = graph.openManagement()
mgmt.updateIndex(mgmt.getGraphIndex("byNameComposite"), SchemaAction.REINDEX).get()
mgmt.updateIndex(mgmt.getGraphIndex("byNameAndAgeComposite"), SchemaAction.REINDEX).get()
mgmt.commit()

後書き

ある意味、上記の実験は温かいものと柔らかいものの比較です。 考えてみると、グラフ DBMS は同じ結果を得るために他の操作を実行します。 ただし、テストの一環として、次のようなリクエストを伴う実験も実施しました。

g.V().hasLabel('ZoneStep').has('id',0)
    .repeat(__.out().simplePath()).until(__.hasLabel('ZoneStep').has('id',1)).count().next()

歩行距離を反映します。 しかし、そのようなデータであっても、グラフ DBMS は数秒を超える結果を表示しました...これは、もちろん、次のようなパスがあったという事実によるものです。 0 -> X -> Y ... -> 1、グラフエンジンもチェックしました。

次のようなクエリの場合でも、

g.V().hasLabel('ZoneStep').has('id',0).out().has('id',1)).count().next()

XNUMX 秒未満の処理時間では生産的な応答を得ることができませんでした。

この話の教訓は、美しいアイデアや模範的なモデリングが望ましい結果をもたらさないということです。これは、ClickHouse の例を使用してはるかに高い効率で実証されています。 この記事で紹介されている使用例は、グラフ DBMS の明らかにアンチパターンですが、そのパラダイムでのモデリングには適しているように見えます。

出所： habr.com