Garbage collection for failure prediction and repartitioning

• US 8,447,918 B2
• Filed: 04/07/2010
• Issued: 05/21/2013
• Est. Priority Date: 04/08/2009
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Sprinkle, Robert S., Borchers, Albert T., Swing, Andrew T.
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US12/755,964
• Publication Number:
  US 20100262766A1
• Time in Patent Office: 1,140 Days
• Field of Search: None
• US Class Current: 711/103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G11C 2029/0409 Online test
• CPC Class Codes: G11C 29/52 Protection of memory contents; Detection of errors in memory contents
• CPC Class Codes: G11C 29/88 with partially good memories

Abstract

A method of formatting a data storage device that includes a plurality of flash memory chips includes monitoring a failure rate of memory blocks of one or more flash memory chips of a storage device that has a first usable size for user space applications, estimating a future usable size of the data storage device based on the monitored failure rate, and defining, via a host coupled to the data storage device, a second usable size of the data storage device for user space applications based on the monitored failure rate.

Claims

1. A method of formatting a data storage device, wherein the device includes a plurality of flash memory chips, the method comprising:

monitoring a failure rate of memory blocks of one or more flash memory chips of a storage device, wherein the storage device has a first usable size for user space applications;

estimating a future usable size of the data storage device based on the monitored failure rate; and

defining, via a host coupled to the data storage device, a second usable size of the data storage device for user space applications based on the monitored failure rate.

2. The method of claim 1, further comprising:

writing valid data stored on the data storage device to a location off of the data storage device;

reformatting the data storage device to have the second usable size; and

writing at least a portion of the valid data to the reformatted data storage device from the location off the data storage device back to the data storage device.

3. The method of claim 1, wherein monitoring the failure rate of the memory blocks includes monitoring the failure rate of the memory blocks as a function of a number of write-erase cycles performed on the blocks.

4. The method of claim 1, wherein monitoring the failure rate of the memory blocks includes storing information about a number of successful write-erase operations performed on each of the memory blocks.

5. The method of claim 1, further comprising:

monitoring an amount of valid data stored on the storage device,

wherein defining, via the host coupled to the data storage device, the second usable size of the data storage device for user space applications is additionally based on the amount of valid data stored on the storage device.

6. The method of claim 1, wherein estimating the future usable size of the data storage device includes fitting data about the monitored failure rate of the memory blocks to a theoretical curve that characterizes a failure probability of a block.

7. The method of claim 1, wherein:

the storage device includes a first partition that includes a first subset of the plurality of flash memory chips and a second partition that includes a second subset of the plurality of flash memory chips, and

the first subset does not include any memory chips of the second subset and wherein the second subset does not include any memory chips of the first subset,

the method further comprising;

monitoring a failure rate of memory blocks of one or more flash memory chips of the first partition, wherein the first partition has a first usable size for user space applications;

estimating a future usable size of the first partition based on the monitored failure rate; and

defining, via the host coupled to the data storage device, a second usable size of the first partition for user space applications based on the monitored failure rate.

8. The method of claim 7, wherein a usable size of the second partition remains constant while the second usable size of the first partition is defined.

9. An apparatus comprising:

a flash memory data storage device that includes a plurality of flash memory chips; and

a host operably coupled to the data storage device via an interface, the host including;

a wear monitoring engine configured to monitor a failure rate of memory blocks of one or more of the flash memory chips;

a modeling engine configured to estimate a future usable size of the data storage device based on the monitored failure rate; and

a formatting engine configured to format the data storage device to have a first usable size for user space applications; and

configured to format the data storage device to have a second usable size for user space applications based on the monitored failure rate.

10. The apparatus of claim 9, wherein the formatting engine is further configured to:

write valid data stored on the data storage device to a location off of the data storage device;

reformat the data storage device to have the second usable size; and

write at least a portion of the valid data to the reformatted data storage device from the location off of the data storage device back to the data storage device.

11. The apparatus of claim 9, wherein monitoring the failure rate of the memory blocks includes monitoring the failure rate of the memory blocks as a function of a number of write-erase cycles performed on the blocks.

12. The apparatus of claim 9, wherein the host further includes a memory configured to store information about a number of successful write-erase operations performed on each of the memory blocks.

13. The apparatus of claim 9, wherein the host further includes a configuration detection engine configured to monitor an amount of valid data stored on the storage device, and

wherein defining the second usable size of the data storage device for user space applications is additionally based on the amount of valid data stored on the storage device.

14. The apparatus of claim 13, wherein estimating the future usable size of the data storage device includes fitting data about the monitored failure rate of the memory blocks to a theoretical curve that characterizes a failure probability of a block.

15. The apparatus of claim 9, wherein the host further includes a partition engine configured to partition the data storage device into a first partition that includes a first subset of the plurality of flash memory chips and a second partition that includes a second subset of the plurality of flash memory chips, wherein the first subset does not include any memory chips of the second subset and wherein the second subset does not include any memory chips of the first subset, and

wherein the wear monitoring engine is further configured to monitor a failure rate of memory blocks of one or more flash memory chips of the first partition, wherein the first partition has a first usable size for user space applications,

wherein the modeling engine is further configured to estimate a future usable size of the first partition based on the monitored failure rate, and

wherein the formatting engine is further configured to define a second usable size of the first partition for user space applications based on the monitored failure rate.

16. The apparatus of claim 15, wherein a usable size of the second partition remains constant while the second usable size of the first partition is defined.