Are there algorithims for polling optimization?

Question

I have a web-application with an async HTTP backend, which gets called by the client by AJAX requests. The client has to start a job and then polls for the result.

I started with a simple 150ms polling interval, which was fine for small jobs, but big jobs, which could take several minutes, threw many failed requests to the server.

Currently, I just add 1000ms to the delay after every poll, so the polling gets slower over time for longer requests, but never longer than 10 seconds.

Are there some formulas, statistics, or algorithms that I could use to dynamically optimize the polling time?

Answer 1

If the server can give a rough estimate of how long a job will take, then I would return that estimate in the first response (the one indicating that the job was received/accepted). The client can then wait at least that time before it starts polling for results.

To avoid flooding a server with unsuccessful polling requests, you might also use a scheme that is often used to send retries over an unreliable protocol: After sending a request, wait a time T before sending a retry. After sending a retry, double the waiting time, until a maximum T2. After success, the waiting time gets reset to its default (minimum) value T1. You could, for example, use the values T1 = 250ms and T2 = 16s

As an example, here is what the polling would look like for a job that is estimated at 2 minutes and runs a little late (network latency ignored):

Time             Action/Reply
----             ------------
0:00.000         Start job. Server responds with a duration of 2:00 minutes
2:00.000         Polling starts. Server responds job still running
2:00.250         First retry. Job still running
2:00.750         Second retry. Job still running
2:01.429             Job finishes
2:01.750         Third retry. Job reported as done.

As you can see, there is some latency in reporting that the job is done, but what is a delay of a few hundred milliseconds if you were already waiting 2 minutes for the job to complete?

Answer 2

This really depends on how much time it takes on average to perform the job and the standard deviation of this time.

Once you know this, you have a good idea about what your minimum and maximum waiting times are for 95% of jobs (2 standard deviations). So I would plan for a minimum polling time somewhere in the vicinity of 2 standard deviation (so that statistically, only 5% of jobs have finished at this point).

From there, it largely depends on you, but ideally you would poll with higher frequency as you approach the norm and then fall off afterwards. I can't tell you at what rate you should poll the server, since you are the one which ultimately determines how much traffic you can support. Have you also considered web sockets?

Answer 3

An alternative option is to use something like long polling or websockets. This way you can replace slamming the server with multiple "is it done yet?" requests with a single "tell me when your done" request