APPARATUS, SYSTEM, AND METHOD FOR STORAGE SPACE RECOVERY AFTER REACHING A READ COUNT LIMIT

• US 20090125671A1
• Filed: 11/18/2008
• Published: 05/14/2009
• Est. Priority Date: 12/06/2006
• Status: Active Grant

• Current Assignee: Unification Technologies LLC (Acacia Research Corporation)
• Original Assignee: Fusion-IO Incorporated (Western Digital Corporation)
• Inventors: Walker, John, Uphoff, Stephan, Flynn, David, Thatcher, Jonathan, Zappe, Michael, Aune, Joshua, Lagerstedt, Bert, Strasser, John, Vigor, Kevin
• Granted Patent: US 8,074,011 B2
• Time in Patent Office: Days
• US Class Current: 711/103
• CPC Class Codes: G06F 11/1008 in individual solid state devices G06F11/1004 takes precedence
• CPC Class Codes: G06F 11/108 Parity data distribution in semiconductor storages, e.g. in SSD
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G06F 2212/2022 Flash memory
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0601 Interfaces specially adapted for storage systems
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores
• CPC Class Codes: H04L 12/4625 Single bridge functionality, e.g. connection of two networks over a single bridge
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]
• CPC Class Codes: H05K 7/1444 Complex or three-dimensional-arrangements; Stepped or dual mother boards

Abstract

An apparatus, system, and method are disclosed for storage space recovery after reaching a read count limit. A read module reads data in a storage division of solid-state storage. A read counter module then increments a read counter corresponding to the storage division. A read counter limit module determines if the read count exceeds a maximum read threshold, and if so, a storage division selection module selects the corresponding storage division for recovery. A data recovery module reads valid data packets from the selected storage division, stores the valid data packets in another storage division of the solid-state storage, and updates a logical index with a new physical address of the valid data.

Claims

1. An apparatus for storage recovery, the apparatus comprising:

a read module that reads at least a portion of a data packet stored in a first storage division, the first storage division comprising a portion of solid-state storage in a solid-state storage device;

a read counter module that increments a read counter in response to the read module reading data stored in the first storage division, the read counter corresponding to the first storage division, wherein the solid-state storage device comprises a plurality of storage divisions and each storage division comprises a separate read counter;

a read counter limit module that determines if the read counter corresponding to the first storage division has reached a maximum read threshold;

a storage division selection module that selects the first storage division for recovery in response to a read counter reaching the maximum read threshold, the read counter corresponding to the first storage division; and

a data recovery module that, in response to the storage division selection module selecting the first storage division for recovery, reads valid data packets from the first storage division, stores the valid data packets in a second storage division in the solid-state storage device, and updates a logical index with a new physical address of the valid data, the logical index comprising a mapping of physical addresses of data packets stored in the solid-state storage to logical identifiers corresponding to the data packets.

2. The apparatus of claim 1, further comprising:

a read counter preliminary limit module that determines if the read counter corresponding to the first storage division has reached a preliminary read threshold;

a storage division read module that reads at least a portion of the data locations within the first storage division in response to the read counter preliminary limit module determining that the read counter corresponding to the first storage division has reached the preliminary read threshold, wherein the storage division read module reads the data locations within the storage division to determine if errors exist in data stored in the storage division;

a storage division error module that determines if errors identified by the storage division read module have reached an error threshold; and

wherein the storage division selection module further selects the first storage division for recovery in response to the storage division error module determining that the number of errors identified by the storage division read module has reached the error threshold.

3. The apparatus of claim 2, wherein in response to the read counter preliminary limit module determining that the read counter corresponding to the first storage division has reached the preliminary read threshold, the storage division error module further increases the preliminary read threshold by a predetermined amount.

4. The apparatus of claim 1, wherein in response to the read counter limit module determining that the read counter corresponding to the first storage division has reached a maximum read threshold, the data recovery module further resets the read counter corresponding to the first storage division.

5. The apparatus of claim 1, further comprising a threshold adjustment module that adjusts at least the maximum read threshold.

6. The apparatus of claim 5, wherein the threshold adjustment module adjusts at least the maximum read threshold based on one or more of amount of time that the solid-state storage device is in operation, number of retired storage divisions, number of retired logical storage divisions wherein a logical storage division comprises a group of storage divisions, number of erase cycles, number of program operations, read count, operating temperature, and an environmental condition.

7. The apparatus of claim 5, wherein the threshold adjustment module adjusts at least the maximum read threshold based on a number of times the storage division selection module selected a storage division for recovery as a result of a number of errors found in one or more of a storage division, a chip, a group of chips, a die, a group of die, and a logical storage division wherein the logical storage division comprises a group of storage divisions.

8. The apparatus of claim 5, wherein the threshold adjustment module adjusts at least the maximum read threshold based on one or more of statistical data, parameters, heuristics, rules, and/or algorithms related to solid-state storage life expectancy and curve fitting data.

9. The apparatus of claim 5, wherein the threshold adjustment module adjusts at least the maximum read threshold based on information from a management system, the information comprising information derived from one or more of test data related to solid-state storage, operational data collected from solid-state storage in use, and data from a solid-state storage supplier.

10. The apparatus of claim 5, wherein the threshold adjustment module adjusts at least the maximum read threshold based on a confidence factor, the confidence factor comprising a probability that data transmitted from the solid-state storage as a result of a read request will be error free.

11. The apparatus of claim 5, wherein the threshold adjustment module adjusts at least the maximum read threshold based on one or more of data resulting from testing of the solid-state storage comprising the storage division, manufacturer representative test data, and data dependent upon configuration of the solid-state storage.

12. The apparatus of claim 1, further comprising an ECC module wherein the storage division selection module selects the first storage division for recovery in response to the ECC module reading one or more ECC blocks within the first storage block and determining that the one or more ECC blocks comprise a number of errors that exceeds one or more correction thresholds.

13. The apparatus of claim 12, wherein the ECC module determines that the one or more ECC blocks exceeds the correction thresholds by one or more of determining a mean number of errors, determining a median number of errors, a distribution of errors, determining that at least one ECC block exceeds a correction threshold, and determining that one or more ECC blocks exceeds a first correction threshold and a total number of errors of the one or more ECC blocks exceeds a second correction threshold.

14. The apparatus of claim 1, further comprising a sequential storage module that sequentially writes data packets in a storage division of the solid-state storage device, wherein the data packets are stored sequentially on the solid-state storage device in an order that the data packets are received from one or more clients and from a storage division marked for recovery such that the sequentially stored data packets are stored contiguously within a storage division and comprise the data packets received from the one or more clients interspersed with the data packets received from a storage division marked for recovery.

15. The apparatus of claim 1, further comprising a storage division recovery determination module that determines if the first storage division is in a condition to be available for writing data packets in response to the data recovery module completing copying valid data from the first storage division.

16. The apparatus of claim 1, further comprising a storage division recovery module that marks the first storage division available for writing data packets in response to the data recovery module storing the valid data packets in a second storage division.

17. The apparatus of claim 16, wherein a storage division comprises an erase block and further comprising an erase module that erases an erase block selected for recovery prior to the storage division recovery module marking the erase block available for writing data packets, wherein the erase module erases the erase block selected for recovery in response to the data recovery module copying valid data packets from the selected erase block.

18. The apparatus of claim 16, further comprising a garbage marking module that identifies a data packet in a storage division as invalid in response to an operation indicating that the data packet is no longer valid.

19. The apparatus of claim 18, wherein the data packet in the storage division is a first data packet and an operation indicating that the first data packet is no longer valid comprises writing a second data packet to the solid-state storage device wherein the second data packet indicates that the first data packet is invalid.

20. The apparatus of claim 18, wherein an operation indicating that the data packet is no longer valid comprises one of a delete operation and a read-modify-write operation, the delete operation signifying that the data packet is to be deleted and the read-modify-write operation comprising reading the data packet, modifying the data packet, and writing the modified data packet to another location in the solid-state storage device.

21. The apparatus of claim 18, wherein identifying a data packet as invalid comprises modifying an entry in the logical index to indicate that the data packet is invalid.

22. The apparatus of claim 1, wherein one or more of the storage division selection module, the data recovery module, and the storage division recovery determination module operate autonomously from the read module, the read counter module, and the read counter limit module.

23. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division with a low amount of wear.

24. The apparatus of claim 23, wherein identifying a storage division with a low amount of wear comprises identifying a storage division with one or more of a low number of erase cycles, a low read count, and a low bit error rate.

25. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division with a high amount of wear.

26. The apparatus of claim 25, wherein identifying a storage division with a high amount of wear comprises identifying a storage division with one or more of a high number of erase cycles, a high read count, a high bit error rate, a high bit error rate with a low read count, and a non-recoverable error-correcting code (“

ECC”

) block.

27. The apparatus of claim 25, wherein the storage division recovery module marks the storage division selected for recovery as unavailable for storing data.

28. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division with a high amount of invalid data.

29. The apparatus of claim 1, wherein the storage division selection module selects a storage division for recovery by identifying a storage division using a combination of two or more of a program count, erase cycle count, read count, bit error rate, amount of invalid data, erase cycles, and a non-recoverable ECC block.

30. The apparatus of claim 1, wherein the solid-state storage is arranged in an array of storage elements and a storage division comprises a virtual storage division that includes a storage division within each storage element in a row of storage elements accessed together.

31. A system for storage recovery, the system comprising:

a solid-state storage device comprising solid-state storage, the solid-state storage comprising one or more storage divisions, each storage division comprising a portion of the solid-state storage

a solid-state storage controller comprising

a read module that reads at least a portion of a data packet stored in a first storage division;

a read counter module that increments a read counter in response to the read module reading data stored in the first storage division, the read counter corresponding to the first storage division, wherein each storage division comprises a separate read counter;

a read counter limit module that determines if the read counter corresponding to the first storage division has reached a maximum read threshold;

a storage division selection module that selects the first storage division for recovery in response to a read counter reaching the maximum read threshold, the read counter corresponding to the first storage division; and

a data recovery module that, in response to the storage division selection module selecting the first storage division for recovery, reads valid data packets from the first storage division, stores the valid data packets in a second storage division in the solid-state storage device, and updates a logical index with a new physical address of the valid data, the logical index comprising a mapping of physical addresses of data packets stored in the solid-state storage to logical identifiers corresponding to the data packets.

32. A computer program product comprising a computer readable medium having computer usable program code executable to perform operations for storage recovery, the operations of the computer program product comprising:

reading at least a portion of a data packet stored in a first storage division, the first storage division comprising a portion of solid-state storage in a solid-state storage device;

incrementing a read counter in response to reading data stored in the first storage division, the read counter corresponding to the first storage division, wherein the solid-state storage device comprises a plurality of storage divisions and each storage division comprises a separate read counter;

determining if the read counter corresponding to the first storage division has reached a maximum read threshold;

selecting the first storage division for recovery in response to a read counter reaching the maximum read threshold, the read counter corresponding to the first storage division; and

in response to selecting the first storage division for recovery, reading valid data packets from the first storage division, storing the valid data packets in a second storage division in the solid-state storage device, and updating a logical index with a new physical address of the valid data, the logical index comprising a mapping of physical addresses of data packets stored in the solid-state storage to logical identifiers corresponding to the data packets.

33. The computer program product of claim 32, further comprising

determining if the read counter corresponding to the storage division has reached a preliminary read threshold;

reading at least a portion of the data locations within the first storage division in response to determining that the read counter corresponding to the first storage division has reached the preliminary read threshold, wherein the computer program product reads the data locations within the storage division to determine if errors exist in data stored in the storage division;

determining if a number of identified errors has reached an error threshold; and

selecting the first storage division for recovery in response to determining that the number of identified errors has reached the error threshold.

34. The computer program product of claim 32, further comprising sequentially writing data packets in a storage division of the solid-state storage device, wherein the data packets are stored sequentially on the solid-state storage device in an order that the data packets are received from one or more clients and from a storage division marked for recovery such that the sequentially stored data packets are stored contiguously and comprise the data packets received from the one or more clients interspersed with the data packets received from a storage division marked for recovery.

35. The computer program product of claim 32, further comprising marking the first storage division available for writing data packets in response to storing the valid data packets on a second storage division.

36. The computer program product of claim 35, wherein a storage division comprises an erase block and further comprising erasing an erase block selected for recovery prior to marking the erase block available for writing data packets, wherein the erase block is erased in response to copying valid data packets from the selected erase block.