Method and system for allocating cache memory for a network database service

• US 6,493,810 B1
• Filed: 04/28/2000
• Issued: 12/10/2002
• Est. Priority Date: 04/28/2000
• Status: Expired due to Term

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Raghuraman, Melur K., Tay, Yong Chiang, Pang, Jee Fung
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): Peugh, Brian R.
• Application Number:
  US09/560,804
• Time in Patent Office: 956 Days
• Field of Search: 711/170, 711/171, 711/100, 711/118, 711/129, 711/134, 711/130, 707/501.1
• US Class Current: 711/170
• CPC Class Codes: H04L 67/5682 Policies or rules for updating, deleting or replacing the stored data
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]

Abstract

A method is provided for estimating the size of cache memory required for optimal performance of a network database service, such as a directory service, by means of an iterative process. In the estimation process, the memory size N for best-case performance (i.e., the memory size that avoids any disk I/O operation) is first determined. The allocated memory size is then given a starting value. The probability (p) of cache-miss is then estimated for that memory size. Another probability (q), which is the probability that a record requested by a frequent user of the service is not in the cache, is also estimated for the memory size. The performance impact of the disk I/O rate indicated by p and q is then evaluated. If the performance is not adequate, the cache memory size is adjusted to a different value. The miss probabilities p and q are again estimated, and the performance impact is estimated. This iterative process is continued until the cache memory size is found to provide adequate estimated performance.

Claims

1. A method of determining a size of cache memory for a network database service to cache data retrieved from a database on a disk, comprising the steps of:

determining a best-case cache size for the network database service;

assigning an initial value for the size of cache memory;

estimating a first probability value corresponding to a general cache-miss rate for the size of the cache memory;

deriving a second probability value corresponding to a cache-miss rate for a frequent user with the size of the cache memory;

evaluating performance of the network database service with the first and second probability values to determine whether the performance is adequate; and

if the performance of the network database service is determine to be not adequate, adjusting the size of the cache memory;

repeating the steps of estimating, deriving, evaluating and adjusting until the performance of the network database service is determined to be adequate.

2. A method as in claim 1, wherein the step of determining the best-case cache size includes:

determining an average size of data retrieved for a user;

determining a peak number of active users connected to the network database service;

calculating the best-case cache size as a product of the average size of data retrieved and the peak number of active users connected.

3. A method as in claim 1, wherein the step of estimating the first probability value includes estimating a number of requests for records per user and calculating the first probability value as a function of the best-case cache size and the number of requests per user.

4. A method as in claim 1, wherein the network database service is a directory service.

5. A computer-readable medium having computer-executable instructions for performing steps for estimating a size of cache memory for a network database service, comprising:

determining a best-case cache size for the network database service;

assigning an initial value for the size of cache memory;

estimating a first probability value corresponding to a general cache-miss rate for the size of the cache memory;

deriving a second probability value corresponding to a cache-miss rate for a frequent user with the size of the cache memory;

evaluating performance of the network database service with the first and second probability values to determine whether the performance is adequate; and

if the performance of the network database service is determine to be not adequate, adjusting the size of the cache memory;

repeating the steps of estimating, deriving, evaluating and adjusting until the performance of the network database service is determined to be adequate.

6. A computer-readable medium as in claim 5, wherein the network database service is a directory service.

7. A computer-readable medium as in claim 6, wherein the step of determining the best-case cache size includes:

determining an average size of data retrieved for a user;

determining a peak number of active users connected to the network database service;

calculating the best-case cache size as a product of the average size of data retrieved and the peak number of active users connected.

8. A computer-readable medium as in claim 7, wherein the step of estimating the first probability value includes estimating a number of requests for records per user and calculating the first probability value as a function of the best-case cache size and the number of requests per user.