RequestFairQueue selection cost grows with historical group activations

[andreatnvidia]

Priority Level

High (Major functionality broken)

Describe the bug

RequestFairQueue retains one heap entry for every historical group activation. _activate_group() appends a new tuple to _heap, while commit() removes only the corresponding entry from _active_heap_entries. The stale tuple remains in _heap permanently.

select_next() copies and heapifies the full historical heap on every selection, then pops stale tuples until it reaches a current active entry. Selection cost and retained state therefore grow with total requests processed rather than the number of active request groups.

This creates increasing event-loop CPU overhead during long asynchronous generation runs without changing the number of active groups.

Steps/Code to reproduce bug

from data_designer.engine.models.request_admission.queue import RequestFairQueue, RequestWaiter
from data_designer.engine.models.request_admission.resources import (
    RequestAdmissionItem,
    RequestDomain,
    RequestGroupSpec,
    RequestResourceKey,
)

resource = RequestResourceKey("provider", "model", RequestDomain.CHAT)
group = RequestGroupSpec(resource)
queue = RequestFairQueue()

for index in range(1_000):
    waiter = RequestWaiter(
        waiter_id=str(index),
        item=RequestAdmissionItem(resource=resource, group=group),
        enqueued_at=float(index),
    )
    assert queue.enqueue(waiter)
    selection = queue.select_next(lambda _waiter, _view: True)
    assert selection is not None
    assert queue.commit(selection) is waiter

assert not queue.has_waiters
print(len(queue._heap), len(queue._active_heap_entries))

The queue has no waiters or active groups, but _heap still contains approximately 1,000 historical entries. Repeating the loop continues to grow the heap.

Expected behavior

Request selection state and cost should be bounded by currently active request groups. Historical activations should either be removed or compacted, or select_next() should construct its temporary heap from _active_heap_entries only.

Weighted fair ordering and transaction semantics should remain unchanged.

Agent Diagnostic / Prior Investigation

The request-admission design documents describe RequestFairQueue as the canonical weighted-fair queue, but no existing issue was found for historical heap growth.

A GIL-only profile of a long asynchronous generation run attributed 18.42% of samples to request-admission queue selection. A minimal active-only heap change reduced that share to 0.51%, a 97.2% relative reduction. In the same controlled workload, response and completed-record throughput improved by approximately 22-25%.

A focused regression test can repeatedly activate and drain one group, then count heap pops during the next public select_next() call. The fixed implementation requires one pop regardless of the number of historical activations.

Additional context

The affected queue is internal, so the fix should not require a public API change. This is related to the request-admission work tracked by #645.

Checklist

• I reproduced this issue or provided a minimal example
• I searched the docs/issues myself, or had my agent do so
• If I used an agent, I included its diagnostics above