designing a query system

From the start of this year, I have slowly been going about designing a query system for Krabby. It took five months of sitting still and thinking really hard, but I believe I have a clear grasp of the design now. I’m going to explain why Krabby needs a query system (because I thought it wouldn’t for a while), the special features I wanted, and how everything fits together.

precursor: the push-based architecture

My original vision for Krabby was a push-based architecture where tasks “push” their outputs to later tasks that need them. I thought this would have a lower overhead than a “pull-based” query system. And this felt feasible because (particularly in the earlier stages of compilation) the dependencies between tasks can be known upfront. The compiler could execute many independent tasks of the same type in an easily parallelized fashion.

This greatly influenced the design of my name resolution algorithm. My idea was to (often pre-emptively) parse Rust source files from the target crate’s src/ folder and inject their results into a global database of Rust items. The database would also store pending references to as-yet-undiscovered items, and when those items got added, the references would be resolved.

I was quite happy with this design for a while, but as I got into the weeds of the implementation back in December, I realized the design had some important flaws.

• Because the global database tracked pending references, it was basically a specialized query system — I hadn’t escaped that complexity.

• Because it was lazy, it wouldn’t make good use of the CPU cache: items could be added (and thus inserted in the cache) much earlier than their first use. An eager approach, where items are looked up when they are first needed, would improve the use of the cache.

• Unbalanced dependency graphs (containing long chains of tasks that must be done serially) would not be handled efficiently. The architecture is unable to identify tasks which are heavily depended upon, and does not control when they are executed. They might be executed very late in compilation, and cause a single CPU to keep working after everything else is done. In contrast, a pull-based approach would add an element of demand-driven prioritization.

• A pull-based approach can target a different goal (e.g. cargo check vs. cargo build vs. identifying a particular Rust item) easily. This is crucial for making Krabby usable for LSPs, where user-initiated actions (e.g. find all references to foo()) should be evaluated as quickly as possible, with minimal unrelated work.

This stopped my name resolution implementation work in its tracks. I began designing the query system at the very start of 2026, and (excluding a two-month tangent to write housekeeping), it’s been my primary focus. Let me tell you: designing a query system is a lot of work!!

my wish list

I am perpetually saddened by the fact that codebases are fundamentally limited by their historic design choices. The way a program is architected specializes it, and sets it down a path it cannot be shaken from easily. I keep seeing features and optimizations blocked by years-old decisions that never considered their possibility. It’s just the way things are, but I find it heartbreaking.

With all my projects, but Krabby in particular, I try to explore the design space as thoroughly as I can—to look five, maybe ten steps ahead. I try to design things to elegantly allow for all the possibilities I can foresee. This is fallible, of course, but I find solace in knowing I tried. That’s my excuse for writing a seven-thousand-word blog post.

Here’s the list of interesting features I thought of for Krabby’s query system. I’m mostly focusing on the ways it departs from rustc’s query system and salsa. I’m not going to try implementing all of these features immediately, but I have tried to integrate their needs in my design.

• Concurrency: The query system should operate across multiple threads and efficiently distribute tasks (which are fine-grained units of work) between them. It needs to handle contention (different threads trying to compute the same data) and detect cycles across threads.

  This isn’t a unique feature, but I think it has the biggest effect on the design. rustc’s frontend already supports concurrency (it has been in development for a while, but it is now tested as part of CI). I hope to embrace parallelism even more with Krabby, treating it as a requirement from day one and letting it shape the rest of the design.

  The housekeeping crate was an important step towards concurrency. It provides an essential ingredient for building high-performance concurrent data structures: a safe way to deallocate resources shared between threads. While other implementations of this exist, housekeeping provides some additional features (and, I hope, better performance). I plan to write up its design sometime.

• Asynchrony: Tasks should be able to pause and resume. This unlocks several features on its own, and deserves a sub-list:

  • If a task depends upon something running on a different thread, it can pause, allow other tasks to execute on the current thread, and resume once the dependency task completes. salsa does not support asynchronous tasks, and it deals with such situations by blocking the current thread.

  • A task can depend upon multiple other tasks at the same time, and only resume once all of them are complete. This is a second kind of batching: tasks can make multiple queries at the same time, and pause if any of them cannot be computed immediately. This is analogous to structured concurrency for async functions: waiting for multiple futures to complete concurrently rather than .await-ing them one at a time.

  • Asynchronous I‍/‍O tasks can be implemented. Since Krabby incorporates Cargo, a key asynchronous I‍/‍O task is fetching resources from the network. This allows Krabby to fully implement Cargo’s functionality with queries.

  • It unlocks the use of io_uring, a Linux subsystem for batching system calls and trimming overhead (often by a huge margin!). Somewhat surprisingly, I‍/‍O can be a bottleneck for Rust compilation, sometimes: it comes up when saving incremental compilation state, and when loading source files to identify changes since the previous compilation.

  I’m not going to implement this with Rust’s actual async mechanism, since I have some concerns about its performance. I’ve thought about some concrete types of tasks and what their async state is going to look like, and I’ve concluded that using async would not substantially cut down on boilerplate. A manual implementation would have less (memory and runtime) overhead.

• Batching: The query system should collect together tasks by type (e.g. “name-resolve this Rust module”) and try executing batches of (e.g. 64) tasks of the same type at a time.

  Batching is a principle I often try to explore with Krabby. It should have some immediate, minor benefits (e.g. better use of the code cache), but its real value will come in the distant future. I think there is a genuine possibility that certain tasks in the Rust compiler could be written in an explicitly batched way, and that this could unlock unforeseen optimizations.

  While I don’t have numbers to hand (and I plan to collect some soon), hash table lookups (which appear everywhere in compilers) can be significantly optimized by batching. They are almost entirely memory-bound, so their latency is much worse than their throughput: they are slow to execute, but they don’t take up too many CPU resources. Modern CPUs are already very good at ILP and can get other work done while memory fetches for hash table lookups are ongoing; I think explicit batching could improve runtime by another 20-40%.

  The other optimization that would be unlocked by batching is of course SIMD. While you can probably find SIMD-based lexers in the wild, I have never seen SIMD being explored for more complicated stages of compilation, such as AST lowering or type checking. I don’t know whether anything will come of it, but I believe such avenues are worth exploring, and batching has the best chance of making them worthwhile.

• Pre-emptive tasks: Some tasks should be executed even if they haven’t been queried for yet. Whenever a worker thread finishes its current tasks, it should eagerly find new ones to execute. Tasks can be sorted (using some simple ad-hoc heuristics) to prioritize executing tasks whose results will probably be queried for soon.

  “Wait, you need a multi-threaded queue to distribute tasks, and you want it to support prioritization? Where are you going to find that??” Well, dear reader, turns out I already wrote one last year for Krabby’s push-based architecture! And it’s fast! As you’ll see, the task queue helps implement several other features too.

• Integrating Cargo: Krabby would build-in support for Cargo, implementing the cargo CLI, parsing Cargo.toml, and resolving dependencies itself. (You would still be able to use it like rustc or patch it into your own build system.) While this isn’t a feature of the query system, it has far-reaching consequences and I think it bears mentioning.

  I often run into cases where cargo build and cargo check rebuild crates unnecessarily and use a single CPU for a very long time. A simple example: while working on rustc, I removed some unused code in rustc_ast, and this caused 48 other crates to be rebuilt over 90 seconds. There are several problems here:

  • Cargo has a very simplistic understanding of rustc; if the modification times of any source files (see the tracking issue for using checksums) or dependencies of a crate have changed, Cargo will re-invoke rustc. I think it assumes every invocation of rustc will lead to different output, so it will also rebuild any crate depending on that output. Running touch compiler/rustc_ast/src/lib.rs (changing the mtime but not the contents of the file) and re-compiling, which should be a simple no-op, still rebuilt 48 crates and took 15 seconds.

  • While rustc uses a query system and avoids repeating work, it only does so for the later stages of compilation. Parsing, name resolution, and macro expansion are not part of the query system today. Any invocation of rustc will lead to these stages being repeated in full.

  • rustc requires a crate’s dependencies to be compiled before it starts. This sounds reasonable on the surface, but it severely impedes parallelism and it’s not functionally necessary. Given a long chain of crates that depend on each other, a change to the innermost crate will cause the whole chain to be rebuilt, serially. rustc already tries to amortize this: it splits code generation from the rest of compilation, so the first half of compilation for each crate happens in parallel with the codegen for its dependencies. A fine-grained approach is needed to resolve the issue in full.

  I believe I can avoid these issues in Krabby. Krabby will compile all crates in the dependency graph simultaneously, and could start compiling two crates in parallel even if one depends on the other. I’m phrasing Krabby’s dependency graph in units of Rust items, not crates, so you need a long chain of Rust items that depend on each other to bottleneck Krabby. And Krabby will work around many such cases; for example, a function call foo() can be type-checked given the signature of foo, not its implementation; so given 20 functions that call each other, Krabby could resolve all 20 function signatures, and then all 20 function calls, in parallel. I think Krabby would largely eliminate the frustration of single-CPU bottlenecks for end users.

  Integrating Cargo would add and remove overhead: Krabby would have to track the crate from which every bit of data (e.g. a Rust item) originates, whereas rustc (usually) only needs to think about the crate undergoing compilation. On the other hand, Krabby can communicate data between dependency crates via memory, instead of writing it to and reading from a file on disk. Regardless of the mitigation of bottlenecks, I am quite sure integrating Cargo will speed up compilation significantly.

• Better incrementality: Query results should be saved for incremental compilation in a simple, user-configurable cache. Cached queries should be keyed in a context-free way (i.e. not be bound to the prior compilation).

  This sounds simple, but it’s a really ambitious change, and I’m very excited about it. You see, rustc’s incremental cache only holds the information it used during the most recent compilation. Data from previous compilations that is not used by the most recent compilation gets removed. Thus, simple changes, like undoing a previous addition or jumping around between Git commits, easily trip up rustc and re-do work unnecessarily. Furthermore, rustc requires that all the information from the previous compilation is available in the incremental cache. You can’t limit the size of the target folder (a problem that gets much worse with Cargo).

  In Krabby, I plan to save data about queries in a simple key-value cache, where you could configure a cache eviction policy (e.g. LRU). For example, a “type-check this function” query would be keyed by the contents of the function. I think it would unlock a lot of user-visible benefits:

  • You could configure a maximum size for the cache, e.g. limiting your target folder to 1GiB. If Krabby can’t fit all the data it wants there, it would have to recompute data more often, but it would be rare and it could give you a warning; that’s a worthwhile tradeoff for avoiding 50GB target folder explosions. We can tune the cache eviction policy to prioritize important, expensive-to-compute data.

  • Much of the cache could be reused, even if you change Cargo feature flags. Today, Cargo stores multiple incremental caches in target, keyed by the subject crate and its feature flags. Compiling a different set of feature flags under Cargo causes a full rebuild; this would not be the case for Krabby.

  • Following from this, you could have a system-wide cache for common crates, which would provide speedups even if you compile those crates with different feature flags. This is sort of like a built-in sccache. It could keep track of frequently used crates and prioritize storing them in this cache.

  • Krabby could use a shared cache to compile multiple checkouts of the same codebase at different commits; this could be incredibly useful if you’re looking at different versions of a big codebase simultaneously (e.g. for bisecting a bug or benchmarking).

• Streaming queries: Sometimes Krabby needs to compute a collection of data. Think of the “find all references” command in your IDE; glob imports (i.e. use foo::*); or Cargo’s --workspace option. In all of these cases, the compiler has to identify every item in a collection (every use, every imported item, every Cargo package). Some items may be discovered quickly, while others might be very time-consuming. You might have references located in other crates, glob imports from a module containing its own glob imports, or Cargo packages identified by a filesystem glob like crates/**. Streaming queries is the idea of returning items as they are discovered, instead of waiting for all items to be discovered exhaustively. This can lower latency, reduce work, and improve parallelism.

• Accelerating compiler development: While working on rustc, I often run its tests/ui test suite. This will compile over 20,000 independent Rust files and check the compiler’s output (almost always for specific error messages). My laptop is outfitted with some great hardware, but building the compiler running tests/ui takes a while (21,532 tests in 160 seconds; 133 tests per second; 8 tests per second per thread). I think we can do better!

  I know that my changes were unrelated to the vast majority of these tests. The compiler’s query system could help verify this for me. If it were able to detect which parts of the compiler, and thus which query implementations, had changed, it could use the incremental cache to re-run only those queries, finishing quickly if their output is unchanged.

  I spent a few hours thinking about this, and it’s really hard to implement in a safe, correct way. You would have to back this up with full, non-incremental tests; in the very best case, as weekly CI runs. But it seems… doable… the code for each kind of query could be compiled into a separate shared library, and we could rely on simple “has this file changed?” mechanisms as a good start. I think this would speed up build times too.

the design

Tying all of these features together into a single coherent design was really tricky. In particular, concurrency, asynchrony, and batching interact with each other in subtle ways. Their combined complexity is far more than the sum of their parts. But I think (I hope!) my design accounts for everything.

Let’s define some important terms. The query system is responsible for computing units of data, like “the Rust edition of this crate” or “the expansion of foo!()”. A query is a request for a unit of data. The same data can be queried for multiple times. A task computes some requested data. If some data is queried for, a task will be executed to compute it. While executing, a task can query for more data. The defining property of the query system is memoization: even if data is queried for multiple times, it should only be computed once.

The query system is initialized with a top-level task, such as cargo build. It strives to complete the task as soon as possible. Our goal is to minimize latency, the time between the start and end of the task. We can achieve this by parallelizing aggressively and reusing work.

The workload of the query system can be viewed as a graph of tasks and queries, or a stack of function calls. Consider a Cargo package foo with a single file src/main.rs:

fn main() {
  foo();
}

fn foo() {}

That’s already pretty complicated! I’ve tried to model it pretty closely to concrete implementation needs. You can see some of the features I talked about previously: Cargo is handled within Krabby; early steps like parsing are part of the query system; and function calls only require the signature, not the body, of the callee.

In the context of this graph, the query system’s job is to execute tasks as efficiently as possible. Given a finite number of CPUs, it needs to decide schedule tasks to execute across those CPUs over time; its scheduling decisions determine when compilation will finish, and thus the overall latency.

The best possible latency (assuming infinite, perfect parallelism) is bounded by the longest chain of tasks which depend on each other: the critical path. The critical path must consider how long each task takes; in the graph, I’ve highlighted a potential critical path in bold red. The query system must strive to identify critical paths and prioritize their execution.

While this graph may feel quite thorough, it misses a lot. In particular, it doesn’t identify why a task like “find foo()” was executed. It was needed by a later task, “nameres main() body”, but how did we know it was needed before the later task was executed? The later task had to inform the query system that it needed “find foo()”; it must have started executing earlier than shown in the graph. Let’s try a different visualization—a call stack:

cargo build
load Cargo.toml
compile foo
find main()
parse src/main.rs
nameres main() signature
codegen main()
typeck main() body
typeck main() signature
nameres main() body
find foo()
parse src/main.rs
nameres foo() signature
typeck foo() signature
codegen foo()
typeck foo() body
nameres foo() body
typeck foo() signature

This shows us something very useful: the start and end boundaries for tasks. Tasks like “compile foo” start very early and end very late; they encompass many other tasks. It highlights the causality implicit in the previous graph: tasks can be caused by others without depending on them. The “parse src/main.rs” task doesn’t depend on the “load Cargo.toml” task; but it was only invoked because of the results of the latter.

This call stack could be optimized a bit. “codegen main()” requests “codegen foo()” after “typeck main() body” is complete; but we can figure out foo() is needed earlier. “codegen main()” could directly invoke “nameres main() body”, concurrently to “typeck main()”, and ascertain the need for foo() from that.

This call stack view is not strictly superior to the graph. It shows the “parse src/main.rs” task multiple times. It obscures parallelism: it’s less obvious which tasks can be executed in parallel. I find both visualizations helpful; they have strengths in different contexts.

This section has been pretty generic thus far. Let’s get into the details of Krabby’s design. I’ve organized the following sections as an explanation of the system as a coherent whole, where each section covers a different topic. I would suggest skimming through the sections to get an overview, as if this were a paper.

tasks

A task computes a unit of data. A task is an instance of a class which the query system is aware of. A class is a concrete name for a task implementation, which is a concrete Rust type and associated code. Task metadata is information managed by the query system about the task.

Tasks have a life cycle. Tasks may be enqueued in the task queue, before they are queried for. They will eventually be started, due to the task queue or a query by another task. If they need to wait for pending queries to complete, they become blocked; when all their pending queries are complete, they are resumed. Eventually, they are finished.

A task implementation centers around a concrete Rust type. This type holds the state of the task across its life cycle (from the time it is enqueued / queried for, until it is finished). The type has several properties:

• A reference to a slot, which holds the output of the task. It is a container analogous to a OnceLock. It holds the metadata of the task.

  Slots can be allocated and managed by the user instead of the query system. This is particularly helpful for name resolution, where I plan to write a concurrent “database” to map Rust paths to items. I will structure the database to provide additional useful operations, e.g. finding declarations across namespaces and resolving glob imports. I can allocate slots directly within the database.

• A poll function, which contains the code for the task. It is executed to start and resume the task. It is very similar to Future::poll(); it takes a reference to the task state, a handle to the query system, and tries to make progress on the task.

  It may initiate queries for other data. It does not need to return anything; the query system records all the queries it makes, and can automatically determine whether the task is blocked on any pending queries. If it is not blocked on anything, it must have finished, and written the output to a pre-determined slot.

  Poll functions are intended to be implemented by hand. They can (and should!) query for as much data as they can concurrently. As far as I can tell, most poll functions will follow a simple pattern:

  • execute all known queries (even pending ones from a previous poll)
  • accumulate the results into the task state
  • this may result in new queries; execute them too, repeatedly

  • if all queries were resolved successfully:

    • post-process the state and write the output to its slot

• A priority: determined using ad-hoc heuristics, this controls when the task will be started from the task queue. Priorities should reflect the critical path length of the task (tasks which appear earlier in critical paths should have higher priorities). For example, “compile a crate” tasks should generally have a higher priority than “type-check a function” tasks, because the subject crates might need lots of time to compile. Priorities can change over time. They could leverage statistics from previous compilation sessions.

• A batch poll function, which is equivalent to (but possibly more efficient than) calling the poll function on a list of task states one by one. It can transpose the regular control flow (where the same sequence of steps are followed one by one for each task state) and instead process all task states one by one for each step in the sequence; this may provide low-level performance improvements. It could even unlock the use of (auto)vectorization.

Over their lifecycle, the query system records different information about tasks. Most of this information is stored in the task slot.

• No information is saved before a task is started.

• When a task is started, it is marked as such in the slot. Once marked, it cannot be started again; this ensures tasks are memoized. If the task was initiated because of a query by another task, this link is not explicitly recorded here; it is recorded by the executing thread.

• If a task is queried for after it has started, the queries are recorded in the task slot. This should be quite rare.

• If the task is waiting on one or more blocked (not pending) queries, the task slot accomodates a counter for blocked queries and a way to resume the task. Every time a query finishes, it decrements the counter; once it reaches zero, all blocked queries are complete, and the task will be resumed.

• For incremental compilation, the list of queries emitted by the task (in order) is recorded. This information is not stored in the task slot, and it is only recorded if incremental compilation is enabled.

Task classes are stateful. They are represented by class handles, through which data (as produced by the tasks) can be queried for. Class handles are reference-counted, and are held as long as more queries can appear. Once they are dropped, any associated data can be dropped too. This makes it possible to deallocate significant chunks of data in the middle of compilation.

A good example (and the main one on my mind) is name resolution. Here’s a simplified idea of a name resolution task for function bodies:

// converts AST -> HIR
struct NameResFnBody {
  slot: Arc<Slot<FnBodyHir>>,
  // a HIR that contains unresolved references
  hir: FnBodyHirBuilder,
  // the scope of the containing module
  scope: Arc<NameResScope>,
}

impl Task for NameResFnBody {
  fn poll(&mut self, handle: &mut QuerySystemHandle) {
    // `uref` is e.g. `foo`, `util::block_on`
    // `uref.base()` is `foo`, `util`
    for uref in self.hir.unresolved_refs() {
      // `path` is e.g. `takeaway{crate#123}::util`
      let path = self.scope.get(uref.base());
      if let Ready(decl) = handle.lookup_decl(path) {
        // may cause macro expansion and reveal new refs
        self.hir.insert(uref.user(), decl);
      }
      // keep going even if a query is blocked
    }

    if !handle.blocked() {
      // all queries finished, the fn is resolved.
      self.slot.write(hir.finished());
    }
  }

  fn priority(&self) -> u32 {
    400 // could also be dynamic
  }
}

queries

A query is a request for some data. Queries are initiated by tasks (their sources), and the data they request is computed by other tasks (their targets), so they can be viewed as links between tasks (as we see in the execution graph above).

Like tasks, queries have a life cycle. First, they are initiated. If the requested data has already been computed (i.e. the target task is finished), they are marked as complete immediately. Otherwise, they are pending; the target task has not yet started, or (in rare cases) is already running. The worker thread responsible for the source task will try to start the query, locking the underlying task slot and starting the target task. If the target task is already running, starting fails, and the query becomes blocked. Blocked queries are registered in the metadata of target tasks so they can resume source tasks upon completion.

Queries can form cycles. If a set of queries depend on each other, they would all block indefinitely. Cycles are not always an error; they can occur beningly during name resolution (e.g. while resolving circular imports), and are a major consideration for trait solving. Query cycles must be broken by reporting to one of the involved tasks that it is part of a cycle. The task can choose how to handle this; it might stop and produce an error, or it might retry the cyclic queries with different arguments. The selection of this task, among those in the cycle, is arbitrary, and results should not depend on it. Note that cycles can be nested and interleaved in complex and unintuitive ways.

There is special support for streaming queries. These are queries whose results are collections (ordered, i.e. Vec, or unordered, i.e. HashMap/HashSet). They can return results incrementally (adding to the collection over time). When a task depends on such a query, it can observe the data collected thus far, even if all results are not yet available. It will be blocked on the query, but will be resumed every time new data is added, as well as when the query completes.

worker threads

Tasks are executed by a fixed number of worker threads. A worker thread holds a set of ongoing tasks, which it is responsible for executing, and a reference to the task queue, through which it can obtain new tasks.

Worker threads try to execute tasks in batches; they organize new and old tasks by their class and execute all available tasks in a class, one class at a time. They use the batch poll functions defined by task implementations. For each known (or recently used) class of tasks, they maintain a pending set: a set of tasks of that class that are ready to start/resume. These sets are picked from arbitrarily and executed; if a set has very few tasks, more (of exactly that class) may be loaded from the task queue first.

If a task is executed, and it queries for data that has not yet been computed, the task will be stashed away locally and the requested tasks will be started (they will be added to the pending sets of their classes, so that they can be batched). The original task is considered their parent. The newly started tasks may get stashed themselves, resulting in a hierarchy of stashed tasks.

The worker thread keeps track of the reason a local task is being executed. It may be executed because it was fetched from the task queue, or because it was queried for by another local task (in which case it stores an identifier for that parent task). When a local task completes, the queries waiting on it (the parent, if any, and others tracked in the task metadata) are unblocked, possibly causing some tasks to be resumed.

caches

Krabby has an in-memory cache and an on-disk cache. Both store pairs of keys and values. Values can be looked up by their keys and new key-value pairs can be inserted. The two caches use different concepts of keys and values. The in-memory cache is essential for compilation—it includes task metadata and output slots. The on-disk cache is only used for incremental compilation, and it records the execution of tasks in greater detail.

The in-memory cache holds per-class and inter-class data. For each task class, it holds a database of task slots. These encompass completed, ongoing, and enqueued tasks. When a query is emitted, the corresponding slot is looked up here (and is added if it does not yet exist).

The on-disk cache augments this, allowing values from previous compilation sessions to be reused. It is more expensive to look into, so it is only used for certain (more expensive) classes of tasks, after the in-memory cache is checked. (In some cases, data may be loaded before it is needed.) It stores task recordings.

A task recording allows re-executing a task incrementally. While executing, the task emitted queries. The task recording stores the key and result of the task, and the keys and results of the emitted queries, in the order they occurred. The task can be replayed by invoking those queries again; if all their results match the stored values, the stored result matches the up-to-date output of the task. Multiple task recordings may be cached for the same key, and they may share the same initial queries.

Data in the on-disk cache is canonicalized. Data irrelevant for a task, such as identifier IDs, can be moved to an external array and replaced by indices into that array. These indices will be used consistently throughout a task recording, so they correspond between the task key and its results. The external array will not be included in the cache key, so queries with different identifier IDs could use the same cache entry.

Large values (e.g. HIR data structures) will appear multiple times in the on-disk cache. The output of a query, which may be such a large value, will be referenced by its dependents, and possibly used as inputs to other queries. For efficiency, these values are interned—they are deduplicated (across the entire on-disk cache) and identified by small numeric IDs. This is relevant to incremental compilation.

The caches can be configured with eviction policies and maximum sizes. This is most important for the on-disk cache, to limit the size of your target folder. I haven’t looked into the theory of eviction policies, but I guess we could start with simple LRU and tune the implementation over time. Applying a maximum size to the in-memory cache is useful in the face of memory pressure.

incremental compilation

Some tasks are impure. They perform I‍/‍O and their results can vary across compilations. The most important such tasks read Rust source files from disk. These tasks don’t emit queries; they are leaves in the query tree. They are the starting point for incremental compilation.

rustc and salsa use the red-green algorithm for incremental compilation. They operate relative to the previous compilation (and do not consider or store data from older compilations). Tasks are considered “green” if their results are the same as from the previous compilation, and “red” if they have changed. The on-disk cache holds task recordings from the previous compilation. Tasks are re-executed (from top-down or bottom-up), eventually leading to the recomputation of the impure leaves. If a task’s result is unchanged, it is marked green. If all a task’s inputs (the results of the queries it emitted) are green, it too is marked green. If any of the task’s inputs are red, it is recomputed; if its result has not changed, it is still marked green.

Krabby extends the red-green algorithm to re-use data from older compilations where possible. It continues to specially cater to the immediately previous compilation; however, when a task needs to be recomputed (i.e. its inputs are red), Krabby first checks the on-disk cache for a matching task recording. Data from the previous compilation is allowed to be missing (to satisfy cache limits), preventing the affected tasks from being marked green. But data for those tasks might be available from older compilations, and data for the dependents of those tasks might still be cached.

In some cases, Krabby can apply heuristics to deviate from this algorithm. It may choose to re-execute some tasks before they are known to be needed, e.g. to pre-emptively check often-used tasks, or to support batching.

cycle detection

Krabby uses three algorithms to detect cycles: an eager, per-thread one, that is fast but reports false negatives; a lazy, cross-thread one, that runs infrequently but reports false positives, and a slow one that can check cycles in a particular task. The eager algorithm is the conventional one for cycle detection (where you check the current thread’s stack of queries). The lazy algorithm is analogous to a deadlock detector, and it relies on an interesting notion of reachability. The slow algorithm walks the dependency graph around a particular task to unambiguously identify cycles.

If a task emits a query for data that is in the process of being computed, the query and the task are blocked. The target task may be running on a different thread (due to concurrency), running on the same thread (due to batching), or a cycle is being formed. In the latter case, the target task will get blocked on the query too; this forms a deadlock. The tasks involved in the cycle will be blocked forever.

A blocked task is blocked on one or more queries. Krabby measures whether the task can be progressed. A task can be progressed if 1) it is executing, 2) it was blocked but is now ready to resume, or 3) if it is blocked right now but one of its dependencies can be progressed. This is a deliberately weak definition: some tasks caught in deadlocks might be misclassified this way.

Suppose that a task is blocked on two queries, one causing a cycle/deadlock, the other being executed. By the above definition, Krabby would assume this task can be progressed. But once the second dependency finishes executing, the task will only be blocked on the cycle causing query; Krabby would recognize that it cannot be progressed. Even if a deadlocked task is misclassified, it will only be misclassified temporarily.

So, Krabby periodically collects all the tasks that definitely can be progressed, from the local ready-to-resume tasks on each worker thread. It looks up the blocked tasks depending on them and marks them as can-be-progressed, recursively. The blocked tasks that do not get marked are parts of cycles. However … some tasks might be misclassified due to race conditions (akin to tearing) while collecting from the worker threads.

The last step, then, is to pick tasks that are likely to be deadlocked, and to explore their dependencies recursively to confirm it. Once a cycle is identified, the task is unblocked, and the cycle will be reported to the task when it resumes.

A few optimizations: cycle detection is skipped for certain classes of tasks, if the user believes they cannot run into cycles. The lazy algorithm only considers blocked tasks that are sufficiently old (e.g. have been blocked for more than 500 microseconds). I expect to find more ways to tune it in the future.

what’s next?

These ideas have been swirling around in my head for more than seven months, and they still make my brain hurt a bit. I think they’re ripe for implementing, though! I’m going to present my query system at EuroRust 2026 in Barcelona, during which I’ll show off query-based implementations of Cargo, one using salsa and one using krabby-query. I’m currently working on the salsa implementation, and getting a good sense of the specific queries I will need; I’m going to start implementing krabby-query soon. I’m super excited!!!

If something feels unclear, you’d like to hear more details about something, or you just want to keep up with Krabby development, join our Zulip!