Fair by design: orchestrating background jobs in Ruby

Let’s start with one of my favorite weird metrics: the Pentagon Pizza Index. As the theory would have it, when a political crisis is brewing, late-night pizza deliveries around the Pentagon spike. The staff can’t go home, so they order food. Some have even tried to use this as a predictor of major geopolitical events. Fortunately, this post is not about geopolitics. It’s about pizza background jobs.

Still, imagine you own a pizza place. You’ve got a kitchen, chefs, and a single queue of orders. Your chefs take the next order from that queue. It’s predictable and efficient. Then, “Client X” calls with a massive late-night order. You think: “Time for some sweet, sweet, revenue!”

But a few minutes later, a “regular” customer walks in for one slice. The cashier has to turn them away: “Sorry, it’ll be a couple of hours. We’re backed up with a huge order.” The customer leaves hungry and annoyed: “So unfair! I just wanted a single slice.”

And they would be right. It was unfair. Nothing dramatic happened and the kitchen did exactly what it was designed to do. But you just lost a customer. And next time, they may not come back, even on a quiet night. So, what happened? And could you have done something differently?

Irina Nazarova CEO at Evil Martians

Need help with fair prioritization? Evil Martians can help you choose and build the right background job strategy.

Book a call

Latency isn’t the whole story

In the world of background job processing, the first metric we look at is queue latency: the age of the oldest job still waiting.

Latency is directly tied to quality of service (QoS). High latency makes users angry, just like in the pizza story. The natural reaction is to increase throughput by adding more workers. But workers cost money. Autoscaling helps you avoid paying for idle workers, but it also has a ceiling: a system has limited database connections, external API rate limits, and other shared resources.

Even before that ceiling, throwing more money at the problem can stop paying off. Better QoS at higher operational cost does not always bring more customers or more revenue.

In either case, you have a bottleneck. Every system has one. The only difference is whether it is wide enough for your peak traffic. If it is not, latency becomes unavoidable. And when latency is unavoidable, what do we do?

In the pizza story, imagine we could pause the huge order, serve the single-slice customer, then resume. The large customer might not even notice. But the small customer definitely would. The total time to process all orders stays the same. So do overall throughput and queue latency. And yet, the QoS improves. Why? Because we treated our customers fairly.

What does “fair” mean?

There are actually formal ways to measure fairness. For instance, economists use the Gini index and network engineers use Jain’s fairness index. But most teams do not need a fairness metric to know when a queue is unfair. If you have a first-in, first-out queue, occasional high latency, and tenants who can enqueue very different amounts of work, you probably have a fairness problem.

Intuitively, fairness means that everyone gets a piece of the pie: a slice of the shared resource, up to their appetite, but never at the expense of others. In other words, everyone gets an equal share at first. If some tenants need less, the leftovers are split equally among those who still need more. This continues until the resource is fully allocated.

If the shared resource is worker time, then the obvious implementation is to replace one global queue with one queue per tenant and poll those queues round-robin. As a good-enough approximation, you could also poll them at random. Either way, every tenant gets an equal chance to have one of their jobs processed. Everyone gets a turn. Tenants with more work can still consume more, but only after others have had a chance to make progress.

Of course, this is the most basic case, where all tenants are treated equally. If you want to give some VIP tenants priority but still not at the expense of normal tenants, you need to change the algorithm slightly: assign different weights to the per-tenant queues and poll them according to those weights, rather than giving every queue the same probability.

But either way, this means we would have a dynamic, potentially large set of queues, and most background job processors are not designed to handle this.

A look inside background job processors

Let’s look under the hood of four popular Ruby background processors and see how they would handle a large, dynamic set of queues.

Sidekiq

In the open source version of Sidekiq, every worker would make the following request to Redis every time it wants to pull a job for processing:

BRPOP queue:tenant_1 queue:tenant_2 ... queue:tenant_N <timeout>

BRPOP checks queue:tenant_1, then queue:tenant_2, and so on until it finds a job. If all queues are empty, it waits instead of polling Redis continuously, so Redis doesn’t get hammered. With equal queue weights, Sidekiq gives each queue the same chance of being checked first by shuffling the queue list before making a request.

This is surprisingly close to the fair scheduler we sketched above.

The catch is dynamic queues. Sidekiq workers subscribe to a fixed, static queue list. You can’t add or remove tenant queues while the process is running.

We’d also need to track “active” tenants, meaning tenants with jobs waiting to be processed, so we don’t poll every tenant queue in the system every time. Imagine doing that with hundreds of thousands of tenants.

Still, if Sidekiq supported a dynamic list of queues, implementing fair scheduling on top would be almost within reach.

Sidekiq Pro

Unfortunately, the open source version has one serious drawback: after BRPOP, the job is no longer in Redis. If a worker dies mid-job, that job can be lost.

Sidekiq Pro fixes this reliability problem. It’s one of the main reasons teams choose it over the open source version.

But to make job processing more reliable, it had to change how workers pull jobs for processing:

LMOVE queue:tenant_1 queue:sq|<worker ID>|tenant_1 RIGHT LEFT
LMOVE queue:tenant_2 queue:sq|<worker ID>|tenant_2 RIGHT LEFT
...
LMOVE queue:tenant_N queue:sq|<worker ID>|tenant_N RIGHT LEFT

In Sidekiq Pro, every worker has its own set of “in-progress” queues. LMOVE moves a job from the tenant queue into the matching worker queue. The worker removes the job only after processing it. If the worker dies, the job is still in Redis and can be recovered.

The trade-off is losing the single blocking BRPOP across all queues. Because of Redis constraints, each worker now has to try all queues one by one with LMOVE until it finds work. Those calls are non-blocking, so a worker can end up polling Redis over and over just to fetch a single job. This does not scale well with the number of queues, so tracking the “active” queues would be absolutely essential: it would increase the chance of pulling a job in a few requests instead of going through the whole queue list.

But Sidekiq Pro still doesn’t support dynamic queues, so it was never an option anyway.

Solid Queue

Solid Queue stores jobs in a relational database and uses FOR UPDATE SKIP LOCKED so multiple workers can poll efficiently without waiting on the same locked rows:

SELECT job_id
FROM solid_queue_ready_executions
WHERE queue_name = 'tenant_N'
ORDER BY priority ASC, job_id ASC
LIMIT ?
FOR UPDATE SKIP LOCKED;

Like Sidekiq Pro, it polls one queue at a time until it finds work, so it also doesn’t scale well with the number of queues.

However, unlike Sidekiq, Solid Queue actually does support dynamic queues: you can tell a worker to process all queues named like tenant_*.

That can make polling less efficient than explicit queue names. The exact cost depends on whether you use MySQL, PostgreSQL, or SQLite, but in any case, Solid Queue has to make one extra request before each poll:

SELECT DISTINCT(queue_name)
FROM solid_queue_ready_executions
WHERE queue_name LIKE 'tenant_%';

Overall, that’s not too bad. The catch is that Solid Queue doesn’t support weighted queues like Sidekiq does. Queues are polled in exactly the order the database returns them.

If it at least shuffled the list before polling, then it’d support the basic use case where all tenants are treated equally. For the VIP case, where some tenants are given priority, it would need to figure out where and how to store the weights.

Still, Solid Queue seems much easier to adjust toward our idea of fair scheduling with dynamic per-tenant queues than Sidekiq.

GoodJob

Like Solid Queue, GoodJob is backed by a relational database—PostgreSQL, in this case. Instead of FOR UPDATE SKIP LOCKED, it defaults to using advisory locks to avoid lock contention when pulling jobs from the database:

WITH rows AS MATERIALIZED (
    SELECT id, active_job_id FROM good_jobs
    WHERE queue_name = 'tenant_N' AND (<more filters>)
    ORDER BY priority DESC NULLS LAST, created_at ASC
    LIMIT ?
)
SELECT id FROM rows
WHERE pg_try_advisory_lock(<lock hash based on active_job_id>)
LIMIT 1

Additionally, it relies on PostgreSQL notifications as a best-effort wake-up signal, so the workers don’t have to poll the database as much.

However, it supports neither dynamic queues nor weighted queues, making GoodJob an even worse fit for our use case than either Sidekiq or Solid Queue.

Unfortunately, none of the background job processors we looked at are built with fairness and multi-tenancy in mind. That’s not an oversight; they simply optimize for different things: performance and reliability. It’s difficult enough to achieve those things while being general-purpose. Fairness is a specialized requirement, and it adds overhead.

So, what are we supposed to do?

Building a specialized in-house background job processor would be insane. These processors aren’t FIFO queues with a few extra features. They handle retries, graceful shutdowns, and years of hard-learned production edge cases. So, instead of replacing the processor, let’s try to work with what we already have.

Fairness strategies

We’re going to look at four strategies that could bring some fairness into our background job processing while building on top of the existing infrastructure.

Strategy 1: shuffle-sharding

This strategy is primarily about workload isolation: if something bad happens to one part of the workload, it doesn’t affect the rest. The term shuffle sharding was coined by the AWS team while building Amazon Route 53.

We could achieve isolation with traditional sharding: assign each tenant to one shard and dedicate a set of workers to that shard. Then, when one tenant blocks their shard, only tenants assigned to the same shard are affected.

If we used Sidekiq with ten shards, we could route the workload between them like this:

SomeHeavyJob.set(queue: "shard_#{tenant_id % 10}").perform_async(tenant_id)

Then we could launch ten Sidekiq processes, one for each shard:

bundle exec sidekiq -q shard_0
bundle exec sidekiq -q shard_1
# ...
bundle exec sidekiq -q shard_9

Assuming tenants are distributed uniformly, the chance that two tenants share a shard is one in ten, or 10%. The more shards we create, the fewer tenants one greedy tenant can affect. If we created as many shards as we have tenants and allocated the same resources to each shard, we would essentially achieve fairness.

However, every shard needs at least one dedicated worker. With too many shards, we’re bound to see workers sitting idle because their shards have no work. In other words, as the number of shards grows, the blast radius of one greedy tenant shrinks, but the risk of underutilizing our resources grows.

Now imagine that, instead of routing every tenant’s jobs to just one shard, we deterministically assign each tenant a random pair of shards. Then we choose one of those two shards at random for every job:

def shards_for(tenant_id)
  # Seed the random number generator to get the same shards every time.
  (0..9).to_a.sample(2, random: Random.new(tenant_id))
end

SomeHeavyJob.set(queue: "shard_#{shards_for(tenant_id).sample}").perform_async(tenant_id)

Now each tenant’s workload can be handled by two Sidekiq processes instead of one, improving resource utilization. However, if a greedy tenant previously monopolized one shard, they now monopolize two. That means each job from another tenant has a 20% chance of landing in one of the affected shards instead of 10%.

On the surface, that sounds worse. But the chance that a greedy tenant fully blocks another tenant’s workload has dropped from 10% to about 2%: that’s the chance that both tenants share the exact same pair of shards.

Even if a tenant shares one shard with a greedy tenant, the part of their workload routed to the other shard can still make progress.

This follows the shuffle-sharding pattern described in the AWS article: instead of assigning each tenant to exactly one shard, we assign them to small, overlapping subsets of shards.

The number of unique subsets grows combinatorially with the number of shards. With enough combinations, we could give every tenant a different subset. No two tenants would share every shard, so the chance of one fully blocking another would be 0%.

That said, the main purpose of this approach is workload isolation. For example, if a poisonous HTTP request takes down all the servers handling one tenant, other tenants should still be able to use the service, as long as they don’t share the same set of shards with that tenant. But when we apply it to fair scheduling for background jobs, it can get awkward.

HTTP requests are synchronous and relatively short-lived; if one hits a bad server, it can be retried against another. A background job routed to a flooded queue simply stays there.

This could leave a tenant importing 100 files from cloud storage with 99 files imported successfully while one remains stuck for a long time. That might be even more annoying than delaying the whole batch.

If we want processing to remain consistent within a single tenant’s workload, we can’t route their jobs into multiple shards.

Are we stuck with traditional sharding, then? Not necessarily!

What allows shuffle-sharding to utilize more resources than regular sharding is that workers handle overlapping subsets of tenants. We can achieve a similar effect by assigning overlapping subsets of shards to Sidekiq processes. For example, each process could pull from three equally weighted shards:

bundle exec sidekiq -q shard_0,1 -q shard_1,1 -q shard_2,1
bundle exec sidekiq -q shard_1,1 -q shard_2,1 -q shard_3,1
# ...
bundle exec sidekiq -q shard_9,1 -q shard_0,1 -q shard_1,1

This significantly improves resource utilization, but the chance that one tenant blocks another remains 10%. And since processes are no longer tied to shards one-to-one, we could create more shards than processes, reducing that chance even further.

This raises a question: why not launch a set of identical processes that pull from every shard and, thus, achieve full resource utilization?

bundle exec sidekiq -q shard_0,1 -q shard_1,1 -q shard_2,1 ... -q shard_9,1

With ten shards, we probably could. But this stops scaling as the number of shards grows, as we saw earlier when looking at how Sidekiq Pro pulls jobs from Redis.

And that’s shuffle-sharding in a nutshell. It doesn’t prevent unfairness: when a greedy tenant blocks a shard, they block it for everyone else in that shard. But it can make the problem dramatically less noticeable, especially at scale.

Strategy 2: interruptible iteration

Another strategy that could help with fairness is interruptible iteration. Pioneered by Shopify with its job-iteration gem, the idea has since made its way into both Sidekiq and Ruby on Rails.

The main idea is straightforward: instead of doing all the work inside one long, indivisible job, split it into small iterations and keep a cursor that records the last completed iteration. If the job is interrupted, we can resume from that cursor next time instead of starting over.

Here’s how an iterable file import could look with Sidekiq:

class ImportFilesJob
  include Sidekiq::IterableJob

  def build_enumerator(import_id, cursor:)
    active_record_records_enumerator(
      Import.find(import_id).files.pending,
      cursor: cursor
    )
  end

  def each_iteration(file, _import_id)
    file.import!
  end
end

ImportFilesJob.perform_async(import.id)

Sidekiq calls each_iteration once for every file and updates the cursor as it goes. On a graceful shutdown, it finishes the current iteration, saves the cursor, and re-enqueues the job. When a worker picks it up again, processing resumes with the next file.

That behavior makes deployments and restarts safer, but iteration alone doesn’t make scheduling fair. By default, an iterable job keeps running until it finishes or the worker is interrupted. It doesn’t return to the back of the queue after every item.

To turn interruptible iteration into a fairness strategy, the job needs to yield after a limited amount of time. Sidekiq’s built-in IterableJob API doesn’t currently support this, but if we used Shopify’s job-iteration gem instead, we could configure a maximum runtime like this:

ImportFilesJob.job_iteration_max_job_runtime = 2.minutes

Once that time budget expires, the job finishes its current iteration, saves the cursor, and re-enqueues itself. This gives jobs from other tenants a chance to claim the worker.

Overall, the interruptible iteration strategy is somewhat orthogonal to fairness. You’ll probably want resumable jobs regardless of which fairness strategy you choose, because long, monolithic jobs are simply risky and cumbersome.

But it could also solve our fairness problem because by processing each batch sequentially, we limit the execution to a single worker, and by time-bounding that execution, we prevent that batch from holding the worker indefinitely.

However, if one tenant can submit many large batches at once, their jobs can still occupy every worker and crowd out everyone else. Limiting each tenant to one active batch prevents that, but if we have more workers than active batches, some workers will sit idle. So, this strategy works well when the workload naturally comes in batches and there are enough active batches to keep the worker pool busy.

Strategy 3: throttling

Unlike the two strategies above, throttling targets fairness directly. It does so by punishing greedy tenants: we detect when a tenant is being greedy, then route their excess jobs into a slower queue.

How do we detect greediness? My favorite mental model is the leaky bucket algorithm.

Picture a bucket with water flowing in and leaking out. Water leaks at a configured rate. While the bucket has capacity, we can pour water in bursts or at a consistent rate. Once it fills, any additional water spills over.

Now, suppose tenants pour water by enqueueing jobs (say, one job equals one liter of water). Before enqueueing a job, we check whether there is enough capacity in that tenant’s bucket. If there is, we send the job to the main queue. If the water would spill, we send it to the slow queue.

Then we can configure Sidekiq to poll the main and slow queues like this:

bundle exec sidekiq -q main,4 -q slow,1

With those weights, Sidekiq checks the main queue four times as often as the slow queue.

Unlike in shuffle-sharding, all workers process both queues. If the main queue is empty, those same workers can drain the slow queue at full capacity. As long as either queue contains jobs, we don’t leave workers idle simply because they were assigned to the wrong queue.

I won’t go deeper into the implementation here because we already have an article explaining this approach and presenting a gem that implements it for Sidekiq. It uses Redis sorted sets and sliding time windows instead of leaky buckets, but the overall idea is the same.

I’ll only mention that throttling has two catches, both related to the fact that it approximates fairness at enqueue time.

First, bursty workloads are hard to judge fairly. One tenant may place 100 orders in a day, then go silent for a month. Another might place 10 orders every day for that entire month. If your threshold treats more than 10 orders on any single day as greedy, you punish the first tenant even though they submit less work over the month.

Second, once a job is routed to the slow queue, it is stuck there until processed. If the tenant stops being greedy later, the already-throttled work does not magically move back.

However, if your tenants’ workloads are fairly consistent over time—even if some tenants submit more work than others—throttling is a strong fit. It is simple, scales amazingly well (especially with leaky buckets), and avoids the underutilization problem.

Strategy 4: per-tenant queues + custom scheduler

The previous strategies have something in common: they scale well, but they are imperfect. They improve fairness for specific workloads, yet each has edge cases. If we want a universal solution—one that can enforce our definition of fairness across workload shapes—we need something more radical: a scheduler. In other words, we need to hire a manager.

Let’s go back to the pizza story. Instead of sending every order straight to the kitchen queue, suppose we hire a manager with a ledger. Every incoming order goes into that ledger first. The manager watches the shared kitchen queue, sleeps while the chefs have enough work, and wakes up periodically to schedule another batch for processing when they are running low.

For the chefs, nothing has changed. In fact, they may not even know they have a manager. They still pull orders from a single shared queue and process orders.

Instead, the burden of fairness now falls on the manager. The manager can be a dictator, play favorites, or treat everyone equally. That’s totally up to them. But we can envision that they implement the ideal fairness strategy we described at the beginning: the ledger holds a virtual queue for each customer, and the manager picks randomly among the active queues, giving each an equal chance.

Now, if that sounds like a potential bottleneck, that’s because it is. But not all bottlenecks are created equal! If the scheduler can push a new batch into the main queue faster than workers can finish the previous batch, then it isn’t the thing that’s limiting throughput.

In my experience, this is often the case for the jobs where fairness matters most: AI workflows making slow HTTP requests, data imports streaming large files, report generation running heavy database queries and compiling PDFs, and media processing. These jobs occupy workers long enough for one tenant’s batch to hold everyone else back.

Some of this work is CPU-bound—for example, media processing with ImageMagick or FFmpeg—but much of it leaves the Ruby process waiting on input/output (I/O). Thus, it’s tempting to think that adding more threads, or using a fiber-based processor such as async-job, would reduce queue latency enough that we could forget about fairness. But look at these jobs from the perspective of the whole system: a self-hosted LLM model may be constrained by GPU capacity; an import may be constrained by cloud storage; report generation may be constrained by the database. Increasing concurrency would simply move the bottleneck down the stack.

As long as the system contains a scarce shared resource, a bottleneck is unavoidable.

At a small to medium scale, throughput is more likely to be limited by that resource than by the scheduler, so the scheduler’s potential bottleneck may not matter in practice.

A typical implementation of this approach looks like this:

• Intercept jobs before they enter the main queue.
• Store each intercepted job in a virtual queue for its tenant.
• Keep track of tenants that currently have jobs waiting.
• Run a periodic planner job, perhaps once a minute.
• Have the planner check the main queue’s latency. If it is already high, the planner goes back to sleep. If it is below a threshold, the planner selects jobs from active tenants according to your fairness policy and promotes them to the main queue.

That policy can be as opinionated as you need: equal weight for everyone, more weight for paying tenants, or a cooldown for tenants that just consumed a large share.

The best part of this design is that it leaves the background processor’s core alone. It needs only a way to intercept jobs before they reach the main queue—for example, with Sidekiq middleware—and access to the main queue’s latency metric. Once the scheduler promotes a job, the processor remains responsible for execution, retries, and crash recovery.

Another advantage is how straightforward it is to reason about. We have only two main knobs: how often the scheduler wakes up to push the next batch and the size of that batch.

If we see resource underutilization, each batch is being processed before the scheduler promotes the next one. In that case, we can make the scheduler wake up more often. We only need to ensure that it can finish planning before the next wake-up. If it cannot finish within that shorter interval, we can keep the current interval and increase the batch size instead. If calculating tenant weights is the expensive part, promoting two jobs per tenant instead of one can roughly double the amount of scheduled work without doubling the planning time.

There is a limit. As the number of active tenants grows, the planner takes longer to make its decisions. To keep workers busy, it must promote larger batches, and those larger batches compromise fairness: a newly active tenant has to wait behind more work already sitting in the main queue. At that point, it may be time to switch to one of the more scalable, workload-specific strategies above.

Still, I suspect this design can stretch quite far. If the planner runs once a minute, how many active tenants does it take before the planner cannot decide what to pull within a minute? Quite a lot, I would think. This is the approach that worked best for me personally. I tried the alternatives; this one held up, and we did not run into scaling problems in practice. But your mileage may vary.

Choosing a fairness strategy

We have explored four strategies, each with its own trade-offs and suitable workloads. There are also many variations on these ideas. None is universally best.

If you ask me where to start, I would try per-tenant queues with a custom scheduler first. It is the most flexible option, and it was the only one that consistently worked for me in practice. I would choose something else only if I already had reason to believe the planner could not handle the number of active tenants.

In that case, look at the shape of your workload:

• If you have many active tenants and occasional hogging is tolerable, try shuffle-sharding. It isolates most tenants while accepting that an unlucky few may still share a busy shard.
• If work naturally arrives in large batches, try interruptible iteration. Limit how many batches a single tenant can run concurrently and time-bound each batch’s execution to free worker capacity for other tenants.
• If tenants enqueue jobs at a consistent rate rather than in large bursts, and you mainly need to slow down the greedy tenants, try throttling. It scales well and is straightforward to configure.

Whichever strategy you choose, don’t ignore the problem. Once queue latency becomes visible to users, fairness stops being an abstract scheduling concern and becomes part of the product experience.

A large customer should be able to place a large order. But a small customer should still be able to get that one slice. Design for this before the queue backs up, and you have a much better chance of never turning that customer away.