🥇ניסוי בודק את הישימות של גרף JanusGraph DBMS לפתרון בעיית מציאת נתיבים מתאימים

שלום לכולם. אנו מפתחים מוצר לניתוח תנועה לא מקוונת. לפרויקט יש משימה הקשורה לניתוח סטטיסטי של מסלולי מבקרים על פני אזורים.

כחלק ממשימה זו, משתמשים יכולים לשאול את שאילתות המערכת מהסוג הבא:

כמה מבקרים עברו מאזור "A" לאזור "B";
כמה מבקרים עברו מאזור "A" לאזור "B" דרך אזור "C" ולאחר מכן דרך אזור "D";
כמה זמן לקח לסוג מסוים של מבקר לנסוע מאזור "A" לאזור "B".

ומספר שאילתות אנליטיות דומות.

תנועת המבקר על פני אזורים היא גרף מכוון. לאחר קריאת האינטרנט, גיליתי ש-DBMS גרפים משמשים גם לדוחות אנליטיים. היה לי רצון לראות איך DBMSs גרפים יתמודדו עם שאילתות כאלה (TL; DR; גרוע).

בחרתי להשתמש ב-DBMS JanusGraph, כנציג מצטיין של DBMS בקוד פתוח של גרפים, המסתמך על ערימה של טכנולוגיות בוגרות, שאמורות (לדעתי) לספק לו מאפיינים תפעוליים הגונים:

אחורי אחסון של BerkeleyDB, Apache Cassandra, Scylla;
ניתן לאחסן אינדקסים מורכבים ב- Lucene, Elasticsearch, Solr.

מחברי JanusGraph כותבים שהוא מתאים גם ל-OLTP וגם ל-OLAP.

עבדתי עם BerkeleyDB, Apache Cassandra, Scylla ו-ES, ומוצרים אלה משמשים לעתים קרובות במערכות שלנו, אז הייתי אופטימי לגבי בדיקת ה-DBMS הגרפי הזה. נראה לי מוזר לבחור ב-BerkeleyDB על פני RocksDB, אבל זה כנראה נובע מדרישות העסקה. בכל מקרה, לשימוש במוצר ניתן להרחבה, מומלץ להשתמש ב-backend על Cassandra או Scylla.

לא שקלתי את Neo4j מכיוון שצרור מצריך גרסה מסחרית, כלומר, המוצר אינו פתוח.

גרפים DBMSs אומרים: "אם זה נראה כמו גרף, התייחס לזה כמו גרף!" - יופי!

ראשית, ציירתי גרף, שנעשה בדיוק לפי הקנונים של DBMSs גרפים:

יש מהות 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), רקע בלי לחזור אחורה עד שתמצא את ה-ZoneSteps שמהם יש קצה ל-Zone עם ID=19, ספרו את מספר שרשראות כאלה.

אני לא מתיימר לדעת את כל המורכבויות של חיפוש בגרפים, אבל השאילתה הזו נוצרה על סמך הספר הזה (https://kelvinlawrence.net/book/Gremlin-Graph-Guide.html).

טענתי 50 אלף רצועות באורך של בין 3 ל-20 נקודות לתוך מסד נתונים של גרפים של JanusGraph באמצעות ה-BerkeleyDB backend, יצרתי אינדקסים לפי מַנהִיגוּת.

סקריפט הורדה של 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)

השתמשנו ב-VM עם 4 ליבות ו-16 GB RAM על SSD. JanusGraph נפרס באמצעות פקודה זו:

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

במקרה זה, הנתונים והאינדקסים המשמשים לחיפושים בהתאמה מדויקת מאוחסנים ב-BerkeleyDB. לאחר שביצעתי את הבקשה שניתנה קודם לכן, קיבלתי זמן השווה לכמה עשרות שניות.

על ידי הפעלת 4 הסקריפטים לעיל במקביל, הצלחתי להפוך את ה-DBMS לדלעת עם זרם עליז של Java stacktraces (וכולנו אוהבים לקרוא Java stacktraces) ביומני Docker.

לאחר מחשבה, החלטתי לפשט את דיאגרמת הגרף לדברים הבאים:

החלטה שחיפוש לפי תכונות ישות יהיה מהיר יותר מאשר חיפוש לפי קצוות. כתוצאה מכך, הבקשה שלי הפכה לדברים הבאים:

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

מה ברוסית זה משהו כזה: מצא את ZoneStep עם ID=0, רקע בלי לחזור עד שתמצא את ZoneStep עם ID=19, ספר את מספר השרשראות הללו.

פישטתי גם את סקריפט הטעינה המופיע לעיל כדי לא ליצור קשרים מיותרים, ולהגביל את עצמי לתכונות.

הבקשה עדיין ארכה מספר שניות להשלמתו, דבר שלא היה מקובל לחלוטין עבור המשימה שלנו, מכיוון שהיא כלל לא התאימה למטרות של בקשות AdHoc מכל סוג שהוא.

ניסיתי לפרוס את JanusGraph באמצעות Scylla כיישום Cassandra המהיר ביותר, אבל זה גם לא הוביל לשינויים משמעותיים בביצועים.

אז למרות העובדה ש"זה נראה כמו גרף", לא הצלחתי לגרום ל-DBMS של הגרף לעבד אותו במהירות. אני מניח לחלוטין שיש משהו שאני לא יודע ושניתן לגרום ל-JanusGraph לבצע את החיפוש הזה בשבריר שנייה, עם זאת, לא הצלחתי לעשות זאת.

מכיוון שהבעיה עדיין צריכה להיפתר, התחלתי לחשוב על JOINs ו-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 נקודות:

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 Flink לפני טעינתן ל-ClickHouse.

הביצועים כל כך טובים שכנראה לא נצטרך אפילו לחשוב על סיבוב טבלאות באופן תכנותי. בעבר, היינו צריכים לבצע צירים של נתונים שאוחזרו מ-Vertica באמצעות העלאה ל- Apache Parquet.

לרוע המזל, ניסיון נוסף להשתמש ב-DBMS גרפי לא צלח. לא מצאתי ל-JanusGraph מערכת אקולוגית ידידותית שמאפשרת להתעדכן בקלות במוצר. במקביל, כדי להגדיר את השרת, נעשה שימוש בשיטת 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}

הצלחתי בטעות "להכניס" את גרסת BerkeleyDB של JanusGraph.

התיעוד די עקום מבחינת האינדקסים, שכן ניהול אינדקסים מחייב אותך לבצע איזו שמאניזם די מוזר ב-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. מקרה השימוש המוצג במאמר זה הוא אנטי דפוס ברור עבור DBMSs גרפים, אם כי נראה שהוא מתאים למודלים בפרדיגמה שלהם.

מקור: www.habr.com

ניסוי בודק את הישימות של גרף JanusGraph DBMS לפתרון הבעיה של מציאת נתיבים מתאימים

מסקנה

אחרית דבר

הוספת תגובה ביטול תגובה