Priority Queue

Every queue up to this point held a single kind of job, and consumers took whatever was next without distinguishing it. Jobs entering the same system are not each other’s equals: the carrier’s state event shows up on the recipient’s tracking page and its delay is felt directly; the end-of-day billing record has until morning; the seller’s report job can wait for either. When the previous lesson’s backlog of 525,000 jobs is treated as a single queue, all three wait the same three hours.

This lesson turns the queue itself into a decision. Here, a priority queue is a service-level decision: choosing which job goes ahead of which by looking at its work class. The Data Structures curriculum uses the same English term for a data structure — a heap-based structure that returns the smallest element by key. The two are separate things, and this lesson does not cover the data structure; it measures the capacity cost of the decision.

Three Classes and One Capacity

The measurement window is K01’s V10 assumption: four hours. Three classes enter the window, and all three rates come from K01.

A — state event. 97.22 jobs/s (K01’s peak write rate, via the V8 multiplier). Service level: shows up on the recipient’s tracking page, its wait must be short.

B — billing record. 833.33 jobs/s (K01’s batch job scan rate). Service level: its individual wait does not matter, but it must finish by the end of the window.

C — report job. A hundred reports, each 3,000 records — a size derived from K01 in the previous lesson. Service level: must finish sometime during the day.

The unit of work is one record processed, so all three classes share the same unit. Their combined requirement is 951.39 jobs/s. Capacity is an assumption:

K6 — capacity of the shared consumer group: 900 jobs/s. This is this course’s own assumption and is not added to K01’s table. Rationale: the group was sized to the end-of-day job’s requirement (833.33 records/s) with a small margin, and the event stream and report jobs were added to it later. Its sensitivity appears at the end of the output.

The three classes fully overlapping is the worst case; separating their windows is a design decision that removes this lesson’s problem, and the measurement shows that decision’s value.

Three policies are compared: single queue, which takes jobs in arrival order; strict priority, which gives capacity to A first, the remainder to B, and what is left to C; weighted share, which reserves a fraction of capacity for each class (A 0.15, B 0.75, C 0.10) and passes unused share to the others in order. In the fourth and fifth runs, the previous lesson’s spike is added to A: four times its rate for twenty minutes.

// priority/work-class.mjs — three work classes sharing the same consumer group: single
// queue, strict priority, and weighted share. MODEL: a tick is one second, the work
// unit is one record processed. Results are deterministic (calculation class) and
// machine-independent.
const WINDOW = 4 * 3600;           // K01 assumption V10: end-of-day job window
const A_RATE = (2_800_000 / 86_400) * 3;   // K01 + V8: peak write events/s
const B_RATE = 833.3333;           // K01: batch job scan records/s
const C_COUNT = 100, C_SIZE = 3000;   // report jobs: 3000 records each (lesson 02)
const K6 = 900;                    // this course's assumption K6: shared group capacity (jobs/s)

class Queue {
  constructor() { this.buf = []; this.head = 0; this.backlog = 0; this.arrived = 0; }
  add(t, n) { if (n > 0) { this.buf.push({ t, n }); this.backlog += n; this.arrived += n; } }
  headTime() { return this.head < this.buf.length ? this.buf[this.head].t : Infinity; }
  take(t, s) {
    let remaining = s;
    while (remaining > 1e-9 && this.head < this.buf.length) {
      const batch = this.buf[this.head];
      const taken = Math.min(remaining, batch.n);
      batch.n -= taken; remaining -= taken; this.backlog -= taken;
      this.totalWait = (this.totalWait ?? 0) + taken * (t - batch.t);
      this.completedJobs = (this.completedJobs ?? 0) + taken;
      if (t - batch.t > (this.longestWait ?? 0)) this.longestWait = t - batch.t;
      if (batch.n <= 1e-9) this.head += 1;
    }
    return s - remaining;
  }
}

function run(policy, capacity, aMultiplier) {
  const q = [new Queue(), new Queue(), new Queue()];
  const SHARE = [0.15, 0.75, 0.10];
  for (let t = 0; t < WINDOW; t += 1) {
    const burst = aMultiplier > 1 && t >= 3600 && t < 3600 + 1200;
    q[0].add(t, A_RATE * (burst ? aMultiplier : 1));
    q[1].add(t, B_RATE);
    if (t % Math.floor(WINDOW / C_COUNT) === 0) q[2].add(t, C_SIZE);
    let remaining = capacity;
    if (policy === "single-queue") {
      while (remaining > 1e-9) {
        const i = [0, 1, 2].reduce((a, b) => (q[b].headTime() < q[a].headTime() ? b : a), 0);
        if (q[i].headTime() === Infinity) break;
        remaining -= q[i].take(t, Math.min(remaining, q[i].buf[q[i].head].n));
      }
    } else if (policy === "strict-priority") {
      for (const i of [0, 1, 2]) remaining -= q[i].take(t, remaining);
    } else {
      for (const i of [0, 1, 2]) remaining -= q[i].take(t, Math.min(remaining, capacity * SHARE[i]));
      for (const i of [0, 1, 2]) remaining -= q[i].take(t, remaining);
    }
  }
  return q;
}

const LABEL = ["A state event", "B billing", "C report"];
console.log(`window ${WINDOW} s (V10), capacity K6 = ${K6} jobs/s`);
console.log(`required rate = ${((A_RATE * WINDOW + B_RATE * WINDOW + C_COUNT * C_SIZE) / WINDOW).toFixed(2)} jobs/s\n`);
for (const [label, pol, cap, mult] of [["single queue", "single-queue", K6, 1], ["strict priority", "strict-priority", K6, 1],
  ["weighted share", "share", K6, 1], ["strict priority + A burst", "strict-priority", K6, 4],
  ["weighted share + A burst", "share", K6, 4]]) {
  console.log(`${label} (capacity ${cap})`);
  console.log("  class             arrived  completed  completed/arrived  avg. wait(min)  longest(min)  remaining backlog");
  const queues = run(pol, cap, mult);
  for (const [i, qu] of queues.entries()) {
    const completed = qu.completedJobs ?? 0;
    console.log(`  ${LABEL[i].padEnd(16)} ${qu.arrived.toFixed(0).padStart(8)} ${completed.toFixed(0).padStart(9)} ` +
      `${(completed / qu.arrived).toFixed(3).padStart(13)} ${((qu.totalWait ?? 0) / Math.max(completed, 1) / 60).toFixed(1).padStart(17)} ` +
      `${((qu.longestWait ?? 0) / 60).toFixed(1).padStart(12)} ${Math.max(0, qu.backlog).toFixed(0).padStart(14)}`);
  }
  const total = queues.reduce((a, qu) => a + Math.max(0, qu.backlog), 0);
  console.log(`  total remaining backlog: ${total.toFixed(0)}\n`);
}

const required = (A_RATE * WINDOW + B_RATE * WINDOW + C_COUNT * C_SIZE) / WINDOW;
console.log(`shortfall = (${required.toFixed(2)} - ${K6}) x ${WINDOW} = ` +
  `${((required - K6) * WINDOW).toFixed(0)} jobs; same in every policy`);
console.log(`closing the shortfall: capacity ${K6} -> ${required.toFixed(2)} jobs/s (x${(required / K6).toFixed(3)}) ` +
  `or window 4.00 -> ${(4 * required / K6).toFixed(2)} h (V10)`);
console.log("K6 sensitivity (weighted share, total remaining backlog):");
for (const cap of [850, 900, 950]) {
  const total = run("share", cap, 1).reduce((a, qu) => a + Math.max(0, qu.backlog), 0);
  console.log(`  capacity ${cap} -> ${total.toFixed(0)}`);
}

window 14400 s (V10), capacity K6 = 900 jobs/s
required rate = 951.39 jobs/s

single queue (capacity 900)
  class             arrived  completed  completed/arrived  avg. wait(min)  longest(min)  remaining backlog
  A state event     1400000   1324264         0.946               6.5         13.0          75736
  B billing        12000000  11350736         0.946               6.5         13.0         649263
  C report           300000    285000         0.950               6.5         12.9          15000
  total remaining backlog: 740000

strict priority (capacity 900)
  class             arrived  completed  completed/arrived  avg. wait(min)  longest(min)  remaining backlog
  A state event     1400000   1400000         1.000               0.0          0.0              0
  B billing        12000000  11560000         0.963               4.4          8.8         440000
  C report           300000         0         0.000               0.0          0.0         300000
  total remaining backlog: 740000

weighted share (capacity 900)
  class             arrived  completed  completed/arrived  avg. wait(min)  longest(min)  remaining backlog
  A state event     1400000   1400000         1.000               0.0          0.0              0
  B billing        12000000  11260000         0.938               7.4         14.8         740000
  C report           300000    300000         1.000               0.3          0.6              0
  total remaining backlog: 740000

strict priority + A burst (capacity 900)
  class             arrived  completed  completed/arrived  avg. wait(min)  longest(min)  remaining backlog
  A state event     1750000   1750000         1.000               0.0          0.0              0
  B billing        12000000  11210000         0.934               9.5         15.8         790000
  C report           300000         0         0.000               0.0          0.0         300000
  total remaining backlog: 1090000

weighted share + A burst (capacity 900)
  class             arrived  completed  completed/arrived  avg. wait(min)  longest(min)  remaining backlog
  A state event     1750000   1750000         1.000               3.5         18.1              0
  B billing        12000000  10910000         0.909              12.0         21.8        1090000
  C report           300000    300000         1.000               0.3          0.6              0
  total remaining backlog: 1090000

shortfall = (951.39 - 900) x 14400 = 740000 jobs; same in every policy
closing the shortfall: capacity 900 -> 951.39 jobs/s (x1.057) or window 4.00 -> 4.23 h (V10)
K6 sensitivity (weighted share, total remaining backlog):
  capacity 850 -> 1460000
  capacity 900 -> 740000
  capacity 950 -> 20000

Single Queue Is Fair and Wrong

In the first block, all three classes’ numbers are nearly identical: completion ratio 0.946 / 0.946 / 0.950, average wait 6.5 minutes for all three, longest wait 13.0 minutes. The single queue treats them equally.

The cost of that equality is that the classes’ service levels are not equal. The state event shown on the recipient’s tracking page waits 6.5 minutes; the billing record, which has until morning, waits the same 6.5 minutes. The single queue harms no class and helps none; it is a policy with no concept of service level.

Strict Priority Produces Starvation

In the second block, A was given absolute priority. The result for A is flawless: all 1,400,000 jobs finish, average and longest wait both 0.0 minutes. B also improves — wait drops from 6.5 to 4.4 minutes, completion rises from 0.946 to 0.963 — because all the capacity A leaves over goes to it.

For C, the result is different: zero jobs complete. None of the hundred reports finish; all 300,000 jobs are still sitting in the queue at the end of the window. This is starvation: as long as the higher classes’ combined demand fills capacity, nothing is left for the lower class, and its wait time cannot be expressed as a number, because the job never starts. Strict priority is not an ordering — it is a conditional cancellation.

Weighted Share Redistributes the Shortfall

In the third block, each class received a share. A is again flawless (0.0 minutes wait), because its reserved share is 135 jobs/s against its need of 97.22. All of C finishes: the whole 300,000 jobs, average wait 0.3 minutes.

B pays the cost: completion falls from 0.963 to 0.938, remaining backlog rises from 440,000 to 740,000. The difference is exactly 300,000 — C’s own job volume. The policy change created no new work; it took C’s job at B’s expense, and the accounting balances to the penny.

A Share Is Both a Floor and a Ceiling

The last two blocks show the same policies under A’s spike. Under strict priority, A is again unaffected: all 1,750,000 jobs, 0.0 minutes wait. Under weighted share, A waits: 3.5 minutes on average, 18.1 minutes at the longest. The reason is direct — during the spike, A’s rate rises to 388.9 jobs/s, while its reserved share is 135 jobs/s. Unused shares are passed to A, but they are not enough.

A share is a floor and a ceiling at the same time. The mechanism that saves C from starvation is the same one that limits A during the spike. The choice of policy therefore does not answer “which one is better” but “what do we want to happen on each class’s bad day.” Strict priority makes the other classes pay for the top class’s bad day; weighted share limits every class’s bad day to its own share.

Back to the Estimate

The last three lines mark this lesson’s boundary. The three classes’ combined requirement is 951.39 jobs/s, capacity is 900; the shortfall over the four-hour window is 740,000 jobs. This number is the same in all five runs. In the single queue it is 75,736 + 649,263 + 15,000; under strict priority, 0 + 440,000 + 300,000; under weighted share, 740,000 + 0 + 0. The policy chooses who the shortfall is charged to; it does not shrink the shortfall. In the runs with the spike, the total rises to 1,090,000, and the difference is exactly the 350,000 jobs that were added.

Two ways close the shortfall, both outside the queue: raising capacity from 900 to 951.39 jobs/s (1.057 times), or extending the V10 window from 4.00 hours to 4.23 hours. K6’s sensitivity confirms this: at capacity 850, the total remaining is 1,460,000; at 900, it is 740,000; at 950, it is 20,000. A six-percent increase in capacity erases 97 percent of the shortfall.

The result that flows back to K01 is this: V10’s four-hour window holds when the end-of-day job runs alone. Once another stream enters the same group, the window is no longer a constraint but a shared resource, and whether V10 is met can no longer be judged from B’s rate alone.

Summary

• A priority queue is a service-level decision; the priority queue in the Data Structures curriculum is a data structure, and it is not covered in this lesson.
• In the single queue, all three classes get the same numbers — completion 0.946 / 0.946 / 0.950, wait 6.5 minutes — so there is no concept of service level.
• Strict priority serves the top class flawlessly (0.0 minutes wait) and produces starvation in the bottom class: zero of a hundred reports finished, 300,000 jobs stayed in the queue.
• Weighted share finishes all of C and B pays the cost to the penny: B’s remaining backlog rises from 440,000 to 740,000, an increase of exactly 300,000.
• A share is both a floor and a ceiling: under A’s spike, strict priority never makes A wait, while weighted share makes it wait 3.5 minutes on average and 18.1 minutes at the longest.
• The total shortfall is independent of the policy: 740,000 jobs in three of the five runs; closing it means raising capacity by a factor of 1.057 or extending the V10 window to 4.23 hours.

Next Step

This lesson treated order as a preference: a priority queue chose which order jobs were taken in, letting the fast one go ahead of the slow one. A job’s wait here was a service-level decision, not a correctness problem. For some jobs, though, order is not something that can be chosen. The same shipment’s state events overwrite each other; if “left the transfer hub” and “delivered” are processed in reverse order, the shipment appears back in transit after it has already been delivered, and the result is corrupted — this is why the order of 2,279 shipments broke across eight consumers in the third lesson. For jobs like these, order is not a preference but a constraint. The next lesson takes up jobs whose order must be preserved, and examines how that constraint can be kept alongside concurrency.