Skip to content

A Short Note on Atomicity and Ordering

February 15, 2016

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.

5 Comments leave one →
  1. February 15, 2016 8:33 am

    Careful with the word “atomicity”, it means different things to different people/in different contexts. Do you mean “all or nothing”? Total order?

    Also, don’t confuse the total ordering of writes with causality. For instance, serialisability requires a total order but not causal order (e.g. when implemented with 2PC). A client of a serialisable system might submit transactions T1 and T2 in that order, which will be committed in the total order T2 then T1.

    • February 15, 2016 3:31 pm

      It’s a fair cop – I was primarily thinking all-or-nothing since I was interested in the relationship between a single operation at a high layer of abstraction (hence intuitively perceived as atomic by a client of that layer), and the multiple operations at the next layer down typically involved in implementing it….

  2. Zteve permalink
    February 15, 2016 10:24 am

    It’s this high-level, well-informed viewpoint, drawing comparisons and spotting similarities, that marks this blog out as being special. Keep up the good work.

  3. February 18, 2016 1:54 am

    I just want to add to what @zteve has mentioned earlier. It is because of this sort of concise pieces of information – which are lost in the day-to-day humdrum of usual IT yet very relevant if we want to understand and retain the basics – that I read this blog. I have to admit that I don’t understand every topic that is discussed, yet I feel that I have learnt a bit. Many thanks, @adriancoyler

Trackbacks

  1. Node.fz: fuzzing the server-side event-driven architecture | the morning paper

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: