Low-overhead index for a flash cache
First Claim
1. A method for inserting data segments into a cache, the method comprising:
- determining a short identifier for a data segment in preparation for inserting the data segment into the cache, the data segment associated with a metadata;
performing a lookup operation for the data segment in an index using the short identifier, wherein the index includes entries, each entry including at least a combination of a short identifier and a corresponding metadata, wherein each short identifier in the index is a portion of a corresponding identifier;
determining whether a combination is present in the index for the data segment when the short identifier is present in the index by comparing the metadata of the data segment with entries in the index that include a short identifier that matches the short identifier associated with the data segment;
inserting the data segment into the cache when the short identifier or the combination is not present in the index; and
processing the data segment when the combination is found in the index.
4 Assignments
0 Petitions
Accused Products
Abstract
Systems and methods for a low-overhead index for a cache. The index is used to access content or segments in the cache by storing at least an identifier and a location. The index is accessed using the identifier. The identifier may be shortened or be a short identifier. Because a collision may occur, the index may also include one or more meta-data values associated with the data segment. Collisions can be resolved by also comparing the metadata of the segment with the metadata stored in the index. If both the short identifier and metadata match those of the segment, the segment is likely in the cache and can be accessed. Segments can also be inserted into the cache.
-
Citations
20 Claims
-
1. A method for inserting data segments into a cache, the method comprising:
-
determining a short identifier for a data segment in preparation for inserting the data segment into the cache, the data segment associated with a metadata; performing a lookup operation for the data segment in an index using the short identifier, wherein the index includes entries, each entry including at least a combination of a short identifier and a corresponding metadata, wherein each short identifier in the index is a portion of a corresponding identifier; determining whether a combination is present in the index for the data segment when the short identifier is present in the index by comparing the metadata of the data segment with entries in the index that include a short identifier that matches the short identifier associated with the data segment; inserting the data segment into the cache when the short identifier or the combination is not present in the index; and processing the data segment when the combination is found in the index. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
7. A method for inserting data segments into a cache, the method comprising:
-
performing a lookup operation in an index using a short identifier of a data segment to determine whether the data segment is present in the cache, wherein the data segment is associated with a metadata, wherein the index includes entries, each entry including at least a combination of a short identifier and a corresponding metadata, wherein each short identifier in the index is a portion of a corresponding identifier; when the short identifier is found in an entry in the index, comparing a metadata included in the entry with the metadata associated with the data segment; returning a miss when the metadata in the entry does not match the metadata associated with the data segment; inserting the data segment into the cache when the short identifier is not found in the index or when receiving the miss; determining that a combination for the data segment is present in the index when the short identifier associated with the data segment is present in the index and the metadata in an index entry associated with the matching short identifier of the data segment matches the metadata associated with the data segment;
verifying that the combination identifies the data segment and inserting the data segment into the cache when the combination is not verified, wherein the data segment is not inserted into the cache when the combination is verified. - View Dependent Claims (8, 9, 10, 11, 12, 13)
-
-
14. A non-transitory computer readable medium comprising computer executable instructions that when executed perform a method for inserting data segments into a cache, the method comprising:
-
performing a lookup operation in an index using a short identifier of a data segment to determine whether the data segment is present in the cache, wherein the data segment is associated with a metadata, wherein the index includes entries, each entry including at least a combination of a short identifier and a corresponding metadata, wherein each short identifier in the index is a portion of a corresponding identifier; when the short identifier is found in an entry in the index, comparing a metadata included in the entry with the metadata associated with the data segment; returning a miss when the metadata in the entry does not match the metadata associated with the data segment; inserting the data segment into the cache when the short identifier is not found in the index or when receiving the miss; determining that a combination for the data segment is present in the index when the short identifier associated with the data segment is present in the index and the metadata in an index entry associated with the matching short identifier of the data segment matches the metadata associated with the data segment;
verifying that the combination identifies the data segment and inserting the data segment into the cache when the combination is not verified, wherein the data segment is not inserted into the cache when the combination is verified. - View Dependent Claims (15, 16, 17, 18, 19, 20)
-
Specification