JanusGraph

Index Management

Indexing for Better Performance

대부분의 그래프 쿼리는 해당 property로 식별되는 vertex 또는 edge 리스트에서 순회를 시작

graph indexes: 대규모 그래프에서 이러한 전역 검색 작업을 효율적으로 수행

vertex-centric indexes: 그래프를 통한 실제 순회 속도를 향상

 

g.V().has('name', 'hercules')
g.E().has('reason', textContains('loves'))

graph index없이 위와 같은 쿼리를 질의하면 edge나 vertext에 대해 full scan을 해야한다. 매우 비효율적이다.

Janus는 composite 및 mixed index가 있다.

composite 인덱스는 매우 빠르고 효율적이지만, property key의 equality lookups만 된다.

mixed 인덱스는 여러 조건으로 검색이 가능하다.

 

Composite Index

여러개의 키로 인덱스 구성하는 방법이다.

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

아래의 쿼리에 대해서 위에서 선언한 composite index 둘 다 좋은 성능을 낼 수 없다. 왜냐하면 name이 쿼리에서 생략되어 있기 때문이다. 

g.V().has('age', 30)

 

그리고 아래의 쿼리에 대해서는 byNameComposite 인덱스를 탈 수 있지만, byNameAndAgeComposite을 탈 수 없다. 왜냐하면, age 쿼리가 equal constraint이 아니기 때문이다.

g.V().has('name', 'hercules').has('age', inside(20, 50))

 

composite 인덱스는 추가적인 external index banckend가 필요없기 때문에, 만일 janus storage backend로 사용하는 디비가 원자성 및 일관성을 보장한다면, composite 인덱스 수정이 트랜잭셔널하여 관리에 적합하다.

 

그리고 composite 인덱스를 사용하여, 그래프의 property uniqueness를 설정할 수 있다. unique() 속성을 통해 가능하다.

예를 들어, 전체 그래프에서 name이 unique하려면 다음과 같이 정의할 수 있다.

mgmt = graph.openManagement()
name = mgmt.getPropertyKey('name')
mgmt.buildIndex('byNameUnique', Vertex.class).addKey(name).unique().buildCompositeIndex()
mgmt.commit()

//Wait for the index to become available
ManagementSystem.awaitGraphIndexStatus(graph, 'byNameUnique').call()

//Reindex the existing data
mgmt = graph.openManagement()
mgmt.updateIndex(mgmt.getGraphIndex("byNameUnique"), SchemaAction.REINDEX).get()
mgmt.commit()

Mixed Index

Mixed 인덱스가 composite 인덱스의 제약 사항을 해결할 수 있다. 꼭 equal 연산이 아니더라고 질의할 수 있다는 의미다.

다만, equals 제약사항에 대한 질의에서 composite index보다는 성능이 느리다.

Mixed 인덱스를 설정하려면, 추가적인 index backend가 필요하다.

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('nameAndAge', Vertex.class).addKey(name).addKey(age).buildMixedIndex("search")
mgmt.commit()
//Wait for the index to become available
ManagementSystem.awaitGraphIndexStatus(graph, 'nameAndAge').call()
//Reindex the existing data
mgmt = graph.openManagement()
mgmt.updateIndex(mgmt.getGraphIndex("nameAndAge"), SchemaAction.REINDEX).get()
mgmt.commit()

아래와 같이 명시적으로 설정하여 텍스트 인덱스로 생성할 수 있다.

mgmt.buildIndex('nameAndAge',Vertex.class).addKey(name,Mapping.TEXT.getParameter()).addKey(age,Mapping.TEXT.getParameter()).buildMixedIndex("search")

 

Mixex Index로 다음과 같은 쿼리에 대해서도 인덱스 스캔이 가능하다.

g.V().has('name', textContains('hercules')).has('age', inside(20, 50))
g.V().has('name', textContains('hercules'))
g.V().has('age', lt(50))
g.V().has('age', outside(20, 50))
g.V().has('age', lt(50).or(gte(60)))
g.V().or(__.has('name', textContains('hercules')), __.has('age', inside(20, 50)))

 

Mixed 인덱스는 full-text search, range search, geo search 등에 대해서 지원한다.

Mixed Index는 Composite Index와 달리, 고유성을 지원하진 않는다.

addIndexKey를 사용하여, Index backend에 매핑되는 방식을 설정할 수 있다.

 

Composite graph indexes는 정렬을 지원하지 않는다. 모든 결과를 검색한 다음에 메모리에서 정렬한다. 매우 큰 데이터셋에 대해서 비용이 매우 비쌀 수 있다.

Mixed index는 효율적으로 정렬을 지원한다. 그러나 정렬하려는 property key가 mixed index에 추가되어 있어야 한다. 그렇지 않은 property key로 정렬할 경우, 결과를 전부 메모리에 올려야 한다.

Label Constraint

대부분의 케이스에서 특정 label이 있는 vertex나 edge를 인덱싱하는게 바람직하다.

예를 들어, name property가 있는 모든 single vertex가 아니라 name이 god인 경우만 인덱싱하기 원할 수 있다.

인덱스를 설정할 때 'indexOnly'를 사용하여 특정 vertex 또는 edge만 인덱싱할 수 있다. 

다음은 God이라는 label이 붙은 vertex만 indexing하는 예제이다.

graph.tx().rollback()  //Never create new indexes while a transaction is active
mgmt = graph.openManagement()
name = mgmt.getPropertyKey('name')
god = mgmt.getVertexLabel('god')
mgmt.buildIndex('byNameAndLabel', Vertex.class).addKey(name).indexOnly(god).buildCompositeIndex()
mgmt.commit()
//Wait for the index to become available
ManagementSystem.awaitGraphIndexStatus(graph, 'byNameAndLabel').call()
//Reindex the existing data
mgmt = graph.openManagement()
mgmt.updateIndex(mgmt.getGraphIndex("byNameAndLabel"), SchemaAction.REINDEX).get()
mgmt.commit()

unique 속성도 해당 범위에만 지정된다.

Composite versus Mixed Indexes

exact match에 composite index를 쓰면 된다. 혼합 인덱스보다 훨씬 빠르다. 예외적으로 쿼리 제약 조건의 distinct values의 수가 상대적으로 작거나, 하나의 value가 많은 값과 연관될 경우, mixed index를 쓰기도 한다.(전체 인구 60억에 대해서, 남/여 property key에 '여'로 쿼리할 경우)

numeric range, full-text or geo-spatial indexing에는 mixed index를 사용하는 것을 권장하며, 정렬쿼리에서도 성능이 좋을 수 있다.

Vertex-centric Indexes

vertex별로 구축되는 로컬 인덱스다. 매우 큰 그래프에서 특정 vertex가 수천개의 edge가 있을 수 있다. 해당 vertex를 순회하는 것은 성능이 매우 느리다. 왜냐하면, 큰 하위 집합을 검색한 다음 조건과 일치하는지 확인하기 위해 메모리에서 필터링해야 하기 때문이다.

Vertex-centric Indexes는 edge 검색 성능을 개선하는데 사용된다.

 

아래의 정의를 통해서 특정 시간에 발생한 edge만 검색하는데 성능이 개선될 수 있다.

graph.tx().rollback()  //Never create new indexes while a transaction is active
mgmt = graph.openManagement()
time = mgmt.getPropertyKey('time')
battled = mgmt.getEdgeLabel('battled')
mgmt.buildEdgeIndex(battled, 'battlesByTime', Direction.BOTH, Order.decr, time)
mgmt.commit()
//Wait for the index to become available
ManagementSystem.awaitRelationIndexStatus(graph, 'battlesByTime').call()
//Reindex the existing data
mgmt = graph.openManagement()
mgmt.updateIndex(mgmt.getRelationIndex(battled, "battlesByTime"), SchemaAction.REINDEX).get()
mgmt.commit()

위 예에서는 Direction.BOTH로 양방향에 대해서 설정했지만, 단방향으로 설정하면, 인덱스 유지관리 및 저장비용이 절반으로 줄어든다.

 

mgmt = graph.openManagement()
time = mgmt.getPropertyKey('time')
rating = mgmt.makePropertyKey('rating').dataType(Double.class).make()
battled = mgmt.getEdgeLabel('battled')
mgmt.buildEdgeIndex(battled, 'battlesByRatingAndTime', Direction.OUT, Order.decr, rating, time)
mgmt.commit()

위와 같이 time과 rating으로 Vertex-centric Index를 생성할 경우, rating, time의 순서가 중요하다.

h = g.V().has('name', 'hercules').next()
g.V(h).outE('battled').property('rating', 5.0) //Add some rating properties
g.V(h).outE('battled').has('rating', gt(3.0)).inV()
g.V(h).outE('battled').has('rating', 5.0).has('time', inside(10, 50)).inV()
g.V(h).outE('battled').has('time', inside(10, 50)).inV()

다음과 같은 질의에 대해 1,2번째는 성능이 좋을 수 있지만, 3번째는 인덱스 스캔을 하지 않을 것이라 보면 된다.

 

다양한 제약 조건 순회를 지원하기 위해 동일한 모서리 레이블에 대해 여러 꼭지점 중심 인덱스를 구축할 수 있다.

Ordered Traversals

아래의 질의는 edge를 통과하는 순서를 지정한다.

횡단되는 각 vertex에 대해 (주어진 순서로) edge의 하위 집합을 검색하려면 localLimit 명령을 사용하면 된다.

h = g..V().has('name', 'hercules').next()
g.V(h).local(outE('battled').order().by('time', decr).limit(10)).inV().values('name')
g.V(h).local(outE('battled').has('rating', 5.0).order().by('time', decr).limit(10)).values('place')

 

Order key가 인덱스의 키와 일치하고 요청된 순서(예: 증가 또는 감소)가 인덱스에 정의된 것과 동일한 경우, 이러한 쿼리는 정점 중심 인덱스를 통해 효율적으로 응답할 수 있다.

Index Lifecycle

ENABLED 상태일 때만 인덱스 사용이 가능하다.

인덱스의 State는 다음과 같다.

• INSTALLED The index is installed in the system but not yet registered with all instances in the cluster
• REGISTERED The index is registered with all instances in the cluster but not (yet) enabled
• ENABLED The index is enabled and in use
• DISABLED The index is disabled and no longer in use

Storage Backends

Apache Cassandra

Local Server Mode

로컬 개발 환경 사용시 적합

Remote Server Mode

카산드라 클러스터랑 JanusGraph가 분리된 환경에서 실행.

Remote Server Mode with Gremlin Server

카산드라 클러스터랑 JanusGraph가 분리된 환경에서 실행하나, end user가 자바 기반의 앱이 아니라, gremlin client와 통신하기 때문에, 다중 언어 아키텍처에서 사용할 수 있다.

JanusGraph Embedded Mode

JanusGraph를 카산드라에 임베딩할 수 있다. 같은 JVM에서 실행할 수 있다는 의미이며, 프로세스를 통해서 통신을 하기 때문에 네트워크를 통한 통신 보다 훨씬 오버헤드가 적다. 왜냐하면, 네트워크 통신에서 발생하는 (de)serialization이 사라지고, 네트워크 오버헤드도 없기 때문이다.

이 방식은 JanusGraph가 내부적으로 카산드라 데몬을 실행한다. 더 이상 외부의 클러스터와 연결하지 않고 자체 클러스터가 된다.

Cassandra가 내장된 JanusGraph를 실행하려면 GC 튜닝이 필요.

내장된 Cassandra는 쿼리 응답 지연 시간을 단축할 수 있지만 로드 시 GC 동작은 예측하기 쉽지 않다.

 

카산드라 이외에도 HBase, Google BigTable 등 다양한 스토리지 백엔드를 플러거블하게 지원한다.

Mixed Index Backends

Mixed Index는 Index Backend를 필요로 하는데, ES, Solr, lucene이 있다. geo, range, full-text search를 지원한다.

Search Predicates and Data Types

Compare Predicate

• eq (equal)
• neq (not equal)
• gt (greater than)
• gte (greater than or equal)
• lt (less than)
• lte (less than or equal)

String, Numeric, Date 등은 위 연산을 지원하며, Boolean, UUID는 (n)eq를 지원한다.

JanusGraph Data Model

JanusGraph는 그래프를 인접리스트(adjacency list format)으로 데이터를 저장한다.

vertex의 인접리스트에는 vertex에 연결된 모든 edge(및 속성)가 포함된다.

JanusGraph는 인접리스트 형식으로 그래프를 저장함으로써 정점의 모든 edge와 property가 스토리지 백엔드에 compact하게 저장되어 순회 속도가 빨라진다.

단점은 각 가장자리를 두 번 저장. 즉, edge의 vertex에 대해 한 번씩 저장.

 

그리고 각 vertex의 인접리스트는 정렬되어 저장된다. vertext centric index으로 순회할 때 빠를 수 있다.

 

cell은 column과 value로 구성됩니다. cell은 주어진 row 내의 column으로 고유하게 식별된다.

janusgraph는 bigtable 모델에서 추가 요구사항이 있다.

cell은 column을 기준으로 정렬되어야 한다. 인덱스 구조, 리스트 스킵, 이진 검색을 위해서, 즉 column range로 지정된 cell의 subset을 효율적으로 검색할 수 있어야 한다.

 

Bigtable model서는 row를 key 순서대로 정렬된 상태로 유지할 수 있다.

JanusGraph Data Layout

JanusGraph는 각 인접리스트를 기본 스토리지 백엔드에 행으로 저장한다.

(64비트) Vertix ID는 vertix의 인접리스트를 포함하는 row를 가리키는 key이다.

각 cell에 저장된 edge 및 property는 효율적인 insert delete를 가능하게 한다.

따라서 특정 스토리지 백엔드에서 행당 허용되는 최대 cell 수는 JanusGraph가 이 백엔드에 대해 지원할 수 있는 vertex의 최대 수준이기도 하다.

Individual Edge Layout

각 edge와 property는 cell로 저장된다.
column의 바이트 순서가 edge label의 sort key를 따르도록 직렬화된다.
각 edge/cell의 스토리지 공간을 최대한 작게 유지하기 위해 변수 ID 인코딩 방식과 압축된 object serialization가 사용된다.

 

JanusGraph는 all vertex(property 포함), edge(property 포함) 및 VCI를 Edgestore에 저장한다.

CREATE TABLE edgestore (
                                 key blob,
                                 column1 blob,
                                 value blob,
                                 PRIMARY KEY (key, column1)
) WITH CLUSTERING ORDER BY (column1 ASC)
   AND bloom_filter_fp_chance = 0.01
   AND caching = {'keys': 'ALL', 'rows_per_partition': 'ALL'}
   AND comment = ''
   AND compaction = {'class': 'SizeTieredCompactionStrategy'}
   AND compression = {'chunk_length_in_kb': '64', 'sstable_compression': 'org.apache.cassandra.io.compress.LZ4Compressor'}
   AND crc_check_chance = 1
   AND default_time_to_live = 0
   AND gc_grace_seconds = 864000
   AND max_index_interval = 2048
   AND memtable_flush_period_in_ms = 0
   AND min_index_interval = 128
   AND speculative_retry = '99.0PERCENTILE'
   AND paxos_grace_seconds = 864000
    AND tombstone_gc = {'mode': 'timeout', 'propagation_delay_in_seconds': '3600'};

Cassandra 백엔드에서 key는 파티션 키이고, column1은 클러스터링 키이며, 함께 기본 키를 형성한다.

 

pk가 cassandra의 유니크한 row를 정한다.

그런데 JanusGraph에서는 이 세 개의 column(key, column1, value)를 어떻게 사용할까? 예시를 보자.

1. vertext 추가.

v = graph.addVertex()
graph.tx().commit()

 

cql 조회시 아래와 같이 나옴

cqlsh> select * from janusgraph.edgestore;
key | column1 | value
— — — — — — — — — — + — — — — -+ — — — — — —
0xe000000000000080 | 0x02 | 0x0001049c

 

2. 하나 더 추가.

v2 = graph.addVertex()

graph.tx().commit()

cqlsh> select * from janusgraph.edgestore;
key | column1 | value
— — — — — — — — — — + — — — — -+ — — — — — —
0xe000000000000080 | 0x02 | 0x0001049c
0x1000000000000080 | 0x02 | 0x00010482
(2 rows)

vertex 추가할 때 마다 row 하나씩 추가됨

 

3. v, v2에 edge 추가

v.addEdge(“connect”, v2)

graph.tx().commit()

cqlsh> select * from janusgraph.edgestore;
key | column1 | value
— — — — — — — — — — + — — — — — — — — — — + — — — — — — — — — — — — — — —
0xe000000000000080 | 0x02 | 0x0001049c
0xe000000000000080 | 0x70a080201080081c | 0x
0x0000000000000415 | 0x02 | 0x00010880
0x0000000000000415 | 0x10c0 | 0xa072741e636f6e6e6563f40480
0x0000000000000415 | 0x10c2801800 | 0x8f00018e008080
0x0000000000000415 | 0x10c2801c00 | 0x9981018e008180
0x0000000000000415 | 0x10c2802000 | 0xad80018e008280
0x0000000000000415 | 0x10c2802400 | 0x9981018e008380
0x0000000000000415 | 0x10c2802800 | 0xae80018e008480
0x0000000000000415 | 0x10c2802c00 | 0xb082018e008680
0x0000000000000415 | 0x10c2803000 | 0xb382018e008780
0x0000000000000415 | 0x10c4 | 0x00800c80
0x0000000000000415 | 0x10c8 | 0x008005c5f775054d481480
0x1000000000000080 | 0x02 | 0x00010482
0x1000000000000080 | 0x70a180216080081c | 0x

key '0x0000000000000415'는 edge label "connect"의 schema에 대한 record이다.

edge에는 두 row가 추가된다.

0xe000000000000080 | 0x70a080201080081c | 0x
0x1000000000000080 | 0x70a180216080081c | 0x

 

4. 정점에 속성 추가

v.property(“name”, “bob”)
graph.tx().commit()

0xe000000000000080 | 0x50c0 | 0xa0626fe20c9c

 

 

property는 [0x40, 0x60) 범위에 속하고 edge는 [0x60, 0x80) 범위에 속한다. janusgraph-core 패키지의 IDHandler::getBounds 메소드를 참조.

 

Cassandra는 클러스터링 키(예: 이 경우 column1)를 기준으로 행을 정렬한다.

따라서 쿼리에 property만 필요하거나 edge만 필요한 경우 JanusGraph는 이를 신속하게 가져올 수 있다.

Index

Composite Index

MySQL과 같은 RDB의 Composite Index와는 이름만 같고 완전 다른 개념이다. equality lookup만 가능하다.

edgestore에 vertex 및 edge가 저장된다면, index는 graphindex에 저장된다.

 

composite index는 partition key로 property value를 indexing하고 vertex나 edge ID를 value에 저장한다.

주의사항 

composite index는 높은 카디널리티를 선호한다.

예를 들어, property value가 동일한 vertex가 수십만 개 있는 경우 일반적으로 composite index가 아닌 mixed index 사용을 고려해야 한다.

composite index는 인덱싱된 value를 파티션 키로 저장한다.

동일한 type을 가진 백만 개의 vertex가 있는 경우 동일한 파티션 키를 가진 백만 개의 행이 있게 된다.

이는 대부분의 데이터베이스에서 큰 안티 패턴이다. 이 경우 혼합 인덱스 사용을 고려해야 한다.

 

JanusGraph에서 Edge ID는 Relation ID, Out-Vertex ID, Edge Label ID, In-Vertex ID의 네 부분으로 구성된다.

영숫자를 사용하여 인코딩되고 단일 ID로 연결된다.

gremlin> graph = JanusGraphFactory.open("inmemory")
==>standardjanusgraph[inmemory:[127.0.0.1]]
gremlin> mgmt = graph.openManagement()
==>org.janusgraph.graphdb.database.management.ManagementSystem@fa5f81c
gremlin> mgmt.makeEdgeLabel("follow").make()
==>follow
gremlin> mgmt.commit()
==>null
gremlin> g = graph.traversal()
==>graphtraversalsource[standardjanusgraph[inmemory:[127.0.0.1]], standard]
gremlin> v1 = g.addV("person").next()
==>v[4208]
gremlin> v2 = g.addV("person").next()
==>v[4168]
gremlin> e = g.V(v1).addE("follow").to(v2).next()
==>e[172-38w-t1-37s][4208-follow->4168]
gremlin> graph.tx().commit()
==>null
gremlin> mgmt = graph.openManagement()
==>org.janusgraph.graphdb.database.management.ManagementSystem@7f42e06e
gremlin> mgmt.getEdgeLabel("follow").id()
==>1045
gremlin> e = g.E().next()
==>e[172-38w-t1-37s][4208-follow->4168]
gremlin> e.id()
==>172-38w-t1-37s

 

gremlin> import org.janusgraph.util.encoding.LongEncoding;
==> output omitted
gremlin> LongEncoding.decode("172")
==>1550
gremlin> LongEncoding.decode("38w")
==>4208
gremlin> LongEncoding.decode("37s")
==>4168
gremlin> LongEncoding.decode("t1")
==>1045

 

// recap: query Q1 translates to: [0x70A0, 0x70A1)
g.V(v1).outE("follows").next()
// recap: query Q2 translates to: [0x70A0802000, 0x70A0802001)
g.V(v1).outE("follows").where(__.inV().is(v2)).next()
// query Q4 translates to: [0x60, 0x80)
g.V(v1).outE().where(__.inV().is(v2)).next()

그렇다면 쿼리 Q4에 어떤 문제가 있다.

column은 항상 Label ID로 시작한다는 점을 기억하자.(4개로 구성된)

edge Label을 모르면 이웃 vertex ID를 아는 것은 도움이 되지 않으며 JanusGraph는 모든 에지를 로드해야 한다.
이 경우 조건자가 스토리지 백엔드로 푸시다운되지 않기 때문에 조건자 푸시다운이 실패합니다.

 

// query Q2 translates to: [0x70A0802000, 0x70A0802001)
g.V(v1).outE("follows").where(__.inV().is(v2)).next()
// query Q5 translates to: [0x70A1802000, 0x70A1802001)
g.V(v1).inE("follows").where(__.outV().is(v2)).next()

방향만 다를 뿐 쿼리는 같다. 결과 쿼리에서 방향을 나타내는 1만 다르다.