Rayforce：列式分析与图遍历融合的零依赖嵌入式引擎

背景

在数据工程领域，传统的数据库系统往往将关系型查询（如 SQL 风格的列式分析）与图计算（Graph Traversal）分离处理。这种分离导致了数据在两种模型间转换的开销，以及维护两套执行引擎的复杂性。与此同时，随着嵌入式系统和边缘计算场景对高性能、低资源占用数据处理的需求增长，开发者急需一种既轻量又功能强大的底层引擎。

Rayforce 正是在这一背景下诞生的开源项目。它由 Lynx 联合开发并赞助，旨在提供一个纯 C17 编写、零依赖、可嵌入的数据处理引擎。其核心设计理念是打破列式分析与图遍历之间的壁垒，通过统一的执行管道实现高效的数据处理。该项目不仅提供了底层的 C API，还内置了名为 Rayfall 的 Lisp 风格查询语言，支持从构建、优化到执行的全流程自动化。

核心内容

Rayforce 的核心架构建立在一个统一的有向无环图（DAG）之上，将列式分析和图遍历操作融合在同一个管道中。以下是其技术实现的详细解读：

1. 统一执行管道与优化

Rayforce 的所有操作（扫描、过滤、连接、聚合、窗口函数、图遍历等）都被构建为一个惰性的 DAG。这意味着在调用 ray_execute 之前，没有任何实际计算发生。

在执行前，引擎会经过一个多阶段优化器，执行以下重写步骤：

• 类型推断
• 常量折叠
• 侧向信息传递（Sideways Information Passing, SIP）
• 因子分解
• 谓词下推
• 过滤器重排序
• 投影下推
• 分区剪枝
• 算子融合
• 死代码消除（DCE）

2. 执行引擎：融合的分块字节码

Rayforce 的执行机制基于“融合的分块驱动字节码”（Fused Morsel-driven Bytecode）。

• L1 缓存友好：执行单元将 1024 个元素作为一块（morsel）进行处理，确保数据常驻 L1 缓存，极大提升速度。
• 算子融合：逐元素操作被合并为单遍扫描的块，减少内存访问次数。
• 哈希连接优化：采用基数分区哈希连接（Radix-partitioned hash joins），并将分区大小调整至适配 L2 缓存。
• 并行调度：通过线程池并行分发分块任务。

3. 图引擎支持

除了传统的列式分析，Rayforce 还内置了强大的图计算能力：

• 存储结构：使用双索引 CSR（压缩稀疏行）存储，支持前向和后向遍历，并支持 mmap。
• 算法库：支持 BFS、DFS、Dijkstra、A*、PageRank、Louvain、Betweenness 等经典图算法。
• 高效执行：通过因子化执行避免笛卡尔积的材料化，并利用 SIP 将选择位图反向传播通过扩展链。

4. Rayfall 查询语言

Rayforce 附带了 Rayfall，一种类 Lisp 的查询语言，拥有丰富的一级内置函数。

• 语法示例：

  (set t (table [Symbol Side Qty]
    (list [AAPL GOOG MSFT AAPL GOOG]
          [Buy Sell Buy Sell Buy]
          [100 200 150 300 250])))
  (select {from:t by: Symbol Qty: (sum Qty)})
  

• 特性：支持算术、字符串、聚合、连接、高阶函数和 I/O。Lambda 表达式会惰性编译为字节码，并在基于计算跳转（computed-goto）的虚拟机中运行。
• 向量搜索集成：支持多指标 HNSW 索引（余弦、L2、内积），并提供 cos-dist、knn 等内置函数。支持过滤感知 ANN（Filter-aware ANN），通过 where 谓词将过滤逻辑推入 HNSW 的波束搜索循环中，避免无效候选项占用结果槽位。

5. 内存管理：无 malloc

Rayforce 是一个“无 malloc”引擎，所有内存分配均通过自定义分配器完成：

• 分配策略：采用伙伴分配器（Buddy allocator）结合 slab 缓存，约 90% 的分配操作时间复杂度为 O(1)。
• 线程安全：使用线程局部存储（Thread-local arenas），实现无锁分配和写时复制（COW）引用计数。
• API：所有内存操作通过 ray_alloc 和 ray_free 进行，不依赖系统标准库分配器。

6. 存储与 I/O

• 列式文件：支持 mmap 访问的列式文件、散列表（splayed tables）和按日期分区的表。
• CSV 处理：提供并行 mmap 解析的 CSV 读取器，具备类型推断和空值处理能力。

7. 项目结构与构建

• 构建命令：
  • make：构建调试版本（包含 ASan + UBSan）。
  • make release：构建优化版本。
  • make test：运行完整测试套件。
  • ./rayforce：启动 Rayfall REPL。
• 目录结构：包含 src/mem（内存）、src/ops（DAG/优化器/执行器）、src/lang（Rayfall 解析器/VM）等模块。
• 文档：完整文档托管于 rayforcedb.github.io/rayforce。

关键要点

• 单一管道融合：Rayforce 最大的创新在于将列式分析和图遍历融合在同一个操作 DAG 中，共享多阶段优化器和执行引擎，消除了异构引擎间的数据转换开销。
• 极致性能优化：
  • 执行单元基于 1024 元素的分块（morsel），确保数据常驻 L1 缓存。
  • 哈希连接分区大小经过优化以适配 L2 缓存。
  • 算子融合技术将多个逐元素操作合并为单次扫描。
• 零依赖与嵌入式友好：纯 C17 编写，无外部依赖，无系统 malloc 调用，专为嵌入式和高性能场景设计。
• 高级内存管理：使用伙伴分配器和 slab 缓存实现 O(1) 分配，结合线程局部存储和无锁机制，避免内存碎片和锁竞争。
• 丰富的图与向量搜索支持：不仅支持 BFS、DFS 等图算法，还集成了多指标 HNSW 向量索引，并支持过滤感知的近似最近邻搜索。
• Rayfall 查询语言：提供类 Lisp 语法的交互式查询界面，支持惰性编译和字节码执行，便于快速原型开发和复杂查询编写。
• 生产就绪：由 Lynx 赞助开发，经过生产环境验证，提供完整的 C API 和 Python 绑定（rayforce-py）。

意义与影响

Rayforce 的出现为数据基础设施领域提供了一种新的范式。传统上，处理混合负载（如同时需要复杂 SQL 分析和实时图推荐）的系统通常需要组合多个专用引擎（如 ClickHouse 用于分析，Neo4j 用于图），这带来了巨大的运维复杂性和数据同步成本。Rayforce 通过底层架构的统一，证明了在单一引擎中高效融合这两种计算模式是可行的。

对于嵌入式系统、边缘计算设备以及对延迟和内存极度敏感的应用场景，Rayforce 的“零依赖”和“无 malloc”特性使其成为极具吸引力的选择。它允许开发者在不引入庞大数据库依赖的情况下，获得企业级的数据分析和图计算能力。

此外，Rayforce 对向量搜索和图算法的内置支持，使其在 AI 应用后端、实时风控和金融分析等领域具有广泛的应用潜力。通过提供 Rayfall 语言和