Why are Things Associative?

The big three algebraic properties that show up in the distributed systems literature are associative, commutativity, and idempotency (EYE-dem-po-ten-see). Collectively these are referred to sometimes as “ACI” and these are so prevalent because those are precisely the things you need to require of distributed data structures so that they are oblivious to message reorderings and duplications.

A binary function named + is commutative if a + b = b + a for all a and b. Notable things which are commutative include integer addition, float addition, and operations like taking the larger of two integers. Commutativity is fairly self-explanatory, I think: if the operation doesn’t distinguish between its two inputs, it’s commutative. Idempotency too: a + a = a just says that doing a thing multiple times doesn’t have a different effect from doing it just once.

Of these I think associativity is the most mysterious. An operation + is associative if a+(b+c)=(a+b)+c. What kind of things look like that?

There are database reasons to care that are not also distributed systems reasons to care, and specifically there are reasons that don’t involve commutativity or idempotency: being associative is the property that makes an operation suitable for use as the merge operator in a log-structured merge data structure. When data gets pushed down, we want to be able to compact the files in an order appropriate for maintaining the sizes of levels we want, and associativity means that I am free to merge L2 into L3, or L3 into L4, if I deem fit.

You can see this in how the traditional “set key X to value Y” semantics are in fact associative under “last writer wins.” Say we represent this with the symbols x := y: when such an object is applied to a database, it sets the value of x to y. Because a later write takes precedence over an earlier one, the semantics of a merge is:

(x := a) + (x := b) = (x := b)

It’s easy to check that this object is associative:

  (x := a) + ((x := b) + (x := c))
= (x := c)
= ((x := a) + (x := b)) + (x := c)

Why, though? Why is this associative, integer addition associative, and matrix multiplication associative, but subtraction and exponentiation not? What's the common thread?

The answer is that they’re all special cases of one canonical associative operation: function composition.

Composition of two functions f and g is sometimes written f ∘ g and is defined by (f ∘ g)(x) = f(g(x)). It's easy to see symbolically that this is associative:

  ((f ∘ g) ∘ h)(x)
= (f ∘ g)(h(x))
= f(g(h(x)))
= f((g ∘ h)(x))
= (f ∘ (g ∘ h))(x)

Conceptually it's not too hard to convince yourself this is true: either way, you're still just performing three operations on a value in sequence, first the rightmost one, then the middle one, then the leftmost one.

The key insight is that things that are associative can be framed as functions, whose operation is actually composing those function.

The most natural one is matrix multiplication: if you've taken a linear algebra class (and if you haven't, linear algebra rocks), you are aware that matrices are functions that operate on vectors (they're exactly the linear functions), and multiplying two matrices is composing those two functions. This is why matrices are so useful in computer graphics, where we often want to perform several transformations on space in sequence ("rotate this object by 32 degrees, make it a little bigger, then swivel it over somewhere else"), composing those operations by multiplying matrices and "baking in" the composite transformation saves allows us to quickly perform all the transformations at once. But if this is true, matrix multiplication must be associative, because it is exactly function composition.

It's a little harder to see how something like addition is function composition. The numbers don't act on anything, they're just numbers themselves. But! We could also think of them instead of as operations which add themselves to some other number. 4 is actually then x -> x + 4. Then it's fairly easy to see that either (a + b) + c or a + (b + c) is "construct the operation add c, then add b, then add a."

On the other hand, subtraction isn't like this. Computing a - b - c can't be viewed as composing the values a and b and c as functions because if we look at b and c in isolation we lose the context that b was negated.

This is probably not that important to understand even if you are writing LSM merge operators, because even then it's not that hard to intuit what will and will not work under such a scheme. One noteworthy example of an operation that is commutative but not associative is float addition: if x is small and y is large, then x + y = y, and so x + (x + (x + (x + (... + y) = y, but (x + ... + x) + y might not equal y. Something to keep in mind.