Scheduling operations in non-volatile memory devices using preference values

• US 9,870,149 B2
• Filed: 11/10/2015
• Issued: 01/16/2018
• Est. Priority Date: 07/08/2015
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Sprouse, Steven, Marlin, Ryan
• Primary Examiner(s): TSAI, SHENG JEN
• Application Number:
  US14/937,793
• Publication Number:
  US 20170010815A1
• Time in Patent Office: 798 Days
• Field of Search: 711103
• CPC Class Codes: G06F 12/0246 in block erasable memory, e.g. flash memory
• CPC Class Codes: G06F 12/0253 Garbage collection, i.e. reclamation of unreferenced memory
• CPC Class Codes: G06F 2212/1016 Performance improvement
• 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/7208 Multiple device management, e.g. distributing data over multiple flash devices
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

A method of scheduling memory operations to be performed by non-volatile memory devices in a storage system includes identifying a plurality of memory operations to be performed by a plurality of non-volatile memory devices in the storage system. The number of memory operations in the plurality of memory operations is no greater than the number of non-volatile memory devices in the plurality of non-volatile memory devices; each memory operation is to be performed by a distinct non-volatile memory device; and the memory operations include host writes, garbage collection writes, and garbage collection reads. The method also includes, for each non-volatile memory device, assigning preference values to each of the memory operations. The method further includes assigning each memory operation to a distinct non-volatile memory device, using the preference values assigned to each of the memory operations for each non-volatile memory device.

Claims

1. A method of managing a storage system, the method comprising:

in the storage system, which includes a storage controller and non-volatile memory devices;

identifying a plurality of memory operations to be performed by a plurality of the non-volatile memory devices in the storage system, wherein

the plurality of memory operations comprises a first number of memory operations and the plurality of non-volatile memory devices comprises a second number of memory devices,

the first number is no greater than the second number,

each memory operation of the plurality of memory operations is to be performed by a distinct non-volatile memory device, and

the memory operations comprise host writes, garbage collection writes, and garbage collection reads;

for each non-volatile memory device in the plurality of non-volatile memory devices, assigning preference values to each of the memory operations in the plurality of memory operations, wherein assigning preference values comprises, for a respective non-volatile memory device;

determining that a first memory operation of the plurality of memory operations is associated with a process for which no more than a specified number of memory operations are incomplete; and

in response to the determining, assigning preference values to the memory operations that indicate a preference of the respective non-volatile memory device for the first memory operation over other memory operations of the plurality of memory operations; and

assigning each memory operation in the plurality of memory operations to a distinct non-volatile memory device in the plurality of non-volatile memory devices, using the preference values assigned to each of the memory operations for each non-volatile memory device;

wherein;

assigning each memory operation to a distinct non-volatile memory device comprises;

solving a predefined combinatorial optimization problem, known as The Stable Marriage Problem using the Gale-Shapely algorithm;

or

solving a predefined combinatorial optimization problem, known as The Assignment Problem using the Hungarian algorithm; and

wherein;

the storage controller manages a plurality of processes;

each memory operation is part of a process;

a respective process comprises memory operations of a common type selected from the group consisting of host writes, garbage collection writes, and garbage collection reads; and

the memory operations of a respective process comprise memory operations directed to respective pages in each of the non-volatile memory devices.

2. The method of claim 1, wherein the plurality of non-volatile memory devices comprises a plurality of memory dies, each non-volatile memory device comprising a distinct memory die of the plurality of memory dies.

3. The method of claim 1, wherein:

the plurality of non-volatile memory devices comprises a first memory device and remaining memory devices;

the respective pages of the remaining memory devices store data; and

the respective page of the first memory device stores parity information corresponding to the data stored in the respective pages of the remaining memory devices.

4. The method of claim 1, wherein the determining comprises determining that the first memory operation is an only remaining incomplete memory operation for its process.

5. The method of claim 1, wherein assigning preference values comprises, for a respective non-volatile memory device:

determining that all memory operations that the respective non-volatile memory device currently can perform are of a first type selected from the group consisting of host writes, garbage collection writes, and garbage collection reads; and

in response to the determining, assigning preference values to the memory operations that indicate a preference of the respective non-volatile memory device for the first type of memory operation over other types of memory operations.

6. The method of claim 1, wherein:

the storage controller comprises a front-end controller and a plurality of back-end controllers coupled to the front-end controller;

each back-end controller is coupled to a respective subset of the plurality of non-volatile memory devices;

the front-end controller receives host write requests and schedules garbage collection writes in accordance with the host write requests;

the back-end controllers schedule garbage collection reads, wherein each garbage collection read corresponds to a respective garbage collection write; and

the front-end controller performs the identifying, the assigning of preference values, and the assigning of each memory operation.

7. The method of claim 1, further comprising, for each memory operation of the plurality of memory operations, assigning preference values to each of the non-volatile memory devices,

wherein assigning each memory operation to a distinct non-volatile memory device is performed using both the preference values assigned to each of the non-volatile memory devices for each memory operation and the preference values assigned to each of the memory operations for each non-volatile memory device.

8. The method of claim 7, wherein:

the storage controller comprises a front-end controller and a plurality of back-end controllers coupled to the front-end controller;

each back-end controller is coupled to a respective subset of the plurality of non-volatile memory devices; and

assigning the preference values to each of the non-volatile memory devices comprises, for a respective memory operation of the plurality of memory operations, assigning preference values that indicate a preference of the respective memory operation for a first subset of the plurality of non-volatile memory devices over other subsets of the plurality of non-volatile memory devices.

9. The method of claim 1, wherein:

assigning preference values to each of the memory operations comprises, for each non-volatile memory device, ranking the memory operations in order of preference; and

assigning each memory operation to a distinct non-volatile memory device comprises solving The Stable Marriage Problem in accordance with the ranking of the memory operations in order of preference for each non-volatile memory device;

wherein;

solving The Stable Marriage Problem comprises;

ranking each member of a first group of N non-volatile memory devices in order of preference for each member of a second group of N memory operations, where N is an integer greater than one;

ranking each member of the second group of N memory operations in order of preference for each member of the first group of N non-volatile memory devices; and

for the first and second groups;

assigning each member of each group to a distinct member of the other group, such that there are no two members of different groups who have a higher preference for each other than with their assigned partners.

10. The method of claim 9, further comprising partitioning the memory operations into a group of host writes, a group of garbage collection writes, and a group of garbage collection reads;

wherein ranking the memory operations in order of preference comprises ranking the groups and ordering the memory operations by the ranked groups.

11. The method of claim 1, wherein:

assigning preference values to each of the memory operations comprises, for each non-volatile memory device, assigning weights to the memory operations; and

assigning each memory operation to a distinct non-volatile memory device comprises solving The Assignment Problem in accordance with the weights of the memory operations for each non-volatile memory device

wherein;

solving The Assignment Problem comprises;

ranking each member of a first group of N non-volatile memory devices in order of preference for each member of a second group of N memory operations, where N is an integer greater than one;

weighting each member of the second group of N memory operations in accordance with a cost that varies as a function of assignments; and

for the first and second groups;

assigning each member of each group to a distinct member of the other group, such that a total cost is minimized.

12. The method of claim 11, further comprising partitioning the memory operations into a group of host writes, a group of garbage collection writes, and a group of garbage collection reads;

wherein assigning weights to the memory operations comprises, for each non-volatile memory device, assigning a first weight to each operation in the group of host writes, assigning a second weight to each operation in the group of garbage collection writes, and assigning a third weight to each operation in the group of garbage collection reads, wherein the first, second, and third weights are distinct.

13. The method of claim 1, wherein identifying the number of memory operations to be performed by the non-volatile memory devices comprises:

determining a ratio of host writes to garbage collection writes, based on a write amplification of the storage system;

selecting host writes and garbage collection writes such that a number of host writes and a number of garbage collection writes satisfy the ratio; and

selecting garbage collection reads such that a number of garbage collection reads equals the number of garbage collection writes.

14. A storage system, comprising:

a plurality of non-volatile memory devices;

one or more processors; and

memory storing one or more programs configured for execution by the one or more processors, the one or more programs comprising instructions that when executed by the one or more processors, cause the storage system to;

identify a plurality of memory operations to be performed by a plurality of the non-volatile memory devices in the storage system, wherein

the plurality of memory operations comprises a first number of memory operations and the plurality of non-volatile memory devices comprises a second number of memory devices,

the first number is no greater than the second number,

each memory operation of the plurality of memory operations is to be performed by a distinct non-volatile memory device, and

the memory operations comprise host writes, garbage collection writes, and garbage collection reads;

for each non-volatile memory device in the plurality of non-volatile memory devices, assign preference values to each of the memory operations in the plurality of memory operations, wherein to assign preference values the one or more programs further comprise instructions to cause the storage system to, for a respective non-volatile memory device;

determine that a first memory operation of the plurality of memory operations is associated with a process for which no more than a specified number of memory operations are incomplete; and

in response to determining that the first memory operation of the plurality of memory operations is associated with the process, assign preference values to the plurality of memory operations that indicate a preference of the respective non-volatile memory device for the first memory operation over other memory operations of the plurality of memory operations;

and

assign each memory operation in the plurality of memory operations to a distinct non-volatile memory device in the plurality of non-volatile memory devices, using the preference values assigned to each of the memory operations for each non-volatile memory device;

wherein;

the storage system assigns each memory operation to a distinct non-volatile memory device by;

solving a first predefined combinatorial optimization problem known as The Stable Marriage Problem using the Gale-Shapely iterative algorithm;

or

solving a second predefined combinatorial optimization problem known as The Assignment Problem using the Hungarian algorithm;

and

wherein;

the one or more processors manage a plurality of processes;

each memory operation is part of a process;

a respective process comprises memory operations of a common type selected from the group consisting of host writes, garbage collection writes, and garbage collection reads; and

the memory operations of a respective process comprise memory operations directed to respective pages in each of the non-volatile memory devices.

15. The storage system of claim 14, wherein the plurality of non-volatile memory devices comprises a plurality of memory dies, each non-volatile memory device comprising a distinct memory die of the plurality of memory dies.

17. The storage system of claim 14, wherein:

assigning preference values to each of the memory operations comprises, for each non-volatile memory device, ranking the memory operations in order of preference; and

assigning each memory operation to a distinct non-volatile memory device comprises solving The Stable Marriage Problem in accordance with the ranking of the memory operations in order of preference for each non-volatile memory device;

wherein;

solving The Stable Marriage Problem comprises;

ranking each member of a first group of N non-volatile memory devices in order of preference for each member of a second group of N memory operations, where N is an integer greater than one;

ranking each member of the second group of N memory operations in order of preference for each member of the first group of N non-volatile memory devices; and

for the first and second groups;

assigning each member of each group to a distinct member of the other group, such that there are no two members of different groups who have a higher preference for each other than with their assigned partners.

18. The storage system of claim 14, wherein:

assigning preference values to each of the memory operations comprises, for each non-volatile memory device, assigning weights to the memory operations; and

assigning each memory operation to a distinct non-volatile memory device comprises solving The Assignment Problem in accordance with the weights of the memory operations for each non-volatile memory device;

wherein;

solving The Assignment Problem comprises;

ranking each member of a first group of N non-volatile memory devices in order of preference for each member of a second group of N memory operations, where N is an integer greater than one;

weighting each member of the second group of N memory operations in accordance with a cost that varies as a function of assignments; and

for the first and second groups;

assigning each member of each group to a distinct member of the other group, such that a total cost is minimized.

16. A non-transitory computer-readable storage medium storing one or more programs configured for execution by one or more processors of a storage system that further comprises a plurality of non-volatile memory devices, the one or more programs comprising instructions that when executed by the one or more processors, cause the storage system to:

identify a plurality of memory operations to be performed by a plurality of the non-volatile memory devices in the storage system, wherein

the plurality of memory operations comprises a first number of memory operations and the plurality of non-volatile memory devices comprises a second number of memory devices,

the first number is no greater than the second number,

each memory operation of the plurality of memory operations is to be performed by a distinct non-volatile memory device, and

the memory operations comprise host writes, garbage collection writes, and garbage collection reads;

for each non-volatile memory device in the plurality of non-volatile memory devices, assign preference values to each of the memory operations in the plurality of memory operations, wherein to assign preference values the one or more programs further comprise instructions to cause the storage system to, for a respective non-volatile memory device;

determine that a first memory operation of the plurality of memory operations is associated with a process for which no more than a specified number of memory operations are incomplete; and

in response to determining that the first memory operation of the plurality of memory operations is associated with the process, assign preference values to the plurality of memory operations that indicate a preference of the respective non-volatile memory device for the first memory operation over other memory operations of the plurality of memory operations; and

assign each memory operation in the plurality of memory operations to a distinct non-volatile memory device in the plurality of non-volatile memory devices, using the preference values assigned to each of the memory operations for each non-volatile memory device;

wherein;

the storage system assigns each memory operation to a distinct non-volatile memory device by;

solving a first predefined combinatorial optimization problem known as The Stable Marriage Problem using the Gale-Shapely iterative algorithm;

or

solving a second predefined combinatorial optimization problem known as The Assignment Problem using the Hungarian algorithm; and

wherein;

the one or more processors manage a plurality of processes;

each memory operation is part of a process;

a respective process comprises memory operations of a common type selected from the group consisting of host writes, garbage collection writes, and garbage collection reads; and

the memory operations of a respective process comprise memory operations directed to respective pages in each of the non-volatile memory devices.

19. The non-transitory computer-readable storage medium of claim 16, wherein:

assigning preference values to each of the memory operations comprises, for each non-volatile memory device, ranking the memory operations in order of preference; and

assigning each memory operation to a distinct non-volatile memory device comprises solving The Stable Marriage Problem in accordance with the ranking of the memory operations in order of preference for each non-volatile memory device;

wherein;

solving The Stable Marriage Problem comprises;

ranking each member of a first group of N non-volatile memory devices in order of preference for each member of a second group of N memory operations, where N is an integer greater than one;

ranking each member of the second group of N memory operations in order of preference for each member of the first group of N non-volatile memory devices; and

for the first and second groups;

assigning each member of each group to a distinct member of the other group, such that there are no two members of different groups who have a higher preference for each other than with their assigned partners.

20. The non-transitory computer-readable storage medium of claim 16, wherein:

assigning preference values to each of the memory operations comprises, for each non-volatile memory device, assigning weights to the memory operations; and

assigning each memory operation to a distinct non-volatile memory device comprises solving The Assignment Problem in accordance with the weights of the memory operations for each non-volatile memory device;

wherein;

solving The Assignment Problem comprises;

ranking each member of a first group of N non-volatile memory devices in order of preference for each member of a second group of N memory operations, where N is an integer greater than one;

weighting each member of the second group of N memory operations in accordance with a cost that varies as a function of assignments; and

for the first and second groups;

assigning each member of each group to a distinct member of the other group, such that a total cost is minimized.