从扩线查询能力分析分布式图数据库Titan的设计改

本文先简单介绍了图数据库的发展趋势，而后重点介绍了分布式图数据库Titan，围绕图数据库的典型查询(扩线查询)场景，分析了Titan在设计上的一些待改进点。

从DB-Engines统计信息来看图数据库发展趋势

 

 

从DB-Engines的数据库趋势信息来看，从13年至今，Graph DBMS是增长最快速的一类数据库。而下图给出了知名图数据库的数量以及在DB-Engines所收录的341种数据库中所占的比重：

 

 

尽管从实际的应用现状来看，图数据库依然还是一个相对小众的数据库，但从DB-Engines的趋势信息反映了图数据库未来的巨大发展潜力。

图数据库定义

百度百科对图数据库的定义：

图数据库是NoSQL数据库的一种，它应用图理论存储实体之间的关系信息。最常见例子就是社会网络中人与人之间的关系。关系型数据库用于存储“关系型”数据的效果并不好，其查询复杂、缓慢、超出预期，而图形数据库的独特设计恰恰弥补了这个缺陷。

如下内容翻译自维基百科：

图数据库以图论为基础，并以节点(顶点)、边和属性作为基本概念。

节点表示实体，如人、企业、账户或任何其他要表示的事物，大致相当于关系数据库中的记录、关系或行，或文档数据库中的文档。

边，也称为关系，是连接节点之间的线，表示它们之间的关系。边是图数据库中的关键概念，代表了在其他系统中不能直接实现的关系的抽象。

属性是节点(和边)的重要关联信息。例如，“维基百科”是一个节点，它的关联信息可以是“网站”，或者“参考文献”，或者是一个以“w”开头的字母，这些信息都可以是这个节点的属性。

图其实是一种表达能力非常强的模型，如用来描述社交关系网络，用户与产品的推荐关系，通信网络，交通网络等等，这类数据的特点是各种实体间的关系错综复杂，而实体自身还有属性描述信息，而如果使用传统的RDBMS来存储这类数据，将使得RDBMS变得”沉重不堪”。这类数据其实广泛存在于现实世界中，尤其是伴随着不断发展的人工智能技术，越来越多的复杂关系型向量型数据被挖掘出来，图数据库将会成为一种基础的数据库技术。在区块链领域，作为BlockChain 3.0的典型代表技术IOTA，它的核心技术其实已经是图技术。

图数据库与关系型数据库

数十年来，开发者习惯了使用关系型数据库处理关联的、半结构化的数据集。关系型数据库设计之初是为了处理纸质表格以及表格化结构，它们试图对这种实际中的特殊联系进行建模。然而关系型数据库在处理“复杂关系”数据时却显得力不从心。

让我们通过社交网络领域中一些简单的查询来理解关系型数据库中关系查询的代价。下面是专门介绍Neo4j技术的《Graph Databases》一书中提供的一个非常经典的例子：

下图展示了一个记录朋友关系的简单的连接表设计：

 

 

Person与PersonFriend表

当回答“who are Bob’s friends?”这个问题时很简单。SQL语句如下：

 

 

who are Bob’s friends?

基于这个示例数据，答案是Alice和Zach。这不是一个代价高昂或困难的查询，因为它使用了WHERE语句”WHERE p2.Person = ‘Bob’”，使得返回的行数是可预期的和受限的。

但如果要回答“who is friends with Bob?”，SQL语句则变为：

 

 

who is friends with Bob?

这个查询的答案是Alice。这个反向查询在实现上也很简单，但是数据库端的花销就略微大些了，因为所有的数据行都在PersonFriend中。我们可以加入索引，然后仍会涉及代价高昂的间接层。

当问题是“谁是Alice的朋友的朋友?”时查询就更复杂了:

 

 

谁是Alice的朋友的朋友?

当然基于RDBMS可以做到，而且这个查询还是可能在合理的时间内得到答案的。当查询延伸到第4层、第5层的朋友关系时，由于递归的JOIN查询使得此时的时间空间复杂度变得非常高，从而使查询的效率急剧恶化。

但利用图数据库，我们可以通过如下模型来描述上面的Person与PersonFriend两个表中的数据：

 

 

Person and PersonFriend In Neo4j

在图数据库中，类似于”Bob的朋友”以及”Bob的朋友的朋友“这类查询，我们称之为“扩线查询”。如果需要查询”Bob的朋友的朋友”，只需要从Bob这个节点出发，进行2层扩线查询。不仅在数据模型的表达上更加直观，查询效率也会有质的提升。当2层扩线查询中，如果结果集小于10万级别，Neo4j可以达到ms级别响应。

关于Titan

Titan有如下关键设计：

支持大规模图数据存储，Titan图数据库是建立在分布式集群上，数据存储容量和集群节点数量成正比
支持弹性和线性扩展，高可用，高容错
支持Gremlin图查询语言
支持利用Hadoop计算框架对图数据进行分析
支持外部索引：Elasticsearch、Solr、Lucene
支持ACID和最终一致性
支持多储存引擎：Cassandra、HBase、Berkeley DB和Immemory模式
基于Apache License 2.0

正是基于这些设计，Titan在2015年和2016年期间积累了一批用户，因为当时并没有多少开源图数据库可选。Titan项目原由Aurelius开发，但后来该公司被DataStax收购，Titan原来的开发团队转向闭源图数据库产品的研发，因此，导致Titan项目停更。后来，由IBM领头，在Linux社区开启了JanusGraph项目(该项目直接从Titan项目Fork而来)来试图让停更的Titan复活。但从JanusGraph代码的commits记录来看，尚未见到有较大的改动。

Titan扩线查询

下图是基于Titan的三层扩线过程详解：

 

 

图解

 

 

三层扩线查询流程

每一层查询的输入：

顶点集合VSet。第一层为用户给定的顶点集合，后面的每一层为上一层查询满足条件的边的顶点
顶点Label/顶点属性的过滤条件ConditionA;
边Label/边属性的过滤条件ConditionB。

每一层查询的输出：

1.VSet中满足条件ConditionA的顶点及属性集合ResultVSet;
2.ResultVSet中与每一个顶点相关的满足条件ConditionB的边的集合。

关于最后一次查询：

最后一次扩线查询只查询除了满足ConditionB的边，但与这些边相关的顶点仅有顶点ID的信息，尚不包含任何属性信息，更不确定是否满足ConditionA，因此，需要再做一次属性查询。

查询耗时估算方法：

假设，每一个顶点的出入度为M，属性查询耗时TP，边查询耗时TE，属性与边混合查询耗时TR，理论上，从一个顶点扩线总耗时约为：

TR+M*TR+M*M*TR+M*M*M*TP

因为属性与边是融合在一个列族中的，因此，属性查询耗时与边查询耗时是相互有影响的。从HBase查询原理上分析，TP/TE/TR的差别不是很明显，尤其是数据都没有命中缓存的情况下。

通过对Titan扩线查询能力的实际测试，得到如下一些结论：

当点的平均出入度为20时(即一个顶点的关联边的数目有20个)，从一个点出发，三层扩线耗时在秒级别

当点的平均出入度达到100，若无过滤条件，1个顶点三层扩线的结果将达到将近100w点和100w边，测试结果显示，在没有任何缓存的情况下，1个点的扩线查询耗时超过300秒

当适当的设置过滤条件将三层扩线的结果控制在10w级别，耗时在100s左右，50w级别耗时200s左右

从上面信息可以看出来，Titan的扩线查询效率是比较低的。下文中我们将结合Titan的数据结构进行相关分析。

Titan的数据结构

在Titan中，对象实体被称之为”顶点(Vertex)”，”Vertex”可以有表示其分类的Label信息，而Vertex的描述信息称之为Property。”Vertex”与”Vertex”之间的关系，被称之为”边(Edge)”。一个”Edge”可以是单向的，也可以是双向的。Edge有代表其分类的Label信息，Edge也可以有Property描述信息。

下面是Titan Document中提供的数据模型设计图：

 

 

Titan DataModel

以HBase作为后端存储引擎为例，我们简单说明一下上图中所提供的信息：

RowKey为vertex id

一个Vertex的Properties信息，以及与该Vertex相关的Edges，都以独立的列存储，而且被存成了一行数据

表示Edge的列中，包含了Label信息，Edge ID，相邻Vertex信息，属性等信息。

表示Vertex Perperty的列中，包含了Property的ID，以及Property的值

Titan有哪些待改进点

问题1：顶点属性和边存储在一行中，读取时会相互影响性能

假设顶点有10个属性，出边和入边总共100个，则在该顶点的一行数据中，会有110列(除用户数据之外，还会有一些系统属性，此处忽略)，那么查询该顶点的属性时相当于从110列中只取出10列，在效率上肯定慢于仅从10列中取10列数据，因为多扫描了一些无效数据。也就是说当点的出入度越大时，属性查询耗时将会越大，在扩线的最后一次查询点属性时，就会耗时越久。

问题2：边基于Immutable的存储设计, 属性查询和更新代价较大

从Titan的数据结构可以看出，边作为顶点中的一列存储，边的属性也全部存储在这一列中，那么更新其中某一个属性时，需要先获取整个边的数据，修改完成后再写回，效率较低。而且针对边的属性过滤，Titan的做法是将数据取回客户端，在客户端进行过滤。所以对于扩线场景，需要将所有的边取回客户端，然后再进行边的过滤，增加了网络传输的消耗。

问题3：Titan支持多个后端存储其实是一把双刃剑

Titan支持Cassandra、HBase、Berkeley DB和Immemory模式，JanusGraph还增加了BigTable的支持，无疑可以满足更多的用户，但是为了支持多个后端存储，就需要在软件架构上增加一个可以适配多个存储的数据格式(StaticBuffer)，数据无论是写入还是读取，都需要先转化成中间格式，这里带来了序列化和反序列化的一些性能损耗。当数据量比较小时，性能损耗可能还不是特别明显，但是当点和边到百万级别，这个损耗值相当可观。

问题4：Titan把后端存储当做黑盒，几乎纯Client端的实现

以HBase为例，Titan完全可以基于HBase深度定制一些功能，例如可以利用HBase的Coprocessor能力，将计算过程下推到HBase端，还可以定制查询过滤器，使得查询更加高效。但当前却完全未利用这些能力。

在提出了这些问题之后，事实上也是为JanusGraph指明了关键的优化方向。事实上，正是基于这些点，我们做过一些优化尝试，可以使得扩线查询有非常显著的提升，这些我们将再后续文章中展开。

关于图引擎

很多人往往混淆了图数据库与图引擎的概念，两者其实有各自的聚焦点:

图数据库：偏重于海量图数据的实时存储以及OLTP查询能力，本文着重介绍了图数据库Titan/JanusGraph，另外一个非常典型的图数据库为Neo4j。

图引擎：偏重于在海量图数据中利用成熟的图算法以及图计算引擎进行OLAP分析能力，如Pregel、Powergraph、GraphX等。

图数据库与图引擎，是一种互补关系，未来会有大量的结合应用场景。但在一个系统中，也完全可能融合这两种能力。去年年底，网上一篇名为《从图引擎平台技术，看华为云EI的决心和野心》的文章介绍了华为自研的高性能图引擎技术EYWA，能够在百亿边规模的图数据集中，提供秒级甚至是毫秒级的扩线查询能力，这是一个非常惊讶的结果，EYWA正是华为云已经上线公测的图引擎服务(GES)的核心技术，相信未来能在EYWA中看到融合了图数据库与图引擎的一体化图计算能力。

本文作者：张帅，毕杰山