EDIT: #91 supersedes this with a dramatically simpler approach that uses a permission-slip-assigned timestamp to give total ordering to sessions.

Nope

Unfortunately, distributed systems.

The desire

An operator submitting a job to the rack would like to rely on the following hierarchical mental model:

• At any given time, there is at most one support session on the rack.
  • Creating a new session automatically ends the previous session.
  • Sessions can also be manually ended by the operator.
  • Each session consists of a queue of jobs, each job addressed to a non-empty set of sleds in the rack.
    • Each job is only executed by the sled(s) to which it is addressed.
    • While the session is alive, each sled attempts to execute its queue in linear sequence from the start of the session.
      • Sleds execute their queues independently, without blocking on one another, so each sled potentially has a unique position in its own queue of jobs.
      • No jobs addressed to a sled are skipped by that sled unless explicitly aborted by the operator while enqueued and not yet executed. (Note that while sush supports a "skip job" functionality, this is a request for permission from Oxide to skip the job prior to its distribution to the rack. Operator abort terminates a job once it has already been submitted to the rack.)
      • Every sled executes its filtered sub-sequence of jobs in the same order as every other sled, and this order matches the order in which the jobs were authorized by Oxide Support.
      • Optionally, jobs may specify that they be run concurrently with other jobs, so while the order of jobs starting is fixed, their order of ending may be nondeterministic in this case.
      • If the session ends before all the jobs are finished on a given sled, the sled may not finish executing all the jobs in the session, but will pick up executing jobs from the start of the new session.
      • ⭐ A given job executes at most once on any given sled, no matter what.

The operator expects all these guarantees to be true even if the system is arbitrarily degraded: this is when they will be using sush, and it must follow their mental model without surprises — especially without hard-to-explain surprises! — at their greatest moment of need.

In this document, we will focus primarily around the mechanisms to guarantee:

However, a great deal more mechanism and background need be explained in order to lead up to the punchline(s), much of it justified by the other requirements in this model. Thus, we begin:

Unfortunately, distributed systems

Consider that this mental model must remain sound even when:

• NTP is unavailable, so there is no trustworthy time source to use for ordering observed events or messages.
• The control plane is down, so there is no strongly consistent data store available.
• Enough sleds are out of service that trust quorum cannot unlock, meaning that there is not even an encrypted dataset locally on each sled to store the job queue durably (we reject storing it on the M.2 unencrypted, because this would expose the plain-text job history).
• Arbitrary failures may occur on individual sleds, before and during the support session, up to and including arbitrarily frequent crashes, restarts, and permanent hardware failure.
• Arbitrary disruptions to network topology may occur between individual sleds, before and during the support session, up to and including frequent and prolonged partitions between arbitrary sleds, including transient or permanent failure of one or both switches. (In our model of connectivity for sush, we think of the network as an arbitrary graph topology, even though the realizable topologies are likely a subset of this space. If it's correct for all topologies, it must be correct for whichever occur in reality.)

Causal gossip and its consequences

Sush endeavors to uphold this model in these very adversarial circumstances by hewing to a design of eventual, causal consistency. We rely on the gossip library rumors for causal gossip point-to-point between sleds. This gives us the ability to assign a partial ordering to all messages, including jobs, sent to and between sleds. Because the rack is a distributed system, it does not give us the ability to assign a total ordering to messages.

This would have several consequences for the operator model of sush, which we ameliorate through additional mechanisms:

1. In reality, there may be more than one session at a given time on the rack, since a session could be created and used on either side of a network partition. We resolve this:
   • Two sessions can only coexist as long as they are unaware of one another. As soon as they meet, at most one survives.
   • If two sessions meet through gossip and one started causally after the other, the older session is terminated (this spreads, just like all other gossip, throughout the network).
   • If two sessions meet through gossip and they started concurrently, both are mutually annihilated, and a new session must be established, which will definitionally be in both of their causal futures.
2. The causal versions of the job-start messages are insufficient to ensure that jobs execute in the same linear sequence on every sled, and it's certainly insufficient to ensure that their order of execution matches the specified ordering by Oxide Support, because signed jobs could be submitted out of order to the rack, or even submitted concurrently to different sleds in the rack. We resolve this:
   • Each job's ID is the hash of the preceding job, or, if it is the first job, the hash of the session ID.
   • Knowledge of a job is insufficient to execute it on a sled; the sled must first also know about all the jobs that preceded it in the hash chain.
   • Jobs are started strictly in the order implied by the hash chain, though if specified, they may run concurrently to one another, and may not finish in the same order.

Bootstrapping the gossip network

A third, hidden emergent precondition of causal gossip is that we need to ensure all the causal versions originate from the same "universe of gossip". Rumors uses interval tree clocks to stamp its causal versions, and comparing two versions is meaningless unless they originated from some shared "seed" in time and space. Rumors enforces this: each of its peers declares a unique 128-bit nonce to identify its own causal universe, and refuses gossip with peers who do not share this identifier. A peer which is joining the network may either declare itself the seed, or bootstrap from another peer who is already joined.

Typical treatments of interval tree clocks require a single distinguished originating peer, but sush has no such asymmetry to rely on. We resolve this using the mechanisms in rumors:

• We bootstrap sush's gossip network at every cold boot of the rack by having every peer declare itself the seed, and then attempt to gossip with randomly selected other peers.
• At first, every such gossip will fail due to mismatched nonces.
• For each conflict, either side determines how to proceed based on the lexicographic comparison of its own (min_ticks, network), where min_ticks is the tallest causally ordered chain of events in its set of versioned messages, and network is the random nonce, used as a tie-break.

Because this comparison is anti-symmetric, each peer will agree on who wins the little game. The losing peer discards its local identity and messages, and attempts to bootstrap from the winning peer, joining its network. Provided that the sets of messages eventually quiesce during this bootstrap period (in practice, there will be zero messages during this time), the network quickly converges on a single winning nonce, with all peers causally related to the seed who happened to win. The lexicographic pair chosen for comparison is important: by embedding min_ticks as the winning comparator, we ensure that any new sled joining the existing network will deterministically lose and join the existing network — comparing the network alone would destroy the existing gossip set with a coin flip's probability on each late-joining sled's addition.

The takeaway: on a reasonably healthy cold-boot of the rack, i.e. one in which it is not split-brained from the get-go, the gossip network will extremely rapidly converge to a single causal universe, where all subsequent messages can be partially ordered against one another. Once a sled has booted and connected to the established gossip network, we can rely on it remaining a part of that same causal universe, unless it comes into contact with another partition with a greater min_ticks. In the case where a sled's partition has no messages in gossip, this takeover happens still, but we don't care because there's no data to care about losing.

The only worrisome residual case is one in which the rack cold boots split-brained: in this case, the halves of the split will establish stable, but independent, causal universes (they necessarily must!) and if separate support sessions are initiated each with one half of the split, those two causal universes of gossiped messages will each become non-empty. If and when the split is resolved — if it is resolved before another cold boot of the rack — those halves will collide, and the one with the lesser min_ticks will be obliterated. All records of all of its support sessions will be wiped from memory, and replaced with the winning universe's information. To emphasize, though: this is only possible if the split pre-exists and continues through a cold boot, and is only problematic if two simultaneous support sessions are initiated on either side of the split.

Enough preamble: how do we do it?

The original question, if you can recall back that far above this wall of text, is: how can we ensure jobs are executed at most once, no matter what? This is harder than it may seem.

At its heart, we may be flummoxed at first by the absence of reliable persistent storage: we cannot rely on the option of persisting the set of causal messages (or derived state), because jobs cannot be stored on the unencrypted M.2 drives (they could in principle contain confidential information), and we cannot rely on the presence of an unlocked trust quorum, so they cannot always be stored in the crypt dataset on some arbitrary U.2 drive. But without any form of local persistence, a rebooting or crashing sled would come back, rejoin the gossip network, and immediately attempt to re-execute all the jobs intended for it, from the start of the most recent session.

At first blush, we might think gossip can save us: sush does broadcast confirmation and status messages when it starts jobs, so perhaps a restarting peer can read back through history to learn whether it ran a job or not! Alas, we cannot rely on gossip remembering for us: we do not require gossip before executing a job (so that even a single sled is permitted to run sush), and even if we did, there's no guarantee that our status messages were preserved by gossip, since the sleds which happened to receive them might have crashed before distributing them to the sleds who remain.

The only way to definitively remember what we ourselves have done is to remember it ourselves. But where, and how?

• Where: we must use the M.2 drives, because they are the only storage we can rely on being available always.
• How: we must persist only metadata, never details of jobs or gossip messages, because the M.2 is unencrypted.

As a side-note, we must persist all data to both M.2 drives, and verify that our reads match (or that one drive is entirely missing our persistent state), to avoid situations where the intermittent or permanent failure of an M.2 drive changes our perceived persisted state. This is already implemented, and we deem it acceptable, because the M.2 is not a customer-replaceable part. If an M.2 fails in the field, sush will cease operating on that sled, with a diagnosable error, and the sled should be RMA'd.

Okay, so what metadata?

Let's build this up piece by piece. We'll call the state we're storing a Boundary because it's the boundary between what has been executed, and what has not.

Store the job ID

A natural starting point is to store the job ID of the last-launched job, which globally-uniquely identifies the job!

struct Boundary {
    last_executed: JobId,
}

Is this enough? Let's think: after a reboot, we rejoin gossip and begin receiving a stream of jobs, starting at the "beginning of time" from the perspective of the gossip set. If all we have is the last-executed job ID, we must not execute any of these jobs until we reach the specified job ID, at which point we can begin executing jobs as we were before (notably, we do not blindly execute jobs that we learn about after the boundary, since causal message ordering may contradict job sequence ordering — just as ordinarily, we execute sequentially only the jobs which hash-chain onto the boundary). Because jobs in a session are linearly totally ordered with respect to each other, the job ID is enough to tell us precisely where to draw the boundary. We picked up where we left off, hurrah!

End of story? Unfortunately, the qualifier "in a session" is ... ugh, I'll say it ... load-bearing. While jobs within a session are totally ordered with respect to one another, sessions are only partially ordered with respect to one another. This means that if there's a network partition, we could reboot and end up connected to a partition which holds an entirely distinct session. So long as the partition holds, we will never learn about our persisted last-executed job, and until we do, it's not safe for us to execute anything.

Store the session ID

So maybe we should store the session ID too:

struct Boundary {
    last_session: SessionId, // new!
    last_executed: JobId,
}

What do we do when we find our stored session ID mismatches the most-current one in the partition we've joined? Well, our job ID is irrelevant for this session, so we can discard both, and continue executing everything in this session...

...but then suppose we reboot again, and this time we rejoin the partition holding the original session where our first-stored job ID originated. Now we don't know about it! And by the same rule, we'd gladly discard the session ID and the job ID from the other session, and start executing jobs from our original session. Yikes!

It is now our mission to shield ourselves from the flip-flop.

Store every job ID and session ID

The core of this problem is that we overwrote our state from side A when we joined side B, which caused us to replay jobs from side A when we eventually rejoined it. A simple solution would be to never overwrite information, instead storing all the session/job pairings we learn about. So then:

type Boundary = BTreeMap<SessionId, JobId>;

Then, the same sequence plays out with no damage done: we can flip to a new session (over a reboot), start executing new jobs from it, record the per-session job ID boundary, and then flop back to the original session (over another reboot), and resume executing precisely where we left off.

The only (big) downside is that for safety, we can never evict entries from our mapping, or else we risk replay.

Never, you say? But there's only 32 sleds in the rack! Shouldn't that mean we can only ever track 32 sessions?

Ah, but dear reader, alas! A sled can always power-cycle and get a new session, which means over time, there is no bound to the number of entries in our map! What's more, we don't know which ones to evict, because a session that is observed to have been superseded in one partition may not yet have received the bad news in another...

Store only one job ID and session ID... but also store the session's version

But what if we knew which sessions superseded one another? After all, while sessions are not totally ordered, they are partially ordered. We already use this to great effect to maintain the partial illusion of "one session per rack"; can we use it here?

Indeed, suppose we do this:

struct Boundary {
    last_session_version: Version, // new!
    last_session: SessionId,
    last_executed: JobId,
}

Now let's run the flip-flop again: when our poor sled reboots from side A to side B, it now knows the casual version of session A's start-message, which I'll gloss as "A's version" hence. We now have a case analysis on B's version:

• If B > A, then B supersedes A and we should join B and replace our durable state with that for B
• If B < A, then A supersedes B and therefore we already witnessed the end of B in our past life, now memorialized by our boundary state — so we may participate in gossip with B, but we must never run a job there, and leave our state untouched
• If B || A, then the two sessions are dead men walking: they will mutually annihilate as soon as they encounter one another, and the only safe disposition is to gossip with B but never run a job there, and leave our state untouched
• B cannot equal A, because no messages in the causal gossip universe can have equal versions

Now the flip-flop doesn't have symmetry: if B > A, we'll never run another job in A, so our re-run risk is nil. If B < A or B || A, we never ran jobs in B, and we never rewrote our state, so we can continue onwards in A.

We also need the rule that if we're "sitting out" a session because it was causally prior or incomparable to our stored session's version, we should re-evaluate this each time a new session shows up via gossip: if it's causally posterior to our stored session, we run the same case logic and determine to join it.

This solution uses fixed space, unlike our last one, and all it sacrifices is that sleds which reboot across a partition will not run jobs until the partition is unified. I actually think that this is a desirable property, worth restating:

That's what we're doing here, and it makes things work out very cleanly.

Aren't you forgetting something?

At the beginning of this screed, I described how everything works out so cleanly and nicely if we can manage to bootstrap the rack into a state with a single shared causal universe. But what if we can't? What if the rack cold-boots split-brained, or, equivalently, we add sleds and they cannot connect to the whole network, creating a partition that has never touched the extant gossip network? Unfortunately, sush cannot throw up its hands. We must work here, too.

Let's pull another flip-flop, this one about causal universes, not sessions. You see where this is going, right? We don't record the causal universe, so if we reboot-flip a sled into a partition in another causal universe, its causal comparisons with the sessions in that universe are totally meaningless — comparing versions from two universes is not even a valid question.

Let's add another field:

struct Boundary {
    last_network: Network, // new!
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

This way at least we know when we've got a mismatch! But we're still having a bad time, because unlike sessions, networks aren't even (meaningfully) partially ordered: they can only be compared for equality because they're random nonces.

The particularly studious reader may recall something interesting from our preamble: we have already crafted a deterministic procedure for resolving conflicts between networks — the anti-symmetric comparison we use for gossip bootstrap: compare their min_ticks, then compare their identifiers, as a tie-break. Could we use that here?

I thought so, and then it turned out that it doesn't really work. Imagine we did this:

struct Boundary {
    last_network_version: Version, // tentatively?
    last_network: Network,
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

You could imagine that every time we update the boundary on disk, we capture the causal frontier version of our gossip set, allowing us, when transplanted into another universe, to decide whether our previous universe is going to dominate this one, whensoever they collide in the future. Could we use that to select whether or not to join the new universe and start executing jobs there?

Sadly, no, not safely: in a persistent split-brain, the two partitions continue onwards indefinitely, which means that the determination of which universe dominates is not stable: it can slosh back and forth as messages land in either side's gossip set. Such universe-sloshing is transient and benign at the moment of bootstrap in a healthy rack, because everything immediately converges on a single causal universe before even one support session could be initiated, no less two. But if we allowed a sled to adopt itself into the other side of a partition based on the min_ticks count of one side dominating, two concurrent support sessions on either side of the split could drive the relative min_ticks counts back and forth, inducing precisely the flip-flop effect we're trying our darnedest to stamp out.

Store every network's boundary

When we were faced with a similar problem on the level of sessions, we tried at first to resolve it by storing a map from session to boundary (which was then just a singular job ID). There, we improved by using causality to our advantage. Here, we have no such hope because causal universes are unordered entirely from one another. But could we still do the map approach?

type Boundaries = BTreeMap<Network, Boundary>; // new!

struct Boundary {
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

Sure, but then we have to persist every network we've ever seen forever. Discarding one isn't safe, and for the same reasons as elucidated above for sessions, there's no finite bound to the number of networks that occur over time, and we have no way to locally tell when one no longer exists anywhere in the rack. Dropping anything from the map leads to a probability that we could, in this very specific flip-flop type scenario (which, please note, is a minimal exemplar of a family of situations), re-execute a job.

Maximum growth of this proposed grow-only file is something on the order of a kilobyte per sled reboot, forever, so call that 32 sleds times once per minute, on the top end, if things are going wrong very fast, everywhere. That's almost 50 gigabytes on the world's worst weather day for the rack. Even at a tenth or a hundredth that growth, it's not acceptable for the M.2.

The least worst option

Let's zoom out for a second. At this point, we have designed a set of mechanisms which almost protect us from job re-execution in almost every possible scenario. But not all! And we really want the system to fail closed, because the fail-open behavior means that just the wrong reboot behavior during a particular shape of network partition could lead to re-executing an entire session's worth of jobs on an arbitrary number of sleds. This could drive the rack into an unsupported state, without operator intervention. We do not want this.

But... precisely when can it happen? All this needs to be true:

1. There is a network partition which has existed from the moment one half of the partition has booted (either the rack booted split-brained, or a set of sleds rebooted into a partition from the rest of the rack). This "from boot" requirement is necessary to trigger the distinct irreconcilable causal universes.
2. There is a live support session on both sides of the partition.
3. At least one job addressed to a sled is submitted on the side of the partition it starts on.
4. The sled shuts down (or sush crashes), reconnects to the other side of the partition while down, then comes back up.
5. At least one job addressed to the sled is submitted to it while it's on the other side of the partition.
6. The sled shuts down again (or sush crashes again), and reconnects back to the other side of the partition while down, then comes back up.

It's possible! It's even possible, though unlikely, in the absence of malfeasance. We must handle this case, I believe. But must we handle it with grace?

Outcomes I don't accept:

• The affected sled is permanently unable to accept any new jobs, forever, and the operator cannot fix this. (if we decline to participate in the other network, we could be locked out forever if the partition resolves and that network becomes the only one.)
• The sled re-plays jobs it has already executed. (This would happen if we did the simple thing and replaced the state when moving networks.)
• We blow up the entire gossip network and start everything from scratch. (This is possible to do, but the details get fiddlier the more I write them out, and I have a better idea, below, that's much less destructive.)

Outcomes I can live with (surprisingly — and only because of the unlikelihood of the situation):

• The sled fails to execute any prior jobs which were addressed to it, including those which were submitted after the last job it executed, skipping forward to the present moment and accepting new jobs after this point. This notably violates our otherwise-sacrosanct linear-chain invariant for sessions, but I think it is the least-worst solution to this problem. I welcome dispute! Below, I explain how this could work.

But how? There are two problems here:

1. Detection: How do we know that we've been universe-flip-flopped?
2. Actuation: How do we reliably cause the sled to fail to run all prior jobs addressed to it, while accepting any jobs submitted after the moment it makes this cutover?

Detection

Recall the Boundary state we landed on:

struct Boundary {
    last_network: Network,
    last_session_version: Version,
    last_session: SessionId,
    last_executed: JobId,
}

The problem solved by the last_session_version is establishing a directed edge between sessions, so we can't flip-flop between them: we only move one way along the directed edge, from earlier versions to later ones (and we park at concurrent ones until the partition heals).

We can't do quite the same maneuver for causal universes, because they don't have any inherent ordering between them, and because universe-sloshing due to min_ticks means there's no deterministic choice based on current state, either. But we can establish an arbitrary directed edge, written at the time we traverse it.

All credit to @plotnick for this final keystone in the solution: in addition to the boundary struct above, we track a Bloom filter which represents the set of all past networks we've left behind. If we receive a job request meant for us which we would actually execute (i.e. the session is live and latest):

1. We check the current gossip network against the one in our boundary file: if they match, all done.
2. If they don't match, check the Bloom filter for this network.
   • If there's a hit (and we can size it so that false positives are negligible), we do not execute the job, we instead log an error in the gossip set indicating that we are locked out due to a universe flip-flop (or more operator-legible language, ideally). Then, we proceed to the next section and "actuate" — that is, we cause ourself to permanently transition so that previous jobs addressed to us will not get executed by us, but future jobs addressed to us will. How?? Read on.
   • If there's no hit, mark our previous network identifier from the boundary file in the Bloom filter now, durably on disk, then overwrite the boundary file with information about the current network, session, and job, and execute the job, then continue on normally.

It's important that the flip-flop reset only engages when we actually would have potentially re-executed a job, so that it does not engage during normal initial bootstrap of the gossip network, when it's expected that there are no messages at all — or at most, one causal universe of messages from a single support session. If we triggered the reset on every universe flip-flop, with no need for actionable message content, we'd reset during every bootstrap. This is the maximally liberal check which still prevents the re-execution failure.

Actuation

Okay, so we detected and prevented the universe flip-flop, but now we've locked out a sled from executing jobs. If we didn't do anything about this, it's a coin-flip whether after the partition heals, it will be permanently locked out, or allowed back. We must allow it back, but safely. Here's how:

When the sled logs an error to the gossip set, at that instant, it captures the version of the frontier of the gossip set (which is equal to the version of the error message it just injected). This version marks a unique point in causality: every job submitted strictly in its future light-cone cannot possibly have originated prior to the moment in real-life linear time when the sled discovered the flip-flop. As a consequence, it is safe to execute any job which has a version strictly in the causal future of this moment. It skips executing each job which is concurrent to or in the causal past of this safe threshold, which will potentially skip it forward in time past jobs that it otherwise would have been scheduled to run. It should probably log errors for each of those, for visibility.

In brief: this mechanism causes a sled that is flip-flopped across the boundary of a universe partition to skip running any jobs which were queued for it to run while it was "out of universe", and pick up past the point it returned to.

Some more notes: this is almost, but not quite, Claude's earlier suggestion to track the causal frontier of the gossip set at network join, and filter out jobs that aren't in its causal future. This suggestion feels superficially similar but fails to achieve our goals:

1. It means that jobs queued before a reboot are skipped after a reboot.
2. It does not protect us from re-running jobs that exist in the causal future of whichever potentially out-of-date sled we happen to connect to on first resumption of gossip.

By contrast, this solution generates a unique local point in causality space by capturing the version of a locally originating message, which guarantees that this is "fresh" and nothing else in the gossip set could possibly be in its future, thereby solving (2) above. It also only engages precisely where it needs to, to prevent replay of jobs, and otherwise permits a sled to learn about jobs queued for it upon a reboot, executing them normally, thereby solving (1) above.

A final note: I believe that it might be possible to do away with the Bloom filter construction and simply detect universe mismatches and immediately trigger the skip-to-my-own-lightcone resolution. There are corner cases with keeping it, and corner cases with not keeping it. I would potentially want to err on the side of the simpler construction, but we should think through it together.

In conclusion

Thank you for coming to my TED talk!