Intelligent pre-caching algorithm for a directory server based on user data access history

• US 6,539,382 B1
• Filed: 04/29/1999
• Issued: 03/25/2003
• Est. Priority Date: 04/29/1999
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shi, Shaw-Ben Shepherd, Lin, Dah-Haur, Byrne, Debora Jean
• Primary Examiner(s): Alam, Hosain T.
• Assistant Examiner(s): Ly, Anh
• Application Number:
  US09/303,109
• Time in Patent Office: 1,426 Days
• Field of Search: 707/1-4, 707/100, 707/8, 707/10, 709/203, 709/226, 709/315
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: Y10S 707/954 Relational
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A caching mechanism for a directory service having a backing store. According to the invention, directory search results are cached over a given data capture period, with the information then being used by a data analysis routine to generate a data access history for the user for a particular application. That history is then used to generate a recommended pre-fetch time, a filter key for the pre-fetch, and a preferred cache replacement policy (e.g., static or LRU). Based on that information, a control routine pre-fetches and populates the cache with information that is expected to be needed by the user as a result of that access history.

Claims

1. A method of populating a directory server cache, comprising the steps of:

profiling an application for any repetitive user query patterns;

based on the existence of a repetitive user query pattern, identifying data that are likely to satisfy a directory query expected to occur at an anticipated time; and

populating the cache with the identified data prior to the anticipated time.

2. The method as described in claim 1 wherein the populating step includes pre-fetching the identified data from a backing store associated with the directory server.

3. The method as described in claim 1 wherein the directory query is a Lightweight Directory Access Protocol (LDAP) query.

4. The method as described in claim 1 further including the step of implementing a cache replacement policy based on the repetitive user query pattern.

5. The method as described in claim 4 wherein the cache replacement policy maintains the identified data in the cache until a cache lifetime expires.

6. The method as described in claim 4 wherein the cache replacement policy flushes least recently used entries from the cache.

7. The method as described in claim 1 wherein the repetitive user query pattern is captured over a given period.

8. The method as described in claim 1 wherein information comprising the repetitive user query pattern is stored in a first portion of the cache and the identified data is stored in a second portion of the cache.

9. A method for caching search result retrieved from a backing store in response to a Lightweight Directory Access Protocol (LDAP) directory service generating filter-based queries, comprising the steps of:

capturing information in response to LDAP search queries to the backing store applied against a given application;

analyzing the captured information to identify a repetitive user query pattern;

based on the existence of a repetitive user query pattern, identifying data that are likely to satisfy a directory query expected to occur at an anticipated time;

populating a cache with the identified data prior to the anticipated time; and

responsive to a new LDAP search query, retrieving the identified data from the cache in lieu of the backing store.

10. The method as described in claim 9 wherein the populating step includes pre-fetching the identified data from the backing store.

11. The method as described in claim 9 further including the step of implementing a cache replacement policy based on the repetitive user query pattern.

12. The method as described in claim 11 wherein the cache replacement policy maintains the identified data in the cache until a cache lifetime expires.

13. The method as described in claim 9 wherein the repetitive user query pattern is captured over a given period.

14. The method as described in claim 9 wherein information comprising the repetitive user query pattern is stored in a first portion of the cache and the identified data is stored in a second portion of the cache.

15. A method of populating a cache, comprising the steps of:

capturing information in response to search queries to a database applied against a given application;

analyzing the captured information to identify a repetitive user query pattern;

based on the existence of a repetitive user query pattern, identifying data that are likely to satisfy a directory query expected to occur at an anticipated time;

pre-fetching the identified data from the backing store prior to the anticipated time;

populating the cache with the pre-fetched identified data; and

responsive to a new search query, retrieving the identified data from the cache in lieu of the backing store.

16. The method as described in claim 15 further including the step of identifying a cache replacement policy based on the repetitive user query pattern.

17. A computer program product in computer-readable medium for populating a directory server cache, comprising:

means for profiling an application to identify any repetitive user query patterns;

means responsive to the profiling means identifying a repetitive user query pattern for identifying data that are likely to satisfy a directory query expected to occur at an anticipated time; and

means for populating the cache with the identified data prior to the anticipated time.

18. The computer program product as described in claim 17 wherein the populating means includes means for pre-fetching the identified data from a backing store associated with the directory server.

19. The computer program product as described in claim 17 further including the means for implementing a cache replacement policy based on the repetitive user query pattern.

20. A directory service, comprising:

a directory organized as a naming hierarchy having a plurality of entries each represented by a unique identifier;

a relational database management system having a backing store for storing directory data;

a directory server cache;

a caching mechanism for populating the directory server cache, comprising;

means for profiling an application to identify any repetitive user query patterns;

means responsive to the profiling means identifying a repetitive user query pattern for identifying data that are likely to satisfy a directory query expected to occur at an anticipated time; and

means for populating the cache with the identified data prior to the anticipated time.

21. The directory service as described in claim 20 wherein the populating means includes means for pre-fetching the identified data from a backing store associated with the directory server.

22. The directory service as described in claim 20 further including the means for implementing a cache replacement policy based on the repetitive user query pattern.

23. The directory service as described in claim 20 wherein the directory is compliant with the Lightweight Directory Access Protocol (LDAP).

24. A caching system for use with a directory server having a backing store, comprising:

a cache;

a data capture module for capturing information over a given time period about a user'"'"'s search queries exercised against a given application;

a data analysis module for processing the information to identify a user access pattern and generating cache control information; and

a control module for using the control information to populate the cache.

25. The caching system as described in claim 24 wherein the control information includes a pre-fetch time, a filter key, and a cache replacement policy.