predictable ordering
In your problem Specifications you included
- if a burst of high priority messages is sent, they should not completely starve lower priority messages (in this regard "priority" is more a QoS level)
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.
Two priorities, {low, high}, suffice for discussing this. Suppose we see a random mix of the priorities offered by a Poisson process, with lambda low enough that the queues sometimes drain entirely, so we have idle capacity. In a traditional priority setup we would expect this invariant to hold:
- A low priority task will never be dequeued when a high priority task is available.
This extends naturally to using a great many priority values.
Subject to the requirement above that we sometimes have idle capacity, we never completely starve low priority tasks. This suggests that OP uses "starve" in some different way which aligns to business requirements, perhaps in trying to meet a Throughput or a 98th percentile Latency SLA. It may also suggest the input distribution corresponds to clients executing a {submit request, await response, repeat} loop rather than memoryless Poisson arrivals.
I propose an alternate specification, simpler than in OP, which is meaningful to both end users and implementors.
A traditional priority setup can be implemented as a
heap,
with submission timestamps ts that are fine-grained enough to induce a
happens-before
relationship between submitted tasks.
We insert the tuple (-prio, ts) into the queue,
with a value of the task.
(I negate to finesse the sort order.)
The invariant on dequeues of high priority tasks
is that they pop out in ts order, and a similar
invariant holds across low priority tasks.
Sadly they can be starved during a high priority burst.
Suppose both task types always take exactly 100ms to process, and lambda is low enough that at least once a minute we go idle. Now, for ten seconds, we add a (non-Poisson) busy client that injects eleven high priority tasks per second. During this interval and for a brief recovery period afterward, we will see zero low priority dequeues, which seems "unfair". Let's fix that.
Define a fairness parameter, a gran scheduling granularity of, say, 2s.
Associate epoch = int(ts / gran) * gran with each arrival,
so we might see epochs of noon, 12:00:02, 12:00:04, ...
For each arrival, insert an (epoch, -prio, ts) tuple in the queue.
Now we're saying that, within each epoch, the traditional
invariants hold. But if we fail to clear the queue by end of epoch,
newly arriving low priority tasks will get an opportunity to run.
All tasks from prior epochs will run to completion before
we tackle a new epoch.
If that ten-second busy client was going through a {submit, await, repeat} loop, then the "await" stage would start seeing larger delays, reducing its offered load.
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.
Define expected task-per-second arrival rates of lo_rate and hi_rate.
Measure the lo_actual and hi_actual rates with smoothed moving
average, perhaps using the same exponential decay approach
seen in unix uptime.
When things are "normal", when the actual arrival rate is sane,
we insert (-prio, ts) into the queue in the usual way.
During an overload period we randomly knock down high priorities.
Based on rolling a random number, turn priority 2 into 1,
with increasingly higher probability when hi_actual
is increasingly higher than hi_rate.
drop policy
Every physically realized system attached to the internet will drop requests at some point, as offered load can always be ratcheted up. It's just a matter of deciding where the drops should happen and whether you want to be in charge of them.
Consider specifying and authoring such a policy layer which front-ends your queueing layer. Then your queues can confidently plan on never seeing an arrival rate above R, if that is enforced by policy.