High performance object cache

• US 6,915,307 B1
• Filed: 05/06/2002
• Issued: 07/05/2005
• 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, Gourley, David, Haines, Matthew, Totty, Brian, Mattis, Peter, Plevyak, John
• Primary Examiner(s): Coby, Frantz
• Application Number:
  US10/140,497
• Time in Patent Office: 1,156 Days
• Field of Search: 707/100, 707/101, 707/102, 707/103.R, 707/104.1, 717/216, 717/121, 717/170, 719/310, 711/216
• US Class Current: 1/1
• CPC Class Codes: G06F 16/10 File systems; File servers
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface
• CPC Class Codes: Y10S 707/99944 Object-oriented database structure
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

The foregoing needs and other needs are addressed by the present invention, which provides, in one aspect, a mechanism for locating a data object. According to an aspect of the present invention, key values for data objects are generated, each key value may contain a first subkey value and a second subkey value. A mapping associates the first subkey values with storage locations. A particular first subkey value is mapped to storage location that contains second subkeys of a set of key values that correspond to the first subkey value. The storage location also includes additional information that may be used to locate objects associated with the set of key values.

Claims

1. A method of determining a location of a data object, the method comprising the steps of:

generating key values for data objects, wherein each key value of said key values includes a first subkey value and a second subkey value;

establishing a first mapping between first subkey values of said key values and first storage locations, wherein

a particular first subkey value corresponds to a particular set of key values, and

said particular set of key values correspond to a particular set of data objects; and

within the particular storage location of said first storage locations to which said particular first subkey value maps, storing;

second subkey values from the particular set of key values, and

first data for locating said particular set of data objects.

2. The method of claim 1, wherein:

each of said key values further includes a third subkey value;

the first data for locating said particular set of data objects identifies second storage locations; and

the method further includes the step of storing within a particular storage location of the second storage locations identified by the first data;

third key values from the particular set of key values, and

second data for locating said particular set of data objects.

3. The method of claim 1, wherein the step of storing within the particular storage location includes storing disk location values that indicate the location of said particular set of data objects.

4. The method of claim 1, wherein a particular key associated with a particular data object includes a first look-up subkey value and a second look-up subkey value, the method including the step of looking up a particular location for the particular data object by performing steps that include:

using said first mapping and said first look-up subkey value to identify a first storage location of said first storage locations; and

using said second look-up subkey value and the first data in said first storage location to identify said particular location for said particular data object.

5. The method of claim 2, wherein a particular key associated with a particular data object includes a first look-up subkey value, a second look-up subkey value, and a third look-up subkey value, the method including the step of looking up a particular location for the particular data object by performing steps that include:

using said first mapping and said first look-up subkey value to identify a first storage location of said first storage locations;

using said second look-up subkey value and the first data in the first storage location to identify a second storage location of said second storage locations; and

using said third look-up subkey value and the second data in said second storage location to identify said particular location of said particular data object.

6. The method of claim 2, further including the steps of:

retaining said first storage locations in a cache; and

paging subsets of said second storage locations in and out of said cache.

7. The method of claim 1, wherein object names are associated with said data objects, wherein the step of generating key values includes generating said key values based on the names of said data objects.

8. The method of claim 1, wherein the step of generating key values includes generating said key values based on the content of said data objects.

9. The method of claim 1, wherein for said each key value of said key values, the first subkey value includes L contiguous bits from said each key value, the second subkey value includes the next M contiguous bits from said each key value, and the third subkey value includes the next N contiguous bit in said each key value.

10. The method of claim 9, wherein the sum of L, M, and N is less than the number of bits in said each key value.

11. The method of claim 1, further including the step of determining whether a requested data object is stored in a cache by performing one or more steps that include inspecting said first storage locations to determine whether said first storage locations include a first subkey value from a key value generated for said requested data object.

12. The method of claim 11, wherein the step of determining whether said requested data object is stored in a cache includes inspecting said first storage locations to determine whether said first storage locations include a second subkey value from the key value generated for said requested data object when said first storage location includes said first subkey value from the key value generated for said requested data object.

13. A computer-readable medium carrying one or more sequences of instructions for determining a location of a data object, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform the steps of:

generating key values for data objects, wherein each key value of said key values includes a first subkey value and a second subkey value;

establishing a first mapping between first subkey values of said key values and first storage locations, wherein

a particular first subkey value corresponds to a particular set of key values, and

said particular set of key values correspond to a particular set of data objects; and

within the particular storage location of said first storage locations to which said particular first subkey value maps, storing;

second subkey values from the particular set of key values, and

first data for locating said particular set of data objects.

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

each of said key values further includes a third subkey value;

the first data for locating said particular set of data objects identifies second storage locations; and

the computer-readable medium further includes the step of storing within a particular storage location of the second storage locations identified by the first data;

third key values from the particular set of key values, and

second data for locating said particular set of data objects.

15. The computer-readable medium of claim 13, wherein the step of storing within the particular storage location includes storing disk location values that indicate the location of said particular set of data objects.

16. The computer-readable medium of claim 13, wherein a particular key associated with a particular data object includes a first look-up subkey value and a second look-up subkey value, the steps further including the step of looking up a particular location for the particular data object by performing further steps that include:

using said first mapping and said first look-up subkey value to identify a first storage location of said first storage locations; and

using said second look-up subkey value and the first data in said first storage location to identify said particular location for said particular data object.

17. The computer-readable medium of claim 14, wherein a particular key associated with a particular data object includes a first look-up subkey value, a second look-up subkey value, and a third look-up subkey value, the steps further including the step of looking up a particular location for the particular data object by performing further steps that include:

using said first mapping and said first look-up subkey value to identify a first storage location of said first storage locations;

using said second look-up subkey value and the first data in the first storage location to identify a second storage location of said second storage locations; and

using said third look-up subkey value and the second data in said second storage location to identify said particular location of said particular data object.

18. The computer-readable medium of claim 14, the steps further including:

retaining said first storage locations in a cache; and

paging subsets of said second storage locations in and out of said cache.

19. The computer-readable medium of claim 13, wherein object names are associated with said data objects, wherein the step of generating key values includes generating said key values based on the names of said data objects.

20. The computer-readable medium of claim 13, wherein the step of generating key values includes generating said key values based on the content of said data objects.

21. The computer-readable medium of claim 13, wherein for said each key value of said key values, the first subkey value includes L contiguous bits from said each key value, the second subkey value includes the next M contiguous bits from said each key value, and the third subkey value includes the next N contiguous bit in said each key value.

22. The computer-readable medium of claim 21, wherein the sum of L, M, and N is less than the number of bits in said each key value.

23. The computer-readable medium of claim 13, further including the step of determining whether a requested data object is stored in a cache by performing one or more steps that include inspecting said first storage locations to determine whether said first storage locations include a first subkey value from a key value generated for said requested data object.

24. The computer-readable medium of claim 23, wherein the step of determining whether said requested data object is stored in a cache includes inspecting said first storage locations to determine whether said first storage locations include a second subkey value from the key value generated for said requested data object when said first storage location includes said first subkey value from the key value generated for said requested data object.