Reclaiming units by searching units for a predetermined criterion and storing data from a valid subunit

• US 9,141,526 B2
• Filed: 09/14/2011
• Issued: 09/22/2015
• Est. Priority Date: 09/16/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iliadis, Ilias
• Primary Examiner(s): KIM, HONG CHONG
• Application Number:
  US13/231,996
• Publication Number:
  US 20120072683A1
• Time in Patent Office: 1,469 Days
• Field of Search: 711/103, 711/170, 711/154, 707/813
• US Class Current: 1/1
• CPC Class Codes: G06F 12/02 Addressing or allocation; Relocation program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00
• CPC Class Codes: G06F 12/023 Free address space management
• 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 12/0269 Incremental or concurrent garbage collection, e.g. in real-time systems G06F12/0261 takes precedence
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control

Abstract

A method and apparatus for managing write operations in memory. The method includes a memory including units, each of the units including subunits. Data updates are written “out-of-place”, in that new data does not overwrite the memory locations (subunits) where the data is currently stored. The at least one subunit containing the outdated data is marked as invalid. As a result, a subunit can contain up to date data in a valid subunit next to invalid subunits. For reclaiming units for erasure, it is searched amongst the units to identify a unit or units that match a predetermined criterion. The data of valid subunits of such identified unit is rewritten to another unit or units.

Claims

1. A method for managing a computerized memory for storing data, the memory comprising units, each of the units comprising subunits, the method comprising:

searching amongst the units to identify a unit that matches a predetermined criterion;

responsive to identifying the unit that matches the predetermined criterion thereby forming an identified unit, stopping the search and rewriting data of valid subunits of the identified unit into at least one other unit, wherein the predetermined criterion comprises a number of valid subunits of the unit, a number of invalid subunits of the unit, a number of free subunits in the unit, an age of the unit, a time of a most recent write activity to the unit, a time of an earliest write activity to the unit, and a frequency of write activities to the unit; and

erasing the identified unit hereby making the identified unit available for reuse.

2. The method of claim 1, wherein the searching is stopped after an n^th unit matching the predetermined criterion is identified, and wherein rewriting data comprises rewriting at least data of valid subunits of the n^th identified unit into the at least one other unit, wherein 1≦

n<

N, N being a maximum number of units to be searched.

3. The method of claim 1, wherein the searching includes searching amongst the units to identify a unit that contains the number of valid subunits below a threshold.

4. The method of claim 3, wherein the threshold is defined subject to a number of subunits per unit and to a ratio between the number of valid subunits and the total number of subunits in the memory.

5. The method of claim 3, wherein the threshold is a threshold adaptive to the number of valid subunits of previously identified units.

6. The method of claim 4, wherein the threshold is a threshold adaptive to the number of valid subunits of previously identified units.

7. The method of claim 3, wherein the unit with the lowest number of valid subunits is identified amongst all the units, and wherein the threshold is set to this lowest number.

8. The method of claim 5, wherein counters for the numbers of valid subunits are maintained, and wherein the counters are adapted each time a unit with the respective number of valid subunits is identified.

9. The method of claim 7, wherein counters for the numbers of valid subunits are maintained, and wherein the counters are adapted each time a unit with the respective number of valid subunits is identified.

10. The method of claim 1, wherein the searching is carried out sequentially amongst units ordered according to an age index.

11. The method of claim 1, wherein the searching is carried out sequentially amongst a sequence of units, starting from a unit randomly chosen in the sequence.

12. The method of claim 1, wherein the searching is carried out according to a specified unit sequence.

13. The method of claim 1, wherein the memory is a non-volatile solid state memory device or is a memory of a log-structured file system.

14. The method of claim 1, wherein the memory is a flash memory device, and wherein the units are blocks and the subunits are pages of the flash memory device.

15. A computer program product comprising a non-transitory computer readable storage medium having a computer readable program stored therein, wherein the computer readable program, when executed on a computer, causes the computer to:

search amongst units comprised within a memory to identify a unit that matches a predetermined criterion;

responsive to identifying the unit that matches the predetermined criterion thereby forming an identified unit, stopping the search and rewriting data of valid subunits of the identified unit to subunits of at least one other unit, wherein the predetermined criterion comprises a number of valid subunits of the unit, a number of invalid subunits of the unit, a number of free subunits in the unit, arg age of the unit, a time of a most recent write activity to the unit, a time of an earliest write activity to the unit, and a frequency of write activities to the unit; and

erase the identified unit thereby making the identified unit available for reuse.

16. A storage device, comprising:

a memory comprising units, each of the units comprising subunits, a subunit containing either up to date data being a valid subunit or outdated data being an invalid subunit; and

a memory controller configured to;

search amongst the units to identify a unit that matches a predetermined criterion;

responsive to identifying the unit that matches the predetermined criterion thereby forming an identified unit, stop the search;

rewrite data of valid subunits of the identified unit into subunits of at least one other unit, wherein the predetermined criterion comprises a number of valid subunits of the unit, a number of invalid subunits of the unit, a number of free subunits in the unit, an age of the unit, a time of a most recent write activity to the unit, a time of an earliest write activity to the unit, and a frequency of write activities to the unit; and

erase the identified unit thereby making the identified unit available for reuse.

17. The storage device as in claim 16, wherein the memory is a flash based solid state memory with a block/page memory space structure.

18. The storage device as in claim 16, wherein the memory is a non-volatile solid state memory device or is a memory of a log-structured file system.