When does order change a sum?¶

Level: 101 · anyone who has concluded that asynchronous clients cannot change a total, because addition does not care about order

One line: A server that adds up requests one at a time reaches the same total in every order of arrival only while the numbers are integers, every request is applied unconditionally, and each is applied once; floats, a request that can be refused, and a request delivered twice each break it — with no second thread anywhere.

The previous lessons were about handlers running at the same time. This one takes that away. The program below is a server with one thread that handles one request at a time, so no update can be lost, and it tries every order in which the same requests could arrive, then counts how many different totals those orders produce. Asynchronous clients change the order of arrival; if every order gives one total, they cannot change the result.

Verified output of order_py.py — regenerated by tools/run_examples.py, never hand-typed.

integers 5, 10, 20, 40, 80: 120 orders -> 1 distinct total(s): [155]
floats 0.1, 0.2, 0.3: 6 orders -> 2 distinct total(s): [0.6, 0.6000000000000001]
  (0.1 + 0.2) + 0.3 = 0.6000000000000001
  0.1 + (0.2 + 0.3) = 0.6
the same floats, summed with math.fsum: 6 orders -> 1 distinct total(s): [0.6]
a balance that refuses to go below 0, requests +50, -30, -40: 6 orders -> 3 distinct total(s): [10, 20, 50]

one request, +5, delivered twice because the client retried after a lost reply:
  adding every delivery: 20
  adding each request id once: 15

Python stands in for all six languages here, because nothing on this page involves more than one thread. Rust, Go, C, C++ and Java add doubles the same way Python adds floats — IEEE 754 binary64, rounded to nearest. (Not machine-checked here.)

order_py.py

order_py.py in full — pasted here by tools/run_examples.py from the file CI runs.

"""When does the order of arrival change a sum? Every check here tries every
order in which the same requests could reach a server that adds them up, one
at a time, on one thread -- so no update can be lost -- and counts the distinct
totals those orders produce.

    python3 order_py.py
"""

import math
from itertools import permutations


def totals(values, apply, start=0):
    """Every distinct final total, over every order of `values`."""
    results = set()
    for order in permutations(values):
        total = start
        for v in order:
            total = apply(total, v)
        results.add(total)
    return sorted(results)


def report(title, values, results):
    orders = len(list(permutations(values)))
    print(f"{title}: {orders} orders -> {len(results)} distinct total(s): {results}")


def add(total, v):
    return total + v


ints = [5, 10, 20, 40, 80]
report("integers 5, 10, 20, 40, 80", ints, totals(ints, add))

floats = [0.1, 0.2, 0.3]
report("floats 0.1, 0.2, 0.3", floats, totals(floats, add, start=0.0))
print(f"  (0.1 + 0.2) + 0.3 = {(0.1 + 0.2) + 0.3!r}")
print(f"  0.1 + (0.2 + 0.3) = {0.1 + (0.2 + 0.3)!r}")
report("the same floats, summed with math.fsum", floats,
       sorted({math.fsum(order) for order in permutations(floats)}))


def withdraw_only_if_covered(balance, v):
    """A negative request is a withdrawal, refused if it would overdraw."""
    return balance + v if balance + v >= 0 else balance


money = [50, -30, -40]
report("a balance that refuses to go below 0, requests +50, -30, -40", money,
       totals(money, withdraw_only_if_covered))

print()
print("one request, +5, delivered twice because the client retried after a lost reply:")
deliveries = [("req-1", 5), ("req-2", 10), ("req-1", 5)]

total = 0
for _, amount in deliveries:
    total += amount
print(f"  adding every delivery: {total}")

total, seen = 0, set()
for request_id, amount in deliveries:
    if request_id in seen:
        continue  # a retry of a request already applied
    seen.add(request_id)
    total += amount
print(f"  adding each request id once: {total}")

Integers: one total in every order¶

All 120 orders of five integers give one total. Integer addition is commutative (a + b = b + a) and associative ((a + b) + c = a + (b + c)), and any order of adding a list up is some combination of those two swaps.

Python's integers never overflow. In a language with fixed-width integers, an order that passes through a value too big for the type can end differently from one that does not, even when the final sum fits: a Rust debug build panics, Go and Java wrap around and still reach the right final sum, and a signed overflow in C or C++ is undefined behaviour. (Not machine-checked here.)

Floats: two totals from three numbers¶

None of 0.1, 0.2 and 0.3 is exactly a double, and each float addition rounds its exact result to the nearest double again. Which two numbers meet first decides what the first rounding throws away, so (0.1 + 0.2) + 0.3 and 0.1 + (0.2 + 0.3) land on neighbouring doubles. Float addition is commutative but not associative, and a server that adds floats in arrival order can print a different total when the arrivals are reordered. The Python tutorial's Floating-point arithmetic: issues and limitations ↗ explains the rounding, and the Rust library's What a float actually stores ↗ shows the digits of the double that 0.1 really is.

math.fsum ↗ tracks the exact sum and rounds only once at the end, so every order gives the same total. For money, the usual answer is not to use floats at all: count in integer cents, or use a decimal type.

A refusal: three totals from three requests¶

A balance that refuses a withdrawal it cannot cover is not "add every number". Whether -40 is applied depends on the balance at the moment it arrives, so the arrival order decides which requests are refused: +50, -30, -40 refuses the -40 and ends at 20; +50, -40, -30 refuses the -30 and ends at 10; -30, -40, +50 refuses both and ends at 50. A cap, a stock level, a rate limit — any "add, unless" — makes the total depend on order. A server with such a rule has to decide what order means, for example the order in which its single owner receives the requests, rather than hope the arrival order is the right one.

A duplicate: wrong in every order¶

A client sends +5, the server applies it, and the reply is lost. The client cannot tell whether the request was applied, so it sends it again. Adding every delivery counts that +5 twice, and no ordering fixes it. Networks and message queues commonly promise at-least-once delivery for exactly this reason: retrying is how they avoid losing a message, and the cost is that a message can arrive twice.

The fix is to make applying a request idempotent: the client sends a request id, the same one on every retry, and the server applies each id once. The second loop in the program does that with a set of the ids already applied. For the check to hold up, recording the id and changing the total have to happen in one atomic step — one lock, or one database transaction — or two copies of the same retry can both pass the check before either records it, the check-then-act version of the lost update. Payment APIs work this way; Stripe's idempotent requests ↗ is a public example.

The rule¶

A total comes out the same however and whenever the requests arrive when:

the operation does not care about order — commutative and associative, which integer addition is and float addition, "add unless" and "set to" are not;
each request is applied exactly once — which, over a network, means at-least-once delivery plus an idempotency key;
each application is one atomic step — the lock, atomic add or single owner of Keeping every update, or a database statement or transaction as in The lost update in a database.

Even then, only the final total is fixed. Someone who reads the total while requests are still arriving sees whatever subset has been applied so far, and a different subset on a different run.