Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-09-09
2002-12-24
Corrielus, Jean M. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06499037
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention is directed, in general, to distributed databases and, more specifically, to a system and method for serializing updates to ancestor sites in a distributed database.
BACKGROUND OF THE INVENTION
Database systems were first implemented at only a single database site. As the number of distributed applications requiring access to the database increased, the complexity, size and the time required to access the database systems also increased. Shortly thereafter, a single database site became unable to process all the information in a timely manner.
To correct this database processing problem, companies developed new database systems in which the database was replicated at different sites along a network. With the use of replicated databases, distributed applications were able to achieve a higher level of performance, reliability and availability. However, the higher level of performance came with a price.
Replicated databases improved performance, but management of the replicated data became vastly more complicated. Gigabytes of data are replicated in distributed data warehouses and various World Wide Web sites on the Internet. In telecom as well as data networks, network management applications require real-time dissemination of updates to replicas with strong consistency guarantees.
Two broad approaches have been developed to handle the problem of replica updates in a distributed database system, an eager protocol and a lazy protocol. The eager protocol updates all the replicas of an item as part of a single transaction. Thus, an eager protocol ensures that executions are serializable. However, a major disadvantage of an eager protocol's algorithms is that the a number of operations in the transaction increases with the degree of replication, and since deadlock probability is proportional to the fourth power of the transaction size, eager protocols are unlikely to scale beyond a small number of sites.
In contrast, the lazy protocol posts updates to replicas through independent transactions that are spawned by the original updating transaction after it commits. Thus, the effective size of a transaction is reduced and the overall performance of the system improves due to fewer deadlocks. However, transaction execution must be orchestrated carefully to ensure serializability across the entire distributed database.
Due to its superior performance benefits, a number of conventional database management programs (e.g., Sybase®, Oracle®, CA-OpenIngres®) provide support for updating via a lazy protocol. Specifically, these programs provide an option in which each transaction executes locally, and then is propagated asynchronously to replicas after it commits (the replicas at each site are updated in the context of a separate transaction). Since each transaction executes locally and independently, the systems do not require multi-site commit protocols (e.g., two-phase commit) which tend to introduce blocking and are thus not easily scalable.
A problem, however, with the lazy replication approaches of most conventional systems is that they can easily lead to non-serializable executions. For instance, it is possible for the same data item to be concurrently updated at two different sites, thus resulting in an update conflict. Currently, commercial systems use reconciliation rules (e.g. , install the update with the later timestamp) to merge conflicting updates. These rules do not guarantee serializability, unless the updates are commutative.
Another problem with lazy replication approaches is that they cannot serialize updates if the distributed database system is described by a cyclic copy graph. Current lazy replication approaches require that the distributed database system be described by a directed acyclic copy graph in order to ensure the serialization. Therefore, what is needed in the art is a way to guarantee serializability of updates within a replicated database system when the distributed database system is described by a cyclic copy graph.
SUMMARY OF THE INVENTION
To address the above-discussed deficiencies of the prior art, the present invention provides a system for, and method of, ensuring serialization of updates from a replica site in a distributed database that is described by a copy graph and a distributed database incorporating the system or the method. In one embodiment, the system includes: (1) a directed acyclic copy graph (DAG) creation module that identifies backedges in, and removes the backedges from, the copy graph to yield a DAG and (2) a propagation module, associated with the DAG creation module, that initially employs eager updating to propagate the updates along the backedges and thereafter employs lazy updating to propagate the updates along edges of the directed acyclic copy graph to ensure the serialization. For purposes of the present invention, a “backedge” is defined as one of a set of edges that, when the set is removed from a cyclic copy graph, yields an acyclic copy graph.
The present invention therefore introduces the broad concept of breaking updates down into two categories: a first involving updates along backedges in which eager updating is employed for speed and serialization, and a second involving a DAG in which lazy updating can be employed without subjecting the database to undue record locking.
In one embodiment of the present invention, the propagation module initially employs the eager updating to propagate the updates only along the backedges. Alternatively, eager updating can be employed with respect to some (but not all) of the edges that are not backedges.
In one embodiment of the present invention, the propagation module performs the eager updating as one atomic transaction. Those skilled in the pertinent art are familiar with atomic transactions affecting both a primary copy and one or more replicas. Alternatively, the eager updating can be performed as more than one atomic transaction.
In one embodiment of the present invention, the propagation module performs the eager updating with timestamps. It is preferable to perform the eager updating with timestamps when the subsequent lazy updating is timestamp-based. The Detailed Description that follows will describe when the propagation module shifts from backedge eager updating to lazy updating within the DAG in the context of timestamp-based updating.
In one embodiment of the present invention, the lazy propagation is performed without timestamps. It is preferable to perform the eager updating without timestamps when the subsequent lazy updating does not employ timestamps. The Detailed Description that follows will describe when the propagation module shifts from backedge eager updating to lazy updating within a forest (to be defined) based on the DAG in the context of timestamp-free updating.
In one embodiment of the present invention, a counterpart of the system is located at each replica of the distributed database. A replica is a site that comprises a copy of the whole database or a site that contains at least one element of the database. Alternatively, the system may be located at a single replica site, or at fewer than all sites.
The foregoing has outlined, rather broadly, preferred and alternative features of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject of the claims of the it invention. Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiment as a basis for designing or modifying other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.
REFERENCES:
patent: 5581753 (1996-12-01), Terry et al.
patent: 5596754 (1997-01-01), Lomet
patent: 5768594 (1998-06-01), Blelloch et al.
patent: 5802322 (1998-09-01), Nibl
Breitbart Yuri J.
Komondoor Raghavan V.
Rastogi Rajeev
Seshadri Srinivasan
Silberschatz Abraham
Corrielus Jean M.
Hitt Gaines & Boisbrun
Nguyen Tam V
LandOfFree
System and method for serializing updates to ancestor sites... 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 serializing updates to ancestor sites..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for serializing updates to ancestor sites... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2980818