Learn

Architecture & pattern guides

Read the idea, build it on a Grid, prove it in a challenge. Short, practical guides — illustrated with RodGrid's own nodes — on system design, design patterns, flow modeling, and how to get the most out of the app.

All articles

Priority Queue

Let urgent work overtake routine work that is waiting: native priorities or one queue per class, how to keep low priority from starving, why a message a worker already holds is not overtaken, and who gets to set the priority.

Three hours and twenty minutes

That is about how long build #90417 sat in the queue. It was a one-line fix for a production outage, pushed by an on-call engineer minutes after the CI service's dependency bot had opened its nightly pull requests across every repository, with about 3,000 builds waiting. The service runs 60 build agents and a build takes about four minutes: 3,000 × 4 minutes ÷ 60 agents = 200 minutes. The hotfix needed four minutes of work and joined the back of the line.

The queue absorbed a burst, which is Queue-Based Load Leveling, and the agents shared it the way Competing Consumers describes. More agents are not the obvious answer either: capacity to clear 3,000 builds in minutes would sit idle the rest of the day. The trouble is that a first-in, first-out queue knows one thing about a message, when it arrived, and what separates these two builds is what a wait costs. For the dependency update, nothing until morning. For the hotfix, another minute of outage.

A Priority Queue lets urgent work overtake routine work that is still waiting: the next free worker gets the most urgent message instead of the oldest. The ranking is the business's to set, such as a hotfix before a bot's update, or a paid customer's job before a free one. Two classes, urgent and routine, are enough for this CI service.

One queue with levels, or one queue per class

There are two ways to build it, and your broker may choose for you. Some brokers have native priorities: each message carries a priority number and the broker hands out the highest first. RabbitMQ does this on a classic queue declared with a maximum priority (x-max-priority). Amazon SQS has no message priority, Kafka has none because a partition is read in offset order, and Azure Service Bus does not sort a queue by priority either. There you use separate queues, one per class, here builds-urgent and builds-routine, and the worker decides which to read.

Two classes, one pool of agents

A free agent reads builds-urgent first and builds-routine only when urgent is empty. Each build still goes to one agent.

The loop in that diagram is a strict drain: take from urgent while it holds anything, and only then from routine. Sixty agents finishing four-minute builds at staggered times free one every four seconds on average, so the hotfix now waits seconds, with the same hardware. Native priorities are less to build, but you usually get the rule the broker implements; with separate queues the rule is your own code.

Either way you have given up arrival order on purpose: two builds of one repository in different classes can start in the opposite order to their pushes. Keeping messages in sequence is the job of Sequential Convoy.

The dependency update that never ran

Strict drain has a failure that takes longer to show. In one release week, teams sent their release candidates as urgent, about 15 builds a minute. That is everything 60 agents can do at four minutes a build, so every agent that came free found something in builds-urgent, and builds-routine got nothing for four days. One of the builds in there carried a security patch. This is starvation: low-priority work blocked for as long as urgent work keeps coming. Three defences are common.

  • Weighted drain. The agent takes, say, nine urgent builds for every routine one while both have work. At worst, routine still averages 1.5 of the 15 builds a minute. Urgent gives up a tenth of its capacity during a flood and nothing otherwise, because an empty routine queue hands its turn back.
  • A reserved share. Six of the 60 agents read routine first, whatever urgent holds, and take urgent only when routine is empty. The floor is about the same as 9:1, and it takes one setting per agent instead of a counter.
  • Ageing. A message's priority rises as it waits: here, a small job moves any routine build older than 12 hours onto builds-urgent, deleting the original only once the broker confirms the copy is durably stored: a crash between the two can leave duplicate copies but does not lose the build, so each build must be safe to run again. If urgent stays flooded, promoted builds simply join its line, and enough of them turn it back into one first-in, first-out queue.

None of these creates capacity. If more than 15 builds a minute arrive for long enough, some queue grows whatever the drain rule says, and priorities only choose which one. Deciding what to refuse at that point is Load Shedding.

Already in an agent's hands

Priority decides what goes next. It has no say over what has already left the queue, and that shows in two ways.

The first is prefetch. To avoid a network round trip per message, many consumers take several messages in advance and keep them locally. Those messages are delivered, so the queue can no longer reorder them. Suppose each agent prefetches five builds: it runs one and holds four, in the order they arrived. The hotfix reaches the first agent to finish a build, within seconds, and lands behind the four that agent still has, and 4 × 4 minutes means about 16 minutes before it starts. A prefetch of one fixes this for a round trip per message, which is nothing beside a four-minute build. For tasks that take milliseconds that round trip adds up, so keep prefetch small and accept that a few messages get ahead.

The second is the long job. A broker does not reach into a worker and stop it. If 90-minute integration suites occupy all 60 agents, a hotfix waits for the first of them to finish, however high its priority. The usual answer is a few agents that read only urgent, and the time they sit idle is the price. Cancelling a running build to make room is yours to build, and the job must be safe to run again.

When everything is urgent

The first version let any team write priority: urgent in its build config. Within months about 70% of builds were urgent, because for each team, on each build, that was the sensible thing to write. At 70% the urgent queue is most of the old queue under a new name, and the hotfix waits behind other people's lint runs. Priority inflation is what happens when the party that benefits sets the priority.

So the service stopped asking. The class now comes from facts a requester cannot simply type: a protected hotfix/ branch with on-call approval is urgent, the bot's account is always routine, and a plan tier would be read from billing, never from the message. One customer flooding its own class is a different problem, limited by Throttling.

Adding the second class in the Challenge

The Competing Consumers Challenge holds the Priority Queue node in its palette, and its six nodes are enough for a Client, two Priority Queue nodes and three Competing Consumers. Its brief does not ask for priorities, so add them on top of what it does ask, each message reaching one worker and throughput rising with workers, and label the edge leaving each queue with its drain rule, such as "9 of 10" and "1 of 10". Then ask your drawing: if urgent never empties, what does routine get? The much larger Distributed Job Scheduler Challenge lists job priorities among its requirements.

The wait you watch

Queue depth will not tell you whether this works, since 3,000 routine builds is a normal night. Measure the wait between publishing a message and a worker starting on it, per class: here the 95th percentile for urgent, with a target of two minutes, and the age of the oldest routine build, promoted or not, counted from its first publish. Urgent over target while its queue is short points to prefetch or long jobs. The 12 hours only trigger promotion, so that age can pass them; if it keeps climbing, check that the job is running, how crowded urgent is, and whether routine's share or total load is the problem. Urgent above about a tenth of all builds, a threshold this service chose, means checking for an incident or for routine work classified as urgent; no drain setting fixes the second.

Practice this