Wear leveling for low-wear areas of low-latency random read memory

• US 8,001,318 B1
• Filed: 10/28/2008
• Issued: 08/16/2011
• Est. Priority Date: 10/28/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goodson, Garth R., Iyer, Rahul N.
• Primary Examiner(s): Nguyen; Than
• Application Number:
  US12/260,013
• Time in Patent Office: 1,022 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 2212/7211 Wear leveling

Abstract

Described herein are method and apparatus for performing wear leveling of erase-units of an LLRRM device that considers all active erase-units. Wear counts of all active erase-units (containing client data) and free erase-units (not containing client data) are tracked. Wear counts are used to determine low-wear active erase-units having relatively low wear counts and high-wear free erase-units having relatively high wear counts. In some embodiments, data contents of low-wear active erase-units are transferred to high-wear free erase-units, whereby the low-wear active erase-units are converted to free erase-units and may later store different client data which may increase the current rate of wear for the erase-unit. The high-wear free erase-units are converted to active erase-units that store client data that is infrequently erased/written, which may reduce the current rate of wear for the erase-unit. As such, wear is spread more evenly among erase-units of the LLRRM device.

Claims

1. A storage system for storing client data, the storage system comprising:

at least one low-latency random read memory (LLRRM) device, the LLRRM device comprising a plurality of active erase-units that store client data and a plurality of free erase-units that do not store client data;

active and free wear count (WC) data structures, the active WC data structure comprising an entry for each active EU in the LLRRM device, the free WC data structure comprising a plurality of entries for a plurality of free EUs in the LLRRM device, each entry in the active and free WC data structures comprising a wear count associated with an EU, the wear count indicating a number of erase cycles performed on the EU; and

a wear leveling module executed by a processor, the wear leveling module configured for;

selecting a pair of EUs for performing wear leveling, the selected pair comprising an active EU and a free EU that are selected based on the information in the active and free WC data structures; and

performing wear leveling on the selected pair by copying client data from the active EU to the free EU.

2. The storage system of claim 1, wherein the entries in the active and free WC data structures are sorted according to wear counts.

3. The storage system of claim 1, wherein the wear leveling module is further configured for:

initiating wear leveling upon determining that a variance of two predetermined wear counts in the active and free WC data structures exceeds a predetermined variance threshold.

4. The storage system of claim 3, wherein the two predetermined wear counts comprise:

an absolute lowest wear count and an absolute highest wear count in the active and free WC data structures;

a lowest wear count in the active WC data structure and a highest wear count in the free WC data structure;

or

an average wear count of the active EUs in the active WC data structure and an average wear count of free EUs in the free WC data structure.

5. The storage system of claim 3, wherein the wear leveling module comprises a parameter interface configured for:

receiving a plurality of values for the predetermined variance threshold to dynamically change the predetermined variance threshold.

6. The storage system of claim 1, wherein the wear leveling module is further configured for:

initiating wear leveling upon determining that a variance of two predetermined wear counts in the active and free WC data structures exceeds a predetermined variance threshold and a predetermined wear indicator threshold has been exceeded, a wear indicator reflecting a total number of erase cycles performed on the LLRRM device.

7. The storage system of claim 6, wherein the wear leveling module is further configured for:

initiating wear leveling upon determining that conditions of one of two or more different combinations of predetermined variance thresholds and predetermined wear indicator thresholds are met.

8. The storage system of claim 1, wherein the selected pair comprises:

an active EU having a wear count within the lowest 10% of wear counts in the active WC data structure and a free active EU having a wear count within the highest 10% of wear counts in the free WC data structure;

or

an active EU having a lowest wear count in the active WC data structure and a free active EU having a highest wear count in the free WC data structure.

9. The storage system of claim 1, wherein the wear leveling module is further configured for performing wear leveling on the selected pair of active and free EUs by:

converting the active EU to a free EU by removing its entry from the active WC data structure and adding it to the free WC data structure; and

converting the free EU to an active EU by removing its entry from the free WC data structure and adding it to the active WC data structure.

10. The storage system of claim 1, wherein the wear leveling module is further configured for:

continuing to select pairs of EUs for performing wear leveling based on the information in the active and free WC data structures and performing wear leveling on the selected pairs until a predetermined termination event occurs, the occurrence of the predetermined termination event being determined using information in the active and free WC data structures.

11. The storage system of claim 10, wherein the predetermined termination event comprises a variance between two predetermined wear counts in the active and free WC data structures becoming equal to or less than a predetermined variance threshold.

12. The storage system of claim 10, wherein the two predetermined wear counts comprise:

an absolute lowest wear count and an absolute highest wear count in the active and free WC data structures;

a lowest wear count in the active WC data structure and a highest wear count in the free WC data structure;

or

an average wear count of the active EUs in the active WC data structure and an average wear count of free EUs in the free WC data structure.

13. The storage system of claim 1, wherein the LLRRM device comprises a non-volatile, rewridata structure solid state memory having lower latency in performing random write requests relative to disk devices.

14. A storage system for storing client data, the storage system comprising:

at least one low-latency random read memory (LLRRM) device, the LLRRM device comprising a plurality of active erase-units that store client data and a plurality of free erase-units that do not store client data;

active and free wear count (WC) data structures, the active WC data structure comprising an entry for each active EU in the LLRRM device, the free WC data structure comprising a plurality of entries for a plurality of free EUs in the LLRRM device, each entry in the active and free WC data structures comprising a wear count associated with an EU, the wear count indicating a number of erase cycles performed on the EU; and

a wear leveling module executed by a processor, the wear leveling module configured for;

initiating wear leveling upon determining that a variance of two predetermined wear counts in the active and free WC data structures exceeds a predetermined variance threshold; and

upon wear leveling being initiated, performing wear leveling on a selected pair of EUs comprising an active EU and a free EU by copying client data from the active EU to the free EU.

15. The storage system of claim 14, wherein the two predetermined wear counts comprise:

an absolute lowest wear count and an absolute highest wear count in the active and free WC data structures;

a lowest wear count in the active WC data structure and a highest wear count in the free WC data structure;

or

an average wear count of the active EUs in the active WC data structure and an average wear count of free EUs in the free WC data structure.

16. The storage system of claim 14, wherein the selected pair comprises:

an active EU having a wear count within the lowest 10% of wear counts in the active WC data structure and a free active EU having a wear count within the highest 10% of wear counts in the free WC data structure;

or

an active EU having a lowest wear count in the active WC data structure and a free active EU having a highest wear count in the free WC data structure.

17. The storage system of claim 14, wherein the wear leveling module is further configured for performing wear leveling on the selected pair of active and free EUs by:

converting the active EU to a free EU by removing its entry from the active WC data structure and adding it to the free WC data structure; and

converting the free EU to an active EU by removing its entry from the free WC data structure and adding it to the active WC data structure.

18. The storage system of claim 14, wherein the wear leveling module is further configured for:

continuing to perform wear leveling on selected pairs of active and free EUs until a predetermined termination event occurs, the occurrence of the predetermined termination event being determined using information in the active and free WC data structures.

19. A storage system for storing client data, the storage system comprising:

at least one low-latency random read memory (LLRRM) device, the LLRRM device comprising a plurality of active erase-units that store client data and a plurality of free erase-units that do not store client data;

active and free wear count (WC) data structures, the active WC data structure comprising an entry for each active EU in the LLRRM device, the free WC data structure comprising a plurality of entries for a plurality of free EUs in the LLRRM device, each entry in the active and free WC data structures comprising a wear count associated with an EU, the wear count indicating a number of erase cycles performed on the EU; and

a wear leveling module executed by a processor, the wear leveling module configured for;

selecting for wear leveling an active EU having a wear count within the lowest 10% of wear counts in the active WC data structure and a free active EU having a wear count within the highest 10% of wear counts in the free WC data structure; and

performing wear leveling by copying client data from the active EU to the free EU.

20. The storage system of claim 19, wherein the wear leveling module is further configured for:

initiating wear leveling upon determining that a variance of two predetermined wear counts in the active and free WC data structures exceeds a predetermined variance threshold.

21. The storage system of claim 19, wherein the wear leveling module is further configured for performing wear leveling on the selected pair of active and free EUs by:

converting the active EU to a free EU by removing its entry from the active WC data structure and adding it to the free WC data structure; and

converting the free EU to an active EU by removing its entry from the free WC data structure and adding it to the active WC data structure.

22. The storage system of claim 19, wherein the wear leveling module is further configured for:

continuing to select pairs of EUs for performing wear leveling based on the information in the active and free WC data structures and performing wear leveling on the selected pairs until a predetermined termination event occurs, the occurrence of the predetermined termination event being determined using information in the active and free WC data structures.

23. A method for performing wear leveling in a storage system for storing client data, the storage system comprising at least one low-latency random read memory (LLRRM) device, the LLRRM device comprising a plurality of active erase-units that store client data and a plurality of free erase-units that do not store client data, the method comprising:

maintaining active and free wear count (WC) data structures, the active WC data structure comprising an entry for each active EU in the LLRRM device, the free WC data structure comprising a plurality of entries for a plurality of free EUs in the LLRRM device, each entry in the active and free WC data structures comprising a wear count associated with an EU, the wear count indicating a number of erase cycles performed on the EU;

selecting a pair of EUs for performing wear leveling, the selected pair comprising an active EU and a free EU that are selected based on the information in the active and free WC data structures; and

performing wear leveling on the selected pair by copying client data from the active EU to the free EU.

24. The method of claim 23, further comprising:

initiating wear leveling upon determining that a variance of two predetermined wear counts in the active and free WC data structures exceeds a predetermined variance threshold.

25. The method of claim 24, wherein the two predetermined wear counts comprise:

an absolute lowest wear count and an absolute highest wear count in the active and free WC data structures;

a lowest wear count in the active WC data structure and a highest wear count in the free WC data structure;

or

an average wear count of the active EUs in the active WC data structure and an average wear count of free EUs in the free WC data structure.

26. The method of claim 23, wherein the selected pair comprises:

an active EU having a wear count within the lowest 10% of wear counts in the active WC data structure and a free active EU having a wear count within the highest 10% of wear counts in the free WC data structure;

or

an active EU having a lowest wear count in the active WC data structure and a free active EU having a highest wear count in the free WC data structure.

27. The method of claim 23, further comprising:

continuing to select pairs of EUs for performing wear leveling based on the information in the active and free WC data structures and performing wear leveling on the selected pairs until a predetermined termination event occurs, the occurrence of the predetermined termination event being determined using information in the active and free WC data structures.