CSR格式如何更新？ GES图计算引擎HyG揭秘之数据更新

本文分享自华为云社区《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是如何实现快照合并的。

关注#华为云开发者联盟# 点击下方，第一时间了解华为云新鲜技术~

华为云博客_大数据博客_AI博客_云计算博客_开发者中心-华为云

十年磨一剑的华为云GES，高明在哪

本文分享自华为云社区《华为云GES：十年磨一剑，打造业界一流的云原生分布式图数据库-云社区-华为云》，作者：GES图引擎服务小图 。

1、浅谈云原生图数据库

图数据库（graph database）是一个使用图结构进行语义查询的数据库，它使用节点、边和属性来表示和存储数据。该系统的关键概念是图，它直接将存储中的数据项，与数据节点和节点间表示关系的边的集合相关联。这些关系允许直接将存储区中的数据连接在一起，并且在许多情况下，可以通过一个操作进行检索。

图数据库强调数据之间的关系。查询图数据库中的关系很快，因为它们永久存储在数据库本身中。可以使用图数据库直观地显示关系，使其对于高度互联的数据非常有用。因此图数据库广泛应用在互联网、知识图谱、金融风控等需要挖掘深度关联关系的场景。

“到2023年，图技术将促进全球30%企业的快速决策场景化。需要图还是不需要？这已不再是个问题，一定是需要”，Gartner公司副总裁、杰出分析师Mark Beyer讲到。

云原生图数据库从名字看是从云原生和图数据库概念发展而来的。而云原生的概念通用意义上可以理解为应用以服务化或云化的方式提供给用户。此类云原生图数据库是在云基础架构之上进行构建的，图数据库组件在云基础设施之上构建、部署和分发。这种云原生属性是它相比于其他类型图数据库最大的特点。作为一种云平台，云原生图数据库以 SaaS（软件即服务，Software-as-a-Service）的形式进行分发。

2、云原生数据库与其他图数据库解决方案有什么不同？

从上图的图数据库VS图数据库on云服务器VS云原生图数据库的对比图我们可以看到：云原生图数据库因为具有即开即用、稳定可靠、管理便捷、弹性伸缩等优点，可以帮助用户减少图数据库总拥有成本（TCO）和运维工作量（O&M），用户可以将主要精力聚焦在核心业务上。

3、华为云GES：为什么受到客户的广泛认可？

华为云图引擎服务（GES）是一种基于华为云基础架构和平台的在线数据处理图数据库，提供即开即用、可扩展且完全托管的分析型图数据库服务。作为拥有自主知识产权的分布式原生图数据库和图引擎产品，提供一站式的图存储、图查询和图计算能力，支持业界标准图查询语言cypher和gremlin，同时支持30+高性能算法，覆盖多场景分析计算，具备10+图神经网络和图嵌入算法。广泛应用于互联网、政务、安平、税务、电力等行业，为客户的辅助决策、降本增效等提供专业、高效的服务。

从2013年预研到2015年GES内核Eywa研发内部立项再到现在，整十年的发展过程中，华为云GES始终保持高强度研发投入，已经硕果累累。GES同时提供与HCS8.X、HCSO配套的混合云版本。从2017年底华为云正式公测，到目前上线华为云国内站10+站点，海外新加坡、俄罗斯、阿联酋、爱尔兰、南非等站点，马电、法电等合营云站点，服务海内外几十家客户，目前呈现多点开花的局面，显示出GES强大的产品竞争力。

十年磨一剑，GES作为国内最早发布的云原生分布式图数据库，“云原生”优势主要体现在如下几个方面：

完全托管

GES是完全托管的在线图数据库服务，后台会为每个最终租户创建与之对应的资源租户，部署GES需要的计算、存储、网络等资源，均通过资源租户发放，用户只需通过GES提供的Portal界面或者API访问图数据库即可，无需关注图数据后台的底层资源。GES提供了7*24小时oncall，如果这些资源发生故障（比如所在的物理机故障），oncall会立即感知到并处理，整个过程用户无需操作，用户省心又安心。

针对部分用户希望感知到图数据库后台资源（比如CPU、内存、磁盘等）以及图数据库关键指标（响应时间、容量占用等）的诉求，GES针对每个图实例也对接了华为云的CES服务，用户可以在CES界面查看到GES的监控指标，并对关注的指标配置告警，一旦监控值超过阈值，可以及时通知到用户。

资源动态扩展

GES提供了在线对图实例进行扩容、扩副本的能力，实现资源动态扩展。

扩容操作一般发生在容量不足的场景，比如初始阶段申请了一亿规格的图实例，后期随着业务的增长需要扩容到十亿规格，可以简单通过界面点击完成，整个扩容过程业务不中断且支持从小规格一次性扩容到任意的大规格。

扩副本操作一般发生在并发性能有更高要求的场景，比如初始阶段申请了一亿规格的图实例，默认GES是提供一主一从两个副本部署方式，后期随着业务的增长对QPS有了更高的要求，可以扩容成一主多从多个副本。扩副本整个过程可以简单通过界面点击完成，整个扩副本过程中业务不中断，且支持一次性扩容多个副本。

版本在线升级

GES图实例的版本支持在线升级，用户只需要在界面点击即可升级到最新版本，新版本可能是新需求上线、漏洞修复（包括开源软件或者操作系统）、Bug修复等。升级过程由用户触发且不收取任何费用。

GES当前版本发布周期在1个月左右，也就是说用户的新需求最快可以1个月之内上线。GES新版本上线后，用户通过升级即可满足新需求。借助华为云内部强大的版本发布系统，针对严重阻塞用户的问题，GES能够做到24小时修复。比如2021年Log4J爆出的“核弹级”漏洞，GES在24小时之内完成了新版本上线，上线后用户快速升级即可完成漏洞修复。

容灾和数据高可靠

GES实例采用一主多从架构，主从切换业务不感知，使用多副本机制保障高可用。支持跨AZ容灾，单机房故障不丢数据、不中断业务，RTO秒级。

图实例支持手工备份和自动备份两种备份方式。手工备份用户可以在界面点击触发，一般用作重大变更（比如升级或者数据清空）前生成一个数据快照，如果变更问题可以及时将数据会退到该快照。自动备份是图数据库内部的行为，为数据可靠性服务。如果服务器发生宕机，GES后台会通过自动备份和写日志，快速进行数据恢复，确保数据不丢失。

GES实例支持跨AZ部署，用户只需要在发放图实例时勾选上启用跨AZ即可，无需额外费用。主从集群数据跨机房存放，实现单机房故障不丢数据。业务计算资源跨机房调度，单机房故障不中断业务。且在正常情况下，计算和数据在数据中心内部交互，减少机房间带宽消耗。

KMS数据加密

如上面所讲，GES是完全托管的服务，用户的备份数据是存储到资源租户的OBS桶上面，针对部分用户数据密级较高的场景，GES提供了基于KMS服务的数据加密方案。

GES加密存储的客户数据包括两种：

1、客户原始数据：支持创建的元数据文件存储到OBS上时加密。

2、导入到图系统里面的数据：

（1）String类型的属性会存储到云硬盘EVS，支持对EVS加密。

（2）增量备份、全量备份会备份到OBS/HDFS，支持对增量备份和全量备份的加密。

GES提供了基于KMS服务的数据加密方案，如下图所示：

站在管理面视角：

?租户管理员登录华为公有云后，在GES Console上申请创建加密实例；

? GES Service接收到创建加密实例请求后，向KMS Service申请主密钥和集群密钥，并生成数据库密钥下发给GES内核；

? GES业务实例在初始化时加载密钥，并加密保存。

站在数据面视角：

?客户导入点、边数据集、Schema文件，支持这些数据存储在OBS时使用KMS加密；

? 若用户创建图备份，则在内存数据加密后生成备份数据并存储到OBS；若用户从备份恢复图，则从OBS下载备份数据，然后解密后加载到内存。

安全性

GES提供多个特性来保障租户图实例的可靠性和安全性，例如VPC、安全组、权限设置、SSL连接、手动/自动备份等，如下图所示：

网络隔离：VPC 允许租户通过配置 VPC 入站 IP 范围来控制连接图实例的 IP 地址段。GES实例运行在租户独立的 VPC 内。租户可以创建一个跨可用区的子网组，之后可以根据业务需要，将部署 GES的实例选择此子网完成，GES 在创建完实例后会为租户分配此子网的 IP 地址，用于连接GES实例。GES 实例部署在租户 VPC 后，租户可通过 VPN 使其它 VPC 能够访问实例所在 VPC，也可以在 VPC 内部创建 ECS，通过私有 IP 连接GES实例。租户可以综合运用子网和安全组的配置，来完成GES实例的隔离，提升实例的安全性。认证鉴权：GES实例任何操作，都需要进行IAM认证鉴权。访问控制：租户可以为不同的用户组分配不同的GES权限，包括GES Administrator、GES Super User、GES Operator权限。GES Administrator拥有GES的最高权限，可以对GES资源进行任意操作；GES Super User拥有除创建和删除GES实例以外的所有操作权限，包括GES实例的启动/停止、导入/导出，GES实例的访问等操作；GES Operator拥有GES实例的访问操作，无法进行GES实例的资源类操作。存储加密：GES支持读取加密存储到OBS的数据，加密密钥由 KMS 管理。备份与恢复：GES 提供自动/手动两种备份方法，执行备份后会对整个GES实例进行全量备份，这些备份数据存储在华为 OBS 桶中，当用户删除实例时，会同步删除 OBS 桶中的备份。用户也可以从已有的备份恢复到实例。数据安全：用户删除 GES 实例时，存储在GES实例中的数据都会被删除，任何人都无法查看及恢复数据。主机安全：GES基于华为云内部欧拉操作系统，做了多种加固，定期更新操作系统最新补丁。采用图实例升级的方式，用户可以及时修复OS漏洞。细粒度权限控制：

在企业生产里面，权限控制尤为重要。例如，在公司里面，HR部门才能看到绩效、级别等信息；财务部门才肯看到账号、转账等信息；而其他信息公开，公司内所有员工都可以看到。

GES图实例提供了界面化的细粒度权限控制，可对特定Label的特定属性设置遍历（traverse）、读、写权限。适用于企业对不同部门的权限设置，并对用户组进行授权，权限模型如下图所示：

过载控制

过载，是服务或应用处理的请求超过了自身所能承载的能力，造成服务或应用自身处理请求时延变慢、错误率增加，或者请求失败，乃至服务中断。GES图实例内部集成了过载控制组件，提供了流控、降级、熔断等机制帮助业务实现过载保护。

GES按需地为每个图实例预置了系统CPU、系统内存、应用JVM内存、应用连接数、应用任务阻塞数等5种过载指标，确保整个系统不会被恶意或者无意的瞬时高并发容量冲垮。而且一旦发生过载，GES还可以根据用户诉求设置降级策略，确保这一异常情况下用户的核心业务核心API不受影响。

支持HCS、HCSO、华为云多种形态

针对不同客户对云形态的要求，GES提供 HCS、HCSO、华为云等多种云形态的版本，配套HCS8.X和HCSO 23.3.0、23.9.0等版本，方便用户选择不同场景下的云服务。

号外！

华为将于2023年9月20-22日，在上海世博展览馆和上海世博中心举办第八届华为全联接大会（HUAWEICONNECT 2023）。本次大会以“加速行业智能化”为主题，邀请思想领袖、商业精英、技术专家、合作伙伴、开发者等业界同仁，从商业、产业、生态等方面探讨如何加速行业智能化。

我们诚邀您莅临现场，分享智能化的机遇和挑战，共商智能化的关键举措，体验智能化技术的创新和应用。您可以：

在100+场主题演讲、峰会、论坛中，碰撞加速行业智能化的观点参观17000平米展区，近距离感受智能化技术在行业中的创新和应用与技术专家面对面交流，了解最新的解决方案、开发工具并动手实践与客户和伙伴共寻商机

感谢您一如既往的支持和信赖，我们热忱期待与您在上海见面。

大会官网：

欢迎关注“华为云开发者联盟”公众号，获取大会议程、精彩活动和前沿干货。

关注#华为云开发者联盟# 点击下方，第一时间了解华为云新鲜技术~

华为云博客_大数据博客_AI博客_云计算博客_开发者中心-华为云