Skip to content

Fair-queue #weightedShuffle never decrements totalWeight, biasing env ordering when biases are enabled #4001

@yashs33244

Description

@yashs33244

Summary

In internal-packages/run-engine/src/run-queue/fairQueueSelectionStrategy.ts, #weightedShuffle declares totalWeight once over all items and never decrements it after splicing an item out. Each iteration draws random = this._rng() * totalWeight against the stale full-set total, so the inner consume loop overshoots and clamps to a fixed index — producing a systematically non-uniform shuffle instead of weighted-uniform.

The two sibling methods do it correctly: #weightedRandomQueueOrder and #selectTopEnvs both totalWeight -= ...weight before their splice. #weightedShuffle is the copy missing that line.

Impact

Only reached when a fair-queue bias is enabled (concurrencyLimitBias or availableCapacityBias > 0; both default to 0), so it's latent under defaults. When enabled, the env ordering is skewed — e.g. for 4 equal-weight items the final output position lands roughly 9% / 43% across items instead of ~25% each (the first pick is unbiased because the set is still full, which masks it in naive tests).

Suggested fix

Make totalWeight a let and add totalWeight -= items[index].weight; immediately before items.splice(index, 1), matching the two sibling methods.

How to verify

Inject a seeded _rng (the class already accepts one), run #weightedShuffle over N equal-weight items many times, and assert each output position is ~uniform within tolerance. Fails before the fix (skewed), passes after.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type
    No fields configured for issues without a type.

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions