Using history of unaligned writes to cache data and avoid read-modify-writes in a non-volatile storage device

• US 9,703,491 B2
• Filed: 07/03/2014
• Issued: 07/11/2017
• Est. Priority Date: 05/30/2014
• Status: Active Grant

• Current Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Original Assignee: SanDisk Technologies LLC (Western Digital Corporation)
• Inventors: Mathur, Akshay, Kotte, Dharani, Biswas, Chayan, Kannan, Baskaran
• Primary Examiner(s): Giardino, Jr., Mark
• Assistant Examiner(s): Sain, Gautam
• Application Number:
  US14/323,929
• Publication Number:
  US 20150347030A1
• Time in Patent Office: 1,104 Days
• Field of Search: 711103
• CPC Class Codes: G06F 12/08 in hierarchically structured memory systems, e.g. virtual memory systems
• CPC Class Codes: G06F 12/0871 Allocation or management of cache space
• CPC Class Codes: G06F 2212/214 Solid state disk
• CPC Class Codes: G06F 2212/312 In storage controller
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

Systems, methods and/or devices are used to enable using history of unaligned writes to cache data and avoid read-modify-writes in a non-volatile storage device. In one aspect, the method includes (1) receiving a plurality of input/output (I/O) requests including read requests and write 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 unaligned write requests during a predetermined time period, and (b) if so: (i) determining one or more sub-regions within the region that are accessed more than a predetermined threshold number of times during the predetermined time period, and (ii) caching data from the determined one or more sub-regions.

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, comprising a respective region of the plurality of regions in the logical address space of the host, has a history of unaligned write requests to the region in the logical address space of the host during a predetermined time period, wherein unaligned write requests are write requests not aligned with predefined page boundaries; and

in accordance with a determination that the region has a history of unaligned write requests to the region in the logical address space of the host during the predetermined time period;

determining one or more sub-regions of a plurality of sub-regions within the region that are accessed more than a predetermined threshold number of times during the predetermined time period; and

caching, from a storage medium of the storage device to a cache of the storage device, data from the determined one or more sub-regions.

2. The method of claim 1, wherein, caching data from the determined one or more sub-regions includes:

in response to a subsequent write request to a respective sub-region of the determined one or more sub-regions, caching the respective sub-region.

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 unaligned write requests during the predetermined time period includes:

tracking a total number of unaligned write requests to the region; and

determining whether the total number of unaligned write requests to the region is greater than a first threshold.

4. The method of claim 1, further comprising, with respect to a sub-region of the determined one or more sub-regions, subsequent to caching data from the sub-region:

writing subsequent write requests to the sub-region to the cache;

reading subsequent read requests from the sub-region from the cache; and

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

5. 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 unaligned write requests during the predetermined time period.

6. 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.

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

8. The method of claim 1, wherein the predetermined threshold number is configurable.

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

10. 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.

11. The method of claim 10, 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.

12. 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, comprising a respective region of the plurality of regions in the logical address space of the host, has a history of unaligned write requests to the region in the logical address space of the host during a predetermined time period, wherein unaligned write requests are write requests not aligned with predefined page boundaries; and

in accordance with a determination that the region has a history of unaligned write requests to the region in the logical address space of the host during the predetermined time period;

determining one or more sub-regions of a plurality of sub-regions within the region that are accessed more than a predetermined threshold number of times during the predetermined time period; and

caching, from a storage medium of the storage device to a cache of the storage device, data from the determined one or more sub-regions.

13. The storage device of claim 12, wherein, caching data from the determined one or more sub-regions includes:

in response to a subsequent write request to a respective sub-region of the determined one or more sub-regions, caching the respective sub-region.

14. The storage device of claim 12, wherein, with respect to a region of the plurality of regions, determining whether the region has a history of unaligned write requests during the predetermined time period includes:

tracking a total number of unaligned write requests to the region; and

determining whether the total number of unaligned write requests to the region is greater than a first threshold.

15. The storage device of claim 12, wherein the one or more programs, which when executed by the one or more processors, further cause the storage device to, with respect to a sub-region of the determined one or more sub-regions, subsequent to caching data from the sub-region:

write subsequent write requests to the sub-region to the cache;

read subsequent read requests from the sub-region from the cache; and

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

16. The storage device of claim 12, 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.

17. 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, comprising a respective region of the plurality of regions in the logical address space of the host, has a history of unaligned write requests to the region in the logical address space of the host during a predetermined time period, wherein unaligned write requests are write requests not aligned with predefined page boundaries; and

in accordance with a determination that the region has a history of unaligned write requests to the region in the logical address space of the host during the predetermined time period;

determining one or more sub-regions of a plurality of sub-regions within the region that are accessed more than a predetermined threshold number of times during the predetermined time period; and

caching, from a storage medium of the storage device to a cache of the storage device, data from the determined one or more sub-regions.

18. 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 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

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, comprising a respective region of the plurality of regions in the logical address space of the host, has a history of unaligned write requests to the region in the logical address space of the host during a predetermined time period, wherein unaligned write requests are write requests not aligned with predefined page boundaries; and

in accordance with a determination that the region has a history of unaligned write requests to the region in the logical address space of the host during the predetermined time period;

determining one or more sub-regions of a plurality of sub-regions within the region that are accessed more than a predetermined threshold number of times during the predetermined time period; and

caching, from a storage medium of the storage device to a cache of the storage device, data from the determined one or more sub-regions.

19. The non-transitory computer readable storage medium of claim 18, wherein, caching data from the determined one or more sub-regions includes:

in response to a subsequent write request to a respective sub-region of the determined one or more sub-regions, caching the respective sub-region.

20. The non-transitory computer readable storage medium of claim 18, wherein, with respect to a region of the plurality of regions, determining whether the region has a history of unaligned write requests during the predetermined time period includes:

tracking a total number of unaligned write requests to the region; and

determining whether the total number of unaligned write requests to the region is greater than a first threshold.

21. The non-transitory computer readable storage medium of claim 18, wherein the one or more programs further include instructions for, with respect to a sub-region of the determined one or more sub-regions, subsequent to caching data from the sub-region:

writing subsequent write requests to the sub-region to the cache;

reading subsequent read requests from the sub-region from the cache; and

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

22. The non-transitory computer readable storage medium of claim 18, 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.