Low-overhead index for a flash cache

• US 10,055,351 B1
• Filed: 06/29/2016
• Issued: 08/21/2018
• 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:
  US15/196,163
• Time in Patent Office: 783 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 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.

2. The method of claim 1, wherein the metadata includes a segment type or a segment length, and wherein the identifier comprises a key or a cryptographic hash or a fingerprint and the short identifier comprises, respectively, a short key, a short cryptographic hash or a short fingerprint.

3. The method of claim 1, wherein the metadata in the request is compared with the corresponding metadata in the index when more than one short identifier matches the corresponding portion of the identifier in the lookup request.

4. The method of claim 1, further comprising issuing a read request when the combination is present in the index.

5. The method of claim 4, further comprising returning a provisionally true result to a client before a read of the cache is completed.

6. The method of claim 1, further comprising receiving the segment from the cache and an identifier of the segment from the cache.

7. The method of claim 6, further comprising 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.

8. The method of claim 1, further comprising performing an asynchronous read when the combination is present.

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.

10. The method of claim 9, wherein the metadata includes a segment type or a segment size.

11. The method of claim 9, further comprising disregarding the insertion when the combination is present in the index.

12. The method of claim 9, further comprising updating the index to point to the new segment and marking a previous segment for deletion from the cache.

13. The method of claim 9, further comprising inserting the segment into the cache to improve a locality of the segment for future erasures or future sequential reads.

14. The method of claim 9, further comprising detecting a collision when performing the lookup operation when more than one short identifier matches the identifier of the segment.

15. The method of claim 14, further comprising resolving the collision by comparing the metadata of the segment with the metadata included in the index.

16. The method of claim 9, wherein the short identifier is less than half the size of the identifier.

17. The method of claim 9, wherein the identifier comprises a key, a cryptographic hash, or a fingerprint and the short identifier comprises, respectively, a short key, a short cryptographic hash, or a short fingerprint.

18. The method of claim 17, wherein the identifier comprises a hash of the data segment.

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.

20. The method of claim 19, wherein the metadata includes a segment type or a segment length and the corresponding metadata includes a segment type or a segment length, and wherein the identifier comprises a key, a cryptographic hash, or a fingerprint and the short identifier comprises, respectively, a short key, a short cryptographic hash, or a short fingerprint.