Systems and methods for adaptive reserve storage

A storage layer may over-provision physical storage resources of a storage medium by reserving a portion of the full physical storage capacity of the storage medium for use as reserve capacity. The reserve capacity may be used to prevent write stall conditions and/or for grooming operations, such as storage recovery, refresh, and the like. A reserve module may be configured to adapt the reserve capacity in accordance with, inter alia, operating conditions on the storage layer. The reserve module may be configured to dynamically modify the storage capacity available through the storage layer. A cache layer configured to cache data of a backing store on the storage layer, may be configured to add and/or remove cache entries in response to changes in the reserve capacity.

TECHNICAL FIELD

This disclosure relates to storage systems and, in particular, to systems and methods for managing reserve storage capacity of a non-volatile storage device.

SUMMARY

Disclosed herein are embodiments of a method for adaptive reserve storage. The disclosed method may comprise providing access to storage space of a storage device allocated to a cache, wherein the allocated storage space is less than a total storage space of the storage device, and modifying the storage space allocated to the cache based on a determined write load for the cache, by one or more of, increasing the storage space allocated to the cache in response to a decrease in the determined write load for by the cache, and/or decreasing the storage space allocated to the cache in response to an increase in the determined write load for the cache.

The method may further comprise determining the write load for the cache based on one or more of a number of storage divisions in a write queue, a rate of storage recovery operations performed on the storage device, write operations performed on the storage device per unit time, a rate of write operations performed on the storage device in response to cache misses, a rate of write operations performed on the storage device in response to write operations pertaining to data in the cache, and a ratio of write operations to read operations performed in the storage space allocated to the cache. The disclosed method may further include using the reserved storage space to relocate data within the storage device. Alternatively, or in addition, the reserve storage may be used one or more of grooming operations, storage division recovery operations, data relocation operations, and available write capacity.

In some embodiments, a portion of the total storage space of the storage device is designated as reserve storage space of the storage device, such that increasing the storage space allocated to the cache comprises decreasing the reserve storage space, and decreasing the storage space allocated to the cache comprises increasing the reserve storage space. Decreasing the storage space allocated to the cache comprises evicting data from the cache. Evicting the data from the cache may comprise deallocating the data in the storage device. Alternatively, or in addition, decreasing the storage space allocated to the cache comprises removing one or more entries from the cache.

Disclosed herein are embodiments of an apparatus for adaptive reserve storage. The disclosed apparatus may comprise a storage layer of a storage medium, wherein a portion of a storage capacity of the storage medium is provisioned as reserve storage capacity and another portion is provisioned as available storage capacity, wherein the available storage capacity is less than an accessible physical storage capacity of the storage medium, a monitoring module configured to monitor storage operations performed on the storage medium, and a reserve module configured to modify a size of the reserve storage capacity in response to the monitored storage operations.

The monitoring module may be configured to determine an operating profile of the storage medium based on the monitored storage operations, and wherein the operating profile comprises one or more of a rate of write operations performed on the storage medium, a ratio of write operations to read operations performed on the storage medium, write capacity availability, and write stall conditions.

The reserve module may be configured to modify the size of the reserve storage capacity in response to determining an optimal size of the reserve storage capacity based on one or more of a quality of service policy and a optimization criterion. In some embodiments, the reserve module is be configured to expand the reserve storage capacity in response to the operating profile indicating increased write loads on the storage medium, wherein expanding the reserve storage capacity comprises contracting the available storage capacity. The reserve module may be configured to reduce the reserve storage capacity in response to the monitored storage operations indicating high write capacity availability on the storage medium.

In some embodiments, the apparatus may include a groomer module configured to re-initialize storage divisions of the storage medium to a writeable state and to maintain a write queue identifying writeable storage divisions of the storage medium. The apparatus may further comprise an allocation module of a cache, which may be configured to reallocate cache tags of the cache in response to modifications to a size of the available storage capacity. In response to a reduction in the size of the available storage capacity, the allocation module may be configured to a) evict data from the cache, and/or b) deallocate one or more cache tags corresponding to the evicted data.

Disclosed herein are further embodiments of operations for adaptive reserve storage. The operations may include performing storage operations on a solid-state storage medium having a usable storage capacity, wherein a portion of the usable storage capacity is designated as reserve capacity, and another portion of the useable storage capacity is available for use to store data of a client, determining a write workload for the solid-state storage medium in response to the storage operations performed on the solid-state storage medium, and/or modifying a size of the reserve capacity based on the determined write workload, wherein modifying the size of the reserve capacity comprises modifying a size of the portion of usable storage capacity that is available to store data of the client.

In some embodiments, the disclosed operations further comprise developing a write capacity profile in response to the storage operations performed on the solid-state storage medium, wherein developing the write capacity profile comprises monitoring one or more of a size of a write queue of the solid-state storage medium, a rate of write operations performed on the solid-state storage medium, a ratio of write operations to read operations performed on the storage medium, and storage recovery operations performed on the solid-state storage medium.

The client may comprise a cache layer, and wherein the cache layer is configured to modify a capacity of the cache in response to modifying the size of the reserve capacity. The operations may further include informing the cache layer of the modification to the size of the portion of usable storage capacity that is available to store data of the client.

DETAILED DESCRIPTION

FIG. 1Ais a block diagram of one embodiment of a computing system100comprising a storage layer130configured to provide I/O and/or storage services to one or more I/O clients106. The computing system100may comprise any computing device, including, but not limited to, a server, desktop, laptop, embedded system, mobile device, and/or the like. In some embodiments, the computing system100may include multiple computing devices, such as a cluster of server computing devices. The computing system100may comprise processing resources101, volatile memory resources102(e.g., random access memory (RAM)), non-volatile storage resources103, and a communication interface105. The processing resources101may include, but are not limited to, general purpose central processing units (CPUs), application-specific integrated circuits (ASICs), and programmable logic elements, such as field programmable gate arrays (FPGAs), programmable logic arrays (PLGs), and the like. The non-volatile storage resources103may comprise a non-transitory machine-readable storage medium, such as a magnetic hard disk, solid-state storage medium, optical storage medium, and/or the like. The communication interface105may be configured to communicatively couple the computing system100to a network115. The network115may comprise any suitable communication network, including, but not limited to, a Transmission Control Protocol/Internet Protocol (TCP/IP) net work, a Local Area Network (LAN), a Wide Area Network (WAN), a Virtual Private Network (VPN), a Storage Area Network (SAN), a Public Switched Telephone Network (PSTN), the Internet, and/or the like.

The I/O clients106may include, but are not limited to, operating systems (including bare metal operating systems, guest operating systems, virtual machines, and the like), virtualization systems (virtualization kernels, hypervisors, virtual machines, and/or the like), file systems, database systems, remote I/O clients (e.g., I/O clients106communicatively coupled to the computing system100and/or storage layer130through the network115), and/or the like.

The storage layer130(and/or modules thereof) may be implemented in software, hardware, or a combination thereof. In some embodiments, portions of the storage layer130are embodied as executable instructions, such as computer program code, which may be stored on a persistent, non-transitory storage medium, such as the non-volatile storage resources103, storage medium140, firmware, and/or the like. The instructions and/or computer program code may be configured for execution by the processing resources101of the computing system100and/or processing resources of other components and/or modules, such as the storage controller139. Alternatively, or in addition, portions of the storage layer130and/or other modules disclosed herein may be embodied as machine components, such as general and/or application-specific components, programmable hardware, FPGAs, ASICs, hardware controllers, storage controllers, and/or the like.

The storage layer130may be configured to perform storage operations on the storage medium140. The storage medium140may comprise any storage medium capable of storing data persistently. As used herein, “persistent” data storage refers to storing information on a persistent, non-volatile storage medium. The storage medium140may include non-volatile storage media, such as solid-state storage media in one or more solid-state storage devices or drives (SSD), hard disk drives (e.g., Integrated Drive Electronics (IDE) drives, Small Computer System Interface (SCSI) drives, Serial Attached SCSI (SAS) drives, Serial AT Attachment (SATA) drives, etc.), tape drives, writeable optical drives (e.g., CD drives, DVD drives, Blu-ray drives, etc.), and/or the like.

In some embodiments, the storage medium140comprises non-volatile, solid-state memory, which may include, but is not limited to, NAND flash memory, NOR flash memory, nano RAM (NRAM), magneto-resistive RAM (MRAM), phase change RAM (PRAM), Racetrack memory, Memristor memory, nanocrystal wire-based memory, silicon-oxide based sub-10 nanometer process memory, graphene memory, Silicon-Oxide-Nitride-Oxide-Silicon (SONOS), resistive random-access memory (RRAM), programmable metallization cell (PMC), conductive-bridging RAM (CBRAM), and/or the like. Although particular embodiments of the storage medium140are disclosed herein, the teachings of this disclosure could be applied to any suitable form of memory, including both non-volatile and volatile forms. Accordingly, although particular embodiments of the storage layer130are disclosed in the context of non-volatile, solid-state storage devices, the storage layer130may be used with other storage devices and/or storage media.

In some embodiments, the storage medium140includes volatile memory, which may include, but is not limited to, RAM, dynamic RAM (DRAM), static RAM (SRAM), synchronous dynamic RAM (SDRAM), etc. The storage medium140may correspond to the memory of the processing resources101, such as a CPU cache (e.g., L1, L2, L3 cache, etc.), graphics memory, and/or the like. In some embodiments, the storage medium140is communicatively coupled to the storage layer130by use of an interconnect127. The interconnect127may include, but is not limited to, peripheral component interconnect (PCI), PCI express (PCI-e), serial advanced technology attachment (serial ATA or SATA), parallel ATA (PATA), small computer system interface (SCSI), IEEE 1394 (FireWire), Fiber Channel, universal serial bus (USB), and/or the like. Alternatively, the storage medium140may be a remote storage device that is communicatively coupled to the storage layer130through the network115(and/or other communication interface, such as a Storage Area Network (SAN), a Virtual Storage Area Network (VSAN), and/or the like). The interconnect127may, therefore, comprise a remote bus, such as a PCE-e bus, a network connection (e.g., Infiniband), a storage network, Fibre Channel Protocol (FCP) network, HyperSCSI, and/or the like.

The storage layer130may be configured to manage storage operations on the storage medium140by use of inter alia, the storage controller139. The storage controller139may comprise software and/or hardware components, including, but not limited to, one or more drivers and/or other software modules operating on the computing system100, such as storage drivers, I/O drivers, filter drivers, and/or the like; hardware components, such as hardware controllers, communication interfaces, and/or the like; and so on. The storage medium140may be embodied on a storage device141. Portions of the storage layer130(e.g., storage controller139) may be implemented as hardware and/or software components (e.g. firmware) of the storage device141.

The storage controller139may be configured to implement storage operations at particular storage locations of the storage medium140. As used herein, a storage location refers to a unit of storage of a storage resource (e.g., a storage medium and/or device) that is capable of storing data persistently; storage locations may include, but are not limited to, pages, groups of pages (e.g., logical pages and/or offsets within a logical page), storage divisions (e.g., physical erase blocks, logical erase blocks, etc.), sectors, locations on a magnetic disk, battery-backed memory locations, and/or the like. The storage locations may be addressable within a storage address space144of the storage medium140. Storage addresses may correspond to physical addresses, media addresses, back-end addresses, address offsets, and/or the like. Storage addresses may correspond to any suitable storage address space144, storage addressing scheme, and/or arrangement of storage locations.

The storage layer130may comprise an interface131through which I/O clients106may access storage services provided by the storage layer130. The storage interface131may include one or more of a block device interface, an object storage interface, a file storage interface, a key-value storage interface, a virtualized storage interface, one or more virtual storage units (VSUs), an object storage interface, a database storage interface, and/or other suitable interfaces and/or an Application Programming Interface (API), and the like.

The storage layer130may provide for referencing storage resources through a front-end storage interface. As used herein, a “front-end storage interface” refers to an interface and/or namespace through which I/O clients106may refer to storage resources of the storage layer130. A storage interface may correspond to a logical address space132. The logical address space132may comprise a group, set, collection, range, and/or extent of identifiers. As used herein, an “identifier” or “logical identifier” (LID) refers to an identifier for referencing an I/O resource; LIDS may include, but are not limited to, names (e.g., file names, distinguished names, and/or the like), data identifiers, references, links, front-end identifiers, logical addresses, logical block addresses (LBAs), storage unit addresses, virtual storage unit (VSU) addresses, logical unit number (LUN) addresses, virtual unit number (VUN) addresses, virtual logical unit number (VLUN) addresses, virtual storage addresses, storage addresses, physical addresses, media addresses, back-end addresses, unique identifiers, globally unique identifiers (GUIDs), and/or the like.

The logical capacity of the logical address space132may correspond to the number of LIDs in the logical address space132and/or the size and/or granularity of the storage resources referenced by the LIDs. In some embodiments, the logical address space132may be “thinly provisioned.” As used herein, a thinly provisioned logical address space132refers to a logical address space132having a logical capacity that exceeds the physical storage capacity of the underlying storage resources (e.g., exceeds the storage capacity of the storage medium140). In one embodiment, the storage layer130is configured to provide a 64-bit logical address space132(e.g., a logical address space comprising 2^26 unique LiDs), which may exceed the physical storage capacity of the storage medium140. The storage layer130may leverage the large, thinly provisioned logical address space132to efficiently allocate and/or reference contiguous ranges of LIDs for the I/O clients106, while reducing the chance of naming conflicts.

The translation module133of the storage layer130may be configured to map LIDs of the logical address space132to storage resources (e.g., data stored within the storage address space144of the storage medium140). The logical address space132may be independent of the back-end storage resources (e.g., the storage medium140); accordingly, there may be no set or pre-determined mappings between LIDs of the logical address space132and the storage addresses of the storage address space144. In some embodiments, the logical address space132is sparse, thinly provisioned, and/or over-provisioned, such that the size of the logical address space132differs from the storage address space144of the storage medium140.

The storage layer130may be configured to maintain storage metadata131pertaining to storage operations performed on the storage medium140. The storage metadata134may include, but is not limited to, a forward map comprising any-to-any mappings between LIDs of the logical address space132and storage addresses within the storage address space144, a reverse map pertaining to the contents of storage locations of the storage medium140, validity bitmaps, reliability testing and/or status metadata, status information e.g., error rate, retirement status, and so on), cache metadata, and/or the like. Portions of the storage metadata134may be maintained within the volatile memory resources102of the computing system100. Alternatively, or in addition, portions of the storage metadata134may be stored on non-volatile storage resources103and/or the storage medium140.

FIG. 1Bdepicts one embodiment of any-to-any mappings between LIDs of the logical address space132and back-end identifiers (e.g., storage addresses) within the storage address space144. The any-to-any mappings may be maintained in one or more data structures of the storage metadata134. As illustrated inFIG. 1B, the translation module133may be configured to map any storage resource identifier (any LID of the logical address space132) to any back-end storage location. As further illustrated, the logical address space132may be sized differently than the underlying storage address space144. In theFIG. 1Bembodiment, the logical address space132may be thinly provisioned, and, as such, may comprise a larger range of LIDs than the range of storage addresses in the storage address space144.

As disclosed above, I/O clients106may reference storage resources of the storage layer130by use of, inter alia, LIDs of the logical address space132. Accordingly, the logical address space132may correspond to a logical or front-end interface of the storage resources, and the mappings to particular storage addresses within the storage address space144may correspond to a back-end interface of the storage resources.

The storage layer130may be configured to maintain the any-to-any mappings between the logical interface and back-end interface in a forward map160(FIG. 1B). The forward map160may comprise any suitable data structure, including, but not limited to, an index, a map, a hash map, a hash table, a tree, a range-encoded tree, a b-tree, and/or the like. The forward map160may comprise entries162corresponding to LiDs that have been allocated for use to reference data stored on the storage medium140. The entries162of the forward map160may associate LIDs164A-D with respective storage addresses166A-D within the storage address space144. The forward map160may be sparsely populated and, as such, may omit entries corresponding to LIDs that are not currently allocated to I/O clients106and/or are not currently in use to reference valid data stored on the storage medium140. In some embodiments, the forward map160comprises a range-encoded data structure, such that one or more of the entries162correspond to a plurality of LIDs (e.g., a range, extent, and/or set of LIDs). In theFIG. 1Bembodiment, the forward map160includes an entry162corresponding to a range of LIDs164A (LID range34of length 4, comprising LIDs34-37) mapped to a corresponding range of storage addresses166A (16987-16990). The entries162of the forward map160may be indexed by LID in, inter alia, a tree data structure. The disclosure is not limited in his regard, however, and could be adapted to use any suitable data structure and/or indexing mechanism.

Referring toFIG. 1C, in some embodiments, the storage medium140may comprise a solid-state storage array145comprising a plurality of solid-state storage elements146A-Y. As used herein, a solid-state storage array (or array)145refers to a set of two or more independent columns148. A column148may comprise one or more solid-state storage elements146A-Y that are communicatively coupled to the storage layer130in parallel using, inter cilia, the interconnect127. Rows147of the array145may comprise physical storage units of the respective columns148(solid-state storage elements146A-Y). As used herein, a solid-state storage element146A-Y includes, but is not limited to, solid-state storage resources embodied as a package, chip, die, plane, printed circuit board, and/or the like. The solid-state storage elements146A-Y comprising the array145may be capable of independent operation. Accordingly, a first one of the solid-state storage elements146A may be capable of performing a first storage operation while a second solid-state storage element146B performs a different storage operation. For example, the solid-state storage element146A may be configured to read data at a first physical address, while another solid-state storage element146B reads data at a different physical address.

A solid-state storage array145may also be referred to as a logical storage element (LSE). As disclosed in further detail herein, the solid-state storage array145may comprise logical storage units (rows147). As used herein, a “logical storage unit” or row147refers to a combination of two or more physical storage units, each physical storage unit on a respective column148of the array145. A logical erase block refers to a set of two or more physical erase blocks, a logical page refers to a set of two or more pages, and so on. In some embodiments, a logical erase block may comprise erase blocks within respective logical storage elements146A-Y and/or banks. Alternatively, a logical erase block may comprise erase blocks within a plurality of different arrays145and/or may span multiple banks of solid-state storage elements.

FIG. 1Ddepicts one embodiment of storage medium140comprising a plurality of independent banks149A-N, each comprising one or more solid-state storage arrays145A-N. Each of the independent banks149A-N may be communicatively coupled to the storage controller139via a respective interconnect127A-N. The storage layer130may be configured to store data on respective banks149A-N of the storage medium140. Further embodiments of systems and methods for arranging data for storage on solid-state storage arrays145A-N and/or banks149A-N of solid-state storage arrays145A-N are disclosed in U.S. patent application Ser. No. 13/784,705, entitled “Systems and Methods for Adaptive Storage,” filed Mar. 4, 2013, for David Flynn et al, which is hereby incorporated by reference in its entirety.

Referring back toFIG. 1A, the storage layer130may further comprise a log storage module135configured to store data on the storage medium140in a log structured storage configuration (e.g., in a storage log). As used herein, a “storage log” or “log structure” refers to an ordered arrangement of data within the storage address space144of the storage medium140. Data in the storage log may comprise and/or be associated with persistent metadata. Accordingly, the storage layer130may be configured to store data in a contextual, self-describing format. As used herein, a contextual or self-describing format refers to a data format in which data is stored in association with persistent metadata. In some embodiments, the persistent metadata may be configured to identify the data and, as such, may comprise and/or reference the logical interface of the data (e.g., may comprise the LID(s) associated with the data). The persistent metadata may include other information, including, but not limited to, information pertaining to the owner of the data, access controls, data type, relative position or offset of the data, information pertaining to storage operation(s) associated with the data (e.g., atomic storage operations, transactions, and/or the like), log sequence information, data storage parameters (e.g., compression algorithm, encryption, etc.), and/or the like.

FIG. 1Eillustrates one embodiment of a contextual data format. The data packet format110ofFIG. 1Ecomprises a data segment112and persistent metadata114. The data segment112may be of any arbitrary length and/or size. The persistent metadata114may be embodied as one or more header fields of the data packet110. The persistent metadata114may be configured to define the logical interface of the data segment112and, as such, may include and/or reference the LID(s) associated with the data segment112. AlthoughFIG. 1Edepicts packet format110, the disclosure is not limited in this regard and could associate data (e.g., data segment112) with persistent, contextual metadata in other ways, including, but not limited to, an index on the storage medium140, a storage division index, a separate metadata channel, and/or the like.

In some embodiments, the log storage module135is further configured to associate data packets110with sequence information113. The sequence information113may be used to determine the relative order of the data packets110stored on the storage medium140. In some embodiments, the log storage module135and/or storage controller139are configured to assign sequence information113to sections of the storage medium140. The sections may correspond to storage divisions, erase blocks, logical erase blocks, and/or the like. Each section may be capable of storing a plurality of data packets110. The log storage module135may be configured to append data packets110sequentially within the physical address space of the respective sections of the storage medium140(by use of the storage controller139). The relative position of data packets110within a section may determine the relative order of the data packets110within the section. The order of the sections of the storage medium140may be determined by use of, inter alia, sequence information113of the sections. The sequence information113may be assigned to respective sections of the storage medium140when the sections are initialized for use (e.g., erased), programmed, closed, and/or the like, such that the sequence information113defines an ordered sequence of sections within the storage address space144. Accordingly, the order of a data packet110within the storage log may be determined by: a) the relative position of the data packet110within a particular storage division and b) the order of the storage division relative to other storage divisions in the storage address space144.

In some embodiments, the storage layer130may be configured to manage an asymmetric, write-once storage medium140, such as a solid-state storage medium, flash storage medium, or the like. As used herein, a “write-once” storage medium refers to a storage medium that can only be reliably programmed once, and/or must be reinitialized (e.g., erased) each time new data is written or programmed thereon. A write-once storage medium may, therefore, comprise a “writeable,” “initialized,” or “erased” state in which the storage medium is capable of having data programmed thereon, and a “written state” in which the storage medium has had data programmed thereon and, as such, must be erased before being used to store new data. As used herein, an “asymmetric” storage medium refers to a storage medium that has different latencies for different types of storage operations. In some embodiments, for example, read operations may be faster than write/program operations, and write/program operations may be much faster than erase operations (e.g., reading the media may be hundreds of times faster than erasing, and tens of times faster than programming the storage medium). The storage medium140may be partitioned into storage divisions that can be erased as a group (e.g., erase blocks). As such, modifying a single data segment “in-place” may require erasing the entire erase block comprising the data and rewriting the modified data to the erase block, along with the original, unchanged data. This may result in inefficient “write amplification,” which may excessively wear the media. In some embodiments, therefore, the storage layer130may be configured to write data “out-of-place.” As used herein, writing data “out-of-place” refers to updating and/or overwriting data at different storage location(s) rather than overwriting the data “in-place” (e.g., overwriting the original physical storage location of the data). Updating and/or overwriting data out-of-place may avoid write amplification, since existing, valid data on the erase block with the data to be modified need not be erased and recopied. Moreover, writing data out-of-place may remove erasure from the latency path of many storage operations, such that erasure latency is not part of the “critical path” of write operations.

The storage layer130may be configured to perform storage operations out-of-place by use of, inter alia, the log storage module135. The log storage module135may be configured to append data at a current append point within the storage address space144in a manner that maintains the relative order of storage operations performed by the storage layer130, forming a “storage log” on the storage medium140. As used herein, a “storage log” refers to a data storage configuration configured to define a relative order of storage operations performed on the storage medium140.

The storage layer130may further comprise a media management module136configured to manage storage resources of the storage medium140. The media management module136may be configured to reclaim storage resources of the storage device141that comprise invalid and/or obsolete data. The media management module136may be further configured to manage grooming operations, such as wear leveling, data refresh, data reliability, and the like. As disclosed above, the storage device141may comprise a write-once storage medium140; the media management module136may be configured to initialize storage divisions for use by the log storage module135(e.g., put storage divisions into a writeable state). Reclaiming a storage division may comprise, inter alia, relocating valid data stored on the storage division (if any), and erasing the storage division. The media management module136may be configured to maintain a queue of writeable storage divisions (e.g., storage divisions that have been reclaimed and/or erased).

The storage layer130may further comprise a reserve module138configured to adapt the reserve capacity on the storage medium140in response to operating conditions on the storage layer130(e.g., to manage a write capacity of the storage medium140). As used herein, the “write capacity” of the storage layer130refers to the amount of storage divisions that are in a writeable state (e.g., have been erased and/or initialized). The current write capacity available to the storage layer130may be based on, inter alia, the number of writeable storage divisions available on the storage medium140. The write capacity may differ from the full physical storage capacity of the storage device141. As disclosed in further detail herein, the reserve module138may be configured to dynamically modify a write capacity reserve on the storage medium140to prevent write stall conditions.

As disclosed in further detail herein, the storage layer130may be configured to perform storage operations “out-of-place” within the storage address space144of the storage device141in order to, inter cilia, address asymmetric properties of the storage medium140. In some embodiments, the storage layer130may be configured to append data to a storage log, by use of the log storage module135. The append-only, write-out-of-place storage paradigm of the storage layer130may leverage a reserve capacity of initialized storage divisions to operate efficiently.

FIG. 2depicts another embodiment of a system200comprising a storage layer130. In theFIG. 2embodiment, the storage medium140may comprise a plurality of independent banks149A-N, each of which may comprise one or more storage arrays145A-N, as disclosed above.

The storage controller139may comprise a storage request receiver module231configured to receive storage requests from the storage layer130via an interconnect127. The storage request receiver module231may be further configured to transfer data to/from the storage layer130and/or I/O clients106. Accordingly, the storage request receiver module231may comprise one or more direct memory access (DMA) modules, remote DMA modules, bus controllers, bridges, buffers, and so on.

The storage controller139may comprise a write module240that is configured to store data on the storage medium140in response to requests received via the storage request receiver module231. The storage requests may comprise and/or reference the logical interface of the data pertaining to the requests. The write module240may be configured to store the data in a self-describing storage log, which, as disclosed above, may comprise appending data packets110sequentially within the storage address space144of the storage medium140. The data packets110may comprise and/or reference the logical interface of the data (e.g., may comprise the LID(s) associated with the data). The write module240may comprise a write processing module242configured to process data for storage. Processing data fir storage may comprise one or more of: a) compression processing, b) encryption processing, c) encapsulating data into respective data packets110(and/or other containers), d) performing error-correcting code (ECC) processing, and so on. A write buffer244may be configured to buffer data for storage on the storage medium140. In some embodiments, the write buffer244may comprise one or more synchronization buffers configured to synchronize a clock domain of the storage controller139with a clock domain of the storage medium140(and/or interconnect127).

The log storage module135may be configured to select storage location(s) for data storage operations and may provide addressing and/or control information to the storage arrays145A-N of the independent banks149A-N. The log storage module135may be configured to append data sequentially in a log format within the storage address space144of the storage medium140, as disclosed herein.

Storage operations to write data on the storage medium140may comprise: a) appending one or more data packets to the storage log on the storage medium140and b) updating storage metadata134to associate LID(s) of the data with the storage addresses of the one or more data packets. In some embodiments, the storage metadata134may be maintained on memory resources of the storage controller139(e.g., on dedicated volatile memory resources of the storage device141comprising the storage medium140). Alternatively, or in addition, portions of the storage metadata134may be maintained within the storage layer130(e.g., on a volatile memory102of the computing device110ofFIG. 1A). In some embodiments, the storage metadata134may be maintained in a volatile memory by the storage layer130, and may be periodically stored on the storage medium140.

The storage controller139may further comprise a data read module241configured to read data from the storage log on the storage medium140in response to requests received via the storage request receiver module231. The requests may comprise LID(s) of the requested data, a storage address of the requested data, and/or the like. The read module241may be configured to: a) determine the storage address(es) of the data packet(s)110comprising the requested data by use of, inter alia, the forward map160, b) read the data packet(s)110from the determined storage address(es) on the storage medium140, and c) process data for use by the requesting entity. Data read from the storage medium140may stream into the read module241via a read buffer245. The read buffer245may comprise one or more read synchronization buffers for dock domain synchronization, as described above. A read processing module243may be configured to processes data read from the storage medium140, which may include, but is not limited to, one or more of: a) decompression processing, b) decryption processing, c) extracting data from one or more data packet(s)110(and/or other containers), d) performing ECC processing, and so on.

The storage controller139may further comprise a bank controller252configured to selectively route data and/or commands of the write module240and/or read module241to/from particular independent banks149A-N. In some embodiments, the storage controller139is configured to interleave storage operations between the independent banks149A-N. The storage controller139may, for example, read from the storage array145A of bank149A into the read module241while data from the write module240is being programmed to the storage array14513of bank149B. Further embodiments of multi-bank storage operations are disclosed in U.S. patent application Ser. No. 11/952,095, entitled, “Apparatus, System, and Method for Managing Commands for Solid-State Storage Using Bank Interleave,” filed Dec. 12, 2006 for David Flynn et al., which is hereby incorporated by reference in its entirety.

The write processing module242may be configured to encode data packets110into ECC codewords. As used herein, an ECC codeword refers to data and corresponding error detection and/or correction information. The write processing module242may be configured to implement any suitable FCC algorithm and/or generate FCC codewords of any suitable type, which may include, but are not limited to, data segments and corresponding ECC syndromes, ECC symbols, ECC chunks, and/or other structured and/or unstructured ECC information. FCC codewords may comprise any suitable error-correcting encoding, including, but not limited to, block ECC encoding, convolutional ECC encoding, Low-Density Parity-Check (LDPC) encoding, Gallager encoding, Reed-Solomon encoding, Hamming codes, Multidimensional parity encoding, cyclic error-correcting codes, BCH codes, and/or the like. The write processing module242may be configured to generate ECC codewords of a pre-determined size. Accordingly, a single packet may be encoded into a plurality of different ECC codewords and/or a single ECC codeword may comprise portions of two or more packets. Alternatively, the write processing module242may be configured to generate arbitrarily sized ECC codewords. Further embodiments of error-correcting code processing are disclosed in U.S. patent application Ser. No. 13/830,652, entitled, “Systems and Methods for Adaptive Error-Correction Coding,” filed Mar. 14, 2013 for Jeremy Fillingim et al, which is hereby incorporated by reference in its entirety.

As disclosed, herein, the storage layer130may be configured to manage an asymmetric, write-once storage medium140by, inter alia, storing data sequentially within the storage address space144(e.g., writing data out-of-place, in a contextual, log-based storage format).FIG. 3Adepicts one embodiment300A of data stored sequentially within the storage address space144of the storage medium140by the storage layer130. The storage log350may comprise data stored with persistent metadata configured to determine a log order352of the data (e.g., log order352of packets110[A][0]-110[N][P]). The tog storage module135may be configured to append data packets110sequentially within the storage address space144(e.g., within storage divisions370[1]-370[N]), by use of, inter cilia, the storage controller139. The log storage module135may be configured to fill the respective storage divisions370[1]-370[N] before appending data to other storage divisions. The order in which data is appended to the respective storage divisions370[1]-370[N] in the storage address space144may be determined according to the availability of erased and/or initialized storage divisions370[1]-370[N], as disclosed in further detail herein.

In theFIG. 3Aembodiment, the log storage module135may have stored data packets110[1][A]-110[1][P] sequentially within the storage address space of storage division370[1], such that data packet110[1][P] is later in the storage log (stored more recently) relative to data packet110[1][A].FIG. 3Afurther illustrates data packets110stored sequentially within other storage divisions370[2]-370[N]: data packets110[2][A]-110[2][P] are stored sequentially within storage division370[2], data packets110[3][A]-1110[3][P] are stored sequentially within storage division370[3], data packets110[N][A]-110[N][P] are stored sequentially within storage division370[N], and so on.

As disclosed herein, the storage layer130may mark the storage divisions370[1]-370[N] with respective sequence information113[1]-113[Y] configured to define the order in which the storage divisions370[1]-370[1]-370[N] were programmed. Accordingly, the order in which the data packets110[1][A]-110[N][P] were stored within the respective storage divisions370[1]-370[N] may be defined by, inter alia, sequence information113[1]-113[Y] of the storage divisions370[1]-370[N]. In some embodiments, sequence information113[1]-113[Y] may be stored at predetermined locations within the storage divisions370[1]-370[N] (e.g., in a header, at a predetermined offset, or the like). The respective sequence information113[1]-113[Y] may be stored on the storage divisions370[1]-370[N] when the storage divisions370[1]-370[N] are initialized (e.g., erased) by the media management module136, selected for use by the log storage module135, and/or placed in a write queue by the media management module136; when data is appended to the storage divisions370[1]-370[N]; when the storage divisions370[1]-370[N] are closed; and/or the like.

In theFIG. 3Aembodiment, the sequence information113[Y] may correspond to the most recent (youngest) storage division370[1]-370[N] of the storage log350, and the sequence information113[1] may correspond to the earliest (oldest) storage division370[1]-370[N] of the storage log. Therefore, and as illustrated inFIG. 3A, the log order352of the storage divisions370[1]-370[N] may be370[N] (most recent),370[1],370[3], and370[2] (oldest). The order of the individual data packets110[1][A]-110[N][P] within the storage log350may be determined based on the sequence information113[1]-113[Y] of the storage divisions370[1]-370[N] and the relative storage location(s) of the data packets110[1][A]-110[N][P] within the storage divisions370[1]-370[N]. In theFIG. 3Aembodiment, the log order352from most recent to oldest is:110[N][P]-110[N][A],110[1][P]-110[1][A],110[3][P]-110[3][A], and110[2][P]-110[2][A].

FIG. 3Bdepicts one embodiment300B of storage operations, performed by the storage layer130, configured to append data to an ordered storage log350. As disclosed herein, the storage address space144may comprise a plurality of storage divisions370[1]-370[N] (e.g., erase blocks, logical erase blocks, or the like), each of which can be initialized for use in storing data (e.g., erased). The storage divisions370[1]-370[N] may comprise respective storage locations, which may correspond to banks149A-N, storage arrays145A-N, pages, logical pages, blocks, sectors, and/or the like, as disclosed herein. The storage locations may be assigned respective storage addresses within the storage address space144(e.g., storage address 0 of storage division370[1] through storage address X of storage division370[N]).

The log storage module135may be configured to store data sequentially within respective storage divisions370[1]-370[N], by use of the storage controller139. The log storage module135may be configured to sequentially append data packets110at a current append point180within the storage address space144. In theFIG. 3Bembodiment, the current append point180corresponds to storage location182of storage division370[1]. The log storage module135may be configured to sequentially increment the append point180within the storage division370[1] until the storage division370[1] is fully programmed (and/or filled within a threshold or boundary condition).

In response to filling the storage division370[1], the log storage module135may be configured to advance181the append point180to a next available storage location (e.g., a next available storage division370[1]-370[N]). As used herein, an “available” storage location refers to a storage location that is “writeable” and/or in a “writeable state.” As used herein, a storage location that is in a writeable state refers to a storage location that has been initialized and has not yet been programmed (e.g., has been erased). As disclosed above, some types of storage media can only be reliably programmed once after erasure. Accordingly, a writeable storage location may refer to a storage location and/or storage division370[1]-370[N] that is erased. Conversely, storage locations that have been programmed and/or are not initialized are in an “un-writeable” state. Advancing181the append point180may comprise selecting a writeable storage division370[2]-370[N]. As disclosed in further detail herein, in some embodiments, advancing181the append point180to the next available storage location may comprise selecting a storage division370[1]-370[N] from a queue of available storage divisions370[1]-370[N] (a write queue337, as disclosed in conjunction withFIG. 3Cbelow).

In theFIG. 3Bembodiment, the storage division370[2] may be unavailable for use by the log storage module135(e.g., un-writeable) due to, inter alia, not being in an erased state, being out-of-service due to high error rates, or the like. Therefore, after filling the storage location182, the log storage module135may skip the unavailable storage division370[2] and advance181the append point180to the next available storage division370[3]. The log storage module135may be configured to continue appending data to storage locations183-185, after which the append point180is advanced to a next available storage division370[1]-370[N], as disclosed herein.

After storing data on the “last” storage location within the storage address space144(e.g., storage location189of storage division370[N]), the log storage module135may advance181the append point180by wrapping back to the first storage division370[1] (or the next available storage division, if storage division370[1.] is unavailable). Accordingly, the storage layer130may be configured to manage the storage address space144as a loop or cycle (e.g., as illustrated inFIG. 3C).

As disclosed herein, the log storage module135may be configured to append data sequentially, in a format configured to define a storage log350on the storage medium140. The log storage format implemented by the storage layer130may be used to modify and/or overwrite data out-of-place. Performing storage operations out-of-place may avoid write amplification, since existing valid data on the storage divisions370[1]-370[N] comprising the data that is being modified and/or overwritten need not be erased and/or recopied. Moreover, writing data out-of-place may remove erasure from the latency path of many storage operations (the erasure latency may not be a part of the timing path of write operations).

In theFIG. 3Bembodiment, a data segment D0 corresponding to LID A may be stored at storage location191. The data segment D0 may be stored in association with persistent metadata (e.g., in the packet format110, disclosed above). The data segment112of the packet110may comprise the data segment D0, and the persistent metadata114may comprise the LID(s) associated with the data segment (e.g., LID A). An I/O client106may request an operation to modify and/or overwrite the data associated with the LID A, which may comprise replacing the data segment D0 with data segment D1. The storage layer130may perform this operation out-of-place by appending a new packet110comprising the data segment D1 at a different storage location193on the storage medium140, rather than modifying the existing data in place, at storage location191. The storage operation may further comprise updating the storage metadata134to associate the LID A with the storage address of storage location193and/or to invalidate the obsolete data D0 at storage location191. As illustrated inFIG. 3B, updating the storage metadata134may comprise updating an entry of the forward map160to associate the LID A164E with the storage address of the modified data segment D1. Updating the storage metadata134may further comprise updating one or more reverse indexes and/or validity bitmaps, as disclosed in further detail herein.

Performing storage operations out-of-place (e.g., appending data to the storage log) may result in obsolete and/or invalid data remaining on the storage medium140(e.g., data that has been erased, modified, and/or overwritten out-of-place). As illustrated inFIG. 3B, modifying the data of LID A by appending the data segment D1 to the storage log rather than overwriting and/or replacing the data segment D0 in place at storage location191results in keeping the obsolete version of the data segment D0 on the storage medium140. It may not be efficient to immediately remove the obsolete version of the data segment D0 since, as disclosed above, erasing the data segment D0 may involve erasing an entire storage division370[1] and/or relocating valid data on the storage division370[1]. As such, over time, the storage medium140may accumulate a significant amount of obsolete and/or “invalid” data. As used herein, “invalid” data refers to data that does not need to be retained on the storage medium140, which may include data modified and/or overwritten in subsequent storage operations, data corresponding to deallocated LIDs, data erased by an I/O client106, and/or the like.

In some embodiments, the storage layer130is configured to maintain storage metadata134comprising a reverse index168. The reverse index168may be configured to, inter alia, identify invalid data within the storage divisions370[1]-370[N] of the storage medium140. The reverse index168may correspond to the storage address space144of the storage medium140. In some embodiments, the reverse index168comprises one or more validity bitmaps comprising entries169configured to identify storage locations comprising invalid data. The reverse index168may be further configured to maintain information pertaining to the storage location(s) and/or storage division(s)370[1]-370[N], including, but not limited to: wear level, reliability characteristics (e.g., error rate), performance characteristics (e.g., read time, write time, erase time, and so on), data age (e.g., time since last program operation, refresh, or the like), read disturb count, write disturb count, and so on. In theFIG. 3Bembodiment, storing the data segment D1 of LID A at storage location193renders data segment D0 at storage location191obsolete. In response, the storage layer130may be configured to mark the entry169associated with storage location191as invalid to indicate that the storage location191comprises data that does not need to be retained on the storage medium140.

The storage layer130may be configured to reconstruct the storage metadata134, including the forward map160, by use of contents of the storage log on the storage medium140. In theFIG. 3Bembodiment, the current version of the data associated with LID A may be determined based on the relative log order of the data packets110at storage locations191and193. Since the data packet at storage location193is ordered after the data packet at storage location191in the storage log350, the storage layer130may determine that storage location193comprises the most recent, up-to-date version of the data corresponding to LID A. The storage layer130may reconstruct the forward map160to associate the LID A with the data packet at storage location193(rather than the obsolete data at storage location191). The storage layer130may be further configured to mark the storage location193as comprising invalid data that does not need to be retained on the storage medium140.

As disclosed above, the storage layer130may comprise a media management module136configured to reclaim storage resources occupied by invalid data and/or prepare storage divisions370[1]-370[N] for use by the log storage module135. The media management module136may be further configured to perform other media management operations including, but not limited to, refreshing data stored on the storage medium140(to prevent error conditions due to data degradation, write disturb, read disturb, and/or the like), monitoring media reliability conditions, and/or the like.

In some embodiments, the media management module136is configured to operate as a background process, outside of the critical path for servicing storage requests of the I/O clients106. The media management module136may identify storage divisions370[1]-370[N] to reclaim by use of the storage metadata134(e.g., the reverse index168). As used herein, reclaiming a storage resource, such as a storage division370[1]-370[N], refers to erasing the storage division370[1]-370[N] so that new data may be stored/programmed thereon. The storage layer130may identify storage divisions370[1]-370[N] to reclaim based on one or more factors, which may include, but are not limited to, the amount of invalid data stored on the storage division370[1]-370[N], the amount of valid data in the storage division370[1]-370[N], wear levels of the storage division370[1]-370[N] (e.g., number of program/erase cycles), time since the storage division.370[1]-370[N] was programmed and/or refreshed, the relative order of the storage division370[1]-370[N] within the storage log350, and so on. The media management module136may identify invalid data on the storage medium140, such as the data segment D0 at storage location191, by use of the storage metadata134(e.g., the reverse index168and/or forward map160). The media management module136may determine that storage locations that are not associated with valid identifiers (LIDs) in the forward map160and/or are marked invalid in the reverse map168comprise invalid data that does not need to be retained on the storage medium140.

As used herein, a storage recovery operation to reclaim a storage division370[1]-370[N] may comprise: a) identifying valid data stored on the storage division370[1]-370[N] (by use of the storage metadata134), b) relocating the identified data to other storage locations, and c) initializing the storage division370[1]-370[N] (e.g., erasing the storage division370[1]-370[N]). Initializing the storage division370[1]-370[N] may further comprise marking the storage division370[1]-370[N] with sequence information113configured to identify an order of the storage division370[1]-370[N] within the storage log350, as disclosed herein. Further embodiments of systems and methods for reclaiming storage resources are disclosed in U.S. Pat. No. 8,402,201, entitled “Apparatus, System, and Method for Storage Space Recovery in Solid-State Storage,” issued on Mar. 19, 2013 to David Flynn et al., which is hereby incorporated by reference in its entirety.

FIG. 3Cis a block diagram of one embodiment300C of a media management module136of the storage layer130. The media management module136may comprise a groomer module336configured to manage grooming operations on the storage medium140, which may include reclaiming storage divisions370[1]-370[N], as disclosed herein. The media management module136may be further configured to write capacity metadata137, which may include a write queue337configured to identify storage divisions370[1]-370[N] that are in a writeable state (e.g., storage divisions370[1]-370[N] that have been erased and/or initialized). The media management module136may place storage divisions370[1]-370[N] into the write queue337in response to recovering and/or initializing the storage divisions370[1]-370[N], by use of the groomer module336. The log storage module135may access the write queue337to advance the append point180within the storage log350, as disclosed above. The write capacity metadata137may be maintained with the storage metadata135and/or in separate metadata storage.

The number of storage divisions370[1]-370[N] in the write queue337may determine the amount of write capacity currently available to the storage layer130. As used herein, “write capacity” refers to the amount of storage capacity that is currently available for performing write operations (e.g., capacity that is in a writeable state). Accordingly, the write capacity may correspond to the number of storage divisions370[1]-370[N] that are currently in a writeable state. The write capacity may differ from the amount of “free” physical storage capacity on the storage medium140. As used herein, “free” physical storage capacity refers to physical storage capacity that is not currently in use to store valid data. “Used” or “occupied” physical storage capacity refers to physical storage capacity that is currently being used to store valid data. As disclosed above, the storage layer130may be configured to write data out-of-place due to the asymmetric, write-once properties of the storage medium140. Accordingly, data that is invalid and/or obsolete may remain on the storage medium140until removed in a reclamation operation. The storage resources that are occupied by invalid data (and/or are in a non-writeable state) represent storage capacity that could be used to store other, valid data, but are not available to do so until they are re-initialized by the groomer module336(e.g., erased).

Referring back toFIG. 3B, after storing D1 at storage location193, the storage location193represents “used” physical storage capacity (e.g., storage resources occupied by valid data). The storage location191, however, comprises invalid data and, as such, represents “free” physical storage capacity, which is not currently available for use. Although storage location191is “free,” the storage location191is not usable for write operations until the corresponding storage division370[3] is recovered. Therefore, although the storage location191represents “free” space on the storage medium140, the storage location191does not contribute to the available write capacity of the storage medium140until it is re-initialized.

Referring again toFIG. 3C, the groomer module336may be configured to identify and reclaim storage resources for use by the media management module136. As illustrated in state315A, the groomer module336may iterate over the storage divisions370[1]-370[N] comprising the storage log350, to identify storage divisions370[1]-370[N] suitable for recovery. As disclosed above, the groomer module336may be configured to select storage divisions370[1]-370[N] for recovery based on the amount of invalid data on the storage divisions370[1]-370[N], the last program time of the storage divisions, reliability metrics, and the like. The groomer module336may be configured to evaluate storage divisions370[1]-370[N] at a current recovery point382within the storage address space144. The recovery point382may correspond to a “tail” region353of the storage log350. As used herein, the tail of the storage log350refers to storage divisions370[1]-370[N] ordered after other, younger storage divisions in the storage log350(e.g., storage division370[2] ofFIG. 3A). Conversely, the “head” region351of the storage log350refers to data that was recently appended to the storage log350. The groomer module336may be configured to evaluate and/or reclaim older storage divisions370[1]-370[N] in the storage log350before evaluating and/or reclaiming more recent storage divisions370[1]-370[N]. The groomer module336may, therefore, be configured to traverse the storage address space144of the storage log350in reverse log order383(e.g., from older to more recent).

As illustrated in state315A, the groomer module336may be configured to schedule storage recovery operations at a rate configured to ensure that the log storage module135has sufficient write capacity to efficiently satisfy write requests of the I/O clients106. Accordingly, the groomer module336may be configured to schedule storage reclamation operations to occur at a similar rate to which the log storage module135is appending data to the storage medium140at the append point180. Accordingly, the log storage module135may have available, writeable storage divisions369in the write queue337for use in satisfying write requests from the I/O clients106.

As disclosed above, storage recovery operations may be high-latency as compared to read and/or write operations (e.g., it may take 10 to 100 times longer to erase a storage division370[1]-370[N] than to read and/or program data to the storage division370[1]-370[N]). Moreover, the groomer module336may be configured to reclaim storage resources in the background, and as such, may suspend such operations while other storage requests are being serviced by the storage layer130. As illustrated in state315B, in response to write-intensive workloads involving large numbers of write requests and/or requests to write large amounts of data, the log storage module135may consume the available write capacity of the storage device141(e.g., consume large numbers of the writeable storage divisions369). The groomer module336may be unable to keep up with the demand for write capacity, such that the log storage module135exhausts the capacity of writeable storage divisions369in the write queue337.

In response to exhausting the write capacity of the storage device141(and/or exceeding a write capacity threshold), the storage layer130may enter a “write stall” state. In a write stall state, the storage layer130may be configured to stall write operations until additional write capacity is made available (e.g., until the groomer module336reclaims additional write capacity by, inter alia, reclaiming storage divisions370[1]-370[N], as disclosed herein). Storage recovery operations may be complicated due to the lack of available write capacity (e.g., it may be difficult to relocate valid data from the storage divisions370[1]-370[N] that are being reclaimed). In some embodiments, the media management module136may be configured to maintain a threshold amount of write capacity in order to perform grooming operations. The relocation write capacity threshold may correspond to an amount of write capacity available to relocate valid data on storage divisions370[1]-370[N] that are being reclaimed. Relocation capacity may be equivalent to one or more storage divisions370[1]-370[N] and/or a portion of a storage division370[1]-370[N] (e.g., using a garbage collection bypass, as disclosed in U.S. Pat. No. 8,402,201, which is incorporated herein).

The media management module136may be configured to prevent write stall conditions. In some embodiments, the media management module136is configured to increase the priority of the storage recovery operations of the groomer module336in response to determining that the available write capacity is less than a threshold value. Increasing the priority of the storage recovery operations may comprise allowing the recovery operations to preempt other storage operations and/or requests being serviced by the storage layer130(e.g., configure the groomer module336to operate in the foreground).

Alternatively, or in addition, the media management module136may comprise a reserve module138configured to over-provision storage resources of the storage device140. As used herein, “over-provisioning” refers to allocating, designating, reserving, and/or provisioning storage resources of the storage medium140for use as, inter alia, additional write capacity. Over-provisioning may comprise designating a portion of the physical storage capacity available on the storage medium140as reserve capacity. As used herein, the “physical storage capacity” of the storage medium140refers to the storage capacity of the storage address space144of the storage medium140. The physical storage capacity may exclude portions of the storage medium140that are not accessible to I/O clients106(and/or the storage layer130), such as portions of the storage medium140designated for use as replacements for failed storage divisions, dedicated metadata storage locations and/or channels, and the like.

FIG. 3Ddepicts one embodiment300D of storage capacity reservations of a media management module136. As illustrated inFIG. 3D, the storage medium140may comprise a storage address space144used to store data of the I/O clients106by use of, inter alia, the storage layer130as disclosed herein. The storage medium140may further comprise auxiliary storage divisions371[1]-371[G] for use as replacements for failed and/or unreliable storage divisions370[1]-370[N]. In some embodiments, storage divisions371[1]-371[X] in the auxiliary region343may be mapped into the storage address space in response to storage division failure conditions. Embodiments of apparatus, systems, and methods for managing failure conditions are disclosed in U.S. Pat. No. 8,195,978, entitled “Apparatus, System, and Method for Detecting and Replacing a Failed Data Storage,” issued Jun. 5, 2012, which is hereby incorporated by reference in its entirety. The physical storage capacity of the storage medium140may correspond to the number of useable storage divisions370[1]-370[N] in the storage address space144. In theFIG. 3Dembodiment, the storage medium140comprises N storage divisions370[1]-370[N] and the physical storage capacity of the storage medium140is N times the storage capacity of the respective storage divisions370[1]-370[N].

The storage layer130may be configured to determine the amount of physical address space that is currently in use to store data of the I/O clients106. As disclosed above, “occupied” or “used” physical storage capacity refers to the physical storage capacity that is currently being used to store valid data (e.g., is occupied by valid data). “Free” or “unoccupied” physical storage capacity refers to storage capacity that is not currently being used to store valid data. Physical storage occupancy may be determined by use of the forward map160(and/or other storage metadata134). The assignments between LIDs and storage locations in the forward map160may represent physical storage capacity that is in use to store valid data. The used physical storage capacity of the storage medium140may, therefore, be determined by summing and/or combining the storage locations referenced in the forward map160, in some embodiments, the media management module136is configured to maintain usage information for the storage medium140(e.g., a running total of the occupied physical storage capacity on the storage medium140). Further embodiments for managing physical storage resources of a storage medium are disclosed in U.S. patent application Ser. No. 12/879,004, entitled “Apparatus, System, and Method for Allocating Storage,” filed Sep. 9, 2010 for Jonathan Thatcher et al., which is hereby incorporated by reference in its entirety.

As disclosed above, the “free” or “unoccupied” storage capacity of the storage medium140may not be usable for write operations until the corresponding storage divisions370[1]-370[N] are re-initialized. Therefore, existence of free storage capacity on the storage medium140may not guarantee that the storage layer130will be capable of servicing write requests without first recovering storage resources on the storage device141(e.g., in a write stall condition). Accordingly, in some embodiments, the reserve module138may over-provision storage resources by reserving a portion of the physical storage capacity of the storage medium140(e.g., as free storage divisions370[1]-370[N] available for relocation and/or write operations). The storage layer130may manage the storage medium140as having less physical storage capacity than the full physical storage capacity390available on the storage medium140. As depicted inFIG. 3D, the reserve module138may assign storage space equivalent to one or more storage divisions370[1]-370[N] as over-provisioned, reserve capacity394. The remaining storage space may be available storage capacity392. In theFIG. 3Dembodiment, the reserve module138may provision reserve capacity394equivalent to R storage divisions370[1]-370[N]. The remaining storage capacity equivalent to N-R storage divisions370[1]-370[N] may be provisioned as available storage capacity392of the storage layer130. In other embodiments, the reserve module138may be configured to provision reserve capacity394as a percentage and/or proportion of the full storage capacity390of the storage medium140(e.g., 20 percent of the full capacity390).

The reserve capacity394may not correspond to specific storage divisions370[1]-370[N] within the storage address space144; all of the storage divisions370[1]-370[N] may remain available to the storage layer130for performing storage and/or grooming operations. The storage layer130may, however, treat the storage medium140as being at “full” capacity in response to filling the equivalent of the available capacity392. In some embodiments, the storage layer130may report the available capacity392as the full storage capacity of the storage device141through, inter alia, the storage interface131. Accordingly, I/O clients106may view the storage layer130as providing the available capacity392as opposed to the full capacity390.

In one embodiment, for example, the storage medium140may have a physical storage capacity of 160 GB. The reserve module138may over-provision the 160 GB, by designating 32 GB as reserved capacity394, and 128 GB as available storage capacity392. The storage layer130may, therefore, treat the storage medium140as having a storage capacity of 128 GB. The 32 GB of reserved capacity394may be leveraged as write and/or relocation capacity by the media management module136, as disclosed herein. The media management module136may leverage the reserve capacity392to provide additional write capacity for the log storage module135and/or for use by the groomer module336for media management and grooming operations, such as storage recovery (e.g., garbage collection), data refresh, reliability management, wear leveling, and the like.

In some embodiments, the reserve module138may be configured to provision a pre-determined amount of reserve capacity394within the storage medium140. The pre-determined amount of reserve capacity394may be based on a write capacity profile346(FIG. 3C), which may correspond to a pre-determined deployment profile347A corresponding to a priori characteristics of the storage layer130, storage controller139, storage medium140. I/O clients106, computing system100, and the like. The deployment profile347A may include characteristics, such as the latency of storage recovery operations (e.g., the time required to erase a storage division370[1]-370[N]), the latency of write operations (e.g., the time required to program data to the storage medium140), an input/output operations per second (IOPS) capability of the storage layer130, characteristics of the computing system100and/or network115(e.g., bandwidth, throughput, and so on), and the like.

The reserve module138may be configured to implement a static, pre-determined available storage capacity392based on the a priori information of the deployment profile347A. A static, predetermined reserve percentage may not, however, accurately reflect actual usage conditions of the storage layer130and, as such, may result in inefficient operation. As indicated above, a pre-determined reserve percentage may be based on capabilities of the storage layer130and/or storage medium140, such as, for example, a maximum write ION rating of the storage layer130and/or storage medium140. Actual usage and/or operational conditions may significantly differ from these boundary conditions. In one embodiment, for example, the I/O clients106may impose light write loads on the storage layer130, and as such, the pre-determined reserve capacity394may be significantly larger than what is actually needed for efficient operation, resulting in wasted storage capacity. In another embodiment, a pre-determined reservation percentage may be based on expected IOPS usage. The I/O clients106may, however, impose write loads that are higher than expected, resulting in reduced performance due to write stall conditions.

In some embodiments, the reserve module138is configured to dynamically modify the reserve capacity394. The reserve module138may determine the reserve capacity394for the storage layer by use of the write capacity metadata137. As illustrated inFIG. 3C, the write capacity metadata137may comprise a write capacity profile346that includes a deployment profile347A pertaining to pre-determined, a priori characteristics of the storage layer130, as disclosed above, and an operating profile347B configured to indicate current and/or historical usage characteristics of the storage layer130. The operating profile347B may correspond to the availability of write capacity on the storage medium140(e.g., may indicate whether the storage layer130has sufficient write capacity for efficient operation).

The reserve module138may comprise an reserve analysis module338configured to determine an optimal reservation capacity394for the storage layer130by use of the write capacity profile346. The reserve module138may further comprise a monitoring module339configured to maintain the operating profile347B of the storage layer130(e.g., develop the operating profile347B).

The monitoring module339may be configured to develop the operating profile347B by monitoring usage characteristics of the I/O clients106, the operational conditions of the storage layer130, and so on. The operating profile347B may comprise any suitable operating characteristic and/or property including, but not limited to: the write load on the storage layer130, observed write performance (e.g., observed IOPS capabilities of the storage layer130and/or storage medium140), observed performance of the groomer module336(e.g., recovery rate, erase latency, and so on), rate of write requests received from110clients106, size of write requests received at the storage layer130, write stall rate (if any), groomer priority, availability of write capacity (e.g., number of storage divisions370[1]-370[N] available in the write queue337), write operations performed on the storage device per unit time, a rate of write operations performed on the storage device in response to cache misses, a rate of write operations performed on the storage device in response to write operations pertaining to data in the cache, and so on.

The reserve analysis module338may be configured to determine the size of the reserve capacity394in response to operating conditions of the storage layer130(e.g., the write capacity profile346). As disclosed above, the IOPS of write operations performed on the storage layer130may determine the rate at which the write capacity of the storage layer130is consumed, and as such, may determine the relative rate of grooming operations and/or the write overhead needed to prevent write stall conditions. Accordingly, in some embodiments, the reserve analysis module338may size the reserve capacity394in accordance with an observed IOPS rate (e.g., expand the reserve capacity394in response to increases in the write load on the storage layer130, and contract the reserve capacity394in response to decreases in the write load). The disclosure is not limited in this regard, however, and may calculate an optimal reserve capacity394in response to any suitable characteristic of the operating profile347B including, but not limited to: write load, write IOPS, ratio of write operations to read operations, groomer performance, write stall conditions (if any), groomer activity, write capacity availability, I/O client106demands and/or requests, configuration parameters, and so on. The reserve analysis module338may determine that more reserve capacity394is needed in response to one or more of: high write TOPS conditions, increased groomer activity (e.g., groomer forced to preempt other I/O requests), low write capacity availability (e.g., fewer than a threshold number of storage divisions370[1]-370[N] in the write queue), and/or the like. Conversely, the reserve analysis module338may determine that less reserve capacity394is needed in response to one or more of: low write IOPS conditions (higher proportion of reads than writes), low groomer activity, high write capacity availability, and/or the like.

In embodiments, the reserve analysis module338is configured to determine the optimal size for the reserve capacity394by use of a reserve policy348. The reserve policy348may comprise trigger conditions and/or rules configured to determine a size of the reserve capacity394in response to certain operating conditions (as indicated by the write capacity metadata346). The reserve policy348may comprise configuration parameters349A, which may be set by, inter alia, the I/O clients106(and/or other entities) through the storage interface131(and/or other interface mechanism). The configuration parameters349A may comprise preferences pertaining to the reserve capacity348, such as a minimum reserve capacity394, maximum reserve capacity394, Quality of Service (QoS) parameters, and/or the like. The QoS parameters may comprise write IOPS requirements of one or more I/O clients106. The reserve analysis module338may be configured to set the reserve capacity394to ensure that the write IOPS of the QoS parameters can be satisfied, which, in some embodiments, may comprise increasing the size of the reserve capacity394to prevent write stall conditions. Alternatively, or in addition, the configuration parameters349A may comprise a storage capacity availability QoS, configured to guarantee availability of a particular storage capacity to one or more I/O clients106, which may set an upper limit on the size of the reserve capacity394.

In some embodiments, the reserve policy348may comprise an optimization criterion349B. The reserve analysis module338may use the optimization criterion349B to determine an optimal reserve capacity394for the storage layer130by, inter alia, maximizing the optimization criterion349B. The optimization criterion349B may correspond to characteristic(s) of the write capacity profile346and/or may configuration settings of the I/O clients. The optimization criterion349B may, for example, be configured to minimize write latency (e.g., reduce write stall conditions), and as such, may weight maximizing write capacity higher than maximizing storage space availability. In another embodiment, the storage layer130may be used to cache data of another storage system. Decreasing the reserve capacity394may enable the storage layer130to improve overall I/O performance by increasing the effective size of the cache. Therefore, in this embodiment, the optimization criterion349B may be adapted to weight storage capacity availability over write performance.

The reserve module138may be configured to dynamically resize the reserved capacity394and/or available capacity392based on the reservation size determined by the reserve analysis module338. Dynamically resizing the available capacity392may comprise configuring the storage layer130to expose different amount(s) of physical storage capacity to the I/O clients106. Dynamically resizing the available capacity may, therefore, comprise indicating a different storage capacity for the storage device141through, inter alia, a storage interface, such as the storage layer interface131. Reducing the available storage capacity may comprise reformatting and/or resizing a virtual storage device exposed to the I/O clients106, which may comprise removing data of the I/O clients from the storage medium140, relocating the data to other storage resources, and/or the like. In some embodiments, resizing the available capacity392may comprise issuing a request to resize the storage resources of the storage layer130to an entity (e.g. a user, administrator, operating system, hypervisor, and/or the like), and resizing the storage resources based on a response from the entity.

In some embodiments, modifying the available capacity392may comprise reconfiguring an I/O client106utilizing storage services of the storage layer130, such as a cache.FIG. 4Adepicts one embodiment of a system400A comprising a cache layer430configured to cache data of a backing store470. The cache layer430may be paired with the storage layer130to cache data of the backing store470. In some embodiments, the cache layer430may be implemented as a component and/or module of the storage layer130. Alternatively, and as illustrated inFIG. 4A, the cache layer430may be implemented separately from the storage layer130(e.g., as an I/O client106).

The backing store470may comprise storage resources including, but not limited to: one or more a hard drives, a RAID, a JBOD storage system, a network attached storage (NAS) system, a storage area network (SAN), and/or the like. The backing store470may comprise a plurality of physical storage locations capable of storing data of the I/O clients106(storage address space474). The backing store470may be communicatively coupled to the computing system100and/or cache layer430through a local bus, remote bus, network115, and/or the like.

I/O clients106may access the storage resources of the backing store470through a backing store address space (BSAS)472. The BSAS472may correspond to a logical address space of the backing store470and may comprise a set, range and/or extent of identifiers (LBAs), as disclosed herein. The identifiers of the BSAS472may correspond to physical storage locations within a storage address space474of the backing store470. As illustratedFIG. 4A, the mappings may comprise deterministic one-to-one mappings between the BSAS472and the storage address space474(e.g., cylinder-sector-head to LBA mappings). In other embodiments, the backing store470may comprise a mapping layer configured to implement other mapping schemes, such as any-to-any mappings between the BSAS472and storage address space474.

The cache layer430be configured to selectively cache data of the backing store470on the storage medium140. The cache layer430may maintain cache metadata434corresponding to the cache storage resources available to the cache layer430. The cache storage resources may be represented by use of cache entries or cache tags432(e.g., a cache address space), which may be configured to identify data of the backing store470that has been cached on the storage medium140(and/or identify storage capacity available to the cache layer430). The cache tags432may be assigned to respective LBAs of the BSAS472and/or to storage locations on the storage medium140. Mappings between the LBAs and the storage locations may be maintained in any suitable mapping structure including, but not limited to: an index, a map, a hash map, a hash table, a tree, a range-encoded tree, a b-tree, and/or the like. As illustrated inFIG. 4A, in some embodiments, the cache tags432may correspond to a forward map460comprising entries462configured to map identifiers464A-N of the BSAS472(e.g., LBAs12213and55627) to respective storage addresses466A-N within the storage address space144of the storage medium140(e.g., any-to-any, fully associate cache mappings). The map identifiers464A-N may map to storage addresses within the storage address space474of the backing store by use of a translation layer of the backing store470and/or other storage layer. In other embodiments, the cache metadata434may comprise set-associative and/or n-way associative mappings.

In some embodiments, the cache layer430is configured to implement the cache metadata434by use of the storage metadata134maintained by the storage layer130(e.g., the cache tags432may be implemented by use of the forward map160, as disclosed herein). Alternatively, the cache layer430may maintain the cache metadata434separately and/or independently of the storage metadata134.

The cache layer430may comprise an I/O redirection module442configured to filter I/O requests within the I/O stack104of the computing system100. The I/O stack104may define a storage architecture in which storage services, such as file system drivers, volume drivers, disk drivers, and the like, are deployed. Storage services may be configured to intemperate by issuing and/or consuming I/O requests within various layers of the I/O stack104, which may include a file layer, a volume layer, a disk layer, a SCSI layer, and so on. The I/O redirection module442may comprise a filter driver configured to monitor I/O requests within the I/O stack104, such as I/O request packets (IRP) of a Microsoft Windows® operating system. The disclosure is not limited in this regard, however, and may be applied to any suitable I/O stack104and/or framework of any operating system (e.g., Unix®, LINUX, OSX®, Solaris®, or the like). The I/O redirection module may identify I/O requests directed to the backing store470, and selectively redirect the I/O requests to the cache layer430to be serviced within the cache layer430.

The cache layer430may further comprise an admission module444configured to selectively admit data of the backing store470into the cache on the storage medium140based on, inter alia, access metadata446pertaining to the BSAS472and/or cache tags432. Further embodiments of cache storage systems are disclosed in U.S. patent application Ser. No. 13/349,417 entitled “Systems and Methods for Managing Cache Admission,” filed Jan. 12, 2012 for Nisha Talagala et al., which is hereby incorporated by reference in its entirety.

The cache tags432may correspond to the storage capacity available to the cache layer430(e.g., the amount of data the cache layer430is capable of caching). The cache layer430may be paired with the storage layer130, which may be configured to provision storage capacity to the cache layer430. The storage capacity provisioned to the cache layer430may be based on a) the available physical storage capacity392of the storage layer130and/or b) storage requirements of other I/O clients106, and/or the like.

The cache layer430may comprise an allocation module438configured to adjust the size of the cache in accordance with the storage capacity provisioned to the cache layer430. The allocation module438may be configured to increase and/or decrease the size of the cache in response to changes in the storage capacity allocated to the cache layer430. The allocation module438may be configured to increase the size of the cache by, inter alia, provisioning one or more additional cache lines and/or cache storage locations for use in caching data of the backing store470. Accordingly, increasing the size of the cache may comprise provisioning one or more additional cache tags432. Decreasing the size of the cache may comprise removing one or more existing cache lines and/or cache storage locations from the cache, which may comprise removing one or more of the cache tags432. Removing a cache tag432may comprise evicting the cache tag432from the cache by, inter alia, a) removing the cache tag432from the storage metadata434, and/or b) flushing the cache tag432to the backing store470(e.g., writing dirty and/or unsynchronized data of the evicted cache tag432to the backing store470).

The allocation module438may be configured to adjust the size of the cache in response to dynamic changes to the reserve capacity394implemented by the reserve module138. As disclosed herein, the reserve module138may be configured to dynamically adjust the reserve capacity392in response to, inter alia, operating conditions on the storage layer130. The reserve module138may, for example, be configured to increase the reserve capacity394(reducing the available capacity392) in response to high write load conditions, and to decrease the reserve capacity394(increasing the available capacity392) in response to low write load conditions. The reserve module138may be configured to inform the allocation module438of changes to the reservation capacity494, and the allocation module482may adjust the size of the cache accordingly (e.g., by adding and/or removing cache tags432, as disclosed herein). In some embodiments, the reserve module138is configured to request a change to the storage allocation to the I/O clients106(e.g., cache layer430), and implement the requested change in response to acknowledgement(s) from the I/O clients106. In response to a request to change the storage capacity available to the cache layer430, the allocation module438may be configured to adjust the size of the cache (e.g., by evicting data from the cache), and acknowledge the request in response to completing the cache size adjustment(s). The request-acknowledge interface may be configured to prevent data loss due to storage capacity changes.

FIG. 49illustrates embodiments4009of cache size adjustment implemented by the cache layer430and/or storage layer130, as disclosed herein. In state415A, the cache layer430may comprise a cache capacity496A, which may correspond to M cache tags432[1]-432[M]. The cache layer430may be configured to cache data of the backing store470on the storage medium140by use of, inter alia, the cache tags432[1]-432[M]. Accordingly, each of the cache tags432[1]-432[M] may correspond to data of the backing store470admitted into the cache by the cache admission module444(e.g., and stored on the storage medium140). As disclosed above, the cache layer430may be configured to maintain access metadata446, which may comprise, inter cilia, access characteristics pertaining to BSAS472and/or cache tags432[1]-432[M].

In state415B, the allocation module438may receive an indication that the storage capacity provisioned to the cache layer430is to be reduced. In response, the allocation module438may select one or more cache tags432[1]-432[M] for eviction. The allocation module438may determine the number of cache tags432[1]-432[M] to remove in order to comply with the requested capacity reduction. The cache tag reduction497may be determined based on the modification to the storage capacity provisioned to the cache layer430and/or the size of the cache tags432[1]-432[M] (e.g., the storage capacity represented by the respective cache tags432[1]-432[M]). In state415B of theFIG. 4Bembodiment, the allocation module438may determine that the cache tag reduction497corresponds to removal of E cache tags432[1]-432[1M].

The allocation module438may be configured to select a set of E cache tags433A-E for eviction from the cache. In some embodiments, the set of E cache tags433A-E may be selected from a particular region and/or section of the cache tags432[1]-432[M] (e.g., the last E cache tags432[M−E]432[M]). Alternatively, and as depicted inFIG. 4B, the cache tags433A-E may be selected anywhere within the set of cache tags432[1]-432[M]. The set of E cache tags433A-E may be selected by use of the admission module444, which may select the cache tags433A-E based on access characteristics of the cache tags433A-E least recently accessed, sequentially, and/or the like).

In response to selecting the cache tags433A-E, the cache layer430may be evicted by: a) writing data of the cache tags433A-E to the backing store470(if necessary), and b) deallocating the cache tags433A-E. Deallocating the cache tags433A-E may comprise removing the cache tags433A-E from the cache metadata434, removing entries corresponding to the cache tags433A-E from a forward map160(and/or other mapping structures), and the Deallocating the cache tags433A-E may further comprise issuing one or more deallocation messages (TRIM messages) to the storage layer130indicating that data corresponding to the cache tags433A-E does not need to be retained on the storage medium140.

Removing the cache tags433may further comprise modifying the cache metadata434to reference a reduced number of cache tags432. As illustrated in state4150, evicting the cache tags433A-E may result in the cache metadata434comprising a smaller set of cache tags432[1]-432[M-E], corresponding to the reduced storage capacity4960provisioned to the cache layer430. In response to removing the cache tags433A-E (and/or modifying the cache metadata434) the allocation module438may acknowledge completion of the capacity reduction. In response to the acknowledgement, the reserve module138may implement the reduction in available capacity392(an increase to reserve capacity394), as disclosed herein.

The allocation module438may be configured increase the size of the cache in response to, inter alia, an indication from the storage layer130that additional storage capacity is available to the cache layer430(e.g., based on a reduction in the reserve capacity394, as disclosed above). The allocation module438may be configured to add one or more cache tags432based on the increase in storage capacity (e.g. the amount of additional storage capacity provisioned to the cache layer430and/or the storage capacity corresponding to each cache tag432). The storage capacity increase illustrated in state415D corresponds to X additional cache tags432(capacity increase498), resulting in an increased cache capacity496D corresponding to M+X cache tags432. The allocation module438may add the X cache tags432using any suitable mechanism. In some embodiments, the allocation module438may insert the cache tags432into the forward map160(and/or other data structure and/or pool), and, in response, the admission module444may utilize the cache tags432to admit data of the backing store470into the cache, as disclosed herein.

Referring back toFIG. 3C, the reserve module138may comprise an reserve analysis module338configured to determine an optimal size of the reserve capacity394based on, inter alia a reserve policy348and/or write capacity profile346. The write capacity profile346comprises an operating profile347B that includes and/or indicates operating characteristics of the storage layer130. The write capacity profile346may be maintained by a monitoring module339, configured to monitor operating conditions on the storage layer130. In some embodiments, the cache layer430may be configured to provide cache profiling information to the monitoring module339(through the storage interface131). The cache profile information may correspond to the access metrics of the cache entries (access metrics of LBAs within the BSAS472), cache write load (e.g., write IOPS), cache read load (e.g., read IOPS), cache hit rate, cache eviction rate, and the like. The cache profile information may pertain to LBAs admitted into the cache. In some embodiments, the cache profile information may further comprise profiling information and/or access metrics pertaining to LBAs of the backing store470that have not been admitted into the cache. The cache profile information may further include cache performance metrics, such as cache hit rate and/or cache miss rates, and/or the like.

The monitoring module339may be configured to incorporate the cache profiling information received from the cache layer430into the write capacity profile346, for use by the reserve analysis module338to determine an optimal size of the reserve capacity394. The cache profiling information may, for example, indicate expected performance impacts of changes to the reserve capacity394. In one embodiment, the cache profiling information may indicate a high cache miss rate. In response, the reserve analysis module338may reduce the size of the reserve capacity494, which may increase the size of the available capacity492, allowing the cache layer430to admit additional data into the cache and, inter cilia, reduce the cache miss rate. In another embodiment, the cache profiling information may indicate a low miss rate. In response and/or in combination with other factors (such as low write capacity and/or the like), the reserve analysis module338may increase the reserve capacity394since, based on the cache profiling information, the reduction in cache capacity is unlikely to significantly affect performance.

In some embodiments, the allocation module438of the cache layer430may be configured to request a particular storage capacity. The allocation module438may request the storage capacity through the storage interface131(and/or other interface mechanism). The requested storage capacity may be indicated in the reserve policy348as configuration parameter349A (e.g., a QoS policy for the cache layer430) and/or an optimization criterion349B, as disclosed herein.

FIG. 5is a flow diagram of one embodiment of a method500for reserving storage capacity. Step510may comprise assigning storage space of a storage layer130to a cache, such as the cache layer430disclosed herein. Step510may comprise selecting a reserve capacity for the storage layer130based on, inter alia, a write capacity profile349(e.g., deployment profile347A and/or operating profile347B), as disclosed herein. Provisioning storage capacity at step510may comprise reporting a storage capacity of the storage layer130through a storage interface131and/or within an I/O stack104of the computing system100. Alternatively, or in addition, provisioning the storage capacity at step510may comprise informing the cache layer430of the storage capacity provisioned thereto through, inter alia, the storage interface131and/or other interface mechanism.

Step520may comprise modifying the storage space assigned to the cache layer430. Step520may be performed in response to the reserve analysis module338determining a different size for the reserve capacity394based on, inter alia, the write capacity profile346and reserve policy348, as disclosed herein.

In some embodiments, the reserve analysis module338may determine a size for the reserve capacity394based on, inter alia, the write load on the storage layer130. The write load on the storage layer130may be a function of one or more of the write capacity available to the storage layer130(e.g., the number of storage divisions370[1]-370[N] available in the write queue337), the IOPS rate of write requests performed on the storage layer130, a size and/or throughput of the write requests, a ratio of write to read requests, groomer performance, groomer priority, and so on. Step520may, therefore, comprise maintaining a write capacity profile346by use of, inter alia, the monitoring module339, as disclosed herein. Step520may further comprise receiving cache profiling information from the cache layer430.

In some embodiments, step520comprises increasing the storage capacity provisioned to the cache layer130in response to low write load conditions, and decreasing the storage capacity provisioned to the cache layer130in response to high write load conditions. Step520may further comprise informing the cache layer430of the change in storage capacity provisioned thereto. In response, the allocation module438of the cache layer430may be configured to add and/or remove cache tags432, as disclosed herein.

FIG. 6is a flow diagram of another embodiment600for managing write capacity of a storage medium140. Step610may comprise allocating storage capacity to a cache layer430. Step610may comprise allocating cache tags432for use by the cache layer430in accordance with the storage capacity provisioned to the cache layer430.

Step620may comprise modifying the cache tag allocation of step610. Step620may be performed in response to a request to modify the storage resources provisioned to the cache layer430. The request may be received from the reserve module138of the storage layer130, as disclosed herein. Modifying the cache tag allocation at step620may comprise reducing the size of the cache by: a) selecting cache tags432for eviction from the cache, and b) removing the selected cache tags432. Removing the cache tags432may comprise flushing the cache tags432to the backing store470by, inter alia, writing data of the cache tags432to the backing store470(if necessary). Removing the selected cache tags432may further comprise deallocating the cache tags432by, inter alit, removing the cache tags from the cache metadata434and/or issuing one or more de-allocation messages to the storage layer130indicating that data corresponding to the selected cache tags432does not need to be retained on the solid-state storage medium140.

FIG. 7is a flow diagram of another embodiment of a method700for adaptive storage reservations. Step710may comprise determining a reserve capacity394for the storage layer130. Step710may be based on characteristics of the deployment profile347A of the write capacity profile346. In some embodiments, step710may comprise reserving a pre-determined or default amount of reserve capacity394. Step710may comprise reporting the storage capacity, of the storage device141as the available storage capacity392, which may differ from the frill physical storage capacity390of the storage medium140. Step710may further comprise provisioning storage capacity to one or more I/O clients106, such as the cache layer430, as disclosed herein.

Step720may comprise developing a write capacity profile346by use of, inter alia, the monitoring module339. Step720may comprise monitoring operating conditions of the storage layer130, including, but not limited to: write load, write IOPS, ratio of write operations to read operations, groomer performance, write stall conditions (if any), groomer activity, write capacity availability, I/O client106demands and/or requests, and the like. Step720may comprise receiving profiling information from other I/O clients106, such as cache profiling information from the cache layer430.

Step730may comprise evaluating the write capacity profile information346and/or reserve policy348in order to determine whether the reserve capacity394should be modified. Step730may comprise determining an optimal reserve capacity394for the storage layer130. The optimal reserve capacity394may be determined by applying configuration parameters349A, such as QoS policies, configuration parameters, and/or the like, to the operating conditions of the storage layer130as indicated by the write capacity profile346. Alternatively, or in addition, step730may comprise evaluating an optimization criterion349B configured to weight performance characteristics according to configuration preferences of the I/O) clients106, as disclosed herein.

Step740may comprise determining whether to modify the reserve capacity394. Step740may comprise comparing the reserve capacity394determined at step740(e.g., the optimal reserve capacity742) to the current reserve capacity394. Step740may comprise determining to modify the reserve capacity740in response to the optimal reserve capacity394differing from the current reserve capacity394by more than a threshold. The threshold of step740may be configured to prevent excessive modifications to the reserve capacity394(e.g., thrashing). In some embodiments, steps730and/or740may comprise heuristics feedback mechanisms configured to prevent modifications to the reserve capacity394due to transient and/or short-term operating conditions.

In response to determining that the reserve capacity394is to be modified, the flow may continue to step750. Step750may comprise modifying the reserve capacity394(and available capacity392) in accordance with the optimal reserve capacity determined at step730. As disclosed above, modifying the reserve capacity394may comprise modifying storage capacity allocations to one or more I/O clients106. Step750may comprise informing the I/O clients106of the change in available storage capacity392. In some embodiments, step750comprises issuing a request to modify the storage capacity to one or more I/O clients106(e.g., the cache layer430). Step750may further comprise implementing the modification in response to receiving an acknowledgement from the one or more I/O clients106.

FIG. 8is a flow diagram of another embodiment of a method800for adaptive storage reservations. Step810may comprise allocating cache entries (e.g., cache tags432) of a cache layer430. Step810may comprise allocating the cache entries in accordance with the storage resources and/or capacity available to the cache layer430in a storage device141.

Step820may comprise populating the cache entries with data of a primary storage system, such as the backing store470. Populating the cache entries may comprise admitting data of the primary storage into the cache by, inter cilia, storing data of the primary storage on the storage medium140using the storage layer130.

Step830may comprise providing cache profiling information to the storage layer130. The cache profiling information may include, but is not limited to: access metrics of the cache entries (access metrics of LBAs within the BSAS472), cache write load (e.g., write IOPS), cache read load (e.g., read IOPS), cache hit rate, cache eviction rate, and/or the like. Step830may, therefore, comprise maintaining cache profiling information pertaining to the cache, providing access to the cache profiling information to the storage layer130and/or transmitting the cache profiling information to the storage layer130. The monitoring module339of the storage layer130may be configured to incorporate the cache profiling information into a write capacity profile346, which may be used to determine an optimal reserve capacity394, as disclosed herein.

Step840may comprise receiving a request to modify the storage capacity allocated to the cache layer430. Step840may be received from the storage layer130in response to the reserve analysis module338determining a different optimal reserve capacity394by use of the write capacity profile346and/or reserve policy348, as disclosed herein.

Step850may comprise modifying the cache entries in accordance with the modified storage capacity of step840. Step850may comprise adding or removing cache entries. Adding cache entries may comprise appending and/or inserting additional cache entries into cache metadata434for use by the admission module444to cache additional data of the primary storage. Removing cache entries may comprise a) selecting cache entries to remove based on, inter alia, cache access metadata446maintained by the cache layer430, b) removing the selected cache entries by, inter alia, flushing the cache entries to the backing store and/or deallocating cache entries in the cache metadata434and/or storage layer130.

Step860may comprise acknowledging the request of step840. The request may be acknowledged in response to modifying the cache entries at step850(e.g., flushing the cache entries that are to be removed).

This disclosure has been made with reference to various exemplary embodiments. However, those skilled in the art will recognize that changes and modifications may be made to the exemplary embodiments without departing from the scope of the present disclosure. For example, various operational steps, as well as components for carrying out operational steps, may be implemented in alternative ways depending upon the particular application or in consideration of any number of cost functions associated with the operation of the system (e.g., one or more of the steps may be deleted, modified, or combined with other steps). Therefore, this disclosure is to be regarded in an illustrative rather than a restrictive sense, and all such modifications are intended to be included within the scope thereof. Likewise, benefits, other advantages, and solutions to problems have been described above with regard to various embodiments. However, benefits, advantages, solutions to problems, and any element(s) that may cause any benefit, advantage, or solution to occur or become more pronounced are not to be construed as a critical, a required, or an essential feature or element. As used herein, the terms “comprises,” “comprising,” and any other variation thereof are intended to cover a non-exclusive inclusion, such that a process, a method, an article, or an apparatus that comprises a list of elements does not include only those elements but may include other elements not expressly listed or inherent to such process, method, system, article, or apparatus. Also, as used herein, the terms “coupled,” “coupling,” and any other variation thereof are intended to cover a physical connection, an electrical connection, a magnetic connection, an optical connection, a communicative connection, a functional connection, and/or any other connection.

Additionally, as will be appreciated by one of ordinary skill in the art, principles of the present disclosure may be reflected in a computer program product on a machine-readable storage medium having machine-readable program code means embodied in the storage medium. Any tangible, non-transitory machine-readable storage medium may be utilized, including magnetic storage devices (hard disks, floppy disks, and the like), optical storage devices (CD-ROMs, DVDs, Blu-ray discs, and the like), flash memory, and/or the like. These computer program instructions may be loaded onto a general purpose computer, special purpose computer, or other programmable data processing apparatus to produce a machine, such that the instructions that execute on the computer or other programmable data processing apparatus create means for implementing the functions specified. These computer program instructions may also be stored in a machine-readable memory that can direct a computer or other programmable data processing apparatus to function in a particular manner, such that the instructions stored in the machine-readable memory produce an article of manufacture, including implementing means that implement the function specified. The computer program instructions may also be loaded onto a computer or other programmable data processing apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer-implemented process, such that the instructions that execute on the computer or other programmable apparatus provide steps for implementing the functions specified.