Return to Answer

retrofit

Given an existing simple priority queue, e.g. rabbitmq, you could easily retrofit it with approximately the same epoch behavior.

Allocate a (zero-origin) vector of queues. Define index active_queue = 0, where new arrivals always go. We can always find alternate_queue as 1 minus that. Define current_epoch according to gran and a recent timestamp.

New arrivals are thrown into the active queue in the usual way, and the alternate queue is empty.

At some point we notice that we need to update current_epoch to a subsequent epoch, and we follow this procedure:

1. Unconditionally assign current_epoch to be current.
2. Ask whether the alternate queue is empty. Iff empty, toggle the active queue to use it, via active_queue = 1 - active_queue.

So at start of each epoch, leftover jobs from previous epoch(s) are being processed in the alternate queue. If we are lightly or moderately busy, we toggle which queue shall be the active one exactly once per epoch.

If we're getting behind, some leftovers will languish in the alternate queue for more than gran seconds, and we don't toggle. Hence the active queue depth becomes unusually large. At some point the alternate queue drains, the epoch ticks over, and at last we toggle. Since there's an unusually large number of leftovers that may be from multiple epochs, it may take multiple epochs for the alternate queue to drain, even if offered load suddenly goes to zero. As offered load tapers down, so will queue depths, and eventually we go back to toggling once per epoch.

In this way we ensure that newly arriving high priority tasks cannot starve ancient low priority ones.

which would fit in better with Desiderata, as it is on the vague side. We don't have numbers on "burst" and "starve", and it's unclear how to evaluate whether some historic activity trace is correct or not. I will assume infinite queue capacity, and that in the long-term offered load is less than server capacity, perhaps due to a throttling layer that precedes our queueing layer or perhaps due to ability to scale out with unlimited budget VM spawning.

which would fit in better with Desiderata, as it is on the vague side. We don't have numbers on "burst" and "starve", and it's unclear how to evaluate whether some historic activity trace is correct or not. I will assume infinite queue capacity, and that in the long-term offered load shall be less than server capacity, perhaps due to a throttling layer that precedes our queueing layer or perhaps due to ability to scale out with unlimited budget VM spawning.

Here's a stochastic alternative.

deadline approach

Another way to describe fairness is to look at service deadlines, perhaps retaining that gran interval. For arrivals of either priority, we typically expect they will be dequeued within gran seconds. Define "starvation" as blowing that deadline.

During a period of starvation where low priority dequeues happen more than gran seconds after enqueue, reduce the priority of new arrivals. So an incoming priority of 2 would be reduced to 1, and low priority arrivals would be unchanged.

We focus on time spent in the queue, something this layer exercises control over, since in general the task execution times could have a long tailed distribution.

Here's a stochastic alternative.