Global rate limiting to hit an API from workers that live on multiple machines?

Question

I have to design a system where an API has to be hit to get the meta info about some data. We have multiple workers, that take jobs from multiple queues. Now the API has a rate limit of say 500 per minute.

Since we are using python, so getting the interpreter lock and wait for the time interval won't work as workers here are on different machines.

I have to ensure that workers running on different machines, globally don't exhaust the rate limit of the API.

Few things that affect the design are that this data comes in bursts, like 20,000 30,000 at a time. Multiple workers can pick jobs that process each burst of data and should not exceed the API rate limit.

Research Done :

So, while researching, the most applicable solution I found was to use an implementation of leaky bucket algorithm. Where the system makes requests at constant rate irrespective of the bursts of input.

It is not applicable as it is, because of multiple workers.

Proposed Solution :

Here is a solution that I've come up :

It is a variant on leaky bucket algorithm that also uses a distributed cache lock.

1. An input burst comes
2. A worker picks the data (say 20,000 items)
3. Get a lock by setting a cache key in the cache server.
4. Performs leaky bucket algorithm over these 20,000 items by hitting the API at a constant rate within the limit.

5. When done, releases the cache key lock.

6. If another bursts comes, while the previous burst was being processed and is picked by a different worker.

7. It checks that the distributed cache lock has been acquired, and thus gets added back to the queue with a back-off of 5 minutes.

This way we ensure that only one worker is hitting the API at a time with the allowed rate.

By batching the items, they can be efficiently updated to the data in a single query also.

How to implement the above system in the most robust way possible given the factors? And what can be the improvements in the proposed solution?

Answer 1

The approach you should take will depend on how fast the non-api dependent work is.

• If a worker waits on the api. ie completes the other work before the rate limit interval is over

Simply have a single queue and a single worker.

• If the worker takes longer than the api interval to process an item. but the api requests are known in advance of the work.

Make the api requests with a single worker. processing one batch at a time and storing the results. Have multiple workers processing the non api limited work and using the results from the api worker.

If you split the api request across batches you will slow down or prevent batches being completed. Your strategy should prioritise the most important batches and work on them first.

• If the non-apu work is slow, but api request is not known untill that work is complete.

Have multiple workers running against the priority batch and storing the required api requests.

Have a single api worker processing the stored api requests and finishing off.

• Flaws in your solution

Your proposed use of a cache server as a locking method is brittle. If the batch worker crashes without releasing the lock, all work will stop untill the cache expires.

Similarly, if the cache expires or the cache server restarts a random worker will start and block the partially complete batch.

Further more, you waste processing time by having workers sitting around waiting. when they could be assisting with the non api work.

If the non-api work is fast then your existing queuing solution already provides a blocking mechanism.