本文分享自华为云社区《CSR格式如何更新？ GES图计算引擎HyG揭秘之数据更新》，作者： π 。

HyG 图计算引擎采用 CSR 格式来存储图的拓扑信息，CSR 格式可以将稀疏矩阵的存储空间压缩，进而大大降低图的存储开销，同时具备访问效率高、格式易转化等优点。利用 CSR + 列存（parquet 格式）的组合，HyG 获得了很高的图访问性能。但是，对于数据需要增量更新的场景，CSR 的更新非常困难，可能会导致大量的数据复制和移动，进而影响系统性能。HyG 对传统 CSR 更新进行了一系列优化，实现了高效的数据更新。

什么是 CSR 格式？

CSR 格式是一种常用的稀疏矩阵存储格式，它将稀疏矩阵以三个数组的形式存储。具体来说，CSR 格式使用 values、column indices 和 row offsets 三个数组来表示稀疏矩阵。

定义 NNZ（Num-non-zero）为矩阵 M 中非 0 元素的个数。

第一个数组为 values 数组。其中，values 数组的长度为 NNZ，分别从左到右从上到下的非零元素的值。

第二个数组为 column 数组。其中，column 数组的长度为 NNZ，其对应于 values 数组中的元素的 column_index（例如元素 8 排列在所在行的第 3 个位置,因此其 column index 为 2）。第三个数组为 row offsets，其中 row offsets 的数组大小为 m+1，其前 m 个元素分别代表这每一行中第一个非零元素在 Values 数组的下标。（例如元素 2 是第二行的第二个元素，其在 values 数组中的下标为 2.）

CSC 和 CSR 类似，只不过和 CSR 行列互换。values 数组里是按列存的数值，row offsets 变成了 col offsets，column 数组变成了 row 数组。

CSR 格式由于其紧凑的存储方式和高效的计算方式，已经成为了处理稀疏矩阵的标准格式之一。具体来说，CSR 格式可以利用连续的内存块来存储非零元素，这使得计算机在处理稀疏矩阵时可以跳过大量的零元素，从而提高了计算效率。此外，CSR 格式所需要的存储空间相对于其他格式，如 COO 格式（Coordinate）等，也更为紧凑，这在处理大型稀疏矩阵时非常有利。

如何更新 CSR 格式数据？

传统方案：

更新图数据需要对三个数组进行操作：values、columns 和 row offset。

更新

要更新矩阵中某个位置（i，j）的值，需要找到该位置在 CSR 格式中对应的行（第 i 行）在 values 和 columns 数组中的起始和结束索引。具体而言，该行的非零元素在 values 数组中的起始位置是 row offset [i]，结束位置是 row offset [i+1]-1。然后，在 columns 数组中找到对应的列（第 j 列）的索引位置。

接下来，可以直接更新 values 数组中对应位置的值，即 values[row offset[i]+k]，其中 k 是 columns 数组中第 j 列的索引位置。

插入

如果要插入一个新的非零元素，可以按照以下步骤进行：

1、找到要插入的元素在 CSR 格式中对应的行（第 i 行）在 values 和 columns 数组中的起始和结束索引，方法同上。

2、在 columns 数组中找到新元素应该插入的位置，即找到插入元素后 columns 数组中第 j 列的索引位置。

3、将新元素的值插入到 values 数组中正确的位置，并将 columns 数组中对应位置以及后面的元素向后移动一个位置。

4、更新 row offset 数组中第 i 行及其后面所有行的元素起始位置，因为在第 i 行插入了一个新的非零元素。

删除

如果要删除一个非零元素，可以按照以下步骤进行：

1、找到要删除的元素在 CSR 格式中对应的行（第 i 行）在 values 和 columns 数组中的起始和结束索引，方法同上。

2、在 columns 数组中找到要删除的元素的位置。

3、从 values 和 columns 数组中删除该元素，并将后面的元素向前移动一个位置。

4、更新 row offset 数组中第 i 行及其后面所有行的元素起始位置，因为在第 i 行删除了一个非零元素。

需要注意的是，更新 CSR 格式中的元素可能会导致数组长度的变化，因此需要动态分配和释放内存空间。此外，在进行插入和删除操作时，可能需要对 row offset 数组中的元素进行更新，这可能会影响 CSR 格式的性能。

总之，CSR 格式的更新操作相对复杂，需要对三个数组进行操作，并需要考虑内存分配和数组长度的变化等问题，这十分不利于实时分批式的增量更新。

HyG 数据更新策略

• 每次更新都会生成一个子图（delta_graph），这个子图是 CSR 格式，描述了增量信息。

• 引入 deleted_biset 数组，记录被删除的点、边信息。

• 按顺序加载 MergedPG = pg + [delta_graph]

• 对各点、边按照所属的 pg/ delta_graph 进行本地访问和增、删。

因为 HyG 考虑了分布式切分图的场景，我们将场景简化，接下来描述一下数据更新的流程。图原始数据如下图所示，图中包含 4 个点，4 条边，4 条边上的值分别为 1、7、2、8。

图对应的 CSR 格式如下图所示，这个是原始的拓扑数据。

我们对数据进行更新，基于原始图新增了边 0(src)->3(dst)，边的值为 3。删除了边 1(src)->2(dst)，边的值为 8。

新增了 1 条边，边的 src 是 0，dst 是 3，因此 CSR 的 row offset 为[1 1 1 1]，column 为[3]，value 为[3]。进而得到了右侧的 delta graph。

删除了 1 条边，这条边是属于 pg（原始图），所以，我们会对 pg 的 deleted_bitset 置位，因为删除是 column 数组的最后一个，因此，我们会将最后一个 bit 置为 1，表示这个边已被删除。

到此，我们就完成了一次增、删操作，生成了一个新的 delta graph，这个 delta graph 跟历史数据没有任何关系，它只表示了本次增量的数据，因此，对于超大规模的图，更新数据不再需要大量的数据拷贝和移动，只需要生成一个很小的 delta graph 就可以了。

图访问

经过增量更新，全量图的信息就会被分解为一个原始图和一个增量图。HyG 设计了一种同时读取到两个图信息的访问迭代器（以下简称“二级迭代器”），这种迭代器会将这多个子图视为一个全量图访问，可以在不同的子图间游走。

HyG 增量图迭代性能优化

HyG 增量图会产生多个快照，每个快照是一个子图，对应着一次 commit。算法读取增量图需要依赖 HyG 的二级迭代器，迭代器会在不同的快照间游走，校验点、边是否已被删除，最终返回给算法结果。因此，迭代器需要维护很多信息，远远大于 pg（原始图）的轻量级迭代器，进而使增量图迭代的性能很低，快照数量越多性能下降越剧烈。

优化方案

HyG 引入基于页的快照索引技术来缓解由于存在大量快照导致的性能下降问题。

为每个快照划分虚拟页，比如页的大小是 4K，那么一个页对应着 4K 个点以及这 4k 点对应的边。索引表记录了每个页最近被更新的快照，因此，如果这个页没有被更新，那么利用索引表可以直接跳过对应的快照。

索引表采用 copy on write 的方式更新，每生成一个新快照，会把上一个快照的全部索引信息 copy 一份，然后把修改信息更新到对应的索引上，得到最新快照的索引表。

同时，对于二级迭代器的构造，我们也进行了优化，尽量减少数据成员的数量，当迭代器在不同快照间切换时，去更新该快照的上下文信息，而不会维护所有快照的信息。

利用快照索引技术，我们可以快速的定位到点、边对应的最新修改的快照，进而可以跳过很多无效的访问。但是，随着快照数量的增多，图遍历的性能还是会不断下降，被删除的点、边不但浪费了大量的存储空间，还会增加无效的访问延时，因此，设计一套有效的自动化合并方案，当快照数量过多或者删除点、边过多时，触发合并，提升系统性能。如果大家感兴趣，我们后面会接着介绍 HyG 是如何实现快照合并的。

点击关注，第一时间了解华为云新鲜技术~