图解开源JanusGraph内部数据存储结构
本文以图解的形式详细介绍了开源图数据库JanusGraph的内部数据存储结构,包括Vertex/Property/Edge等信息如何存储于HBase数据表中,以及各自的数据格式定义。
备注:本文基于JanusGraph 0.2.0版本进行介绍,其他版本有可能有差异。
开源图数据库Titan项目已经停止更新,JanusGraph是Titan项目的演进产品。到目前为止,JanusGraph与Titan在核心机制上相差不大。JanusGraph/Titan有如下关键设计:
支持大规模图数据存储,Titan图数据库是建立在分布式集群上,数据存储容量和集群节点数量成正比;
支持弹性和线性扩展,高可用,高容错;
支持Gremlin图查询语言;
支持利用Hadoop计算框架对图数据进行分析;
支持外部索引:ElasticSearch、Solr、Lucene;
支持多储存引擎:Cassandra、HBase、Berkeley DB和InMemory模式;
基于Apache License 2.0;
本文内容以HBase作为Storage Backend,详细介绍JanusGraph的内部数据存储结构。
JanusGraph基本概念
在介绍关系数据的数据存储结构之前,我们先来看一下JanusGraph的基本概念。
如同大多数图数据库一样,JanusGraph采用属性图进行建模。基于属性图的模型,JanusGraph有如下概念:
Vertex Label:节点的类型,用于表示现实世界中的实体类型,比如”人”,“车”。在JanusGraph中,每一个节点有且只有一个Vertex Label。当不显式指定Vertex Label时,采用默认的Vertex Label。
Vertex:节点/顶点,用于表示现实世界中的实体对象。
Edge Label:边的类型,用于表示现实世界中的关系类型,比如“通话关系”,“转账关系”,“微博关注关系”等;
Edge: 边,用于表示一个个具体的联系。JanusGraph的边都是单向边。如果需要双向边,则通过两条相反方向的单向边组成。JanusGraph不存在无向边。
Property Key:属性的类型,比如“姓名”,“年龄”,“时间”等。Property Key有Cardinality的概念。Cardinality有SINGLE、LIST和SET三种选项。这三种选项分别用于表示一个Property中,对于同一个Property Key是只允许有一个值、允许多个可重复的值,还是多个不可重复的值。
Property:属性,用于表示一个个具体的附加信息,采用Key-Value结构。Key就是Property Key,Value就是具体的值。
属性图举例:
张三与李四是同事关系,他们从2017年开始成为同事,用属性图表达:
图切割
作为一种分布式图数据库,JanusGraph需要将数据切分存储到多台机器上。
典型的图切割方法有两种: 一种是按点切割,另一种是按边切割。
按点切割(Vertex-Cut)
按Vertex切割时,切割线通过图的Vertex,而不是Edge。每一条Edge边只保存一次,并且每一条Edge只出现在一台机器上,邻居多的Vertex会被分发到不同的机器上。
按边切割(Edge-Cut)
按Edge切割时,切割线只穿过连接vertex的edge,此时,每一个vertex只保存一次。切断的Edge会保存到多台机器上。
JanusGraph采用的分片方式是按Edge切割,而且是对于每一条边,都会被切断。切断后,该边会在起始Vertex上和目的Vertex上各存储一次。通过这种方式,JanusGraph不管是通过起始Vertex,还是从目的Vertex,都能快速找到对端Vertex。
备注:
对于Super Node的存储模式不同,这里暂不展开讨论。
JanusGraph允许将Edge Label定义为单向感知的edge. 对于单向感知的edge,只会从起始vertex查询此edge,不会从目的vertex反向查询。因此,这种情况下,目的节点不存储该vertex,仅在起始节点存储。
存储方式
还是以上面的例子为例,按边切割后,变成如下结果:
在JanusGraph中,是点为中心,按切边的方式存储数据的。节点的ID作为HBase的Rowkey,节点上的每一个属性和每一条边,作为该Rowkey的一个个独立的Cell。即每一个属性、每一条边,都是一个个独立的KCV结构(Key-Column-Value)。
如下图所示:
备注: 简化起见,此处暂不考虑节点中如何记录其所属的Vertex Label。
详细存储格式
Vertex存储格式
Vertex ID以Rowkey的形式存储在HBase中。Vertex ID总共64个bit。
Vertex ID由partition id、count、ID padding三部分组成。
最高位5个bit是partition id. partition是JanusGraph抽象出的一个概念。当Storage Backend是HBase时,JanusGraph会根据partition数量,自动计算并配置各个HBase Region的split key,从而将各个partition均匀映射到HBase的多个Region中。然后通过均匀分配partition id最终实现数据均匀打散到Storage Backend的多台机器中。
中间的count部分是流水号,其中最高位比特固定为0.
最后几个bit是ID padding, 表示Vertex的类型。具体的位数长度根据不同的Vertex类型而不同。最常用的普通Vertex,其值为’000’。
各个Vertex类型后缀划分如下(拷贝自源码):
Property存储格式
一个Property Key所关联的属性值有可能有一个,也有可能有多个,因此,JanusGraph使用Cardinality来描述Property Key的这种特点。Cardinality
有SINGLE
,LIST
和SET
三种类型:
SINGLE表示一个Property Key只对应一个Value,这是最常用的场景。
LIST表示一个Property Key可以对应多个Value,多个Value可以有重复值。
SET表示一个Property Key可以对应多个Value,多个Value不可以有重复值。
JanusGraph的Property,在不同的Cardinality下,数据存储结构略有不同。整体原则是:根据Cardinality的不同,列名本身能够确定唯一的一个属性。
Cardinality为SINGLE时的存储结构
HBase的列名只存储Property Key的ID及方向。具体的Property Value值以及Property ID(JanusGraph为每一个Property分配的唯一ID),都存放在Cell的Value中。另外,如果该Property还有额外的Remaining properties,也会放在Value中。Remaining properties一般不使用,仅在一些特殊场景下,用于为该Property记录更多的附加信息(比如存储元数据Edge Labe的定义等)。
PropertyKeyID及方向整个结构的详细结构在后文中描述;属性的值
占用一个或多个字段,具体格式在后文描述;属性的ID
及Remaining属性
采用相同的格式,具体格式在后文描述。
Candinality为LIST时的存储结构
各个部分与Cardinality为SINGLE时的结构相似,区别在于属性的ID被放在了列名中,而不是放在Value中。
Candinality为SET存储结构
各个部分与Cardinality为SINGLE时的结构相似,区别在于属性的值被放在了列名中,而不是放在Value中。
属性的Property Key ID和方向存储结构
每一个Property Key本身也有一个唯一的ID。为标识各个属性是属于哪一种Property Key,JanusGraph记录了各个属性对应的Property Key的ID。JanusGraph在存储时,会将Property Key ID以及DirectionID(分系统类型/隐藏/常规不隐藏三种属性)组装在一起,使用多个字节来表示。
属性的ID和属性值存储结构
属性的值根据Property Key中定义的数据类型不同,有不同的序列化器。比如,String有StringSerializer, integer有IntegerSerializer. 其中IntegerSerializer与属性ID的格式化方式相同。
属性的ID作为一种无符号整数,JanusGraph将其格式化为多个字节。每一个字节的最高位比特用于表示是最后一个字节。0
表示不是最后一个字节,1
表示是最后一个字节。
边存储格式
JanusGraph的Edge Label也有一个MULTIPLICITY
概念。MULTIPLICITY
有MULTI
等不同的取值,其中以MULTI
取值最为常用。
MULTIPLICITY为MULTI时的存储结构
边的存储格式与属性类似,Property Key和Edge Label被抽象成了Relation Type,并采用相同的数据结构。SortKey是一种特殊的属性。JanusGraph允许在定义Edge Label时指定其中的一个或多个属性为Sort Key。对于边的Sort Key属性,JanusGraph在存储时会将其存储在Relation Type ID的后面,其他所有字段的前面。通过这种方式,可以保证一个节点的多条同一个类型的边,会按Sort Key属性排序存储。这对于一个节点有大量边时,对查询性能提升有帮助。
MULTIPLICITY不是MULTI并且此方向有多条边时的存储结构
MULTIPLICITY不是MULTI并且此方向仅有一条边时的存储结构
以上系作者根据自己对源代码的理解整理而成,难免有不准确或者不全面的地方。欢迎指正,交流。
- 点赞
- 收藏
- 关注作者
评论(0)