Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-04-29
2003-03-25
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C709S223000, C709S218000
Reexamination Certificate
active
06539382
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Technical Field
This invention relates generally to providing directory services in a distributed computing environment.
2. Description of the Related Art
A directory service is the central point where network services, security services and applications can form a integrated distributed computing environment. The current use of a directory services may be classified into several categories. A “naming service” (e.g., DNS and DCE Cell Directory Service (CDS)) uses the directory as a source to locate an Internet host address or the location of a given server. A “user registry” (e.g., Novell NDS) stores information of all users in a system composed of a number of interconnected machine. The central repository of user information enables a system administrator to administer the distributed system as a single system image. Still another directory service is a “yellow pages” lookup provided by some e-mail clients e.g., Netscape Communicator, Lotus Notes, Endora and the like.
With more applications and system services demanding a central information repository, the next generation directory service will need to provide system administrators with a data repository that can significantly ease administrative burdens. In addition, the future directory service must also provide end users with a rich information data warehouse that allows them to access department or company employee data, as well as resource information, such as name and location of printers, copy machines, and other environment resources. In the Internet/intranet environment, it will be required to provide user access to such information in a secure manner.
To this end, the Lightweight Directory Access Protocol (LDAP) has emerged as an IETF open standard to provide directory services to applications ranging from e-mail systems to distributed system management tools. LDAP is an evolving protocol that is based on a client-server model in which a client makes a TCP/IP connection to an LDAP server, sends requests, and receives responses. The LDAP information model in particular is based on an “entry,” which contains information about some object. Entries are typically organized in a specified tree structure, and each entry is composed of attributes.
LDAP provides a number of known functions including query (search and compare), update, authentication and others. The search and compare operations are used to retrieve information from the database. For the search function, the criteria of the search is specified in a search filter. The search filter typically is a Boolean expression that consists of attribute name, attribute value and Boolean operations like AND, OR and NOT. Users can use the filter to perform complex search operations. The filter syntax is defined in RFC 1960.
LDAP thus provides the capability for directory information to be efficiently queried or updated. It offers a rich set of searching capabilities with which users can put together complex queries to get desired information from a backing store. Increasingly, it has become desirable to use a relational database for storing LDAP directory data. Representative database implementations include DB/2, Oracle, Sybase, Informix and the like. As is well known, Structured Query Language (SQL) is the standard language used to access such databases.
One of main goals for implementing an LDAP directory service with an relational database backing store is to provide a design and implementation such that all LDAP search queries can be executed efficiently. In the case of repetitive searches involving the same search query, however, it is not cost-effective to return to the backing store repetitively due to the nature of the database management system. In particular, it is very time consuming and expensive to go through the DBMS layers necessary to access entries inside the database for every entry required to be returned.
One approach to solving this problem is to use caching. As is well known, caching is a commonly used mechanism to improve performance. Instead of going to the server to obtain the requested data, a copy of that data stored in local memory is used to satisfy the data access request. However, most of the caching algorithms known today focus on how to maintain the cache after the data is retrieved from the server. Therefore, a user only sees a performance benefit after the data is initially accessed. In other words, the cache is primarily useful for applications that make the same query many times. There are a large number of applications that only make queries once or infrequently. Such queries, however, are made on a regular basis. A representative application is single sign-on (SSO), which enables an authorized user to perform one initial sign-on to access a variety of networks, systems and applications. These applications may actually take a performance hit due to the effort required to update and maintain a cache that never gets used because the same query is rarely repeated. In addition, information in the cache is lost when the directory server is rebooted. Therefore, known caching mechanisms do not address all of the requirements for applications of this type.
BRIEF SUMMARY OF THE INVENTION
It is an object of this invention to provide a novel caching mechanism, preferably for use by applications that exhibit a pattern within their queries so that these applications recognize a performance benefit the first time data is accessed during a given time period.
Another primary object of the present invention is to populate a cache before a user makes a query into a directory server having a backing store. In this case, the user obtains a fast response, even if he or she tries to access the data for the first time.
It is yet another object of the present invention to pre-fetch given data and populate a cache with such data based upon a user's data access history. This access history is also preferably used to implement a cache replacement policy.
Yet another more general object of the present invention is to provide a pre-caching mechanism for applications that typically access data sources periodically and on a daily basis.
It is a more general object of this invention to obviate repetitive inquiries into a relational database backing store used by a hierarchical-based directory service.
It is yet another object to search a relational database using hierarchical, filter-based queries, such as LDAP, and efficiently caching search results to increase search efficiency for repetitive queries.
Another object of this invention is to cache search results in a more efficient manner in a directory service having a relational database backing store.
Still another important object is to provide a mechanism for populating a local storage area associated with an LDAP directory service with directory search results retrieved from a relational database.
Yet another general object of this invention is to enhance the efficiency of a directory service using a caching mechanism.
The present invention is preferably implemented in a directory server having a backing store. According to the invention, a method for populating a cache for an application begins by profiling the application for repetitive user query patterns that reoccur during specific time periods on a periodic (e.g., daily, weekly, etc.) basis. Based on the repetitive user query patterns, the method identifies given information that is likely to satisfy a query expected to be generated at a given time. Prior to the given time, the cache is populated with the given information. Thus, if the user makes the query as expected, the given information will be present in the cache and will not have to be fetched from the backing store.
The foregoing has outlined some of the more pertinent objects and features of the present invention. These objects and features should be construed to be merely illustrative of some of the more prominent features and applications of the invention. Many other beneficial results can be attained by applying the disclosed invention in a different mann
Byrne Debora Jean
Lin Dah-Haur
Shi Shaw-Ben Shepherd
Alam Hosain T.
Burwell Joseph R.
Judson David H.
LaBaw Jeffrey S.
Ly Anh
LandOfFree
Intelligent pre-caching algorithm for a directory server... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Intelligent pre-caching algorithm for a directory server..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Intelligent pre-caching algorithm for a directory server... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3038667