Channels ▼

Andrew Koenig

Dr. Dobb's Bloggers

Data Structure Audits

November 15, 2012

Last week , I suggested using the operating system to help you put firewalls around parts of a system that might fail. I want to continue by discussing how to clean up after such subsystem failures.

More Insights

White Papers

More >>


More >>


More >>

Many data structures can be divided into two parts, which we might call the data part and the structure part. The idea is that a data structure contains a collection of data, together with additional information that can be used to access those data particularly easily or quickly. For example, the data in a typical filesystem are the contents of the disk blocks that constitute the filesystem. Each file has a corresponding part of the filesystem that keeps track of the blocks that constitute it. Directories (also known as folders) store collections of name/value pairs that make it possible to locate particular files. Moreover, there is usually an additional data structure that keeps track of all of the disk blocks that are not part of any file, so that when a user program wants to create a file, or add to a file that already exists, it is easy to find space on disk to do so.

It is not hard to imagine an invariant for a filesystem. It might specify that every disk block is part of a file, a directory, free space, or one (and only one) of the auxiliary data structures that keep track of the files, directories, or free space. Because this property is an invariant, operating-system code that manipulates the filesystem can assume that it is true, and such code is responsible for ensuring that the invariant remains true whenever user code is executing.

Just about anyone who has spent much time working with filesystems has learned two things about them:

  • Despite the best of intentions, it is not always possible to maintain the invariant in the face of a hardware crash or power failure.
  • Accordingly, most modern operating systems come with some kind of filesystem verifier that can be used to ensure that the underlying data structures — and associated invariants — are valid when required.

Filesystem checkers are tremendously useful. Not only can running such a program after a crash repair any damage that the crash might have caused (or that might have caused the crash!), but it also reports whether damage was present. Such reports are particularly useful to filesystem designers, because the designers may be able to redesign their filesystems to make them more robust against particularly common kinds of failure. This benefit to designers comes in addition to the benefit to users that an ordinary crash need not cause extensive data loss.

A filesystem checker is an example of a data-structure auditing program. Such a program typically verifies or reconstructs the structure part of a data structure from the data part. Such a program has two prerequisites:

  • The data has to be stored in a way that even if the structure becomes corrupted, it is still possible to reconstruct it.
  • Someone has to spend the time to write the auditing program and figure out when to use it.

I first learned about data-structure audits from a fellow I met at a conference. He had spent many years working on telephone switching systems at a time at which processors were so expensive that a typical telephone central office had only two of them — despite a requirement of no more than eight hours of down time for any reason over 40 years. He said that this level of reliability required three separate strategies.

Related Reading

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.