Conflictless replication in a multi-master directory system

• US 7,340,488 B2
• Filed: 04/30/2004
• Issued: 03/04/2008
• Est. Priority Date: 05/15/2003
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Blanco, Marcos Ares, Reveane, Joseph
• Primary Examiner(s): Alam; Shahid A
• Application Number:
  US10/837,316
• Publication Number:
  US 20040230615A1
• Time in Patent Office: 1,404 Days
• Field of Search: 707/100, 707/101, 707/203, 707/204, 707/8, 707/201, 707/202, 715/511
• US Class Current: 1/1
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/275 Synchronous replication
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation
• CPC Class Codes: Y10S 707/99952 Coherency, e.g. same view to multiple users
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A directory server system may include master servers and a non-master server, each server storing directory server data that includes updates, each update having a creation time. The master servers exchange replicate updates through update communications. Each master server may include an update state builder for maintaining local update state items including an estimate time indication related to update communications received by the local master server about the directory server data stored by the designated master server. A master server may also include an upper time builder for evaluating an upper time value that is the earliest one of the estimate time indications in the local update state items. A master server may also include a master-to-non-master replicate function, for sending to the non-master server the updates in the local directory server data which have an associated creation time no later than the upper time value.

Claims

1. A master server, for use in a directory server system having other master servers and a non-master server, each server configured to store directory server data, comprising updates, each update having a creation time, the master servers configured to exchange replicate updates through update communications, said master server compnsing:

an update state builder configured to maintain local update state items, each item being associated to a designated master server and comprising an estimate time indication related to update communications received by the local master server about the directory server data stored by the designated master server,

an upper time builder configured to evaluate an upper time value, said upper time value being the earliest one of the estimate time indications in the local update state items, and

a master-to-non-master replicate function, configured to send to the non-master server those of the updates in the local directory server data which meet a time condition, said time condition including an upper time condition which comprises the fact that an update has an associated creation time which is no later than the upper time value such that those updates in the local directory server data that have an associated creation time later than the upper time value are not sent to the non-master server.

2. The master server of claim 1, wherein the directory server data comprises:

original updates, which have been locally created in the master server at their respective creation time, and

replicate updates performed in the master server after receipt of update communications about the directory server data stored by the other master servers.

3. The master server as claimed in claim 2, wherein the update state builder is configured to derive the estimate time indication of each item being associated to a designated master server from update communications received by the local master server about original updates of the directory server data stored by the designated master server.

4. The master server of claim 3, wherein the update state builder is configured to derive the estimate time indication of each item being associated to a designated master server from a first time indication representing the latest creation time amongst the updates replicated in the local master server from said original updates.

5. The master server as claimed in claim 4, wherein the update state builder is configured to derive the estimate time indication of each item being associated to a designated master server from a second time indication representing the latest update communication received by the local master server from the designated master server.

6. The master server as claimed in claim 5, wherein the update state builder is configured to evaluate the estimate time indication of each item being associated to a designated master server as the earliest one of the first time indication and the second time indication.

7. The master server as claimed in claim 6, wherein the master server has an update log for storing history of the updates applied in its directory server data, the master-to-non-master function being capable of selecting the updates to send from the update log.

8. The master server of claim 7, wherein each update of the update log comprises:

update data defining the update,

an update time indication representing the creation time at which the update was locally created.

9. The master server as claimed in claim 8, wherein the update log is ordered according to the update time indications.

10. The master server as claimed in claim 8, wherein the update time indications in the update log have the same format as the first time indications.

11. The master server as claimed in claim 8, wherein the update time indications in the update log have the same format as the second time indications.

12. The master server as claimed in claim 7, wherein the update state builder may evaluate the first time indications by scanning the update log.

13. The master server as claimed in claim 7, wherein said local master server is adapted to firstly receive target update state items from the non-master-server, each target update state item being associated to a designated master server and comprising a target time indication, representing the latest creation time amongst the updates replicated in the non-master server from original updates created in the designated master server, and the local master server further has a lower time builder capable of evaluating a lower time value, said lower time value being the earliest target time indication in the target update status items,

said time condition further comprising a lowest time condition, which comprises the fact that an update has an associated creation time which is no earlier than the lower time value.

14. The master server as claimed in claim 13, wherein the update time indications in the update log have the same format as the target time indications in the target update state items.

15. The master server as claimed in claim 5, wherein the update state builder has a second time indication storage for storing the second time indications, each second time indication associated to a designated master server being refreshed, in response to the receipt of an update communication in the local master server from said designated master server, with a time related to that update communication.

16. The master server of claim 15, for use in a local master server configured to receive the second time indications of a remote master server upon the receipt of an update communication from the remote master server, wherein the update state builder is further responsive to the receipt of an update communication from the remote master server, for refreshing each second time indication being associated to a designated master server amongst the local second time indications, with the latest one of:

the second time indication associated to said designated master server amongst the second time indications received from said remote master server,

the second time indication associated to said designated master server amongst the second time indications associated to said designated master server amongst the local second time indications.

17. The master server as claimed in claim 4, wherein the update state builder has a first time indication storage for storing the first time indications, the first time indication storage being refreshed in response to an update being applied in the directory server data.

18. A method of operating a master server in a directory server system, having other master servers and a non-master server,

each server configured to store directory server data, comprising updates, each update having a creation time,

the master servers configured to exchange replicate updates through update communications,

each master server comprising local update state items, in which each item is associated to a designated master server and comprises an estimate time indication related to update communications received by the local master server about the directory server data stored by the designated master server, the method comprising the steps of:

a) evaluating an upper time value as the earliest one of the estimate time indications in the local update state items, and

b) sending to the non-master server those of the updates in the local directory server data which meet a time condition, said time condition including an upper time condition which comprises the fact that an update has an associated creation time which is no later than the upper time value such that those updates in the local directory server data that have an associated creation time later than the upper time value are not sent to the non-master server.

19. The method of claim 18, wherein the directory server data comprises:

original updates, which have been locally created in the master server at their respective creation time, and

replicate updates performed in the master server after receipt of update communications about the directory server data stored by the other master servers.

20. A method of operating a master server in a directory server system, having other master servers and a non-master server,

each server configured to store directory server data, comprising updates, each update having a creation time,

the master servers configured to exchange replicate updates through update communications,

each master server comprising local update state items, in which each item is associated to a designated master server and comprises an estimate time indication related to update communications received by the local master server about the directory server data stored by the designated master server,

the method comprising the steps of:

a) evaluating an upper time value as the earliest one of the estimate time indications in the local update state items, wherein step a) comprises a preliminary step of;

i) deriving the estimate time indication of each item being associated to a designated master server from update communications received by the local master server about original updates of the directory server data stored by the designated master server, and

b) sending to the non-master server those of the updates in the local directory server data which meet a time condition, said time condition including an upper time condition which comprises the fact that an update has an associated creation time which is no later than the upper time value.

21. The method of claim 20, wherein said step i) comprises deriving the estimate time indication of each item being associated to a designated master server from a first time indication representing the latest creation time amongst the updates replicated in the local master server from said original updates.

22. The method as claimed in claim 21, wherein step a) comprises:

determining the estimate time indication of each item being associated to a designated master server from a second time indication representing the latest update communication received by the local master server from the designated master server.

23. The method as claimed in claim 22, wherein step a) comprises evaluating the estimate time indication of each item being associated to a designated master server as the earliest one of the first time indication and the second time indication.

24. The method as claimed in claim 20, wherein the master server comprises an update log for storing a history of the updates applied in its directory server data, wherein step b) further comprises selecting the updates to send from the update log.

25. The master server of claim 24, wherein step a) further comprises scanning the update log.

26. The method as claimed in claim 24, wherein the master server is configured to receive target update state items from the non-master server,

each target update state item being associated to a designated master server and comprising a target time indication, representing the latest creation time amongst the updates replicated in the non-master server from original updates created in the designated master server,

wherein step a) further comprises evaluating a lower time value as the earliest target time indication in the target update status items, and

said time condition further comprises a lowest time condition, which comprises the fact that an update has an associated creation time which is no earlier than the lower time value.

27. The master server of claim 26, wherein each update of the update log comprises an update time indication representing the creation time at which the update was locally created,

said update log being increasingly ordered according to the update time indications, wherein step b) comprises:

b1) fetching in the update log the update whose creation time matches the lower time value,

b2) fetching the next update in the update log,

b3) checking whether the non-master has already received said next update, if not sending that next update to the non-master, and

b4) checking whether the next update has a creation time that is no later than the upper time value, and if not repeating steps b2) through b4).