SCALABLE GARBAGE COLLECTION

• US 20200133841A1
• Filed: 10/25/2018
• Published: 04/30/2020
• Est. Priority Date: 10/25/2018
• Status: Active Application

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Davis, Brandon, Cui, Wentian, Fay, Matthew Paul
• Granted Patent: US 10,846,216 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/1048 Scalability
• CPC Class Codes: G06F 2212/152 Virtualized environment, e.g. logically partitioned system
• CPC Class Codes: G06F 2212/163 Server or database system
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

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.

Claims

1. A method, comprising:

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;

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;

if the section does not correspond to any check-pointed data set;

performing the garbage collection process on the section;

if the section does correspond to a check-pointed data set;

performing, by the processing device, a scalable garbage collection process on the section.

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; and

performing the garbage collection process on the section.

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; and

preventing the storage array controller from performing the garbage collection process on the section.

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; and

adding an item to a second task list corresponding to the data.

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;

identifying data of interest in the region;

adding an item corresponding to the data of interest 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;

receive an indication to perform 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;

if the section does not correspond to any check-pointed data set;

perform the garbage collection process on the section;

if the section does correspond to a check-pointed data set;

perform a scalable garbage collection process on the section.

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; and

perform the garbage collection process on the section.

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; and

prevent the storage array controller from performing the garbage collection process on the section.

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; and

add an item to a second task list corresponding to the data.

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;

identify data of interest in the region;

add an item corresponding to the data of interest 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:

receive an indication to perform 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;

if the section does not correspond to any check-pointed data set;

perform the garbage collection process on the section;

if the section does correspond to a check-pointed data set;

perform, by the processing device, a scalable garbage collection process on the section.

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; and

perform the garbage collection process on the section.