Measured Performance of Time Interval Concurrency Control Techniques
Jerre D. Noe, David B. Wagner · 1987
This paper reports on an implementation of Bayer’s Time Interval concurrency control method and compares it to the performance of a conventional timestamp method. The implementation was done on the Eden experimental local area network. Insofar as the authors are aware, this is the first actual implementation of the time interval technique. The time interval approach clearly is better than time stamp ing. It provides higher throughput, causes one-third as many distributed transaction aborts, and requires very little additional overhead compared to time stamps. Within the time interval method we further explored and compared the early and late serialization schemes described by Bayer and hi colleagues. Early and late serialialization with time intervals show comparable performance over a range of read/write ratios and multiprogr amming levels. In systems that write to disk at the end of all alterations, rather than writing incrementally, late serialization performs better than early serialization because checkpointing to disk can run in parallel with the concurrency control phase. 1 Motivation For This Study There has been a great deal of interest in the performance of concurrency control algorithms in the literature in recent years [l, 7,9,10,11,13,17,20]. Most of these studies were either simulationbased or analytical in nature, although some used a combination Pamission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the tide of the publication and its date appear, and notice is given that copying is by permission of the Very Large Data Base Endowment. To copy otherwise, or tu republish, requires a fee and/or special permission from the Endowment. Proceedings of the 13th VLDB Conference, Brighton 1987 of the two approaches. To the best of our knowledge, there have been no comparative implementations of distributed concurrency control methods. The comparison of actual implementations of concurrency control methods is desirable because modeling and simulation studies generally do not include enough detail to exhibit the effects of finite processing limitations (CPU, disk, and network) on performance. (Three notable exceptions to this are the papers by Agrawal and Carey [l], Carey and Muhanna [7], and Sevcik [20].) Unless the system components are heavily underutilized, this factor should have a noticeable effect on performance whenever a large percentage of the work done by transactions is wasted work, i.e. work which is spent on transaction attempts that ultimately abort. In fact, Agrawal and Carey [l] postulated that contradictory results obtained by different researchers comparing the same algorithms are caused by the inclusion of finite processing resources in the model by some and not by others. Their simulation study included these factors and bore out their hypothesis. The current study reports measurements on the first known implementation of the Tie Interval method proposed by Bayer et. al. [3]. The implementation was carried out on the Eden local-area network, an object-oriented, experimental distributed system [2]. 2 Description of the Research 2.1 Choice of Protocols The Time Interval method was an outgrowth of the RAC protocol [4], which took advantage of the “before” and “after” images used by transaction systems for recovery purposes. RAC was a lock-based protocol that allowed multiple readers, using the old image, even during preparation of the new image by another (single) writer. This meant, of course, that the updating transaction had to be serialized to follow the commitment of the read-only transactions. However, this allowed more concurrency due to the one-writer, multiple-reader compatibility. It turns out that, in order to guarantee the correctness of the RAC protocol, both the “before” and “after” images of an object may be needed by the system for some period of time, even aper the new image has been successfully committed’. Bayer points out that ‘The miterk+ for image deletion are explained briefly in Section 3.2.2; for more detaila refer to [4].