0

We are trying to redesign our microservice architecture-based application to support multiple tenants. We have a simple queue service that will be utilized by other services to queue any asynchronous jobs. On the other side individual microservices will poll the queue service to fetch/pick any asynchronous jobs that they can process at frequent intervals (dequeue).

To ensure fairness during dequeuing we are using a simple round-robin algorithm implemented using a circular list in Redis (https://redis.io/commands/lmove#pattern-circular-list). We maintain the service name as the key/list name and all the tenant identifiers as value. This allows us to do a round-robin on a per-service basis whenever a fetch request lands from a particular service. We have used Redisson's Deque data structure (which stores all the Tenants) to iterate over all the Tenants in a round-robin manner.

This approach has a disadvantage. Even the tenants with no jobs (which in our case is higher) are being considered when a fetch request lands and this results in some delay for tenants with jobs.

Instead of adding all the tenant identifiers to the list, we can add only the tenants with jobs as we can identify the tenants when the queueing operation happens. We can remove the tenants from the list during dequeuing. But since our application is multi-threaded we are not so sure on how to handle the concurrency part in Redis i.e there is a possibility that we could remove a tenant from the list just as he gets a new job.

For example, tenant1 was added to the list when a job was queued and during dequeuing just as we issued the command to Redis to remove tenant1 from the list another new job for the tenant1 landed. Now during this new queueing operation for the new job, we will try to add tenant1 back to the list. Due to network latency or the multithreaded nature of the application if the add tenant operation got executed before the remove command and then the remove command would delete the tenant identifier from the list. This would result in tenant1 not being available on the list even though he has a job in the queue.

How can we solve this issue or are there any other approaches that we can consider?

1 Answer 1

1

First of all: you can't have perfect fairness, don't try to build a very complex solution to ensure fairness under all circumstances, it won't work. Keep it simple, that will make it easier to reason about it.

Second, avoid busy waiting/polling. REDIS has blocking operations on lists, these should be used when possible.

If I understand correctly, you have a number of microservices, each serving requests from possibly all tenants.

Starting from the back of the processing flow, I would set up S*T queues where S is the number of services, and T is the number of tenants. Each service would call BLPOP on all its lists, ordered by increasing tenant activity (it needs to keep activity stats but that's simple). That way, each service preferantially processes requests from less active tenants, ensuring fairness on average.

At the job insertion point, you need to decide whether sorting into one of the service/tenant specific queues is done by the tenant or by some dispatcher process that processes a single incoming job queue and places the jobs into their appropriate service queues. As this dispatcher will easily keep up with the incoming job stream, it doesn't need to ensure fairness.

(edit in response to comment)

I'm not sure whether I made my approach sufficiently clear. Let's for the moment only consider one job type, type A. Tenants may be numbered 1 to 10. Tenant 1 would insert its A jobs into list A-1, tenant 2 into A-2 etc.

The A worker knows that it needs to serve 10 tenants, and it performs a

BLPOP A-1 A-2 A-3 A-4 A-5 A-6 A-7 A-8 A-9 A-10 0

REDIS will return a pair consisting of the first queue in which an element was found, and that element. Now the worker decreases its activity gauges for all clients logarithmically (multiply by 0.5^((time_now-time_last)/half_life)) and increases the activity gauge for that tenant by 1.0. It then sorts the tenants (respectively the queue names) by increasing activity gauge, so that the tenants/lists with least activity are checked first on the next access. The factor by which activity is decreased determines the "half-life" of activity. If you choose a lower half-life, the system forgets faster that it has served one tenant a lot lately, while a higher value will make the algorithm remember longer and be somewhat fairer in the long run but with the risk of temporarily starving tenants which had a lot of activity recently.

If all tenants had equal activity until now, the tenant that just got serviced (say tenant 1) will be put at the end of the list of list names due to it having the highest average activity at the moment, so it will only be considered during the next run if no other tenant has work to do (which is fair, why let them wait if nobody else needs your service?):

BLPOP A-2 A-3 A-4 A-5 A-6 A-7 A-8 A-9 A-10 A-1 0

As soon as any other tenant has work to do, it gets served preferentially (and after that it will be put at the end of the queue).

If you dynamically order the queues by recent average activity, each tenant will receive approximately equal service. For example, if you can handle 60 jobs per minute and you have 10 tenants, each will get approximately 6 jobs per minute done, regardless of the pattern in which their jobs arrive, and their queue size. If your total handling capacity is less than the total demand, you will not be able to serve all tenants, regardless of how you distribute service. If there is just a peak load (for example, activity during the first 15 minutes of a workday is much higher) some tenants will need to wait. If you distribute handling capacity proportionally to number of jobs per tenant, every tenant will have to wait approximately the same time until all jobs are done, but if you split processing capacity equally between them only the ones with many jobs are penalized. It's up to you to decide which one is fairer.

To give more service to a tenant that needs it (and possibly pays for it) you may divide the recent activity of that tenant by some factor to service it proportionally more often than the other tenants. But this can't change the fact that when your processing capacity is less than the frequency of job arrivals your queues will grow to infinity, so you should always plan for reasonable excess capacity to avoid growing queues.

1
  • Thanks for the answer @Hans-Martin. We have segregated the queue already based on service and tenant. The approach laid out by you would be something similar to the shortest job first algorithm but the only difference being we always consider tenants with fewer jobs in the queue. But this might lead to starvation for tenants with a huge number of jobs in their queue if tenants with fewer jobs get added to the list frequently. Am I missing anything here?
    – Raghu
    Mar 8, 2022 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.