性能调优

在大规模图数据上的内存占用和性能表现是图分析在现实场景中成功的关键。本节我们将深入探讨GraphScope中属性图数据结构的内部设计，分析影响内存占用和性能的因素，最后给出一些优化图分析性能和降低内存使用量的建议。

属性图的内存占用

我们首先深入了解属性图数据结构的详细设计，看看它是如何存储在内存中的，以及哪些因素会影响内存占用。

属性图数据结构

GraphScope 使用 ArrowFragment 数据结构 defined in Vineyard 来表示属性图。基本上，ArrowFragment 包含以下成员：

• 索引器：用户输入图中的顶点通常是自然整数或字符串。为了使图分析处理更高效，我们需要将用户输入中的原始ID映射到一个连续的整数范围内。这一过程需要一个称为VertexMap的数据结构，它本质上是一个哈希映射，将原始顶点ID映射到内部顶点ID，并包含一个数组用于记录每个分区中的原始顶点ID。

  • o2g__: 每个分区中每个标签的顶点都有这样一个哈希映射表。该哈希映射表可以是扁平哈希映射表或完美哈希映射表。

    哈希映射表的键类型与原始顶点ID相同（通常是int64_t或std::string_view），值类型则是内部顶点ID（通常是uint64_t）。

  • oid_arrays__: 每个分区中每个标签对应的原始顶点ID数组。

    该数组的类型与原始顶点ID相同（通常为int64_t或string）。

• 拓扑结构：属性图的第一个主要部分是拓扑结构：它本质上是一个CSR（压缩稀疏行格式）矩阵：

  • 入边：每个(src_type, edge_type) 对都有一个CSR矩阵来表示其入边。该CSR矩阵由一个indptr数组和一个indices数组组成：

    • ie_lists_--: indptr数组，其中每个元素是一个(neighbor_vertex_id, edge_table_index)对，第一个值是相邻顶点ID，第二个值是指向对应边表的索引。

      默认情况下，neighbor_vertex_id的类型是uint64_t或uint32_t，而edge_table_index的类型是size_t。

      indptr数组的大小为num_edges。

    • ie_offsets_lists_--: indices数组，该数组中的每个元素都是一个offset，切片ie_lists[ie_offsets[i]:ie_offsets[i+1]]表示顶点i的边。

      默认情况下，offset的类型为size_t。

      indices数组的大小为num_vertices + 1，这是一个基于0的偏移量数组。

  • 出边：一个CSR矩阵，与入边类似，但表示当前分区的出边。

    • oe_lists_--: indptr数组，数组中的每个元素都是一个(neighbor_vertex_id, edge_table_index)对，其中第一个是相邻顶点ID，第二个是指向对应边表的索引。

      默认情况下，neighbor_vertex_id的类型是uint64_t或uint32_t，而edge_table_index的类型是size_t。

      indptr数组的大小是num_edges。

    • oe_offsets_lists_--: indices数组，该数组中的每个元素都是一个offset，切片oe_lists[oe_offsets[i]:oe_offsets[i+1]]表示顶点i的边集合。

      默认情况下，offset的类型为size_t。

      indices数组的大小为num_vertices + 1，这是一个基于0的偏移量数组。

• 属性：属性图的第二部分是属性：每个顶点标签和每个边标签都有一个属性表：

  • edge_tables_-: 边属性表，每个边标签都有对应的表；

  • vertex_tables_-: 顶点属性表，每个顶点标签都有对应的表。

内存使用量估算

给定分片的内存使用量，其中顶点数为V，边数为E，原始ID类型为OID_T，内部ID类型为VID_T，可估算如下：

• 索引器：

  • 使用扁平哈希表时：(sizeof(OID_T) + sizeof(VID_T) + sizeof(uint8_t)) * V / load_factor；

    根据我们的实践观察，load_factory通常处于[0.4, 0.5]范围内。

  • 使用完美哈希映射：(sizeof(OID_T) * V) * (1 + overhead)。

    实际上，overhead通常处于[0.15, 0.2]范围内。

• 拓扑结构：

  • 入边: (sizeof(VID_T) + sizeof(size_t)) * E + sizeof(size_t) * (V+1);

  • 出边：与入边相同，(sizeof(VID_T) + sizeof(size_t)) * E + sizeof(size_t) * (V+1)。

• 属性：

  • 边属性：取决于您有多少个边属性。

    在GraphScope中，默认情况下会生成一个额外的列edge_id属性（类型为int64_t）并将其添加到边表中作为每条边的唯一标识符。

  • 顶点属性：取决于您拥有多少顶点属性。

    在GraphScope中，默认情况下原始顶点ID也会作为属性保留在顶点表中。

优化内存使用

基于上述分析，我们总结出以下减少内存碎片占用的优化技巧：

• 优化索引器：

  • 使用完美哈希映射。这不是默认选项，但可以通过在graphscope.g()和graphscope.load_from()中设置参数use_perfect_hash=True来启用。

    如上所述，完美哈希映射可以大幅减少顶点映射的内存占用。

  • 使用本地顶点映射。GraphScope内部实现了两种顶点映射，前者称为GlobalVertexMap，它在索引器中存储所有分片中的所有顶点；后者称为LocalVertexMap，它仅在索引器中存储相关顶点（与当前分片内部顶点之间存在边的顶点）。

    LocalVertexMap不是默认选项，但可以通过graphscope.load_from()中的参数vertex_map="local"启用。LocalVertexMap适用于需要扩展到多个节点（例如数十或数百个工作节点）的图，但它确实存在一些灵活性限制，只能在通过graphscope.load_from()加载图时使用，且不支持重复调用add_vertices/edges()。

• 优化拓扑结构：

  • GraphScope 使用 uint64_t 作为 VID_T（内部顶点ID）以支持大规模图数据。然而根据上述分析，VID_T的类型是影响拓扑结构部分内存占用的关键因素之一。

    如果您确定您的图规模较小（顶点数少于 10^8，具体阈值取决于标签数量和分区数量），可以通过在 graphscope.g() 和 graphscope.load_from() 中使用 vid_type="int32_t" 选项，将 VID_T 设为 int32_t 类型来优化内存使用。

  • GraphScope 支持在 graphscope.g() 和 graphscope.load_from() 中使用 compact_edges=True 选项， 通过 delta 和 varint 编码压缩 ie_lists 和 oe_lists 数组。这种压缩方式 可以将拓扑部分的内存占用减少一半，但在遍历图片段时会带来最高达 20% 的计算开销。

• 优化属性：

  • 通过在graphscope.g()和graphscope.load_from()中使用参数generated_eid=False，可以避免在边表中生成edge_id列。当您的边属性不多且只需运行高效分析任务时，这能显著节省内存空间（减少sizeof(size_t) * E）。

    请注意，如果您打算在图上运行交互式查询，则必须将参数generated_eid设为True。

  • 可以通过在graphscope.g()和graphscope.load_from()中使用参数retain_oid=False来避免保留顶点表中的vertex_id列。虽然帮助不大(节省sizeof(OID_T) * V)，但如果图的E/V比率较低(图有很多顶点但没有那么多边)，收益会更显著。

    请注意，如果您打算在图上运行交互式查询，参数retain_oid必须设为True。

优化图分析性能

GraphScope 支持在具有多个顶点标签、边标签和属性的 ArrowFragment 图上进行分析应用，也支持在仅包含一个顶点标签、一个边标签且每个顶点和边最多只有一个属性的 ArrowProjectedFragment 图上进行分析。

• 在ArrowFragment上的分析应用需要一个隐式的"扁平化"处理过程，使其成为ArrowFlattenFragment。

  ArrowFlattenFragment可以视为属性图ArrowFragment的一个"视图"。它主要是为了兼容性目的而存在，在遍历时会有性能损耗。在实际应用中，如果分析应用的性能至关重要，应该避免使用扁平化片段，而应该改用投影片段。

• 在ArrowProjectFragment上的分析应用需要一个隐式的"投影"过程来创建ArrowProjectedFragment。这个过程涉及遍历边并生成新的offsets数组。

  为了优化在相同图上使用相同投影设置运行多个不同算法时的运行时间，建议先显式地将片段投影到ArrowProjectFragment，以避免"投影"过程的开销。例如：

  不要这样做：

  g = ....   # 可以隐式投影的片段
  
  r1 = sssp(g, src=1)
  r2 = pagerank(g)
  r3 = wcc(g)
  ...
  

  应该先显式投影：

  g = ....   # 可以隐式投影的片段
  
  projected_g = g._project_to_simple()
  r1 = sssp(projected_g, src=1)
  r2 = pagerank(projected_g)
  r3 = wcc(projected_g)
  

在对ArrowFragment应用分析算法时，如果满足以下条件：(1) 仅包含一个顶点标签，(2) 仅包含一个边标签，且(3) 每个顶点和边最多只有一个属性，那么系统将生成ArrowProjectedFragment；否则将使用ArrowFlattenFragment。