GRIN: 图检索接口¶
GRIN是GraphScope中提出的一种标准图数据检索接口。其目标是为图计算引擎提供一种统一的方式，以检索存储在GraphScope内不同存储引擎中的图数据，并简化这些引擎之间的集成过程。
GRIN 是用 C 语言定义的，因此可以移植到用不同编程语言（如 C++、Rust 和 Java）编写的系统中。它提供了一组通用的操作和数据结构处理程序，可用于访问图数据，而无需考虑底层存储引擎。
遍历：通过导航图结构来探索顶点之间的关系
检索：获取顶点和边的数据及属性
过滤器：基于分区或属性条件筛选数据结构
最新版本的标头可在GRIN中找到。 针对计算和存储的Vineyard实现可在Vineyard中找到。
动机¶
GRIN背后的动机源于需要为GraphScope的计算引擎制定一个通用的图数据访问标准。促成这一需求的因素包括：
整合多种图计算引擎和存储引擎的复杂性：GraphScope包含众多图计算引擎和存储引擎，每个引擎都有自己的数据模型、查询语言和API。这使得这些引擎之间的集成具有挑战性，因为每个引擎都需要单独的集成工作。
互操作性与协作的需求：为了充分发挥GraphScope的潜力，需要增强不同组件之间的互操作性和协作。建立统一的图数据访问标准将有助于加速GraphScope的发展，并使其对更广泛的用户群体更加易用。
大规模图处理需求日益增长：随着生成的数据量不断增加，市场对能够高效分析大规模图数据的图处理系统的需求也在持续上升。建立统一的图数据访问标准有助于加速GraphScope引擎新功能的开发。
通过在C语言中定义GRIN接口，可以轻松地通过外部函数接口(FFI)与包括Java、Python和Rust在内的多种编程语言集成，使这些语言能够调用C函数。此外，GRIN成为一种与语言无关的标准，可在不同的编程环境中使用，而无需每个环境都自行实现该标准。这极大地简化了依赖GRIN的图计算系统的开发和维护，因为它允许开发人员使用他们偏好的编程语言和工具，同时仍然能够使用通用标准访问和处理图数据。
统一图检索¶
如前所述，GRIN为计算引擎提供了一种统一的方法，通过一组通用的图遍历、数据检索和条件过滤操作来访问存储在不同存储引擎中的图。这些操作被定义为C函数，其返回值和参数通常是图概念的句柄，例如顶点和边。
以下示例展示了如何使用GRIN API处理图查询。带有GRIN_前缀的数据类型是句柄，而带有grin_前缀的函数则是GRIN中的API。此外，GRIN还提供了以GRIN_开头的宏来反映存储特性。每个实现GRIN API的存储引擎都可以根据自身特性（如图分区策略和列表检索方式）来配置这些宏。本示例的存储提供者是Vineyard。
该示例演示了如何同步与特定边类型关联的顶点属性值。输入参数包括partitioned_graph、本地partition、edge_type_name（例如likes）和vertex_property_name（例如features）。任务是找到所有类型为"likes"的"边界边"的目标顶点，且这些顶点必须具有名为"features"的属性。在此上下文中，边界边是指源顶点为主顶点、目标顶点为镜像顶点的边，这基于底层存储使用的"边切割"分区策略。对于每个这样的顶点，我们会将其"features"属性值发送到其主分区。
void sync_property(GRIN_PARTITIONED_GRAPH partitioned_graph, GRIN_PARTITION partition, const char* edge_type_name, const char* vertex_property_name) {
GRIN_GRAPH g = grin_get_local_graph_from_partition(partitioned_graph, partition); // get local graph of partition
GRIN_EDGE_TYPE etype = grin_get_edge_type_by_name(g, edge_type_name); // get edge type from name
GRIN_VERTEX_TYPE_LIST src_vtypes = grin_get_src_types_from_edge_type(g, etype); // get related source vertex type list
GRIN_VERTEX_TYPE_LIST dst_vtypes = grin_get_dst_types_from_edge_type(g, etype); // get related destination vertex type list
size_t src_vtypes_num = grin_get_vertex_type_list_size(g, src_vtypes);
size_t dst_vtypes_num = grin_get_vertex_type_list_size(g, dst_vtypes);
assert(src_vtypes_num == dst_vtypes_num); // the src & dst vertex type lists must be aligned
for (size_t i = 0; i < src_vtypes_num; ++i) { // iterate all pairs of src & dst vertex type
GRIN_VERTEX_TYPE src_vtype = grin_get_vertex_type_from_list(g, src_vtypes, i); // get src type
GRIN_VERTEX_TYPE dst_vtype = grin_get_vertex_type_from_list(g, dst_vtypes, i); // get dst type
GRIN_VERTEX_PROPERTY dst_vp = grin_get_vertex_property_by_name(g, dst_vtype, vertex_property_name); // get the property called "features" under dst type
if (dst_vp == GRIN_NULL_VERTEX_PROPERTY) continue; // select out the pairs whose dst type does NOT have such a property called "features"
GRIN_VERTEX_PROPERTY_TABLE dst_vpt = grin_get_vertex_property_table_by_type(g, dst_vtype); // prepare property table of dst vertex type for later use
GRIN_DATATYPE dst_vp_dt = grin_get_vertex_property_data_type(g, dst_vp); // prepare property type for later use
GRIN_VERTEX_LIST __src_vl = grin_get_vertex_list(g); // get the vertex list
GRIN_VERTEX_LIST _src_vl = grin_select_type_for_vertex_list(g, src_vtype, __src_vl); // select the vertex of source type
GRIN_VERTEX_LIST src_vl = grin_select_master_for_vertex_list(g, _src_vl); // select master vertices under source type
size_t src_vl_num = grin_get_vertex_list_size(g, src_vl);
for (size_t j = 0; j < src_vl_num; ++j) { // iterate the src vertex
GRIN_VERTEX v = grin_get_vertex_from_list(g, src_vl, j);
#ifdef GRIN_TRAIT_SELECT_EDGE_TYPE_FOR_ADJACENT_LIST
GRIN_ADJACENT_LIST _adj_list = grin_get_adjacent_list(g, GRIN_DIRECTION::OUT, v); // get the outgoing adjacent list of v
GRIN_ADJACENT_LIST adj_list = grin_select_edge_type_for_adjacent_list(g, etype, _adj_list); // select edges under etype
#else
GRIN_ADJACENT_LIST adj_lsit = grin_get_adjacent_list(g, GRIN_DIRECTION::OUT, v); // get the outgoing adjacent list of v
#endif
size_t al_sz = grin_get_adjacent_list_size(g, adj_list);
for (size_t k = 0; k < al_sz; ++k) {
#ifndef GRIN_TRAIT_SELECT_EDGE_TYPE_FOR_ADJACENT_LIST
GRIN_EDGE edge = grin_get_edge_from_adjacent_list(g, adj_list, k);
GRIN_EDGE_TYPE edge_type = grin_get_edge_type(g, edge);
if (!grin_equal_edge_type(g, edge_type, etype)) continue;
#endif
GRIN_VERTEX u = grin_get_neighbor_from_adjacent_list(g, adj_list, k); // get the dst vertex u
const void* value = grin_get_value_from_vertex_property_table(g, dst_vpt, u, dst_vp); // get the property value of "features" of u
GRIN_VERTEX_REF uref = grin_get_vertex_ref_for_vertex(g, u); // get the reference of u that can be recognized by other partitions
GRIN_PARTITION u_master_partition = grin_get_master_partition_from_vertex_ref(g, uref); // get the master partition for u
send_value(u_master_partition, uref, dst_vp_dt, value); // the value must be casted to the correct type based on dst_vp_dt before sending
}
}
}
}
void run(vineyard::Client& client, const grape::CommSpec& comm_spec,
vineyard::ObjectID fragment_group_id) {
LOG(INFO) << "Loaded graph to vineyard: " << fragment_group_id;
auto pg = get_partitioned_graph_by_object_id(client, fragment_group_id);
auto local_partitions = grin_get_local_partition_list(pg);
size_t pnum = grin_get_partition_list_size(local_partitions);
assert(pnum > 0);
// we only sync the first partition as example
auto partition = grin_get_partition_from_list(local_partitions, 0);
sync_property(pg, partition, "likes", "features");
}
GRIN 概念¶
本节将解释GRIN中的关键概念，帮助用户更轻松地理解GRIN API。
预定义宏¶
GRIN提供了一组预定义的C宏，供存储引擎用于描述其特性。当存储引擎实现GRIN API时，应首先设置这些宏以展示其功能特性，例如分区策略和启用的索引。
好处是双重的：
在计算引擎方面，当不同存储引擎声明或弃用某些功能时，开发者可以使用替代逻辑和GRIN API来实现他们的方法。这使得基于存储功能声明的代码切换发生在编译阶段而非运行时。因此，它在不牺牲效率的前提下扩展了GRIN实现方法的多功能性。
在存储引擎方面，预定义的宏可以过滤掉大量不必要的API，避免开发者用样板代码或低效方式实现它们，因为不同存储引擎的设计可能存在巨大差异。
以下是一个关于顶点属性局部完备性的预定义宏示例。
提供了四个宏：
GRIN_ASSUME_ALL_VERTEX_PROPERTY_LOCAL_COMPLETEGRIN_ASSUME_MASTER_VERTEX_PROPERTY_LOCAL_COMPLETEGRIN_ASSUME_BY_TYPE_ALL_VERTEX_PROPERTY_LOCAL_COMPLETEGRIN_ASSUME_BY_TYPE_MASTER_VERTEX_PROPERTY_LOCAL_COMPLETE
某些假设可能比其他假设更具主导性，这意味着某些假设适用的范围比其他假设更广。因此，存储提供商在设置这些假设时应谨慎。在这里，假设1主导其他假设，这意味着当定义了假设1时，假设2至4将无效。此外，假设2主导假设4，假设3也主导假设4。
GRIN在不同假设下提供不同的API接口。假设仅定义了3；这意味着特定类型的顶点在本地拥有完整的属性，无论该顶点是主节点还是镜像节点。在这种情况下，GRIN提供了一个API来返回这些本地完整的顶点类型。
如果这四个宏都未定义，GRIN将提供一个针对每个顶点的API，用于判断顶点属性是否在本地完整。
分区策略¶
GRIN提供两种预定义的分区策略类型（即边切分和顶点切分）。每种策略可视为基于对分区策略的普遍理解而设计的一组细粒度预定义宏。对于采用混合分区策略的存储系统，开发者可以依次设置这些细粒度宏。
边切分策略¶
顶点数据对于主顶点来说是本地完整的。
所有边的边数据在本地都是完整的。
主顶点的邻居在本地是完整的。
顶点属性在主顶点上是局部完整的。
所有边的边属性在本地都是完整的。
顶点切割分区策略¶
所有顶点的顶点数据在本地都是完整的。
所有边的边数据在本地都是完整的。
镜像分区列表可用于主顶点广播消息。
所有顶点的顶点属性在本地都是完整的。
所有边的边属性在本地都是完整的。
属性图模型¶
GRIN对其属性图模型做出以下假设。
顶点有类型，边也有类型。
边类型与顶点类型对之间的关系是多对多的。
属性绑定到顶点和边类型，但某些属性可能具有相同的名称。
可以为顶点和边（非其类型）分配标签，主要用于查询过滤，且标签不具有属性。
实现指南¶
计算引擎¶
从GRIN获取GRIN API
使用GRIN API实现一个包装类（通常是
grin_fragment或grin_graph）。当你发现某些功能难以实现或效率低下时，请与GRIN设计者讨论。
使用包装类（例如
grin_fragment）编写或修改应用程序。寻找一个存储实现来设置端到端测试。
存储引擎¶
在您的系统中创建一个grin文件夹，并导航进入该文件夹。
将GRIN添加为子模块，并将
predefine.template复制出来作为predefine.h
$ git submodule add https://github.com/GraphScope/GRIN.git include
$ cp include/predefine.template predefine.h
根据存储特性修改
predefine.h中的StorageSpecific部分。尽可能在grin下的另一个文件夹（例如src）中实现头文件。如果发现某些函数的时间复杂度不是图大小的亚线性，请与GRIN设计者讨论。
编写一个特定于存储的方法，从您的存储中获取图处理器。
运行图遍历测试。
设计详情¶
处理器¶
GRIN 提供了一系列处理图概念的处理器，例如顶点、边和图本身。
由于GRIN中几乎所有内容都是处理器，只有少数字符串名称例外，因此在GRIN中图概念的类型与其处理器总是混合使用的。
例如，GRIN使用Vertex类型来表示顶点处理器的类型，而不是使用VertexHandler以保持代码简洁。
边¶
对于任何有向边
(u, v)，其中方向从u指向v，u是源顶点，而v是目标顶点。
列表¶
GRIN提供了两种可选方法，即数组式检索和迭代器，用于GRIN_VERTEX_LIST、GRIN_EDGE_LIST和GRIN_ADJACENT_LIST的列表检索。
对于其他模式级别的列表，如GRIN_VERTEX_TYPE_LIST或GRIN_PARTITION_LIST，GRIN通常采用数组式列表检索方式，并且不会为这些列表提供GRIN_ENABLE_宏。
数组式检索¶
只有当存储能够提供列表的大小以及按位置（即数组索引）检索元素的API时，用户才能使用列表处理程序的数组式检索功能。否则，存储应提供一个列表迭代器，详见下一节。
通常，数组式检索由以
_LIST_ARRAY结尾的宏控制顶点列表数组式检索示例
/* grin/topology/vertexlist.h */ GRIN_VERTEX_LIST grin_get_vertex_list(GRIN_GRAPH g); // 获取图的顶点列表 #ifdef GRIN_ENABLE_VERTEX_LIST_ARRAY size_t grin_get_vertex_list_size(GRIN_GRAPH g, GRIN_VERTEX_LIST vl); // 实现返回顶点列表大小的API GRIN_VERTEX grin_get_vertex_from_list(GRIN_GRAPH g, GRIN_VERTEX_LIST vl, size_t idx); // 实现按位置返回顶点列表元素的API #endif /* run.cc */ { auto vertexlist = grin_get_vertex_list(g); // 使用图(句柄)g auto sz = grin_get_vertex_list_size(g, vertexlist); for (auto i = 0; i < sz; ++i) { auto v = grin_get_vertex_from_list(g, vertexlist, i); } }
列表迭代器¶
如果列表大小未知或为了提高顺序扫描效率，会向调用者提供一个列表迭代器处理器。
通常迭代器是通过以
_LIST_ITERATOR结尾的宏来启用的顶点列表迭代器示例
/* grin/topology/vertexlist.h */ #ifdef GRIN_ENABLE_VERTEX_LIST_ITERATOR GRIN_VERTEX_LIST_ITERATOR grin_get_vertex_list_begin(GRIN_GRAPH g, GRIN_VERTEX_LIST vl); // 获取顶点列表的起始迭代器 GRIN_VERTEX_LIST_ITERATOR grin_get_next_vertex_list_iter(GRIN_GRAPH g, GRIN_VERTEX_LIST_ITERATOR vli); // 获取下一个迭代器 bool grin_is_vertex_list_end(GRIN_GRAPH g, GRIN_VERTEX_LIST_ITERATOR vli); // 检查是否到达末尾 GRIN_VERTEX grin_get_vertex_from_iter(GRIN_GRAPH g, GRIN_VERTEX_LIST_ITERATOR vli); // 从迭代器中获取顶点 #endif /* run.cc */ { auto iter = grin_get_vertex_list_begin(g, vl); // 使用图(句柄)g和顶点列表vl while (!grin_is_vertex_list_end(g, iter)) { auto v = grin_get_vertex_from_iter(g, iter); iter = grin_get_next_vertex_list_iter(g, iter); } }
属性¶
属性与顶点和边类型绑定。这意味着即使某些属性可能具有相同的名称，只要它们绑定到不同的顶点或边类型，GRIN就会为这些属性提供不同的处理程序。这是因为，尽管具有相同名称的属性通常在图中提供相同的语义，但出于效率考虑（例如短日期和长日期），它们在底层存储中可能具有不同的数据类型。
为了避免与存储引擎的不兼容性，我们做出了将属性绑定到顶点和边类型下的设计选择。同时，GRIN提供了一个API来获取具有(相同)给定属性名的所有属性处理器。
/* grin/property/type.h */ GRIN_VERTEX_TYPE grin_get_vertex_type_by_name(GRIN_GRAPH g, const char* name); /* grin/property/property.h */ GRIN_VERTEX_PROPERTY grin_get_vertex_property_by_name(GRIN_GRAPH g, GRIN_VERTEX_TYPE vtype, const char* name); GRIN_VERTEX_PROPERTY_LIST grin_get_vertex_properties_by_name(GRIN_GRAPH g, const char* name); /* run.cc */ { auto vtype = grin_get_vertex_type_by_name(g, "Person"); // 获取Person的顶点类型 auto vprop = grin_get_vertex_property_by_name(g, vtype, "Name"); // 获取绑定到Person的Name属性 auto vpl = grin_get_vertex_properties_by_name(g, "Name"); // 获取图中所有顶点类型(如Person、Company)下名为Name的所有属性 }
标签¶
GRIN 不会区分顶点和边上的标签，这意味着一个顶点和一条边可能拥有相同的标签。
然而存储可以通过宏
WITH_VERTEX_LABEL和WITH_EDGE_LABEL分别告知GRIN顶点或边是否启用了标签。
排序¶
GRIN 提供了排序顶点列表的假设。
GRIN还假设如果一个顶点列表已排序，那么该列表中的顶点具有完全的顺序关系。
排序后的顶点列表有助于实现顶点列表连接等计算，以及使用顶点作为数组索引的数据结构（如顶点数组）。
参考¶
GRIN在分区图中引入了引用概念。它代表一个实例的引用，该引用可以在访问该实例的当前分区之外的其他分区中被识别。
例如，
GRIN_VERTEX_REF是一个GRIN_VERTEX的引用，可以在其他分区中被识别。/* grin/partition/partition.h */ GRIN_VERTEX_REF grin_get_vertex_ref_for_vertex(GRIN_GRAPH, GRIN_VERTEX); const char* grin_serialize_vertex_ref(GRIN_GRAPH, GRIN_VERTEX_REF); GRIN_VERTEX_REF grin_deserialize_to_vertex_ref(GRIN_GRAPH, const char*); GRIN_VERTEX grin_get_vertex_from_vertex_ref(GRIN_GRAPH, GRIN_VERTEX_REF); /* run.cc in machine 1 */ { auto vref = grin_get_vertex_ref_for_vertex(g, v); // 获取v的顶点引用，该引用可以在机器2中被识别 const char* msg = grin_serialize_vertex_ref(g, vref); // 序列化为消息 // 将消息发送到机器2... } /* run.cc in machine 2 */ { // 从机器1接收消息... auto vref = grin_deserialize_to_vertex_ref(g, msg); // 反序列化回顶点引用 auto v = grin_get_vertex_from_vertex_ref(g, vref); // 如果g能识别该顶点引用，则转换为顶点 }
主节点与镜像节点¶
主顶点和镜像顶点的概念源自顶点切割分区策略。当一个顶点在多个分区中被识别时，graphscope将其中一个指定为主顶点，其余作为镜像顶点。这主要是为了实现数据聚合目的，为每个顶点提供一个共享的中央节点。
在边切割分区中，概念演变为内部顶点与外部顶点。GRIN采用主顶点与镜像顶点来分别表示内部顶点和外部顶点，以此统一这些概念。
本地完整¶
局部完整性的概念是指图组件在分区内是否围绕顶点或边保持局部完整。
以顶点和属性为例。GRIN认为顶点是"属性局部完整"的，如果它能在分区内本地获取该顶点的所有属性。
存在诸如"边属性局部完整"、"顶点邻居局部完整"等概念。
GRIN 不假设主节点上存在任何本地完整性。因为在某些极端情况下，主节点可能不会在本地包含所有数据或属性。
GRIN 目前提供顶点级别/边级别的局部完整判定API，而类型级别判定API的引入有待讨论。
自然ID特性¶
概念表示图的模式，例如顶点类型和绑定到特定边类型的属性，在许多存储引擎中通常从
0开始自然编号到num - 1。为了便于上层计算引擎进行进一步优化，GRIN提供了自然编号ID特性。如果存储系统也对图模式概念使用自然编号，则可以提供此特性。