乐趣区

关于图表:图解图库JanusGraph系列一文知晓图数据底层存储结构

jiezi

常识是永远的流行色!

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

一：存储模式

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

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)
phone phone(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 的分布式唯一性采纳 数据库 + 号段 模式进行生成；
退出移动版