Patent ID: 12197736

DETAILED DESCRIPTION

Embodiments of the improved technique will now be described. One should appreciate that such embodiments are provided by way of example to illustrate certain features and principles but are not intended to be limiting.

An improved technique of managing the rate of I/O (Input/Output) request processing includes a token-bucket arrangement having first, second, and third token buckets. The first token bucket is provided with sufficient tokens to accommodate an expected baseline level of I/O requests, whereas the second token bucket is provided with sufficient tokens to accommodate an expected excess level of I/O requests during bursts. The third token bucket is provided with tokens at predefined intervals and limits a total amount of bursting available during those intervals.

FIG.1shows an example environment100in which embodiments of the improved technique can be practiced. Here, multiple hosts110are configured to access a data storage system116over a network114. An administrative machine118may also be configured to access the data storage system116, e.g., for enabling an administrator to run an administrative program118afor configuring the data storage system116.

The data storage system116includes one or more nodes120(e.g., node120aand node120b), and storage180, such as magnetic disk drives, electronic flash drives, and/or the like. Nodes120may be provided as circuit board assemblies or blades, which plug into a chassis (not shown) that encloses and cools the nodes. The chassis has a backplane or midplane for interconnecting the nodes120, and additional connections may be made among nodes120using cables. In some examples, the nodes120are part of a storage cluster, such as one which contains any number of storage appliances, where each appliance includes a pair of nodes120connected to shared storage. In some arrangements, a host application runs directly on the nodes120, such that separate host machines110need not be present. No particular hardware configuration is required, however, as any number of nodes120may be provided, including a single node, in any arrangement, and the node or nodes120can be any type or types of computing device capable of running software and processing host I/O's.

The network114may be any type of network or combination of networks, such as a storage area network (SAN), a local area network (LAN), a wide area network (WAN), the Internet, and/or some other type of network or combination of networks, for example. In cases where hosts110are provided, such hosts110may connect to the node120using various technologies, such as Fibre Channel, iSCSI (Internet small computer system interface), NVMeOF (Nonvolatile Memory Express (NVMe) over Fabrics), NFS (network file system), and CIFS (common Internet file system), for example. As is known, Fibre Channel, iSCSI, and NVMeOF are block-based protocols, whereas NFS and CIFS are file-based protocols. The node120is configured to receive I/O requests112according to block-based and/or file-based protocols and to respond to such I/O requests112by reading or writing the storage180.

The depiction of node120ais intended to be representative of all nodes120, although nodes120may differ from each other in various details. As shown, node120aincludes one or more communication interfaces122, a set of processors124, and memory130. The communication interfaces122include, for example, SCSI target adapters and/or network interface adapters for converting electronic and/or optical signals received over the network114to electronic form for use by the node120a. The set of processors124includes one or more processing chips and/or assemblies, such as numerous multi-core CPUs (central processing units). The memory130includes both volatile memory, e.g., RAM (Random Access Memory), and non-volatile memory, such as one or more ROMs (Read-Only Memories), disk drives, solid state drives, and the like. The set of processors124and the memory130together form control circuitry, which is constructed and arranged to carry out various methods and functions as described herein. Also, the memory130includes a variety of software constructs realized in the form of executable instructions. When the executable instructions are run by the set of processors124, the set of processors124is made to carry out the operations of the software constructs. Although certain software constructs are specifically shown and described, it is understood that the memory130typically includes many other software components, which are not shown, such as an operating system, various applications, processes, and daemons.

As further shown inFIG.1, the memory130“includes,” i.e., realizes by execution of software instructions, an I/O rate manager140, a data read/write manager150, and persistent storage structures160. The I/O rate manager140is configured to limit the speed at which I/O requests112may be processed. The read/write manager150is configured to perform reading and/or writing of host data, and the persistent storage structures160are configured to persistently store and organize host data, e.g., in the form of LUNs (Logical UNits), volumes, file systems, virtual machine disks, and the like. One should appreciate that the I/O rate manager140, read/write manager150, and persistent storage structures may each have memory-resident components but may also include components that are persistently stored in storage180.

In example operation, hosts110issue I/O requests112to the data storage system116. Node120receives the I/O requests112at the communication interfaces122and initiates further processing. Such processing may include operation of the I/O rate manager140to limit the rate at which I/O requests112may be forwarded to the read/write manager150or to other downstream components for processing, i.e., for effectuating specified read and/or write operations. Read operations may be performed by reading addresses specified in read I/O requests in the persistent storage structures160(or within cache, not shown). Likewise, write operations may be performed by writing data specified in write I/O requests to specified addresses in persistent storage structures (or cache).

In an example, the I/O rate manager140operates based on settings, which may be configured, for example, by an administrator, e.g., via the administrative program118a. To this end, the administrative program118amay include a graphical user interface (GUI) or a command line interface (CLI) for enabling administrators to configure settings. Settings for I/O processing speed may be configurable in any desired manner, such as per host110, per host application, per volume, per group of volumes, or in any other desired manner. Settings may be configurable for desired groups, e.g., per user group, per tenant, or the like. Alternatively, the same general settings may be applied to all users. In accordance with improvements hereof, settings are provided for configuring baseline I/O processing rate separately from burst I/O processing rate. In addition, settings are provided for specifying a total amount of bursting allowed within a given period, e.g., within a predefined interval.

FIG.2shows an example arrangement of the I/O rate manager140in additional detail. Here, three separate token buckets are provided, a first token bucket (Bucket A), a second token bucket (Bucket B), and a third token bucket (Bucket S). A token generator210is configured to provide tokens220to token buckets A, B, and S at respective rates and/or at respective intervals. Although a single token generator210is shown, separate token generators alternatively may be provided, such as one for each of the token buckets A, B, and S. Token generator210is preferably implemented in software.

Bucket A receives tokens220at a first rate, RA, which is determined so as to satisfy an expected baseline level of I/O requests112. For example, the rate RAat which tokens are added to Bucket A closely matches the rate at which tokens are expected to be consumed (subtracted) from Bucket A in exchange for processing the baseline level of I/O requests112. As I/O requests112arrive from hosts, for example, such I/O requests are processed in exchange for tokens, which are expected to be consumed from Bucket A at approximately the same rate RAat which they are added.

The exchange relationship between tokens and I/O requests can be established in a variety of ways, such as based on numbers of I/O requests, whether the I/O requests are reads or writes, and/or amounts of data to be read or written. In a simple example, one token may be exchanged for processing one I/O request112, regardless of whether it is a read or a write. In another example, one token may be exchanged for each kilobyte of data to be read or written. For instance, a 1-kB (kilobyte) read may be exchanged for one token, whereas a 10-kB write may be exchanged for 10 tokens. Thus, for example, if the expected baseline level of I/O request processing is 100 kB/s (kilobytes per second), the rate RAmay be set to 100 tokens per second. For ease of processing, the exchange relationship is preferably simple and is based on readily available data; however, arbitrarily complex exchange relationships may also be used.

As further shown inFIG.2, Bucket B receives tokens220at a second rate, RB, which is established to satisfy an expected excess level of I/O requests112associated with bursts. For example, if the baseline level of I/O request processing is 100 kB/s and the bursting level is 120 kB/s, then the excess level of I/O request processing would be 20 kB/s (120 kB/s−100 kB/s). To accommodate such excess levels of I/O request processing, the rate RBmay be set to the token-rate equivalent of 20 kB/s, e.g., 20 tokens per second assuming one token is valued at 1 kB. It can thus be seen in this example that Bucket B is filled more slowly than Bucket A (RB<RA), even though bursting involves a greater rate of I/O requests112than does baseline I/O processing. This arrangement reflects the fact that the bursting rate of I/O requests is related to the sum of the baseline rate RAand the excess rate RBassociated with bursting, rather than just with the bursting rate RB.

In example operation, I/O requests arrive and the I/O rate manager140checks Bucket A for sufficient tokens to satisfy those I/O requests. The tokens available from Bucket A are generally sufficient to exchange for incoming I/O requests112provided that the rate of those requests does not exceed the expected baseline rate. As long as Bucket A has enough tokens220to satisfy the incoming requests, no tokens are drawn from Bucket B. But if Bucket A runs out of tokens220, indicating that the expected baseline level of I/O requests112has been exceeded (i.e., a burst is occurring), tokens220may then be drawn from Bucket B, which may continue to pay out tokens until the burst is complete.

If the rate of I/O requests112exceeds the expected bursting rate, Bucket A and Bucket B may both run out of tokens220. Once this occurs, tokens are no longer available to exchange for I/O requests112. New I/O requests may then be queued, e.g., as I/O requests112qin queue230, where they may wait in line for processing until sufficient tokens220again become available. Poller240may regularly check for queued requests112qand forward them for processing, in the order received.

The arrangement as described so far accommodates both baseline levels of I/O requests and bursts, but it nevertheless suffers from a deficiency, as nothing described so far limits the duration of bursting. Indeed, bursting may continue at the rate based on RA+RBindefinitely, with the two buckets A and B acting effectively as a single bucket.

In accordance with further improvements hereof, this deficiency is addressed by providing Bucket S (the Special bucket). Bucket S is limited in the tokens it receives to no greater than a maximum number P of tokens220during predefined intervals (reset intervals) of time, designated by T. For example, Bucket S may be refilled up to P tokens once per reset interval T, which may be a day, an hour, a week, or any other suitable interval of time. Upon the expiration of each reset interval T, the number of tokens220in Bucket S may be restored to the allowed maximum number P, such as 50, 100, 200, 1000, etc.

In operation, any time tokens are consumed from Bucket B (during bursts), an equal number of tokens is consumed from Bucket S. But once Bucket S runs out of tokens, no more tokens are allowed to be consumed from Bucket B, even if Bucket B still contains tokens. Only when Bucket S is replenished (at the end of the reset interval7) can tokens again be drawn from Bucket B. In this manner, Bucket S limits the overall amount of bursting available and prevents applications from sustaining high, bursting levels of I/O requests112all of the time.

Token generator210may replenish tokens220in buckets A, B, and S in any suitable manner. For Buckets A and B, for example, tokens220may be replenished continuously or at determined intervals, such as once per minute, once per hour, or the like. Typically, Buckets A and B are replenished at different rates, i.e., RA< >RB, although circumstances may arise in which these rates are the same. Rates RAand RBare typically constant and may be changed only by an administrator. This too is not a firm requirement, however, as rates RAand RBmay be varied automatically, e.g., in response to load predictions. Bucket S may be replenished once per reset interval T, although this also is not required. For example, if reset interval T is 24 hours and maximum token value P is 120, Bucket S may be topped off to 50 tokens (P/24) every hour. A variety of approaches are feasible.

In some examples, Buckets A, B, and/or S are replenished in response to receipt of I/O requests112. For instance, when an I/O request112is received for processing, the I/O rate manager140may check the current time as well as the immediately previous time that a respective bucket was replenished, and then add a number of tokens based on the time difference and the rate of replenishment for the respective bucket.

In an example, Buckets A and B are not allowed to grow indefinitely (e.g., in the absence of I/O requests) but rather are limited in the maximum numbers of tokens they can contain, which may be referred to as respective “bucket sizes.” In an example, the sizes of Buckets A and B are set based on their respective rates, RAand RB. Thus, the size of Bucket A may be proportional to RAand the size if Bucket B may be proportional to RB. As indicated above, the size of Bucket S is P. A good estimate for P is the RB*t, where “t” is the expected burst duration. The size of Bucket S is typically much larger the size of either Bucket A or Bucket B.

FIG.3shows an example method300for configuring the I/O rate manager140. The method300may be performed, for example, by the administrative program118a, which may be operated by an administrator of the data storage system116, e.g., via a GUI or CLI.

At310, the administrative program118areceives inputs for configuring I/O processing rates. Such inputs may include, for example, an expected baseline I/O rate (e.g., I/O's per second or kB/s), an expected burst rate (e.g., I/O's per second or kB/s), a burst duration t (e.g., in minutes or other time units), and a reset interval T (e.g., in minutes or other time units). In some examples, expected baseline I/O rate and expected burst rate are constants for a given system, application, or user, such that the only inputs needed are burst duration t and reset interval T.

At320, the administrative program118adetermines a token feed rate RAfor Bucket A. For example, RAmay be based on the expected baseline I/O rate. At this time, the administrative program118amay also determine the size of Bucket A, e.g., based on the token feed rate RA.

At330, the administrative program118adetermines a token feed rate RBfor Bucket B. For example, RBmay be based on the difference between the expected burst I/O rate and the expected baseline I/O rate. At this time, the administrative program118amay also determine the size of Bucket B, e.g., based on the token feed rate RB.

At340, the administrative program118adetermines the size P for Bucket S. For example, P may be computed as RB*t, the expected burst duration.

The above-described acts of method300may be performed in any suitable order. In the event that different limits are desired for different entities (applications, hosts, volumes, and the like), the method300may be repeated for each such entity.

FIG.4shows an example method400of controlling the rate of I/O request processing. The method400is typically performed, for example, by the I/O rate manager140, which may reside in the memory130of node120aand may be run by the set of processors124. In method400, it is assumed that tokens220are being added to Buckets A, B, and S in the manner described above in connection withFIG.2. The focus of method400is on consumption (rather than replenishment) of tokens220.

As shown at the top ofFIG.4, an I/O request112arriving from a host110may enter the queue230(FIG.2), where the I/O request waits in line to be processed, i.e., in a first-in, first-out (FIFO) manner. Poller240regularly checks the queue230and forwards the next I/O request112qin line to step410for further processing. It is noted that enqueuing and polling may be avoided if the queue230is empty. In such cases, method400may instead begin at step410.

At410, the I/O rate manager140obtains the I/O request112and determines the exchange value of that I/O request in tokens220. As explained above, the exchange value may be a single token for a single I/O request. Alternatively, it may be one token per kilobyte read or written, or some other value. Here, as a general example, we assume that the exchange value of the I/O request112is N tokens.

At420, the I/O rate manager140determines whether Bucket A contains at least N tokens. If it does, then operation proceeds to430, whereupon the Bucket A is decremented by N tokens. At440, the I/O request112is further processed, e.g., by passing the I/O request to the read/write manager150for executing the requested read or write. Operation then returns to410, whereupon the I/O rate manager140awaits the next I/O request112or, if any I/O requests112qare waiting in the queue230, selects the next I/O request112qin line for processing. Operation then proceeds from there.

Returning to420, if Bucket A had had only M tokens, M<N, then the I/O request cannot be paid for from Bucket A alone. In this case, operation proceeds to450, whereupon the I/O rate manager140determines whether each of Buckets B and S contains at least N−M tokens, i.e., the balance of required tokens not available from Bucket A. If each of Buckets B and S contains at least N−M tokens, then operation proceeds to460, whereupon the buckets are decremented. For example, Bucket A is decremented by M tokens and Buckets B and S are each decremented by N−M tokens. Operation then proceeds again to440, whereupon the I/O request is processed as described above. Operation then returns to410, where a next I/O request may be obtained for processing.

Returning to450, if either Bucket B or Bucket S has fewer than N−M tokens, then the I/O request cannot immediately be processed. Instead, the I/O request is placed on the queue230, or it is kept in the queue if it had previously been obtained from the queue. In other examples, the I/O request may simply be failed, i.e., the node120amay inform the originating host110that the I/O request did not complete. Operation next returns to410, whereupon the next I/O request is obtained, either directly or from the queue, and the value of the next I/O request in tokens is determined. The method400is repeated in this manner indefinitely.

In the manner described, method400normally consumes tokens220from Bucket A for meeting baseline I/O processing demands. During bursts, method400may exhaust Bucket A and turn to Buckets B and S for needed tokens. But I/O requests are queued (or failed) if either Bucket B or Bucket S has fewer than the number of tokens needed. Generally speaking, Bucket B limits the extent of individual bursts, while Bucket S limits the total, overall amount of bursting that may be done during any reset interval T.

FIG.5shows an example method500that may be carried out in connection with the environment100and provides a summary of some of the features described above. The method500is typically performed, for example, by the software constructs described in connection withFIG.1, which reside in the memory130of the node120aand are run by the set of processors124. The various acts of method500may be ordered in any suitable way. Accordingly, embodiments may be constructed in which acts are performed in orders different from that illustrated, which may include performing some acts simultaneously.

At510, a plurality of I/O requests112are received. The I/O requests include read requests and/or write requests.

At520, the plurality of I/O requests112are processed in exchange for tokens220, such that each I/O request112is processed only if sufficient tokens220are available to process the I/O request112.

At530, the tokens are managed using first, second, and third token buckets, such as Bucket A, Bucket B, and Bucket S, respectively. The first token bucket (Bucket A) is provided with sufficient tokens220to accommodate an expected baseline level of I/O requests, and the second token bucket (Bucket B) is provided with sufficient tokens to accommodate an expected excess level of I/O requests112during bursts. The third token bucket (Bucket S) is provided with tokens at predefined intervals (T) and limits an overall amount of bursting available during the predefined intervals.

An improved technique has been described for managing the rate of I/O (Input/Output) request processing. The technique includes a token-bucket arrangement having first, second, and third token buckets. The first token bucket (Bucket A) is provided with sufficient tokens220to accommodate an expected baseline level of I/O requests112, whereas the second token bucket (Bucket B) is provided with sufficient tokens220to accommodate an expected excess level of I/O requests112during bursts. The third token bucket (Bucket S) is provided with tokens220at predefined intervals (T) and limits a total amount of bursting available during those intervals.

Having described certain embodiments, numerous alternative embodiments or variations can be made. For example, although the I/O rate manager140has been shown at a particular level of I/O processing (e.g., prior to read/write manager150), this is merely an example. Alternatively, the I/O rate manager140may be disposed at any suitable level of I/O request processing where it is desired to limit processing speed.

Further, although the processing of I/O requests112has been described as proceeding one I/O request at a time, where each I/O request has an equivalent token value, embodiments are not limited to this arrangement. For example, an alternative arrangement may process I/O requests in batches, where each batch is assigned an equivalent token value and is processed (e.g., inFIG.4) on a per-batch basis, rather than a per-I/O request basis.

Also, although embodiments have been described that involve one or more data storage systems, other embodiments may involve computers, including those not normally regarded as data storage systems. Such computers may include servers, such as those used in data centers and enterprises, as well as general purpose computers, personal computers, and numerous devices, such as smart phones, tablet computers, personal data assistants, and the like.

Further, although features have been shown and described with reference to particular embodiments hereof, such features may be included and hereby are included in any of the disclosed embodiments and their variants. Thus, it is understood that features disclosed in connection with any embodiment are included in any other embodiment.

Further still, the improvement or portions thereof may be embodied as a computer program product including one or more non-transient, computer-readable storage media, such as a magnetic disk, magnetic tape, compact disk, DVD, optical disk, flash drive, solid state drive, SD (Secure Digital) chip or device, Application Specific Integrated Circuit (ASIC), Field Programmable Gate Array (FPGA), and/or the like (shown by way of example as medium550inFIG.5). Any number of computer-readable media may be used. The media may be encoded with instructions which, when executed on one or more computers or other processors, perform the process or processes described herein. Such media may be considered articles of manufacture or machines, and may be transportable from one machine to another.

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. Also, a “set of” elements can describe fewer than all elements present. Thus, there may be additional elements of the same kind that are not part of the set. Further, ordinal expressions, such as “first,” “second,” “third,” and so on, may be used as adjectives herein for identification purposes. Unless specifically indicated, these ordinal expressions 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. Also, and unless specifically stated to the contrary, “based on” is intended to be nonexclusive. Thus, “based on” should be interpreted as meaning “based at least in part on” unless specifically indicated otherwise. Although certain embodiments are disclosed herein, it is understood that these are provided by way of example only and should not be construed as limiting.

Those skilled in the art will therefore understand that various changes in form and detail may be made to the embodiments disclosed herein without departing from the scope of the following claims.