Marius Eriksen: Reflow for Incremental Cloud Data Processing

At GRAIL we are developing an assay for early cancer detection, a surprisingly computationally intensive problem. That has required investment in data infrastructure, including workflow systems that compose the tools used in bioinformatics and other data-processing domains.

These workflows resemble software builds but have different constraints. Tasks may run for hours or days, inputs can reach terabytes or petabytes, and decisions may depend on the actual data or on intermediate results. The workflows I mean connect external tools into a dependency graph, as in many ETL and bioinformatics pipelines.

Many existing systems expose an embedded DSL or a declarative format and target a backend such as Kubernetes or AWS Batch. In our experience they often require users to assemble dependency graphs manually, and the system sees execution dependencies without a strong model of the data flowing between tasks.

Our observation is that workflows are programs. The graph is an implementation detail, rather like the low-level machinery beneath an ordinary program. We want to express the desired data-processing task directly and let the system derive the graph.

Reflow is a functional language with mostly inferred static types and modules. It composes external tools, imposes a data model, evaluates incrementally and runs independent work in parallel. Its runtime also provisions cluster resources dynamically, with the aim that a user can write and run a program without manually managing the infrastructure.

A sequence-alignment example looks like an ordinary program: bindings, a function and file references. The special exec expression invokes an external binary while referring naturally to values in its lexical environment. This is the connection between the language and existing tools.

The motivations are ordinary programming abstractions, a strong data model, simple operations and what I call an API for data. Instead of manually tracking where each intermediate file lives, we want typed, composable expressions that describe and produce those results.

Our goals include modules that can be tested and reused, seamless cluster execution, static type safety and incremental computation. A type error discovered before execution matters especially when a task might otherwise run for five hours. A small dependency footprint also helps portability between cloud providers.

We built a new system because the data model and runtime assumptions are fundamental, not features easily bolted on afterward. Co-designing the language, runtime and cluster manager let us reduce the total system complexity.

In a deliberately extravagant hello-world demo, an exec runs echo inside an Ubuntu Docker image with one CPU and one gigabyte of memory. A previous execution is cached; changing the program causes Reflow to request an EC2 spot instance, boot it and run the command. From the user’s perspective, running the script and supplying credentials is enough to initiate the process.

The language aims for familiar functional programming features: functions, modules and static types inferred locally. It is deliberately limited rather than seeking unrestricted computational power. Simplicity matters both to users and to the implementation, which began as a one-person project.

The core syntax includes bindings, records, tuples, lists, maps, file references and functions. Blocks have local bindings and evaluate to an expression; conditionals are expressions with both branches. These features resemble those of other modern languages.

Exec expressions invoke external tools. They can interpolate values from the surrounding scope and return files or directories, including multiple outputs. At runtime those references materialize as paths, but programs should not rely on the particular path names.

Comprehensions map operations over collections and can combine iteration, destructuring and filters. For example, we can align files for each sample, traverse nested collections and exclude a bad sample. The syntax expresses the task without manually constructing a dependency graph.

Every Reflow file is a module. Modules may declare parameters, with defaults where appropriate, and can instantiate other modules. Exported names begin with a capital letter, and a Main expression can be run from the command line with module parameters supplied as flags.

Adjacent comments provide documentation, and the documentation tool displays exported names, parameters and inferred types. A module can expose a sample’s aligned data and index while another module determines its inputs. The resulting interface gives data consumers types, documentation and compositionality.

Three evaluation properties work together: evaluation is lazy, follows data dependencies, and memoizes reductions using referential transparency. Expressions are evaluated only when needed; independent expressions can run concurrently; and previously computed results can be reused.

For example, a tuple may contain a cheap string and an expensive file-producing exec. If a caller extracts only the string, the exec never needs to run. Laziness allows modules to expose expensive values without forcing all consumers to compute them.

Comprehensions can align independent samples in parallel without a special parallel-loop construct. The same applies outside comprehensions: wherever expressions have no dependency on one another, the evaluator can run them concurrently.

Referential transparency and memoization make repeated expressions reusable. An index computed in one workflow can be referenced by another without separately managing the intermediate file. Reflow tracks its dependencies, so a changed input forces the index to be recomputed.

Consider extracting features, training a model and evaluating it on a separate test set. Adding a training example requires feature extraction for that example and retraining; changing training code can reuse existing features but must rerun training and evaluation. Removing a test example changes the evaluation rather than the feature extraction and training stages.

The next demo creates a dog montage. A module uses ImageMagick to resize source JPEGs to 50-by-50 thumbnails, and another computation combines them. Hundreds of images expose parallel work, so Reflow provisions multiple cloud instances and runs the resizes concurrently.

When I change the montage and run it again, the thumbnails have already been computed. Reflow reuses them and performs the changed downstream work; the existing cluster also reduces startup delay. The result is a much faster second run.

The implementation relies on a small external API surface and a few flexible abstractions. The evaluator runs wherever the Reflow binary runs, such as a laptop. It requests cloud resources only when external binaries need to execute.

An alloc is a resource allocation with container execution and a file repository. Its containers and repository live and die with the allocation. Reflow asks a cluster manager for allocs and can transfer content between their repositories when downstream work needs results from several places.

Repositories name files by content hash. Durable repositories, such as an S3-backed cache in the AWS implementation, share an interface with ephemeral alloc repositories. An association table links computation keys and result keys so cached executions can be found.

Reflow separates two evaluators. One walks the language’s abstract syntax tree and produces a flow graph; another evaluates that graph. Exec nodes represent operations such as importing data, running a container or exporting data. Continuation nodes call back into the syntax-tree evaluator to create additional subgraphs as needed.

Incremental evaluation searches the flow graph top-down for cached results, then computes missing work bottom-up. In the dog example, it first imports the list of images, then a continuation produces the resize subgraph. Cached thumbnails are reused while missing ones run in parallel, after which the montage can be computed.

Referential transparency also makes an expression a stable name for its value under the model. A module can hold both the description of a computation and a key for its result. This suggests treating modules as data APIs and organizing their names in a dataspace.

A normal script may depend on an image name that changes over time. A bundle freezes the module dependency graph and resolves external dependencies such as container images into a binary artifact. The bundled module remains usable as a first-class module while providing a stable anchor for the computation.

A dataspace maps symbolic names to modules. Those names can be inspected, documented and evaluated, giving consumers typed, modular and stable data interfaces. A policy could require a replacement module to be a subtype of the previous one, helping prevent incompatible updates while preserving incremental evaluation.

At the time of the talk Reflow is open source, used heavily at GRAIL and also by several other organizations. The goal is an integrated data-processing environment in which the user supplies credentials and the system handles execution and infrastructure.

Asked what it means to do the smallest amount of work, I clarify that I mean the total work required to compute the requested result, given cached results. Available resources may limit parallelism, so tasks are queued. The system does not yet prioritize based on which task would unlock the most downstream work.

Reflow supports branches such as if expressions. An audience member asks what happens when an underlying image changes without a source change: Reflow resolves image names to content digests and includes those in cache keys, so a changed image causes recomputation. Bundles can freeze those dependencies for production.

If resource requirements are underestimated, Reflow can oversubscribe some resources. Memory is harder because a process may run out; the runtime tries to recognize out-of-memory failures and retry with more memory. Better dynamic profiling and treating resource requests as hints are possible future improvements.

A question about large incremental graphs prompts a discussion of evaluator efficiency. The first implementation retraversed the graph whenever something changed; later work tracks dirty nodes and reference counts incrementally. Reflow graphs are often smaller than graphs in some other incremental systems, though users can generate very large ones.

What about time or randomness? The Reflow language does not expose those dynamic effects as ordinary expressions. More generally, the data model assumes that an external computation with the same inputs and fixed environment produces semantically equivalent output. Reflow cannot enforce that assumption for arbitrary external tools.

Asked about richer types, I say the team plans stronger declarations, for example describing a CSV’s columns or restrictions on a BAM file. Such types could let the system check more properties of data interfaces.

Language-level failures currently propagate and fail the task; there is no general failure-handling mechanism in the language. The runtime can nevertheless recognize certain infrastructure failures, such as out-of-memory or disk exhaustion, and retry under different conditions. An application failure remains a failure.

Reflow’s core data model is oriented around files, directories and bulk data. Its implementation uses DynamoDB for associations; loading results into external databases is possible through execution, with experimental support mentioned in the talk, but databases are not treated as a special core data type.