Using History of I/O Sizes and I/O Sequences to Trigger Coalesced Writes in a Non-Volatile Storage Device

• US 20150347040A1
• Filed: 07/03/2014
• Published: 12/03/2015
• Est. Priority Date: 05/30/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Enterprise IP LLC (Western Digital Corporation)
• Inventors: Mathur, Akshay, Kotte, Dharani, Biswas, Chayan, Kannan, Baskaran, Patro, Sumant K.
• Granted Patent: US 10,656,842 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0613 in relation to throughput
• CPC Class Codes: G06F 3/0616 in relation to life time, e.g. increasing Mean Time Between Failures [MTBF]
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• 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/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• 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 to enable using history of I/O sizes and I/O sequences to trigger coalesced writes in a non-volatile storage device. In one aspect, the method includes (1) receiving a plurality of input/output (I/O) requests to be performed in a plurality of regions in a logical address space of a host, and (2) performing one or more operations for each region of the plurality of regions in the logical address space of the host, including (a) determining whether the region has a history of I/O requests to access data of size less than a predefined small-size threshold during a predetermined time period, (b) determining whether the region has a history of sequential write requests during the predetermined time period, and (c) if both determinations are true, coalescing subsequent write requests to the region.

Claims

1. A method, comprising:

receiving, at a storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host; and

performing one or more operations for each region of the plurality of regions in the logical address space of the host, including;

determining whether the region has a history of I/O requests to access data of size less than a predefined small-size threshold during a predetermined time period;

determining whether the region has a history of sequential write requests during the predetermined time period; and

in accordance with a determination that the region has a history of I/O requests to access data of size less than a predefined small-size threshold during the predetermined time period and that the region has a history of sequential write requests during the predetermined time period, coalescing subsequent write requests to the region.

2. The method of claim 1, wherein coalescing subsequent write requests to the region includes:

performing a read ahead operation, to read data from a storage medium of the storage device;

storing read data obtained by the read ahead operation to a cache;

writing one or more subsequent write requests to the cache; and

writing contents of the cache to the storage medium in a merged operation.

3. The method of claim 1, wherein, with respect to a region of the plurality of regions, determining whether the region has a history of I/O requests to access data of size less than a predefined small-size threshold includes:

tracking a total number of write requests to write data of size less than the predefined small-size threshold; and

determining whether the total number of write requests to write data of size less than the predefined small-size threshold is greater than a first threshold.

4. The method of claim 1, wherein, with respect to a region of the plurality of regions, determining whether the region has a history of I/O requests to access data of size less than a predefined small-size threshold includes:

tracking a total number of write requests to write data of size less than the predefined small-size threshold;

tracking a total number of write requests to write data of size greater than a predefined large-size threshold; and

determining whether the total number of write requests to write data of size less than the predefined small-size threshold is greater than a first threshold and whether the total number of write requests to write data of size greater than a predefined large-size threshold is less than a second threshold.

5. The method of claim 1, wherein, with respect to a region of the plurality of regions, determining whether the region has a history of sequential write requests during the predetermined time period includes tracking whether a total number of sequential I/O requests to the region has exceeded a sequential request threshold.

6. The method of claim 1, wherein, with respect to a region of the plurality of regions, determining whether the region has a history of sequential write requests during the predetermined time period includes tracking whether a total number of sequential I/O requests to the region has exceeded a sequential request threshold and tracking whether a total number of sequential write requests to the region has exceeded a sequential write threshold.

7. The method of claim 5, further comprising, for each region of the plurality of regions in the logical address space, setting a flag to denote the determination of whether the total number of sequential I/O requests to the region has exceeded the sequential request threshold.

8. The method of claim 1, further comprising, for each region of the plurality of regions in the logical address space, setting a flag to denote the determination of whether the region has a history of sequential write requests during the predetermined time period.

9. The method of claim 1, further comprising, for each region of the plurality of regions in the logical address space, storing information in a data structure to maintain a history of I/O request patterns in the region for the predetermined time period.

10. The method of claim 1, wherein the predefined small-size threshold is configurable.

11. The method of claim 1, wherein the predetermined time period is configurable.

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

13. The method of claim 1, wherein the storage device comprises one or more three-dimensional (3D) memory devices and circuitry associated with operation of memory elements in the one or more 3D memory devices.

14. The method of claim 13, wherein the circuitry and one or more memory elements in a respective 3D memory device, of the one or more 3D memory devices, are on the same substrate.

15. A storage device, comprising:

one or more processors; and

memory storing one or more programs, which when executed by the one or more processors cause the storage device to;

receive, at the storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host; and

perform one or more operations for each region of the plurality of regions in the logical address space of the host, including;

determining whether the region has a history of I/O requests to access data of size less than a predefined small-size threshold during a predetermined time period;

determine whether the region has a history of sequential write requests during the predetermined time period; and

coalescing, in accordance with a determination that the region has a history of I/O requests to access data of size less than a predefined small-size threshold during the predetermined time period and that the region has a history of sequential write requests during the predetermined time period, subsequent write requests to the region.

16. The storage device of claim 15, wherein coalescing subsequent write requests to the region includes:

performing a read ahead operation, to read data from a storage medium of the storage device;

storing read data obtained by the read ahead operation to a cache;

writing one or more subsequent write requests to the cache; and

writing contents of the cache to the storage medium in a merged operation.

17. The storage device of claim 15, wherein the one or more programs, which when executed by the one or more processors, further cause the storage device to:

for each region of the plurality of regions in the logical address space, set a flag to denote the determination of whether the region has a history of sequential write requests during the predetermined time period.

18. The storage device of claim 15, wherein the one or more programs, which when executed by the one or more processors, further cause the storage device to:

for each region of the plurality of regions in the logical address space, store information in a data structure to maintain a history of I/O request patterns in the region for the predetermined time period.

19. A storage system, comprising:

a storage medium;

one or more processors; and

memory storing one or more programs, which when executed by the one or more processors cause the storage system to;

receive, at a storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host; and

perform one or more operations for each region of the plurality of regions in the logical address space of the host, including;

determining whether the region has a history of I/O requests to access data of size less than a predefined small-size threshold during a predetermined time period;

determine whether the region has a history of sequential write requests during the predetermined time period; and

coalescing, in accordance with a determination that the region has a history of I/O requests to access data of size less than a predefined small-size threshold during the predetermined time period and that the region has a history of sequential write requests during the predetermined time period, subsequent write requests to the region.

20. A non-transitory computer readable storage medium, storing one or more programs configured for execution by one or more processors of a storage device, the one or more programs including instructions for:

receiving, at a storage device, a plurality of input/output (I/O) requests from a host, the plurality of I/O requests including read requests and write requests to be performed in a plurality of regions in a logical address space of the host; and

performing one or more operations for each region of the plurality of regions in the logical address space of the host, including;

determining whether the region has a history of I/O requests to access data of size less than a predefined small-size threshold during a predetermined time period;

determining whether the region has a history of sequential write requests during the predetermined time period; and

in accordance with a determination that the region has a history of I/O requests to access data of size less than a predefined small-size threshold during the predetermined time period and that the region has a history of sequential write requests during the predetermined time period, coalescing subsequent write requests to the region.

21. The non-transitory computer readable storage medium of claim 20, wherein coalescing subsequent write requests to the region includes:

performing a read ahead operation, to read data from a storage medium of the storage device;

storing read data obtained by the read ahead operation to a cache;

writing one or more subsequent write requests to the cache; and

writing contents of the cache to the storage medium in a merged operation.

22. The non-transitory computer readable storage medium of claim 20, wherein the one or more programs further include instructions for:

for each region of the plurality of regions in the logical address space, setting a flag to denote the determination of whether the region has a history of sequential write requests during the predetermined time period.

23. The non-transitory computer readable storage medium of claim 20, wherein the one or more programs further include instructions for:

for each region of the plurality of regions in the logical address space, storing information in a data structure to maintain a history of I/O request patterns in the region for the predetermined time period.