Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
2001-03-16
2003-12-09
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000
Reexamination Certificate
active
06662196
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to the field of data replication.
“Bidirectional Database Replication” is specified as the application of database deltas (i.e., the results of transactions being performed against a database) from either of two databases in a pair to the other one. Transaction I/O (e.g., inserts, updates, and deletes) applied to one database are applied to the other database and vice-versa. Both databases are “live” and are receiving transactions from applications and/or end users. U.S. Pat. No. 6,122,630 (Strickler et al.), which is incorporated by reference herein, discloses a bidirectional database replication scheme for controlling transaction ping-ponging.
In the database world, a collision is classically defined as a conflict that occurs during an update. A collision occurs when a client reads data from the server and then attempts to modify that data in an update, but before the update attempt is actually executed another client changes the original server data. In this situation, the first client is attempting to modify server data without knowing what data actually exists on the server. Conventional techniques for minimizing or preventing collisions include database locking and version control checking. These techniques are commonly used in systems that have one database, wherein many users can access the data at the same time.
When a database system includes replicated databases, the problem of collisions becomes greater, since clients may be requesting database changes to the same data at the same physical or virtual location or at more than one physical or virtual locations. Collision or conflict detection schemes have been developed for replicated database systems. After a collision is detected, a variety of options are available to fix or correct the out-of-sync databases. However, it would be more desirable to prevent collisions from happening in the first place.
One conventional distributed transaction scheme used in Oracle distributed database systems is known as the “two-phase commit mechanism.” A side effect of this scheme is often a degree of collision prevention. The two phases are prepare and commit. In the prepare phase, a global coordinator (i.e., the transaction initiating node) asks participants to prepare the transaction (i.e., to promise to commit or rollback the transaction, even if there is a failure). The participants are all of the other nodes in the system. The transaction is not committed in the prepare phase. Instead, all of the other nodes are merely told to prepare to commit. During the prepare phase, a node records enough information about the transaction so that it can subsequently either commit or abort and rollback the transaction. If all participants respond to the global coordinator that they are prepared, then the coordinator asks all nodes to commit the transaction. If any participants cannot prepare, then the coordinator asks all nodes to roll back the transaction. Prior to the prepare phase, locks are placed on the appropriate data and the data is updated, thereby preventing many types of collisions. This scheme relies on a transaction coordinator for both local and remote database updating. If there are a large number of nodes in the system, the transaction coordinator must actively manage the updating of all of the other nodes. The node coordination puts large processing demands on the transaction coordinator and requires a large amount of messaging to occur throughout the system. Due to its messaging nature, the two-phase commit mechanism is not used for efficient replication of distributed databases.
Accordingly, there is an unmet need for a collision avoidance scheme in a bidirectional database replication system that is relatively simple to implement, efficiently uses communication medium, scales efficiently and easily, prevents all types of collisions, and which does not place large demands on local application programs to perform complex node coordination duties. The present invention fulfills such a need.
REFERENCES:
patent: 5036518 (1991-07-01), Tseung
patent: 5095421 (1992-03-01), Freund
patent: 5276871 (1994-01-01), Howarth
patent: 5452445 (1995-09-01), Hallmark et al.
patent: 5579318 (1996-11-01), Reuss et al.
patent: 5615364 (1997-03-01), Marks
patent: 5680573 (1997-10-01), Rubin et al.
patent: 5710922 (1998-01-01), Alley et al.
patent: 5721915 (1998-02-01), Sockut et al.
patent: 5721916 (1998-02-01), Pardikar
patent: 5721918 (1998-02-01), Nilsson et al.
patent: 5734898 (1998-03-01), He
patent: 5737601 (1998-04-01), Jain et al.
patent: 5740433 (1998-04-01), Carr et al.
patent: 5745753 (1998-04-01), Mosher et al.
patent: 5757669 (1998-05-01), Christie et al.
patent: 5758150 (1998-05-01), Bell et al.
patent: 5778388 (1998-07-01), Kawamura et al.
patent: 5781910 (1998-07-01), Gostanian et al.
patent: 5794252 (1998-08-01), Bailey et al.
patent: 5799305 (1998-08-01), Bortvedt et al.
patent: 5799306 (1998-08-01), Sun et al.
patent: 5799322 (1998-08-01), Mosher, Jr.
patent: 5799323 (1998-08-01), Mosher, Jr. et al.
patent: 5806075 (1998-09-01), Jain et al.
patent: 5832203 (1998-11-01), Putzolu et al.
patent: 5835915 (1998-11-01), Carr et al.
patent: 5870761 (1999-02-01), Demers et al.
patent: 5884325 (1999-03-01), Bauer et al.
patent: 5884327 (1999-03-01), Cotner et al.
patent: 5884328 (1999-03-01), Mosher, Jr.
patent: 5924095 (1999-07-01), White
patent: 5924096 (1999-07-01), Draper et al.
patent: 5970488 (1999-10-01), Crowe et al.
patent: 5991771 (1999-11-01), Falls et al.
patent: 6012059 (2000-01-01), Neimat et al.
patent: 6032158 (2000-02-01), Mukhopadhyay et al.
patent: 6122630 (2000-09-01), Strickler et al.
patent: 6243702 (2001-06-01), Bamford et al.
patent: 6243715 (2001-06-01), Bogantz et al.
patent: 6353834 (2002-03-01), Wong et al.
patent: 6493726 (2002-12-01), Ganesh et al.
Description of Two-Phase Commit Mechanism, Oracle8 Distributed Database Systems, Release 8.0, Document No. A58247-01, 1997, 3 pages.
Processing SQL Statements, Oracle7 Server Application Developer's Guide, 1996, 26 pages.
Data Concurrency, Oracle7 Server Concepts Manual, 1996, 28 pages.
Image/SQL: Issues and answers concerning SQL tables, Hewlett-Packard Company, Nov. 29, 1995, 34 pages.
Q&A: Replication in Microsoft Access for Windows 95, Microsoft Office Developer Forum, Nov. 22, 1995, 8 pages.
Multi-Version Concurrency Control, PostgreSQL User's Guide, Index and Chapter 10, 60-63, 1996-99, 11 pages.
Bodin et al., “Evaluating Two Loop Transformations for Reducing Multiple Writer False Sharing”, 7th Annual Workshop on Languages and Compiler for Parallel Computing, New York, Aug. 1994.
Holenstein Bruce D.
Holenstein Paul J.
Strickler Gary E.
Akin Gump Strauss Hauer & Feld L.L.P.
Goddard Brian
ITI, Inc.
Metjahic Safet
LandOfFree
Collision avoidance in bidirectional database replication does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Collision avoidance in bidirectional database replication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Collision avoidance in bidirectional database replication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3123265