Using sub-region I/O history to cache repeatedly accessed sub-regions in a non-volatile storage device

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:
• for each sub-region of a plurality of sub-regions of the region in the logical address space of the host, wherein each sub-region includes two or more pages and two or more logical block addresses (LBAs):
• determining, and storing in a data structure in the storage device, a total number of times the sub-region in the logical address space of the host is accessed during a predetermined time period;
• in accordance with the determined total number of times the sub-region is accessed, determining whether the sub-region in the logical address space of the host is accessed more than a predetermined threshold number of times during the predetermined time period;
• and
• in accordance with the determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.

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:
• for each sub-region of a plurality of sub-regions of the region in the logical address space of the host, wherein each sub-region includes two or more pages and two or more logical block addresses (LBAs):
• determining, and storing in a data structure in the storage device, a total number of times the sub-region in the logical address space of the host is accessed during a predetermined time period;
• in accordance with the determined total number of times the sub-region is accessed, determining whether the sub-region in the logical address space of the host is accessed more than a predetermined threshold number of times during the predetermined time period;
• and
• in accordance with the determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.

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:
• for each sub-region of a plurality of sub-regions of the region in the logical address space of the host, wherein each sub-region includes two or more pages and two or more logical block addresses (LBAs):
• determining, and storing in a data structure in the storage device, a total number of times the sub-region in the logical address space of the host is accessed during a predetermined time period;
• in accordance with the determined total number of times the sub-region is accessed, determining whether the sub-region in the logical address space of the host is accessed more than a predetermined threshold number of times during the predetermined time period;
• and
• in accordance with a determination that the sub-region in the logical address space of the host is accessed more than the predetermined threshold number of times in the predetermined time period, caching, from a storage medium of the storage device to a cache of the storage device, data from the sub-region.