Taming the Noisy Neighbor: Simple Fair Queues vs Amazon SQS

In many services a shared, paid "line" (e.g., an external AI API) behaves like a FIFO queue with multiple producers. When one producer (A) bursts with many requests, other producers (B, C) are starved, a situation known as the Noisy Neighbor Problem, where a single tenant monopolizes resources.

Common Solutions

Two typical approaches exist. The first splits the queue per producer, giving each its own line; this eliminates interference but can be costly because each line incurs a purchase cost. The second limits the production speed of each producer, adding rate‑limiting logic and retry mechanisms, which increases component complexity.

Amazon SQS

Amazon SQS implements a fair‑queue algorithm that detects noisy neighbors and reorders messages so that quieter tenants (B, C, D) are processed first, while the noisy tenant's messages wait until the backlog clears. This approach solves the problem but may be overkill for simpler scenarios.

Alternative Approach (Broccoli)

A lightweight solution called Broccoli (written in Rust) uses per‑producer queues and a single round‑robin scheduler. Each producer gets a dedicated queue and a client ID. The client IDs are stored in a round‑robin queue. When a new message arrives, it is placed in the producer's queue; if the producer's ID is not already in the round‑robin queue, it is appended.

Message consumption works by taking the client ID at the head of the round‑robin queue, pulling one message from that producer's queue, and processing it. If the producer's queue becomes empty, its ID is removed; otherwise the ID is moved to the tail of the round‑robin queue. This ensures alternating execution of producers, automatically balances load, and avoids extra cost because only one paid line is used.

The design is simple, self‑balancing, and avoids the complexity of dynamic weighting or advanced algorithms while still providing fair access for all tenants.

Code

The core logic consists of two parts: insertion of new messages and consumption of messages. Insertion stores the message in the producer's queue and ensures the producer's ID is present in the round‑robin queue. Consumption retrieves the head ID, processes one message, and updates the round‑robin queue based on whether the producer's queue still has pending messages.

All of this can be implemented in a few lines of Rust; the full source is available at https://github.com/densumesh/broccoli .