Method and system for network data replication

Details Method and system for network data replication Method and system for network data replication

2000-10-02

2003-11-25

Metjahic, Safet (Department: 2171)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C709S221000, C709S223000

Reexamination Certificate

active

06654771

ABSTRACT:

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 via a network. In order to keep the data maintained by each server up to date, changes made by one server are replicated to all other servers of the database system. Replication is the process by which changes present on a “source” server are received by and applied to 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, a plurality of directory service agents (DSAs) each maintain 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 globally unique identification (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, a 64 bit number. 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 a (Database-GUID, USN) pair, 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
) does not have any 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 that are less than 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.
There is another scenario in which directory service information may be lost, potentially creating replication inconsistencies. This problem arises in the context of the replication of directory service partition(s) that can be dynamically added to and removed from DSAs. Due to the removal and/or addition of one or more partitions, current replication techniques, as applied to DSAs, may lose some changes, causing inconsistency across DSAs. Consequently, it would be desirable to provide a solution wherein information that is replicated in a distributed system may persist across the addition and removal of partiti

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3144956