A Short Note on Atomicity and Ordering

Just a short observation to start the week this week, inspired by the All File Systems are Not Created Equal paper that we looked at last week.

Atomicity (or lack thereof) and (re-)ordering are common issues that crop up again and again in different guises to cause us problems in systems. It all boils down to these two factors:

  1. What seems to be a single atomic operation at one level of abstraction is often composed of (implemented as) multiple distinct operations at the next level down, and
  2. What appear to be sequential operations at one level of abstraction may be re-ordered (normally for performance reasons) at the next level down.

These two facts cause visibility issues, and crash recovery issues unless great care is taken. Visibility issues can arise when the results of a single higher level operation become partially visible (the effects of some of the lower level operations are seen, but not others). Visibility issues can also arise when the effects of a later operation are seen before an earlier one (out of order). If we now consider that the system might crash at any point then we also must contend with partial results (partially completed operations) and out of order persistent results that we need to recover from. Oh, and by the way, it’s turtles all the way down…

Examples:

So if you’re designing a layered system, or using someone else’s abstraction (even a hardware one) it pays to think about atomicity and ordering.