Multiversion Concurrency Control Before InterBase

Posted by on in Blogs

I've been doing some reading in the area of concurrency theory, and, interestingly, have found some citations on the use of multiple record versions for concurrency control and recovery which predate InterBase.

The Birth of InterBase

First, some InterBase history. According to this timeline Jim Starkey started writing JRD -- a personal project which would later grow into InterBase -- between 1981 and 1984 while at DEC. Ann Harrison states that:

[Jim] began playing with shadowing, which he saw as a way to provide a repeatable read without blocking updates. Then, one morning in the shower, he realized that the shadows could be also prevent update conflicts and undo failed transactions.

Groton Database Systems was founded in 1984, and InterBase as a product went into beta about a year after that.

So InterBase's implementation of multiversion concurrency control and recovery was conceived sometime between 1981 and 1984, and implemented by 1985.

Multiversion Concurrency Control In Computing Literature Before InterBase

Multiversion concurrency control is described in some detail 4.3 and 5.5 of this 1981 paper by Philip Bernstein and Nathan Goodman -- then employed by the Computer Corporation of America. [Note: An ACM Portal subscription is required to read the full text of the paper.] Bernstein and Goodman's paper cites a 1978 dissertation by D.P. Reed which quite clearly describes MVCC and claims it as an original work. Reed's paper is cited by 66 other authors, according to the Guide to Computing Literature, and Bernstein and Goodman's, 180 times.

Conclusions

It seems that the idea of multiversion concurrency control and recovery is somewhat older than InterBase, at least insofar as discussion in technical papers is concerned. Working implementations were somewhat harder to come by. DEC's Rdb/ELN was a commercial database using MVCC and was released just prior to InterBase, but it was also designed by Jim Starkey in the same time period. Other than that, the only earlier working example I can find is a noncommercial application discussed in Reed's paper.

Jim Starkey notes in the comments section that he was unaware of Reed's paper, despite having discussed the subject with Bernstein, and came up with the same idea independently, later on.

Comments are not available for public users. Please login first to view / add comments.