Efficient implementation of optimized host-based garbage collection strategies using xcopy and multiple logical stripes

• US 10,185,658 B2
• Filed: 07/12/2016
• Issued: 01/22/2019
• Est. Priority Date: 02/23/2016
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: O'Krafka, Brian W., Bolkhovitin, Vladislav, Shivhare, Vivek
• Primary Examiner(s): Sadler, Nathan
• Application Number:
  US15/208,540
• Publication Number:
  US 20170242790A1
• Time in Patent Office: 924 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• 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/1036 Life time enhancement
• CPC Class Codes: G06F 2212/7201 Logical to physical mapping or translation of blocks or pages
• CPC Class Codes: G06F 2212/7205 Cleaning, compaction, garbage collection, erase control
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• 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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0652 Erasing, e.g. deleting, data cleaning, moving of data to a wastebasket
• CPC Class Codes: G06F 3/0679 Non-volatile semiconductor memory device, e.g. flash memory, one time programmable memory [OTP]
• CPC Class Codes: G06F 3/0688 Non-volatile semiconductor memory arrays

Abstract

Systems, methods and/or devices are used for efficient implementation of optimized host-based garbage collection strategies using xcopy and arrays of flash devices. In one aspect, a method of managing a storage system having one or more storage devices includes a host-based garbage collection operation that includes identifying two or more logical stripes in accordance with data storage information stored at the host system, and enabling a process of coalescing valid data in the two or more logical stripes. Further, the use of an internal copy operation (e.g., xcopy), allows the host-based garbage collection operation to occur without transferring data back to the host, thus minimizing the number of I/O operations between the host and storage devices. Additionally, use of the host-based garbage collection operation allows more sophisticated garbage collection algorithms (e.g., matching the current workload) to be used, and ensures that multiple logical stripes are available to write data.

Claims

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

at a host system that is distinct from the plurality of storage devices, performing a host-based garbage collection operation, comprising;

identifying, in accordance with data storage information stored at the host system, one or more logical stripes, wherein

each logical stripe of the one or more logical stripes is a distinct contiguous sequence of logical addresses in a logical address space of the host system,

each logical stripe includes two or more contiguous sequences of valid logical addresses, which are separated from each other by one or more gaps,

a size of each logical stripe is a same predetermined size, and

logical addresses for each logical stripe in the logical address space of the host system are mapped to physical addresses in a physical address space of the plurality of storage devices by mapping information in the plurality of storage devices; and

in accordance with the identifying, for each logical stripe of the one or more logical stripes, coalescing valid data, including;

for at least one contiguous sequence of valid logical addresses of the group of two or more contiguous sequences of valid logical addresses, in a logical stripe in the logical address space of the host system, sending instructions from the host system to one or more storage devices of the plurality of storage devices to move valid data corresponding to a first contiguous sequence of valid logical addresses from a first physical location in the physical address space to a second physical location in the physical address space; and

for each respective logical stripe of the one or more logical stripes, repacking the two or more contiguous sequences of valid logical addresses, in the respective logical stripe in the logical address space of the host system, to a single contiguous set of logical addresses in a contiguous portion of a corresponding target logical stripe, in the logical address space of the host system, the corresponding target logical stripe comprising the respective logical stripe or another logical stripe distinct from the respective logical stripe, wherein the other logical stripe is a second contiguous sequence of logical addresses in the logical address space of the host system distinct from the first contiguous sequence of logical addresses in the logical address space of the host system.

2. The method of claim 1, wherein identifying the one or more logical stripes, in the logical address space of the host system, includes determining how many logical stripes are needed for the host-based garbage collection operation.

3. The method of claim 1, wherein identifying the one or more logical stripes, in the logical address space of the host system, includes identifying the one or more logical stripes in accordance with selection criteria.

4. The method of claim 1, including:

partitioning the plurality of storage devices into two or more regions, wherein a respective region of the two or more regions corresponds to a respective logical stripe of the one or more logical stripes, in the logical address space of the host system.

5. The method of claim 4, wherein partitioning the plurality of storage devices includes:

determining how many regions are needed for the host-based garbage collection operation;

determining an over-provisioning amount for the two or more regions.

6. The method of claim 4, wherein partitioning the plurality of storage devices includes dynamically adjusting the two or more regions as workload of the storage system changes.

7. The method of claim 1, further comprising:

after coalescing valid data in the one or more logical stripes, in the logical address space of the host system,

classifying an incoming write request; and

selecting a logical stripe in which to place the incoming write request in accordance with classification criteria.

8. The method of claim 1, wherein the one or more logical stripes, in the logical address space of the host system, include a first logical stripe and a second logical stripe;

and

the first logical stripe is used for data with a first set of characteristics and the second logical stripe is used for data with a second set of characteristics, distinct from the first set of characteristics.

9. The method of claim 1, wherein coalescing valid data in the one or more logical stripes includes:

migrating valid data between distinct logical stripes of the one or more logical stripes in the logical address space of the host system in accordance with migration criteria.

10. The method of claim 1, wherein sending instructions from the host system to the one or more storage devices to move valid data corresponding to the first contiguous sequence of valid logical addresses includes issuing one or more xcopy commands to the one or more storage devices.

11. The method of claim 1, wherein the instructions to move valid data comprise copy instructions that copy valid data corresponding to valid logical addresses in the one or more logical stripes, in the logical address space of the host system, from initial memory portions in the plurality of storage devices to different memory portions in the plurality of storage devices corresponding to new logical addresses in the one or more logical stripes in the logical address space of the host system.

12. The method of claim 1, further comprising:

for each contiguous sequence of valid logical addresses in the one or more logical stripes, in the logical address space of the host system, after sending said instructions, invalidating data corresponding to the first contiguous sequence of valid logical addresses at the first physical location in the physical address space.

13. The method of claim 1, further comprising:

in accordance with a determination that first garbage collection scheduling criteria of the storage system are met, triggering performance of the host-based garbage collection operation, wherein the first garbage collection scheduling criteria of the storage system are independent of second garbage collection scheduling criteria used to trigger performance of internal garbage collection operations within each storage device of the plurality of storage devices.

14. The method of claim 13, wherein performance of the host-based garbage collection operation is triggered so as to ensure that internal garbage collection operations within each storage device are minimized.

15. The method of claim 13, wherein the first garbage collection scheduling criteria include criteria corresponding to a write operation workload of the storage system, criteria corresponding to a projected workload of the storage system, or criteria corresponding to a number of empty logical stripes in the storage system.

16. The method of claim 1, further comprising:

repeatedly performing, over a period of time, said host-based garbage collection operation to ensure that at least a minimum number of logical stripes, in the logical address space of the host system and managed by the host system, are available in which to place write data.

17. The method of claim 1, wherein the method is controlled by the host system, which includes a client, on behalf of which, data is stored in the storage system.

18. The method of claim 1, wherein the plurality of storage devices comprises one or more flash memory devices.

19. The method of claim 1, wherein the one or more logical stripes is a group of two or more logical stripes.

20. A host system, comprising:

an interface for operatively coupling to a storage system having a plurality of storage devices;

one or more processors; and

memory storing one or more programs, which when executed by the one or more processors cause the host system that is distinct from the plurality of storage devices to perform a host-based garbage collection operation comprising;

identifying, in accordance with data storage information stored at the host system, one or more logical stripes, wherein

each logical stripe of the one or more logical stripes is a distinct contiguous sequence of logical addresses in a logical address space of the host system,

each logical stripe includes two or more contiguous sequences of valid logical addresses, which are separated from each other by one or more gaps,

a size of each logical stripe is a same predetermined size, and

logical addresses for each logical stripe in the logical address space of the host system are mapped to physical addresses in a physical address space of the plurality of storage devices by mapping information in the plurality of storage devices; and

in accordance with the identifying, for each logical stripe of the one or more logical stripes, coalescing valid data, including;

for at least one contiguous sequence of valid logical addresses of the group of two or more contiguous sequences of valid logical addresses, in a logical stripe in the logical address space of the host system, sending instructions from the host system to one or more storage devices of the plurality of storage devices to move valid data corresponding to a first contiguous sequence of valid logical addresses from a first physical location in the physical address space to a second physical location in the physical address space; and

for each respective logical stripe of the one or more logical stripes, repacking the two or more contiguous sequences of valid logical addresses, in the respective logical stripe in the logical address space of the host system, to a single contiguous set of logical addresses in a contiguous portion of a corresponding target logical stripe, in the logical address space of the host system, the corresponding target logical stripe comprising the respective logical stripe or another logical stripe distinct from the respective logical stripe, wherein the other logical stripe is a second contiguous sequence of logical addresses in the logical address space of the host system distinct from the first contiguous sequence of logical addresses in the logical address space of the host system.

21. The host system of claim 20, wherein the one or more programs include:

a compacting module having instructions for moving valid data corresponding to the first contiguous sequence of valid logical addresses, in the logical address space of the host system, from a first physical location in the physical address space to a second physical location in the physical address space, and

for each logical stripe in the logical address space of the host system, repacking valid logical addresses in the respective logical stripe to a beginning of the respective logical stripe.

22. The host system of claim 20, wherein the one or more logical stripes is a group of two or more logical stripes.

23. A non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of a host system that is distinct from a plurality of storage devices in a storage system, the one or more programs including instructions that when executed by the one or more processors cause the host system to perform a host-based garbage collection operation, including:

identifying, in accordance with data storage information stored at the host system, one or more logical stripes, wherein

each logical stripe is a distinct contiguous sequence of logical addresses in the logical address space of the host system,

each logical stripe includes two or more contiguous sequences of valid logical addresses, which are separated from each other by one or more gaps,

a size of each logical stripe of the one or more logical stripes is a same predetermined size, and

logical addresses for each logical stripe in the logical address space of the host system are mapped to physical addresses in a physical address space of the plurality of storage devices by mapping information in the plurality of storage devices; and

in accordance with the identifying, for each logical stripe in the one or more logical stripes, coalescing valid, including;

for at least one contiguous sequence of valid logical addresses of the group of two or more contiguous sequences of valid logical addresses, in a logical stripe in the logical address space of the host system, sending instructions from the host system to one or more storage devices of the plurality of storage devices to move valid data corresponding to a first contiguous sequence of valid logical addresses from a first physical location in the physical address space to a second physical location in the physical address space; and

for each respective logical stripe of the one or more logical stripes, repacking the two or more contiguous sequences of valid logical addresses, in the respective logical stripe in the logical address space of the host system, to a single contiguous set of logical addresses in a contiguous portion of a corresponding target logical stripe, in the logical address space of the host system, the corresponding target logical stripe comprising the respective logical stripe or another logical stripe distinct from the respective logical stripe, wherein the other logical stripe is a second contiguous sequence of logical addresses in the logical address space of the host system distinct from the first contiguous sequence of logical addresses in the logical address space of the host system.

24. The non-transitory computer readable storage medium of claim 23, wherein the one or more logical stripes is a group of two or more logical stripes.

25. A storage system, comprising:

a plurality of storage devices;

one or more subsystems having one or more processors; and

memory storing one or more programs, which when executed by the one or more processors cause the one or more subsystems to perform operations comprising;

at a host system that is distinct from the plurality of storage devices, performing a host-based garbage collection operation, comprising;

identifying, in accordance with data storage information stored at the host system, one or more logical stripes, wherein

each logical stripe is a distinct contiguous sequence of logical addresses in a logical address space of the host system,

each logical stripe includes two or more contiguous sequences of valid logical addresses, which are separated from each other by one or more gaps,

a size of each logical stripe of the one or more logical stripes is a same predetermined size, and

logical addresses for each logical stripe in the logical address space of the host system are mapped to physical addresses in a physical address space of the plurality of storage devices by mapping information in the plurality of storage devices; and

in accordance with the identifying, for each logical stripe in the one or more logical stripes, coalescing valid data, including;

for at least one contiguous sequence of valid logical addresses of the group of two or more contiguous sequences of valid logical addresses, in a logical stripe in the logical address space of the host system, sending instructions from the host system to one or more storage devices of the plurality of storage devices to move valid data corresponding to a first contiguous sequence of valid logical addresses from a first physical location in the physical address space to a second physical location in the physical address space; and

for each respective logical stripe of the one or more logical stripes, repacking the two or more contiguous sequences of valid logical addresses, in the respective logical stripe in the logical address space of the host system, to a single contiguous set of logical addresses in a contiguous portion of a corresponding target logical stripe, in the logical address space of the host system, the corresponding target logical stripe comprising the respective logical stripe or another logical stripe distinct from the respective logical stripe, wherein the other logical stripe is a second contiguous sequence of logical addresses in the logical address space of the host system distinct from the first contiguous sequence of logical addresses in the logical address space of the host system.

26. The storage system of claim 25, wherein the one or more logical stripes is a group of two or more logical stripes.