Using a PID controller to opportunistically compress more data during garbage collection

• US 10,678,436 B1
• Filed: 05/29/2018
• Issued: 06/09/2020
• Est. Priority Date: 05/29/2018
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Jiang, Yanwei, Karumbunathan, Aswin, Neelakantam, Naveen, Vijayasankar, Kiron, Feng, Bo, Engel, Joern
• Primary Examiner(s): Rones, Charles
• Assistant Examiner(s): Li, Hewy H
• Application Number:
  US15/991,976
• Time in Patent Office: 742 Days
• 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/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0661 Format or protocol conversion arrangements
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: H03M 7/30 Compression speech analysis-synthesis for redundancy reduction G10L19/00; for image communication H04N; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
• CPC Class Codes: H03M 7/607 Selection between different types of compressors

Abstract

A storage system performs garbage collection with data compression. A storage controller in the storage system determines a garbage collection directive by evaluating the amount of reclaimable space relative to a target amount of reclaimable space. Garbage collection is performed using data compression tunable to compression aggressiveness according to the garbage collection directive.

Claims

1. A storage system, comprising:

a storage array;

a storage controller, operatively coupled with the storage array;

the storage controller configured to;

determine a garbage collection directive by evaluating a present amount of reclaimable space in the storage array relative to a target amount of reclaimable space in the storage array; and

perform garbage collection in the storage array, using data compression tuned to compression aggressiveness according to the garbage collection directive, wherein

a cost or benefit of the data compression is determined, over a range of parameter values or compression algorithms, relative to a rate of the garbage collection; and

,

the data compression performed by the storage controller is tuned to compress live data from the reclaimable space over a range of the compression aggressiveness according to the garbage collection directive, to direct the rate of the garbage collection in accordance with the cost or benefit.

2. The storage system of claim 1, wherein;

to determine the garbage collection directive, the storage controller is configured to;

determine the garbage collection directive as a process control output by adding at least a first term proportional to an error comprising the target amount of reclaimable space in the storage array, as a set point, minus the present amount of reclaimable space in the storage array, as a process variable, and a second term proportional to an integral of the error.

3. The storage system of claim 1, wherein the storage controller is tuned to select from a plurality of compression algorithms according to the garbage collection directive.

4. The storage system of claim 1, wherein the data compression used by the storage controller is tuned through a parameter within a compression algorithm according to the garbage collection directive.

5. The storage system of claim 1, wherein the storage controller is tuned to select proportions of data from the reclaimable space for two or more levels of the compression aggressiveness according to the garbage collection directive.

6. The storage system of claim 1, wherein the storage controller is tuned to select live data for the data compression according to life expectancy of the live data.

7. The storage system of claim 1, wherein the storage controller comprises a PT controller, a PID controller having a zero coefficient for a derivative of an error term, or a PID controller having a non-zero coefficient for a derivative of the error term.

8. A method of garbage collection in a storage system, performed by the storage system, the method comprising:

determining a present amount of reclaimable space in storage memory of the storage system;

determining a garbage collection directive based on the present amount of reclaimable space in comparison to a target amount of reclaimable space, wherein the determining the garbage collection directive comprises determining the garbage collection directive as a process control output of a proportional-integral-derivative (PID) controller or proportional-integral (PI) controller that has as input an error comprising, the target amount of reclaimable space in the storage memory minus the present amount of reclaimable space; and

performing garbage collection in the storage memory, using data compression tuned to compression aggressiveness according to the garbage collection directive.

9. The method of claim 8, further comprising:

selecting from a plurality of compression algorithms according to the garbage collection directive;

for the garbage collection.

10. The method of claim 8, further comprising:

tuning a compression algorithm through a parameter according to the garbage collection directive, for the garbage collection.

11. The method of claim 8, further comprising:

selecting proportions of data from the reclaimable space for two or more levels of the compression aggressiveness according to the garbage collection directive, for the garbage collection.

12. A tangible, non-transitory, computer-readable media having instructions thereupon which, when executed by a storage controller, cause the storage controller to:

determine a present amount of reclaimable space in storage memory of a storage system;

form a garbage collection directive based on a difference between the present amount of reclaimable space and a target amount of reclaimable space in the storage memory, wherein to form the garbage collection directive, the storage controller is to determine the garbage collection directive as a process control output of a proportional-integral-derivative (PID) controller or proportional-integral (PI) controller that has as input an error comprising the target amount of reclaimable space in the storage memory, as a set point, minus the present amount of reclaimable space, as a process variable;

tune data compression aggressiveness according to the garbage collection directive; and

perform garbage collection in the storage memory, with data compression, using the tuned data compression aggressiveness.

13. The tangible;

non-transitory computer-readable media of claim 12, wherein to tune the data compression aggressiveness;

the instructions are to cause the storage controller to;

select from a plurality of compression algorithms according to the garbage collection directive, for the data compression as used in performing the garbage collection.

14. The tangible;

non-transitory computer-readable media of claim 12, wherein to tune the data compression aggressiveness, the instructions are to cause the storage controller to;

tune a compression algorithm through a parameter according to the garbage collection directive, for the data compression as used in performing the garbage collection.

15. The tangible;

non-transitory computer-readable media of claim 12, wherein to tune the data compression aggressiveness, the instructions are to cause the storage controller to;

select proportions of data from the reclaimable space for two or more levels of the compression aggressiveness according to the garbage collection directive, for the data compression as used in performing the garbage collection.

16. The tangible, non-transitory computer-readable media of claim 12, wherein the instructions are to cause the storage controller to:

determine life expectancy of live data, based on timestamps or sequence numbers; and

select the live data for the data compression according to the life expectancy of the live data.

17. The tangible, non-transitory computer-readable media of claim 12, wherein the tuned data compression aggressiveness directs a rate of the garbage collection in accordance with a determined cost or benefit of the data compression aggressiveness relative to the rate of the garbage collection.