Algorithm to limit the speed of processing items

Question

I need to process a large number of data items, and I need to restrict the speed at which they are processed. For example, not more than 20 items per minute.

I've thought about an algorithm for that, where I'd keep a list with the time when each past item was processed, then I can know how many more I can process at a given time.

However, this is not very elegant since I need to manage this list. I'm wondering, is there any known algorithm that handles this problem?

Edit:

To answer the comments: processing should be as fast as possible. And it's 1-minute intervals no matter when they start. I will be sending data to a server, so the goal is not to overload that server. However, the faster the processing can be done the better.

Answer 1

I will be sending data to a server, so the goal is not to overload that server.

Then let that server give back a signal when it's ready to get more data.

If there is a error message it replies with when overloaded then you can do a dynamic throttling. You send completed packets to the server until one fails, then you wait x time (and throttle the computation by not letting more items be computed until the send queue is no longer full) and try sending the packet again and continue sending completed packets.

This has the advantage that if you ever upgrade the receiving server you don't need to adjust the (hardcoded) throttle.

Answer 2

Let's assume that each Task (data item related processing task) ends in a queue on your server. In order to get your 20 jobs per minute in an easy way, you could set up a recurring task, which every minute pulls maximum 20 items from the input queue and places them into a processing queue, which is then being processed by 1 or more threads.

How you do that depends on your ecosystem and programming environment. In F#, for example, you could use the MailboxProcessor<> from FSharp.Control namespace to create an actor style of solution, doing just that. On C#, you could use the Task model. On Pony (yes, that is also a programming language ;) ), you could use actors (as all you do there, is to use actors). In rather low level C/C++ environments, you could allocate a small pool of threads (1..a fraction of the number of your servers cores), which then draw their tasks from the processing queue (work stealing). And so on.

This still produces load spikes on your server, since every minute it will aggressively work on the tasks of processing the scheduled items.

If you want to get a more balanced background load within the 1 minute time frame, you need to take more details about your processing code into account. If, for example, the time to process 1 item is rather a constant and not varying much in processing complexity, you could do some dynamic estimation of the processing time for 1 item and then draw your 20 items from the input queue, only to schedule a fraction of them every 60/20=3 seconds (some previous tasks might still be running, given that your server also has other stuff to do and its workload is not constant). How many to schedule is then the objective of the estimator.

The last remaining problem to worry about is back pressure. If you hard limit the processing rate of items, but the influx of new tasks is out of this servers control, your input queue will grow unboundedly. So, rather, I would try to throttle processing more or less, depending on the length of the input queue. Or add actual back pressure to the client/server communication. For example, have your server request 20 items every minute (in a batch) instead of having the client send to the server whatever they want.

Unless this is a kind of research project or there are other compelling reasons, I would not consider to get all too sophisticated on this problem. The keep it simple approach saves you time, lines of code (and as such, potential bugs) and in extreme cases the funny looks of your coworkers (if you went overboard with your solution).

If you actually program the client side (and not the server side as I assumed above) and if your server code made bad life choices (no back pressure in the protocol), you can still do what I described above to get your throttling. What I called input queue above would now be your output queue. And your task which is scheduled once per minute now simply draws max 20 items from the output queue and sends it as a batch to the server.

Answer 3

Given that you want to start processing as soon as the time constraint lets you (instead of starting processing in 20-item bursts and waiting a minute in between), you could use two queues, a small blocking queue and a larger queue of waiting elements.

The small queue is a blocking queue that keeps a rotating log of the last twenty items that were taken from the queue with timestamps. Every time an element is taken from the front of the queue, the current timestamp is added to the log and the oldest entry removed. Putting new elements into the queue is blocked until the oldest entry in the log is at least 60s in the past. The processing server takes an element from this queue whenever possible.

The larger queue accepts lots of inputs (unbounded queue if you want to process every input eventually, but you could also set a maximum capacity or deny adding new elements based on expected waiting time or something). A transfer job takes elements from the waiting queue, puts it into the small queue or blocks until it is possible to do that (which by design of the small queue ensures your time constraint).

Advantage of using two queues: You can scale up the backend by using more processing servers, each with its own time constraint, its own small queue and own transfer job. The larger queue in front then acts as a load balancer.

Answer 4

Keep it simple

You shouldn't need any additional queues or data structures beyond the ones you have already devised to handle the queue of items and the logic to process them. Just stick a Sleep statement (or its equivalent in your language) somewhere in your main loop, and make it configurable.

Unless there is some NFR that I'm missing, there is no reason to make it any more complicated than that.

My answer would be different if you were doing high volume, needed precisely 20 items in exactly one minute, or if your system required a very high availability level. Otherwise, Keep It Simple Stupid.

Answer 5

ratchet freaks answer is probably the best option, but to add a bit more detail..

If the goal is to be nice to the server or its other clients, the server can best tell you when it's under stress. But, the first step in the backed should simply be job prioritization and queuing. If the server knows your work isn't as latency sensitive as other jobs, it shouldn't generally matter how often you submit jobs; they'll be bumped down in priority (delayed) as needed.

In the worst case, the server can actually issue an HTTP 429 (too many requests).

All that said, if this isn't feasible for you on the server side, the simplest and most scalable client side solution would be to insert a small delay between each request. Ideally, use a delay that is proportional to request processing time and "how nice" you're trying to be for the server... It may not result in 20 jobs per minute, but you'll know for certain that you're leaving the server alone at least P% of the time.

P is simply a number you can pick and use to delay requests as a function of the most recent request time. (Or as a rolling average, or whatever.)