Patrick E. O'Neil
Abstract
A method is presented for permitting record updates by long-lived transactions without forbidding simultaneous access by other users to records modified. Earlier methods presented separately by Gawlick and Reuter are comparable but concentrate on “hot-spot” situations, where even short transactions cannot lock frequently accessed fields without causing bottlenecks. The Escrow Method offered here is designed to support nonblocking record updates by transactions that are “long lived” and thus require long periods to complete. Recoverability of intermediate results prior to commit thus becomes a design goal, so that updates as of a given time can be guaranteed against memory or media failure while still retaining the prerogative to abort. This guarantee basically completes phase one of a two-phase commit, and several advantages result: (1) As with Gawlick's and Reuter's methods, high-concurrency items in the database will not act as a bottleneck; (2) transaction commit of different updates can be performed asynchronously, allowing natural distributed transactions; indeed, distributed transactions in the presence of delayed messages or occasional line disconnection become feasible in a way that we argue will tie up minimal resources for the purpose intended; and (3) it becomes natural to allow for human interaction in the middle of a transaction without loss of concurrent access or any special difficulty for the application programmer. The Escrow Method, like Gawlick's Fast Path and Reuter's Method, requires the database system to be an “expert” about the type of transactional updates performed, most commonly updates involving incremental changes to aggregate quantities. However, the Escrow Method is extendable to other types of updates.
- 1 DATE, C. J. An introduction to Database Systems. Vol. 2. Addison-Wesley, Reading, Mass., 1983. Google Scholar
Digital Library
- 2 GAWLICK, D. Processing "hot spots" in high performance systems. In Proceedings of Spring COMPCON 85, 30th IEEE Computer Society International Conference (San Francisco, Calif.), IEEE, New York, 1985, 249-251.Google Scholar
- 3 GAWLICK, D., AND KINKADE, D. Varieties of concurrency control in IMS/VS Fast Path. Bull. IEEE Database Eng. 8, 2 (June 1985), 3-10.Google Scholar
- 4 GRAY, J. Notes on Data Base Operating Systems: Operating Systems--An Advanced Course. Springer-Verlag, New York, 1979.Google Scholar
- 5 GRAY, J. The transaction concept: Virtues and limitations. In Proceedings of the 7th VLDB Conference (Cannes, France). 1981, pp. 144-154.Google Scholar
- 6 HAERDER, T., AND REUTER, A. Principles of transaction-oriented database recovery. A CM Comput. Surv. 15, 4 (Dec. 1983), 287-317. Google ScholarDigital Library
- 7 IBM. IBM Program Product General Information Manual GH20-9069-2, IMS/VS Version 1 Fast Path Feature.Google Scholar
- 8 KEYDATA CORP. Keydata Order Entry Service Summary. Keydata Corp., Watertown, Mass., 1977.Google Scholar
- 9 REUTER, A. Concurrency on high-traffic data elements. In A CM Symposium on Principles of Database Systems (Mar. 1982). ACM, New York, 1982, 83-92. Google ScholarDigital Library
- 10 SCHLAGEVER, G. Enhancement of Concurrency in Database Systems by the Use of Special Rollback Methods, Data Base Architecture. North-Holland, Amsterdam, 1979.Google Scholar
- 11 ULLMAN, J.D. Principles of Database Systems. 2nd ed. Computer Science Press, Rockville, Md., 1982. Google ScholarDigital Library
Index Terms
- The Escrow transactional method
Recommendations
Refined transactional lock elision
PPoPP '16Transactional lock elision (TLE) is a well-known technique that exploits hardware transactional memory (HTM) to introduce concurrency into lock-based software. It achieves that by attempting to execute a critical section protected by a lock in an atomic ...
Stretching transactional memory
PLDI '09Transactional memory (TM) is an appealing abstraction for programming multi-core systems. Potential target applications for TM, such as business software and video games, are likely to involve complex data structures and large transactions, requiring ...
Safe privatization in transactional memory
PPoPP '18Transactional memory (TM) facilitates the development of concurrent applications by letting the programmer designate certain code blocks as atomic. Programmers using a TM often would like to access the same data both inside and outside transactions, ...
Reviews
Clement R. Attanasio
This paper reviews Fast Path concurrency control and Reuter's extension to Fast Path. Fast Path is an optimistic strategy, in that a change to a data value is logically made within a transaction if a predicate on the field is true when the change is requested. The system actually postpones the change until the transaction COMMITS, at which point the system verifies that the predicate is still true (if the predicate has become false, the transaction is aborted). Reuter's extension guarantees that the predicate is true at COMMIT if it was true at the time of the original request, by maintaining the list of outstanding, uncommitted update requests and verifying that subsequent predicates are true for all possible sequences of COMMITS of those requests. The motivation for these approaches is to increase concurrency of access to particular fields, over that which would be obtained using traditional locking strategies. The assumption is that there are certain fields in a database that are accessed very frequently by transactions, and that the logic of the transactions is such that they can execute correctly so long as those fields lie within previously known intervals. The author applies the concept of “Escrow Transactional Method” to Reuter's method. This is an elucidation but not an enhancement, as far as I can tell. He also extends Reuter's method to discuss techniques for supporting recovery of transactions after system failures. This paper is interesting for the background it describes and the issues it identifies. The author's treatment of some issues he raises is less satisfying. Recoverable transactions are difficult to write in his system, since “it is the responsibility of the program to recover its internal logical state. . . .” He assures us, but does not convince me, that “we should not blind ourselves to solutions that at first appear `inefficient',” when discussing the amount of calculation required to permit multiuser access to fields undergoing Escrow update. I believe that his extension to Reuter's method is quite conventional. Nevertheless, I recommend this paper because it is well written, discusses an interesting approach to concurrency control, and identifies many real issues. The author displays a willingness to discuss them in the context of practical considerations, as well as theoretical ones.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments