Linked List Insertion Capable of Surviving Abnormal Termination

I just finished a short conversation with Aaron Randall from London who used the little Windows Live Messenger Flash application in my sidebar (oh, how I love thee, Internets) to ask me a question he had about linked lists after reading one of my posts:

“I am trying to understand the data structure for a doubly-linked list. I wanted to see if there was any way of having a data structure that could survive things like hardware failure (the computer can go down during updating a doubly-linked list without having its node broken/separated)”

His question was specifically for insertion and it got me thinking. The problem here is that given three nodes (inserting B between A and C), there are four steps to insertion into a doubly linked list, none of which has to be made in any specific order: Update A’s forward link to B, update B’s forward link to C, update B’s backward link to A and also update C’s backward link to B.

Given an abnormal termination, one has to be able to resume operation with the assumption that the data’s integrity remains. This means that no matter during which phase of the insertion the computer fails, you will be able to resume normal work when it returns to its normal state.

RuggedLinkedListNodeI came up with a solution in which you would have a two-phase commit using six steps:

  1. A’s FutureNext pointer is set to point to B. Commit to disk.
  2. B’s Next pointer is set to point to C.
  3. A’s Next pointer is copied from its FutureNext pointer.
  4. C’s Previous pointer is set to point to B.
  5. B’s Previous pointer is set to point to A.
  6. A’s FutureNext pointer is nullified. Commit to disk.

The first step is the first phase in the two-phase commit, in which the link to the new node is established. Should a failure occur at any time after the first stage’s completion, a simple batch application scanning nodes for a non-null FutureNext pointer and completing the remaining five steps would be sufficient to keep data integrity.

Hope this helps, Aaron. :)

Advertisements

3 thoughts on “Linked List Insertion Capable of Surviving Abnormal Termination

  1. Or, you could use an atomic single linked list, such as the Win32 SList or any other implementation of a lock-free linked list. Since the operation is atomic, it’s guaranteed to either succeed or fail.
    An alternative approach would be to use a real transaction to update the data instead of inventing your own resource manager. (Which obviously has problems like “commit to disk” which sounds very atomic but could fail partially, leaving parts of your data in an inconsistent state.)

  2. Very good and valid points, Sasha.
    I was attacking this from a purely design-wise, academic angle, when OS-based solutions are clearly better when it comes down to actually implementing it.

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