Scalable garbage collection

Patent metadata

Field	Value
Publication number	US-10846216-B2
Application number	US-201816170596-A
Country	US
Kind code	B2
Filing date	Oct 25, 2018
Priority date	Oct 25, 2018
Publication date	Nov 24, 2020
Grant date	Nov 24, 2020

Abstract

A method of scalable garbage collection includes receiving an indication to perform a garbage collection process on a section of a database of a storage array comprising a plurality of storage devices. The method further includes determining, by a processing device of a storage array controller of the storage array, whether the section corresponds to any check-pointed data set. The method further includes, if the section does not correspond to any check-pointed data set: performing the garbage collection process on the section. The method further includes, if the section does correspond to a check-pointed data set: performing, by the processing device, a scalable garbage collection process on the section.

First claim

What is claimed is:

1. A method, comprising:
initiating a garbage collection process on a section of a database of a storage array comprising a plurality of storage devices;
determining, by a processing device of a storage array controller of the storage array, whether the section corresponds to any check-pointed data set that comprises a count of a number of writes performed on a corresponding section and one or more regions of the corresponding section having overwritten data; and
performing, by the processing device, a scalable garbage collection process on the section upon determining that the section corresponds to a check-pointed data set, wherein the scalable garbage collection process is performed on one or more regions of the section having overwritten data.

2. The method of claim 1 , wherein performing the scalable garbage collection process on the section comprises: determining that an item in a first task list corresponds to the check-pointed data set.

3. The method of claim 2 , further comprising:
determining that the item in the first task list indicates that data in the check-pointed data set should be garbage collected, wherein the scalable garbage collection process is performed on the section upon the determination.

4. The method of claim 2 , further comprising:
determining that the item in the first task list indicates that data in the check-pointed data set should not be garbage collected, wherein the storage array controller is prevented from performing the scalable garbage collection process on the section upon the determination.

5. The method of claim 2 , further comprising:
determining that the item in the first task list indicates that data in the check-pointed data should be analyzed, wherein an item is added to a second task list corresponding to the data upon the determination.

6. The method of claim 2 , wherein the item in the first task list corresponds to at least one of: a write operation, a move operation, or a deduplication operation.

7. The method of claim 1 , further comprising:
scanning a region of the database;
adding an item corresponding to data of interest identified during the scan to a first list; and
check-pointing the region after completing the scan.

8. The method of claim 7 , further comprising: dynamically modifying an amount of resources allocated to scanning the region of the database based on a performance threshold.

9. The method of claim 1 , wherein the database is a log-structured database.

10. A storage system comprising:
a storage array comprising one or more storage devices; and
a storage array controller coupled to the storage array, the storage array controller to:
initiate a garbage collection process on a section of a database of the storage array;
determine whether the section corresponds to any check-pointed data set that comprises a count of a number of writes performed on a corresponding section and one or more regions of the corresponding section having overwritten data; and
perform a scalable garbage collection process on the section upon determining that the section corresponds to a check-pointed data set, wherein the scalable garbage collection process is performed on one or more regions of the section having overwritten data.

11. The storage system of claim 10 , wherein to perform the scalable garbage collection process on the section the storage array controller is to: determine that an item in a first task list corresponds to the check-pointed data set.

12. The storage system of claim 11 , the storage array controller further to:
determine that the item in the first task list indicates that data in the check-pointed data set should be garbage collected, wherein the scalable garbage collection process is performed on the section upon the determination.

13. The storage system of claim 11 , the storage array controller further to:
determine that the item in the first task list indicates that data in the check-pointed data set should not be garbage collected, wherein the storage array controller is prevented from performing the scalable garbage collection process on the section upon the determination.

14. The storage system of claim 11 , the storage array controller further to:
determine that the item in the first task list indicates that data in the check-pointed data should be analyzed, wherein an item is added to a second task list corresponding of the data upon the determination.

15. The storage system of claim 11 , wherein the item in the first task list corresponds to at least one of: a write operation, a move operation, or a deduplication operation.

16. The storage system of claim 10 , the storage array controller further to:
scan a region of the database;
add an item corresponding to data of interest identified during the scan to a first list; and
check-point the region after completing the scan.

17. The storage system of claim 16 , the storage array controller further to: dynamically modify an amount of resources allocated to scanning the region of the database based on a performance threshold.

18. A non-transitory computer-readable medium comprising instructions, which when executed, cause a processing device of a storage array controller to:
initiate a garbage collection process on a section of a database of a storage array;
determine whether the section corresponds to any check-pointed data set that comprises a count of a number of writes performed on a corresponding section and one or more regions of the corresponding section having overwritten data; and
perform, by the processing device, a scalable garbage collection process on the section upon determining that the section corresponds to a check-pointed data set, wherein the scalable garbage collection process is performed on one or more regions of the section having overwritten data.

19. The non-transitory computer-readable medium of claim 18 , wherein to perform the scalable garbage collection process on the section the processing device is to: determine that an item in a first task list corresponds to the check-pointed data set.

20. The non-transitory computer-readable medium of claim 19 , the processing device further to:
determine that the item in the first task list indicates that data in the check-pointed data set should be garbage collected, wherein the scalable garbage collection process is performed on the section upon the determination.

Assignees

• Pure Storage Inc

Inventors

• Davis Brandon
• Cui Wentian
• Fay Matthew Paul

Classifications

• Y02D10/00

  Energy efficient computing, e.g. low power processors, power management or thermal management · CPC title

• G06F2212/1044

  Space efficiency improvement · CPC title

• G06F2212/152

  Virtualized environment, e.g. logically partitioned system · CPC title

• G06F2212/7205

  Cleaning, compaction, garbage collection, erase control · CPC title

• G06F2212/7208

  Multiple device management, e.g. distributing data over multiple flash devices · CPC title