Fair Queuing

Eventually you need this

As any application evolves, it is eventually recognized that prioritization in a queue is not enough. Low level kernel developers learned this decades ago, but it's strangely missing from almost every job queuing platform available.

Conceptually, queuing always starts out the same way, when you can't perform an operation in real-time, you need to store those jobs to be done ASAP. So you put them in a queue. Then you realize that some operations are more important than others, so you add prioritization to help identify jobs that need to get done Now vs Later. At some point, you get enough jobs that you realize that your queue is full of jobs that are equally important, but some clients are being starved because the other clients got their 1 million items in the queue before anyone else, and so now a client has to wait a long time before even getting 1 job. This is where fair queuing comes in.

Fair queuing is about adding some sense of scheduling to queues, so that one client does not dominate the queue, and all clients have a fair chance to get a job to work on.

There are many different algorithms for providing this type of scheduling. In an ideal world, you would just have N queues for N clients, and you would round robin between those N queues. This becomes unwieldy when you start having thousands of clients or queues. AllQ (behind the scenes) uses a form of stochastic fairness queuing which takes a user provided "shard" key, and builds a hash based on that shard key, and stores jobs in queues based on that hash. This provides a way for there to be a finite number of queues, and still provide a statistically fair queuing algorithm (for jobs of unknown length).

Most of the complexity is hidden from the client in AllQ, and the fair queuing can all happen behind the scenes (and with configurable options via ENV variables)

Last updated