High performance object cache

• US 6,128,623 A
• Filed: 04/15/1998
• Issued: 10/03/2000
• 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): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US09/060,866
• Time in Patent Office: 902 Days
• Field of Search: 707/100, 707/103, 711/118, 711/119, 711/120, 711/121, 711/122
• US Class Current: 711/118
• 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 may be 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 so that inactive objects are deleted and free space becomes contiguous. Because the objects are substantially contiguously allocated, reading and writing an typical object requires only one or two disk head actuator movements; thus, the cache can efficiently and smoothly stream data off of the storage device, providing optimal delivery of multimedia objects. The disclosure also encompasses a computer apparatus, computer program product, and computer data signal embodied in a carrier wave that are similarly configured.

Claims

1. In a cache for information objects that are identified by key values based on names of the information objects, comprising a tag table that indexes the information objects using set subkey values based on the key values, a directory table having a plurality of blocks indexed to sets in the tag table by second subkey values based on the key values, and data storage areas referenced by the blocks in the directory table, a method of delivering a requested information object to a client from the cache at a server, comprising the steps of:

(A) receiving a name that identifies a requested information object;

(B) computing a fixed size key value comprising a plurality of subkeys, 11 based on the name;

(C) looking up the requested information object in a directory table, using the subkeys as lookup keys; and

(D) retrieving a copy of the requested information object from the data storage areas using a reference contained in a matching block in the directory table.

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

selecting a version of the requested information object from a list in said cache of a plurality of versions of the requested information objects;

identifying a storage location of the requested information object in said cache based on an object key stored in the list in association with the first version;

retrieving the requested information object from the storage location; and

delivering the requested information object to the client.

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

storing the list contiguously with each of the plurality of versions of the requested information object;

in each of the blocks, storing a size value of the requested information object in association with such block, wherein the size value indicates a storage size of the list and the plurality of versions of the information object;

and wherein step (D) comprises the step of reading the list and the plurality of versions concurrently.

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

storing the information objects contiguously in a mass storage device.

5. The method recited in claim 4, wherein the step of storing the information objects comprises the step of writing the information objects in contiguous available storage space of the mass storage device, while concurrently performing steps (A) through (D) with respect to another information object.

6. The method recited in claim 4, further comprising the steps of:

storing each of the information objects in a contiguous pool of the mass storage device.

7. The method recited in claim 6, further comprising the steps of:

storing each of the information objects in one of a plurality of arenas in the pool.

8. The method recited in claim 7, further comprising the step of consolidating streaming data transfers of different speeds into a write aggregation buffer.

9. The method recited in claim 7, further comprising the steps of:

storing each of the information objects in one or more fragments, allocated from arenas.

10. The method recited in claim 9, wherein the fragments comprising an information object are linked from the previous fragment key.

22. The method recited in claim 1, which steps (B) and (C) use subkey partition and table organization, thereby providing fast cache miss determination while using modest memory.

11. 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:

establishing a cache for information objects that are identified by key values based on names of the information objects, comprising a tag table that indexes the information objects using set subkey values based on the key values, a directory table having a plurality of blocks indexed to sets in the tag table by second subkey values based on the key values, and data storage areas referenced by the blocks in the directory table;

delivering a requested information object to a client from the cache at a server, by;

(A) receiving a name that identifies a requested information object;

(B) computing a fixed size key value comprising a plurality of subkeys, based on the name;

(C) looking up the requested information object in a directory table, using the subkeys as lookup keys; and

(D) retrieving a copy of the requested information object from the data storage areas using a reference contained in a matching block in the directory table.

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

selecting a version of the requested information object from a list in said cache of a plurality of versions of the requested information objects;

identifying a storage location of the requested information object in said cache based on an object key stored in the list in association with the first version;

retrieving the requested information object from the storage location; and

delivering the requested information object to the client.

13. The computer-readable medium recited in claim 12, further comprising sequences of instructions for performing the step of storing the list contiguously with each of the plurality of versions of the requested information object;

in each of the blocks, storing a size value of the requested information object in association with such block, wherein the size value indicates a storage size of the list and the plurality of versions of the information object;

and wherein step (D) comprises the step of reading the list and the plurality of versions concurrently.

14. The computer-readable medium recited in claim 11, further comprising sequences of instructions for performing the step of storing the information objects contiguously in a mass storage device.

15. The computer-readable medium recited in claim 14, wherein the step of storing the information objects comprises the step of writing the information objects in contiguous available storage space of the mass storage device, while concurrently performing steps (A) through (D) with respect to another information object.

16. The computer-readable medium recited in claim 14, further comprising sequences of instructions for performing the step of storing each of the information objects in a contiguous pool of the mass storage device.

17. The computer-readable medium recited in claim 16, further comprising sequences of instructions for performing the step of storing each of the information objects in one of a plurality of arenas in the pool.

18. The computer-readable medium recited in claim 17, further comprising sequences of instructions for performing the step of consolidating streaming data transfers of different speeds into a write aggregation buffer.

19. The computer-readable medium recited in claim 17, further comprising sequences of instructions for performing the step of storing each of the information objects in one or more fragments, allocated from arenas.

20. The computer-readable medium recited in claim 19, wherein the fragments comprising an information object are linked from the previous fragment key.

21. The computer-readable media recited in claim 11, which steps (B) and (C) use subkey partition and table organization, thereby providing fast cache miss determination while using modest memory.