Adaptive ingest throttling in layered storage systems

A method of accepting writes in a multilayered storage system is provided. The method includes (a) monitoring a rate of flushing of data from a first data storage component to a second data storage component; (b) setting an intake rate for the first data storage component based on the monitored flushing rate; and (c) throttling writes to the first data storage component based on the set intake rate. An apparatus, system, and computer program product for performing a similar method are also provided.

BACKGROUND

Data storage systems are arrangements of hardware and software in which storage processors are coupled to arrays of non-volatile storage devices, such as magnetic disk drives, electronic flash drives, and/or optical drives. The storage processors service storage requests arriving from host machines (“hosts”), which specify blocks, files, and/or other data elements to be written, read, created, deleted, etc. Software running on the storage processors manages incoming storage requests and performs various data processing tasks to organize and secure the data elements on the non-volatile storage devices.

Some storage systems are arranged in layers. For example, a storage driver stack may include several drivers that are arranged in order such that write commands arrive at an upper-level driver and, after some initial processing, pass to a next level driver, and then to another, until a lowest-level driver is reached. In some systems, different drivers are associated with different parts of physical storage, such as cache and persistent storage.

The foregoing background is presented for illustrative purposes to assist the reader in readily understanding the background in which the invention was developed. However, the foregoing background is not intended to set forth any admission that any particular subject matter has the legal effect of prior art.

SUMMARY

Conventional layered storage systems may operate sub-optimally when the rate at which data is received by a particular layer exceeds the rate at which the data can be flushed to a next layer. Although rate mismatches may be acceptable for short bursts, a layer may reach a maximum data buffering capacity if the mismatch continues, causing the layer to stop accepting further data. Some systems handle rate mismatches by utilizing a high watermark, so that, once a layer has reached a specified percentage of its capacity (e.g., 75%), throttling is applied to incoming writes to that layer, slowing an ingest rate of that layer until data can be flushed to the next layer. Throttling may be accomplished by introducing delays in acknowledgements to write commands received from a higher layer, such as from a host. Because throttling is usually applied when a layer is already almost full, some write commands may experience significant delays, while others may experience virtually none. Thus, these solutions suffer from “unfairness,” meaning that some writes are penalized much more than others. In addition, significant delays may lead to unacceptable results; for example, certain network filesystems may unmount a drive if a large delay is encountered.

Thus, it would be desirable to operate a multi-layered storage system with an adaptive throttling scheme that does not suffer from inconsistent delays and/or unfairness. This result may be accomplished by monitoring the flushing rate of a layer and using the monitored flushing rate to adaptively set a maximum intake rate for that layer going forward. If the actual intake rate begins to exceed the set maximum intake rate, throttling can be applied so that the actual intake rate returns below the set maximum intake rate. The throttling may be rate-based and implemented with fine granularity, allowing short or moderate delays to be utilized in most cases. In some embodiments, the monitored flushing rate may be used, with adjustments, to yield the set intake rate, such as, for example, by taking the flushing rate and using it with upward adjustment based on a data reduction ratio achieved by processing within the layer. As another example, the flushing rate may be taken and used with upward adjustment up in the event that additional capacity (e.g., processing capacity, storage bus capacity, etc.) is not fully-utilized.

In one embodiment, a method of accepting writes in a multilayered storage system is provided. The method includes (a) monitoring a rate of flushing of data from a first data storage component to a second data storage component; (b) setting an intake rate for the first data storage component based on the monitored flushing rate; and (c) throttling writes to the first data storage component based on the set intake rate. An apparatus, system, and computer program product for performing a similar method are also provided.

The foregoing summary is presented for illustrative purposes to assist the reader in readily grasping example features presented herein. However, the foregoing summary is not intended to set forth required elements or to limit embodiments hereof in any way.

DETAILED DESCRIPTION OF THE INVENTION

Embodiments are directed to techniques for operating a multi-layered storage system with an adaptive throttling scheme that does not suffer from inconsistent delays and/or unfairness. This result may be accomplished by monitoring the flushing rate of a layer, and using the monitored flushing rate to adaptively set a maximum intake rate for that layer going forward. If the actual intake rate begins to exceed the set maximum intake rate, throttling can be applied so that the actual intake rate returns below the set maximum intake rate. The throttling may be rate-based and implemented with fine granularity, allowing short or moderate delays to be utilized in most cases. In some embodiments, the monitored flushing rate may be used, with adjustments, to yield the set intake rate, such as, for example, by taking the flushing rate and using it with upward adjustment based on a data reduction ratio achieved by processing within the layer. As another example, the flushing rate may be taken and used with upward adjustment up in the event that additional capacity (e.g., processing capacity, storage bus capacity, etc.) is not fully-utilized.

FIG. 1depicts an example data storage system (DSS)30. DSS30may include one or more computing devices32. Each computing device32may be any kind of computing device or collection (or cluster) of computing devices, such as, for example, a personal computer, workstation, server computer, enterprise server, data storage array device, laptop computer, tablet computer, smart phone, mobile computer, etc.

Each computing device32at least includes processing circuitry36and memory40. In some embodiments, a computing device32may also include persistent storage as well as various kinds of interfaces (not depicted). Computing device32also includes interconnection circuitry.

Processing circuitry36may be any kind of processor or set of processors configured to perform operations, such as, for example, a microprocessor, a multi-core microprocessor, a digital signal processor, a system on a chip, a collection of electronic circuits, a similar kind of controller, or any combination of the above. As depicted processing circuitry36includes a plurality of processing cores37(depicted as cores37(i),37(ii), . . . ).

Memory40may be any kind of digital system memory, such as, for example, random access memory (RAM). Memory40stores an operating system (OS, not depicted) in operation (e.g., a Linux, UNIX, Windows, MacOS, or similar operating system). Memory40also stores a monitoring module42, a setting module44, a throttling module46, and other software modules which each execute on processing circuitry36. Memory40may also store various other data structures used by the OS, monitoring module42, setting module44, throttling module46, and various other applications (not depicted).

In some embodiments, memory40may also include a persistent storage portion (not depicted). Persistent storage portion of memory40may be made up of one or more persistent storage devices, such as, for example, magnetic disks, flash drives, solid-state storage drives, or other types of storage drives. Persistent storage portion of memory40is configured to store programs and data even while the computing device32is powered off. The OS, applications, monitoring module42, setting module44, and throttling module46are typically stored in this persistent storage portion of memory40so that they may be loaded into a system portion of memory40upon a system restart or as needed. The monitoring module42, setting module44, and throttling module46, when stored in non-transitory form either in the volatile portion of memory40or in persistent portion of memory40, each form a computer program product. The processing circuitry36running one or more applications thus forms a specialized circuit constructed and arranged to carry out the various processes described herein.

DSS30also includes a first data storage component50and a second data storage component62. In some embodiments, first data storage component50is a cache (e.g., made up of nonvolatile memory or mirrored or battery-backed volatile memory) and second data storage component62is persistent storage configured for long-term or medium-term storage (e.g., for storage meant to last for days or longer). This persistent storage may include any kind of persistent storage devices, such as, for example, hard disk drives, solid-state storage devices (SSDs), flash drives, etc. Storage interface circuitry (not depicted) controls and provides access to the persistent storage. Storage interface circuitry may include, for example, SCSI, SAS, ATA, SATA, FC, M.2, and/or other similar controllers and ports.

In other embodiments, first data storage component50is an upper-layer driver in an I/O driver stack, while second data storage component62is a lower-layer driver in the I/O driver stack. In these embodiments, first data storage component50is typically a buffered driver that is able to temporarily store a limited amount of data, typically subject to a capacity limit. In yet other embodiments, data storage components50,62may be other layers of storage in a set of layers of storage.

In some embodiments, data storage components50,62may be part of computing device32, while in other embodiments, one or both of data storage components50,62may be located on another computing device or apparatus (e.g., a data storage array) separate from the computing device32.

In operation, first data storage component50receives commands54that include respective input data52. In some embodiments, the input data52of each write command may be a page or block of data. In some of these embodiments, each page or block has a standardized size (e.g., 4 kilobytes, 8 kilobytes, etc.), although in other embodiments, various block sizes may be allowed. In some embodiments, processing circuitry36operates to transform input data52into output data60, which is in a form ready to be sent down to the second data storage component62. For example, processing circuitry36may perform compression, deduplication, and or reordering/reorganization (e.g., placing in address order) operations on the input data52to yield output data60. In some embodiments, output data60may be an extent of data that is able to hold around 1,000 compressed blocks (e.g., output data60may be arranged as extents 2 megabytes in size). Thus, the input data52may be altered (e.g., compressed) and reorganized to become output data60. However, the first data storage component50only has a limited capacity, so the output data60must be flushed down to the second data storage component62at some point. In some embodiments, every so often (e.g., every 1 second or 10 seconds), a flushing operation operates to flush some of the output data60down to the second data storage component62, at which point its space within the first data storage component50may be freed for new input data52. In some embodiments, all output data60that has been placed into complete form (e.g., containing a maximum number of compressed pages that have been placed in the correct order) is flushed during each flushing cycle. In other embodiments, a least-recently-used or least-recently-accessed list is used to only flush some of the output data60in a cycle.

Regardless, over the course of a cycle, monitoring module42monitors the flushing activity to calculate a flushing rate64. For example, in a 10-second cycle, thirty 2-megabyte (MB) extents of output data60may be flushed, which might yield a flushing rate64of 6 MB per second.

After each flushing cycle, setting module44may operate to generate a maximum intake rate66based on the monitored flushing rate. In some embodiments, the intake rate66may be set to be equal to the flushing rate64. In some embodiments, the flushing rate64is multiplied by an average data reduction ratio (i.e., the average factor by which data is reduced during processing from input data52to output data60) to yield the maximum intake rate66. Thus, given a flushing rate64equal to 6 MB per second, the maximum intake rate66may be set to be 24 MB per second, assuming an average data reduction ratio of 4 times. In some embodiments, the flushing rate64is divided by a utilization of processing and/or storage resources to yield the maximum intake rate66. Thus, for example, if only 1/10 of available resources during a flushing cycle are used to flush output data60to the second data storage component62, then ten times more output data60could have been flushed were there a need to do so. Therefore, given a flushing rate64equal to 6 MB per second, the maximum intake rate66may be set to be 60 MB per second. In some embodiments, the flushing rate64is both multiplied by an average data reduction ratio and divided by a utilization of processing and/or storage resources to yield the maximum intake rate66. Thus, using the values from the above examples, the maximum intake rate66may be set to be 240 MB per second.

Afterwards, in a next intake cycle (which may or may not coincide with the flushing cycles), throttling module46operates to throttle the incoming write commands54so that the input data52is received, on average, no faster than the set maximum intake rate66. In some embodiments, this may be achieved by monitoring the average intake rate and applying delays if it gets too high. In an example, the maximum intake rate66is set to 240 MB per second and the intake cycle is 10 seconds long; if, after 2 seconds more than 480 MB (e.g., 520 MB) of input data52have been received, then throttling module46applies delays to the incoming write commands so that the intake rate over the rest of the intake cycle is reduced. Since applying an average rate of 240 MB per second over 10 seconds yields 2400 MB, no more than 2400−520=1880 MB should be received over the rest of the cycle (average intake rate drops from 260 MB per second over the first two seconds to no more than 235 MB per second over the last eight seconds). This may be accomplished by delaying sending an acknowledgment signal56back to the initiating host or application for each write command. That works to slow the intake rate because an initiating host or application will refrain from sending subsequent write commands54until a previous write command54has been acknowledged. Since the rate only needs to be slowed by a small amount, only a small amount of delay in returning each acknowledgment signal56is needed (e.g., 5 milliseconds). In other embodiments, throttling module46applies throttling using techniques other than application of delays

Computing device32may also include network interface circuitry (not depicted), which may include one or more Ethernet cards, cellular modems, Fibre Channel (FC) adapters, Wireless Fidelity (Wi-Fi) wireless networking adapters, and/or other devices for connecting to a network (not depicted).

FIG. 2illustrates an example method100performed by DSS30for operating a multi-layered storage system with an adaptive throttling scheme. It should be understood that any time a piece of software (e.g, monitoring module42, setting module44, throttling module46) is described as performing a method, process, step, or function, what is meant is that a computing device32on which that piece of software is running performs the method, process, step, or function when executing that piece of software on its processing circuitry36. It should be understood that one or more of the steps or sub-steps of method100may be omitted in some embodiments. Similarly, in some embodiments, one or more steps or sub-steps may be combined together or performed in a different order.

In step110, monitoring module42monitors a rate of flushing (i.e., the flushing rate64) of data (e.g., output data60) from a first data storage component50(e.g., a cache, an upper-layer storage driver, etc.) to a second data storage component62(e.g., long-term persistent storage, a lower-layer storage driver, etc.). In some embodiments, step110includes sub-step112,114, and/or118. In sub-step112, the monitoring is performed over a first time interval (i.e., a flushing interval). The flushing rate64over each flushing interval is recorded and then used in step120.

In sub-step114, the monitoring module42also measures a utilization of system resources that are applied to flushing (e.g., during the flushing interval). In some embodiments, this may include (sub-step115) measuring an amount of processing resources actually devoted to flushing as a percentage of a maximum amount of processing resources that is permitted to be devoted to flushing. For example, if the flushing interval is ten seconds long and up to ten cores37are permitted to be assigned to performing flushing operations, then the number of seconds during which each core37performs flushing may be measured and summed, dividing by the maximum of 100 core-seconds. Thus, if one core37(i) spends 2 seconds flushing, and a second core37(ii) spends 2.5 seconds flushing, the utilization ratio may be calculated as (2+2.5)/100=4.5%. It should be understood that this calculation is presented by way of example only. In some embodiments, rather than the flushing being the limiting factor in the speed of emptying out the first data storage layer50, the processing of input data50into output data60(e.g., compressing, deduplicating, and reordering) may be the limiting factor, in which case the utilization of cores dedicated to processing input data50into output data60may be measured, or it may be some combination of the utilization of flushing and processing input data50into output data60.

In some embodiments, instead of measuring the utilization of cores37in step115, monitoring module42may instead (sub-step116) measure an amount of storage resources actually devoted to flushing as a percentage of a maximum amount of storage resources that that is permitted to be devoted to flushing. For example, the utilization of a storage bus and/or the utilization of storage device transaction rates (e.g., in I/Os per second) of the second data storage component62may be measured. In some embodiments, sub-steps115and116may be combined, using whichever yields a more limiting result. For example, if the processing utilization is 4.5%, but the utilization of storage device transaction rates is 25%, then the utilization of storage utilization device transaction rates value would be used instead.

Step110also includes sub-step118, in which monitoring module42measures the quantity of data (e.g., output data60) flushed from the first data storage component50(e.g., during the flushing interval).

Then, in step120, which may be performed after the conclusion of a flushing interval, the setting module44sets the maximum intake rate66for the first data storage component50based on the monitored flushing rate64. In some embodiments, this means (sub-step122) setting a maximum amount of data (e.g., input data52) allowed to be received into the first data storage component50per unit time, on average.

In some embodiments, step120includes sub-step124and/or sub-step126. In sub-step124, the measured amount of data (e.g., output data60) flushed or the flushing rate64is adjusted up based on the utilization ratio measured in sub-step114(if the utilization ratio is less than 100%), such as by dividing the measured amount of data flushed or the flushing rate64by the utilization ratio. In sub-step126, the measured amount of data (e.g., output data60) flushed or the flushing rate64is adjusted up based on a data reduction ratio or a compression ratio achieved between the input data52and the output data60, such as by multiplying the measured amount of data flushed or the flushing rate64by the data reduction ratio or compression ratio. The compression ratio takes into account the reduction in size due to compression while the data reduction ration takes into account the reduction in size due to both compression and deduplication. In some embodiments, the data reduction ratio and/or compression ratio may be measured directly, while in others it may be estimated (such as by using regression or machine learning based on various inputs) or approximated (such as by assuming a typical data reduction ratio or compression ratio, such as a value of 4 or 6, for example).

In some embodiments, step120includes sub-step128. In sub-step128, the maximum intake rate66is not set directly from the measured flushing rate64. Rather, whatever value the maximum intake rate66was set to previously is adjusted up or down based on whether the measured flushing rate64has gone up or down (in some embodiments as corrected by sub-steps124,126). In some embodiments, this may be done by measuring (as part of step110) a latency with which various writes from the first data storage component50to the second data storage component62were accomplished, and if the latency has increased from a previous time interval, decreasing the maximum intake rate66. Conversely, if the latency has decreased from a previous time interval, sub-step128would instead increase the maximum intake rate66. Then, in step130, throttling module46throttles writes54to the first data storage component50based on the set maximum intake rate66. In some embodiments (sub-step132), throttling module46performs this throttling over a second time interval (i.e., a throttling interval) entirely subsequent to the first time interval (i.e., the flushing interval). In some embodiments, the throttling interval may be of the same length as the flushing interval, but in other embodiments it may be shorter or longer. If the throttling interval is the same length as the flushing interval, it may coincide exactly with the following flushing interval or the one after that, or it may be offset from the flushing intervals.

In some embodiments, step130may include sub-steps134-138. In step134, throttling module46tracks an amount of input data52(e.g., by measuring a number of pages or blocks) received for intake into the first data storage component50(e.g., during the throttling interval). This tracking may be performed throughout the throttling interval. For example, if the throttling interval is 10 seconds long, the amount of data may be measured every second or at a finer granularity. Then (after each measurement), in sub-step135, throttling module46determines whether or not the monitored amount of data received for intake divided by the elapsed time exceed the set maximum intake rate. If not, operation proceeds with sub-step138in which throttling module46refrains from applying delays to incoming write commands54(at least until a subsequent performance of sub-step135yields an affirmative result). If sub-step135yields an affirmative result, then operation proceeds with sub-step136. In sub-step136, throttling module146applies delays to reduce the intake rate (e.g., for the remainder of the throttling interval). In some embodiments, sub-step136includes sub-step137, in which throttling module46, for one or more of a plurality of applications or hosts that have sent write commands54to the DSS30, delays returning acknowledgment signals56in response to the write commands54sent by the one or more applications or hosts, which causes those applications or hosts to refrain from sending further write commands54for the amount of the delay.

FIG. 3depicts an example arrangement200of first data storage component50, according to some embodiments. Arrangement200includes a ring buffer201stored in cache (or in buffered memory of a storage driver). Ring buffer201includes a set of metadata entries202that each include information about respective write commands54that have been received, such as a pointer208to an ingested page252(depicted as ingested pages252(a),252(b),252(c),252(d), . . . ) of input data52and a logical address where that data is supposed to be stored (e.g., a logical block address within a logical disk). As write commands54are received, new metadata entries202are added to a head204of the ring buffer201, and as the metadata entries202are processed (e.g., their respective ingested pages252are moved to output extents260), old metadata entries202are removed from a tail206of the ring buffer201.

A core assignment237may assign various cores37of the computing device32to different tasks. Thus, as depicted, core37(i) is assigned to perform intake of write commands54into the ring buffer201and associated ingested pages252. Cores37(ii),37(iii) are assigned to process ingested pages252for conversion into compressed pages222that are placed into output extents260. Cores37(iv),37(v) are assigned to flush output extents260down to the second data storage component62. Core37(vi) is assigned as idle. The assignment of cores37may change over time, although there may be a maximum number of cores37permitted to be assigned to any single type of task at any given time.

As depicted, ingested page252(a) is compressed into compressed page222(a) and stored in output extent260(1). Ingested page252(b) happens to be identical to ingested page252(a), so deduplication is performed. Thus compressed page222(a) also represents ingested page252(b). Ingested page252(c) is compressed into compressed page222(c) and stored in output extent260(1). Ingested page252(d) is compressed into compressed page222(d) and stored in output extent260(2).

When an output extent260has become filled with compressed pages222(although, in some embodiments, uncompressed pages may also be stored in output extents260if they are not compressible), such that there is no more room in that output extent260for additional compressed pages222, that output extent260becomes eligible for flushing. In some embodiments, all eligible output extents260are flushed during the next flushing interval (if possible). In other embodiments, a minimum number of output extents260may be retained in cache at all times with the output extents260that have been accessed (either for read or write) most recently being prioritized for retainment (e.g., using a least-recently accessed linked list to schedule output extents260for flushing).

The ratio of the size of the received ingested pages252in comparison to the final size of all the output extents260that represent those ingested pages252is the data reduction ratio achieved for that data. In the long-term, this ratio should be roughly constant, although there may be fluctuations in the short-term based on the type of data received and other factors. It may be calculated continuously or repeatedly for each flushing interval, or it may be estimated over the course of one or more flushing intervals for use in future throttling intervals. It may also be approximated.

Thus, techniques have been presented for operating a multi-layered storage system30with an adaptive throttling scheme that does not suffer from significant delays and/or unfairness. This result may be accomplished by monitoring the flushing rate64of a layer50and using the monitored flushing rate64to adaptively set a maximum intake rate66for that layer50going forward. If the actual intake rate begins to exceed the set maximum intake rate66, throttling can be applied so that the actual intake rate returns below the set maximum intake rate66. The throttling may be rate-based and implemented with fine granularity, allowing short or moderate delays to be utilized in most cases. In some embodiments, the monitored flushing rate64may be used, with adjustments to yield the set maximum intake rate66, such as, for example, by taking the flushing rate66and using it with upward adjustment based on a data reduction ratio achieved by processing within the layer50. As another example, the flushing rate66may be taken and used with upward adjustment in the event that additional capacity (e.g., processing capacity, storage bus capacity, etc.) is not fully-utilized.

As used throughout this document, the words “comprising,” “including,” “containing,” and “having” are intended to set forth certain items, steps, elements, or aspects of something in an open-ended fashion. Also, as used herein and unless a specific statement is made to the contrary, the word “set” means one or more of something. This is the case regardless of whether the phrase “set of” is followed by a singular or plural object and regardless of whether it is conjugated with a singular or plural verb. Further, although ordinal expressions, such as “first,” “second,” “third,” and so on, may be used as adjectives herein, such ordinal expressions are used for identification purposes and, unless specifically indicated, are not intended to imply any ordering or sequence. Thus, for example, a “second” event may take place before or after a “first event,” or even if no first event ever occurs. In addition, an identification herein of a particular element, feature, or act as being a “first” such element, feature, or act should not be construed as requiring that there must also be a “second” or other such element, feature or act. Rather, the “first” item may be the only one. Although certain embodiments are disclosed herein, it is understood that these are provided by way of example only and that the invention is not limited to these particular embodiments.

While various embodiments have been particularly shown and described, it will be understood by those skilled in the art that various changes in form and details may be made therein without departing from the spirit and scope of the appended claims.

For example, although various embodiments have been described as being methods, software embodying these methods is also included. Thus, one embodiment includes a tangible non-transitory computer-readable storage medium (such as, for example, a hard disk, a floppy disk, an optical disk, flash memory, etc.) programmed with instructions, which, when performed by a computer or a set of computers, cause one or more of the methods described in various embodiments to be performed. Another embodiment includes a computer that is programmed to perform one or more of the methods described in various embodiments.

Furthermore, it should be understood that all embodiments which have been described may be combined in all possible combinations with each other, except to the extent that such combinations have been explicitly excluded.