Low-overhead index for a flash cache

• US 10,353,820 B2
• Filed: 08/14/2018
• Issued: 07/16/2019
• Est. Priority Date: 06/29/2016
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Wallace, Grant R., Shilane, Philip N.
• Primary Examiner(s): Chappell, Daniel C.
• Application Number:
  US16/103,499
• Publication Number:
  US 20190004957A1
• Time in Patent Office: 336 Days
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0877 Cache access modes
• CPC Class Codes: G06F 12/0891 using clearing, invalidating or resetting means
• CPC Class Codes: G06F 12/0893 Caches characterised by their organisation or structure
• CPC Class Codes: G06F 12/1408 by using cryptography for digital transmission H04L9/00
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/222 Non-volatile memory

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.

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.

2. The method of claim 1, wherein processing the data segment includes disregarding the data segment and leaving an existing data segment in the cache.

3. The method of claim 2, wherein processing the data segment includes improving locality in the cache by inserting the data segment into the cache and marking the previous data segment in the cache for deletion.

4. The method of claim 1, further comprising, after determining that the combination is present in the index, comparing a full identifier of the data segment with a full identifier associated with the combination in the index.

5. The method of claim 1, further comprising, when more than one combination is found in the index, identifying a most correct combination in the index.

6. The method of claim 5, further comprising identifying the most correct combination based on the metadata and the short identifier or based on a full identifier.

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.

8. The method of claim 7, further comprising disregarding the data segment and leaving an existing data segment in the cache when the combination is verified.

9. The method of claim 8, further comprising improving locality in the cache by inserting the data segment into the cache and marking the previous data segment in the cache for deletion.

10. The method of claim 7, further comprising, after determining that the combination is present in the index, verifying the combination by comparing a full identifier of the data segment with a full identifier associated with the combination in the index.

11. The method of claim 7, further comprising, when more than one combination is found in the index, identifying a most correct combination in the index.

12. The method of claim 11, further comprising identifying the most correct combination based on comparing the metadata associated with the data segment with the metadata stored in the entries whose short identifiers match the short identifier of the data segment.

13. The method of claim 11, further comprising identifying a most correct combination based on a full identifier of the data segment.

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.

15. The non-transitory computer readable medium of claim 14, further comprising disregarding the data segment and leaving an existing data segment in the cache when the combination is verified.

16. The non-transitory computer readable medium of claim 15, further comprising improving locality in the cache by inserting the data segment into the cache and marking the previous data segment in the cache for deletion.

17. The non-transitory computer readable medium of claim 14, further comprising, after determining that the combination is present in the index, verifying the combination by comparing a full identifier of the data segment with a full identifier associated with the combination in the index.

18. The non-transitory computer readable medium of claim 14, further comprising, when more than one combination is found in the index, identifying a most correct combination in the index.

19. The non-transitory computer readable medium of claim 18, further comprising identifying the most correct combination based on comparing the metadata associated with the data segment with the metadata stored in the entries whose short identifiers match the short identifier of the data segment.

20. The non-transitory computer readable medium of claim 18, further comprising identifying a most correct combination based on a full identifier of the data segment.