Distributed directory replication

• US 7,315,854 B2
• Filed: 10/25/2004
• Issued: 01/01/2008
• Est. Priority Date: 10/25/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: International Business Machines Corporation
• Inventors: Kumar, Apurva
• Primary Examiner(s): Alam; Shahid
• Assistant Examiner(s): Ly; Anh
• Application Number:
  US10/972,740
• Publication Number:
  US 20060089925A1
• Time in Patent Office: 1,163 Days
• Field of Search: 707100-102, 707/3, 707/4, 707/10, 709/223, 709/233, 709/226
• US Class Current: 707/754
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• 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: Y10S 707/956 Hierarchical
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A replication model has replicas store selected entries from subtrees. Only entries satisfying a particular search criterion specified by a filter are stored. Query containment is used to determine whether the query can be answered locally, or a referral to a remote server is required.

Claims

1. A method for processing a search request of a computer directory containing records hierarchically arranged as a directory information tree (DIT) at a replica server, said method comprising:

receiving an incoming search request from a client computer;

forming a replicated directory, said forming comprising storing a filtered replica of one or more directory entries matching one or more predetermined search specifications, wherein said filtered replica comprises a duplicate of said one or more directory entries, and wherein said search specifications comprise a base corresponding to a root entry of said search request in said DIT, a scope of said search request under said root entry, a filter corresponding to a search criterion of said search request, and attributes required from the directory entries satisfying said search criterion;

determining whether said search request is semantically contained within said replicated directory using a query containment rule,

such that said search request is determined to be semantically contained within the replicated directory only if a base of said search request is the same or a descendant of a base of said filtered replica, and

such that said search request is determined to be not semantically contained within said replicated directory only if said base of said search request is one of not the same and not a descendant of said base of said filtered replica; and

responding to said search request based on the determining process, wherein the response to said search request when said search request is semantically contained within the filtered replica comprises answering said search request based upon the filtered replica without making a referral of said search request to said replica server, and wherein the response to said search request when said search request is not contained within the filtered replica comprises referring said search request to said replica server.

2. The method of claim 1, further comprising determining whether a search request can be answered by the filtered replica based upon meta-information included in a parent of a base object of the filtered replica.

3. The method of claim 1, further comprising determining whether a search request can be referred to a peer replica based upon meta-information included in a parent of a base object of the filtered replica.

4. The method of claim 1, wherein in the storing process, the predetermined search specification comprises a search request scoped as one of a base search, a single-level search, or an entire subtree search.

5. The method of claim 1, wherein said search request is determined to be semantically contained within the replicated directory entries only if (a) a scope of said filtered replica is a subtree, or (b) said scope of said filtered replica is the same as a scope of said search request and said search request and said filtered replica have the same base, or (c) said scope of said filtered replica is a single-level and said scope of said search request is a base and said base of said search request is a child of a base of said filtered replica.

6. The method of claim 1, wherein said search request is determined to be semantically contained within the replicated directory entries only if a filter of said search request is more restrictive than a filter of said filtered replica such that any entry satisfying a condition specified by said filter of said search request also satisfies a condition specified by said filtered replica

7. The method of claim 1, wherein said search criterion comprises a Boolean combination of atomic and negative atomic filters, wherein said atomic filter comprises any of an equality, ordering, and substring assertion on an attribute value.

8. A method for processing a search request of a computer directory containing records hierarchically arranged as a directory information tree (DIT) at a replica server, said method comprising:

receiving an incoming search request from a client computer;

forming a replicated directory, said forming comprising storing a filtered replica of one or more directory entries matching one or more predetermined search specifications, wherein said filtered replica comprises a duplicate of said one or more directory entries, and wherein said search specifications comprise a base corresponding to a root entry of said search request in said DIT, a scope of said search request under said root entry, a filter corresponding to a search criterion of said search request, and attributes required from the directory entries satisfying said search criterion;

determining whether said search request is semantically contained within said replicated directory using a query containment rule,

such that said search request is determined to be semantically contained within the replicated directory only if (a) a scope of said filtered replica is a subtree, or (b) said scope of said filtered replica is the same as a scope of said search request and said search request and said filtered replica have the same base, or (c) said scope of said filtered replica is a single-level and said scope of said search request is a base and said base of said search request is a child of a base of said filtered replica, and

such that said search request is determined to be not semantically contained within said replicated directory only if one of (a) said scope of said filtered replica is not said subtree, (b) said scope of said filtered replica is not the same as said scope of said search request and said search request and said filtered replica do not have the same base, and (c) said scope of said filtered replica is not said single-level and said scope of said search request is not said base and said base of said search request is not said child of said base of said filtered replica; and

responding to said search request based on the determining process, wherein the response to said search request when said search request is semantically contained within the filtered replica comprises answering said search request based upon the filtered replica without making a referral of said search request to said replica server, and wherein the response to said search request when said search request is not contained within the filtered replica comprises referring said search request to said replica server.

9. The method of claim 8, further comprising determining whether a search request can be answered by the filtered replica based upon meta-information included in a parent of a base object of the filtered replica.

10. The method of claim 8, further comprising determining whether a search request can be referred to a peer replica based upon meta-information included in a parent of a base object of the filtered replica.

11. The method of claim 8, wherein in the storing process, the predetermined search specification comprises a search request scoped as one of a base search, a single-level search, or an entire subtree search.

12. The method of claim 8, wherein said search request is determined to be semantically contained within the replicated directory entries only if a base of said search request is the same or a descendant of a base of said filtered replica.

13. The method of claim 8, wherein said search request is determined to be semantically contained within the replicated directory entries only if a filter of said search request is more restrictive than a filter of said filtered replica such that any entry satisfying a condition specified by said filter of said search request also satisfies a condition specified by said filtered replica.

14. The method of claim 8, wherein said search criterion comprises a Boolean combination of atomic and negative atomic filters, wherein said atomic filter comprises any of an equality, ordering, and substring assertion on an attribute value.

15. A method for processing a search request of a computer directory containing records hierarchically arranged as a directory information tree (DIT) at a replica server, said method comprising:

receiving an incoming search request from a client computer;

forming a replicated directory, said forming comprising storing a filtered replica of one or more directory entries matching one or more predetermined search specifications, wherein said filtered replica comprises a duplicate of said one or more directory entries, and wherein said search specifications comprise a base corresponding to a root entry of said search request in said DIT, a scope of said search request under said root entry, a filter corresponding to a search criterion of said search request, and attributes required from the directory entries satisfying said search criterion;

determining whether said search request is semantically contained within said replicated directory using a query containment rule, such that said search request is determined to be semantically contained within the replicated directory entries only if a filter of said search request is more restrictive than a filter of said filtered replica such that any entry satisfying a condition specified by said filter of said search request also satisfies a condition specified by said filtered replica, and

such that said search request is determined to be not semantically contained within said replicated directory only if said filter of said search request is not more restrictive than said filter of said filtered replica such that any said entry satisfying said condition specified by said filter of said search request does not also satisfies said condition specified by said filtered replica; and

responding to said search request based on the determining process, wherein the response to said search request when said search request is semantically contained within the filtered replica comprises answering said search request based upon the filtered replica without making a referral of said search request to said replica server, and wherein the response to said search request when said search request is not contained within the filtered replica comprises referring said search request to said replica server.

16. The method of claim 15, further comprising determining whether a search request can be answered by the filtered replica based upon meta-information included in a parent of a base object of the filtered replica.

17. The method of claim 15, further comprising determining whether a search request can be referred to a peer replica based upon meta-information included in a parent of a base object of the filtered replica.

18. The method of claim 15, wherein in the storing process, the predetermined search specification comprises a search request scoped as one of a base search, a single-level search, or an entire subtree search.

19. The method of claim 15, wherein said search request is determined to be semantically contained within the replicated directory entries only if a base of said search request is the same or a descendant of a base of said filtered replica, and wherein said search request is determined to be semantically contained within the replicated directory entries only if (a) a scope of said filtered replica is a subtree, or (b) said scope of said filtered replica is the same as a scope of said search request and said search request and said filtered replica have the same base, or (c) said scope of said filtered replica is a single-level and said scope of said search request is a base and said base of said search request is a child of a base of said filtered replica.

20. The method of claim 15, wherein said search criterion comprises a Boolean combination of atomic and negative atomic filters, wherein said atomic filter comprises any of an equality, ordering, and substring assertion on an attribute value.