内容简介:JanusGraph是以邻接列表存储的,这意味着图形存储为邻接列表的顶点集合。顶点的邻接列表包含所有点的边(出边和入边,包含边的属性)和顶点对应的属性。 JanusGraph按排序顺序维护邻接列表中的每个顶点,其顺序由排序键和边标签的排序顺序定义。排序顺序允许使用以顶点为中心的索引有效地检索邻接列表的子集。 JanusGraph图形的邻接列表可以存储在支持Bigtable数据模型的任何存储后端中。 对于图形的存储,对于图的拆分格式有两种方式:按点切割、按边切割。通过以邻接列表格式存储图形,JanusGrap
JanusGraph是以邻接列表存储的,这意味着图形存储为邻接列表的顶点集合。顶点的邻接列表包含所有点的边(出边和入边,包含边的属性)和顶点对应的属性。 JanusGraph按 排序 顺序维护邻接列表中的每个顶点,其顺序由排序键和边标签的排序顺序定义。排序顺序允许使用以顶点为中心的索引有效地检索邻接列表的子集。 JanusGraph图形的邻接列表可以存储在支持Bigtable数据模型的任何存储后端中。 对于图形的存储,对于图的拆分格式有两种方式:按点切割、按边切割。
- 按点切割:根据点进行切割,每个边只存储一次
- 按边切割:根据边进行切割,以节点为中心,边会存储两次,JanusGraph就是采用的按边切割,按边切割后以邻接列表的形式存储图形。
通过以邻接列表格式存储图形,JanusGraph确保所有顶点的边和属性紧密地存储在存储后端中(比如Hbase\Cassandra等),从而可以加速遍历。缺点是每个边必须存储两次一次作为source顶点的出边被存储,一次作为target顶点入边被存储,当然这也使我们可以在source Vertex和target Vertex中任意顶点都可以快速找到对端。
Bigtable数据模型:
来自官网的示意图:
在Bigtable数据模型中,每个表是行的集合,由一个key唯一标识。每行由任意(可以很大数量但是必须有限数量)数量的cell组成。cell由column和value组成。cell由给定行内的column唯一标识。 cell(单元格)、column(列)、value(列值) Bigtable模型中的行称为“宽行”,因为它们支持大量cell,并且不必像关系数据库中那样预先定义这些cell的column。在关系型数据库中我们必须先定义好表的schema,才可以存储数据,如果存储过程中想要改变表结构,则所有的数据都要对变化的列做出变化。但是Bigtable模型存储中就不必如此,每个行的column不同,我们可以随时仅对某一行进行变化,也不许预先定义行的schema,只需要定义图的schema即可。 JanusGraph对Bigtable数据模型有一个额外要求:存储边的单元格必须按column排序,并且列范围指定的单元格子集必须是有效可检索的(例如,通过使用索引结构,跳过列表或进行二进制搜索)。 此外,特定的Bigtable实现可以使行按其键的顺序排序。JanusGraph可以利用这样的键序来有效地划分图形,从而为非常大的图形提供更好的加载和遍历性能。但是,这并不是必需的。
JanusGraph的存储:
来自官网的示意图:
前面说过,JanusGraph使用Bigtable模型进行存储数据,如果使用的存储后台支持键顺序(如Hbase),则邻接列表将按Vertex Id排序进行顺序存储的。 在JanusGraph存储数据的表中,行的唯一key可以是任意字符串(目前最大为64KB,尽管用户大多数只使用10-100字节,下面介绍了vertex id的组成)。每次在一行中读或写数据都是一个原子操作(尽管一行中不同列可能正在进行读或写),这个设计使客户端可以更加方便的推导出在并发更新相同行时的系统行为。 在JanusGraph中,是点为中心,按切边的方式存储数据的。比如在Hbase中节点的ID作为HBase的Rowkey,节点上的每一个属性和每一条边,作为该Rowkey的一个个独立的Cell。即每一个属性、每一条边,都是一个个独立的KCV结构(Key-Column-Value)。
1:具体案例
比如我们下面有一个图,
拆分定义后为:
然后其存储格式就基本就可以确定了。
2:vertex id的组成:
- Vertex ID以Rowkey的形式存储在HBase中,Vertex ID共包含64个bit。
- Vertex ID由partition id、count、ID padding三部分组成。 2. 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'。
其组成图为(腾讯云社区):
3:边和属性在cell中具体的存储形式
下面来自官网的示意图:
深蓝色框表示使用可变长度编码方案编码的数字,以减少它们消耗的字节数。红框表示使用关联属性键中引用压缩元数据序列化的一个或多个属性值(即对象)。灰色框表示未压缩的属性值(即序列化对象)
上图中我们可以看出,Edge和Property在cell中都是由column(列)和value(值)组成。 Edge中column由labelid(边标签id)+direction(边的方向,相对于节点的出边或者入边)+sort key(用于边排序的key)+adjacent vertex id(临近顶点的id)+edge id(边id)组成,value由signature key(签名密匙)+other properties(边的其他属性)组成。
注意:此处的组成元素SortKey是一种特殊的属性,JanusGraph允许在定义Edge Label时指定其中的一个或多个属性为Sort Key,主要的作用是:将数据序列化进行存储时,序列化中edge会根据你设定的sort key进行排序,比如A有多个朋友关系的edge,每一个edge都有一个建立时间(createtime),sort key便可以在存储时将边按照建立时间进行顺序存储,这样便于查找某个createtime的边,也便于范围查找。
此处的signature key观看源码其实就是一个list数组, 里面存储的是边的property的key id(注意不是property id),作用是:边的other properties是被序列化存储在磁盘中,当我们查找 边是否包含某一属性时不可能将其序列化回来再进行查找,这时候signature key的作用就体现出来了,通过其就可以知道这条边有什么属性,就可以更快的进行查找。现在再看‘红框表示使用关联属性键中引用压缩元数据序列化的一个或多个属性值’这句话,说的就是我引用属性的key id 。 signature key有一种空间的换时间的感觉。。
Property中column由key id(属性的键id)组成,value由属性id+属性值组成。
这里注意key id 和 property id,key id 是属性key的id,举个栗子:name:李阳,这里的key id就是name这个property key的id,而name:李阳整体有一个id就是property id 了
4:其中对于property的存储:
一个Property Key所关联的属性值有可能有一个,也有可能有多个,因此,JanusGraph使用Cardinality来描述Property Key的这种特点。有SINGLE,LIST和SET三种类型, 源码中的PropertyKey接口可以看到:
public interface PropertyKey extends RelationType { Class<?> dataType(); Cardinality cardinality(); } 复制代码
- SINGLE表示一个Property Key只对应一个Value,这是最常用的场景。
Cardinality为SINGLE时的存储结构,HBase的列名只存储Property Key的ID。具体的Property Value值以及Property ID(JanusGraph为每一个Property分配的唯一ID),都存放在Cell的Value中。另外,如果该Property还有额外的Remaining properties,也会放在Value中。Remaining properties一般不使用,仅在一些特殊场景下,用于为该Property记录更多的附加信息(比如存储元数据Edge Labe的定义等)。
- LIST表示一个Property Key可以对应多个Value,多个Value可以有重复值。
Candinality为LIST时的存储结构,各个部分与Cardinality为SINGLE时的结构相似,区别在于属性的ID被放在了列名中,而不是放在Value中。
- SET表示一个Property Key可以对应多个Value,多个Value不可以有重复值。
Candinality为SET存储结构,各个部分与Cardinality为SINGLE时的结构相似,区别在于属性的值被放在了列名中,而不是放在Value中,前提是去除了重复。
JanusGraph的Property,在不同的Cardinality下,数据存储结构略有不同。整体原则是:根据Cardinality的不同,列名本身能够确定唯一的一个属性即可。
5:Edge label 的多样性
默认的多重性是MULTI
- MULTI:允许任意一对顶点之间的同一标签具有多个边。
- SIMPLE:在任何一对顶点之间最多允许拥有此类标签的一个边。
- MANY2ONE:在图形中的任何顶点上最多允许此标签的一个传出边,但不对传入边施加约束。边标签mother是MANY2ONE多样性的一个例子,因为每个人最多只有一个母亲,但母亲可以有多个孩子。
- ONE2MANY:在图形中的任何顶点上最多允许此标签的一个传入边,但不对传出边施加约束。边标签winnerOf是ONE2MANY多样性的一个例子,因为每个比赛最多只赢一个人,但一个人可以赢得多个比赛。
- ONE2ONE:在图表的任何顶点上最多允许此标签的一个传入边和一个传出边。边标签结婚是ONE2ONE多样性的一个例子,因为一个人与另一个人结婚。
Property Key和Edge Label被抽象成了Relation Type,并采用相同的数据结构。所以说 Property Key和Edge Label不能被设置为相同的名字。
6:序列化:
每个边和属性都作为一个cell存储在其相邻顶点的行中。它们会被序列化并且column的字节顺序会遵循edge 的column中的sort key进行存储。变量id编码方案和压缩对象序列化使每个edge/cell的存储所占空间都尽可能小。 边的序列化从边标签的唯一ID开始(由JanusGraph指定)。这通常是一个小数字,并且使用变量id编码进行压缩。该id的最后一位是偏移量,用于存储这个边是入边(in)还是出边(out)。接下来,存储包括sort key 的属性值,它是使用edge label定义的,因此排序键对象元数据可以引用边缘标签。之后,存储相邻顶点的id。JanusGraph不存储实际的顶点id,而是存储拥有此邻接列表的顶点的id。顶点id后跟此边的id,JanusGraph为每条边分配了一个唯一的id。这就是edge cell的column。edge的cell的column包含边的压缩序列化后的签名属性(由标签的签名键定义)以及未压缩序列化的边的任何其他属性。 属性的序列化表示更简单,column中只包含属性的键ID。属性id和属性值存储在value中。但是,如果将属性键定义为list()或者set(),则property id也存储在column中(上面property存储中说到过)。
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="true" 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。
refer:博客 博客
如果转载此博文,请附上本文链接,谢谢合作~ : juejin.im/user/5c3036…
如果感觉这篇文章对您有所帮助,请点击一下“喜欢”或者“关注”博主,您的喜欢和关注将是我前进的最大动力!
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- Oracle 体系结构 - 逻辑和物理存储结构之间的关系
- 树形结构数据存储方案(五):区间嵌套
- 树形结构数据存储方案(三):闭包表
- 树形结构数据存储方案(二): 物化路径
- [译] 数据库内部存储结构探索
- 请问二叉树等数据结构的物理存储结构是怎样的?
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
深度探索Linux操作系统
王柏生 / 机械工业出版社 / 2013-10-15 / 89.00
《深度探索linux操作系统:系统构建和原理解析》是探索linux操作系统原理的里程碑之作,在众多的同类书中独树一帜。它颠覆和摒弃了传统的从阅读linux内核源代码着手学习linux操作系统原理的方式,而是基于实践,以从零开始构建一个完整的linux操作系统的过程为依托,指引读者在实践中去探索操作系统的本质。这种方式的妙处在于,让读者先从宏观上全面认清一个完整的操作系统中都包含哪些组件,各个组件的......一起来看看 《深度探索Linux操作系统》 这本书的介绍吧!