Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-12-15
2002-09-17
Metjahic, Safet (Department: 2171)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000
Reexamination Certificate
active
06453326
ABSTRACT:
TECHNICAL FIELD OF THE INVENTION
This invention relates generally to database systems, and more particularly to data replication among multiple servers of a database network.
BACKGROUND OF THE INVENTION
A database system often contains multiple servers connected by a network. In order to keep the data maintained by each server up to date, changes made by one server will be replicated to all other servers of the database system. Replication is the process by which changes present on a “source” server are received and applied by a “destination” server. The changes being replicated may have originated on the source server or on another server.
For instance, in a proposed computer network, there are a plurality of directory service agents (DSAs) each maintaining a local database of directory service information. Each of the DSAs can make changes to the directory information, and the changes are replicated to other DSAs in the network. To keep track of the changes to allow proper. replication, each change (e.g., creating a new user, changing a user's password, etc.) originated by a DSA is identified by a database GUID and an update sequence number (USN). The database GUID identifies the local database of the DSA in which the change was originated. Each database GUID corresponds to exactly one DSA. The USN is a monotonically increasing serial number that is, for example, 64-bit long. It increases by one for each originating or replicated-in change applied to the database.
The database GUID and the USN together form a “signature” represented as (Database-GUID, USN), which uniquely identifies the change—i.e., no two changes should carry the same signature. In this regard, a USN is meaningless without the context of the database GUID for the purpose of uniquely identifying the change. For example, the change (Database-GUID
1
,
5
) has no relevance to the change (Database-GUID
2
,
5
). The change. (Database-GUID
1
,
10
), on the other hand, does have a relationship to the change (Database-GUID
1
,
5
) in that the change at USN
10
was made after the change at USN
5
, because the USNs were associated with the same database GUID and USNs increase over time.
Each update in a DSA's database is labeled with the signature of the change generated by the originating write and the USN at which the change was applied locally by the DSA. The latter is known as “usnChanged.” For an update that originated on the local DSA, the USN in the signature and the usnChanged are identical, and the database GUID in the signature is the database GUID of the local DSA. For an update that originated on another DSA and was later replicated to the local DSA, the USN in the signature (which is relative to the database GUID of the originating DSA) bears no relationship with the usnChanged (which is relative to the database GUID of the local DSA), and the database GUID in the signature is not the database GUID of the local DSA.
To facilitate replication of changes, each DSA tracks “watermarks” of the signatures issued on all other DSAs for changes that it has applied locally. The watermark is an assertion that every change made on the DSA corresponding to the database GUID at or below the given USN has been applied to the local DSA. This includes changes originated on the DSA with the given GUID as well as changes originated on other DSAs that have been applied to the DSA with the given GUID. For example, if DSA
2
has recorded the watermark (Database-GUID
1
,
10
), then it asserts that it has applied all changes made in Database-GUID
1
at USNs
1
,
2
,
3
, . . . ,
10
. The set of watermarks a particular DSA has with respect to all other DSAs is known as its “up-to-dateness vector,” or “UTD vector.”
In this proposed network database, the receiver of changes initiates the replication. In other words, the destination DSA asks the “source” DSA for any changes the source DSA may have that the destination does not. This form of replication is also known as “pull” replication. To respond to the replication request, the source DSA needs an efficient method to locate these changes that should be replicated to the destination DSA. It does so by checking in the UTD vector presented by the destination DSA in its request for a watermark relative to the source DSA's database GUID. If such a watermark is found, and assuming the watermark is X, the source DSA knows that it only has to look at updates in its database with usnChanged value greater than X. This is because the UTD vector indicates that all changes originated or replicated by the source DSA with USN at or below X have already been applied to the destination DSA, so that updates with usnChanged less or equal to X do not have to be replicated again. If no watermark relative to the source DSA's database GUID can be found, the destination has to look at all updates in its database, i.e., starting at USN
0
.
For each update on the source DSA found by comparing its usnChanged with the watermark, the source DSA looks at the. signature of the update and references it against the UTD vector provided by the destination. If a watermark is found with the database GUID of the signature of the change, the change has to be sent to the destination DSA if and only if the USN of the signature is greater than the USN in the watermark. This is again because the watermark indicates that the destination has applied all updates at or prior to its associated USN. If no watermark is found with the database GUID of the signature, the update is sent to the destination DSA.
After the destination has received and applied all changes sent by the source DSA, the destination DSA then asserts it is at least as up-to-date with respect to other DSAs as the source DSA is. The destination DSA then updates each of its watermarks to at least the corresponding USN recorded in the watermarks with corresponding database GUIDs at the source, and adds any watermarks relative to database GUIDs not in its own UTD vector but present in the source DSA's UTD vector.
Although this scheme of controlling data replication based on watermarks can potentially provide efficient data replication across a database system, the reliability of the replication is put in question in the event a server has to be restored from backup. In real-world operations, there is always the risk that the local database of a server will be damaged or somehow made irrecoverable such that the database has to be reconstructed from a backup. A consequence of the restoration is that the restored server has lost the changes it made after the backup and before the restoration. Those “lost” changes, however, may have already been replicated to other servers in the system. When the restored server continues from the restored state and adds new changes, some of the changes may be given signatures that have already been used for changes made before the restoration and replicated to other servers. Thus, two coexisting yet different changes may have the same signature. This can cause great confusion and inconsistency in the data replication, and, as a result, there is no guarantee of the convergence of the data on different servers through replication. Different approaches, such as the “backsyncing” process that will be described in greater detail below, have been proposed to address this problem of replication after restoration, but fail to provide satisfactory results.
SUMMARY OF THE INVENTION
In view of the foregoing, the present invention provides a method and system for replicating database changes among servers of a database system that effectively removes the inconsistency problems encountered after restoration from backup as described above by assigning a new GUID to a server after it has been restored. This new GUID is used for identifying new changes made by the server after restoration. By virtue of the use of the new GUID, new changes made after restoration will not be confused with any changes made by the server after the backup and before the restoration, which are identified by the old GUID of the server,
Parham Jeffrey B.
Raghavan Rengarajan S.
Metjahic Safet
Microsoft Corporation
Nguyen Cam-Linh
LandOfFree
Method and system for network data 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 Method and system for network data replication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for network data replication will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2896128