图数据库论文阅读：分布式图数据库GeaBase
本文绝大多数内容翻译自阿里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 ])*相关文章