Method and system for data replication

Abstract

A method and mechanism for data replication is disclosed. One embodiment of the invention relates to an efficient and effective replication system using LDAP replication components. Another embodiment of the invention pertains to a schema and format independent method for data replication. Procedures for adding, deleting, and modifying replicated data, and for replicating conflict resolution are also disclosed. A further embodiment of the invention is directed to improved methods and mechanisms for adding and removing nodes from a replication system.

Claims

What is claimed is:

1. A process for database replication comprising:

receiving a change request to modify data at a first replication site;

implementing said change request at said first replication site;

generating a change record corresponding to said change request; said change record having a schema independent format;

sending said change record to a second replication site; and

implementing said change record to a copy of said data at said second replication site.

2. The process of claim 1 in which said change request is directed to LDAP directory data.

3. The process of claim 1 in which implementing said change record at said replication site comprises:

generating a database instruction that is specific to schema and data organizations at said second replication site.

4. The process of claim 3 further comprising:

accessing metadata at said second replication site to generate said database instruction.

5. The process of claim 1 further comprising copying said change record to a first replication log at said first replication site, in which sending said change record to said second replication site comprises replicating said change record from said first replication log to a second replication log at said second replication site.

6. The process of claim 1 in which implementing said change record at said second replication site is performed using synchronous replication.

7. The process of claim 6 further comprising:

adding said change record to a change log at said first replication site; and

monitoring said change log for entry of new change records.

8. The process of claim 6 further comprising:

adding said change record to a second change log at said second replication site; and

monitoring said second change log for entry of new change records.

9. The process of claim 1 in which implementing said change record at said second replication site is performed using asynchronous replication.

10. The process of claim 9 in which said change record is sent to said second replication site in a periodic manner.

11. The process of claim 9 in which said change record is sent to said second replication site upon a trigger event.

12. The process of claim 1 in which schema and data organizations of said first replication site is different than that of said second replication site.

13. A process for replication of LDAP directory data in a distributed LDAP environment, comprising:

receiving an LDAP operation request at a first LDAP server, said first LDAP server located at a first LDAP site;

implementing said LDAP operation request to LDAP directory data at said first LDAP site;

generating a change log entry to a change log, said change log entry independent of schema and data organizations at said first LDAP site, said change log entry corresponding to said LDAP operation request;

replicating said change log entry to a second change log at a second LDAP site; and

utilizing said change log entry at said second change log to implement said LDAP operation request at said second LDAP site.

14. The process of claim 13 in which said schema and data organizations of said first replication site is different than that of said second replication site.

15. The process of claim 13 in which implementing said LDAP operation request to said second LDAP site comprises:

generating a database instruction that is specific to schema and data organizations at said second LDAP site.

16. The process of claim 15 further comprising:

accessing metadata at said second LDAP site to generate said database instruction.

17. The process of claim 13 in which replicating said change log entry comprises:

copying said change log entry from said change log to a first replication log at said first LDAP site; and

replicating said change log entry from said first replication log at said first LDAP site to a second replication log at said second LDAP site.

18. The process of claim 13 in which said LDAP directory data is synchronously replicated.

19. The process of claim 14 further comprising:

monitoring said change log for addition of said change log entry.

20. The process of claim 13 in which said LDAP directory data is asynchronously replicated.

21. The process of claim 20 in which said change log entry is replicated to said second LDAP site in a periodic manner.

22. The process of claim 20 in which said change log entry is sent to said second LDAP site upon a trigger event.

23. A computer program product that includes a medium usable by a processor, the medium having stored thereon a sequence of instructions which, when executed by said processor, causes said processor to execute a process for database replication, said process comprising:

receiving a change request to modify data at a first replication site;

implementing said change request at said first replication site;

generating a change record corresponding to said change request; said change record having a schema independent format;

sending said change record to a second replication site; and

implementing said change record to a copy of said data at said second replication site.

24. A computer program product that includes a medium usable by a processor, the medium having stored thereon a sequence of instructions which, when executed by said processor, causes said processor to execute a process for replication of LDAP directory data in a distributed LDAP environment, said process comprising:

receiving an LDAP operation request at a first LDAP server, said first LDAP server located at a first LDAP site;

implementing said LDAP operation request to LDAP directory data at said first LDAP site;

generating a change log entry to a change log, said change log entry independent of schema and data organizations at said first LDAP site, said change log entry corresponding to said LDAP operation request;

replicating said change log entry to a second change log at a second LDAP site; and

utilizing said change log entry at said second change log to implement said LDAP operation request at said second LDAP site.

25. A process for database replication comprising:

receiving a change request to modify data at a first replication site;

implementing the change request at the first replication site;

translating the change request into a schema independent change record;

sending the schema independent change record to a second replication site; and

implementing the schema independent change record to a copy of the data at the second replication site.

26. The process of claim 25 wherein implementing the schema independent change record comprises issuing a change instruction that is specific to schema and data organization at the second replication site.

27. The process of claim 26 wherein implementing the schema independent change record further comprises accessing metadata at the second replication site to generate the change instruction.

28. The process of claim 25 further comprising copying the change record to a first replication log at the first replication site, wherein sending the schema independent change record to a second replication comprises replicating the schema independent change record from the first replication log to a second replication log at the second replication site.

29. The computer program product of claim 23, wherein said process further comprises:

copying said change record to a first replication log at said first replication site, in which sending said change record to said second replication site comprises replicating said change record from said first replication log to a second replication log at said second replication site.

30. The computer program product of claim 23, wherein implementing said change record at said second replication site is performed using synchronous replication.

31. The computer program of claim 30, wherein said process further comprises:

adding said change record to a change log at said first replication site; and

monitoring said change log for entry of new change records.

32. The computer program product of claim 30, wherein said process further comprises:

adding said change record to a second change log at said second replication site; and

monitoring said second change log for entry of new change records.

33. The compute program product of claim 24, wherein said schema and data organizations of said first replication site is different than that of said second replication site.

34. The computer program product of claim 24, wherein implementing said LDAP operation request to said second LDAP site comprises:

generating a database instruction that is specific to schema and data organizations at said second LDAP site.

35. The computer program product of claim 34, wherein said process further comprises:

accessing metadata at said second LDAP site to generate said database instruction.

36. The computer program product of claim 24, wherein replicating said change log entry comprises:

copying said change log entry from said change log to a first replication log at said first LDAP site; and

replicating said change log entry from said first replication log at said first LDAP site to a second replication log at said second LDAP site.

37. The computer program product of claim 24, wherein said LDAP directory data is synchronously replicated.

38. The computer program product of claim 37, wherein said process further comprises:

monitoring said change log for addition of said change log entry.

Description

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention relates to the replication of data in a database system.

2. Background

Data replication is the process of maintaining multiple copies of a database object in a distributed database system. Performance improvements can be achieved when data replication is employed, since multiple access locations exist for the access and modification of the replicated data. For example, if multiple copies of a data object are maintained, an application can access the logically "closest" copy of the data object to improve access times and minimize network traffic. In addition, data replication provides greater fault tolerance in the event of a server failure, since the multiple copies of the data object effectively become online backup copies if a failure occurs.

In general, there are two types of propagation methodologies for data replication, referred to as "synchronous" and "asynchronous" replication. Synchronous replication is the propagation of changes to all replicas of a data object within the same transaction as the original change to a copy of that data object. For example, if a change is made to a table at a first replication site by a Transaction A, that change must be replicated to the corresponding tables at all other replication sites before the completion and commitment of Transaction A. Thus, synchronous replication can be considered real-time data replication. In contrast, asynchronous replication can be considered "store-and-forward" data replication, in which changes made to a copy of a data object can be propagated to other replicas of that data object at a later time. The change to the replicas of the modified data object does not have to be performed within the same transaction as the original calling transaction.

Synchronous replication typically results more overhead than asynchronous replication. More time is required to perform synchronous replication since a transaction cannot complete until all replication sites have finished performing the requested changes to the replicated data object. Moreover, a replication system that uses real-time propagation of replication data is highly dependent upon system and network availability, and mechanisms must be in place to ensure this availability. Thus, asynchronous replication is more generally favored for noncritical data replication activities. Synchronous replication is normally employed only when application requires that replicated sites remains continuously synchronized.

One approach to data replication involves the exact duplication of database schemas and data objects across all participating nodes in the replication environment. If this approach is used in a relational database system, each participating site in the replication environment has the same schema organization for the replicated database tables and database objects that it maintains. If a change is made to one replica of a database table, that same change is propagated to all corresponding database tables to maintain the consistency of the replicated data. Since the same schema organization used the replicated data across all replication sites, the instructions used to implement the changes at all sites can be identical.

Generally, two types of change instructions have been employed in data replication systems. One approach involves the propagation of changed data values to each replication site. Under this approach, the new value for particular data objects are propagated to the remote replication sites. The corresponding data objects at the remote sites are thereafter replaced with the new values. A second approach is to use procedural replication. Under this approach, a database query language statement, e.g., a database statement in the Structured Query Language ("SQL"), is propagated instead of actual data values. The database statement is executed at the remote sites to replicate the changes to the data at the remote replication sites. Since all replication sites typically have the same schema organization and data objects, the same database statement can be used at both the original and remote sites to replicate any changes to the data.

A significant drawback to these replication approaches is that they cannot be employed in a heterogeneous environment in which the remote replication sites have different, and possibly unknown, schema organizations for the replicated data. For example, consider if information located in a single database table at a first replication site is stored within two separate tables at a second replication site. The approach of only propagating changed values for a data object to a remote replication site presents great difficulties, since the data object to be changed at the first replication site may not exist in the same form at the second replication site (e.g., because the data object exists as two separate data items at the second replication site). Using procedural replication results in similar problems. Since each replication site may have a different schema organization for its data, a different database statement may have to be specifically written to make the required changes at the remote sites. Moreover, if the schema organization of the remote site is unknown, it is impossible to properly formulate a database statement to replicate the intended changes at the remote site.

Another drawback to these approaches in which database schema and objects are exactly duplicated across the replication environment is that they require greater use of synchronous replication. If a schema change is made to a database table at one site, then that change must be synchronously propagated to all other sites. This is because the basic structure of the table itself is being changed. Any further changes to that database table without first synchronously changing the underlying schema for that table could result in conflicts to the data. Moreover, synchronous replication of the schema changes could require that the replication environment be quieced during the schema change, affecting the availability of the system.

One type of database application for which data replication is particularly useful is the replication of data for directory information systems. Directory information systems provide a framework for the storage and retrieval of information that are used to identify and locate the details of individuals and organizations, such as telephone numbers, postal addresses, and email addresses.

One common directory system is a directory based on the Lightweight Directory Access Protocol ("LDAP"). LDAP is an object-oriented directory protocol that was developed at the University of Michigan, originally as a front end to access directory systems organized under the X.500 standard for open electronic directories (which was originally promulgated by the Comite Consultantif International de Telephone et Telegraphe "CCITT" in 1988). Standalone LDAP server implementations are now commonly available to store and maintain directory information. Further details of the LDAP directory protocol can be located at the LDAP-devoted website maintained by the University of Michigan at http://www.umich.edu/.about.dirsvcs/ldap/doc/, including the following documents (which are hereby incorporated by reference in their entirety): RFC-1777 Lightweight Directory Access Protocol; RFC-1558 A String Representation of LDAP Search Filters; RFC-1778 The String Representation of Standard Attribute Syntaxes; RFC-1779 A String Representation of Distinguished Names; RFC-1798 Connectionless LDAP; RFC-1823 The LDAP Application Program Interface; and RFC-1959 An LDAP URL Format.

LDAP directory systems are normally organized in a hierarchical structure having entries organized in the form of a tree, which is referred to as a directory information tree ("DIT"). The DIT is often organized to reflect political, geographic, or organizational boundaries. A unique name or ID (which is commonly called a "distinguished name") identifies each LDAP entry in the DIT. An LDAP entry is a collection of one or more entry attributes. Each entry attribute has a "type" and one or more "values." Each entry belongs to a particular object class. Entries that are members of the same object class share a common composition of possible entry attribute types.

There are significant drawbacks to existing systems for performing replication of LDAP entries, objects, and attributes. Many conventional replication systems used for LDAP replication do not have robust procedures for adding or deleting replication nodes. For example, the addition or deletion of replication nodes in a conventional LDAP system often results in system downtime to implement configuration changes. Moreover, many existing systems for LDAP replication do not have robust procedures for adding, deleting, or modifying replicated data or handling replication conflicts.

Therefore, there is a need for an improved method and system for replicating data in a database system. There is further the need for a robust and efficient replication system for performing LDAP replication.

SUMMARY OF THE INVENTION

The present invention is directed to methods and mechanisms for data replication. According to an aspect of the invention, an efficient and effective replication system is disclosed using LDAP replication components. Another aspect of the invention pertains to a schema and format independent method and method for data replication. Yet another aspect of the invention relates to procedures for adding, deleting, and modifying replicated data and for replication conflict resolution. Another aspect of the invention relates to improved methods and mechanisms for adding and removing nodes from a replication system.

Further details of aspects, objects, and advantages of the invention are described below in the detailed description, drawings, and claims.

BRIEF DESCRIPTION OF THE DRAWINGS

The accompanying drawings are included to provide a further understanding of the invention and, together with the detailed Description of Embodiment(s), serve to explain the principles of the invention.

FIG. 1 depicts a system architecture for data replication according to an embodiment of the invention.

FIGS. 2A, 2B, and 2C depict one approach for storing LDAP data in database tables.

FIG. 3 depicts a system architecture for replicating LDAP directory data according to an embodiment of the invention.

FIG. 4 shows an alternate approach for storing LDAP data in database tables.

FIG. 5 illustrates an example of a directory information tree.

FIG. 6 is a diagram of a computer hardware system with which the present invention can be implemented.

FIG. 7 is an additional diagram of computer hardware system with which the present invention can be implemented.

FIG. 8 depicts a revised version of the table shown in FIG. 2C.

FIG. 9 is a flow diagram showing a process for adding a new LDAP site to a replication environment according to an embodiment of the invention.

FIG. 10 is a flow diagram showing a process for removing an LDAP site from a replication environment according to an embodiment of the invention.

FIG. 11 illustrates a revised version of the directory information tree shown in FIG. 5.

DETAILED DESCRIPTION

The present invention is directed to a method and mechanism for replication in a database system that does not depend upon the same schema or data organizations being maintained at each replication site. The present invention is particularly well suited for LDAP data replication. According to one aspect of the invention, any data changes at a first replication site are replicated to other replication sites using schema and system independent change records. The change records are created in a standard format that is usable by all other replication sites in the system. Once the change record has been propagated to each remote replication site, the change record is then utilized to implement database instructions that are appropriate for the specific schema and system parameters of the remote site.

FIG. 1 depicts a system architecture for performing data replication according to an embodiment of the invention. Note that FIG. 1 illustrates the invention with reference to two replication sites; however, the inventive principles described herein is equally applicable to systems having more than two replication sites.

A first replication site 2 includes a database 4 having database data 6 and a data dictionary 8. Data dictionary 8 contains metadata that describes the schema and data organizations of database 4. First replication site 2 includes a server 10 that is responsible for accessing and modifying the database data 6 in database 4. Any client 14 that seeks to modify the database data 6 sends a request 12 to server 10 to add, change, or delete data. In response to request 12, change instructions 16 are issued to modify the database data 6.

A second replication site 52 similarly includes a database 54 having database data 56 and a data dictionary 58. Second replication site 52 further includes a server 60 that is responsible for accessing and modifying the database data 56 in database 54. If changes are to be made to database data 56, server 60 issues change instructions 66 to implement the requested changes.

For the purposes of illustration, assume that the system of FIG. 1 is used in a "peer-to-peer" or "multi-master" replication environment. In many peer-to-peer or multi-master replication environments, data changes made at a replication site are propagated to other replication sites, without the need for an overall "master" replication site. Thus, if a change request 12 at first replication site 2 is implemented to database data 6, that same change is replicated to the database data 56 at second replication site 52. Likewise, if a change request is made to second replication site 52 that is implemented to database data 56, that same change is replicated to the database data 6 at first replication site 2.

When a change request 12 is received at first replication site 2, server 10 issues change instruction 16 to implement the change request 12. The change instruction 16 takes into account the exact schema organization of the data object to be changed. Thus, the change instruction is schema-specific, and in a heterogeneous environment cannot simply be sent to all remote replication sites to replicate the data change, since the schema and/or system configuration of the remote replication sites may be entirely different than the schema and system configuration of local replication site 2.

According to the invention, server 10 translates either change instruction 16 or change request 12 into a schema and system independent change record 20. Change record is in a generic format that is consistent and recognizable across all replication sites in the system. In the normal contemplated usage of the invention, change record 20 comprises change information that is focussed upon the specific data to be added, deleted, or modified by the change request 12, and does not contain information regarding the schema organization of the data at the originating replication site.

The change record 20 is added to a change record table 24 at first replication site 2. According to an embodiment, it is the contents of the change record table 24 that is actually replicated to other replication sites. Thus, the contents of change record table 24 is replicated to the change record table 74 of second replication site 52. The change record 70, which is the replicated version of change record 20, is retrieved by server 60 to be applied to database data 56. Server 60 analyzes change record 70 to determine what data items are being changed. Based upon information located in the data dictionary 58, server 60 translates change record 70 into change instructions 66 that is specific to the schema and system configuration of database 54. The change instruction 66 is applied to replicate the change at replication site 52.

Since the change records are created in a format that is independent of schema or system configuration for the replication sites, true peer-to-peer replication is achieved in a heterogeneous environment, regardless of the schema, data, or system configurations of the database systems taking part in the replication environment.

ILLUSTRATIVE EXAMPLE

The present illustrative example is directed to an LDAP information system, which is used to provide a framework for the storage and retrieval of information that are used to identify and locate the details of individuals and organizations, such as telephone numbers, postal addresses, and email addresses. Recall from above that LDAP directory systems are normally organized in a hierarchical structure having entries organized in the form of a tree, which is referred to as a directory information tree ("DIT"). The DIT is often organized to reflect political, geographic, or organizational boundaries. A unique name or ID (which is commonly called a "distinguished name") identifies each LDAP entry in the DIT. An LDAP entry is a collection of one or more entry attributes. Each entry attribute has a "type" and one or more "values." Each entry belongs to a particular object class. Entries that are members of the same object class share a common composition of possible entry attribute types.

Referring to FIG. 5, shown is an example of a hierarchical tree of directory entities. Entry 96 is the top most level of DIT 20 and is of object class "organization" having an attribute type "Org. Name" with an attribute value of "Oracle". Entry 96 is the "parent" entry for three "child" entries (97, 98, and 99) directly beneath it in DIT 20. Entries 97, 98, and 99 are objects of object class "Department" each having attributes "Dept. Name" and "State." Entry 97 has an attribute type "Dept. Name" having a value of "Administration" and an attribute type "State" with the value "CA". Entry 98 has an attribute "Dept. Name" with the value "Sales" and an attribute type "State" with an attribute value "NY". Entry 99 has an attribute type "Dept. Name" with an attribute value "R&D" and an attribute type "State" with a value of "CA".

Entry 103 is a child entry of entry 97. Entry 103 represents an object of class "Person" having the following attribute type-value pairs: (1) attribute type "Last Name" with a value of "Founder"; (2) attribute type "First Name" with a value of "Larry"; (3) attribute type "Tel. No." with a value of "555-4444"; and (4) attribute type "State" with a value of "CA".

Entry 102 is a child entry of entry 98. Entry 102 represents an object of class "Person" having the following attribute type-value pairs: (1) attribute type "Last Name" with a value of "Jones"; (2) attribute type "First Name" with a value of "Joe"; (3) attribute type "Tel. No." with a value of "555-3333"; (4) attribute type "Manager" having the value of "Jim Smith"; and (5) attribute type "State" having the value "CA". Note that entries 102 and 103 are both members of object class Person, but entry 102 has more listed object attributes than entry 103. In many object-oriented based systems, objects that are members of the same object class may share a common set of possible object attributes, but some members of the class may not necessarily have values for some of the possible attributes. In this example, entry 103 does not have a value for attribute type "Manager" while entry 102 does have a value for this attribute.

Entries 100 and 101 are child entries of entry 99. Entries 100 and 101 are both members of object class "Person." Entry 100 is defined by the following attribute type-value pairs: (1) attribute type "Last Name" with a value of "Doe"; (2) attribute type "First Name" with a value of "John"; (3) attribute type "Tel. No." with a value of "555-1111"; (4) attribute type "Manager" having the value of "Larry Founder"; and (5) attribute type "State" having the value "CA". Entry 101 is defined by the following attribute type-value pairs: (1) attribute type "Last Name" with a value of "Smith"; (2) attribute type "First Name" with a value of "Jim"; (3) attribute type "Tel. No." with a value of "555-2222"; and (4) attribute type "Manager" having the value of "John Doe"; and (5) attribute type "State" having the value "NY".

FIGS. 2A, 2B, and 2C depict one approach to storing the LDAP directory entries from DIT 20 of FIG. 5, into a relational database management system ("RDBMS") or other database system using tables. In this approach, a separate table is provided for each object class in the system. FIG. 2A shows an object class table 202 for the Organization class, which includes entry 96 from DIT 20 as a member of that class. FIG. 2B is an example of an object class table 204 for the object class Department, which includes entries 97, 98, and 99. FIG. 2C is an example of an object class table 206 for the object class Person, which includes entries 100, 101, 102, and 103 from DIT 20.

Each row of the object class table represents a single object of that corresponding object class. Thus, the Person class table 206 of FIG. 2C includes four rows, one row for each of the person class entries of DIT 20 (i.e., entries 100, 101, 102, and 103). Discrete columns within the object class table represent attributes of an object within the object class. A separate column us provided for each possible attribute of an object class. The Person class table 206 of FIG. 2C includes five columns for object attributes "Last Name," "First Name," "Tel. No.," "Manager," and "State." Similar rows and columns in FIGS. 2A and 2B describe the objects and attributes for the Department and Organization objects of DIT 20.

An alternate approach to representing the DIT 20 of FIG. 5 in relational tables involves the implementation of a single table that comprises information describing objects and object attributes on the system. This table is hereby referred to as the "attribute_store" table. The attribute_store table comprises four columns having the following characteristics:

    Column Name     Datatype          Constraint Description
    EID             Number            Not null  ID for an entry
    AttrName        Character-numeric           Attribute ID for a
                                                particular attribute
    AttrVal         Character-numeric           Attribute values
    AttrKind        Character string  Not null  Kind of Attribute
                                                (Operational, User
                                                etc.)

    Column Name   Datatype          Constraint Description
    EID           Number            Not null  ID for an entry
    AttrName      Character-numeric           Attribute ID for a
                                              particular attribute
    AttrVal       Character-numeric           Attribute values
    AttrKind      Character string  Not null  Kind of Attribute
                                              (Operational, User
                                              etc.)
    AttrVer       Character String            Attribute version and
                                              timestamp

            Step 1.
            Entry
            (name)      Step 2.                                     Human
    Change  Conflict    Apply         New
     Intervention
    type    Check       change        Queue       Retry Queue       Queue
    Add     Search for  Compose       (a) Perform (a) Repeat step 1 NOTE: A
     change
            the parent  the correct   step 1 and  and 2.            entry would
            entry in    identifier    2.          (b) If both steps typically
     get into
            directory   (distinguished (b) If both succeed put the   this queue
     if the
            tree that   name or       steps       change to purge   parent
     entry fails
            matches     DN) for the   succeed put queue             to be
     located in
            with the    entry being   the change  (c) If one of the two the
     consumer
            object      added         to purge    steps fails,      directory
     during
            identifier  under its     queue       decrement the retry the
     period of
            (GUID) in   parent        (c) If one  count of the change normal
     retry.
            the change  entry         of the two  entry.            Same steps
     as in
            entry.      identified    steps fails, (d) If change fails retry
     queue
            If the      by GUID       put the     on the last retry processing
     with
            parent      in the        change into because of a      the
     exception of
            entry       consumer      retry queue duplicated target step (c).
            exists,     directory.    and set the entry, apply conflict If
     there are
            continue    Apply the     retry count resolution as     failures,
     the entry
            with step 2. change in     to the      follows:          is
     retained in this
                        the           configured  Older creation time queue
     until
                        consumer      maximum.    stamp wins. If    human
                        directory.                there is a tie, the
     intervention.
                                                  smaller GUID wins.
                                                  (e) If one of steps
                                                  1&2 fails on the
                                                  last retry for any
                                                  reasons other than
                                                  duplicate DN, put
                                                  the change into
                                                  Human Intervention
                                                  queue.

            Step 1.
            Entry
            (name)      Step 2.                                 Human
    Change  Conflict    Apply       New                         Intervention
    type    Check       change      Queue       Retry Queue     Queue
    Delete  Search for  Delete the  (a) Perform (a) Repeat steps 1 Same steps
     as in
            the entry in entry found step 1 and  & 2.            retry queue
            the directory in step 1.  2.          (b) If both     processing
     with
            tree matched             (b) If both succeed put the the exception
     of
            with the                steps       change to purge step (c).
            object                  succeed put queue.          If there are
            identifier              the change  (c) If either of the failures,
     the entry
            (GUID) in               to purge    two steps fails, is retained in
     this
            the change              queue       decrement the   queue until
            entry.                  (c) If one  retry count in the human
                                    of the two  change entry.   intervention.
                                    steps fails, (d) If either of the
                                    put the     two steps fails on
                                    change into the last retry
                                    retry queue move the change
                                    and set the to the human
                                    retry count intervention
                                    to the      queue.
                                    configured
                                    maximum.

                          Step 2.
                          a. Attribute
                          Conflict
            Step 1.       Check (for
            Entry (name)  Modify only).                             Human
    Change  Conflict      b. Apply      New
     Intervention
    type    Check         change.       Queue       Retry Queue     Queue
    Modify  Search for the a. Filter the (a) Perform (a) Repeat steps 1 Same
     steps as in
            correct unique modification  step 1 and  & 2.            retry
     queue
            identifier    in change     2.          (b) If both     processing
     with
            (distinguished entry by      (b) If both succeed put the the
     exception of
            name or DN)   comparing     steps       change to purge step (c).
            in the target each attribute succeed put queue.          If there
     are
            directory that in change     the change  (c) If either of the
     failures, the entry
            matches with  entry against to purge    two steps fails, is
     retained in this
            the object    the one in    queue       decrement the   queue until
            identifier    target entry. (c) If one  retry count in the human
            (GUID) in the (1. newer     of the two  change entry.
     intervention.
            change entry. modify time   steps fails, (d) If either of the
                          wins. 2.      put the     two steps fails on
                          greater version change into the last retry
                          wins. 3.      retry queue move the change
                          smaller       and set the to the human
                          hostname      retry count intervention
                          using string  to the      queue.
                          comparison    configured
                          rule wins.).  maximum.
                          b. Apply the
                          filtered
                          modification.

            Step 1.
            Entry
            (name)        Step 2.                                  Human
    Change  Conflict      Apply     New                            Intervention
    type    Check         change    Queue       Retry Queue        Queue
    Modify  Search for    Perform   (a) Perform (a) Repeat step 1 and Same
     steps as in
    RDN     the current   modify    step 1 and  2.                 retry queue
            unique        RDN       2.          (b) If both steps  processing
     with
            identifier    operation (b) If both succeed put the    the
     exception of
            (distinguished using the steps       change to purge    step (c).
            name or       current   succeed put queue              If there are
            DN) that      DN        the change  (c) If one of the two failures,
     the entry
            matches       acquired  to purge    steps fails, decrement is
     retained in this
            with the      from step queue       the retry count of the queue
     until
            object        1.        (c) If one  change entry.      human
            identifier              of the two  (d) If change fails on
     intervention.
            (GUID) in               steps fails, the last retry because
            the change              put the     of a duplicated target
            entry.                  change into entry, apply conflict
                                    retry queue resolution as follows:
                                    and set the Older creation time
                                    retry count stamp wins. If there
                                    to the      is a tie, the smaller
                                    configured  GUID wins.
                                    maximum.    (e) If one of steps
                                                1&2 fails on the last
                                                retry for any reasons
                                                other than duplicate
                                                DN, put the change
                                                into Human
                                                Intervention queue.

            Step 1.
            Entry
            (name)        Step 2.                                   Human
    Change  Conflict      Apply       New
     Intervention
    type    Check         change      Queue       Retry Queue       Queue
    Modify  Search for the Perform     (a) Perform (a) Repeat step 1 Same steps
     as in
    DN      current unique the         step 1 and  and 2.            retry
     queue
            identifier    modify DN   2.          (b) If both steps processing
     with
            (distinguished operation   (b) If both succeed put the   the
     exception of
            name or DN)   using the   steps       change to purge   step (c).
            that matches  current     succeed put queue             If there
     are
            with the object DN and      the change  (c) If one of the two
     failures, the entry
            identifier    new parent  to purge    steps fails,      is retained
     in this
            (GUID) in the DN          queue       decrement the retry queue
     until
            change entry. acquired    (c) If one  count of the change human
            Search for the from step   of the two  entry.
     intervention.
            new parent    1.          steps fails, (d) If change fails
            DN that                   put the     on the last retry
            matches with              change into because of a
            the parent                retry queue duplicated target
            GUID in the               and set the entry, apply conflict
            change entry.             retry count resolution as
                                      to the      follows:
                                      configured  Older creation time
                                      maximum.    stamp wins. If there
                                                  is a tie, the smaller
                                                  GUID wins.
                                                  (e) If one of steps
                                                  1&2 fails on the last
                                                  retry for any reasons
                                                  other than duplicate
                                                  DN, put the change
                                                  into Human
                                                  Intervention queue.

                                                Human
                                                Intervention
                  New queue       Retry queue   queue           Purge queue
    Retry count in 0               >0         -1              -2
    change entry
    Change number >last change <=last change <=last change <=last
     change
    in change entry number applied  number applied number applied  number
     applied
                  in change log.  in change log. in change log.  in change log.

• Inventors
  Shih, Kuang-Yu; Srinivasan, Uppili;
• Assignee
  Oracle International Corporation (Redwood Shores, CA)
• Published
  Sep-2-2003
• Current US Classes:
  707/201
  707/203
  707/204
• Application #
  515680
• International Classes
  G06F 012/00; G06F 017/30
• Field of Search
  707/10 707/203 707/204 707/202 707/101 709/201 709/101
• Examiner
  Robinson; Greta
• Agent
  Bingham McCutchen LLP
• US Patent References:
  4714995
  5295256
  5442780
  5454106
  5471613
  5499371
  5615362
  5664173
  5706506
  5799306
  5806074
  5809502
  5884324
  5937409
  5937414
  5963932
  5995999
  6009422
  6012067
  6016499
  6029178
  6047284
  6052681
  6058401
  6078925
  6085188
  6122258
  6122630
  6131098
  6134559
  6154743
  6163776
  6178416
  6189000
  6199062
  6301589
  6338092
  6356913
  6412017
  6453310