Head-of-line blocking and priority inversion
How does one shared line couple work that has nothing in common, even with resources to spare?
Head-of-line blocking
Head-of-line (HOL) blocking means that the item at the front of a queue blocks everything behind it.
Take one shared FIFO channel. The item at the head costs 10 seconds. Every item behind it costs 1 millisecond. The 1 ms items must wait 10 seconds. During the wait, utilization may be tiny: the big item might use just one thread out of many. Resources are idle, but requests are blocked.
The cause is the combination of two properties:
- a single queue, and
- heterogeneous cost (very different sizes of work in the same line).
Break either one and the problem disappears. So there are exactly two families of fixes.
| Fix | Idea | Examples |
|---|---|---|
| Break the sharing | Use many queues, one per class or per destination | HTTP/2 streams, per-connection channels, per-destination connection pools, per-class thread pools |
| Break the heterogeneity | Bound the maximum size of one work item | Chunking, pagination, streaming responses, request-size limits |
For the bulk request: split it into chunks of 50 rides (so each chunk costs 100 ms), and give the bulk work its own thread pool. Both families, used together.
HOL blocking reappears at every layer that imposes a total order on independent work. A fix placed above the ordering layer does not remove the ordering layer. HTTP/2 is the standard case: it removed HOL blocking from the application and left it in TCP (Priority and multiplexing). A Kafka partition is a total order by construction, so a slow consumer of one key blocks every key in that partition (Key-based ordering).
Priority inversion
The classic case has three parties: a low-priority task L, a high-priority task H, and a medium-priority task M.
- L holds a lock.
- H needs the same lock, so H must wait for L.
- M becomes ready. M has higher priority than L, so the scheduler runs M and preempts (interrupts) L.
Now H waits on L, L waits for the CPU, and M runs. H's effective priority is M's. The priority system has inverted, and every mechanism worked exactly as designed.
Mars Pathfinder is the famous real case. A high-priority bus-management task blocked on a mutex (a lock) held by a low-priority meteorological task. A medium-priority communications task kept preempting the meteorological task. A watchdog timer saw the bus task miss its deadline and reset the spacecraft, again and again. The watchdog is a manufactured fail-stop mechanism, and it worked correctly. It converted a scheduling problem into a reboot loop.
Two fixes exist, and both make priority a property of the resource, not just of the task:
- Priority inheritance: the lock holder temporarily takes the priority of the highest-priority waiter.
- Priority ceiling: each lock carries the maximum priority of any task that could ever acquire it, and the holder runs at that priority.
The insight: a task that holds a resource a high-priority task needs is, for that time, doing high-priority work.
The distributed version
Any shared middle tier serves requests from callers of mixed priority and knows nothing about their priority: a connection pool, a message broker, a metadata service, a data-warehouse queue. An interactive query then waits behind a batch backfill on the same pool. For example, a rider's "book now" request waits in the same database connection pool as a finance team's nightly export.
The principle is the same, but the mechanism is harder. Priority must be propagated in-band with the request, which means the priority travels inside the request itself. This is the global-invariant principle (a property that must hold across a whole chain cannot be kept by per-hop configuration). It is the same structure as deadline propagation and retry budgets. It has the same plumbing cost (every hop must carry it) and the same requirement: no hop may drop it. If the shared tier belongs to a third party, propagation is impossible, and your only option is physical separation of pools (the reserved lanes of Prioritization and short-query lanes).