Maintaining counters for high performance object cache

• US 6,453,319 B1
• Filed: 04/05/2000
• Issued: 09/17/2002
• Est. Priority Date: 04/15/1998
• Status: Expired due to Term

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Inktomi Corporation (Apollo Global Management, Inc.)
• Inventors: Beguelin, Adam, Mattis, Peter, Plevyak, John, Haines, Matthew, Gourley, David, Totty, Brian
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US09/543,238
• Time in Patent Office: 895 Days
• Field of Search: 707/100, 707/103, 711/118, 711/119, 711/120, 711/121, 711/122, 370/236, 370/252, 370/429
• US Class Current: 1/1
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: Y10S 707/955 Object-oriented
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure

Abstract

A high-performance cache is disclosed. The cache is designed for time- and space-efficiency for a diverse range of information objects. Information objects are stored in portions of a non-volatile storage device called arenas, which are contiguous regions from which space is allocated in parallel. Objects are substantially contiguously allocated within an arena and are mapped by name keys and content-based object keys to a tag table, an open directory, and a directory table. The tag table is indexed by the name keys, and stores references to sets in the directory table. The tag table is compact and therefore can be stored in fast main memory, facilitating rapid lookups. The directory table is organized so that at least a frequently-accessed portion of it also usually resides in fast main memory, which further speeds lookups. The tag and directory tables are organized to quickly determine non-presence of objects. Large objects are chunked into fragments, which are chained using a forward functional-iteration mechanism, to prevent the need for mutating existing on-disk data structures. Garbage collection periodically moves objects within an arena or to other arenas. Additionally, for a plurality of counters, the following is computed: (1) the sum of values stored in the counters, and (2) the maximum value that can be represented by the coimters. Each of the counters are decremented when the sum is greater than half of the maximum value. Each of the counters is associated with an information object, which is deleted when a counter is decremented to zero.

Claims

1. A method of managing a plurality of counters stored in a computer memory, comprising the steps of:

computing a sum by summing values actually stored in each of the plurality of counters;

determining the maximum value that can be stored in each of the plurality of counters;

determining a maximum sum value by summing the maximum values that can be stored in each of the plurality of counters;

determining a threshold value based on the maximum sum value; and

decrementing each of the counters when the sum is greater than the threshold value that is based on a maximum sum value.

2. The method recited in claim 1, further comprising the steps of:

storing each of the plurality of counters in association with a description of one of a plurality of information objects stored in a cache; and

deleting one of the information objects that is associated with one of the counters when the counter is decremented to zero.

3. The method of claim 1, wherein the threshold value is a particular percentage of the maximum sum value.

4. The method of claim 3, wherein the threshold value is equal to one half of the maximum sum value.

5. The method of claim 1, wherein:

each counter of said plurality of counters is associated with a corresponding information object in a cache; and

the steps further include incrementing a particular counter of said plurality of counters when the corresponding information object is accessed.

6. The method of claim 5, wherein:

each counter of said plurality of counters is associated with a corresponding information object in a cache;

the plurality of counters includes a first counter associated with a corresponding first information object;

the step of decrementing each counter includes decrementing said first counter to a threshold counter value; and

the steps further include deleting the first information object when the first counter has been decremented to the threshold counter value.

7. The method of claim 6, wherein the threshold counter value is zero.

8. The method claim 1, further including identifying a set of information objects as least recently used based on the values of said plurality of counters.

9. A computer-readable medium carrying one or more sequences of one or more instructions for managing a plurality of counters stored in a computer memory, the one or more sequences of one or more instructions including instructions which, when executed by one or more processors, cause the one or more processors to perform the steps of:

computing a sum by summing values actually stored in each of the plurality of counters;

determining the maximum value that can be stored in each of the plurality of counters;

determining a maximum sum value by summing the maximum values that can be stored in each of the plurality of counters;

determining a threshold value based on the maximum sum value; and

decrementing each of the counters when the sum is greater than the threshold value that is based on a maximum sum value.

10. The computer-readable medium recited in claim 9, further comprising sequences of instructions for performing the steps of:

storing each of the plurality of counters in association with a description of one of a plurality of information objects stored in a cache; and

deleting one of the information objects that is associated with one of the counters when the counter is decremented to zero.

11. The computer-readable media of claim 9, wherein the threshold value is a particular percentage of the maximum sum value.

12. The computer-readable media of claim 11, wherein the threshold value is equal to one half of the maximum sum value.

13. The computer-readable media of claim 9, wherein:

each counter of said plurality of counters is associated with a corresponding information object in a cache; and

the steps further include incrementing a particular counter of said plurality of counters when the corresponding information object is accessed.

14. The computer-readable media of claim 13, wherein:

each counter of said plurality of counters is associated with a corresponding information object in a cache;

the plurality of counters includes a first counter associated with a corresponding first information object;

the step of decrementing each counter includes decrementing said first counter to a threshold counter value; and

the steps further include deleting the first information object when the first counter associated with the information object has been decremented to the threshold counter value.

15. The computer-readable media of claim 14, wherein the threshold counter value is zero.

16. The computer-readable media of claim 9, wherein the steps further include identifying a set of information objects as least recently used based on the values of said plurality of counters.