Electrical computers and digital processing systems: multicomput – Multicomputer synchronizing
Reexamination Certificate
1999-01-25
2001-08-14
Follansbee, John A. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Multicomputer synchronizing
C707S793000, C707S793000
Reexamination Certificate
active
06275863
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to transaction systems and, more particularly, to a system and method for programming and executing long running transactions which guarantee correctness and avoid failures from conflicts with other applications that access the same resources.
2. Description of the Related Art
Transaction processing over a network provides interactions between client or user stations. Transaction processing systems such as form processing systems, automatic teller machines (ATM) and the like, provide user interfaces which support “short running” transactions. Short running transactions are fast (often milliseconds) and include instructions supplied to or by a system server from/to user stations. The short running transactions which access an object, use locks to deny access to the object or similar objects in the server's database by others at the time of access.
For distributed computational systems, a unifying concept is implemented to provide consistent, safe and reliable transactions. This concept is called ACID. ACID stands for atomicity, consistency, isolation and durability. Atomicity represents a transaction's changes to state. Either all changes happen or none happen. These changes may include any state changes to objects, data, etc. Consistency requires that the view of shared resources presented to any one transaction be consistent with the semantic or integrity constraints on those resources. For example, if a system can show a set of account balances for a bank branch and the total balance for the branch, then the values presented to any one transaction should add up, i.e. the sum of the presented account balances must be equal to the value presented as the branch total. In other words, the actions taken as a whole should not violate the integrity constraints associated with the state. Isolation represents that even though the transaction may execute concurrently; it appears to each transaction that each other transaction occurred either entirely before or entirely after it, but not both. Durability represents that once a transaction completes successfully (commits); its changes to the state survive failures. These concepts are described in detail in
Transaction Processing: Concepts and Techniques
, by Gray and Reuter, Morgan Kaufmann Publishers San Francisco, Calif. 1993 (ISBN 1-55860-190-2), incorporated herein by reference.
To achieve ACID conditions, short running transactions are typically employed. Transaction servers supporting short running systems subject users to lock outs until other transactions with access to shared resources for which that user is competing have completed and released their locks. For example, an ATM machine may lock out additional users trying to access the same bank account. Short transactions provide access to the server for short duration interactions. When processing a short running transaction that accesses a particular object, all other users are locked out and must wait until the server has processed the prior transaction(s). This results in a bottleneck which becomes time consuming when many users attempt to access the object on the server. Existing short running transaction systems predefine the lock modes available for each object. These are typically Shared (S) and Exclusive (X). For read-only access to the object to proceed, the transaction must have an S or an X lock on the object. For read-write access to the object to proceed, the transaction must have an X lock. If any transaction is reading the object, all other transactions are prevented from writing to the object. In addition, if any transaction is writing to the object, all other transactions are prevented from having any access (read or write) to the object. This causes extremely long lock-wait times (and hence extended transaction response times) in traditional systems where the amount of contention for shared resources or the lock-hold life times become long.
Attempts have been made to increase throughput and to provide more easily accessed systems. Field calls have been used in systems such as IMS FastPath™, and are described in
Transaction Processing: Concepts and Techniques
, by Gray and Reuter, Morgan Kaufmann Publishers San Francisco, Calif. 1993 (ISBN 1-55860-190-2). Field calls are used to minimize the lock footprint in terms of the amount of data locked and the time the lock is held, and are used in the prior art only to drive short running transactions. Escrow locks, also discussed by Gray and Reuter are a refinement of field calls, also applied in the context of short running transactions.
Optimistic transactions are a known technique in which objects in a transaction are not locked during the course of a transaction. The transaction commits if and only if the state of participating objects in the datastore has not changed since the beginning of the transaction thus indicating that no other user has touched the object. Optimistic transactions are degenerate forms of field calls. Because optimistic transactions require rolling back a transaction if the state of any object has changed in any way, they unnecessarily reduce throughput since the change in state may not actually require the transaction to be aborted. For example, even if an account's balance has changed (due to another withdrawal) in the course of a funds transfer operation, the operation should still be able to proceed as long as the balance is sufficiently large to cover both withdrawals.
Workflow and Sagas are two technologies which begin to address system and server design for long running units of business and business processes. Workflow, as characterized by the IBM product MQ series Workflow (previously known as IBM Flowmark) and the WorkFlow management Coalition (WfMC) standards, provides approaches to providing automated management and control of “long running” business processes involving collections of users. Workflow systems manage recovery of the state of the workflow (i.e., they know reliably which activities have been started and which have been completed, etc.) but do not address recovery of resources manipulated as part of the activities which make up the workflow, nor do they provide an approach for handling contention when activities from different business processes must compete for access to shared resources.
Sagas (see “Coordinating activities through extended sagas: a summary”, H. Garcia-Molina et al., Compcon Spring '91, Digest of Papers, pages 568-573) require the programmer to code a set of compensating transactions and do not support concurrency. This art does not address or provide an approach to managing contention for shared resources. Further, traditional lock modes usually involve a closed (i.e., fixed set) of lock modes which preclude concurrent usage of the same objects.
Versioning for objects to be accessed has been used for long running transactions, but the task of reconciling conflicting versions is left to the user. This is not preferred since the user must manually determine the version of the object needed to perform the transaction.
Therefore, a need exists for a system and method for providing concurrent usage of objects in a database to increase throughput in long running transactions. A further need exists for a system and method for executing long running transactions which implement ACID properties and avoid false conflicts with other applications.
SUMMARY OF THE INVENTION
A method for programming and executing long running transactions between interface devices and a server includes the steps of providing a predicate set and a transform set, the predicate set defining conditions for which updates to states in accordance with the activity are to be made and the transform set for applying the updated states pursuant to the predicate set, committing the activity for processing upon establishment of communication with the server from the interface device, establishing communication with the server from the interface device to initiate the long running transa
Leff Avraham
Parr Francis N.
Rayfield James T.
Benson Walter
F. Chau & Associates LLP
Follansbee John A.
International Business Machines Corp.
LandOfFree
System and method for programming and executing long running... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for programming and executing long running..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for programming and executing long running... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2446549