skip to content

A nightly fold over transactions was split across workers and its total now varies per run - what property is missing?

level: seniorimportance: should knowfreq 50%

answer

  1. regrouping must not change the answer
  2. chunk boundaries became visible
  3. associativity, not commutativity
  4. the seed is applied once per chunk
  5. binary floating-point addition regroups badly

basics

~20 s

Associativity. Splitting a fold regroups its combinations, and only an associative combining step gives the same answer under every grouping. Varying totals per run mean the chunk boundaries or the merge order are moving and the step can see it.

solid answer

~50 s

A sequential fold fixes one grouping: `(((z + a) + b) + c) + d`. Chunking it computes `(z + a + b)` and `(z + c + d)` separately and merges them, which is a *different* grouping of the same operands. The result survives that only if the step is **associative** - regrouping is unobservable. Commutativity is a separate property and is not required, as long as partial results are merged in chunk order; it becomes required only if merges land in whatever order finishes first. Two more things have to hold: the per-chunk seed must be the merge's identity, or it is injected once per chunk instead of once overall, and a step whose accumulator type differs from the element type needs a two-function form - accumulate an element into an accumulator, plus an associative merge of two accumulators. A run-to-run variation usually means either a non-associative step, such as binary floating-point addition, or a merge order that is not pinned.

code

pseudocode · 12 lines
pseudocode
partials = []
for each chunk in split(transactions)
    partials.append(fold(chunk, emptyTotals, accumulate))

// merged in chunk order, so merge need not be commutative
result = emptyTotals
for each p in partials
    result = merge(result, p)

// required: merge is associative, emptyTotals is its identity
// merge(merge(x, y), z) == merge(x, merge(y, z))
// merge(emptyTotals, x) == x

go deeper

for a junior

Know that splitting a fold across workers regroups its combinations, and that the answer only survives if regrouping does not change the result.

for a middle

State associativity and commutativity separately and say which one splitting needs, then show a step that is associative but not commutative and explain why it still splits.

for a senior

Diagnose the reported symptom in order: regroup a fixed input by hand, compare a one-chunk run with a four-chunk run to expose a repeated seed, check whether merge order is pinned, and check the accumulator's numeric representation.

for a principal

Make the property a reviewable contract: any job intended to be distributed declares its merge function, its identity, and a test that regroups a fixed input, so the decision to parallelise is not an implicit bet on someone's arithmetic.

## What splitting actually changes Run sequentially, a fold commits to one grouping of its operands: ```pseudocode (((seed + a) + b) + c) + d ``` Split across two workers and merged, it commits to another: ```pseudocode ((seed + a) + b) merged with ((seed + c) + d) ``` The operands are the same and their order is the same. Only the **bracketing** moved, plus - importantly - the seed now appears twice. So there are exactly two questions to ask of any fold you want to split, and they are separable: 1. Is the combining step **associative**, so that regrouping cannot be observed? 2. Is the seed the step's **identity**, so that applying it once per chunk is the same as once overall? Fail the first and the answer depends on where the chunk boundaries fell - which is precisely a total that changes when the worker count, the input size or the scheduling changes. Fail the second and the answer is off by a fixed multiple of the seed. ## Associativity is the one you need; commutativity usually is not They are different properties and conflating them is the most common mistake in this material. | Property | Statement | Needed to split a fold? | |---|---|---| | Associativity | `(x + y) + w` equals `x + (y + w)` | **Yes**, always - splitting regroups | | Commutativity | `x + y` equals `y + x` | Only if partials merge in arbitrary completion order | Concatenating text or appending collections is associative and **not** commutative, and splits perfectly well as long as the partial results are merged left to right in chunk order. Averaging a running value with each element is commutative in its two arguments and **not** associative, and cannot be split at all. If the merge step consumes partials as they finish - first worker home wins - then order is no longer under your control and commutativity becomes a second requirement on top of associativity. ## The near-associative trap The nastiest version of this defect is a step that is associative in mathematics and not in the machine. Binary floating-point addition rounds after every operation, so the rounding error depends on the grouping; regrouping the same amounts changes the last digits. A reconciliation that agrees to the cent on small inputs and drifts on large ones, differently on each run, is the signature. The fixes are structural rather than clever: accumulate in a fixed-point or integer representation of the smallest unit, or pin the chunking so the grouping is at least reproducible. ## When the accumulator is not the element type A totals record is not a transaction, so there is no single step of the form `(x, x) -> x` to be associative about. The splittable form of such a fold needs **two** functions: - **accumulate**: `(accumulator, element) -> accumulator`, used inside a chunk; - **merge**: `(accumulator, accumulator) -> accumulator`, used to combine chunk results. The property that has to hold is that **merge** is associative and that the empty accumulator is its identity, and that merging two accumulators gives the same answer as having accumulated both chunks' elements into one. Reviewing that relationship explicitly is the practical version of this question, because it is where real bugs live: a merge that adds counts and takings correctly but keeps only the left side's largest sale, or that concatenates two collections whose order then depends on which worker finished first. ## Diagnosing the reported symptom Given "the nightly total varies per run", the useful order of checks is: 1. **Is the step associative?** Regroup a small fixed input by hand two ways and compare. If they differ, stop - the split is invalid, not flaky. 2. **Is the seed the merge's identity?** Compare a one-chunk run against a four-chunk run on identical input; a difference that is an exact multiple of the seed names the cause. 3. **Is the merge order pinned?** If partials merge on completion and the step is not commutative, the total follows the scheduler. 4. **Is the accumulator representation exact?** Near-associative arithmetic drifts without any of the above being wrong. Note what is *not* on the list: adding a lock. Mutual exclusion fixes interleaved updates to shared state; it does nothing about grouping, so a pure non-associative step protected by a perfect lock still returns a different number when the chunk boundaries move. ## Why this is the senior version of fold The junior question is what a fold does. This one is the reason the functional vocabulary is worth anything operationally: a fold whose step is associative with an identity seed can be cut into pieces, run anywhere, and merged in any bracketing, and the answer is a property of the data rather than of the schedule. Everything about distributing the work rests on that one algebraic property, and the property has to be checked, not assumed.

  • Does the combining step also have to be commutative?
    Only if partial results may be merged in whatever order they finish. If the merge walks the partials in chunk order, associativity alone is enough - concatenating text is the standard example: associative, not commutative, and perfectly splittable.
  • The accumulator is a totals record and the elements are transactions - what exactly must be associative?
    Not the per-element step, which has no matching types to regroup. You need a second function that merges two totals records, and it is that merge which must be associative with the empty record as its identity, and must agree with having accumulated both chunks into one.
  • Would a lock around the shared accumulator fix the varying total?
    No. A lock serialises updates and removes interleaving, but the grouping still depends on chunk boundaries and completion order. A non-associative step under a perfect lock still gives a different total when the worker count changes.

saying these in an interview costs you the question

  • Says the step must be commutative in order to split the work
  • Applies a non-identity seed to every chunk
  • Assumes binary floating-point addition is associative
  • Thinks a lock makes any combining step splittable
  • Cannot say what changes when the chunk boundaries move
  • Calls a grouping-dependent total a flaky test