Alias-free content-indexed object cache

• US 6,292,880 B1
• Filed: 04/15/1998
• Issued: 09/18/2001
• 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, Totty, Brian, Mattis, Peter, Plevyak, John, Haines, Matthew
• Primary Examiner(s): Kim, Matthew
• Assistant Examiner(s): ANDERSON, MATTHEW D
• Application Number:
  US09/060,886
• Time in Patent Office: 1,252 Days
• Field of Search: 711/118, 711/3, 711/123, 711/206, 711/216, 711/221, 707/3, 707/10, 707/203, 707/7
• US Class Current: 711/216
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/99937 Sorting

Abstract

A method for caching information objects is provided. 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 contiguously allocated within an arena and are mapped to directory tables that provide an efficient search mechanism. Each object is identified by a name key and a content key. The name key is constructed by applying a hash function to the composition of the name or URL of the object along with implicit or explicit context about the request. The content key is constructed by applying a hash function to the entire contents of the object data. Buckets and blocks in the directory tables store tags and subkeys derived from the keys. Since duplicate objects that have different names will hash to the same content key, the cache can detect duplicate objects even though they have different names, and store only one copy of the object. As a result, cache storage usage is dramatically reduced, and tracking object aliases is not required. The disclosure also encompasses a computer apparatus, computer program product, and computer data signal embodied in a carrier wave that are configured similarly.

Claims

1. A method of delivering an information object to a client from a cache at a server, comprising the steps of:

(A) establishing a cache table in a memory of the server, the cache table mapping name key values to vectors of alternates, wherein said information object is associated with a name key value that said cache table maps to a particular vector of said vectors of alternates;

(B) computing a content key that uniquely identifies the information object by applying a hash function to the information object; and

(C) storing the content key in one of the alternates of said particular vector of alternates;

(D) computing another content key that uniquely identifies another information object by applying a hash function to said other information object, wherein said other information object is associated with said name key value; and

(E) storing the other content key in another one of said alternates of said particular vector of alternates.

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

storing, in said one of the alternates, a reference to the location of the information object on a mass storage device, wherein the reference is associated with the content key.

3. The method recited in claim 1, wherein step (B) comprises the step of:

computing a content key that uniquely identifies the information object by applying a one-way hash function to the information object.

4. The method recited in claim 3, wherein step (B) comprises the step of:

computing a content key that uniquely identifies the information object by applying an MD5 one-way hash function to the information object.

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

receiving a request to retrieve the information object using the name of the information object;

looking up the information object in said cache table using the name key;

retrieving said particular vector of alternates;

selecting a content key from among the alternates of said particular vector of alternates based upon a context of the request;

looking up a location of the information object in the mass storage device based on the content key; and

delivering the information object to the client.

6. The method recited in claim 1, wherein step (A) comprises the steps of:

(A1) computing the name key based upon the name of the information object and a context of a request to retrieve the information object.

7. The method recited in claim 6, wherein step (A1) comprises the steps of:

computing the name key by applying a one-way hash function to the name of the information object combined with information describing a context of a request to retrieve the information object.

8. The method recited in claim 1, wherein step (A) comprises the steps of:

computing the name key by applying a MD5 one-way hash function to the name of the information object combined with information describing a context of a request to retrieve the information object.

9. The method recited in claim 1, wherein said other information object is a version of said information object.

10. A computer-readable medium carrying one or more sequences of instructions for caching information objects, 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:

(A) establishing a cache table in a memory of the server, the cache table mapping name key values to vectors of alternates, wherein said information object is associated with a name key value that said cache table maps to a particular vector of said vectors of alternates;

(B) computing a content key that uniquely identifies the information object by applying a hash function to the information object; and

(C) storing the content key in one of the alternates of said particular vector of alternates;

(D) computing another content key that uniquely identifies another information object by applying a hash function to said other information object, wherein said other information object is associated with said name key value; and

(E) storing the other content key in another one of said alternates of said particular vector of alternates.

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

storing, in said one of the alternates, a reference to the location of the information object on a mass storage device, wherein the reference is associated with the content key.

12. The computer-readable medium recited in claim 10, wherein step (B) comprises the step of:

computing a content key that uniquely identifies the information object by applying a one-way hash function to the information object.

13. The computer-readable medium recited in claim 12, wherein step (B) comprises the step of:

computing a content key that uniquely identifies the information object by applying an MD5 one-way hash function to the information object.

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

receiving a request to retrieve the information object using the name of the information object;

looking up the information object in said cache table using the name key;

retrieving said particular vector of alternates;

selecting a content key from among the alternates of said particular vector of alternates based upon a context of the request;

looking up a location of the information object in the mass storage device based on the content key; and

delivering the information object to the client.

15. The computer-readable medium recited in claim 10, wherein step (A) comprises the steps of:

(A1) computing the name key based upon the name of the information object and a context of a request to retrieve the information object.

16. The computer-readable medium recited in claim 15, wherein step (A1) comprises the steps of:

computing the name key by applying a one-way hash function to the name of the information object combined with information describing a context of a request to retrieve the information object.

17. The computer-readable medium recited in claim 10, wherein step (A) comprises the steps of:

computing the name key by applying a MD5 one-way hash function to the name of the information object combined with information describing a context of a request to retrieve the information object.

18. The computer-readable medium recited in claim 10, wherein said other information object is a version of said information object.

19. A method for caching data objects, the method comprising the steps of:

establishing a first mapping between name hash key values, which are generated by applying a hash function to names associated with said data objects, and a first set of storage locations;

establishing a second mapping between content hash key values, which are generated by applying a hash function to the content of said data objects, and a second set of storage locations;

storing said content hash key values in said first set of storage locations; and

storing said data objects in said second set of storage locations.

20. The method of claim 19 wherein:

the first mapping maps a first name hash key value to a particular first storage location within said first set of storage locations;

said first name hash key value is associated with a first name for a particular data object;

the method further comprises the step of locating said particular data object in response to a first request by performing the steps of;

using said first mapping and said first name hash key value to locate said particular first storage location;

reading a content hash key value located at said particular first storage location;

using said second mapping and said content hash key value to locate a particular second storage location within said second set of storage locations; and

reading said particular data object from said particular second storage location.

21. The method of claim 20 wherein:

said first mapping also maps a second name hash key value to said particular first storage location;

said second name hash key value is associated with a second name for said particular data object that is different from said first name for said particular data object;

the method further comprises the step of locating said particular data object in response to a second request by performing the steps of;

using said first mapping and said second name hash key value to locate said particular first storage location;

reading said content hash key value located at said particular first storage location;

using said second mapping and said content hash key value to locate said particular second storage location within said second set of storage locations; and

reading said particular data object from said particular second storage location.

22. The method of claim 19 wherein:

said second set of storage locations is a part of a cache; and

the steps of establishing a first mapping and storing said data objects include;

if a particular data object has a plurality of alternative names, then

(A) storing the particular object at only one location within said cache, and

(B) mapping, within said first mapping, a plurality of name hash key values, which correspond to said plurality of alternative names, to one or more storage locations within said first set of storage locations, wherein each of said one or more storage locations contains a content hash key value that said second mapping maps to said one location where said particular data object is located.

23. A computer-readable medium carrying one or more sequences of instructions for caching data objects, 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:

establishing a first mapping between name hash key values, which are generated by applying a hash function to names associated with said data objects, and a first set of storage locations;

establishing a second mapping between content hash key values, which are generated by applying a hash function to the content of said data objects, and a second set of storage locations;

storing said content hash key values in said first set of storage locations; and

storing said data objects in said second set of storage locations.

24. The computer-readable of claim 23 wherein:

the first mapping maps a first name hash key value to a particular first storage location within said first set of storage locations;

said first name hash key value is associated with a first name for a particular data object;

the computer-readable media further comprises instructions for performing the step of locating said particular data object in response to a second request by performing the steps of;

using said first mapping and said first name hash key value to locate said particular first storage location;

reading a content hash key value located at said particular first storage location;

using said second mapping and said content hash key value to locate a particular second storage location within said second set of storage locations; and

reading said particular data object from said particular second storage location.

25. The computer-readable of claim 24 wherein:

said first mapping also maps a second name hash key value to said particular first storage location;

said second name hash key value is associated with a second name for said particular data object that is different from said first name for said particular data object;

the computer-readable media further comprises instructions for performing the step of locating said particular data object in response to a second request by performing the steps of;

using said first mapping and said second name hash key value to locate said particular first storage location;

reading said content hash key value located at said particular first storage location;

using said second mapping and said content hash key value to locate said particular second storage location within said second set of storage locations; and

reading said particular data object from said particular second storage location.

26. The computer-readable of claim 23 wherein:

said second set of storage locations is a part of a cache; and

the steps of establishing a first mapping and storing said data objects include;

if a particular data object has a plurality of alternative names, then

(A) storing the particular object at only one location within said cache, and

(B) mapping, within said first mapping, a plurality of name hash key values, which correspond to said plurality of alternative names, to one or more storage locations within said first set of storage locations, wherein each of said one or more storage locations contains a content hash key value that said second mapping maps to said one location where said particular data object is located.