THINING DATABASES FOR GARBAGE COLLECTION

• US 20200133548A1
• Filed: 12/30/2019
• Published: 04/30/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
• Granted Patent: US 11,262,929 B2
• Time in Patent Office: 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 storage controller coupled to the storage array. The storage controller comprising a processing device to remap a plurality of deduplication references in a deduplication map to point to an earlier occurrence of duplicate data of a data block for the deduplication map. The processing device further to update an entry of the deduplication map associated with the plurality of deduplication references with a record indicating that the entry is no longer referenced and trim the entry from the deduplication map that is associated with the record.

Claims

1. A system comprising:

a storage array; and

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

remap a plurality of deduplication references in a deduplication map to point to an earlier occurrence of duplicate data of a data block for the deduplication map;

update an entry of the deduplication map associated with the plurality of deduplication references with a record indicating that the entry is no longer referenced;

trim the entry from the deduplication map that is associated with the record.

2. The system of claim 1, wherein the processing device further to:

select the earlier occurrence of duplicate data associated with the plurality of deduplication references in the deduplication map, wherein the deduplication references represent duplicate data of the data block in the deduplication map.

3. The system of claim 2, wherein the processing device further to determine that a location of the entry corresponds to an original entry of the data block in the deduplication map based on a range of sequence identifiers associated with updates to the deduplication map.

4. The system of claim 3, wherein to determine the location, the processing device to:

identify one of the sequence identifiers for the entry; and

determine whether the sequence identifier is within the range of sequence identifiers.

5. The system of claim 3, wherein responsive to determining that the location of the entry corresponds to the original entry of the data block in the deduplication map, the processing device to issue an instruction to perform trim of the entry from the deduplication map that is associated with the record.

6. The system of claim 2, wherein the to select, the processing device to determine whether a hash value in the deduplication map for the deduplication references and the data block correspond.

7. The system of claim 1, wherein the storage array stores the data block.

8. A method comprising:

remapping a plurality of deduplication references in a deduplication map to point to an earlier occurrence of duplicate data of a data block for the deduplication map;

updating, by a processing device, an entry of the deduplication map associated with the plurality of deduplication references with a record indicating that the entry is no longer referenced;

trimming the entry from the deduplication map that is associated with the record.

9. The method of claim 8, further comprising:

selecting the earlier occurrence of duplicate data associated with the plurality of deduplication references in the deduplication map, wherein the deduplication references represent duplicate data of the data block in the deduplication map.

10. The method of claim 9, further comprising determining that a location of the entry corresponds to an original entry of the data block in the deduplication map based on a range of sequence identifiers associated with updates to the deduplication map.

11. The method of claim 10, wherein determining the location comprises:

identifying one of the sequence identifiers for the entry; and

determining whether the sequence identifier is within the range of sequence identifiers.

12. The method of claim 10, wherein responsive to determining that the location of the entry corresponds to the original entry of the data block in the deduplication map, issuing an instruction to performing trimming of the entry from the deduplication map that is associated with the record.

13. The method of claim 9, wherein the selecting comprises determining whether a hash value in the deduplication map for the deduplication references and the data block correspond.

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

remap, by the processing device, a plurality of deduplication references in a deduplication map to point to an earlier occurrence of duplicate data of a data block for the deduplication map;

update an entry of the deduplication map associated with the plurality of deduplication references with a record indicating that the entry is no longer referenced;

trim the entry from the deduplication map that is associated with the record.

15. The non-transitory computer readable storage medium of claim 14, wherein the processing device is further to select the earlier occurrence of duplicate data associated with the plurality of deduplication references in the deduplication map, wherein the deduplication references represent duplicate data of the data block in the deduplication map.

16. The non-transitory computer readable storage medium of claim 15, wherein the processing device further to determine that a location of the entry corresponds to an original entry of the data block in the deduplication map based on a range of sequence identifiers associated with updates to the deduplication map.

17. The non-transitory computer readable storage medium of claim 16, wherein to determine the location, the processing device to:

identify one of the sequence identifiers for the entry; and

determine whether the sequence identifier is within the range of sequence identifiers.

18. The non-transitory computer readable storage medium of claim 16, wherein responsive to determining that the location of the entry corresponds to the original entry of the data block in the deduplication map, the processing device to issue an instruction to perform trim of the entry from the deduplication map that is associated with the record.

19. The non-transitory computer readable storage medium of claim 15, wherein the to select, the processing device to determine whether a hash value in the deduplication map for the deduplication references and the data block correspond.

20. The non-transitory computer readable storage medium of claim 15, wherein the data block is stored in a storage array.