Managing Write Operations in a Computerized Memory

• US 20120072683A1
• Filed: 09/14/2011
• Published: 03/22/2012
• Est. Priority Date: 09/16/2010
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Iliadis, Ilias
• Granted Patent: US 9,141,526 B2
• Time in Patent Office: Days
• US Class Current: 711/159
• 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, wherein the memory performing data updates by writing data updates out-of-place, wherein data updates to outdated data are written to a subunit different from a subunit containing the outdated data and wherein the subunit containing the outdated data is invalid while a subunit containing up-to-date data is a valid subunit;

said method comprising;

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

stopping the search and rewriting data of valid subunits of an identified unit into at least another unit after a unit that matches the predetermined criterion is identified.

2. The method of claim 1, wherein the step of 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 at least another unit, wherein 1≦

n<

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

3. The method of claim 1, wherein the criterion involves the number of valid subunits of a unit.

4. The method of claim 2, wherein the criterion involves the number of valid subunits of a unit.

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

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

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

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

9. The method of claim 5 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.

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

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

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

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

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

15. 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.

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

17. A computer readable storage medium tangibly embodying a computer readable program code having computer readable instructions which, when implemented, cause a computer to carry out the steps of a method of claim 1.

18. 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 write data updates to a subunit different from the subunit the outdated data is contained whereby the subunit containing the outdated data is invalid;

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

stop the search after a unit that matches the predetermined criterion is identified; and

rewrite data of valid subunits of an identified unit into subunits of at least another unit.

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

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