Method and system for rebalancing data stored in flash memory devices

• US 9,442,670 B2
• Filed: 08/27/2014
• Issued: 09/13/2016
• Est. Priority Date: 09/03/2013
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Kruger, Warren Fritz
• Primary Examiner(s): Gu, Shawn X
• Application Number:
  US14/470,596
• Publication Number:
  US 20150067245A1
• Time in Patent Office: 748 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1048 using arrangements adapted for a specific error detection or correction feature
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7202 Allocation control and policies
• CPC Class Codes: G06F 2212/7204 Capacity control, e.g. partitioning, end-of-life degradation
• CPC Class Codes: G06F 2212/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0634 by changing the state or mode of one or more devices
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0653 Monitoring storage devices or systems
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G11C 16/349 Arrangements for evaluating degradation, retention or wearout, e.g. by counting erase cycles
• CPC Class Codes: G11C 29/822 for read only memories

Abstract

The embodiments described herein include systems, methods and/or devices that may enhance the endurance of a storage system including a storage medium. The method includes: dividing a plurality of flash memory devices into logical chunks each logical chunk including one or more flash memory blocks; assigning a weight to each of the flash memory devices for a distribution algorithm, where the weight is based on at least a number of available logical chunks; and storing data in the logical chunks in accordance with the distribution algorithm. The method includes detecting a trigger condition for a respective flash memory device. In response to detecting the trigger condition, the method includes: decreasing the weight of the respective flash memory device; updating the distribution algorithm to reflect the decreased weight of the respective flash memory device; and rebalancing data stored in the plurality of flash memory devices in accordance with the updated distribution algorithm.

Claims

1. A method of managing a storage system that comprises a storage controller and a plurality of flash memory devices, each with a plurality of flash memory blocks, the method comprising:

at the storage controller;

assigning a weight to each of the plurality of flash memory devices for a distribution algorithm, wherein each of the plurality of flash memory devices has a plurality of logical chunks, each logical chunk including one or more flash memory blocks, and wherein the weight is based on at least a number of available logical chunks for the respective flash memory device, the available logical chunks for the respective flash memory device including logical chunks that already store data and logical chunks able to store new data;

storing data in the plurality of logical chunks of the plurality of flash memory devices in accordance with the distribution algorithm;

detecting a predefined trigger condition with respect to a respective flash memory device of the plurality of flash memory devices; and

in response to detecting the predefined trigger condition;

decreasing the weight corresponding to the respective flash memory device, the decreased weight corresponding to a decreased number of the available logical chunks for the respective flash memory device;

updating the distribution algorithm to reflect the decreased weight of the respective flash memory device; and

rebalancing data stored in the plurality of flash memory devices in accordance with the updated distribution algorithm.

2. The method of claim 1, wherein the rebalancing includes migrating at least one logical chunk from the respective flash memory device to a second flash memory device different from the respective flash memory device.

3. The method of claim 2, wherein the second flash memory device is located in a different failure domain than the respective flash memory device.

4. The method of claim 1, wherein detecting the predefined trigger condition comprises determining that at least a threshold number of blocks of the respective flash memory device have failed, wherein each flash memory block is the minimum size erasable unit of a respective flash memory device in the plurality of flash memory devices.

5. The method of claim 1, wherein the storage controller detects the predefined trigger condition after directing a memory access request to the respective flash memory device.

6. The method of claim 1, further comprising:

in response to detecting the predefined trigger condition, querying the respective flash memory device to determine whether the size of the respective flash memory device is smaller than a previous size of the respective flash memory device; and

wherein the decreasing, updating, and rebalancing are performed in accordance with a determination that the query indicates that the size of the respective flash memory device is smaller than the previous size of the respective flash memory device.

7. The method of claim 1, wherein the predefined trigger condition indicates that a counter of failed flash memory blocks for the respective flash memory device exceeds an integer multiple of a threshold number, the threshold number comprising the number of flash memory blocks included in a logical chunk or an integer multiple of the number of flash memory blocks included in a logical chunk.

8. The method of claim 1, wherein a size of a plurality of logical chunks predetermined by software.

9. The method of claim 1, wherein a size of a plurality of logical chunks is determined based on a protocol used by the storage system.

10. The method of claim 1, further comprising:

in response to detecting the predefined trigger condition with respect to the respective flash memory device, re-encoding data in at least one logical chunk of the respective flash memory device with a higher level of error correction protection than a prior encoding of the data in the at least one logical chunk of the respective flash memory device.

11. The method of claim 1, further comprising:

arranging the plurality of logical chunks into a plurality of redundancy sets, each redundancy set comprising one or more logical chunks and storing redundant data sufficient to enable recovery of data stored in at least one of the one or more logical chunks.

12. The method of claim 11, further comprising:

associating one or more logical chunks comprising a respective redundancy set with the respective redundancy set in an indirection table.

13. A storage controller, comprising:

one or more processors;

a host interface configured to couple the storage controller to a host;

a storage medium interface configured to couple the storage controller to a storage medium including a plurality of flash memory devices, each with a plurality of flash memory blocks;

a storage controller memory storing instructions, which, when executed by the one or more processors, causes the storage controller to perform operations comprising;

assigning a weight to each of the plurality of flash memory devices for a distribution algorithm, wherein each of the plurality of flash memory devices has a plurality of logical chunks, each logical chunk including one or more flash memory blocks, and wherein the weight is based on at least a number of available logical chunks for the respective flash memory device, the available logical chunks for the respective flash memory device including logical chunks that already store data and logical chunks able to store new data;

storing data in the plurality of logical chunks of the plurality of flash memory devices in accordance with the distribution algorithm;

detecting a predefined trigger condition with respect to a respective flash memory device of the plurality of flash memory devices; and

in response to detecting the predefined trigger condition;

decreasing the weight corresponding to the respective flash memory device, the decreased weight corresponding to a decreased number of the available logical chunks for the respective flash memory device;

updating the distribution algorithm to reflect the decreased weight of the respective flash memory device; and

rebalancing data stored in the plurality of flash memory devices in accordance with the updated distribution algorithm.

14. The storage controller of claim 13, wherein the rebalancing includes migrating at least one logical chunk from the respective flash memory device to a second flash memory device different from the respective flash memory device.

15. The storage controller of claim 14, wherein the second flash memory device is located in a different failure domain than the respective flash memory device.

16. The storage controller of claim 13, wherein the instructions cause the storage controller to perform further operations comprising:

in response to detecting the predefined trigger condition with respect to the respective flash memory device, re-encoding data in at least one logical chunk of the respective flash memory device with a higher level of error correction protection than a prior encoding of the data in the at least one logical chunk of the respective flash memory device.

17. The storage controller of claim 13, wherein the instructions cause the storage controller to perform further operations comprising:

arranging the plurality of logical chunks into a plurality of redundancy sets, each redundancy set comprising one or more logical chunks and storing redundant data sufficient to enable recovery of data stored in at least one of the one or more logical chunks.

18. The storage controller of claim 17, wherein the instructions cause the storage controller to perform further operations comprising:

associating one or more logical chunks comprising a respective redundancy set with the respective redundancy set in an indirection table.

19. A non-transitory computer readable storage medium, storing one or more programs for execution by one or more processors of a storage controller coupled to a storage medium including a plurality of flash memory devices, wherein each flash memory device includes a plurality of flash memory blocks, the one or more programs including instructions that when executed by the one or more processors cause the storage controller to:

assign a weight to each of the plurality of flash memory devices for a distribution algorithm, wherein each of the plurality of flash memory devices has a plurality of logical chunks, each logical chunk including one or more flash memory blocks, and wherein the weight is based on at least a number of available logical chunks for the respective flash memory device, the available logical chunks for the respective flash memory device including logical chunks that already store data and logical chunks able to store new data;

store data in the plurality of logical chunks of the plurality of flash memory devices in accordance with the distribution algorithm;

detect a predefined trigger condition with respect to a respective flash memory device of the plurality of flash memory devices; and

in response to detecting the predefined trigger condition;

decrease the weight corresponding to the respective flash memory device, the decreased weight corresponding to a decreased number of the available logical chunks for the respective flash memory device;

update the distribution algorithm to reflect the decreased weight of the respective flash memory device; and

rebalance data stored in the plurality of flash memory devices in accordance with the updated distribution algorithm.

20. The non-transitory computer readable storage medium of claim 19, wherein the rebalancing includes migrating at least one logical chunk from the respective flash memory device to a second flash memory device different from the respective flash memory device.

21. The non-transitory computer readable storage medium of claim 20, wherein the second flash memory device is located in a different failure domain than the respective flash memory device.

22. The non-transitory computer readable storage medium of claim 19, wherein the one or more programs further include instructions that when executed by the one or more processors cause the storage controller to:

in response to detecting the predefined trigger condition with respect to the respective flash memory device, re-encode data in at least one logical chunk of the respective flash memory device with a higher level of error correction protection than a prior encoding of the data in the at least one logical chunk of the respective flash memory device.

23. The non-transitory computer readable storage medium of claim 19, wherein the one or more programs further include instructions that when executed by the one or more processors cause the storage controller to:

arrange the plurality of logical chunks into a plurality of redundancy sets, each redundancy set comprising one or more logical chunks and storing redundant data sufficient to enable recovery of data stored in at least one of the one or more logical chunks.

24. The non-transitory computer readable storage medium of claim 23, wherein the one or more programs further include instructions that when executed by the one or more processors cause the storage controller to:

associate one or more logical chunks comprising a respective redundancy set with the respective redundancy set in an indirection table.