Fair Turns at Scale

When many users compete for the same pool of workers, one user submitting a million tasks can hold up everyone behind them, even those with just a single task to process. This is an instance of the “noisy neighbor” problem, and it can surface anywhere users share a finite resource: worker pools, connections, bandwidth, or CPU time. The standard tools for distributed task orchestration queues typically work first-in, first-out (FIFO) by default. In contrast, C4ADS’ vtrr-queue changes the ordering itself by always serving whoever has made the least progress so far, weighted by how much work each task actually represents. Every active user moves forward on every pass, so a five-task upload finishes in minutes instead of waiting behind a million-task one.

We built vtrr-queue for Horizons, C4ADS’ open-source intelligence platform that centralizes billions of public records for researchers, journalists, and investigators tracing transnational illicit and malign networks. Bring your Own Data (BYOD), a new release in Horizons, lets any user upload and index their own files as a dataset with no technical barrier. Once a dataset is indexed, investigators can search it alongside the platform’s existing holdings, cross-referencing their own materials against corporate registries, shipping records, and sanctions data. Uploads are also OCR’d for multilingual full-text search, and shareable with colleagues rather than stranded on a laptop.

Horizons ingests at an incredible scale, handling workflows of tens of millions of files at a time. Opening that pipeline to all Horizons users via BYOD introduced the classic “noisy neighbor” problem. For BYOD, queue fairness has to account for both how many files a user uploads and how large they are. vtrr-queue weighs both, so every Horizons user makes progress on their file upload, no matter how much else is in the BYOD queue.

Consider an ice cream shop on a hot day, when the line stretches out the door. After finally placing an order, a customer is shocked to learn the estimated wait is another hour. This is all thanks to Bob, who forgot it was his son’s birthday and has just placed 100 last-minute orders for the party. It makes no difference that the customer behind him wants a single scoop, because the shop fulfills orders strictly in the order received. Everyone waits while the shop works exclusively through Bob’s list.

Bob does not introduce a volume problem, and the shop isn’t understaffed. The work is simply being handed out in the wrong order. None of the usual fixes help, either. The store can’t drop Bob’s orders to “throttle” him; it can’t hire more employees on the spot; and reserving a station for each customer in line would leave most employees idle. What the shop needs is a different order of service, not more capacity.

This is the exact situation we faced when introducing BYOD in Horizons. No single user should be able to monopolize extract, transform, and load (ETL) resources and hold up everyone else uploading at the same time — but none of the commonly suggested remedies applied. Throttling would mean dropping processing tasks a dataset requires, leaving a user with a partially indexed upload. Reserving capacity per user is a poor fit for a platform meant to serve every user indiscriminately. And scaling out the worker pool meant recurring infrastructure cost, which as a nonprofit we couldn’t justify for a problem solvable in software.

A simple solution called “round-robin” solves the problem by enforcing fairness. Instead of the FIFO order in which the system completes requests, the round-robin would enforce a turn-based system for the users waiting for their tasks to complete. Going back to the ice cream shop example, this algorithm cycles through the set of customers and takes one order from each customer per turn: one from Bob, one from Curt, one from Abe, then back around to Bob. This way, the shop can complete other customers’ orders between Bob’s orders instead of making everyone wait behind Bob.

For BYOD, this is the key desired property. If user A uploads a million files and user B uploads only five a moment later, B’s tasks aren’t stuck behind A’s million. Instead, round-robin interleaves the order in which tasks are done by giving each user a fair turn. So round-robin processes user B’s five files within the next few turns instead of waiting for A’s entire batch to drain, and every active user makes forward progress on every pass while sharing the resources equally.

Round robin resolves most of the problem, but one issue remains. Each user gets a turn, but turns aren’t the same size. In the ice cream example, every kid at Bob’s party could have ordered a tremendously large sundae, so each of Bob’s turns take far longer than the single scoop behind him and he keeps monopolizing the counter. For BYOD, a 100 MB file should not carry the same weight as a 1 MB file.

This is where the notion of “virtual time” comes in. Rather than cycling through users turn by turn, virtual-time assigns a weight to every turn, and those weights are configurable for different use cases. Give each turn a weight of 5 MB, for example, and a user can finish five 1 MB files or process 5 MB of a 100 MB file before the turn passes on. A single large request can no longer hold up the whole queue. 

The example oversimplifies slightly, since the system can’t pause mid-file to switch turns. Virtual-time round-robin still has to complete the 100 MB file from user A in a single turn. What it does instead is push user A’s subsequent requests far down a virtual timeline, giving every competing user enough turns to catch up before A comes around again. Each user’s progress also decays after each turn, so everyone gradually works back toward the front. This keeps a user who made a large request earlier from getting stuck behind a flood of small ones

In summary, the algorithm serves whoever has made the least progress so far, updates their progress for the work done, and repeats. Because it always prioritizes the user furthest behind, it guarantees a balanced allocation of resource capacity across all users. For more information, you can check out how the Linux Completely Fair Scheduler (CFS) also uses a virtual-time round-robin algorithm for CPU time.

Implementing virtual-time round-robin correctly means handling atomicity, avoiding races, and scheduling workers so the ordering actually holds under concurrency. C4ADS has packaged that logic into vtrr-queue and released it for teams running Celery and Redis on a Python backend.

The vtrr-queue library is small and easy to plug into an existing project, with familiar patterns. Define a function, enqueue it as a task and a Celery worker picks it up. However, instead of Celery’s default FIFO order, the library configures the workers automatically so tasks execute in virtual-time round-robin order.

Some key points about this library:

• Reused Celery Syntax – The vtrr-queue library’s decorator used to mark a function as a task is based on the decorator that Celery uses. It can use most of the common decorator parameters like max_retries and soft_time_limit.
  
  
• Define custom partition and weights – The library allows individual weights for each task that can be enqueued into the weighted round-robin. Additionally, instead of partitioning the turns based off of the users, partitions can be made custom. For example, they can partition by regions if the goal is for the round-robin to cycle through regions per-turn instead of users.
  
  
• Fully atomic – Every enqueue and dequeue is a single Lua script that runs inside Redis, so concurrent writers and workers will never face a race condition. This guarantees no partial writes occur, no tasks are lost, and no two workers grab the same job.

vtrr-queue is built for a specific problem, and it does not apply everywhere:

• Redis and Celery only. The atomicity guarantees come from Lua scripts running inside Redis, so there’s no path to RabbitMQ, SQS, or another broker without a reimplementation.
  
  
• Weights have to be known at enqueue time. For BYOD, file size is available up front. If the cost of a task can’t be estimated until it runs, the weighting won’t reflect actual work done.
  
  
• Fairness is not throughput. Interleaving users adds bookkeeping on every dequeue. A single user submitting a large batch to an otherwise empty queue finishes no faster than under FIFO – slightly slower, in fact. The gain only appears under contention.
  
  
• Partitions are only as good as their definition. Partitioning by user assumes users are the unit of fairness. If one account belongs to a team and another to a single person, per-user fairness might not be the fairness you’re after.

For full documentation, visit https://github.com/C-Research/vtrr-queue.