Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-06-22
2001-06-05
Homere, Jean R. (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C709S241000
Reexamination Certificate
active
06243702
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to computer systems and, more specifically, to a method and apparatus for reducing propagation delays in a database system.
BACKGROUND OF THE INVENTION
A database server is the software which is used in managing a database, and a client is an application that requests information from a database server. Each computer in a database system is called a node. A node in a distributed database system can perform the functions of a client, a database server, or both. In certain cases, a particular node may perform the functions of multiple database servers, multiple clients, or both. However, for explanation purposes, a node will be described as functioning as a single database server.
A multi-version database system is a database system that manages concurrency control via versions and snapshots of the same database. In a multi-version parallel database system, transactions executing on a plurality of database servers can concurrently access the same database. For a particular transaction, the versions of the data obtained from the database are typically the versions that were current at a particular point in time. The set of all database data that is current as of a particular point in time is commonly termed a “database snapshot”.
To provide transactions with database snapshots, a multi-version parallel database system typically stamps each version of data with a logical timestamp. The logical timestamp assigned to a version of data is typically referred to as a version number. When a transaction requires data from a multi-version database, the database server assigns one or more logical timestamps to the transaction. The logical timestamps that are assigned to transactions are commonly called “snapshot times” as they are used to determine the database snapshot that should be used with particular transactions. Snapshot times are generally provided to a transaction through the use of a logical clock that is maintained by each database server.
When a transaction commits, the transaction is assigned another logical timestamp. The logical timestamp assigned upon commit is referred to as the commit time of the transaction. All changes made by a transaction are considered to have been made at the commit time of the transaction. To supply an ordering to changes within a database, the logical clock of a database server is typically incremented after it is assigned as the commit time of a transaction. Consequently, transactions that commit are assigned commit times that are greater than previously committed transactions.
Thus, logical clocks maintained by database servers are used to provide logical timestamps for a variety of reasons (e.g. snapshot times, version numbers, commit times). Because each database server maintains its own logical clock, a transaction may be assigned a snapshot time that causes information to be read that is slightly older than the most current version. However, because the information obtained for a transaction is from a particular database snapshot, the transaction is guaranteed to receive consistent information that was current as of the particular snapshot time.
FIG. 1
depicts a multi-version parallel database system
100
in which a plurality of database servers (
104
-
108
) provide snapshot times to transactions for accessing database snapshots from a multi-version database
102
. In this example, the multi-version database
102
is represented using a plurality of database snapshots
114
. Each database snapshot
114
represents a virtual state of data as it existed in multi-version database
102
as of database logical timestamps T
23
-T
31
. In this example, T
31
represents the most recent database snapshot of multi-version database
102
. Respectively associated with the database servers
104
,
106
and
108
are logical clocks
110
,
112
and
114
. Currently executing on database servers
104
,
106
and
108
are transactions
116
-
118
,
120
-
122
and
124
-
128
. As depicted, each transaction is executing using data from a particular database snapshot.
When a process executing on a database server begins a transaction, the transaction is assigned a particular snapshot time based on the logical clock that is associated with the database server. The snapshot time guarantees that the version of the data items supplied to the process for the transaction will reflect the state of those data items as of the particular snapshot time. For example, if a transaction TX
1
is assigned a transaction snapshot time of T
1
, the process executing the transaction is guaranteed to be supplied with data items that reflect a state as of time T
1
, even if the data items have been subsequently modified. However while the process is guaranteed to be provided with a consistent set of data items from the database as of the snapshot time, the process may see information that is slightly older than the most current version of the database.
A transaction is considered committed after its changes are made persistent in the database. In certain systems, to commit a transaction, the transaction requests the database server on which it is executing to assign it a commit time. The database server then obtains a commit time from its logical clock and assigns it to the transaction. After obtaining the commit time, the logical clock is then incremented. A log force is then initiated. The log force writes information (redo records) describing the changes made by the transaction to disk. Once the log force is complete, the changes are made persistent in the database. The database may then report to the user that the transaction is committed.
For example, when transaction
120
began executing on database server
106
, the database server
106
accessed its logical clock
112
and assigned transaction
120
a snapshot time of T
26
. Based on a snapshot time of T
26
, the transaction
120
is provided with a database snapshot
114
as of the logical timestamp T
26
. Thus, transaction
120
is guaranteed that it will see a consistent set of data from the multi-version database
102
as of snapshot time T
26
. When transaction
120
completes and is ready to commit, the database server
106
will assign transaction
120
a commit time based on the current value of its logical clock
112
. For example, the logical clock
112
of database server
106
may have incremented to a logical time value of T
30
. Transaction
120
would then be assign a commit time of T
30
for committing its changes to the multi-version database
102
. These changes can then be seen by transactions that are assigned a snapshot time of T
30
or greater.
Because each database server maintains its own logical clock, whether a particular transaction will see a particular change made to the database depends not only on the current logical clock value associated with the database server in which the transaction is executing, but also on the logical clock values that are associated with the other database servers of the database system. Thus, by having each database server maintain its own logical clock, a time dependency is formed between the transactions executing on different database servers of the database system. This time dependency causes a propagation delay to be introduced into the database system that can cause updates that occurred prior to reading the database not to be seen.
A maximum propagation delay period is the maximum interval of time for which changes committed by transaction executing on one database server are propagated to the transactions executing on other database servers of the database system. This maximum propagation delay period guarantees that if a transaction commits changes from one database server, that the committed changes will be seen by all other database servers of the system if a query is performed after the maximum propagation delay period. Thus, if the maximum propagation delay period is greater than zero, then the changes caused by a transaction committing on one database server are not guaranteed to be seen by othe
Bamford Roger J.
Bridge, Jr. William H.
Lee J. William
Srivastava Alok
Brandt Carl L.
Hickman Palermo Truong and Becker LLP
Homere Jean R.
Oracle Corporation
Robinson Greta L.
LandOfFree
Method and apparatus for propagating commit times between a... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for propagating commit times between a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for propagating commit times between a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2523843