Adaptive over-provisioning in memory systems

• US 8,479,080 B1
• Filed: 06/24/2010
• Issued: 07/02/2013
• Est. Priority Date: 07/12/2009
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Shalvi, Ofir, Sommer, Naftali, Kasorla, Yoav
• Primary Examiner(s): TRIMMINGS, JOHN P
• Application Number:
  US12/822,207
• Time in Patent Office: 1,104 Days
• Field of Search: None
• US Class Current: 714/774
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• 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/0223 User address space allocation, e.g. contiguous or non contiguous base addressing
• 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/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: Y02D 10/00 Energy efficient computing, e.g. low power processors, power management or thermal management

Abstract

A method for data storage includes, in a memory that includes multiple memory blocks, specifying at a first time a first over-provisioning overhead, and storing data in the memory while retaining in the memory blocks memory areas, which do not hold valid data and whose aggregated size is at least commensurate with the specified first over-provisioning overhead. Portions of the data from one or more previously-programmed memory blocks containing one or more of the retained memory areas are compacted. At a second time subsequent to the first time, a second over-provisioning overhead, different from the first over-provisioning overhead, is specified, and data storage and data portion compaction is continued while complying with the second over-provisioning overhead.

Claims

1. A method for data storage, comprising:

in a memory that includes multiple memory blocks, specifying at a first time a first over-provisioning overhead, and storing data in the memory while retaining in the memory blocks memory areas, which do not hold valid data and whose aggregate size is at least commensurate in size with the specified first over-provisioning overhead;

compacting portions of the data from one or more previously-programmed memory blocks containing one or more of the retained memory areas; and

at a second time subsequent to the first time, specifying a second over-provisioning overhead that is different from the first over-provisioning overhead, and continuing to store the data and compact the data portions while complying with the second overprovisioning overhead;

wherein storing the data at the first time comprises encoding the data with an Error Correction Code (ECC) having a given redundancy level and storing the encoded data, and wherein specifying the second over-provisioning overhead comprises modifying the given redundancy level of the ECC.

2. The method according to claim 1, wherein storing the data at the first time comprises encoding the data with an Error Detection Code (EDC) having a given size and storing the encoded data, and wherein specifying the second over-provisioning overhead comprises modifying the given size of the EDC.

3. The method according to claim 1, wherein each memory block comprises multiple memory cells, wherein storing the data at the first time comprises programming the data at a given number of bits per cell, and wherein specifying the second over-provisioning overhead comprises modifying the given number of bits per cell.

4. The method according to claim 3, wherein modifying the given number of bits per cell comprises modifying a number of programming levels that are used for programming the memory cells.

5. The method according to claim 3, wherein modifying the given number of bits per cell comprises modifying a coding rate of an Error Correction Code (ECC) that is used for encoding the data.

6. The method according to claim 1, wherein storing the data at the first time comprises storing N pages in a given memory block, and wherein continuing to store the data at the second time comprises storing M pages in the given block, M≠

N.

7. The method according to claim 1, wherein specifying the first and second over-provisioning overheads comprises compressing the data and storing the compressed data at one of the first and second times, and storing the data without compression at the other of the first and second times.

8. The method according to claim 1, wherein specifying the second over-provisioning overhead comprises evaluating a predefined adaptation criterion with respect to at least some of the memory blocks, and setting the second over-provisioning overhead responsively to meeting the adaptation criterion.

9. The method according to claim 8, wherein evaluating the adaptation criterion comprises assessing a wear level of the at least some of the memory blocks.

10. The method according to claim 8, wherein evaluating the adaptation criterion comprises assessing an expected number of errors in the at least some of the memory blocks.

11. The method according to claim 8, wherein evaluating the adaptation criterion comprises assessing a target storage reliability of the data in the at least some of the memory blocks.

12. The method according to claim 8, wherein the adaptation criterion depends on a preference between programming speed and a capacity of the memory.

13. The method according to claim 8, wherein the adaptation criterion depends on a frequency at which the data in the at least some of the memory blocks changes.

14. The method according to claim 1, wherein storing the data comprises accepting the data from a host for storage in a long-term storage device, and temporarily caching the data in the memory.

15. The method according to claim 14, wherein specifying the second over-provisioning overhead comprises receiving from the host a request to free cache memory resources, and setting the second over-provisioning overhead in response to the request.

16. The method according to claim 1, wherein the data is received from a host for storage in the memory, wherein the memory has a specified user capacity that is available to the host, and wherein specifying the second over-provisioning overhead does not change the specified user capacity.

17. The method according to claim 1, wherein specifying the second over-provisioning overhead comprises accepting an indication whether a data item that is stored in the memory is also stored in an additional storage location, and setting the second over-provisioning overhead responsively to the indication.

18. The method according to claim 1, wherein the memory includes multiple memory devices each holding a subset of the memory blocks, and wherein specifying the first and second over-provisioning overheads comprise assigning one of the memory devices to serve as a spare memory device for replacing a faulty memory device, and, until the spare memory device replaces the faulty memory device, using the spare memory device to increase the first overprovisioning overhead.

19. The method according to claim 1, wherein the memory includes multiple memory portions each holding a subset of the memory blocks, and wherein specifying the first over-provisioning overhead comprises individually specifying respective values of the first overprovisioning overhead separately for the memory portions.

20. The method according to claim 19, wherein specifying the respective values of the over-provisioning overhead comprises setting a respective value of the first over-provisioning overhead for a given memory portion based on an expected endurance of the given memory portion.

21. The method according to claim 1, wherein the memory includes multiple memory devices each holding a subset of the memory blocks, wherein specifying the first over-provisioning overhead at the first time comprises assigning each memory device a respective range of logical addresses, and wherein specifying the second over-provisioning overhead at the second time comprises re-assigning the logical addresses among the memory devices in response to a failure of a given memory device.

22. The method according to claim 1, wherein the memory includes multiple memory devices that are grouped in two or more groups, wherein specifying the first overprovisioning ratio comprises individually specifying respective values of the first over-provisioning overhead for the groups, and comprising selecting, responsively to the values, one of the groups for storing an input data item, and storing the input data item in the selected group.

23. The method according to claim 1, wherein storing the data at the first time comprises storing a first portion of the data at a first storage density and a second portion of the data at a second storage density that is different from the first storage density, and wherein specifying the second over-provisioning ratio comprises, at the second time, modifying a ratio between the first and second portions of the data.

24. The method according to claim 23, wherein storing the data comprises storing frequently-changing data at the first storage density, and rarely-changing data at the second storage density.

25. The method according to claim 1, wherein compacting the portions of the data comprises selecting the previously-programmed memory blocks for compaction based on an estimated endurance of the blocks.

26. A method for data storage, comprising:

in a memory that includes multiple memory blocks, predefining a range of logical addresses for storing data in the memory;

defining a number of physical storage locations in the memory blocks, such that data storage in the number of the physical storage locations retains in the memory blocks memory areas that do not hold valid data and whose aggregated size is at least commensurate in size with an initial over-provisioning overhead;

at a first time, storing the data in the memory by mapping the logical addresses to the number of physical storage locations, while complying with the initial over-provisioning overhead, and compacting portions of the data from one or more previously-programmed memory blocks containing one or more of the retained memory areas; and

at a second time subsequent to the first time, defining a modified over-provisioning overhead that is different from the initial over-provisioning overhead, modifying the number of the physical storage locations so as to comply with the modified over-provisioning overhead, and continuing to store the data by mapping the logical addresses to the modified number of the physical storage locations and compacting the data portions;

wherein defining and modifying the number of physical storage locations comprise applying a mapping process, which maps between the logical addresses and the physical storage locations and which varies in accordance with the over-provisioning overhead.

27. The method according to claim 26, wherein applying the mapping process comprises defining a data structure for holding a mapping between the logical addresses and the physical storage locations, and modifying at least one of a size of the data structure and a variable range of data structure in accordance with the over-provisioning overhead.

28. Apparatus for data storage, comprising:

a memory, comprising multiple memory blocks; and

a processor, which is configured to specify at a first time a first over-provisioning overhead and store data in the memory while retaining in the memory blocks memory areas, which do not hold valid data and whose aggregated size is at least commensurate in size with the specified first over-provisioning overhead, to compact portions of the data from one or more previously-programmed memory blocks containing one or more of the retained memory areas, and, at a second time subsequent to the first time, to specify a second over-provisioning overhead that is different from the first over-provisioning overhead and to continue to store the data and compact the data portions while complying with the second over-provisioning overhead;

wherein the processor is configured to encode the data at the first time with an Error Correction Code (ECC) having a given redundancy level and store the encoded data, and to specify the second over-provisioning overhead by modifying the given redundancy level of the ECC.

29. The apparatus according to claim 28, wherein the processor is configured to encode the data at the first time with an Error Detection Code (EDC) having a given size and store the encoded data, and to specify the second over-provisioning overhead by modifying the given size of the EDC.

30. The apparatus according to claim 28, wherein each memory block comprises multiple memory cells, and wherein the processor is configured to program the data at the first time at a given number of bits per cell, and to specify the second over-provisioning overhead by modifying the given number of bits per cell.

31. The apparatus according to claim 30, wherein the processor is configured to modify the given number of bits per cell by modifying a number of programming levels that are used for programming the memory cells.

32. The apparatus according to claim 30, wherein the processor is configured to modify the given number of bits per cell by modifying a coding rate of an Error Correction Code (ECC) that is used for encoding the data.

33. The apparatus according to claim 28, wherein the processor is configured to store the data at the first time by storing N pages per memory block, and to continue to store the data at the second time by storing M pages per memory block, M≠

N.

34. The apparatus according to claim 28, wherein the processor is configured to specify the first and second over-provisioning overheads by compressing the data and storing the compressed data at one of the first and second times, and storing the data without compression at the other of the first and second times.

35. The apparatus according to claim 28, wherein the processor is configured to evaluate a predefined adaptation criterion with respect to at least some of the memory blocks, and to set the second over-provisioning overhead responsively to meeting the adaptation criterion.

36. The apparatus according to claim 35, wherein the processor is configured to evaluate the adaptation criterion by assessing a wear level of the at least some of the memory blocks.

37. The apparatus according to claim 35, wherein the processor is configured to evaluate the adaptation criterion by assessing an expected number of errors in the at least some of the memory blocks.

38. The apparatus according to claim 35, wherein the processor is configured to evaluate the adaptation criterion by assessing a target storage reliability of the data in the at least some of the memory blocks.

39. The apparatus according to claim 35, wherein the adaptation criterion depends on a preference between programming speed and a capacity of the memory.

40. The apparatus according to claim 35, wherein the adaptation criterion depends on a frequency at which the data in the at least some of the memory blocks changes.

41. The apparatus according to claim 28, wherein the processor is configured to accept the data from a host for storage in a long-term storage device, and to temporarily cache the data in the memory.

42. The apparatus according to claim 41, wherein the processor is configured to receive from the host a request to free cache memory resources, and to specify the second over-provisioning overhead in response to the request.

43. The apparatus according to claim 28, wherein the data is received from a host for storage in the memory, wherein the memory has a specified user capacity that is available to the host, and wherein setting of the second over-provisioning overhead does not change the specified user capacity.

44. The apparatus according to claim 28, wherein the processor is configured to accept an indication whether a data item that is stored in the memory is also stored in an additional storage location, and to set the second over-provisioning overhead responsively to the indication.

45. The apparatus according to claim 28, wherein the memory comprises multiple memory devices each holding a subset of the memory blocks, and wherein the processor is configured to assign one of the memory devices to serve as a spare memory device for replacing a faulty memory device, and, until the spare memory device replaces the faulty memory device, to use the spare memory device to increase the first over-provisioning overhead.

46. The apparatus according to claim 28, wherein the memory comprises multiple memory portions each holding a subset of the memory blocks, and wherein the processor is configured to individually specify respective values of the first over-provisioning overhead separately for the memory portions.

47. The apparatus according to claim 46, wherein the processor is configured to set a respective value of the first over-provisioning overhead for a given memory portion based on an expected endurance of the given memory portion.

48. The apparatus according to claim 28, wherein the memory comprises multiple memory devices each holding a subset of the memory blocks, and wherein the processor is configured to assign each memory device a respective range of logical addresses at the first time, and to reassign the logical addresses among the memory devices at the second time in response to a failure of a given memory device.

49. The apparatus according to claim 28, wherein the memory comprises multiple memory devices that are grouped in two or more groups, and wherein the processor is configured to individually specify respective values of the first over-provisioning overhead for the groups, to select, responsively to the values, one of the groups for storing an input data item, and to store the input data item in the selected group.

50. The apparatus according to claim 28, wherein the processor is configured to store the data at the first time by storing a first portion of the data at a first storage density and a second portion of the data at a second storage density that is different from the first storage density, and to modify a ratio between the first and second portions of the data at the second time, so as to specify the second over-provisioning ratio.

51. The apparatus according to claim 50, wherein the processor is configured to store frequently-changing data at the first storage density, and rarely-changing data at the second storage density.

52. The apparatus according to claim 28, wherein the processor is configured to select the previously-programmed memory blocks for compaction based on an estimated endurance of the blocks.

53. Apparatus for data storage, comprising:

a memory, comprising multiple memory blocks; and

a processor, which is configured to predefine a range of logical addresses for storing data in the memory, to define a number of physical storage locations in the memory blocks, such that data storage in the number of the physical storage locations retains in the memory blocks memory areas that do not hold valid data and whose aggregated size is at least commensurate in size with an initial over-provisioning overhead, to store data in the memory at a first time by mapping the logical addresses to the number of the physical storage locations, while complying with the initial overprovisioning overhead, and compacting portions of the data from one or more previously-programmed memory blocks containing one or more of the retained memory areas, and, at a second time subsequent to the first time, to define a modified over-provisioning overhead that is different from the initial over-provisioning overhead, to modify the number of the physical storage locations so as to comply with the modified over-provisioning overhead, and to continue to store the data by mapping the logical addresses to the modified number of the physical storage locations and compact the data portions;

wherein the processor is configured to apply a mapping process, which maps between the logical addresses and the physical storage locations and which varies in accordance with the over-provisioning overhead.

54. The apparatus according to claim 53, wherein the processor is configured to define a data structure for holding a mapping between the logical addresses and the physical storage locations, and to modify at least one of a size of the data structure and a variable range of the data structure in accordance with the over-provisioning overhead.