적합한 경로 찾기 문제 해결을 위한 JanusGraph 그래프 DBMS의 적용 가능성을 테스트하는 실험

안녕하세요 여러분. 오프라인 트래픽 분석을 위한 제품을 개발하고 있습니다. 이 프로젝트에는 지역별 방문자 경로에 대한 통계적 분석과 관련된 작업이 있습니다.

이 작업의 일부로 사용자는 다음 유형의 시스템 쿼리를 요청할 수 있습니다.

• "A" 지역에서 "B" 지역으로 얼마나 많은 방문객이 지나갔는지;
• "A" 영역에서 "C" 영역을 거쳐 "B" 영역으로 이동한 다음 "D" 영역을 통과한 방문자 수;
• 특정 유형의 방문자가 "A" 영역에서 "B" 영역으로 이동하는 데 걸린 시간입니다.

그리고 유사한 분석 쿼리가 많이 있습니다.

영역 간 방문자의 이동은 방향성 그래프입니다. 인터넷을 보다가 그래프 DBMS가 분석 보고서에도 활용된다는 사실을 알게 되었습니다. 나는 그래프 DBMS가 그러한 쿼리에 어떻게 대처하는지 보고 싶었습니다.TL; DR; 신통치 않게).

나는 DBMS를 사용하기로 결정했다. 야누스 그래프, (제 생각에는) 적절한 운영 특성을 제공해야 하는 성숙한 기술 스택에 의존하는 그래프 오픈 소스 DBMS의 뛰어난 대표자입니다.

• BerkeleyDB 스토리지 백엔드, Apache Cassandra, Scylla;
• 복잡한 인덱스는 Lucene, Elasticsearch, Solr에 저장할 수 있습니다.

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 백엔드를 사용하여 JanusGraph 그래프 데이터베이스에 길이가 50~3포인트인 20만 개의 트랙을 로드하고 다음에 따라 인덱스를 생성했습니다. 조치.

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개의 코어와 16GB 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을 찾을 때까지 돌아가지 않고 밟고, 그러한 체인의 수를 세어보세요.

또한 불필요한 연결을 생성하지 않고 속성으로 제한하기 위해 위에 제공된 로딩 스크립트를 단순화했습니다.

요청을 완료하는 데 몇 초가 걸렸는데, 이는 어떤 종류의 AdHoc 요청 목적에도 전혀 적합하지 않았기 때문에 우리 작업에 완전히 허용되지 않았습니다.

가장 빠른 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을 사용하여 두 개의 쿼리를 구성했습니다. 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개 지점을 통과하는 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