US6128623A
Expired / Lapsed
US
⏱️ 0.0 years remaining
High performance object cache
Assignee: Google LLC
•
Filing: 1998-04-15
•
Granted: 2000-10-03
•
Expires: 2018-04-15
Abstract
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.
Inventors
- 👤 Peter Mattis
- 👤 John Plevyak
- 👤 Matthew Haines
- 👤 Adam Beguelin
- 👤 Brian Totty
- 👤 David Gourley
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-03 06:45
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/90; G06F16/95; G06F16/957; G06F16/9574; H; H04; H04L; H04L67/00; H04L67/50; H04L67/56; H04L67/568; Y; Y10; Y10S; Y10S707/00; Y10S707/953; Y10S707/955; Y10S707/99941; Y10S707/99944
Claims Analysis
Total Claims: 24
Claim 1
Independent Claim
165 words
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.
Claim 2
Dependent Claim
165 words
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.
Claim 3
Dependent Claim
80 words
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.
Claim 4
Dependent Claim
83 words
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.
Claim 5
Dependent Claim
21 words
The method recited in claim 1, further comprising the steps of: storing the information objects contiguously in a mass storage device.
Claim 6
Dependent Claim
45 words
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.
Claim 7
Dependent Claim
26 words
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.
Claim 8
Dependent Claim
27 words
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.
Claim 9
Dependent Claim
23 words
The method recited in claim 7, further comprising the step of consolidating streaming data transfers of different speeds into a write aggregation buffer.
Claim 10
Dependent Claim
25 words
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.
Claim 11
Dependent Claim
20 words
The method recited in claim 9, wherein the fragments comprising an information object are linked from the previous fragment key.
Claim 12
Dependent Claim
198 words
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.
Claim 13
Dependent Claim
198 words
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.
Claim 14
Dependent Claim
86 words
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.
Claim 15
Dependent Claim
89 words
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.
Claim 16
Dependent Claim
27 words
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.
Claim 17
Dependent Claim
46 words
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.
Claim 18
Dependent Claim
32 words
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.
Claim 19
Dependent Claim
33 words
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.
Claim 20
Dependent Claim
29 words
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.
Claim 21
Dependent Claim
31 words
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.
Claim 22
Dependent Claim
21 words
The computer-readable medium recited in claim 19, wherein the fragments comprising an information object are linked from the previous fragment key.
Claim 23
Dependent Claim
28 words
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.
Claim 24
Dependent Claim
27 words
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.
References Cited (Backward Citations)
US5611049A
Cited
US5542087A
Cited
US5881229A
Cited
US5748954A
Cited
US5872969A
Cited
US5732267A
Cited
US5826242A
Cited
US5909695A
Cited
US5701432A
Cited
US5727159A
Cited
US5864852A
Cited
EP0811939A2
Cited
US5935207A
Cited
EP0834819A2
Cited
US5852717A
Cited
US5974421A
Cited
US5870763A
Cited
US5924116A
Cited
US5950205A
Cited
US5987233A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-10-03 | 2004-04-03 | 2004-10-03 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-10-03 | 2008-04-03 | 2008-10-03 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-10-03 | 2012-04-03 | 2012-10-03 | $7700.00 | Window Closed / Lapsed |