Skip to content

Fairness in background worker queues

Created by: eseliger

We started introducing background workers a while ago, to offload heavy lifting from request paths and to better manage all our background tasks. This is super helpful and has matured well since its introduction. As we start having more workloads there, it becomes imminent that we sometimes run into fairness problems.

  • Code intel uploads are sometimes not processing for a while, because the sourcegraph/sourcegraph repo sometimes fills the queue with lots of jobs
  • Code intel auto-indexing jobs don't run in a "fair" order, just by creation date. If someone triggers 1000 index jobs for their repos on various branches manually, they will take the executor resources for all users of Sourcegraph for a while
  • Batch changes reconciler runs FIFO, if someone starts a batch change with 500 changesets, they all need to process before user B's first changeset even starts processing
  • SSBC executions easily add hundreds of jobs into the batches executor queue, if user A starts one of these executions, user B needs to wait for ALL the jobs from user A to finish before their first job even starts
  • .. and more examples, which I don't all want to capture here, but you get the idea.

Instead, we should have a more sophisticated dequeueing algorithm, that is more "fair". The ideal end state of this would be: a "fairness group" (TBD) can always have a job start as soon as they queue it, when it's tip of their individual queue. In executor terms that means: We always hold so many executor workers warm that the time between "job record becomes tip of individual queue" and "started_at is set (is dequeued)" is close to 0s. We will need to find good values for the fairness triggers as we go and constantly adjust until we come close to the desired end state.

Some considerations for fairness:

  • We introduce "fairness groups". These could simply be namespaces, or just users.
  • We introduce a maximum concurrency per fairness group
  • We do a round-robin of all requesting fairness groups so that ideally every fairness group can always have at least 1 job running
  • Later we could also limit the maximum amount of jobs in a given time frame (leaking bucket) so that users can have rather high concurrency but not for an entire hour in a row

This needs to be implemented

  • in the dbworker Dequeue method
  • in the rank virtual field on records, so we can return placeInQueue in the API. This should be per individual "fairness group" queue, rather than global. We might want to have a site-admin-only globalPlaceInQueue for debugging purposes.

To experiment with fairness, we want to

  • Make maximum concurrency configurable
  • Make maximum concurrency overwriteable per sub-queue
  • Make this an opt-in feature per workerutil.Worker
  • Have a graph/metric to track the dequeue time for tip of queue for each sub queue

In the future, we might allow executors to attach to these "sub queues" for a single fairness group. (Global vs scoped executors). Also, we might want to experiment with "high priority items", ie. user-invoked vs background-job-invoked.