Fairness algorithm design: DRR vs WFQ/SFQ, aging, and high-cardinality keys

[cognis-digital]

safequeue's scheduler package implements Deficit Round Robin (DRR) (Shreedhar & Varghese, 1996) for per-tenant fairness: each key has a FIFO backlog and a weight, and the round-robin ring grants quantum × weight credit per visit, carrying leftover deficit forward for backlogged keys and resetting it when a key goes idle (so an idle key can't hoard credit and burst on return). This gives weighted, work-conserving fairness with no starvation — see docs/ARCHITECTURE.md.

I'd like to open the design up before we build the next layer. Some questions:

1. Is DRR the right primitive, or should we offer alternatives?

• WFQ / SFQ (start-time fair queuing) gives tighter delay bounds than DRR but needs a virtual-time computation per item. Worth it for latency-sensitive tenants?
• Stochastic Fair Queuing hashes keys into a fixed number of buckets — bounds memory when the key cardinality is unbounded (e.g. per-user), at the cost of occasional collisions. Do we need this for high-cardinality fairness keys?

2. Aging / priority interaction.
Today priority (in the durable core) and fairness (in the scheduler) are separate layers. Should fairness be priority-aware (fair within a priority band), or should they stay orthogonal? A concrete use case: a low-weight tenant with an urgent high-priority item.

3. Dynamic weights.
SetWeight is available but weights are static per call. Is there demand for feedback-driven weights (e.g. shrink a tenant's weight as it exceeds a quota)?

4. Fairness key cardinality.
DRR keeps one backlog per active key. For millions of ephemeral keys this is unbounded memory. Options: cap active keys + spill, SFQ-style hashing, or document it as the caller's responsibility. Preferences?

Interested in real workloads: how many distinct fairness keys do you expect, and what's your tolerance for delay vs strict throughput fairness?