Tombstones for no longer relevant deduplication entries

Patent metadata

Field	Value
Publication number	US-10528280-B1
Application number	US-201715420726-A
Country	US
Kind code	B1
Filing date	Jan 31, 2017
Priority date	Jan 31, 2017
Publication date	Jan 7, 2020
Grant date	Jan 7, 2020

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.

First claim

What is claimed is:

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.

Assignees

• Pure Storage Inc

Inventors

• Sandvig Cary A
• Sapuntzakis Constantine P
• Wang Feng

Classifications

• G06F3/0641 Primary

  De-duplication techniques · CPC title

• G06F3/0608

  Saving storage space on storage systems · CPC title

• G06F3/0673

  Single storage device · CPC title

• G06F12/0253

  Garbage collection, i.e. reclamation of unreferenced memory · CPC title

• G06F3/061

  Improving I/O performance · CPC title