本文绝大多数内容翻译自阿里GeaBase团队于2017年发表在IEEE期刊上的图数据库论文《GeaBase：A High-Performance Distributed Graph Database for Industry-Scale Applications》，文中有很小部分的内容是笔者读论文时的理解。随性翻译，凑合看。
摘要
图分析(Graph Analytics)在过去几年中得到了迅猛的发展，它在工业界的应用领域五花八门，涵盖从电子商务(e-commerce)、社交网络（social network）和推荐系统（recommendation systems）到欺诈检测（Fraud Detection）。实际上，任何问题都需要洞察数据的连接信息，而不仅仅是理解数据本身。在本文中，我们提出了一种新型分布式图数据库GeoBase，它提供了大规模实时存储和分析 图结构数据的能力。我们描述了系统以及实现的细节，包括一种称之为更新中心（Update Center，简称UC）的新型更新架构（Update Architecture），以及一门适用于图遍历和图分析的新语言。我们也将GeoBase和广泛被使用的开源图数据库Titan进行了的性能方面的比较。实验表明，在我们的测试场景中，GeaBase比Titan快182倍；而在社交网络工作负载方面，GeaBase的吞吐量也比Titan提高了22倍。
#1 引言
我们正身处于一个大数据时代，数据间的连接信息和数据本身同样重要，它们一起记录着反映真实世界的信息。图由 二元组定义，这是一种表示数据和数据之间连接信息的很自然的方式。此处的V表示数据（data），也称之为节点（nodes）；而E表示数据之间的连接（connection between data），也称之为边（edges）。
为了高效存储和查询图，业界引入了图数据库。存储在图数据库中的图，通常都属于属性图模型（<节点，边，属性>三元组）。
这类（符合属性图模型）图数据库的关键特征之一是边（或连接）与顶点一同被视为模型的核心组件。因此，可以有效地检索复杂的拓扑结构。与之相反，传统的关系数据库，数据间的连接被单独地存在一张表中，搜索连接的查询需要执行JOIN操作，而JOIN操作通常代价很高。
然而，为工业级规模的应用设计一个高性能的图数据库是相当具有挑战性的。首先，图的不规则数据结构通常导致访问存储系统时产生随机IO，便会使数据局部（data locality）分布情况变差；其次，为了存储大规模的图，通常会对数据进行分区，这样就会提高通信代价，使工作负载（workload）变得不均衡；后，在数据迅速变更的分布式图数据库中保持数据一致性也是一件非常具有挑战性的事。
在本文中，我们会介绍GeaBase（Graph Exploration and Analytics Database，图探测和分析数据库）图数据库，它是一款能够为工业级规模的应用提供实时图遍历和实时图分析功能的新型图数据库。我们将会详尽描述GeaBase架构与实现的完整细节。为了实现高性能和数据一致性这两大目标，GeaBase采用了一些技术：计算靠近存储、双队列更新流水线和用户粘性等。
本文其余部分结构如下：在第二节中，我们描述了文献中的相关工作。在第三节中，我们讨论了GeaBase的实现细节和数据结构。在第四节中，我们讨论了GeaBase的性能，并将结果与开源的分布式图数据库Titan进行了比较。在第五节中，我们总结了本次研究结果，并讨论了未来开展研究工作的方向。
#2 相关工作
文献中已经介绍了几种用以解锁数据连接价值的图数据库和图分析系统。据db-engines.com排名看，Neo4J目前是图数据库中受环境的产品。Neo4J早在十多年前就发行了版产品，并且它已经建立起了一个大型的开发者社区。然而，Neo4J对扩展性仅提供了有限的支持（目前，Neo4J社区版仅支持单机部署，即用户只能纵向拓展机器配置，而企业版提供了横向扩展能力，不过收费不菲），因此它无法处理类似阿里巴巴这样的大公司中的大规模数据集。先进的分布式数据库都具有横向扩展能力，它们一般采用诸如Gremlin或SparQL这样的标准图查询语言。这些查询语言对图分析的支持很有限，如文献[7]–[10]中所提到的离线图分析系统，它们无法实现处理查询时更新或实时响应。
#3 系统概述
在本节中，我们将会详细地介绍GeaBase图数据库的系统架构。如图2所示，GeaBase由四大模块构成：高可用（HA）模块、查询引擎、更新模块和图存储。我们将在下面的小节中分别描述这四个模块。
A. 图存储
在GeaBase图数据库中，节点和边都以键值对格式存储。依据用户自定义的模式，属性（properties）序列化后会被存储到值的部分。依据基于哈希的分片策略， 这些记录（records）会被存到不同的分片（shards）上。在通常情况下，单个GeaBase实例会包含数十个甚至数百个这样的分区，这些分区都会由分区管理器（shard manager）所维护。接下去我们会分别描述数据模型和存储模型的更多细节。
1）数据模型
图数据库的基本数据模型是描述对象链接属性（object-link-property，OLP）。GeaBase数据模型的设计目的是支持海量规模和多维的图，这些图包含具有类型信息的节点，具有方向和类型信息的边以及在节点和边上都附有属性信息。因为多维图是由各种类型的节点和边构成的，所以这些节点和边代表着各种类型的对象以及对象之间复杂的关系。
正如上面提到的那样，GeaBase实例的数据模型使用图模式（Graph Schema）来描述，图模式包含一个节点类型列表 和一个边类型列表。图模式中的节点类型包含一个声明其类型的字段，以及一个表示节点属性字段的键值对列表。对于图模式中的有效节点来说，源节点类型、目的节点类型、边类型、属性列表和方向（orientation，可细分为有向directed或无向undirected）都是必需的。除了上面提到的基本需求之外，用户还可以向节点和边添加可选字段（比如，TTL字段，它表示节点或边的生存时间）。总而言之，当给定一个特定的边或节点类型时，可以从这个图模式中了解到相关的拓扑结构和序列化格式。
2）存储模型
下表给出了GeaBase存储系统中的键值对结构。具体来说，节点以单键值对格式 存储，这个键值对由节点ID、节点类型和节点属性组成。有向边以双键值对格式 存储，称为出边和入边。
它们（指上文提到的出边和入边）都由源节点ID、边类型、时间戳、目标节点ID和边属性这几部分组成。当给定源节点ID，出边则可视为正向索引（Forward Index），用于搜索到达目标节点的轨迹（这种情况可称之为出边导航，out-edge-navigation）。当给定目标节点，入边则可视为反向索引（Reverse Index），用于搜索到达源节点的轨迹（这种情况可称之为入边导航，in-edge-navigation）。所有的边类型、节点类型以及给定边或顶点的属性格式，都已在上文提到的图模式中定义了。
为了节省存储空间，有向边的属性可以存储在某个方向所对应的纪录上。例如，某种已确定类型的边把属性存储在了出边（OutEdge），这意味着会把属性与正向索引会存在一起（Real Property，即实际存储属性），那么反向索引和属性就不会存在一起了（Empty Property，即实际不存储属性）。假设key和vaule的容量比是 ，在出边和入边中都要存储一份相同的属性则需要
倍的容量，仅在一种边上存储属性仅需要
（原文是
，笔者认为有误）倍的容量。
3）分片策略
基于上述数据模型和存储模型，执行分区操作如下。所有记录（Record）都根据键的前8个字节进行分区。例如来说，节点记录会根据节点ID来分散存储（它的键由12个字节构成，前8个字节表示节点ID，后4个字节表示节点类型，因此节点纪录根据节点ID进行分区），出边纪录会根据源节点ID来分散存储，而入边纪录则会按照目标节点ID来分散存储。
采用这种分区策略背后的动机是为了避免在网络中传输大量数据。通过这种分区策略，源节点与其所有出边会位于相同的分区中，该策略同样适用于目标节点和入边。因此，在正向遍历的情况下，我们可在同一分区中获取到边和目标节点的属性。
B. 高可用模块
GeaBase集群的所有节点都会与Zookeeper集群服务间维持心跳联系，从而实现GeaBase服务的高可用。每一个GeoBase集群都保存了一份图数据的完整拷贝，因而也被命名为GeaBase副本（GeaBase Replica）。如果一个GeaBase服务器或一个GeaBase副本崩溃，那么在该服务器和ZooKeeper之间维持的心跳将会超时，随后该服务器信息将从ZooKeeper中剔除。当客户端和其他GeaBase服务器检测到这种变化时，它们会将计算重定向到具有相应数据的其他服务器上（服务失效，计算转移）。
GeaBase的高可用性由主机管理器（Host Manager）、分区管理器（Shard Manager）、心跳客户端（HeartBeat Client）、心跳监控器（HeartBeat Monitor）、配置管理器（Config Monitor）和 ZK集群 这几个模块配合实现。
具体的高可用性实现过程如下：
- 在每一个响应器（Responser）的查询服务启动时，GeaBase将同时启动心跳客户端和主机管理器。
- 心跳客户端会定时向 ZooKeeper汇报自己的状态（是否可用）。主机管理器内部维护了一个心跳监控器和一个配置管理器，分别定时从 ZooKeeper 读取每个响应器的状态以及配置文件的变化信息。
- 如果发生了变化，心跳监控器和配置管理器就会通知主机管理器，然后主机管理器根据情况改变分区管理器中维护的映射表。这样，每个响应器的映射表都是新且一致的，在任何响应器不可用时，查询都会被及时地调度到可用的响应器。
C. 更新模块
本节介绍更新模块的详细信息。GeaBase为数据更新提供了实时和批处理这两种方式，本节会分别详细描述这两种方式。
1）实时更新
实时数据在业务决策、金融风险管理以及其它行业分析领域变得越来越重要。例如，在电子商务中，实时用户行为数据，诸如点击、收藏和购买，它们对于建立用户画像和优化推荐效果是至关重要的。在金融领域里，实时用户购买和交易的数据是风险管理的基础性资源。
如图3所示，针对不同的情况，我们提供了两种实时更新模式：同步模式 和异步模式。在同步模式中，上游系统（Upstream System）将一个更新事件（Update Event）转换成一个查询字符串（Query String），并将转换后的查询字符串直接发送给某个GeaBase Server，然后等待Server端返回携带着更新状态信息的响应。如果更新事件处理成功了，那么后续的读查询（Read Queries）就能够获取到新的数据。当这个模式与上文中所提到的用户粘性策略（User-tickness Strategy）一起使用时，用户每次都会得到完全一致的数据（这段话略微难理解，实际上它在说用户黏着一致性，而用户黏着一致性是终一致性的一个分支）。
在某些情况下，用户更关心更新吞吐量，而不是更新及时性。上游系统可以选择将更新事件转换为消息，然后将其放至分布式队列，所有的GeaBase副本会对消息进行异步消费。在实际应用中，在不同区域（Region）中的多个分布式消息队列服务均可用时，系统会选择接近上游系统的消息队列服务。剩余的工作就是GeaBase副本通过客户端持续地消费所有区域中的所有消息队列中排队着的更新消息。
部分应用并不要求严格的更新顺序，而是需要较高的更新吞吐量。针对这些情况，GeaBase提供了一种异步模式来实现数据的实时更新。上游系统会将更新事件转换成消息，并将其放入分布式消息队列，后这些消息会被GeaBase的副本（Replicas）异步消费掉。
具体来说，放在消息队列中的数据是根据GeaBase预定义的切分策略进行分区的，并且每个Geabase服务器订阅以使用与其所持有的切分对应的队列分区。这种系统架构保证弱消息序。在每一个分区中，消息序列是由消息的接收顺序所决定的；然而，跨分区的消息无法保证有序（同一分区的消息会被有序消费，不同分区间消息无法保证消费的前后顺序）。共享相同Key ID的节点或边的消息，将会被发送到相同的分区。因此，对同一节点或边所做的添加/更新/删除操作，会根据消息发送的顺序被GeaBase副本依次消费掉。
不过这种架构有三大缺点。首先，它不能确保GeaBase副本间的数据一致性。其次，每个GeaBase副本会重复消息编码过程，这样会浪费宝贵的CPU资源。其三，队列消费者太多，会增加队列服务器的压力。
为解决上面提到的问题，我们提出了一种更新中心（Update Center）架构。如图3所示，其中一个GeaBase副本被选为更新中心，它负责集中消费 多个消息队列（存储用户侧生产的消息）中的消息，我们把这个消费多个消息队列的更新中心称为Master队列。更新中心会将编码后的二进制格式消息写入自身的存储系统，并将这个编码后的消息发送给另外一个队列，这个队列我们称之为Slave队列。所有其他的副本（我们称为Slave副本）消费Slave队列中的二进制格式消息并相应地持久化到它们各自的存储系统。通过这种方式，所有的副本始终消费相同的数据，从而确保了数据的一致性。除此之外，编码过程仅在更新中心执行（避免消息被多次编码，浪费宝贵的CPU资源）。值得一提的是，更新中心可以切换到任意的其他副本，因为它们之间的区别仅是消费了不同类型的消息队列。
2）批量更新
尽管采用了实时更新的方法，但有时用户需要从数据仓库中导入离线计算的结果，如图4所示。数据仓库中的数据通常被格式化为表。我们要求所有表都包含以下元素：键ID（Key ID）、值和标记（Tag）。标记表示特定的更新方法，如添加、删除、更新。GeaBase服务器会对表进行分片，每个服务器读取表的一个子集并相应地更新数据库。
D. 查询引擎
1）引擎结构
查询引擎的基本设计原则之一是“计算靠近存储 ”。查询处理如下。当geabase服务器收到查询请求时，它检查查询语句的语法正确性，然后生成与查询语义对应的遍历和计算计划。当查询需要非本地数据时，查询引擎生成一个子查询，该子查询检索远程数据，并通过内部请求将子查询发送到目标节点所在的服务器。如果不需要内部请求，则遍历计划结束，结果数据被发送回客户机。
2）查询语言
GeaBase为图查询和分析提供了一套新的查询语言。GeaBase查询语言支持三种操作：
- 图CRUD操作：GetNodeProp（获取节点属性）、GetEdgeProp（获取边属性）、nav（Navigation，图导航，请参见下文）、GetDistance、Limit、Add/Delete Node/Edge
- 遍历与计算：Sort、Union、Subtract、Combine（set operations）、Agg（group by）、For（iterations）、variables
- 分析：FindLoop、ShortestDistance、KCore等
- 内建（build-in）函数，并且支持用户自定义函数（UDF）
GeaBase查询语言有着类似LISP语言的语法形式，如下所示
( operator [:ATTR=value ])*其中，[:ATTR=value]可以是子查询。
接下去，我们阐述一些常用的算子。请参考我们的网站获取更多细节信息。
3) Nav算子
类似SQL语言中的SELECT语句，Nav(igation) 是GeaBase查询语言中是常用的算子。
(Nav [:START= | :DATA=]
[:EDGE_TYPE= | :REG_EDGE_TYPE=]
[:DEPTH=][:FILTER=][:RETURN=]
[...]
)其中，
- start：起始节点ID。
- edge_type | reg_edge_type：导航的特定边类型或正则表达式。
- depth：导航的大深度（默认值为1，大值为5）。
- filter：过滤条件（类似SQL的where语句）。
举例如下：
(Nav :DATA=(Nav :START=123
:EDGE_TYPE="friend"
:RETURN=@name,@age
:FILTER=@age>40)
:EDGE_TYPE="family"
:RETURN=$0,$1,@location,@city
)内嵌的Nav子查询，
(Nav :START=123
:EDGE_TYPE="friend"
:RETURN=@name,@age
:FILTER=@age>40
)返回节点ID等于123的朋友（边的类型）的名字和年龄（顶点属性），它的过滤条件是朋友节点的年龄应该大于40岁。外部Nav子查询返回所得所有朋友节点的名字和年龄($0，$1)以及它们的家庭住址和所在城市(@location，@city) 。
#4 实验
在本节中，我们将通过实验来验证所提系统的性能。我们使用Twitter社交数据集，通过一系列查询来说明GeaBase的延时、吞吐量和伸缩性，并用流行的开源图数据库Titan来对比结果。性能数据以及实现相关的细节按以下顺序排序提供：1）延时分析，2）吞吐量分析，3）伸缩性分析。
在实验中，我们使用的twitter数据集大约有14.7亿关于follow-following拓扑结构的社交关系（图中的边），这些关系遵循非幂律随动分布（non-power-law follower distribution）。为了测试性能，我们在每条边上添加四个属性：一个长度为10字节的字符串属性、一个长度为100字节长度的字符串属性、一个64位长整型属性和一个双精度浮点型属性。以下实验使用三种类型的查询进行：
- 单跳：Nav查询语句执行一次遍历操作，该操作从一个给定的节点（在我们的例子中是一个用户）开始，遍历边后读取表示起始用户的follower节点，并返回所遍历边的属性。该查询执行单跳遍历，检索一万个节点以及它们所有的属性。
- 双跳：该查询执行两个递归Nav查询操作，检索该用户的双跳follower（即该用户的间接粉丝），每一个Nav查询为起始节点检索出一百个节点。因此，总共会检索一万个节点，每个节点还会返回一个属性（短字符串属性）。
- 四跳：类似于两跳的情况，该查询会执行四个递归Nav查询来检索用户的四跳follower，每个Nav操作检索每个起始节点的一百个节点，并为每个节点检索一个属性。
A. 实验装置
- 性能评估的环境：Linux Kernel v2.6.32，256GB RAM、2 * Intel Xeon 16-Core CPU E5-2682 v4 at 2.50GHz（时钟频率2.50GHz），存储使用SSD，10Gb/s带宽的以太网。
- 实验中用于对比的Titan版本是Community v1.1.0，存储后端使用HBase，混合索引服务使用ElasticSearch。Hadoop/HDFS v2.7.2（3副本），HBase v1.2.3，ElasticSearch v1.5.2。
- 我们定义了遵循GeaBase测试数据结构的图模式，用于构建一个标准的Titan图。用户被视为节点中的字符串属性。Titan为每个节点分配一个全局的ID，并将它作为行键存储在HBase中。为了加快查询，我们为顶点和边各自添加了复合索引（composite index）。在客户端侧，我们使用JavaAPI来构建TitanGraph对象，用以直连HBase集群。
- 所有性能数据取10次查询结果的平均值。每个查询只发送一次，因此后端存储缓存将永远不会命中。
B. 延时结果
我们首先通过测量查询的延时来检查GeaBase的性能，并将结果与Titan进行比较。
图5、图6和图7所示的结果分别表明了GeaBase在单跳、双跳和四跳查询中的性能。从图中可以看出，与Titan相比，GeaBase的单跳查询快了182倍，四跳查询快了62倍。
性能差异较大的原因如下：首先，GeaBase可以通过数据聚类（data clustering，某个点及其邻接边的数据存放在同台机器上）以及采用计算靠近存储的策略来实现更好的数据本地性（data locality）。另一方面，Titan需要从复合索引中搜索起始节点ID来寻到全局ID，然后定位到HBase中全局ID所对应的行，该行中存储了属性。这个过程至少会导致两个检索操作，而GeaBase只需要一个操作。另一方面，所有属性键和节点ID都存储在同一个命名空间中，因为Titan中只有一个表，这将降低查询速度。
另外，在两跳遍历过程中，Titan将每一个查询拆分成一系列RPC调用（串行RPC请求），这些RPC调用复用同一个连接。举例来说，如果您想要检索某个节点的100个follower，它可能会产生至少100次远程调用，并且所有这些调用都是串行发送的，这是非常昂贵的。
除此之外，HBase运行环境依赖JVM，无法主动地控制垃圾收集（GC），而GeaBase存储引擎是用C++编写的，所有它没有这个问题。
这些数据还表明，GeaBase和Titan之间的性能差距在四跳查询时变小了。这是因为四跳查询的通信成本比单跳查询要高得多，其中并没有workers之间的通信。而对于Titan来说，与上述原因相比，内部通信不是一个重要因素。因此，在相同的网络规格下，由于通信成本相似，所以Geabase和Titan之间的性能差距会更小。
c. 吞吐量结果
接下来，我们评估GeaBase的吞吐性能。我们使用与#4-B节相同的查询语句，并测量系统的总吞吐量。
图8、9和10的结果再次证明了它具有比Titan更加优异的性能。在实验中，GeaBase较Titan提升了5到20倍的吞吐量。
D. 可扩展性结果
为了研究GeaBase如何扩展，我们在不同数量的服务器上，使用相同的数据集和相同的查询语句来测量GeaBase的吞吐量，测试结果如图11所示。如您所见，GeaBase在单跳查询场景下实现了近似的线性伸缩性。对于两跳和四跳场景，由于数据共享，GeaBase引擎需要向其他的GeaBase服务器发送远程查询请求，因此通信成本会高得多，这使得图应用的伸缩性变得较差。GeaBase试图对目标服务器进行分组来改进这一点，将通信成本降到低。
#5 结论
本次工作介绍了GeaBase，它是一款高性能可扩展的分布式系统，可用于在线图形遍历（Graph Traversal）和图分析（Graph Analysis）。
该系统采用了诸如更新中心架构 和用户黏着（会话黏着一致性）等新策略，在数据一致性的支持下，实现了高性能的图查询。本文中，我们将GeaBase与流行的分布式开源图数据库Titan进行了比较，结果表明GeaBase比Titan快了182倍。GeaBase使用一个轻量级策略（用户会话粘性一致性，user-stickness）来提供些许一致性功能，但该策略在很多应用中可能还不够。我们将会在今后的工作中进一步探讨这些问题。此外，我们还计划支持更多的图分析功能。
鸣谢
感谢所有参与GeaBase开发的研发人员（此处省略若干大牛），同业也要感谢阿里巴巴集团内部提供有用反馈、建议和BUG报告的为GeaBase用户。
参考文献
来源 https://zhuanlan.zhihu.com/p/69073081
