skip to content

A total over a billion amounts differs in its last digits between two runs over the same input — what explains it?

level: middleimportance: should knowfreq 46%

answer

  1. no promised order for combining partials
  2. every addition rounds to the nearest representable value
  3. a small value absorbed by a large total
  4. width and local folding change the grouping
  5. integers in minor units, or a tolerance

basics

~20 s

Partial results were combined in a different order, and each addition in the usual binary floating-point format rounds. Nothing ever promised a combination order, so the two totals are both correctly rounded and simply not the same number.

solid answer

~50 s

Splitting an aggregate across workers means each piece produces a partial result and those partials are then combined. The engine never promised an order for that combining, and in binary floating-point arithmetic the rounding at each step depends on what is added to what — so a different grouping of the same values gives a slightly different total. What changes the grouping between runs is ordinary: the step width, whether a local fold happened before records crossed the network, and which partial reached the combining worker first. Neither total is wrong; each is correctly rounded for the order it used. The repairs are to change the representation — integer minor units, or an exact decimal type — or to state a tolerance and compare within it. Whether a parallel reduction *requires* an associative combining operation at all is a different subject; here the point is only that the order was never promised.

code

python · 4 lines
python
a, b, c = 1e20, -1e20, 1.0

print((a + b) + c)   # 1.0  -> the two large values cancel, then 1.0 is added
print(a + (b + c))   # 0.0  -> 1.0 is absorbed by the large value, then they cancel

go deeper

for a junior

Recall that fractional values are stored approximately and that adding them in a different order gives a slightly different total; a distributed total does not fix an order.

for a middle

Explain the mechanism: partials are combined in an order nobody promised, each addition rounds, and step width and local folding change which values met which.

for a senior

Show that you check the record multiset first, then decide between changing the representation and stating a tolerance — and that you look for a threshold the drift could flip.

for a principal

Set the rule for the platform: which quantities are exact types by policy, what tolerance a cross-system reconciliation is allowed to assert, and who owns that bound.

## What is actually differing Two executions read the same records and produce totals that agree to eleven digits and differ in the twelfth. Nothing was lost and nothing was double-counted — check that first, because a genuine row-count difference looks the same from a distance. Once the multiset of input records is confirmed identical, what is left is arithmetic. ## Rounding happens at every addition The number format almost every runtime uses for a fractional value stores a fixed number of significant bits. Two consequences follow: - most decimal fractions have no exact representation, so a value is stored as the nearest representable number; - **every** addition rounds its result to the nearest representable number, which means adding a small value to a very large one can change nothing at all — the small value falls below the spacing between representable numbers at that magnitude and is absorbed. Because each step rounds, the total depends on **which values met which**. Add the small values to each other first and they survive as a real amount; feed them one at a time into a huge running total and they vanish. ## Why the grouping changes between runs A distributed aggregate never adds values in one sequence. Each piece of the input produces a partial result and the partials are combined. What determines the grouping is: 1. **the step width** — how many pieces the step processes at once, which sets how many partials there are; 2. **whether a local fold happened before the network** — many engines combine within a worker before sending anything, and some do not, which is a completely different tree of additions; 3. **the arrival order of the partials** at the combining worker, which follows completion timing; 4. **any adjustment the engine made to the not-yet-run part of the plan** from measurements of finished work, which can change the number of partials mid-run. None of those is stated in the program, so none is promised — and each changes the total's last digits. ## Where engine models differ - A **two-phase disk-handoff model**, which runs one grouping step at a time and writes every intermediate to disk before the next begins, has a comparatively rigid combining structure, but the order partials are read back in is still not a contract. - A **continuous record-at-a-time model** folds into a running accumulator as records arrive, so the combining order follows arrival and is not reproducible at all across runs. - A **repeated-small-batch model** produces a partial per small job and then combines across them, adding a layer of grouping that moves with timing. So "the total is stable if the input is stable" is true of no engine in this class, but it is untrue for slightly different reasons in each. ## When the last digits actually matter Most of the time they do not, and a report quoting two decimals is unaffected. They matter when: - a **threshold** is compared against the total, so a drift of one unit in the last place flips a downstream decision from one branch to the other; - a **reconciliation** asserts exact equality against another system's number, and fails on a difference that means nothing; - the magnitudes are **wildly different** — a running total in the billions accumulating individual cents — where absorption is not a last-digit effect but a systematically lost amount; - the aggregate is **not a plain sum**: a variance or a sum of products amplifies the same effect. ## The repairs, in order of preference 1. **Change the representation.** Money is the common case and has an exact answer: hold amounts as integers in minor units, or use an exact decimal type. Integer addition does not round, so the total is the same whatever order the partials were combined in. 2. **State a tolerance.** Where the quantity is genuinely a measurement, assert the comparison as an absolute or relative bound rather than exact equality, and record the bound in the check so nobody tightens it by accident. 3. **Reduce the dynamic range.** Aggregating within groups of similar magnitude before combining across them keeps small values from being absorbed. This is what a local fold before the network does for you incidentally. 4. **Do not reach for a single-process sum.** Pulling a billion values into one process does fix the order, and it also throws away the reason for the cluster; use it as a one-off cross-check, never as the design. ## The claim to make The honest statement is not "the job is deterministic" but "the job produces the same rows, with numeric aggregates equal within a stated bound" — or, once the amounts are integers, "equal exactly". Say which before anyone compares two runs.

  • Would pinning the number of pieces make the total reproducible?
    It narrows the variation without removing it. The number of partials becomes fixed, but the order they reach the combining worker still follows completion timing, a recomputed piece still changes that order, and any runtime adjustment of the plan can change the count anyway. Pin it if you are chasing a difference, but do not sell it as exactness.
  • The amounts are currency. What is the right fix?
    Hold them as integers in minor units — cents rather than dollars — or use an exact decimal type, and keep them in that form through every aggregation. Integer addition does not round, so the total no longer depends on the order the partials were combined in, and the reconciliation can assert exact equality honestly.
  • Why does an average drift more than a plain sum?
    Because it compounds two operations: a sum whose rounding depends on combination order, then a division whose result magnifies any difference already present in the numerator. Quantities built from squares or products — a variance, a weighted total — are worse again, since the wider spread of magnitudes makes absorption more likely.

A scale that only shows whole dollars. Weigh a truck, then put one cent on it: the reading does not move — the cent is absorbed because it is smaller than the smallest change the scale can show. Collect a million cents into a bag first and weigh the bag, and you have ten thousand dollars. Same money, two answers, and the difference is only which things were added together before the reading was taken.

saying these in an interview costs you the question

  • Concludes records must have been lost or duplicated.
  • Says floating-point results are simply random at the last digit.
  • Claims fixing the piece count makes the total exact.
  • Rounds inputs to two decimals and calls the error removed.
  • Asserts exact equality in a reconciliation over measured values.
  • Treats the drift as harmless without checking for a threshold.