The queue that cannot tell time

Our edge runtime finally got a priority queue for guest jobs, and the most important design decision was a refusal: no clocks allowed.

The first sketch of this queue had a bug, and I caught it before it shipped. Ties between same-priority jobs were broken by enqueue timestamp. On one machine that is obviously fine. On a mesh of islands with unsynchronized clocks, it means two islands can enqueue the same jobs in the same order and still disagree about which one runs first. Eleven milliseconds of clock skew, and the schedules diverge.

That version never shipped. What shipped instead is a queue that cannot tell time at all. It has no clock. It has a counter.

The missing piece

Rewind a week. The sandbox crate knew how to do almost everything a job needs. Job::load takes guest module bytes under the 10 MB cap. invoke runs an export. The admit gate checks the VDF receipt before anything runs. The fixed-block pool hands out memory. Everything except the obvious: nobody decided which job goes next.

A job's life was load, then invoke, in whatever order the caller happened to call. That works while one caller runs one job. The issue tracker had carried the gap for a while as item #39, "implement job priority queues," and the mesh was growing past the point where call order is a scheduling policy. Consensus work and relay handoffs needed to jump the line ahead of background sync. So the queue got built.

Why the clock had to go

The naive priority queue orders by (priority, timestamp). Ties go to whoever arrived first, and arrival time comes from the system clock. Every scheduler textbook does this. Every scheduler textbook assumes one machine.

MossyMesh does not have one machine. It has islands that disconnect, work alone, and merge later, and the merge only converges if both sides made the same decisions from the same inputs. That is the determinism SLA the whole project is built around. Now picture two Normal-priority jobs landing on two islands in the same causal order. Island A's clock runs 11 ms ahead of island B's. Both islands stamp their own arrival times, both break the tie "correctly" by their own clocks, and they pick different winners. Same inputs, different schedules, and the merge now has to reconcile a disagreement that never needed to exist.

The rule that fell out: never order by wall-clock when two machines must agree. Order by something both machines derive identically. The queue assigns each ticket a sequence number when it is pushed. The number is a logical clock. It only ever goes up, and it is identical on every island that saw the same pushes in the same order. First-in, first-out (FIFO) within a priority class becomes a pure function of call order, which is exactly the thing both islands share.

The diff

The whole module is sandbox/src/sched.rs, about 330 lines with tests. Four priority classes, one ticket struct, one queue. Here is the real code from the fix, starting with the ordering itself:

// sandbox/src/sched.rs
pub struct JobTicket {
    pub id: u64,        // caller-owned job id; the worker resolves it
    pub priority: JobPriority,
    pub seq: u64,       // assigned by the queue at push time
}

// BinaryHeap is a max-heap: the "greatest" ticket pops first.
impl Ord for JobTicket {
    fn cmp(&self, other: &Self) -> Ordering {
        self.priority
            .cmp(&other.priority)
            .then_with(|| other.seq.cmp(&self.seq))  // oldest first
            .then_with(|| self.id.cmp(&other.id))
    }
}

Read that middle line twice. other.seq.cmp(&self.seq) looks backwards until you remember the heap is a max-heap: the greatest element pops first, so "greatest" has to mean the smallest sequence number. Oldest first. One reversed comparison is the entire FIFO guarantee.

The queue holds tickets, not jobs, and that was the second deliberate refusal. A loaded Job can own up to 10 MB of module bytes. Queue 256 of those directly and the scheduler is silently holding 2.5 GB on a box that has 10 MB of ledger budget. So the queue holds three small integers per entry and the worker keeps the id-to-job table. A full queue is a few kilobytes. Scheduling stays O(log n) and memory stays flat no matter what gets submitted.

pub const MAX_QUEUE_LEN: usize = 256;

pub fn push(&mut self, id: u64, priority: JobPriority)
    -> Result<JobTicket, SchedError>
{
    if self.heap.len() >= MAX_QUEUE_LEN {
        return Err(SchedError::QueueFull);
    }
    let ticket = JobTicket { id, priority, seq: self.next_seq };
    self.next_seq = self.next_seq.wrapping_add(1);
    self.heap.push(ticket);
    Ok(ticket)
}

The bound is the third refusal. Push past 256 and you get QueueFull, loudly, at the edge. The alternative is the unbounded queue, which never says no and then OOMs the worker at 3 AM. I will take the error I can see over the crash I cannot predict. Even a Critical ticket cannot jump a full queue. Backpressure is honest or it is not backpressure.

Same pushes, same order, two tiebreaks. Timestamps inherit clock skew, so the islands diverge on which Normal job runs first. Sequence numbers are assigned by the queue itself, so every island that saw the same pushes agrees. Below: one drain of mixed priorities, Critical first, FIFO inside each class.

What the embedded folks say

I took the design to Reddit before writing it up, the usual protocol: ask Reddit Answers, read the threads it cites, then skim the comments myself. All three threads that mattered were on r/embedded, and the practitioners there had already fought every version of this fight.

On passing descriptors instead of payloads through queues, one commenter in the timer-driven priority queue thread put it plainly: a heap of pointers is the sensible shape, and the moment you start allocating and freeing nodes inside the structure you buy yourself memory fragmentation and jitter. That is the ticket design in one sentence, from someone who learned it the expensive way. Our version is stricter: the queue never even sees the bytes, so there is nothing to fragment.

On the clock problem, the FreeRTOS delays thread had the line I keep coming back to. Paraphrased: the time you calculate is always going to be wrong, because the queue either times out, in which case it was correct, or a command arrives first and it waited less than a tick period. Their fix was the same shape as ours: keep an explicit deadline variable and recompute the remaining time from a monotonic tick counter instead of trusting accumulated wall-clock. Different mechanism, same instinct. Do not let the clock do the ordering.

And on priority inversion, the I2C bus war story: a low-priority temperature sensor task grabbed a shared bus mutex, a high-priority task blocked on it, and a medium-priority task ran to completion in between because nothing told it to wait. The practitioner's kicker, paraphrased: that low-priority task is low priority for a reason, and when it runs or how long it takes is unpredictable. Our queue does not solve inversion, and I am not going to pretend it does. Mutexes with priority inheritance solve inversion. A scheduler just decides who waits, and it should do that predictably.

The unfairness we kept

Strict priority has a known failure mode and its name is starvation. If High tickets keep arriving, Low tickets never pop. I documented that in the module docs as a deliberate choice, not an oversight, because the alternative has its own failure mode: aging and fairness heuristics make the schedule harder to audit, and on this mesh, predictable beats fair. A worker that can explain exactly why job 7 ran before job 12 is worth more than a worker that is fair in a way nobody can reconstruct.

The honest extension is aging driven by the dequeue counter: every N pops, promote the oldest waiting ticket one level. Deterministic, clock-free, fair-ish. It is not in this change. The queue is strict, the docs say it is strict, and the day starvation bites a real deployment, the counter-based aging is the first thing to try. I would rather ship the predictable version and name its flaw than ship the clever version and discover its flaw.

TAKEAWAY // WHAT THE FIX TEACHES

Never order by wall-clock when two machines must agree. Order by (priority, sequence), where the sequence is assigned by the queue itself.
Schedule descriptors, not payloads. A ticket of three integers cannot OOM an edge box; a queued job holding 10 MB of module bytes can.
Bounded queues fail loudly. QueueFull at push time beats an unbounded heap that dies at 3 AM.
One reversed comparison can be the whole FIFO guarantee. Read other.seq.cmp(&self.seq) twice.
Document the unfairness you chose. Strict priority starves low-priority work; saying so in the docs beats discovering it in a postmortem.
Keep the scheduler single-owner. Sharing the queue across threads reintroduces the interleaving nondeterminism the ordering was built to avoid.

The r/embedded threads are worth your time if you build schedulers: the timer-driven priority queue discussion, the FreeRTOS delays and queues thread, and the priority inversion war stories. Practitioners first, as always.

The change is on main as 9b85c81a: new sandbox::sched module, eight unit tests, full workspace suite green at 529 passed. The aging design is still open. If you have a clock-free fairness scheme that keeps the schedule auditable, the issue tracker is listening.