Low-overhead index for a flash cache
AssigneeEMC IP Holding Company LLC
InventorsGrant R. Wallace, Philip N. Shilane
Life of this patent
Estimating the term…
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.
Claims20
A method for managing data segments stored in a cache, the method comprising:
- storing an index in a memory, wherein the index includes entries corresponding to data segments stored in the cache, wherein each entry in the index includes a short identifier and metadata associated with a data segment;
- detecting a collision when multiple short identifiers in the index satisfy a query to the index, wherein the query is associated with an operation on a specific data segment in the cache and wherein the query is associated with information about the specific data segment;
- resolving the collision based on the metadata associated with the multiple short identifiers that satisfy the query by identifying, from among entries in the index associated with the multiple short identifiers, a specific entry that includes a combination of a short identifier that satisfies the query and metadata that matches the information about the specific data segment;
- and
- performing the operation on the specific data segment in the cache identified in the specific entry.
A method for managing data segments stored in a cache, the method comprising:
- storing an index in a memory, wherein the index includes entries corresponding to data segments stored in the cache, wherein each entry in the index includes a combination of a short identifier and metadata associated with a data segment;
- determining whether a combination for a data segment is present in the index, wherein a combination is present at least when a short identifier fora data segment associated with an operation in the cache matches a short identifier in the index;
- detecting a collision when multiple short identifiers in the index satisfies a query to the index related to the data segment, wherein the query is associated with the operation in the cache on a specific data segment and wherein the query is associated with information about the specific data segment;
- resolving the collision, when the multiple short identifiers satisfy the query, based on the metadata associated with the multiple identifiers in the index and the information associated with the specific data segment to identify a specific entry in the index that is associated with the specific data segment associated with the query;
- and
- performing the operation on the specific data segment.
Dependencies are inferred from the claim text.