Are some algorithms simply too hard to implement correctly?

I recently got around to reading a rather old paper: McKusick and Ganger: Soft Updates: A Technique for Eliminating Most Synchronous Writes in the Fast Filesystem.

The paper describes a sophisticated enhancement to the 4.4BSD FFS (Fast FileSystem) algorithms that not only improves performance dramatically, but also eliminates the need to run fsck after every system crash.

The core of the algorithm is to carefully track dependencies between different update requests that the filesystem makes:

With soft updates, the filesystem uses delayed writes (i.e., write-back caching) for metadata changes, tracks dependencies between updates, and enforces these dependencies at write-back time. Because most metadata blocks contain many pointers, cyclic dependencies occur frequently when dependencies are recorded only at the block level. Therefore, soft updates tracks dependencies on a per-pointer basis, which allows blocks to be written in any order. Any still-dependent updates in a metadata block are rolled-back before the block is written and rolled-forward afterwards. Thus, dependency cycles are eliminated as an issue. With soft updates, applications always see the most current copies of metadata blocks and the disk always sees copies that are consistent with its other contents.

It's one of those algorithms that's fairly easy to state but devilishly intricate to implement properly, and the McKusick and Ganger paper is all about implementation.

The core concept of dependency tracking and write ordering is very sound and reliable, and the resulting filesystem has seen enormous practical success. At my day job, we use a similar, though vastly simpler, dependency tracking and write ordering algorithm in the server database, and it, too, has been reliable and has seen enormous practical success.

However, as Val Aurora points out, it's an interesting observation that the basic soft updates algorithm is simultaneously well-known and infrequently used:

If a file system discussion goes on long enough, someone will bring up soft updates eventually, usually in the form of, "Duhhh, why are you Linux people so stupid? Just use soft updates, like BSD!" Generally, there will be no direct reply to this comment and the conversation will flow silently around it, like a stream around an inky black boulder. Why is this? Is it pure NIH (Not Invented Here) on the part of Linux developers (and Solaris and OS X and AIX and...) or is there something deeper going on? Why are soft updates so famous and yet so seldom implemented?

As Aurora notes, the details involved in the implementation turn out to be quite intricate:

I've read this paper at least 15 times, and each time I when get to page 7, I'm feeling pretty good and thinking, "Yeah, okay, I must be smarter now than the last time I read this because I'm getting it this time," - and then I turn to page 8 and my head explodes.

I understand the exploding head issue; the McKusick and Granger paper is dense and detailed. And yet, it seems to me to be almost perfectly written:

• The concepts are explained clearly, accurately, and thoroughly.
• The implementation complexities are covered
• The paper describes the data structures as well as their use

It's really hard to imagine the Soft Updates algorithm being any more clearly described or documented; the paper is nearly ideal. Yet, as Aurora concludes:

when it come to implementation, only programmers with deep, encyclopedic knowledge of the file system's on-disk format can derive the correct ordering rules and construct the associated data structures and web of dependencies. The close coupling of on-disk data structures and their updates and the user-visible data structures and their updates results in weird, counter-intuitive behavior that must be covered up with additional code.

Overall, soft updates is a sophisticated, insightful, clever idea - and an evolutionary dead end. Journaling and copy-on-write systems are easier to implement, require less special-purpose code, and demand far less of the programmer writing to the interface.

How has that assessment fared over the three years since Aurora wrote her article? According to this article from last winter, Linux filesystem engineers remain convinced that Soft Updates are too complex to implement, and other techniques, such as the Journaling or copy-on-write approaches mentioned by Aurora, are still the preferred techniques. As Ted Ts'o observes

The *BSD's didn't get advanced features such as Extended Attribute until some 2 or 3 years after Linux. My theory why is that it required someone as smart as Kirk McKusick to be able to modify UFS with Soft Updates to add support for Extended Attributes and ACL's.

I am comfortable conceding that, if Ted Ts'o feels that a particular filesystem algorithm is too complex, it is too complex.

So it seems that the time for Soft Updates has come and gone. If nothing else, it is extremely informative to study this work, ant it is also interesting to reflect on the rise and fall of the Soft Updates algorithm.

What are other good examples of algorithms that arose, came to be considered to be state of the art, then faded as newer algorithms came along? It's clear that Cryptography is full of such algorithms, but Soft Updates are interesting in that they're from an area that is perhaps less well-known.