Marius Eriksen：用 Reflow 进行云端增量数据处理

在 GRAIL，我们正在开发一项用于早期检测癌症的检测方法，这个问题所需的计算量大得惊人。因此我们需要投入数据基础设施，包括将生物信息学及其他数据处理领域使用的工具组合起来的工作流系统。

这些工作流与软件构建类似，但约束不同。任务可能运行数小时或数天，输入数据可能达到 TB 或 PB 级别，而且决策可能取决于实际数据或中间结果。我所说的工作流将外部工具连接成依赖图，许多 ETL 和生物信息学流水线都是如此。

许多现有系统提供嵌入式 DSL 或声明式格式，并以 Kubernetes 或 AWS Batch 等系统作为后端。根据我们的经验，它们通常要求用户手动组装依赖图，系统只能看到执行依赖，却没有任务之间流动数据的强模型。

我们的观察是，工作流就是程序。依赖图只是实现细节，类似普通程序底层的机制。我们希望直接表达所需的数据处理任务，让系统推导出依赖图。

Reflow 是一种函数式语言，具有大多可推断的静态类型和模块。它组合外部工具，施加数据模型，进行增量求值，并并行运行独立工作。运行时还会动态配置集群资源，目标是让用户编写和运行程序时无须手动管理基础设施。

序列比对的例子看起来像一个普通程序：包含绑定、函数和文件引用。特殊的 exec 表达式调用外部二进制程序，同时自然地引用其词法环境中的值。这就是语言与现有工具之间的连接。

我们的动机包括常见编程抽象、强数据模型、简单操作，以及我所说的“数据 API”。我们希望通过有类型、可组合的表达式描述并产生结果，而不是手动追踪每个中间文件的位置。

我们的目标包括可测试、可复用的模块，无缝的集群执行，静态类型安全和增量计算。如果一个任务原本可能运行五个小时，那么在执行前发现类型错误尤其重要。较少的依赖也有助于在不同云服务商之间迁移。

我们构建新系统，是因为数据模型和运行时假设是根本性的内容，很难事后添加到现有系统中。共同设计语言、运行时和集群管理器，让我们能够降低整个系统的复杂度。

在一个故意设计得很奢侈的 hello-world 演示中，exec 在 Ubuntu Docker 镜像中运行 echo，使用一个 CPU 和 1 GB 内存。先前的执行结果已被缓存；修改程序后，Reflow 请求 EC2 竞价实例，启动它并运行命令。从用户角度看，运行脚本并提供凭据就足以启动整个过程。

语言希望提供熟悉的函数式编程特性：函数、模块和局部推断的静态类型。它有意限制自身，而不是追求不受限制的计算能力。简单性对用户和实现都很重要，这个项目最初只有我一个人。

核心语法包括绑定、记录、元组、列表、映射、文件引用和函数。代码块包含局部绑定并求值得到一个表达式；条件语句也是包含两个分支的表达式。这些特性与其他现代语言类似。

exec 表达式调用外部工具。它可以插入周围作用域中的值，返回文件或目录，也可以有多个输出。运行时这些引用会具体化为路径，但程序不应该依赖特定路径名。

推导式将操作映射到集合上，还可以组合迭代、解构和过滤。例如，我们可以为每个样本比对文件，遍历嵌套集合并排除不良样本。这种语法直接表达任务，无须手动构造依赖图。

每个 Reflow 文件都是一个模块。模块可以声明参数，并在适当时提供默认值，也可以实例化其他模块。导出的名称以大写字母开头；Main 表达式可以从命令行运行，模块参数通过命令行标志提供。

相邻注释构成文档，文档工具会显示导出的名称、参数和推断类型。一个模块可以提供样本的比对数据和索引，另一个模块则确定它的输入。生成的接口为数据使用者提供类型、文档和可组合性。

三项求值特性共同发挥作用：求值是惰性的，遵循数据依赖，并利用引用透明性记忆化归约结果。表达式只在需要时求值；独立表达式可以并发运行；先前计算的结果可以复用。

例如，一个元组可能包含一个计算成本低的字符串和一个生成文件、成本高昂的 exec。如果调用者只取出字符串，就完全不需要运行 exec。惰性求值让模块可以提供昂贵的值，而不强迫所有使用者计算它们。

推导式可以并行比对彼此独立的样本，无须特殊的并行循环结构。推导式之外也是如此：只要表达式之间没有依赖，求值器就可以并发运行它们。

引用透明性和记忆化使重复表达式的结果可以复用。一个工作流中计算出的索引可以供另一个工作流引用，无须单独管理中间文件。Reflow 会追踪其依赖，因此输入改变时索引必须重新计算。

考虑提取特征、训练模型并在独立测试集上评估。增加一个训练样本需要为该样本提取特征并重新训练；修改训练代码时可以复用已有特征，但必须重新训练和评估。删除一个测试样本会改变评估，而不是特征提取和训练阶段。

下一个演示制作一张狗狗拼图。一个模块使用 ImageMagick 将原始 JPEG 图片缩放成 50 × 50 的缩略图，另一个计算将它们组合起来。数百张图片提供了并行工作，因此 Reflow 配置多个云实例并并发执行缩放。

当我修改拼图并再次运行时，缩略图已经计算完成。Reflow 复用这些结果并执行发生变化的下游工作；现有集群也减少了启动延迟。因此第二次运行快得多。

实现依赖很小的外部 API 面和少量灵活抽象。求值器运行在 Reflow 二进制程序所在的位置，例如笔记本电脑。只有需要执行外部二进制程序时，它才会请求云资源。

alloc 是一种资源分配，包含容器执行能力和文件仓库。容器和仓库随该资源分配一起创建和销毁。Reflow 向集群管理器请求 alloc；当下游工作需要来自多处的结果时，它可以在这些仓库之间传输内容。

仓库按内容哈希命名文件。持久仓库，例如 AWS 实现中由 S3 支撑的缓存，与临时 alloc 仓库共享同一接口。关联表将计算键与结果键连接起来，以便找到缓存的执行结果。

Reflow 将求值分为两个求值器。一个遍历语言的抽象语法树并生成数据流图；另一个对该图求值。exec 节点表示导入数据、运行容器或导出数据等操作。延续节点根据需要回调语法树求值器，创建更多子图。

增量求值从上到下搜索数据流图中的缓存结果，再从下到上计算缺失的工作。在狗狗图片例子中，系统先导入图片列表，然后通过延续节点生成缩放子图。已有缩略图从缓存复用，缺失的缩略图并行计算，之后再生成拼图。

引用透明性还使表达式在这一模型下成为其值的稳定名称。模块既可以保存计算的描述，也可以保存结果的键。这启发我们将模块视为数据 API，并在 dataspace 中组织其名称。

普通脚本可能依赖一个随时间变化的镜像名称。bundle 将模块依赖图和容器镜像等外部依赖解析并冻结为二进制产物。打包后的模块仍可作为一等模块使用，同时为计算提供稳定的锚点。

dataspace 将符号名称映射到模块。使用者可以检查、查看文档并求值这些名称，从而获得有类型、模块化且稳定的数据接口。一项策略可以要求替换模块是旧模块的子类型，有助于避免不兼容的更新，同时保留增量求值。

演讲时 Reflow 是开源项目，在 GRAIL 得到广泛使用，也有其他几家机构在使用。其目标是提供集成的数据处理环境：用户提供凭据，系统处理执行和基础设施。

有人问“最少的工作量”是什么意思，我澄清说，这是指在已有缓存结果的情况下，计算所需结果必须完成的总工作量。可用资源可能限制并行度，因此任务会排队。系统目前还不会根据哪个任务能解锁最多下游工作来确定优先级。

Reflow 支持 if 表达式等分支。一位听众问，如果源代码不变但底层镜像改变会怎样：Reflow 将镜像名称解析为内容摘要并放入缓存键，因此镜像变化会触发重新计算。bundle 可以为生产环境冻结这些依赖。

如果低估资源需求，Reflow 可以对某些资源超额分配。内存更难处理，因为进程可能耗尽内存；运行时会尝试识别内存不足错误，并增加内存后重试。未来可以改进动态性能分析，并将资源请求视为提示。

关于大型增量图的问题引出了求值器效率的讨论。最初的实现每次发生变化都会重新遍历图；后来的工作以增量方式追踪脏节点和引用计数。Reflow 图通常比其他一些增量系统的图小，但用户仍然可能生成非常大的图。

时间或随机性怎么办？Reflow 语言不会将这些动态效应作为普通表达式暴露。更一般地说，数据模型假设外部计算在输入相同、环境固定时会产生语义等价的输出。Reflow 无法对任意外部工具强制保证这一假设。

有人问到更丰富的类型，我回答说团队计划支持更强的声明，例如描述 CSV 的列或 BAM 文件的限制。这样的类型可以让系统检查数据接口的更多属性。

目前语言层面的失败会向上传播并使任务失败；语言没有通用的失败处理机制。不过，运行时可以识别某些基础设施失败，例如内存不足或磁盘耗尽，并在不同条件下重试。应用程序失败则仍然是失败。

Reflow 的核心数据模型围绕文件、目录和批量数据。其实现使用 DynamoDB 保存关联；通过执行操作可以将结果加载到外部数据库，演讲中提到了实验性支持，但数据库并不被视为特殊的核心数据类型。