The implementation and performance evaluation of three concurrency control (CC) servers used to access a shared object type, called the semiqueue, within distributed systems are described. The first server uses a purely optimistic policy, which aborts conflicting transactions at their validation phase. The second server uses a purely pessimistic mechanism, which resolves conflicts by delaying a locking request of a transaction if another transaction already holds a lock for a conflicting event. The third server is adaptable and uses a hybrid CC policy. Basically, the authors extend the hybrid scheme proposed earlier by Herlihy [1,2] to include the facility to dynamically adjust the mode in which a server treats conflicting events. The handling of transactions is changed dynamically between optimistic and pessimistic classes according to three simple heuristic methods that base their decision on the state of the object, represented by the size of the queue; the conflict history, represented by the percentage of conflict types in the current environment; and pre-assignment on the basis of priority. The paper presents the results of the performance study of the various servers and concludes with an outline for implementing adaptable CC for the atomic shared B-tree.
The paper is a welcome addition to the rich and still-growing literature on CC. The presentation is clear, and the paper is well organized. The authors have actually implemented the different servers using the distributed language SR running on a Sun machine. Their results can therefore be considered more credible than those of other, simulation-based performance studies. The most interesting result of the paper is that it shows (or at least implies) that it is not infeasible to build adaptable CC servers that perform nearly as well as the best of the purely optimistic, pessimistic, and static hybrid servers over a wide range of conflict levels. Based on that result, the authors recommend the use of adaptable dynamic servers rather than the traditional static locking schemes.
It is important to stress that the paper is mainly a performance study to test and compare some well-known CC techniques and design alternatives. As such, it does not propose new techniques or suggest significant modification to existing techniques. The three heuristic methods used in the adaptable scheme are obvious and simple. Some of the performance results reported in the paper are well known; for example, at low conflict levels, the locking overhead mars the performance of pessimistic methods, and the advantage of the optimistic approach is offset, at high conflict levels, by the wasted work associated with aborted transactions. The test conditions were not intended to be realistic; rather, the main concern of the authors was to provide a fair comparison between the different servers. Furthermore, since all the tests were performed on a single Sun-3 workstation, the performance in a real-life distributed system may not have been accurately captured by the results of these tests. The paper is long: its technical contents could have been conveyed much more concisely. Overall, the performance work presented in this paper is useful and encourages further research in the design and implementation of adaptable CC schemes.