उपयुक्त पथ खोजने की समस्या को हल करने के लिए जानूसग्राफ ग्राफ डीबीएमएस की प्रयोज्यता का परीक्षण करने वाला एक प्रयोग

नमस्ते। हम ऑफ़लाइन ट्रैफ़िक विश्लेषण के लिए एक उत्पाद विकसित कर रहे हैं। परियोजना में विभिन्न क्षेत्रों में आगंतुक मार्गों के सांख्यिकीय विश्लेषण से संबंधित कार्य है।

इस कार्य के भाग के रूप में, उपयोगकर्ता निम्नलिखित प्रकार के सिस्टम प्रश्न पूछ सकते हैं:

कितने आगंतुक क्षेत्र "ए" से क्षेत्र "बी" तक गए;
कितने आगंतुक क्षेत्र "ए" से क्षेत्र "बी" तक क्षेत्र "सी" से और फिर क्षेत्र "डी" से होकर गुजरे;
एक निश्चित प्रकार के आगंतुक को क्षेत्र "ए" से क्षेत्र "बी" तक यात्रा करने में कितना समय लगा।

और इसी तरह के कई विश्लेषणात्मक प्रश्न।

विभिन्न क्षेत्रों में आगंतुकों की आवाजाही एक निर्देशित ग्राफ है। इंटरनेट पढ़ने के बाद, मुझे पता चला कि ग्राफ़ डीबीएमएस का उपयोग विश्लेषणात्मक रिपोर्टों के लिए भी किया जाता है। मेरी यह देखने की इच्छा थी कि ग्राफ़ डीबीएमएस ऐसे प्रश्नों से कैसे निपटेंगे (टी एल; डॉ; खराब)।

मैंने DBMS का उपयोग करना चुना जानूसग्राफ, ग्राफ ओपन-सोर्स डीबीएमएस के एक उत्कृष्ट प्रतिनिधि के रूप में, जो परिपक्व प्रौद्योगिकियों के ढेर पर निर्भर करता है, जो (मेरी राय में) इसे सभ्य परिचालन विशेषताओं के साथ प्रदान करना चाहिए:

बर्कलेडीबी स्टोरेज बैकएंड, अपाचे कैसेंड्रा, स्काइला;
जटिल अनुक्रमितों को ल्यूसीन, इलास्टिक्स खोज, सोलर में संग्रहीत किया जा सकता है।

JanusGraph के लेखक लिखते हैं कि यह OLTP और OLAP दोनों के लिए उपयुक्त है।

मैंने बर्कलेडीबी, अपाचे कैसेंड्रा, स्काइला और ईएस के साथ काम किया है, और ये उत्पाद अक्सर हमारे सिस्टम में उपयोग किए जाते हैं, इसलिए मैं इस ग्राफ़ डीबीएमएस के परीक्षण के बारे में आशावादी था। मुझे RocksDB के स्थान पर बर्कलेDB को चुनना अजीब लगा, लेकिन यह संभवतः लेनदेन आवश्यकताओं के कारण है। किसी भी मामले में, स्केलेबल, उत्पाद उपयोग के लिए, कैसेंड्रा या स्काइला पर बैकएंड का उपयोग करने का सुझाव दिया गया है।

मैंने Neo4j पर विचार नहीं किया क्योंकि क्लस्टरिंग के लिए व्यावसायिक संस्करण की आवश्यकता होती है, यानी उत्पाद खुला स्रोत नहीं है।

ग्राफ़ डीबीएमएस कहते हैं: "यदि यह ग्राफ़ जैसा दिखता है, तो इसे ग्राफ़ की तरह मानें!" - सुंदरता!

सबसे पहले, मैंने एक ग्राफ़ बनाया, जो बिल्कुल ग्राफ़ डीबीएमएस के सिद्धांतों के अनुसार बनाया गया था:

एक सार है 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()

रूसी में क्या कुछ इस तरह है: आईडी = 0 के साथ एक ज़ोन ढूंढें, उन सभी शीर्षों को लें जहां से एक किनारा इसके (ज़ोनस्टेप) तक जाता है, बिना पीछे जाए स्टॉम्प करें जब तक कि आप उन ज़ोनस्टेप्स को नहीं ढूंढ लेते जहां से ज़ोन के लिए एक किनारा है आईडी=19, ऐसी श्रृंखलाओं की संख्या गिनें।

मैं ग्राफ़ पर खोज की सभी पेचीदगियों को जानने का दिखावा नहीं करता, लेकिन यह प्रश्न इस पुस्तक के आधार पर तैयार किया गया था (https://kelvinlawrence.net/book/Gremlin-Graph-Guide.html).

मैंने बर्कलेडीबी बैकएंड का उपयोग करके जानूसग्राफ ग्राफ़ डेटाबेस में 50 से 3 पॉइंट लंबाई तक के 20 हजार ट्रैक लोड किए, इसके अनुसार इंडेक्स बनाए। प्रबंध.

पायथन डाउनलोड स्क्रिप्ट:


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

इस मामले में, सटीक मिलान खोजों के लिए उपयोग किए जाने वाले डेटा और इंडेक्स को बर्कलेडीबी में संग्रहीत किया जाता है। पहले दिए गए अनुरोध को निष्पादित करने पर, मुझे कई दसियों सेकंड के बराबर समय प्राप्त हुआ।

उपरोक्त 4 स्क्रिप्ट को समानांतर में चलाकर, मैं डॉकर लॉग में जावा स्टैकट्रैस (और हम सभी को जावा स्टैकट्रेस पढ़ना पसंद है) की एक हंसमुख धारा के साथ डीबीएमएस को एक कद्दू में बदलने में कामयाब रहा।

कुछ विचार के बाद, मैंने ग्राफ़ आरेख को निम्नलिखित में सरल बनाने का निर्णय लिया:

यह निर्णय लेना कि इकाई विशेषताओं द्वारा खोज करना किनारों द्वारा खोज करने की तुलना में तेज़ होगा। परिणामस्वरूप, मेरा अनुरोध निम्नलिखित में बदल गया:

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

रूसी में जो कुछ इस तरह है: ID=0 के साथ ZoneStep ढूंढें, जब तक आपको ID=19 के साथ ZoneStep न मिल जाए, तब तक वापस जाए बिना स्टॉम्प करें, ऐसी श्रृंखलाओं की संख्या गिनें।

अनावश्यक कनेक्शन न बनाने के लिए मैंने ऊपर दी गई लोडिंग स्क्रिप्ट को भी सरल बना दिया और खुद को विशेषताओं तक सीमित कर लिया।

अनुरोध को पूरा होने में अभी भी कई सेकंड लगे, जो हमारे कार्य के लिए पूरी तरह से अस्वीकार्य था, क्योंकि यह किसी भी प्रकार के एडहॉक अनुरोधों के प्रयोजनों के लिए बिल्कुल भी उपयुक्त नहीं था।

मैंने सबसे तेज़ कैसंड्रा कार्यान्वयन के रूप में स्काइला का उपयोग करके जानूसग्राफ को तैनात करने का प्रयास किया, लेकिन इससे कोई महत्वपूर्ण प्रदर्शन परिवर्तन नहीं हुआ।

तो इस तथ्य के बावजूद कि "यह एक ग्राफ़ जैसा दिखता है", मैं इसे शीघ्रता से संसाधित करने के लिए ग्राफ़ डीबीएमएस नहीं प्राप्त कर सका। मैं पूरी तरह से मानता हूं कि मुझे कुछ पता नहीं है और जानूसग्राफ से यह खोज एक सेकंड में पूरी कराना संभव है, हालांकि, मैं ऐसा करने में सक्षम नहीं था।

चूंकि समस्या को अभी भी हल करने की आवश्यकता है, इसलिए मैंने तालिकाओं के जॉइन और पिवोट्स के बारे में सोचना शुरू कर दिया, जो सुंदरता के मामले में आशावाद को प्रेरित नहीं करता है, लेकिन व्यवहार में पूरी तरह से व्यावहारिक विकल्प हो सकता है।

हमारा प्रोजेक्ट पहले से ही 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
    )

चूँकि आवेषण बैचों में आते हैं, जानूसग्राफ की तुलना में भरना बहुत तेज़ था।

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 बिंदुओं से गुजरने वाली गिनती (*) के लिए क्वेरी निष्पादन समय का एक उदाहरण दिया गया है:

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 का उपयोग करने का निर्णय लिया। हम क्लिकहाउस में लोड करने से पहले अपाचे फ्लिंक का उपयोग करके इवेंट स्ट्रीम को प्री-प्रोसेस करके भौतिक दृश्यों और समानांतरीकरण का उपयोग करके प्रश्नों को हमेशा अनुकूलित कर सकते हैं।

प्रदर्शन इतना अच्छा है कि हमें शायद प्रोग्रामेटिक रूप से पिवोटिंग टेबल के बारे में सोचना भी नहीं पड़ेगा। पहले, हमें वर्टिका से प्राप्त डेटा को Apache Parquet पर अपलोड करके पिवोट्स करना पड़ता था।

दुर्भाग्य से, ग्राफ़ डीबीएमएस का उपयोग करने का एक और प्रयास असफल रहा। मुझे जानूसग्राफ में ऐसा अनुकूल पारिस्थितिकी तंत्र नहीं मिला जिससे उत्पाद के साथ तेजी से आगे बढ़ना आसान हो जाए। साथ ही, सर्वर को कॉन्फ़िगर करने के लिए पारंपरिक जावा तरीके का उपयोग किया जाता है, जो जावा से परिचित नहीं लोगों को खून के आंसू रुलाएगा:

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 दस्तावेज़ से:

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()

अंतभाषण

एक तरह से उपरोक्त प्रयोग गर्म और मुलायम के बीच तुलना है। यदि आप इसके बारे में सोचते हैं, तो एक ग्राफ़ डीबीएमएस समान परिणाम प्राप्त करने के लिए अन्य ऑपरेशन करता है। हालाँकि, परीक्षणों के भाग के रूप में, मैंने एक अनुरोध के साथ एक प्रयोग भी किया जैसे:

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 के उदाहरण का उपयोग करके बहुत अधिक दक्षता के साथ प्रदर्शित किया जाता है। इस आलेख में प्रस्तुत उपयोग का मामला ग्राफ़ डीबीएमएस के लिए एक स्पष्ट विरोधी पैटर्न है, हालांकि यह उनके प्रतिमान में मॉडलिंग के लिए उपयुक्त लगता है।

स्रोत: www.habr.com

निष्कर्ष

अंतभाषण

एक टिप्पणी जोड़ें उत्तर रद्द