RFD 373 Reliable Persistent Workflows

Consider these pieces of control plane functionality:

What’s common among these examples?

With this phrasing, other examples come to mind:

We call these behaviors reliable persistent workflows (RPWs).^[5] We’ve also seen this called the "reconciliation pattern" or a "controller" (a term that’s unfortunately pretty overloaded in software).

Unfortunately, there’s no single right way to implement RPWs. There are a few patterns that work, and there are many patterns that seem like they might work but either don’t solve the problem or create new, harder problems.

The examples of RPWs above are pretty different from the use case for distributed sagas (provided by [steno] to implement [rfd107]'s "one-shot workflows"). With a saga, we define the whole directed acyclic graph (DAG) of actions that will achieve some specific goal like "provision an Instance". Sagas have several properties that make them unsuitable for what we’re trying to do:

Fundamentally, the goal of sagas is to decompose complex one-shot sequences into small pieces so that:

Sagas can potentially be part of the implementation of RPWs, but this too is tricky. More on this under "Pitfalls" below.

All RPWs are activated periodically, even if there’s no reason to think they need to be. This allows the system to repair brokenness resulting from bugs where an RPW is not activated when it should be or when Nexus crashes before the RPW finishes propagating an update.

There are several points in implementing an RPW where we can choose an "incremental" or "full" (or "holistic") approach:

These are separate, related choices. The basic tradeoff is that an incremental approach may be more efficient or scale better, but a full approach is usually easier to make correct. With an incremental approach, it’s easy for one bug to cause a system to be incorrect forever. By contrast, a full approach can often repair brokenness introduced by earlier bugs. A full approach may also have the benefit of the constant work pattern: that the amount of work that the system does does not change drastically under different load conditions.

[_generation_numbers] are a useful pattern for getting the benefits of the "full" approach efficiently and scalably.

It’s useful to group a bunch of "intended state" updates together and assign them a generation number. This is just a unique, monotonically increasing integer. Writing the intended state to CockroachDB already implies a total order on such changes. Generation numbers give us a handle we can use to identify a checkpoint in the neverending sequence of changes.

Using DNS as an example based on [rfd367]: each change to the DNS data is encapsulated into a single generation number. When activating the DNS propagation RPW, Nexus specifies the generation number that was just created. This is essentially a full update (see [_full_vs_incremental_updates]) because the generation number identifies the complete state of the DNS data, not just the change that was made in that generation. (Contrast with the approach where Nexus activates the DNS propagation RPW with a specific list of DNS names that were changed and then the RPW propagates just that.)

Targets (DNS servers) also report their state in terms of the generation number. This allows the RPW to do a full-state comparison by just comparing the generation numbers.

When sending an update to a target, the RPW can choose to send the full contents of a generation or just the delta between two generations. As mentioned above, the former is easier to make correct and also repairs any previous corruption. The latter is considerably more scalable in the long run. (If it comes to it, we can also do both: incrementals for most changes, and an occasional full audit.)

Target-driven propagation means that the body of the RPW lives inside each target rather than Nexus. The target would ask Nexus what its state should be on startup, periodically, or in response to a request from Nexus suggesting that the target update its state.

In order for Nexus to proactively request that the target update its state, Nexus probably still needs to maintain a simpler version of the RPW that can be activated on-demand to make that request to each target.^[10] By simpler, we mean that the "update" step just notifies the target that it should request an update.

This approach works well when the set of targets and updates are very well-defined. For example, this could work well for each Sled Agent to keep track of what customer Instances it’s running, its VPC configuration, and maybe even which control plane zones it’s running. It could work for the DNS servers, too.

Advantages of this approach:

Problems with this approach:

See also the [constant-work] design pattern.

Generally, Nexus-driven propagation means that Nexus runs the body of the RPW. It maintains a background task that periodically compares intended state vs. runtime state and then reaches out to targets to update them.

By "no mutual exclusion", we mean that there’s no mechanism used to ensure that only one Nexus instance activates an RPW at a time. It follows that it must be okay if multiple Nexus instances concurrently try to update various targets. This works well in the same cases where target-driven propagation works. In a sense, it’s very nearly the same thing: maybe the only difference is whether the target or Nexus runs the periodic loop.

Advantages of this approach:

Disadvantages of this approach:

This is Nexus-driven (see above), but where it’s essential that only one Nexus even attempt to perform the update step. The canonical case is service rebalancing. Suppose two Nexus instances decided "expand the CockroachDB cluster by 2 nodes". We really need mutual exclusion here to prevent them from expanding the cluster by 4 nodes.

We really want to avoid these where possible — see [_challenges_with_mutual_exclusion]. But they do exist.

How would we implement this? One approach is to:

Here, we leverage CockroachDB to provide the strong consistency / distributed consensus about who owns the lock. By wrapping this in a saga, and assuming we implement SEC failover (see [_assumptions]), we can assume that anybody who’s taken that lock will eventually finish what they’re doing and release the lock.

Advantages:

Disadvantages:

See [rfd367]. To summarize: DNS data will be stored in CockroachDB. Each name has a row that includes the generation in which it was introduced and (optionally) removed. The targets are DNS servers that will accept one of two kinds of requests: (1) full update to generation X, or (2) incremental update from generation X to generation Y, which should fail if the server is not currently at generation X. The RPW body is fairly straightforward: fetch the latest generation and for each target, either send it a full update to that generation or else fetch its generation, compute a delta, and send it an incremental update.

For background, see [rfd63]. Here, we’re talking about the distribution of VPC configuration. This configuration includes firewall rules, routes, and likely other data.

The "intended state" comprises all the VPC-related configuration that we store in CockroachDB today, including the firewall rules and routes. This information should probably be versioned with a generation number per-VPC.

We may want to think about each VPC’s configuration as an independently-executing RPW to ensure that problems propagating one of them don’t affect the others (and because it’s easier to implement it and report it on a per-VPC basis).^[11]

We may want to further split the distribution of networking configuration for a single VPC into two RPWs: one for sleds and one for boundary services, just so that each of these has a uniform set of targets.

One set of targets are the Sled Agents. The "runtime state" of each Sled Agent is comprised of whatever VPC configuration it needs to store, plus whatever is stored in OPTE. This RPW could be target-driven or Nexus-driven without mutual exclusion. Either Sled Agent could ask Nexus periodically for updated configuration for each VPC that it knows about, or Nexus could periodically ping Sled Agent and suggest that it update its config for a particular VPC. Either way, Nexus could poke Sled Agent to fetch updated config (or provide updated config) when something changes.

The other set of targets are instances of Dendrite, which manage Tofino switch configuration. Their runtime state is comprised of whatever they need to store locally, plus whatever has been programmed into the switch. The update process can work largely the same way, with Dendrite accepting updates in the form of a new versioned configuration. There may be some preference for Nexus-driven updates here if we don’t want Dendrite to have to know about Nexus.

We could think of "the list of customer Instances on a sled and their configuration" as an instance of RPWs. Indeed, the original design basically worked this way: on startup, Sled Agents report that they’re blank and Nexus is expected to invoke instance_ensure() to establish the current desired configuration. There’s no process for periodically ensuring that this configuration remains up-to-date (i.e., that all Sled Agents are running the Instances that we expect they are).

Today, when a change is made to intended state (e.g., an incoming request to halt an Instance), it goes to the Sled Agent first, Sled Agent applies the change, then Sled Agent reports the change in actual state to Nexus, which writes them to CockroachDB. We do not store separate intended vs. actual states. Essentially, the intended state is transient in Nexus and Sled Agent while it’s being applied.

One reason for this is that for Instance runtime state, Nexus and CockroachDB aren’t the only source of truth about the intended state. Customers can halt an Instance from within the Instance, without going through Nexus. That would reflect a change to both the actual and intended states. With the current approach, this works (at least architecturally) because Sled Agent can see the halt and propagate the state change back to Nexus and CockroachDB like any other state change.

One could imagine changing the implementation to work like an RPW:

It makes sense to preserve the current behavior that if a sled reboots, we do not assume the Instances that were running there should be re-established there, but instead they would be re-provisioned, by which we mean that they would go through the process anew of allocating runtime resources (possibly on a different Sled) and being started on some sled. We could still implement an RPW that periodically and on-demand propagates requested changes from CockroachDB to Sled Agent. This would be a substantial difference from how the Instance boot/halt/reboot paths work today. But "boot" likely already needs to be changed substantially (it shouldn’t assume the Instance is tied to a specific sled, even when the Instance is off). It would make this subsystem look more like the rest of the system and potentially be more rigorous.^[12]

Another consequence of this change is that the instance-provision saga would no longer be responsible for booting the VM. Instead, instance-provision would do all the work to allocate resources and record those in CockroachDB, then activate an RPW that would actually propagate the state (i.e., "this instance should be running and should look like this") to the corresponding sled (and anything else that needs to know, like Crucible).

TBD would be how to deal with changes to intended and actual state that are initiated by the VM itself (mentioned above), and how we reconcile conflicting changes from these two different sources of truth. The answer may involve being more specific about which parts of an Instance’s state (e.g., location vs. is-it-running) are owned by whom?

Similarly, we can think of the list of control plane components on a sled (like CockroachDB, Nexus, Internal DNS servers, External DNS servers, etc.) as an RPW.

The RPW would look similar to the one for Instances above. The update process would involve deploying, undeploying, or reconfiguring these components.

The most obvious approach for implementing RPWs is to update the targets inline with any API request (or other operation) that changes the intended state. This doesn’t work because in the event of any failure, we wind up violating one or more of our [_constraints].

We assume here that Nexus would update the intended state in CockroachDB before updating the runtime state of any targets. To do otherwise would violate our constraint about there being a total order on updates, not to mention public API expectations around durability and strong consistency.

If Nexus crashes before updating the targets, it violates the constraint about all targets learning about an update.

If two requests make different changes concurrently, even though CockroachDB will serialize them, there’s nothing to prevent some targets from hearing about the updates in the wrong order. Depending on the implementation, that could cause two targets to converge on a different final state, violating another constraint.

If Nexus fails to update one target (out of many), what would it do? If it completes the request successfully, it violates the constraint about all targets learning about an update. If it fails the request (or even just retries it, inducing additional latency), then it violates the constraint about one offline target blocking updates.

Consider implementing the distribution of VPC firewall rules. Suppose that the desired set of firewall rules is stored in CockroachDB and that changes to this set get propagated to some number of sleds.^[13]

We could say that when a change is made, Nexus kicks off a saga to propagate the new set of rules. If a sled is offline, the saga will keep trying until the sled does come back online. This has several issues:

We could say that when a change is made, if a saga already exists to propagate the rules, then we somehow update that saga to propagate the latest set of rules. There’s not a great way to do this. Recall that saga DAGs are immutable once the saga starts running. You could imagine a saga action whose behavior is dynamic based on the database state, but this gets ugly quickly. It’s fighting the saga framework (which is oriented around actions being small, atomic, idempotent, undoable steps).

We could say that when a change is made, Nexus kicks off a saga to propagate the rules if one is not already running, and that this saga simply does not retry failures. There would need to be some separate mechanism to update those sleds later. On the plus side, this avoids the unbounded queueing and thundering herd and related problems. But it’s not clear why we’d use a saga here, since it wouldn’t have any undo actions.

There are cases where a saga might be part of an RPW. Consider the service rebalancer. Imagine we want to deploy two more CockroachDB nodes. The RPW could see: "I need 7 nodes, but I only have 5. I need to kick off two provisions." It could kick off a saga that deploys the two nodes. It should use a saga here because each of those deployments individually comprises a bunch of steps that we do want to unwind on failure! This case seems to be the exception rather than the rule when it comes to RPWs.

Another use case of sagas is for RPWs that require mutual exclusion, mentioned above.

One approach to implementing RPWs is that when we make a change to intended state, queue a request to propagate that change to each target. The queue could be stored in the database, written transactionally with the change to intended state so that it can’t be missed. Or one might do this only after trying to [_why_not_update_targets_in_line_with_api_requests]. On failure to update a target, we might enqueue a request to propagate the change to that target.

Queues that are used like this have a bunch of problems. If the queue is bounded, you need some fallback mechanism to ensure correctness when the queue is full. In that case, you could just skip the queue altogether. But unbounded queues can turn transient issues into cascading failures that require human intervention to repair.^[14]

Instead of queueing up requests, we activate an RPW by sending a message on a (Rust) channel. A key difference is that any number of messages can be collapsed into one, since the RPW only needs to know if it’s been activated or not. It doesn’t need to know how many times it’s been activated or by what. (See [_full_vs_incremental_updates].) A watch channel is a good fit for this.

An intuitive way to implement RPW behaviors is to say that each job will be owned at any given time by one Nexus instance. It will be the only instance trying to do that thing. Maybe the Nexus instances negotiate that somehow ahead of time, or maybe each one tries to take a lock before activating any RPW.

The problem is that the [cap-theorem] constrains the properties of a distributed lock that we’d like to remain available when the holder goes out to lunch. Systems like [chubby] use time-based leases, such that if a node holding a lock is unresponsive for too long, it loses its lease (lock). But this cannot be enforced without a hard real-time system. Imagine the case where a node obtains a lease, becomes partitioned, then attempts to issue a request to a service that’s only supposed to be used with the lease held. The request is in the local networking stack socket buffer. The lease expires and is given to some other node. Then the partitioned is removed and the request is sent — mutual exclusion is violated. This particular example might seem contrived, but the observation is that if mutual exclusion relies on the lock holder to enforce its own lease time, then it implicitly assumes something about the liveness of that system. That assumption is often violated in practice as a result of partitions, pathological system behavior, debugging activities, etc.

"Taking a lock" in a distributed sense is fraught. Instead, one approach is to take whatever operation would be protected by that lock and make it safe to be called by multiple nodes (the would-be lock holders). Take the DNS propagation RPW. We’d like to put the whole RPW under a mutex. Instead, multiple Nexus instances might duplicate the work of calculating what updates are needed. All that really needs to be protected is the update to each DNS server. But we don’t need to enforce that at Nexus. The DNS servers themselves can serialize the requests that they receive. Another approach is to invert control as described above: have the target be responsible for requesting updated state, possibly in response to a prod from Nexus. There’s no silver bullet for translating mutual exclusion into something else, but there are several patterns that work well in different conditions.

See also: [kleppmann].

We’ve essentially defined correctness by our [_constraints]. The system is broken if a particular RPW comes to rest with some online target not having the latest update. There are a few ways this tends to happen in similar systems:

Each of these represents a bug. But unlike many bugs that only affect the current runtime state of a program, these bugs potentially cause the system to be wrong forever.

We propose several patterns to reduce the risk that the system becomes permanently broken. It can still happen, of course. And bugs can easily cause the system to be broken until the next activation of an RPW. This can noticeably degrade the customer experience. Imagine we forget to update [RFD 21] Instance DNS at provision-time and that’s only fixed by our periodic every-hour reactivation.

We should try to identify activations that we expect will trigger no actions and record an error if we find that they did trigger actions. This should be reported to Oxide support so that we can root-cause and fix the underlying bug. We can’t catch all of these. But we can reliably identify cases where the actual state of the world shouldn’t change behind Nexus’s back, the intended state of the world hasn’t changed since the last successful activation, yet the activation produced next steps to take.

If we get reports of these bugs, what information will we want? Usually we want to know which code path failed to trigger an update. To that end, we’d love to know:

Of course, we could also run into situations where the final state on some target didn’t match what we expect, either because it was different from other targets or different than the intended state. To root-cause these, it would be useful to keep logs of all the work done by RPWs: what actions were computed and taken on which targets. See [_building_block_background_tasks_in_nexus] for an example of what we could keep.

Besides the obvious correctness issues discussed above, operational issues with systems like this include cases where propagation has stopped for some reason. By construction, when the system is seeing changes to the intended state, there’s always a gap between the intended and runtime states. The operational issue revolves around how large this gap is, usually measured in time. e.g., the DNS servers are often going to be a few seconds out-of-date. We probably want to raise an alarm if they become a few minutes out of date.

With the right abstraction in Nexus, it should be possible for Nexus to provide basic metrics about all RPWs, including:

This would enable the system to raise alarms if:

It would also enable the system to affirmatively report how up-to-date some target or subsystem is (instead of expecting people to trust that no alarms means no problems). This follows the principle that software should be able to exonerate itself when it’s not the problem.

This data would also enable Oxide support to answer a lot of questions we might have if we were looking into those alarms, like: did we try to update that target?