Specializing I/O access patterns for flash storage

Patent metadata

Field	Value
Publication number	US-9645917-B2
Application number	US-201213477966-A
Country	US
Kind code	B2
Filing date	May 22, 2012
Priority date	May 22, 2012
Publication date	May 9, 2017
Grant date	May 9, 2017

Abstract

Systems and methods for efficiently using solid-state devices are provided. Some embodiments provide for a data processing system that uses a non-volatile solid-state device as a circular log, with the goal of aligning data access patterns to the underlying, hidden device implementation, in order to maximize performance. In addition, metadata can be interspersed with data in order to align data access patterns to the underlying device implementation. Multiple input/output (I/O) buffers can also be used to pipeline insertions of metadata and data into a linear log. The observed queuing behavior of the multiple I/O buffers can be used to determine when the utilization of the storage device is approaching saturation (e.g., in order to predict excessively-long response times). Then, the I/O load on the storage device may be shed when utilization approaches saturation. As a result, the overall response time of the system is improved.

First claim

What is claimed is:

1. A method comprising:
maintaining a circular log on a non-volatile solid-state storage device as a cache for data from a secondary storage device;
monitoring a depth of a write queue in a memory to estimate a utilization of the non-volatile solid-state storage device having sectors with a size corresponding to an integral multiple of a size of an erase block of the non-volatile solid-state storage device, wherein the non-volatile solid-state storage device erases data in units of the erase block;
determining if the estimate of utilization exceeds a first utilization threshold;
in response to determining that the estimate of utilization exceeds the first utilization threshold, shedding a write request within the write queue to the secondary storage device;
determining if the estimate of utilization exceeds a second utilization threshold; and
in response to determining that the estimate of utilization exceeds the second utilization threshold, shedding a non-essential read from the non-volatile solid-state storage device to the secondary storage device.

2. The method of claim 1 , wherein the shed write request to the secondary storage device includes a non-essential write resulting from one of a read-miss in the cache and a write to the cache when a current copy of the data exists in the secondary storage device.

3. The method of claim 1 , wherein the first utilization threshold and the second utilization threshold are adaptively set.

4. The method of claim 1 , where the non-essential read includes a flash read to satisfy a cache read-hit.

5. A method comprising:
maintaining a circular log on a non-volatile solid-state storage device as a cache for data from a secondary storage device;
monitoring a depth of a write queue in a memory to estimate a utilization of the non-volatile solid-state storage device with sectors having a size corresponding to an integral multiple of a size of an erase block of the non-volatile solid-state storage device, wherein the non-volatile solid-state storage device erases data in units of the erase block;
determining if the estimate of utilization exceeds a utilization threshold; and
in response to determining that the estimate of utilization exceeds the utilization threshold, shedding a write request having the data within the write queue to the secondary storage device, wherein the shed write request includes a non-essential write resulting from one of a read-miss in the cache and a write to the cache when a current copy of the data exists in the secondary storage device.

6. The method of claim 5 , further comprising:
estimating a first expected response time for accessing the non-volatile solid-state storage device;
estimating a second expected response time for accessing the secondary storage device; and
accessing the secondary storage device to satisfy a read request, when the second expected response time is less than the first expected response time.

7. The method of claim 6 wherein estimating the first expected response time further comprises:
computing a mean service time from a measured mean of the depth of the write queue and a measured mean response time of the write queue.

8. The method of claim 6 wherein estimating the first expected response time further comprises:
computing an expected instantaneous response time from a mean service time and an instantaneous depth of the write queue.

9. The method of claim 5 , further comprising:
storing the data in the write queue until the write queue contains a write unit worth of data; and
writing, from the write queue to the non-volatile solid-state storage device, the write unit worth of data.

10. The method of claim 9 , wherein shedding the write request having the data further comprises interspersing metadata regarding the data within the data written to the write unit.

11. The method of claim 9 , further comprising:
estimating the size of the erase block of the non-volatile solid-state storage device; and
setting a size of the write unit to be an integral multiple of the estimate of the erase block size.

12. A processing system comprising:
a processor;
a memory coupled to the processor;
a secondary storage device coupled to the processor;
a non-volatile solid-state storage device coupled to the processor, the non-volatile solid-state storage device including sectors having a size corresponding to an integral multiple of a size of an erase block of the non-volatile solid-state storage device, wherein the non-volatile solid-state storage device erases data in units of the erase block; and
a process executing on the processor operable to:
maintain a circular log on the non-volatile solid state storage device as a cache for data from the secondary storage device;
monitor a depth of a write queue in the memory to estimate a utilization of the non-volatile solid-state storage device;
determine if the estimate of utilization exceeds a utilization threshold; and
in response to determining that the estimate of utilization exceeds the utilization threshold, shed a write request associated with the data within the write queue to the secondary storage device, wherein the shed write request includes a non-essential write resulting from one of a read-miss in the cache and a write to the cache when a current copy of the data exists in the secondary storage device.

13. The processing system of claim 12 , wherein in an event that a write operation reaches an end of a sector range of the circular log of the non-volatile solid-state storage device, continuing the write operation at a beginning of the sector range of the circular log.

14. The processing system of claim 12 , further comprising:
a log cleaning process executing on the processor operable to employ a page replacement policy to evict an old data entry of the cache to make space for the data associated with the shed write request.

15. The processing system of claim 14 , wherein the process is further operable to:
automatically read the old data entry from the cache to the memory before the old data entry is needed for processing when the page replacement policy saves a subset of the old data entry.

16. The processing system of claim 15 , wherein the read of the old data entry from the cache is avoided when the page replacement policy does not save the old data entry.

17. The processing system of claim 12 , wherein the non-volatile solid-state storage device includes flash transition layer to map client page addresses to internal page addresses.

18. The processing system of claim 12 , wherein the non-volatile solid-state storage device is a NAND flash storage device.

19. A system comprising:
a processor;
a memory coupled to the processor;
a secondary storage device coupled to the processor;
a non-volatile solid-state storage device coupled to the processor, the non-volatile solid-state storage device including sectors having a size corresponding to an integral multiple of a size of an erase block of the non-volatile solid-state storage device, wherein the non-volatile solid-state storage device erases data in units of the erase block; and
a process executing on the processor operable to:
maintain a circular log on the non-volatile solid state storage device as a cache having data entries for storing data from the secondary storage device;
monitor a depth of a write queue in the memory to estimate a utilization of the non-volatile solid-state storage device;
determine if the estimate of utilization exceeds a utilization threshold; and

Assignees

• Small Christopher
• Byan Stephen M
• Lentini James F
• Netapp Inc

Inventors

• Small Christopher
• Byan Stephen M
• Lentini James F

Classifications

• G06F12/0866 Primary

  for peripheral storage systems, e.g. disk cache · CPC title

• G06F12/0246 Primary

  in block erasable memory, e.g. flash memory · CPC title

• G06F2212/7203

  Temporary buffering, e.g. using volatile buffer or dedicated buffer blocks · CPC title

• G06F12/0802 Primary

  Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches · CPC title

• G06F2212/222

  Non-volatile memory · CPC title