Garbage collection techniques for a data storage system

• US 9,740,609 B1
• Filed: 02/19/2016
• Issued: 08/22/2017
• Est. Priority Date: 02/19/2016
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Ahmed, Razik S., Fisher, Timothy J., Fry, Aaron D., Ioannou, Nikolas, Ma, Jason, Orr, Matthew R., Pletka, Roman A., Simmons, Lincoln T., Tomic, Sasa
• Primary Examiner(s): Elmore, Reba I
• Application Number:
  US15/047,942
• Publication Number:
  US 20170242789A1
• Time in Patent Office: 550 Days
• Field of Search: 711103, 711154, 711159, 711165, 707649, 707686, 707787, 707813, 707820, 710 34, 710 43, 710 74, 712225, 712228
• CPC Class Codes: G06F 12/0238 Memory management in non-volatile memory, e.g. resistive RAM or ferroelectric memory
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0628 making use of a particular technique
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays

Abstract

A technique for garbage collection in a data storage system includes determining a dirty physical byte count for each of a plurality of candidate garbage collection units. The dirty physical byte count provides a total amount of dirty bytes. At least one of a dirty physical codeword container count and a dirty physical page count is determined for each of the candidate garbage collection units. The dirty physical codeword container count provides an amount of physical codeword containers that are completely dirty and the dirty physical page count provides an amount of physical pages that are completely dirty. A garbage collection unit, included in the candidate garbage collection units, is selected for garbage collection based on the dirty physical byte count and at least one of the dirty physical codeword container count and the dirty physical page count.

Claims

1. A method of garbage collection in a data storage system, comprising:

determining, by a garbage collector, a dirty physical byte count for each of a plurality of candidate garbage collection units, wherein the dirty physical byte count provides a total amount of dirty bytes;

determining, by the garbage collector, at least one of a dirty physical codeword container count and a dirty physical page count for each of the candidate garbage collection units, wherein the dirty physical codeword container count provides an amount of physical codeword containers that are completely dirty and the dirty physical page count provides an amount of physical pages that are completely dirty; and

selecting, by the garbage collector, a garbage collection unit, included in the candidate garbage collection units, for garbage collection based on the dirty physical byte count and at least one of the dirty physical codeword container count and the dirty physical page count.

2. The method of claim 1, further comprising:

performing garbage collection on the selected garbage collection unit.

3. The method of claim 1, further comprising:

in response to the dirty physical byte count for multiple of the candidate garbage collection units being the same, selecting the garbage collection unit for garbage collection to maximize read efficiency.

4. The method of claim 1, further comprising:

in response to the dirty physical codeword container count for multiple of the candidate garbage collection units being the same, selecting the garbage collection unit for garbage collection to minimize write amplification.

5. The method of claim 1, further comprising:

selecting the garbage collection unit for garbage collection based only on the dirty physical byte count and the dirty physical page count.

6. The method of claim 1, further comprising:

selecting the garbage collection unit for garbage collection based on the dirty physical byte count, the dirty physical codeword count, and the dirty physical page count.

7. The method of claim 1, further comprising:

determining current working conditions for the data storage system;

implementing a utility function that is a function of the dirty physical byte count, the dirty physical codeword container count, and the current working conditions; and

selecting the garbage collection unit, included in the candidate garbage collection units, for garbage collection based on the utility function.

8. The method of claim 7, wherein the utility function favors higher read efficiency when a read rate is above a threshold.

9. The method of claim 7, wherein the utility function favors lower write amplification when a write rate is above another threshold.

10. A data storage system, comprising:

a flash controller memory; and

a flash controller coupled to the flash controller memory, wherein the flash controller is configured to;

determine a dirty physical byte count for each of a plurality of candidate garbage collection units, wherein the dirty physical byte count provides a total amount of dirty bytes;

determine at least one of a dirty physical codeword container count and a dirty physical page count for each of the candidate garbage collection units, wherein the dirty physical codeword container count provides an amount of physical codeword containers that are completely dirty and the dirty physical page count provides an amount of physical pages that are completely dirty; and

select a garbage collection unit, included in the candidate garbage collection units, for garbage collection based on the dirty physical byte count and at least one of the dirty physical codeword container count and the dirty physical page count.

11. The data storage system of claim 10, wherein the flash controller is further configured to:

perform garbage collection on the selected garbage collection unit.

12. The data storage system of claim 10, wherein the flash controller is further configured to:

in response to the dirty physical byte count for multiple of the candidate garbage collection units being the same, select the garbage collection unit for garbage collection to maximize read efficiency.

13. The data storage system of claim 10, wherein the flash controller is further configured to:

in response to the dirty physical codeword container count for multiple of the candidate garbage collection units being the same, select the garbage collection unit for garbage collection to minimize write amplification.

14. The data storage system of claim 10, wherein the flash controller is further configured to:

determine current working conditions for the data storage system;

implement a utility function that is a function of the dirty physical byte count, the dirty physical codeword container count, and the current working conditions; and

select the garbage collection unit, included in the candidate garbage collection units, for garbage collection based on the utility function.

15. The data storage system of claim 14, wherein the utility function favors higher read efficiency when a read rate is above a threshold.

16. The data storage system of claim 14, wherein the utility function favors lower write amplification when a write rate is above another threshold.

17. A computer program product, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a data storage system, to cause the data storage system to:

determine a dirty physical byte count for each of a plurality of candidate garbage collection units, wherein the dirty physical byte count provides a total amount of dirty bytes;

determine at least one of a dirty physical codeword container count and a dirty physical page count for each of the candidate garbage collection units, wherein the dirty physical codeword container count provides an amount of physical codeword containers that are completely dirty and the dirty physical page count provides an amount of physical pages that are completely dirty; and

select a garbage collection unit, included in the candidate garbage collection units, for garbage collection based on the dirty physical byte count and at least one of the dirty physical codeword container count and the dirty physical page count.

18. The program product of claim 17, wherein the program instructions further cause the data storage system to:

perform garbage collection on the selected garbage collection unit.

19. The program product of claim 17, wherein the program instructions further cause the data storage system to:

in response to the dirty physical byte count for multiple of the candidate garbage collection units being the same, select the garbage collection unit for garbage collection to maximize read efficiency.

20. The program product of claim 17, wherein the program instructions further cause the data storage system to:

in response to the dirty physical codeword container count for multiple of the candidate garbage collection units being the same, select the garbage collection unit for garbage collection to minimize write amplification.