How can I calculate optimal batch sizes for calls to an external server?

Question

So I have a large number of commands, say 500,000, that I want to send and run on a server somewhere else, and get the answers back. All of these commands together takes a long time to execute - roughly 30 seconds. I could group all those commands together and send them off, have the server execute them all, and then get my results. But that's significantly slower than grouping those commands into batches, which I send off all at the same time, and can then execute on that server in parallel.

However, I can't make the batches too small, because I'm doing this from a browser, and most modern browsers can only keep ~6 concurrent open connections with the same server. So you get a trade off - for large batch sizes, I'm not sending enough concurrent commands to the server. For small batch sizes, I'm sending so many that the browser gets backed up.

I've tried this experimentally, and I wind up with data that looks something like this (pardon the terrible drawing):

On the x axis is the number of batches I use, and on the y axis is the time the whole resulting calculation takes. I haven't succeeded in finding a model that really works for this data, only a basic crude approximation.

All I really want to know is, is there research on this kind of thing I can look up? Some way that, given code execution times on the server, and delay times for getting there, I can calculate the optimal batch size? I can't be the only person who's wanted to solve this problem. If there isn't, then what do you think?

Answer 1

Here's the simplest model I can think of. Assume that each command takes $\beta$ seconds to complete, and it takes $\alpha$ seconds to create a connection. Then I would expect that it would take $\alpha+\beta k$ seconds to complete a batch of size $k$. If there are $N$ commands in total, then we'll need $N/k$ batches. With 6 concurrent TCP connections to the server at a time, this means it'll take $N/(6k) \times (\alpha + \beta k)$ seconds to complete all of the batches. As a function of the batch size, this is

$$f(k) = {\alpha + \beta k \over 6k} N.$$

You can find the optimal batch size by finding $k$ that minimizes $f(k)$, which can in turn be done using calculus by taking the derivative and setting it to zero: $f'(k)=0$. Note that

$$f'(k) = {6\beta k - 6(\alpha + \beta k) \over 36k^2} N = {\alpha \over 6k^2} N.$$

Setting this to zero, we find that $f(k)$ is minimized by taking $k$ as large as possible; in the limit we have $\lim_{k \to \infty} f(k) = \beta/6 N$.

Obviously, this is not what you observe empirically, which suggests that this model is not accurate. I suggest as a next step you start to brainstorm why the model might be inaccurate or what factors it might be overlooking. You might also want to measure and plot some additional metrics, e.g., the average time it takes for each batch to complete (as a function of batch size, i.e., the time between starting execution of command 0 from batch $i$ to starting execution of command 0 from batch $i+1$).