Specializing i/o access patterns for flash storage

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.

What is claimed is: 
     
         1 . A method comprising:
 maintaining a cache on a non-volatile solid-state storage device for data from a secondary storage device, wherein the data is written to the cache in integral multiples of an erase block size of the non-volatile solid-state storage device;   monitoring a depth of a write queue in a memory to estimate a utilization of the non-volatile solid-state storage device;   determining whether the estimate of utilization exceeds a first utilization threshold; and   in response to determining that the estimate of utilization exceeds the first 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.   
     
     
         2 . The method  claim 1  further comprising:
 in response to determining that the estimate of utilization does not exceed the first utilization threshold, determining whether the estimate of utilization exceeds a second threshold; and 
 in response to determining that the estimate of utilization exceeds the second utilization threshold, shedding a non-essential read request to the secondary storage device, wherein the shed non-essential read request includes a read request to satisfy a cache read-hit when a current copy of the data exists in the secondary storage device. 
 
     
     
         3 . The method of  claim 1  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 non-essential input/output (I/O) request when the estimated second expected response time is less than the estimated first expected response time, wherein the non-essential I/O request is selected from one of a read-miss in the cache, a write to the cache when a current copy of the data exists in the secondary storage device, and a read request to satisfy a cache read-hit when a current copy of the data exists in the secondary storage device. 
 
     
     
         4 . The method of  claim 3  wherein estimating the first expected response time of the non-volatile solid-state storage device further comprises:
 inferring a number of write operations in progress by subtracting a current number of free buffers within a buffer pool in the memory from a size of the buffer pool. 
 
     
     
         5 . The method of  claim 3  wherein estimating the first expected response time further comprises determining an expected instantaneous response time of a current write request in the write queue as a multiplication of a mean service time of the write queue by an instantaneous queue depth. 
     
     
         6 . The method of  claim 5  wherein the mean service time of the write queue is determined based on a mean service time of the current request as a ratio of a measured mean response time of the write queue to a measured mean depth of the write queue. 
     
     
         7 . The method of  claim 1  further comprising:
 determining an expected response time of the non-volatile solid-state storage device; and 
 in response to determining that the expected response time of the non-volatile solid-state storage device approaches an expected response time of the secondary storage device, bypassing the cache when the write request inserts new data into the cache. 
 
     
     
         8 . The method of  claim 7  wherein read requests are serviced from the cache. 
     
     
         9 . The method of  claim 7  further comprising:
 in response to determining that the expected response time of the non-volatile solid-state storage device exceeds the expected response time of the secondary storage device, bypassing the cache to service a read request from the secondary storage device. 
 
     
     
         10 . 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; and   a process executing on the processor and configured to:
 maintain a cache on the non-volatile solid-state storage device for data from the secondary storage device, wherein the data is written to the cache in integral multiples of an erase block size of the non-volatile solid-state 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 whether the estimate of utilization exceeds a first utilization threshold; and 
 in response to determining that the estimate of utilization exceeds the first utilization threshold, shed 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. 
   
     
     
         11 . The system of  claim 10  wherein the process executing on the processor is further configured to:
 in response to determining that the estimate of utilization does not exceed the first utilization threshold, determine whether the estimate of utilization exceeds a second threshold; and 
 in response to determining that the estimate of utilization exceeds the second utilization threshold, shed a non-essential read request to the secondary storage device, wherein the shed non-essential read request includes a read request to satisfy a cache read-hit when a current copy of the data exists in the secondary storage device. 
 
     
     
         12 . The system of  claim 10  wherein the process executing on the processor is further configured to:
 estimate a first expected response time for accessing the non-volatile solid-state storage device; 
 estimate a second expected response time for accessing the secondary storage device; and 
 access the secondary storage device to satisfy a non-essential input/output (I/O) request when the estimated second expected response time is less than the estimated first expected response time, wherein the non-essential I/O request is selected from one of a read-miss in the cache, a write to the cache when a current copy of the data exists in the secondary storage device, and a read request to satisfy a cache read-hit when a current copy of the data exists in the secondary storage device. 
 
     
     
         13 . The system of  claim 12  wherein the process executing on the processor configured to estimate the first expected response time of the non-volatile solid-state storage device is further configured to:
 infer a number of write operations in progress by subtracting a current number of free buffers within a buffer pool in the memory from a size of the buffer pool. 
 
     
     
         14 . The system of  claim 12  wherein the process executing on the processor configured to estimate the first expected response time is further configured to determine an expected instantaneous response time of a current write request in the write queue as a multiplication of a mean service time of the write queue by an instantaneous queue depth. 
     
     
         15 . The system of  claim 14  wherein the mean service time of the write queue is determined based on a mean service time of the current request as a ratio of a measured mean response time of the write queue to a measured mean depth of the write queue. 
     
     
         16 . The system of  claim 10  wherein the process executing on the processor is further configured to:
 determine an expected response time of the non-volatile solid-state storage device; and 
 in response to determining that the expected response time of the non-volatile solid-state storage device approaches an expected response time of the secondary storage device, bypass the cache when the write request inserts new data into the cache. 
 
     
     
         17 . The system of  claim 16  wherein read requests are serviced from the cache. 
     
     
         18 . The system of  claim 16  wherein the process executing on the processor is further configured to:
 in response to determining that the expected response time of the non-volatile solid-state storage device exceeds the expected response time of the secondary storage device, bypass the cache to service a read request from the secondary storage device. 
 
     
     
         19 . The system of  claim 10  wherein the process executing on the processor configured to maintain the cache on the non-volatile solid-state storage device is further configured to:
 write data to the cache as a circular log having entries aligned with erase blocks of the non-volatile solid-state storage device. 
 
     
     
         20 . A non-transitory computer readable medium having stored thereon program instructions for execution on a processor, the program instructions configured to:
 maintain a cache on a non-volatile solid-state storage device coupled to the processor for data from a secondary storage device coupled to the processor, wherein the data is written to the cache in integral multiples of an erase block size of the non-volatile solid-state storage device;   monitor a depth of a write queue in a memory coupled to the processor to estimate a utilization of the non-volatile solid-state storage device;   determine whether the estimate of utilization exceeds a first utilization threshold; and   in response to determining that the estimate of utilization exceeds the first utilization threshold, shed 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.