AI-narrated article. Prose is preserved with pronunciation adjustments; code and image cues refer to the written article.
Heaps for Platform Workers: Stable Priorities Without Stale Work
This is the AI-narrated article. The prose follows the written post; pronunciation is adjusted, and code and images are announced separately.
Build a bounded pending queue that handles stable ties, priority changes and cancellation, then define the worker lifecycle the heap cannot provide.
TL;DR: A heap chooses the smallest ordering key, but a reliable worker needs explicit rules for ties, replacement, cancellation and admission. This article builds a bounded Python pending queue with unique sequence numbers, a live dictionary and lazy invalidation. Payloads stay out of comparison and obsolete entries, while periodic compaction limits physical entry count. Correctness checks compare operations against a reference model and reproduce a dictionary comparison failure. The queue deliberately excludes durability, acknowledgements, fairness and thread safety. Treat it as an ordering component beneath an authoritative job lifecycle, with eligibility and tenant policy handled separately.
A worker queue needs more than a smallest item
A platform worker receives artifact scans, reconciliation jobs and urgent repairs. A min-heap can select the smallest priority quickly, but the operational problems arrive later: two jobs tie, an operator cancels pending work, or a retry changes its priority. A naive implementation can dispatch an obsolete entry or retain thousands of superseded payloads while its dashboard reports one pending task.
The useful outcome is a queue whose ordering, admission and cancellation contracts are explicit. This article builds a bounded, single-owner pending queue in Python 3.11. It supports replacement and lazy invalidation without comparing payloads. It is a scheduling component inside a worker, rather than a durable job service.
Read the heap as a partial order
Python's heapq documentation defines a min-heap: each parent compares no greater than either child. With zero-based indexing, node i has children 2*i+1 and 2*i+2. The root is the next minimum; the remaining array is not globally sorted.
Image. A valid heap array and its corresponding tree: parents precede children, but the array is not sorted
The illustrated array [2, 4, 3, 9, 7, 5] is valid even though 4 appears before 3. Repeated pops produce 2, 3, 4, 5, 7, 9. Treating array iteration as dispatch order would choose the wrong next task.
Our entries are (priority, sequence, task_id). Smaller priorities run first. A unique sequence breaks ties, so arbitrary dictionary payloads never enter tuple comparison. Replacing a task gives it a new sequence: it joins the end of its new priority group, even when its priority stays unchanged. That is a deliberate policy, not an automatic property of heaps.
Why keep live state separate?
The live dictionary contains the current priority, sequence and payload for each task ID. Heap entries contain only ordering metadata. A replacement adds another entry and invalidates the old sequence; cancellation removes the live record. Dispatch skips entries whose sequence no longer matches.
This protects against a subtle reused-ID failure. Cancel task a, then admit a new task a: finding the ID alone does not prove an old heap entry is current. The generation check distinguishes them.
Lazy invalidation avoids searching the array for every change, but stale entries still consume memory. Rebuild from live records when physical entries exceed max(32, 2 * pending); clear the heap when pending reaches zero. After a successful operation, physical entries remain within that threshold. This bounds entry count, not total bytes: payload size, Python object overhead and growing sequence integers still matter. Limit serialized input size at admission and use compact references for large artifacts.
Complete Python implementation
Prerequisites are Python 3.11 and a disposable local directory. The example uses only the standard library, makes no network calls and writes no external state. Save this file as priority_queue_20.py. Its contract requires one serial owner: callers must not interleave operations from threads or reentrant callbacks.
Code example. Refer to the written article for the complete code.
Run without -O, which disables assertions:
Code example. Refer to the written article for the complete code.
The main block verifies that an urgent replacement runs before repair, cancelled work stays absent, and draining removes stale entries. Cleanup consists of deleting this example file and any generated __pycache__ directory inside your disposable example directory; there are no containers, credentials or infrastructure to remove.
IDs are bounded strings and priorities are bounded integers. Rejecting floats also rejects NaN, whose comparison behavior would undermine ordering. A full queue rejects a new ID before mutation, while a replacement consumes the existing pending slot. Payloads remain shared references: copy or freeze them upstream if later mutation would change the intended job.
Reproduce a failure without touching a worker
The following broken pattern puts payloads directly into comparison. Run it in a separate Python process:
Code example. Refer to the written article for the complete code.
Equal priorities force tuple comparison onto the dictionaries. A comparison exception can leave the attempted entry appended, so catching the exception and continuing to trust the heap is unsafe. The pinned CPython implementation shows insertion appending before sifting.
Recovery means rebuilding from authoritative pending records with validated ordering keys, then resuming dispatch. In our implementation, sequence numbers prevent payload comparison. If the process encounters allocation failure or internal corruption, do not assume multi-step mutation was transactional: fail the component and reconstruct from the durable source. A heap is an index, not a recovery log.
Verification checks correctness, not throughput
The accompanying correctness script exercises tie order, replacement, cancellation, ID reuse, capacity rejection, payload-reference release and compaction. It also compares 10,000 seeded operations against a dictionary model that selects the minimum current (priority, sequence). After each operation it checks live count, physical-entry bounds and the parent-child heap invariant.
The executed checks completed 10,000 model operations with zero mismatches. In a separate 1,000-replacement check with one live task, the largest physical heap held 32 entries and compaction ran 31 times. The broken dictionary example raised TypeError and left two entries in its heap. These are deterministic local implementation checks. They cannot establish production latency, memory bytes per job, concurrency safety or fairness. No throughput benchmark is supplied. For a deployed worker, observe pending count separately from physical heap entries, oldest pending age by class, admission rejection and compaction duration.
Heap push and pop maintain ordering through a logarithmic tree path; rebuilding uses linear-time heapify. The Python implementation exposes both algorithms. Lazy removal changes the practical cost: one dispatch can skip multiple stale entries, and compaction performs synchronous work. Entry-count bounds do not promise a dispatch-latency bound.
Priority is only one scheduling decision
An endless urgent stream can starve background scans. FIFO tie handling helps only within the same priority. Tenant quotas, reserved capacity or a weighted class scheduler belong above this heap. Validate who can choose priority: accepting arbitrary caller urgency defeats the policy.
Likewise, delayed retries need eligibility handling. If the top entry is not due yet, it can block eligible lower-priority work. Maintain a delay heap keyed by a monotonic deadline, then transfer due work into the ready priority queue. Python's time.monotonic reference describes a clock unaffected by system-clock updates; its values are unsuitable as persistent cross-restart timestamps.
A successful pop removes pending state before execution. There is no lease, acknowledgement, retry storage or crash redelivery. A production worker should claim work from a durable source and use this queue only to order a bounded set of eligible candidates. Cancelling pending work also cannot stop a task already dispatched.
For a simpler threaded handoff, queue.PriorityQueue supplies locking and bounded admission. Its API does not add this replacement protocol. Its task_done/join accounting is in-process coordination, not durable acknowledgement. The pinned queue source shows the synchronization around its heap.
Frequently asked questions
Does a heap keep every element sorted? No. It preserves parent-child ordering so the root is the minimum. Pop repeatedly for dispatch order.
Can I change priority inside an existing entry? Not safely without restoring the invariant. This implementation adds a new generation and ignores obsolete entries.
Does cancellation immediately free all memory? It releases this queue's live payload reference. Other references may retain the object, and small stale metadata can remain until dispatch or compaction.
Is this a production job broker? No. It has no durability, delivery guarantees, fairness or thread safety. Use it as a bounded ordering component under an explicit worker lifecycle.