The queue that stops draining above 40,000 items

A worker consumes messages from SQS, and for each message performs a breadth-first traversal of a dependency graph held in memory to decide which downstream tasks to enqueue. Graphs are typically a few thousand nodes.

For customers with graphs under about 20,000 nodes, a message processes in under 200ms. At around 40,000 nodes, processing takes over 90 seconds and the SQS visibility timeout expires, so the message is redelivered and processed again — forever. The queue depth grows without bound.

The traversal is correct: on small graphs it returns exactly the right task set. Memory use is modest even on the large graphs.

The algorithm is correct and memory is fine, yet it becomes unusable at a specific scale. Diagnose the implementation, and separately tell me what is wrong with the operational design that turned a slow function into an infinite loop.