Low-overhead index for a flash cache
First Claim
1. A method for indexing data segments in a cache, the method comprising:
- performing a lookup operation for a segment in an index using an identifier and 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;
determining whether a combination is present in the index, wherein the combination is present in the index when a short identifier in the index matches a corresponding portion of the identifier in the lookup operation and the metadata in the lookup operation matches the corresponding metadata associated with the short identifier in the index, wherein the corresponding metadata associated with the short identifier in the index allows the combination in the index to be selected when more than one short identifier in the index matches the corresponding portion of the identifier in the lookup operation, wherein the short identifier, considered alone, is not guaranteed to correspond to the segment; and
accessing a segment in the cache based on a location in the index associated with the combination.
9 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 indexing data segments in a cache, the method comprising:
-
performing a lookup operation for a segment in an index using an identifier and 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; determining whether a combination is present in the index, wherein the combination is present in the index when a short identifier in the index matches a corresponding portion of the identifier in the lookup operation and the metadata in the lookup operation matches the corresponding metadata associated with the short identifier in the index, wherein the corresponding metadata associated with the short identifier in the index allows the combination in the index to be selected when more than one short identifier in the index matches the corresponding portion of the identifier in the lookup operation, wherein the short identifier, considered alone, is not guaranteed to correspond to the segment; and accessing a segment in the cache based on a location in the index associated with the combination. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A method for inserting a data segment into a cache, the method comprising:
-
performing a lookup operation for a segment in an index based on an identifier of the segment by comparing the identifier with short identifiers included in the index, wherein the index includes entries, each entry associating a short identifier with a metadata, wherein each short identifier is a portion of a corresponding identifier; for each short identifier in the index that matches a portion of the identifier included in the lookup request, comparing a metadata of the segment associated with the lookup operation with a metadata associated with each of the matching short identifiers in the index, wherein the metadata associated with the short identifiers in the index allows one of the matching short identifiers in the index to be identified as being more likely to correspond to the segment in the lookup operation; verifying that a segment in the cache and associated with the short identifier determined to correspond to the segment in the lookup operation actually corresponds to the segment in the lookup operation; and inserting the segment into the cache when both the short identifier and the metadata corresponding to the identifier and the segment associated with the lookup operation are not present in the index. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A method for indexing data segments in a cache, the method comprising:
-
performing a lookup operation in an index for a segment in the cache using an identifier and a metadata related to the segment, wherein the index includes short identifiers and corresponding metadata, wherein the index includes entries, each entry including at least a combination of a short identifier and a metadata, wherein each short identifier in the index is a portion of a corresponding identifier, wherein none of the short identifiers, considered alone, is guaranteed to correspond to the segment; determining whether a combination for the segment associated with the lookup operation is present in the index, wherein the combination for the segment is present in the index when a short identifier in the index matches a corresponding portion of the identifier in the lookup request and the metadata associated with the lookup operation matches the corresponding metadata associated with the short identifier in the index, wherein the corresponding metadata associated with the short identifier in the index allows the combination of the short identifier and the corresponding metadata in the index to be selected when more than one short identifier in the index matches the corresponding portion of the identifier included in the lookup operation; and accessing the segment in the cache based on a location in the index associated with the combination; and comparing the identifier received from the cache with the identifier in the lookup request to confirm that the segment from the cache is the segment identified in the lookup request. - View Dependent Claims (20)
-
Specification