Tombstones for no longer relevant deduplication entries

• US 10,528,280 B1
• Filed: 01/31/2017
• Issued: 01/07/2020
• Est. Priority Date: 01/31/2017
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Sandvig, Cary A., Sapuntzakis, Constantine P., Wang, Feng
• Primary Examiner(s): Gu, Shawn X
• Application Number:
  US15/420,726
• Time in Patent Office: 1,071 Days
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

An implementation of the disclosure provides a system comprising a storage array comprising a plurality of data blocks and a storage controller coupled to the storage array. The storage controller comprising a processing device to identify a canonical instance of a data block in a vector associated with a deduplication map. The vector represents a plurality of updates to the deduplication map over a determined time period. A deduplication reference representing duplicate data of the data block in the storage array is select from the deduplication map. The deduplication reference is remapped in the deduplication map to point to the canonical instance. Based on the remapping, an entry in the deduplication map for the deduplication reference is updated with a record. Responsive to detecting that the entry is in a location associated with an original entry of the data block in the deduplication map, delete the entry with the record.

Claims

1. A system comprising:

a storage array comprising a plurality of data blocks; and

a storage controller coupled to the storage array, the storage controller comprising a processing device, the processing device to;

identify a canonical instance of a data block in a vector associated with a deduplication map, the vector represents a plurality of updates to the deduplication map over a determined time period;

select, from the deduplication map, a deduplication reference representing duplicate data of the data block in the storage array, wherein the canonical instance represents an earliest occurrence of the duplicate data of the data block in the vector associated with the deduplication map;

remap the deduplication reference in the deduplication map to point to the canonical instance;

update an entry in the deduplication map for the deduplication reference with a record based on the remapped the deduplication reference; and

responsive to detecting that the entry is in a location associated with an original entry of the data block in the deduplication map, delete the entry with the record.

2. The system of claim 1, wherein to determine the vector, the processing device is further to determine a range of sequence identifiers associated with a plurality of updates to the data block.

3. The system of claim 2, wherein to determine whether the deduplication reference is in the vector, the processing device is further to:

identify a sequence identifier for the deduplication reference; and

determine whether the sequence identifier is within the range of sequence identifiers associated with the vector.

4. The system of claim 3, wherein the processing device is further to determine whether the identify sequence identifier for the deduplication reference corresponds to a sequence identifier for the data block.

5. The system of claim 4, wherein the processing device is further to, responsive to determining that the identified sequence identifier corresponds to a sequence identifier for the data block, delete the entry associated with the record from the deduplication map.

6. The system of claim 1, wherein, the processing device is further to determine whether a hash value associated with the deduplication reference and the data block correspond.

7. A method comprising:

identifying, by a processing device, a canonical instance of a data block associated with a deduplication map;

selecting, by the processing device, a deduplication reference from the deduplication map, the deduplication reference represents duplicate data of the data block, wherein the canonical instance represents an earliest occurrence of the duplicate data of the data block in an identified vector for the deduplication map;

remaping the deduplication reference in the deduplication map to point to the canonical instance;

update an entry in the deduplication map for the deduplication reference with a record based on the remaping;

determining, by the processing device, that a location of the entry corresponds to a vector associated with an original entry of the data block in the deduplication map, the vector represents a range of sequence identifiers associated with updates to the deduplication map; and

performing, in view of the determining, a trimming process to trim the entry with the record from the deduplication map.

8. The method of claim 7, wherein determining that the location of the deduplication reference corresponds to the vector:

identifying a sequence identifier for the deduplication reference; and

determining whether the sequence identifier is within the range of sequence identifiers associated with the vector.

9. The method of claim 8, further comprising determining whether the identify sequence identifier for the deduplication reference corresponds to a sequence identifier associated with an original entry for the data block in the deduplication map.

10. The method of claim 9, wherein responsive to determining that the identify sequence corresponds to a sequence identifier for the original entry, issuing an instruction to trim the record from the deduplication map.

11. The method of claim 7, wherein the selecting comprises determining whether a hash value in the deduplication map for the deduplication reference and the data block correspond.

12. A non-transitory computer readable storage medium storing instructions, which when executed, cause a processing device to:

select, by the processing device, a canonical instance for a data block associated with a plurality of deduplication references in a deduplication map, the deduplication references represent duplicate data of the data block in a vector of the deduplication map;

remap the plurality of deduplication references in the vector to point to the canonical instance, wherein the canonical instance represents an earliest occurrence of the duplicate data of the data block in an identified vector for the deduplication map;

update each entry associated with the plurality of deduplication references with a record based on remapping the plurality of deduplication references; and

responsive to detecting that the location of an entry corresponds to an original entry of the data block in the deduplication map, trim entries from the deduplication map that are associated with each record.

13. The non-transitory computer readable storage medium of claim 12, wherein the processing device is further to identify the vector associated with the plurality of deduplication references based on a sequence identifier for the canonical instance.

14. The non-transitory computer readable storage medium of claim 12, wherein the vector comprises a range of sequence identifiers associated with updates to the data block.

15. The non-transitory computer readable storage medium of claim 14, wherein the processing device is further to:

identify a sequence identifier for each of the deduplication references; and

determine whether the sequence identifier is within the range of sequence identifiers associated with the vector.

16. The non-transitory computer readable storage medium of claim 15, wherein the processing device is further to determine whether at least one of the identify sequence identifier for each of the deduplication references corresponds to a sequence identifier for the original entry associated with the data block.

17. The non-transitory computer readable storage medium of claim 12, wherein the processing device is further to determine whether a hash value for each of the deduplication references in the deduplication and the data block correspond.