重磅发布！！！蚂蚁图团队开源高性能原生图存储系统 CStore
作者：唐浩栋
CStore 是一款专门为图分析场景而设计的原生图存储引擎，它采用了 Rust 语言编写，使用基于图的存储结构，针对图分析场景进行特定优化。CStore 可以存储包含千亿级点和万亿级边的图数据，在蚂蚁集团内部的多场景使用中，已经积累了多年的经验，存储容量达到了 PB 级别。
图存储系统
百艺通，不如一艺精
在设计数据存储引擎时，需要考虑众多因素。例如，所应用的具体场景，是联机分析处理(OLAP)还是联机事务处理(OLTP)；再如，数据存储方式的选择，内存、本地硬盘或分布式存储；还有就是存储数据的格式，像是文档、JSON，宽表，对象，键值对等。图存储引擎是诸多数据存储引擎中的一种，它专门用于图数据的存储。从 DB-Engines 网站的统计来看，Graph DBMS 的热度从 2014 后一直领先其他类型数据库。
根据图数据存储方式的不同，现有的图存储引擎主要分为下面几大类：
基于链表，例如 Neo4j。
基于 Hash+链表，例如 ArangoDB。
基于 Key-Value 键值，例如 Titan/JanusGraph/HugeGraph。
基于传统关系型数据库，例如 AgensGraph。
CStore 基于 Array+链表的方式存储数据，支持实时读写能力。为了提供更好的图分析能力，CStore 把图元数据和属性分离存储，单独对元数据构建多级索引。CStore 在存储方式和索引设计上都充分考虑到图语义，有效地结合图数据访问的特点，充分利用计算机硬件的优势，在蚂蚁内部多个场景中得到验证，取得很好的业务效果。接下来从建模、存储、索引三个方面来介绍 CStore 作为原生图存储引擎的特点。
原生图建模
图形数据非常适用于描述复杂的网络关系。与其他存储格式相比较，图形数据具有自身的独特之处。举例来说，在 NoSQL 数据库中，Key-Value 数据库只包含 Key 和 Value 这两种元素，用户更容易理解和操作，并且存储引擎的设计也可以遵循一定的规则。另外，对于 DBMS（数据库管理系统）来说，实体关系模型必须按照一定的规范来进行设计，通常情况下，要求业务表的设计至少要符合第三范式，以此来消除数据冗余现象。CStore 基于属性图来建模，属性图是由点，边，以及点和边上的属性组成的图，点数据中记录了起始点 ID 和图元数据（标签，时间戳），边数据记录了起始点 ID 和图元数据（终点 ID，方向，标签，时间戳），每个起始点 ID 唯一确定一组点边数据。
点边数据进入到 CStore 之后，把点边起始点 ID 转化为从 0 开始的 ID，这个过程称之为 ID 化。由于用户定义的起始点 ID 格式不固定，蚂蚁内部使用的起始点通常大于 20bytes，转化为 4 个 bytes ID 后，可以极大减少索引内存消耗；另外规范化 ID 之后，CStore 使用 array 来做主键索引，array 的 index 为 ID，查询效率为 O(1)。
ID 化之后，点边数据被序列化为 PrimaryKey 和 GraphData，GraphData 由 SecondKey 和 Property 组成。PrimaryKey 记录点边 ID，SecondKey 记录图元数据，Property 记录点边属性数据。
SecondKey 编码格式如下，target id 大小不固定，其他部分消耗 20 bytes。write ts 字段记录数据写入时间，被用于数据淘汰，sequence id 记录了数据写入顺序，transaction 和 compaction 都会用到。graph info 记录是否是点，是否是入边，是否包含属性，标签，其他 meta, 点边时间属性等信息。
这样编码有两点好处：
点边数据变成 CStore 内部具有固定格式的二进制数据，有效减少内存消耗，方便后续数据写入磁盘；
图元数据被压缩到 8 字节，这样可以把更多的图信息放到索引侧，能够提前在索引侧过滤掉用户不需要的数据。
许多图形数据库会选择将点边数据编码为键值对的形式存储。相比之下，CStore 是一款针对图分析场景而设计的存储引擎，目的是提供更快的分析能力。为了实现这一点，CStore 会对经过编码后的图形信息建立多级索引。在下面的内容里，我们将讨论如何存储数据以及构建多级索引。
友好图存储
蚂蚁内部图数据的访问有以下几个特点。
通常相同起始点 ID 的点边数据大概率一起被访问；
相同类型, 时间的数据通常被一起访问；
用户点边数据的属性非常大，而点边元数据信息为固定结构且数据量不大；
点数据查询频率大于边数据。
CStore 在设计存储结构的时候，结合上述特点，对特定场景进行优化。针对第一个特点，CStore 尽可能的把具有相同的起始点 ID 的点边数据存储到物理上连续的存储空间。点边数据被序列化之后，数据首先被写入 GraphData Segment，它为内存数据结构，使用跳表来组成数据，维护了起始点 ID 到 GraphData List 的结构。GraphData Segment 主要有两个功能：
数据聚合。把相同的 src_id 的点边数据聚合到一起存储。
排序。按照用户指定顺序把相同 src_id 的点边数据排序，用于构建二级索引。
GraphData Segment 到达阈值之后被刷入到磁盘，数据被刷入到磁盘之前，把具有相同类型，写入时间（通常以天为单位）的数据作为一个分区写入到连续的物理存储空间，每个分区之间数据互相独立。
再者根据点边数据属性大而元数据固定的特点，CStore 采用了属性分离的架构，把图属性和图元数据分离存储到不同的物理存储空间。一方面对于图元数据单独加索引能够加速图查询性能，另外一方面属性分离也能够减少数据 compaction 的读写放大开销。
另外 CStore 还支持用户配置点边数据存储到不同的存储介质，点边数据在物理上隔离。点边数据的访问频率在不同的场景有所不同，分离存储能够进一步优化数据访问性能，提前过滤掉不需要的数据，减少数据读放大。
高效图索引
CStore 具有高效的图数据检索能力，支持多维度索引，不仅提供针对图元数据的分区索引，主键索引和二级索引，还支持针对点边属性的全文索引，可以根据指定的条件快速定位和返回数据。
GraphData Segment 写入到磁盘之前，把相同起始点 ID 的 GraphData 根据用户指定的顺序排序，然后把排序好的 SecondKey 构建索引，把排序好的 Property 直接写入到属性文件（记为 vs 文件）。
CStore 的分区索引对应到磁盘中某个目录，不同的分区数据落在不同的目录。主键索引是稀疏索引，默认索引间隔为 2048，目前仅支持以起始点 ID 构建主键，主键索引常驻内存。通过主键索引，可以快速定位到属性存储的文件 id 和 offset。
二级索引包括 min max 索引，bloom filter 索引等，用于快速判断某个稀疏索引块是否包含某个主键。min max 索引记录某个索引块的上界和下界，bloom filter 记录索引块的主键。
对于热点数据，二级索引做了特殊支持，比如一个起始点 ID 对应了 10 亿条边，如果没有索引，需要把满足 min max 和 bloom filter 索引的所有边读到内存过滤一次，返回用户指定的数据。为了加速这种场景，CStore 对点边类型，指向，写入时间加了二级索引。比如用户只想要读取 label 为 student，dt 为 2023-10-1 数据，通过二级索引，首先过滤掉所有 label 非 student 的数据，然后过滤掉 dt 非 2023-10-1 的数据，可以极大减少数据读开销，提升用户查询性能。
构建完索引，数据写入到索引文件（记为 is 文件），is 文件按照 LSM-Tree 结构组织，key 为主键索引中的 index，value 为索引 block 压缩后的数据。is 文件内部对于 key 有序，第 0 层单个文件内部对于 key 有序，其他层文件间对于 key 有序。
为了加快 LSM-Tree compact 的性能，CStore 支持单层的多线程 compact。在示意图中，每一个单独的 compactor 都代表一个 compact 工作线程。不同的 compactor 线程和 compact 清理线程（负责清理被 compact 的文件)将会并行执行。
以下是单个 compactor 内部运作过程的示意图，其中包括四个关键步骤：
计算各层次得分并选择其中最高的；
收集需要 compact 的文件；
将上述收集到的文件进行 compact 并生成新的文件；
最后一步是将新的文件更新至 LSM-Tree 及内存索引中。
编译构建
单独编译 CStore 代码需要提前准备 Rust 和 C++工具链。
下载 TuGraph Analytics 代码后，执行以下命令编译 CStore 源代码：
执行 make help 可以查看 makefile 提供的功能，当前版本的功能和对应描述如下：
未来规划
CStore 已在蚂蚁集团内部具备多年大规模生产化经验，未来我们将不断迭代升级，提升系统性能。然而，在一些特定的情况下，我们认识到 CStore 还有进步的空间。在未来一至两年内，我们计划更加深入地探索优化图分析场景，支持图数据列式存储，图融合以及物化视图能力。同时，为了提高用户的体验度，我们也将引入 remote compactor 功能，以解决因 compact 而导致的资源竞争问题。
目前，CStore 系统已全部开源到 TuGraph Analytics 仓库（geaflow-cstore 模块），当前推送的代码涵盖了 CStore 的核心功能特性，仍有大量的增强功能还在整合中。TuGraph 团队将持续投入图存储系统 CStore 的建设工作，也非常欢迎图计算和图存储的开发者一起参与进来，共同推进 CStore 的开源和演进。
总结
当下 TuGraph Analytics 项目已经内置了 CStore JNI 的依赖，你可以在高阶 API 任务中使用并体验 CStore 静态图存储系统，CStore 动态图能力正在建设中，敬请期待。同时我们也非常欢迎图存储系统/Rust 爱好者加入到 CStore 开源项目的建设中来。
相关资料：
欢迎访问：geaflow.github.io 2023-07-05 加入
TuGraphAnalytics是世界最快的OLAP图数据库。 github.com/TuGraph-family/tugraph-analytics
评论