🥇 ылайыктуу жолдорду табуу маселесин чечүү үчүн DBMS JanusGraph графасынын колдонулушун текшерүү үчүн эксперимент

Баарына салам. Биз оффлайн трафикти талдоо үчүн продуктуну иштеп чыгуудабыз. Долбоор аймактар боюнча зыяратчылардын жолдорун статистикалык талдоо менен байланышкан тапшырманы камтыйт.

Бул тапшырманын бир бөлүгү катары, колдонуучулар төмөнкү түрдөгү система сурамдарын бере алышат:

"А" аймагынан "Б" аймагына канча зыяратчы өттү;
канча зыяратчы «А» аймагынан «В» аймагына «С» аймагы аркылуу, андан ары «D» аймагы аркылуу өткөн;
зыяратчылардын белгилүү бир түрү "А" аймагынан "Б" аймагына канча убакытта барды.

жана ушул сыяктуу бир катар аналитикалык суроолор.

Зыяратчынын аймактар боюнча кыймылы багытталган график. Интернетти окугандан кийин, мен график DBMSs аналитикалык отчеттор үчүн да колдонулаарын билдим. Мен DBMS графиги мындай суроолорду кантип чечерин көргүм келди (TL; DR; начар).

Мен DBMS колдонууну тандадым JanusGraph, графигинин көрүнүктүү өкүлү катары, (менин оюмча) ага татыктуу операциялык мүнөздөмөлөрдү бериши керек болгон жетилген технологиялардын топтомуна таянган ачык булактуу DBMS:

BerkeleyDB сактагычы, Apache Cassandra, Scylla;
татаал индекстерди Lucene, Elasticsearch, Solr ичинде сактоого болот.

JanusGraph авторлору ал OLTP жана OLAP үчүн ылайыктуу деп жазышат.

Мен BerkeleyDB, Apache Cassandra, Scylla жана ES менен иштегем жана бул өнүмдөр биздин системаларыбызда көп колдонулат, ошондуктан мен бул графикти DBMS сынап көрүүгө оптимисттик көз карашта болчумун. Мен RocksDB ордуна BerkeleyDBди тандоону кызык деп таптым, бирок бул транзакциянын талаптарына байланыштуу болсо керек. Кандай болгон күндө да, масштабдуу, продуктту колдонуу үчүн, Кассандра же Скиллада бэксенди колдонуу сунушталат.

Мен Neo4jди эске алган жокмун, анткени кластерлөө коммерциялык версияны талап кылат, башкача айтканда, продукт ачык булак эмес.

График DBMSs мындай дейт: "Эгер ал графикке окшош болсо, анда аны график катары караңыз!" - сулуулук!

Биринчиден, мен графикти сыздым, ал так 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).

Мен JanusGraph графигинин маалымат базасына узундугу 50төн 3 пунктка чейинки 20 миң тректерди BerkeleyDB серверинин жардамы менен жүктөдүм, ылайык индекстерди түздүм. лидерлик.

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 ГБ оперативдүү эс тутуму бар VM колдондук. JanusGraph бул буйрукту колдонуу менен жайгаштырылган:

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

Бул учурда, так дал келген издөөлөр үчүн колдонулган маалыматтар жана индекстер BerkeleyDBде сакталат. Мурда берилген өтүнүчтү аткарып, мен бир нече ондогон секундага барабар убакыт алдым.

Жогорудагы 4 скриптти параллелдүү иштетүү менен, мен ДББЖны Докер журналдарында Java стектрэйстеринин (жана баарыбыз Java стектректерин окуганды жакшы көрөбүз) шайыр агымы бар ашкабакка айландырдым.

Бир аз ойлонуп, мен график диаграммасын төмөндөгүдөй жөнөкөйлөштүрүү чечимин кабыл алдым:

Объект атрибуттары боюнча издөө четтери боюнча издөөгө караганда тезирээк болот деп чечим кабыл алуу. Натыйжада менин өтүнүчүм төмөндөгүлөргө айланды:

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 сурамдарынын кандайдыр бир түрүндөгү максаттарына такыр ылайыктуу эмес.

Мен JanusGraphти Scylla аркылуу Кассандраны эң ылдам ишке ашырууга аракет кылдым, бирок бул да эч кандай олуттуу өзгөрүүлөргө алып келген жок.

Ошентип, "бул графикке окшош" болгонуна карабастан, мен DBMS графигин аны тез иштетүү үчүн ала алган жокмун. Мен билбеген бир нерсе бар деп ойлойм жана JanusGraph бул издөөнү секунданын бир бөлүгүндө аткарса болот, бирок мен аны кыла алган жокмун.

Маселе дагы эле чечилиши керек болгондуктан, мен JOIN жана таблицалардын Pivots жөнүндө ойлоно баштадым, бул кооздук жагынан оптимизмди шыктандырган жок, бирок иш жүзүндө толугу менен ишке ашуучу вариант боло алат.

Биздин долбоор мурунтан эле 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 аркылуу эки суроо түзүлдү. А чекитинен В чекитине өтүү үчүн:

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) жана IOWAIT абдан жогору болгон. Ошол эле учурда, ClickHouse диск подсистемасына минималдуу жүктү жаратты.

жыйынтыктоо

Бул түрдөгү сурамдарды тейлөө үчүн ClickHouse колдонууну чечтик. Биз ар дайым суроо агымын ClickHouseга жүктөөдөн мурун Apache Flink аркылуу алдын ала иштетип, материалдаштырылган көрүнүштөрдү жана параллелизацияны колдонуп, андан ары оптималдаштыра алабыз.

Аткаруу абдан жакшы болгондуктан, биз үстөлдөрдү программалык түрдө айландыруу жөнүндө ойлонбой деле калабыз. Мурда биз Verticaдан алынган маалыматтарды Apache Parquetге жүктөө аркылуу буруш керек болчу.

Тилекке каршы, 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()

Мен бир секундага жетпеген убакытта жемиштүү жооп ала алган жокмун.

Окуянын моралдык жагы - кооз идея жана парадигматикалык моделдөө каалаган натыйжага алып келбейт, бул ClickHouse мисалында алда канча жогорку натыйжалуулук менен көрсөтүлөт. Бул макалада келтирилген колдонуу учуру, алардын парадигмасында моделдөө үчүн ылайыктуу көрүнгөнү менен, DBMS графиктери үчүн так анти-үлгү болуп саналат.

Source: www.habr.com

Ылайыктуу жолдорду табуу маселесин чечүү үчүн JanusGraph графигин DBMS колдонуу мүмкүнчүлүгүн сынаган эксперимент

жыйынтыктоо

аягы