Wear leveling in solid state devices

• US 10,019,166 B2
• Filed: 04/15/2016
• Issued: 07/10/2018
• Est. Priority Date: 10/08/2014
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Rastogi, Kanishk, Unnikrishnan, Sanoj Kizhakkekara, Mitra, Anand
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US15/130,320
• Publication Number:
  US 20160231947A1
• Time in Patent Office: 816 Days
• Field of Search: None
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 2212/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 2212/7211 Wear leveling
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0658 Controller construction arrangements
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]

Abstract

Embodiments of the present disclosure provide a memory-efficient mechanism for identifying memory blocks with a low wear count. More particularly, embodiments of the present disclosure provide a mechanism for identifying a memory block whose wear count is within the bottom p % of all wear counts associated with memory blocks in a storage system. If a memory controller always performs the garbage collection operation on a memory block whose wear count is within the bottom p % of all wear counts, then the memory controller is expected to utilize the remaining memory blocks (e.g., memory blocks whose wear count is within the upper (100-p) % of all wear counts) efficiently and level the wear count of at least the remaining memory blocks.

Claims

1. A method comprising:

maintaining, at a memory controller in a storage system comprising a plurality of memory blocks, a wear count table having a plurality of wear count elements, wherein each of the wear count elements is assigned to at least one wear count;

detecting, at the memory controller, a data removal operation performed on one of the plurality of memory blocks;

increasing, by the memory controller, a wear count associated with the one of the plurality of memory blocks from a first wear count to a second wear count;

identifying a first wear count element of the wear count table assigned to the first wear count;

identifying a second wear count element of the wear count table assigned to the second wear count; and

when the first wear count element and the second wear count element are different, decreasing a value of the first wear count element by one and increasing a value of the second wear count element by one.

2. The method of claim 1, wherein the data removal operation comprises a garbage collection operation.

3. The method of claim 1, further comprising determining a threshold wear count based on the wear count table.

4. The method of claim 3, further comprising:

receiving, at the memory controller, a request to remove data in any one of the plurality of memory blocks in the storage system;

selecting, by the memory controller, one of the memory blocks in the storage system;

determining, by the memory controller, a third wear count associated with the selected memory block, wherein the third wear count is indicative of a number of times the memory block has been erased; and

when the third wear count associated with the selected memory block is less than the threshold wear count, causing, by the memory controller, data to be removed from the selected memory block.

5. The method of claim 4, further comprising:

when the third wear count associated with the selected memory block is not less than the threshold wear count, selecting, by the memory controller, a second one of the memory blocks in the storage system;

determining, by the memory controller, a fourth wear count associated with the second one of the memory blocks; and

when the fourth wear count associated with the second one of the memory blocks is less than the threshold wear count, causing, by the memory controller, data to be removed from the second one of the memory blocks.

6. The method of claim 5, wherein when the memory controller is unable to identify, after a fixed number of iterations, a memory block whose wear count is less than the threshold wear count, randomly selecting a memory block for the garbage collection operation.

7. The method of claim 3, wherein determining the threshold wear count comprises determining the threshold wear count based on the value of the first wear count element in the wear count table.

8. The method of claim 7, wherein the value of the first wear count element is indicative of an upper bound of a bottom p % of all wear counts associated with the plurality of memory blocks.

9. A storage system comprising:

one or more storage devices comprising a plurality of memory blocks for maintaining data;

a wear count table having a plurality of wear count elements, wherein each of the wear count elements is assigned to at least one wear count; and

a memory controller configured to;

detect a data removal operation performed on one of the plurality of memory blocks;

increase a wear count associated with the one of the plurality of memory blocks from a first wear count to a second wear count;

identify a first wear count element of the wear count table assigned to the first wear count;

identify a second wear count element of the wear count table assigned to the second wear count; and

when the first wear count element and the second wear count element are different, decrease a value of the first wear count element by one and increase a value of the second wear count element by one.

10. The storage system of claim 9, wherein the data removal operation comprises a garbage collection operation.

11. The storage system of claim 9, wherein the memory controller is further configured to determine a threshold wear count based on the wear count table.

12. The storage system of claim 11, wherein the memory controller is further configured to:

receive a request to remove data in any one of the plurality of memory blocks in the storage system,

select one of the memory blocks in the storage system,

determine a third wear count associated with the selected memory block, wherein the third wear count is indicative of a number of times the memory block has been erased, and

when the third wear count associated with the selected memory block is less than the threshold wear count, cause data to be removed from the selected memory block.

13. The storage system of claim 12, wherein, when the third wear count associated with the selected memory block is not less than the threshold wear count, the memory controller is further configured to:

select a second one of the memory blocks in the storage system;

determine a fourth wear count associated with the second one of the memory blocks; and

when the fourth wear count associated with the second one of the memory blocks is less than the threshold wear count, cause data to be removed from the second one of the memory blocks.

14. The storage system of claim 13, wherein, when the memory controller is unable to identify, after a fixed number of iterations, a memory block whose wear count is less than the threshold wear count, the memory controller is configured to randomly select a memory block for the garbage collection operation.

15. The storage system of claim 11, wherein the memory controller is configured to determine the threshold wear count based on the value of the first wear count element in the wear count table.

16. The storage system of claim 15, wherein the value of the first wear count element is indicative of an upper bound of a bottom p % of all wear counts associated with the plurality of memory blocks.

17. A non-transitory computer readable medium having executable instructions operable to cause a memory controller in a storage system, comprising a plurality of memory blocks, to:

maintain a wear count table having a plurality of wear count elements, wherein each of the wear count elements is assigned to at least one wear count;

detect a data removal operation performed on one of the plurality of memory blocks;

increase a wear count associated with the one of the plurality of memory blocks from a first wear count to a second wear count;

identify a first wear count element of the wear count table assigned to the first wear count;

identify a second wear count element of the wear count table assigned to the second wear count; and

when the first wear count element and the second wear count element are different, decrease a value of the first wear count element by one and increase a value of the second wear count element by one.

18. The computer readable medium of claim 17, further comprising executable instructions operable to cause the memory controller to determine the threshold wear count based on the value of the first wear count element in the wear count table.

19. The computer readable medium of claim 18, wherein the value of the first wear count element is indicative of an upper bound of a bottom p % of all wear counts associated with the plurality of memory blocks.

20. The computer readable medium of claim 17, further comprising executable instructions operable to cause the memory controller to:

receive a request to remove data in any one of the plurality of memory blocks in the storage system,

select one of the memory blocks in the storage system,

determine a third wear count associated with the selected memory block, wherein the third wear count is indicative of a number of times the memory block has been erased, and

when the third wear count associated with the selected memory block is less than the threshold wear count, cause data to be removed from the selected memory block.