A batch spreads one fixed charge over B items, so the per-item cost F/B + v falls like a hyperbola onto a floor at v. Filling the batch makes items wait, and that wait rises linearly with B. Two curves in opposite directions, and no B that is best at both.
Core ideas
The cost curve is the interesting one, because the shape of a hyperbola is what makes “bigger is better” stop being true long before the cost stops falling.
F is paid once per batch whatever is in it: a request, a round trip, an fsync, a commit. Spread over B items it is F/B each, so the first few doublings of B are enormous — 2 100 µ$ at B = 1 becomes 1 100 at two and 300 at ten. v is paid per item and batching does not touch it at all.
F/B + v is a hyperbola sitting on v = 100 µ$. At B = 100 the item costs 120 µ$, so the entire remaining saving available at any batch size whatever is the 20 µ$ still in the F/B term. Going to B = 800 recovers 17.5 of that 20 and costs just over eight times the wait. The curve flattening is not a feature of this example; it is what a hyperbola does.
Items arrive at λ a second, so the first item in a batch waits for the other B − 1 to arrive: (B − 1)/λ, which is 198 ms at B = 100 and λ = 500. Averaged over the batch it is half that, 99 ms. The familiar B/λ is the rule of thumb and it overstates the first item’s wait by exactly one inter-arrival time, 1/λ = 2 ms, at every B.
The material
What each curve does, the two exact waits against the rule of thumb, and where the exact optimum lives when you are prepared to price the latency.
Let F be the cost charged once per batch and v the cost charged per item. For a batch of B items the per-item cost is
F/B + v,
which is strictly decreasing in B, is bounded below by v, and reaches v only in the limit.
The two facts worth carrying are that it always falls and that it never reaches the floor. Together they mean there is no batch size at which the cost stops improving, and therefore no batch size that a cost argument alone will ever choose. Something else has to stop you, and that something is the wait.
Read the last two rows against each other. Going from B = 100 to B = 800 saves 17.5 µ$ an item — a further 14.6% — and multiplies the wait by eight. Going from B = 1 to B = 100 saved 1 980 µ$ an item, a factor of 17.5, for 99 ms. Same curve, and the two ends of it are not remotely the same trade.
With Poisson-free, evenly spaced arrivals at rate λ and a batch that closes when it is full, the k-th item to arrive waits (B − k)/λ for the batch to fill. The first waits (B − 1)/λ, the last waits nothing, and the mean over the batch is (B − 1)/(2λ).
B/λ is what gets quoted, and it is the time to collect B items rather than the time any item spends waiting. The difference is one inter-arrival time and it does not shrink as B grows: at λ = 500 it is 2 ms at every batch size. At B = 100 that is 200 ms quoted against 198 ms actual, which is a one per cent error; at B = 2 it is 2 ms quoted against 2 ms actual for the first item and 1 ms on average, which is not.
A batch that closes only when full stalls forever if arrivals stop, so real systems close on whichever comes first: B items, or a timer of T. The timer bounds the wait no matter what the traffic does; the size bounds it when traffic is heavy. At λ = 500, B = 100 and a 200 ms timer the size wins, which is why the wait in the table is the fill wait rather than the timer.
“Choose B where the curve flattens” is a judgement, and the lab makes it a reproducible one by naming the threshold: it picks the smallest B at which the fixed share F/B has fallen to a stated fraction of v. At twenty per cent of v = 100 µ$ that is F/B ≤ 20, so B = 100. Stating the threshold is what turns a judgement into something a second person can check.
It is still a judgement, and there is an exact answer available once you are willing to price the latency rather than merely observe it. Give waiting a cost per item-second and the total becomes fixed cost per item plus holding cost per item, which is the economic order quantity — minimised in closed form, with no calculus, in “The EOQ Formula Without Calculus” in the Operations Research course “Inventory Models”. Latency plays the holding cost’s part exactly.
A storage engine that calls fsync once per commit pays a fixed charge per call and amortises it across whatever transactions are waiting; the transactions wait for the group to form. That is F/B + v against (B − 1)/(2λ) with different units, and it is priced in “fsync and Group Commit” on “Storage Engines and Indexes”. Recognising the shape is most of the value of this lesson: it recurs at every layer that has a per-operation charge.
One warning about the floor. If v is large relative to F, batching is nearly pointless however large B gets: the curve starts close to its floor and has nowhere to fall. The quantity that decides whether batching is worth designing for is F/v, and it should be computed before the batch size is argued about.
Interactive
One curve down, one curve up, and no B that is best at both
Method
Compute the ratio that decides whether batching helps at all, then pick the size against a stated threshold.
It is the whole size of the prize. At F = 2 000 µ$ and v = 100 µ$ it is 20, so batching can take an item from 21v to v — a factor of twenty-one is available. If F/v is a half, close the question and go and find a different cost.
The shape is the point, and one row cannot show it. Four or five rows make it obvious where the curve stops paying, and keeping F/B as its own column shows exactly how much saving is still on the table.
“The fixed share is down to a fifth of v” gives B = 100 here, reproducibly. Any rule will do as long as it is written down; what does not work is stopping where the curve looks flat, because that is a property of the axis scale.
(B − 1)/λ and (B − 1)/(2λ). Report the first-item figure — 198 ms here — because it is the one a percentile sees, and note that B/λ would have said 200 ms.
If the timer fires before the batch fills, the wait is the timer and the per-item cost is worse than the table says, because the batch closed short. At λ = 500, B = 100 and a 200 ms timer, the size binds and the timer is insurance.
The threshold used here is that the fixed share falls to a fifth of the variable cost. It is stated first so that the batch size is a consequence rather than a preference.
The still on the table line is the one that settles the batch size. Whatever B you choose above one hundred, the most it can save is 20 µ$ an item, because that is all of F/B that is left. The wait, by contrast, has no ceiling at all — it is linear in B forever.
The last block prices the temptation. B = 800 is genuinely cheaper, by 17.5 µ$ an item, and it makes the first item in every batch wait 1.6 s. Whether that is a good trade is a question about the service, and it is answerable only because both numbers are on the page.
For a faded attempt, set F = 500 µ$, v = 250 µ$ and λ = 200/s. Compute F/v and predict from it alone whether batching is worth much here. Then apply the same threshold, compute the per-item cost and both waits at the B it gives, and check against the lab.
You should be able to compute F/v and say how much batching can possibly buy, tabulate F/B + v across several B, name the threshold you stopped at, and report the first-item and mean fill waits alongside the rule of thumb they differ from.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.