Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-09-09
2002-12-31
Corrielus, Jean M. (Department: 2771)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06502095
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
The present invention is directed, in general, to distributed databases and, more specifically, to a timestamp-based system and method for serializing lazy updates 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 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.
Therefore, what is needed in the art is a way to guarantee serializability-of updates within a replicated database system.
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 lazy updates in a distributed database described by a directed acyclic copy graph. In one embodiment, the system includes: (1) a timestamp module that creates a unique timestamp for each of the lazy updates and (2) a propagation module, associated with the timestamp module, that employs edges of the directed acyclic copy graph to propagate the lazy updates among replicas in the distributed database according to said unique timestamp and ensure the serialization.
The present invention therefore introduces the broad concept of employing the edges of the directed acyclic copy graph that describes the distributed database and unique timestamps associated with each of the lazy updates to propagate the lazy updates to the various replicas in the distributed database. In this manner, serialization can be guaranteed in distributed databases described by directed acyclic copy graphs.
In one embodiment of the present invention, the unique timestamp is a function of relationships between each of the lazy updates and a site location within the directed acyclic copy graph. In an embodiment to be illustrated and described, the unique timestamp takes the form of at least one tuple vector.
In one embodiment of the present invention, the unique timestamp is augmented for each sub-transaction to serialize updates to the replicas. In the embodiment to be illustrated and described, the unique timestamp is augmented by added tuples, allowing the propagation of the associated update through the distributed database to be tracked.
In one embodiment of the present invention, the timestamp module creates a lexicographic ordering of tuples for the directed acyclic copy graph and the unique timestamp is a function of the lexicographic ordering of tuples. In a related embodiment, the propagation module serializes the lazy updates as a function of a lexicographic ordering of tuples.
In one embodiment of the present invention, the unique timestamp is a tuple vector. Of course, the timestamp may comprise other or further information to establish the ordering of propagation.
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 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: 5806065 (1998-09-01), Lomet
patent: 5842196 (1998-11-01), Agarwal et al.
patent: 5864851 (1999-01-01), Breithbart et al.
patent: 5999931 (1999-12-01), Breitbart et al.
Johnson et al., “Lazy updates for distributed search structure”, ACM, pp. 337-346, year 1993.*
Jukka Teuhola, “Deferred maintenance of replicated objects”, IEEE, pp. 476-481, Jan. 1996.*
Johnson et al., “distributed indices for accessing distributed data”, IEEE, pp. 199-207, Jan. 1993.*
Jukka Teuhola, “Deferred Maintenance of Replicated Objects in Single-Site Database”, IEEE, pp. 476-481, Jan. 1996.
T. Johnson and P. Krishna, “Distributed Indices for Accessing Distributed Data”, IEEE, pp. 199-207, Jan. 1993.
J. Gray and A. Reuter, “Transaction Processing: Concepts and Techniques, Chapter 7: Islation Concepts”, 1993, pp. 375, 390-391, Morgan-Kaufmann Publishers, San Mateo, CA.
Parvathi Chundi, Daniel J. Rosenkrantz and S.S. Ravi, “Deferred Updates and Data Placement in Distributed Databases”, Research Supported by NSF Grant CCR-90-06396.
Parvathi Chundi, Daniel J. Rosenkrantz, S. S. Ravi. Department of Computer Science, U
Breitbart Yuri J.
Komondoor Raghavan V.
Rastogi Rajeev
Seshadri Srinivasan
Silberschatz Abraham
Corrielus Jean M.
Hitt Gaines & Boisbrun PC
Lucent Technologies - Inc.
LandOfFree
Timestamp-based system and method for serializing lazy... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Timestamp-based system and method for serializing lazy..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Timestamp-based system and method for serializing lazy... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2919642