Wear leveling in solid state devices

• US 10,642,495 B2
• Filed: 06/18/2018
• Issued: 05/05/2020
• Est. Priority Date: 10/08/2014
• Status: Active Grant

• Current Assignee: Sandisk Technologies Incorporated (Western Digital Corporation)
• Original Assignee: Western Digital Technologies Incorporated (Western Digital Corporation)
• Inventors: Rastogi, Kanishk, Unnikrishnan, Sanoj Kizhakkekara, Mitra, Anand
• Primary Examiner(s): Verbrugge, Kevin
• Application Number:
  US16/011,572
• Publication Number:
  US 20180300062A1
• Time in Patent Office: 687 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 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:

receiving, at a memory controller in a storage system, a request to delete data from the storage system;

determining a wear count value associated with a memory block among a plurality of memory blocks of the storage system;

determining whether the wear count value associated with the memory block satisfies a threshold wear count value; and

in response to determining that the wear count value associated with the memory block satisfies the threshold wear count value;

causing, by the memory controller, deletion of data from the memory block.

2. The method of claim 1, further comprising

in response to determining that the wear count value associated with the memory block does not satisfy the threshold wear count value:

selecting a second memory block from the plurality of memory blocks of the storage system;

determining, by the memory controller, whether a wear count value associated with the second memory block satisfies the threshold wear count value; and

in response to determining that the wear count value associated with the second memory block satisfies the threshold wear count value,

causing, by the memory controller, deletion of data from the second memory block.

3. The method of claim 1, further comprising:

in response to determining that the wear count value associated with the memory block does not satisfy the threshold wear count value;

determining, by the memory controller, whether a counter satisfies a threshold number of attempts to identify a memory block associated with a wear count value that satisfies the threshold wear count value;

in response to determining that the counter satisfies the threshold number of attempts;

selecting randomly, by the memory controller, a second memory block from the plurality of memory blocks of the storage system; and

causing, by the memory controller, deletion of data from the second memory block.

4. The method of claim 1, further comprising:

updating the wear count value associated with the memory block to an updated wear count value.

5. The method of claim 4, further comprising:

updating, by the memory controller, the wear count value associated with the memory block to the updated wear count value by increasing the wear count value.

6. The method of claim 4, further comprising:

identifying, by the memory controller, based on the wear count value, a first wear count element in a data structure;

identifying, by the memory controller, based on the updated wear count value, a second wear count element in the data structure;

determining, by the memory controller, whether the first wear count element and the second wear count element are different; and

in response to determining that the first wear count element and the second wear count element are different;

updating, by the memory controller, based on the updated wear count value, the data structure.

7. The method of claim 6, wherein the first wear count element is associated with a first range of wear count values and a first number of memory blocks among the plurality of memory blocks of the storage system, and wherein the second wear count element is associated with a second range of wear count values and a second number of memory blocks among the plurality of memory blocks of the storage system.

8. The method of claim 7, wherein the wear count value is within the first range of wear count values, and the updated wear count value is within the second range of wear count values.

9. The method of claim 7, further comprising:

updating the data structure by decreasing the first number of memory blocks associated with the first wear count element, and increasing the second number of memory blocks associated with the second wear count element.

10. A storage system comprising:

a plurality of memory blocks; and

a memory controller;

wherein the memory controller is configured to;

receive a request to delete data from the storage system;

determine a wear count value associated with a memory block among a plurality of memory blocks of the storage system;

determine whether the wear count value associated with the memory block satisfies a threshold wear count value; and

when the wear count value is determined to be associated with the memory block satisfies the threshold wear count value,

update the wear count value associated with the memory block to an updated wear count value, and

cause deletion of data from the memory block.

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

in response to determining that the wear count value associated with the memory block does not satisfy the threshold wear count value;

select a second memory block from the plurality of memory blocks;

determine whether a wear count value associated with the second memory block satisfies the threshold wear count value; and

in response to determining that the wear count value associated with the second memory block satisfies the threshold wear count value;

cause deletion of data from the second memory block.

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

in response to determining that the wear count value associated with the memory block does not satisfy the threshold wear count value;

determine whether a counter satisfies a threshold number of attempts to identify a memory block associated with a wear count value that satisfies the threshold wear count value; and

in response to determining that the counter satisfies the threshold number of attempts;

select a second memory block from the plurality of memory blocks; and

cause deletion of data from the second memory block.

13. The storage system of claim 10, wherein the memory controller is configured to increase the wear count value to update the wear count value to the updated wear count value.

14. The storage system of claim 10, wherein the memory controller is configured to:

identify, based on the wear count value, a first wear count element in a data structure;

identify, based on the updated wear count value, a second wear count element in the data structure;

determine whether the first wear count element and the second wear count element are different; and

in response to determining that the first wear count element and the second wear count element are different, update the data structure.

15. The storage system of claim 14, wherein the first wear count element is associated with a first one or more wear count values and a first number of memory blocks among the plurality of memory blocks of the storage system, and wherein the second wear count element is associated with a second one or more wear count values and a second number of memory blocks among the plurality of memory blocks.

16. The storage system of claim 15, wherein the wear count value is one of the first one or more wear count values, and the updated wear count value is one of the second one or more wear count values.

17. The storage system of claim 15, wherein the memory controller is configured to:

decrease the first number of memory blocks associated with the first wear count element, and increase the second number of memory blocks associated with the second wear count element, to update the data structure.

18. A system comprising:

means for receiving a request to delete data from a storage system;

means for determining a wear count value associated with a memory block among a plurality of memory blocks of the storage system;

means for determining whether the wear count value associated with the memory block satisfies a threshold wear count value;

in response to determining that the wear count value associated with the memory block satisfies the threshold wear count value;

means for updating the wear count value associated with the memory block to an updated wear count value by increasing the wear count value; and

means for causing deletion of data from the memory block.

19. The system of claim 18, further comprising:

in response to determining that the wear count value associated with the memory block does not satisfy the threshold wear count value;

means for determining whether a counter satisfies a threshold number of attempts to identify a memory block associated with a wear count value that satisfies the threshold wear count value; and

in response to determining that the counter satisfies the threshold number of attempts;

means for selecting randomly a second memory block from the plurality of memory blocks of the storage system; and

means for causing deletion of data from the second memory block.

20. A non-transitory machine-readable medium including machine-executable instructions thereon that, when executed by a processor, perform a method comprising:

receiving a request to delete data from a storage system;

determining a wear count value associated with a memory block among a plurality of memory blocks of the storage system;

determining whether the wear count value associated with the memory block satisfies a threshold wear count value; and

in response to determining that the wear count value associated with the memory block satisfies the threshold wear count value;

causing deletion of data from the memory block;

in response to determining that the wear count value associated with the memory block does not satisfy the threshold wear count value;

determining whether a counter satisfies a threshold number of attempts to identify a memory block associated with a wear count that satisfies the threshold wear count value; and

in response to determining that the counter satisfies the threshold number of attempts;

selecting randomly a second memory block from the plurality of memory blocks of the storage system; and

causing deletion of data from the second memory block.