常识是永远的流行色!

码友们，点赞再看，养成好习惯~

一：存储模式

留言或私信我，邀请你退出“图数据库交换”微信群！

1、图内容

本文以下所有内容基于：JanusGraph基于属性图来进行结构图数据：

属性图： 属性图是由 顶点（Vertex），边（Edge），属性（Property）组成的有向图

Vertex能够蕴含Properties；Edge也能够蕴含Properties；

2、存储办法

图存储的形式罕用的有两种：邻接列表 和 邻接矩阵

JanusGraph采纳邻接列表进行图数据的存储，如下图所示：（此处将图中节点形象为 只有节点，没有属性）

在Janusgraph中一个顶点的邻接列表蕴含该节点对应的属性和关联的边，下述会具体阐明 Janusgraph中邻接列表是如何实现的；

3、图切割形式

图的切割形式分为两种：按节点切割(Vertex Cut)和按边切割(Edge Cut)

  • Vertex Cut：依据点进行切割，每个边只存储一次，只有是节点对应的边便会多一份该节点的存储
  • Edge Cut：依据边进行切割，以节点为核心，边会存储两次，源节点的邻接列表存储一次，指标节点的邻接列表存储一次

在Janusgraph中既存在Edge Cut，也存在Vertex Cut的状况；

在默认的状况下应用边切割，而针对热点节点能够通过配置makeVertexLabel('product').partition()来将节点类型为product类型的节点进行Vertex Cut；

也就是说，在没有上述makeVertexLabel('product').partition()配置的话，JanusGraph所有的图数据都是以Edge Cut的形式来进行切割存储的；

具体能够查看文章：《JanusGraph-分区》中自定义分区局部中对于图切割局部的介绍；

咱们例子来阐明一下：

如下图： 张三用户节点通过手机号关联进去李四用户节点

  • 张三 和 李四 代表Vertex；指向的name、age、gender代表张三的属性
  • edgeA 和edgeB 代表Edge；也能够蕴含边的属性，例如下图中边蕴含属性create_time

按边切割后：

节点
张三name(property)age(property)gender(property)edgeA(edge)
phonephone(property)edgeA(edge)edgeB(edge)
李四name(property)age(property)gender(property)edgeB(edge)

上述能够看到，依照边切割后每一条边会存储两次！

二：BigTable模型

在JanusGraph的存储中， JanusGraph将图形的邻接列表的示意存储在反对Bigtable数据模型的任何存储后端中

BigTable模型如下图：

在Bigtable数据模型中，每个表是行的汇合，由一个key惟一标识。

每行由任意（能够很大数量然而必须无限数量）数量的cell组成；cell由column和value组成，column惟一标识某一个cell。

上述图中，有两局部须要排序的反对：sorted by key 和 sorted by column：

  • sorted by key：标识存储后端存储的数据时依照key的大小进行排序存储的
  • sorted by column：这是JanusGraph对Bigtable数据模型有一个额定要求，存储edge(边)的单元格必须按column排序，并且列范畴指定的单元格子集必须是无效可检索的； 这句话具体解答在下述文章中有体现

在Bigtable模型中的行称为“宽行”，因为它们反对大量cell，并且不用像关系数据库中那样事后定义这些cell的column。

在关系型数据库中咱们必须先定义好表的schema，才能够存储数据，如果存储过程中想要扭转表构造，则所有的数据都要对变动的列做出变动。然而Bigtable模型存储中就不用如此，每个行的column不同，咱们能够随时仅对某一行进行变动，也不许事后定义行的schema，只须要定义图的schema即可。

此外，特定的Bigtable实现能够使行按其键的程序排序。JanusGraph能够利用这样的键序来无效地划分图形，从而为十分大的图形提供更好的加载和遍历性能。

JanusGraph是如何基于BigTable数据模型针对于本身的图数据个性进行设计的呢？

上面咱们看下JanusGraph的逻辑存储构造

三：存储逻辑构造

JanusGraph基于应用BigTable模型的存储后端 实现了本人的存储的逻辑构造

ps：为了更好的了解，上面局部知识点会基于HBase存储后端进行进一步的解释！

1、整体构造

在JanusGraph中，以节点为核心，按切边的形式存储数据的。比方在Hbase中节点的ID作为HBase的Rowkey，节点上的每一个属性和每一条边，作为该Rowkey行的一个个独立的Cell。即每一个属性、每一条边，都是一个个独立的KCV构造(Key-Column-Value)

上图中，咱们能够发现图的存储整体分为三局部：vertex id、property、edge：

  • vertex id： 对应节点的惟一id，如果底层存储应用的是Hbase则代表着以后行的Rowkey，惟一代表某一个节点
  • property： 代表节点的属性
  • edge： 代表节点的对应的边

排序形式分为三种：sorted by id、sorted by type、sorted by sort key：

  • sorted by id： 根据vertex id在存储后端进行顺序存储
  • sorted by type：此处的集体了解为针对于property 和 edge的类型进行排序，保障同种类型的属性或者边间断存储在一块便于遍历查找； // TODO 深层次了解
  • sorted by sort key： sort key是边组成以的一部分，次要作用是，在同种类型的edge下，针对于sort key进行排序存储，晋升针对于指定sort key的检索速度；上面edge构造局部有具体介绍

2、Vertex id 的构造

此处的Vertex id惟一标识图中的某一个节点；节点vertex id的组成构造咱们在源码类IDManager的一段正文中能够发现：

     /*        --- JanusGraphElement id bit format ---      *  [ 0 | count | partition | ID padding (if any) ]     */

这是在Janusgraph在生成所有的id时对立的格局蕴含vertex idedge idproperty id的时候，这个程序也 就是标识咱们再应用gremlin查问出节点时，节点上标识的vertex id； 这个id值的程序不同于hbase实在存储Rowkey的程序！！！！！！！

在对vertex id进行序列化存储时，地位有所调整为：[ partition | 0 | count | ID padding (if any) ] 如下图：

从图中能够看出：

  1. Vertex ID共蕴含一个字节、8位、64个bit
  2. Vertex ID由partition id、count、ID padding三局部组成
  3. 最高位5个bit是partition id。partition是JanusGraph形象出的一个概念。当Storage Backend是HBase时，JanusGraph会依据partition数量，主动计算并配置各个HBase Region的split key，从而将各个partition平均映射到HBase的多个Region中。而后通过平均调配partition id最终实现数据平均打散到Storage Backend的多台机器中
  4. 两头的count局部是流水号，其中最高位比特固定为0；进来最高位默认的0，count的最大值为2的(64-5-1-3)=55次幂大小：3 6028 7970 1896 3968，总共能够生成30000兆个id，齐全满足节点的生成
  5. 最初几个bit是ID padding, 示意Vertex的类型。具体的位数长度依据不同的Vertex类型而不同。最罕用的一般Vertex，其值为'000'

为什么在序列化存储vertex id时，须要调整程序序列化作为RowKey存储到Hbase呢？

咱们通过上面的3个问题来答复：

  1. 为什么JausGraph调配的逻辑区间值，能够影响hbase物理存储呢？ 能够将分区雷同的数据寄存的更近呢？
在上述形容中，hbase应用vertex id作为rowkey，hbase依据rowkey程序排序存储； 每个hbase region存储是一段间断的Rowkey行；

在janusgraph的vertex id的设计中，能够发现将分区值放到了64位的前5位存储！ 在存储数据到hbase时，对rowkey进行排序，因为partition id在前5位，所以同一个分区的vertex id对应的rowkey值相差较小，所以会存储在一块；

  1. 如何疾速的查问到不同类型的节点呢？ 换个说法如何疾速的确定以后的行就是咱们须要的节点类型的行呢？
在JanusGraph的vertex id中蕴含的 ID padding就代表以后的节点类型（留神此处的类型！=lable）。000标识为一般节点，在id的组成部分中，咱们通过后面的剖析，最后面是partition id，只有把 ID padding放在最初几个字节便于查找了；
  1. 为什么查问出的节点显示的vertex id要把0|count放在最后面、partiton和id padding放在前面呢？
这里咱们猜想一下：count占用55位数据！ 试想如果把count不放在最后面，那么id的最小值比2的55次幂还大，显示不敌对！ 如果把0|count放在最后面呢？就会有两个成果：

0在有符号示意中标识以后id始终为正整数！

count是趋势递增的，所以id值也是从小到大趋势递增的，所以节点id的最小值在2的8次幂周边大小； 比把count放在前面显示的id值敌对多了~~~

vertex id是如何保障全局唯一性的呢？

次要是基于数据库 + 号段模式进行分布式id的生成；

体现在图中就是partition id + count 来保障分布式全局唯一性； 针对不同的partition都有本人的0-2的55次幂的范畴的id； 每次要生成vertex id时，首先获取一个partition，获取对应partition对应的一组还未应用的id，用来做count；

janusgraph在底层存储中存储了对应的partition应用了多少id，从而保障了再生成新的分布式vertex id时，不会反复生成！

ps ： JanusGraph中分布式惟一vertex id、edge id、property id的生成剖析，请看《图解JanusGraph系列-分布式惟一id的生成机制》

3、edge 和 property的构造

在上述的JanusGraph的整体构造中，property和edge都是作为cell存储在底层存储中；其中cell又分为column和value两局部，下图展现了这两局部的逻辑构造：

上面咱们详细分析一下 property 和 edge对应的逻辑构造；

3.1 edge的构造

Edge的Column组成部分：

  • label id：边类型代表的id，在创立图schema的时候janusgraph主动生成的label id，不同于边生成的惟一全局id
  • direction：图的方向，out：0、in：1

  • sort key：能够指定边的属性为sort key，可多个；在同种类型的edge下，针对于sort key进行排序存储，晋升针对于指定sort key的检索速度；

    • 该key中应用的关系类型必须是属性非惟一键或非惟一单向边标签；
    • 存储的为配置属性的value值，可多个（只存property value是因为，曾经在schema的配置中保留有以后Sort key对应的属性key了，所以没有必要再存一份）
  • adjacent vertex id：target节点的节点id，其实存储的是指标节点id和源节点id的差值，这也能够缩小存储空间的应用
  • edge id：边的全局惟一id

Edge的value组成部分：

  • signature key：边的签名key

    • 该key中应用的关系类型必须是属性非惟一键或非惟一单向边标签；
    • 存储压缩后的配置属性的value值，可多个（只存property value是因为，曾经在schema的配置中保留有以后signature key对应的属性key了，所以没有必要再存一份）
    • 次要作用晋升edge的属性的检索速度，将罕用检索的属性设置为signature key，晋升查找速度

  • other properties：边的其余属性

    • 留神！ 不蕴含配置的sort key和signature key属性值，因为他们曾经在对应的地位存储过了，不须要屡次存储！
    • 此处的属性，要插入属性key label id和属性value来标识是什么属性，属性值是什么；
    • 此处的property的序列化构造不同于下述所说的vertex节点的property构造，edge中other properties这部分存储的属性只蕴含：proeprty key label id + property value；不蕴含property全局惟一id！

具体解释及思考：

在进行详细分析前，请大家思考几个问题，如下:

  1. 基于上述的edge逻辑构造，JanusGraph是如何结构邻接列表的 或者 是如何获取源节点的邻接节点的？
  2. 上述的Edge逻辑构造中的，每局部的排列的程序的含意是什么？

1、基于上述的edge逻辑构造，JanusGraph是如何结构邻接列表的 或者 是如何获取源节点的邻接节点的？

从上述的整体构造局部中，咱们能够晓得，vertexId行后跟着以后的节点关联的所有的edge；

而在上述的edge的逻辑构造中，有一个adjacent vertex id字段，通过这个字段就能够获取到target节点的vertex id，就相当于指向了target节点，整顿一下：

如上图，通过上述的条件，就能够结构一个VertexA指向VertexB 和 VertexC的邻接链表；

其实，JanusGraph能够了解为结构的是双向邻接列表， 根据上图，咱们晓得vertexA 和 vertexB 和 vertexC存在边关系； 当咱们结构vertexB的邻接列表时，会蕴含指向vertexA的节点，只是说在edge对应的逻辑构造中边的方向不同而已：

总结：JanusGraph通过vertex id行中蕴含所有关联的edge，edge逻辑构造中蕴含指向target节点的数据来组成双向邻接列表的构造；

2、上述的Edge逻辑构造中的，每局部的排列的程序的含意是什么？

首先，在查问的时候为了晋升查问速度，咱们首先要过滤的是什么，针对于edge毋庸置疑是边的类型和边的方向；

所以，为了咱们能够更快的拿到类型和方向，所以在edge的存储构造中，咱们发现作者将类型和方向寄存在了column中，并且是column的最后面局部；这样咱们能够间接通过判断column的第一局部字节就能够对边类型和方向进行过滤！

ps：尽管咱们在写Gremlin语句的时候，可能是语句写的是先过滤边的属性或者其余，然而JanusGraph会针对咱们的gremlin语句进行优化为先过滤边类型和方向

接下来，咱们可能对边的属性进行过滤，咱们怎么晋升常常要过滤的属性的查问速度呢？ 咱们将常常用于范畴查问的属性配置为sort key，而后就能够在过滤完边类型和方向后疾速的进行属性的范畴过滤（此处疾速的指过滤配置为sort key的属性）；

3.2 property的构造

property的存储构造非常的简略，只蕴含key id、property id和value三局部：

  • key id：属性label对应的id，有创立schema时JanusGraph创立； 不同于属性的惟一id
  • property id：属性的惟一id，惟一代表某一个属性
  • value：属性值

留神：属性的类型蕴含SINGLE、LIST和SET三种Cardinality；当属性被设置为LIST类型时，因为LIST容许以后的节点存在多个雷同的属性kv对，仅通过key id也就是属性的label id是无奈将雷同的属性label辨别进去的

所以在这种状况下，JanusGraph的property的存储构造有所变动， property id也将会被存储在column中，如下图：

四：index存储构造

1、Composite Index构造

图一（惟一索引Composite Index结构图）：

图二（非惟一索引Composite Index结构图）：

Rowkey由index label id 和properties value两大部分组成：

  • index label id：标识以后索引类型
  • properties value：索引中蕴含属性的所有属性值，可多个； 存在压缩存储，如果超过16000个字节，则应用GZIP对property value进行压缩存储！

Column由第一个字节0 和 vertex id组成：

  • 第一个字节0：无论是惟一索引，还是非惟一索引此局部都会存在；如图一
  • vertex id：非惟一索引才会在column中存在，用于别离多个雷同索引值对应的不同节点；如图二

value由vertex id组成：

  • vertex id：针对于rowkey + column查问到的value是vertex id，而后通过vertex id查问对应的节点

2、Mixed Index构造

这里以ES作为第三方索引库为例，这里只介绍一般的范畴查找的mixed index的结构：

ES的概念为：index 蕴含多个 type；每个type蕴含多个document id，每个document id蕴含多个field name 和对应的field value；

在Jausgraph中

  • index：蕴含两种，janusgraph_edge 和 janusgraph_vertex两种
  • type：可自定义
  • document id：edge id或者 vertex id
  • field name：索引对应属性的label string
  • field value：属性对应的property value

基于倒排索引的查问程序为，给定过一个property label 和 property value查问对应的Vertex id 或者 edge id，则查问满足要求的field name 和 field value，就能够获取到对应的document id即Vertex id 或者 edge id；

五：序列化数据案例

以序列化实例来看下上述所说的整体构造

测试节点数据：

{    "label":"user",    "propertyMap":{        "create_time":"2016-12-09 02:29:26",        "user_name":"张三",        "user_id":"test110"    },    "vertexId":4152}

测试边数据：

{    "edgeId":17514510,    "label":"user_login_phone_number",    "propertyMap":{        "productid":"2"    },    "sourceId":4152,    "targetId":40964120}

跟踪Janusgraph源码，获取其序列化信息，后端存储应用Hbase：

节点序列化后数据（不蕴含索引）：

边序列化后数据（不蕴含索引）：

节点的vertex id序列化后的数据为56 0 0 0 0 0 0 -128；一个节点对应的属性和边的Rowkey雷同，根据qualifier也就是column来进行辨别；

在边的序列化后果中，蕴含两局部：一部分是节点4152的kcv，一个是节点40964120的kcv；这中央也能够阐明JanusGraph是采纳的双向邻接链表进行图存储的

五：Schema的应用

从上述来看，咱们能够晓得，JanusGraph图的schema该怎么定义次要是由edge labels 、property keys 和vertex labels 组成（Each JanusGraph graph has a schema comprised of the edge labels, property keys, and vertex labels used therein）

JanusGraph的schema能够显式或隐式创立，举荐用户采纳显式定义的形式。JanusGraph的schema是能够在应用过程中批改的，而且不会导致服务宕机，也不会拖慢查问速度。

比方一个简略的显示定义的销售图的scheme：

<propertyKey value="salesman_id" explain="销售人员id" index="" type="java.lang.String" /><propertyKey value="real_name" explain="姓名" index="" type="java.lang.String" /><propertyKey value="role" explain="角色" type="" /><propertyKey value="city_code" explain="所处城市代码" index="" type="" /><propertyKey value="create_time" explain="创立工夫" index="" type="" /><edgeLabel value="saleman_service_for" explain="销售疏导">    <propertys>        <property value="create_time"/>    </propertys></edgeLabel><edgeLabel value="own_salaman_Idcard" explain="销售身份">    <propertys>        <property value="create_time"/>    </propertys></edgeLabel><index elementType="vertex" indexType="compositeIndex" name="salesman_id_I"  >    <propertyKeys>        <propertyKey value="salesman_id" />    </propertyKeys></index><vertexLabel value="salesman" explain="销售"  >    <propertys>        <property value="salesman_id"  />        <property value="real_name" />        <property value="role"  />        <property value="city_code"  />    </propertys>    <edges>        <edge value="saleman_service_for" direction="out" />        <edge value="own_salaman_Idcard" direction="out" />    </edges></vertexLabel>

当然，咱们也能够增加一些其余的能够组成schema的元素，上述三个是必须的，另外的比方索引（index）等，次要的构造还是：

JanusGraph Schema        |-----------Vertex Lables        |-----------Property Keys        |-----------Edge Labels

和关系型数据库不同，图数据的schema是定义一张图，而非定义一个vertex的。在Mysql中，咱们通常将建设一张表定义为创立一个schema，而在JanusGraph中，一个Graph用于一个schema。

六：源码剖析

源码剖析曾经push到github：https://github.com/YYDreamer/janusgraph

七：总结

  • JanusGraph采纳Edge cut的形式进行图切割，并且依照双向邻接列表的模式进行图存储
  • JanusGraph每个节点都是对应的kcv构造； vertex id惟一标识节点；对应的行cell存储节点属性和对应的边
  • 节点id的分布式唯一性采纳数据库+号段模式进行生成；