Patent Description:
Cloud computing and storage is rapidly gaining in popularity. As more and more users and businesses switch their data needs to distributed storage systems, performance degradation of cloud services becomes increasingly important. Large data stores (e.g., databases) are frequently spread over multiple servers and horizontally partitioned (i.e., shards) to increase performance. Sharding of the databases often allows the servers to handle dynamic loads by increasing and decreasing resources in near real-time. However, there is a non-zero reaction time for increasing resources, and a sufficiently fast ramp-up of traffic may overload the underlying storage and cause performance degradation.

<CIT> teaches a server that manages a resource in a virtual environment used by a service. The server includes a load measurement unit, a load prediction unit, a performance measurement unit, a removing unit, a performance prediction unit, and a resource control unit. The load measurement unit measures a load on the service. The load prediction unit predicts a future load on the service, based on the measured load. The performance measurement unit measures a performance of the service. The removing unit removes influence due to the measured load from the measured performance. The performance prediction unit predicts a future performance of the service, based on the performance from which the influence due to the load has been removed. The resource control unit controls the resource, based on the predicted load and the predicted performance.

One aspect of the disclosure provides a method of detecting a traffic ramp-up rule violation. The method includes, receiving, at data processing hardware, data element retrieval requests that each request at least one data element from an information retrieval system. The information retrieval system includes a plurality of data elements. The method also includes determining, by the data processing hardware, a requests per second (RPS) for a key range of the information retrieval system based on a number of the data element retrieval requests received. The method also includes determining, by the data processing hardware, a moving average of RPS for the key range of the information retrieval system over a first time period based on the number of the data element retrieval requests received and determining, by the data processing hardware, a number of delta violations. Each delta violation includes a respective beginning instance in time when the RPS exceeded a delta RPS limit. The delta RPS limit is based on the moving average of RPS. For each delta violation, the method includes determining, by the data processing hardware, a maximum conforming load for the key range over a second time period and determining, by the data processing hardware, whether the RPS exceeded the maximum conforming load for the key range based on the beginning instance in time of the respective delta violation. The method also includes, when the RPS exceeded the maximum conforming load for the key range, determining, by the data processing hardware, that the delta violation corresponds to a full-history violation. The full-history violation is indicative of a degradation of performance of the information retrieval system.

Implementations of the disclosure may include one or more of the following optional features. In some implementations, determining whether the RPS exceeded the maximum conforming load for the key range based on the beginning instance in time of the respective delta violation includes determining, by the data processing hardware, a zero-history RPS limit. The zero-history RPS limit includes a function of a minimum of a historical zero-history RPS limit and the moving average of RPS. The method may also include determining, by the data processing hardware, a duration of time beginning at the beginning instance of the respective delta violation and ending when the RPS no longer exceeds the zero-history RPS limit. The method optionally includes determining, by the data processing hardware, a zero-history violation based on the duration of time that the RPS exceeded the zero-history RPS limit. In some examples, when the RPS exceeded the maximum conforming load for the key range, the method includes determining, by the data processing hardware, that the zero-history violation corresponds to one or more full-history violations.

In some implementations, the method further includes generating, by the data processing hardware, a request grid including a plurality of cells. Each cell represents a fixed-length time bucket of a key bucket and each key bucket includes a range of keys sized to represent a select average amount of requests. Determining the moving average of RPS may include determining a moving average of each key bucket. Optionally, each key bucket is sized to have the same average amount of requests. In some examples, determining the number of delta violations includes determining narrow-band candidate delta violations where each narrow-band candidate delta violation represents an instance in time when the RPS of the respective key bucket exceeds the delta RPS limit. The method may also include determining wide-band candidate delta violations from the narrow-band candidate delta violations where each wide-band delta violation includes neighboring narrow-band delta violations and determining, for each wide-band candidate delta violation, whether the wide-band candidate delta violation is a delta violation based on a quantity or intensity of the requests.

In some implementations, the maximum conforming load includes a maximum load the information retrieval system can maintain without degradation of performance. In some examples, the information retrieval system includes a dynamic range-sharded information retrieval system. Determining the maximum conforming load may include determining the maximum conforming load as a function of a number of data element retrieval requests previously received during a threshold window of time. Optionally, in between each adjacent pair of delta violations, the RPS does not exceed the delta RPS limit.

Another aspect of the disclosure provides a system for detecting traffic ramp-up rule violations. The system includes data processing hardware and memory hardware in communication with the data processing hardware. The memory hardware stores instructions that when executed on the data processing hardware cause the data processing hardware to perform operations. The operations include receiving data element retrieval requests that each request at least one data element from an information retrieval system. The information retrieval system includes a plurality of data elements. The operations also include determining a requests per second (RPS) for a key range of the information retrieval system based on a number of the data element retrieval requests received. The operations also include determining a moving average of RPS for the key range of the information retrieval system over a first time period based on the number of the data element retrieval requests received and determining a number of delta violations. Each delta violation includes a respective beginning instance in time when the RPS exceeded a delta RPS limit. The delta RPS limit is based on the moving average of RPS. For each delta violation, the operations include determining a maximum conforming load for the key range over a second time period and determining whether the RPS exceeded the maximum conforming load for the key range based on the beginning instance in time of the respective delta violation. The operations also include, when the RPS exceeded the maximum conforming load for the key range, determining that the delta violation corresponds to a full-history violation. The full-history violation is indicative of a degradation of performance of the information retrieval system.

This aspect may include one or more of the following optional features. In some implementations, determining whether the RPS exceeded the maximum conforming load for the key range based on the beginning instance in time of the respective delta violation includes determining a zero-history RPS limit. The zero-history RPS limit includes a function of a minimum of a historical zero-history RPS limit and the moving average of RPS. The operations may also include determining a duration of time beginning at the beginning instance of the respective delta violation and ending when the RPS no longer exceeds the zero-history RPS limit. The operations optionally include determining a zero-history violation based on the duration of time that the RPS exceeded the zero-history RPS limit. In some examples, when the RPS exceeded the maximum conforming load for the key range, the operations include determining that the zero-history violation corresponds to one or more full-history violations.

In some implementations, the operations further include generating a request grid including a plurality of cells. Each cell represents a fixed-length time bucket of a key bucket and each key bucket includes a range of keys sized to represent a select average amount of requests. Determining the moving average of RPS may include determining a moving average of each key bucket. Optionally, each key bucket is sized to have the same average amount of requests. In some examples, determining the number of delta violations includes determining narrow-band candidate delta violations where each narrow-band candidate delta violation represents an instance in time when the RPS of the respective key bucket exceeds the delta RPS limit. The operations may also include determining wide-band candidate delta violations from the narrow-band candidate delta violations where each wide-band delta violation includes neighboring narrow-band delta violations and determining, for each wide-band candidate delta violation, whether the wide-band candidate delta violation is a delta violation based on a quantity or intensity of the requests.

Implementations herein are directed toward detecting traffic ramp-ups in distributed storage systems (e.g., cloud storage) that exceed one or more traffic rules or otherwise indicate a potential for performance degradation. A rule violation detector detects violations of a traffic ramp-up rule and receives data element retrieval requests (i.e., to store or retrieve data) for an information retrieval system executing on a distributed storage system. The rule violation detector may receive a portion of the data element retrieval requests (i.e., sample the requests) sufficient to characterize all of the data element retrieval requests destined for the information retrieval system and determine a requests per second (RPS) for a key range of the information retrieval system. The rule violation detector determines a moving average of the RPS for the key range. Using the RPS and the moving average of RPS, the violation detector determines a number of delta violations over a time period. A delta violation includes an instance in time where the moving average RPS exceeded an RPS limit. For each delta violation, the violation detector determines a maximum conforming load for the key range and determines whether the moving average of RPS exceeded the maximum conforming load during a duration of the respective delta violation. When the moving average of RPS exceeded the maximum conforming load for the key range, the violation detector determines that the delta violation corresponds to a traffic ramp-up rule violation.

Distributed storage systems frequently partition databases to easily allow scaling by spreading the load across multiple machines. Databases may be vertically or horizontally partitioned. Horizontally partitioning a database may also be referred to as sharding the database. Each individual partition is referred to as a shard and each shard may be stored on a separate server or other independent computing device. Sharding a database involves separating rows of the database into multiple different tables. This is in contrast to separating columns into different tables (e.g., vertical partitioning). Each partition may have the same columns but different rows. A number of different sharding techniques may be implemented. For example, key based sharding, range based sharding, and directory based sharding are all typical implementations of sharding.

Ranged based sharding involves sharding the data of the database based on ranges of values of shard keys associated with the data. That is, each row of the database is associated with a shard key and the value of the associated shard key determines which shard the row of data is stored at. Each shard may be assigned a contiguous range of shard key values. Thus, data with "close" shard key values is likely to be stored in the same shard, which may increase the efficiency of some requests or operations or queries.

Some distributed storage systems (e.g., range-sharded storage systems) may adjust key-range load balancing according to variations in the incoming load. This may be referred to as key-range capacity auto-scaling. As previously discussed, the full keyspace is split into a number of shards (i.e., key-range splits), which are units of load-balancing. Sustained increased load for a threshold period of time on a shard may result in a "split" operation, where the shard is divided into two or more shards (e.g., adding one or more additional servers or spreading the shards across existing servers), which may effectively double (or more) the capacity of the key-range. In some implementations, adjacent key-range splits that experience low levels of load for a period of time are merged together (i.e., a "merge" operation) to recover unused resources. In some examples, the period of time for a split operation is much shorter than the period of time for a merge operation. For example, the period of time for a split operation may be on the order of <NUM> minute while the period of time for a merge operation may be on the order of a day. Thus, the effective capacity of an arbitrary key-range may be doubled rapidly and the generated capacity may be retained for long period of time to protect against additional spikes in data.

Because there is a delay before capacity may be increased via a split operation (e.g., <NUM> minutes), a sufficiently large and fast ramp-up of user traffic to a single shard (i.e., a key-range split) may result in performance degradation. The splitting and merging behavior of such key-range capacity auto-scaling systems may be modeled by a traffic ramp-up rule. User traffic may be compared against the model to determine violations of the traffic ramp-up rule. A violation of the traffic ramp-up rule may be indicative of performance degradation. In some examples, such a violation impacts the cloud service provider's guarantees (i.e., performance guarantees) to the client responsible for the violation. An example of a traffic ramp-up rule may be a <NUM>/<NUM>/<NUM> rule or the like. With a <NUM>/<NUM>/<NUM> rule, a client may begin operating over an arbitrary key-range at <NUM> RPS and from there increase traffic by <NUM>% every <NUM> minutes. Following this rule may ensure that the system can add resources fast enough that performance degradation does not occur.

In some examples, the traffic ramp-up rule models a traffic limit that user traffic must remain under (e.g., in RPS) in order to avoid degradation of performance of the information retrieval system. Because of the nature of the splitting and merging of the key-range splits, the traffic limit inherently has historical dependencies on previous traffic data and traffic limits. Because of the vast quantities of data and the historical dependencies of determining traffic limits, determining violations of the traffic ramp-up rule typically is a very computationally expensive endeavor.

Referring to <FIG> and <FIG>, in some implementations, a system <NUM> includes one or more client devices <NUM>, 120a-n associated with one or more clients/customers/owners <NUM>, 10a-n, who may communicate, via a network <NUM>, with a remote system <NUM>. The remote system <NUM> may be a distributed system (e.g., cloud environment) having scalable/elastic resources <NUM>. The resources <NUM> include computing resources <NUM> and/or storage resources <NUM>. An information retrieval system <NUM> (e.g., a distributed storage system or a data store) is overlain on the storage resources <NUM> to allow scalable use of the storage resources <NUM> by one or more of the client devices <NUM>. The information retrieval system <NUM> is configured to store data objects <NUM>, 200a-n from the client devices <NUM>. In some examples, the data objects include databases (i.e., rows and columns of data elements <NUM>, 202a-n).

The remote system <NUM> receives data objects <NUM> from a client device <NUM> and stores the data objects <NUM> on the storage abstraction <NUM> by chunking or separating the data objects <NUM> into constituent data elements or data chunks <NUM> and storing the data elements on one or more shards <NUM>, 152a-n. Alternatively, the remote system <NUM> generates an empty data object <NUM> and receives data elements <NUM> from the client device <NUM> to store within the data object <NUM>. As used herein, each shard <NUM> represents separate computing resources <NUM> and storage resources <NUM> (e.g., a separate server) that stores a horizontal partition of the data object <NUM>. The remote system <NUM> may implement any number of shards <NUM> and may dynamically add or remove shards <NUM> based on utilization.

The remote system <NUM> receives data element retrieval requests <NUM> from the clients <NUM> to retrieve one or more data elements <NUM> from the information retrieval system <NUM>. The information retrieval system <NUM> will determine the location of the data element(s) <NUM> based on a shard key value <NUM> (i.e., which shard <NUM> the data element <NUM> is stored at) provided in each data element retrieval request <NUM>. Once the proper shard <NUM> is determined, the information retrieval system <NUM> fetches the appropriate data elements <NUM> and returns them to the requesting client <NUM>. The data element retrieval requests <NUM> may also include requests to add additional or update existing data elements <NUM> to the information retrieval system <NUM>. Again, the information retrieval system <NUM> may use the associated shard key value <NUM> included in the retrieval request <NUM> to determine the appropriate shard <NUM> for storing the uploaded data elements <NUM>.

Referring to <FIG>, in some implementations, the distributed system <NUM> includes loosely coupled memory hosts <NUM>, 110a-n (e.g., computers or servers), each having a computing resource <NUM> (e.g., one or more processors or central processing units (CPUs)) in communication with storage resources <NUM> (e.g., memory hardware, memory hardware, flash memory, dynamic random access memory (DRAM), phase change memory (PCM), and/or disks) that may be used for caching data. The storage abstraction <NUM> overlain on the storage resources <NUM> allows scalable use of the storage resources <NUM> by one or more client devices <NUM>, 120a-n. The client devices <NUM> may communicate with the memory hosts <NUM> through the network <NUM> (e.g., via remote procedure calls (RPC)).

In some implementations, the distributed system <NUM> is "single-sided. " "Single-sided" refers to the method by which most of the request processing on the memory hosts <NUM> may be done in hardware rather than by software executed on CPUs <NUM> of the memory hosts <NUM>. Additional concepts and features related to a single-sided distributed caching system can be found in <CIT>, which is hereby incorporated by reference in its entirety.

The distributed system <NUM> may store constituent data elements or data chunks <NUM> of data objects <NUM> uploaded by client devices <NUM> on the storage resources <NUM> (e.g., memory hardware) of the remote memory hosts <NUM> (e.g., storage abstraction <NUM>) and get the data chunks <NUM> from the remote memory hosts <NUM> via RPCs or via remote direct memory access (RDMA)-capable network interface controllers (NIC) <NUM>. A network interface controller <NUM> (also known as a network interface card, network adapter, or LAN adapter) may be a computer hardware component that connects a computing device/resource <NUM> to the network <NUM>. Both the memory hosts 110a-n and the client device <NUM> may each have a network interface controller <NUM> for network communications. The information retrieval system <NUM> executing on the physical processor <NUM> of the hardware resource <NUM> registers a set of remote direct memory accessible registers a set of remote direct memory accessible regions/locations <NUM>, 118a-n of the storage resource (e.g., memory) <NUM> with the network interface controller <NUM>. Each memory location <NUM> is configured to store a corresponding data element <NUM>.

Referring now to <FIG>, an exemplary data object <NUM> (i.e., a table) includes a number of data elements <NUM> demarcated by columns <NUM> including a first name column 210a, a last name column 210b, a title column 210c, and a column of shard key values <NUM>. Here, the table <NUM> has three rows for simplicity, but in practice the table may have up to trillions of rows. As previously discussed, the remote system <NUM> may separate the data object <NUM> using horizontal partitioning and store the partitions on separate shards <NUM>. In this example, the data object <NUM> is separated and stored Shard <NUM>150a, Shard <NUM>150b, and Shard <NUM>150c based on the shard key value <NUM>. In this example, Shard <NUM>150a stores data elements <NUM> that are associated with a shard key value <NUM> between <NUM> and <NUM>. That is, all data elements associated with a shard key value <NUM> between <NUM> and <NUM> may be stored at Shard <NUM>150a. Shard <NUM>150b stores data elements <NUM> that are associated with a shard key value <NUM> between <NUM> and <NUM>. Similarly, Shard <NUM>150c stores data elements <NUM> that are associated with a shard key value <NUM> between <NUM> and <NUM>. These values are exemplary only, and it is understood that the shard key values <NUM> may be assigned any value (with any or no relationship to the rest of the data object <NUM>) and each shard <NUM> may support any range of shard key values <NUM>. For example, the shard key value <NUM> may be assigned to an existing column of data elements <NUM> within the data object <NUM> (e.g., an employee number, a cost of an item, a location field, etc.). The relationship between the shard key values <NUM> and the data elements (e.g., the shard key cardinality, the shard key frequency, etc.) may affect the performance of the information retrieval system <NUM>.

Still referring to <FIG>, the data object <NUM> is partitioned into three partial data objects <NUM>, 201a-c, each with a number of data elements <NUM>. Here, the row with the shard key value <NUM> of "<NUM>" was stored at Shard <NUM>150a, while the row with the shard key value <NUM> of "<NUM>" was stored at Shard <NUM>150b. Similarly, the row with the shard key value <NUM> of "<NUM>" was stored at Shard <NUM>150c. In this way, the data object <NUM> is split among three shards 150a, 150b, 150c (each of which may be a separate computing resources), thereby increasing the information retrieval system's <NUM> access capacity to the data object <NUM>.

Referring back to <FIG>, the remote system <NUM> executes a rule violation detector <NUM>. As discussed in more detail below, the rule violation detector <NUM> monitors client data element retrieval requests <NUM>. Because the number of requests <NUM> may be extraordinarily large, in some examples, the rule violation detector <NUM> randomly samples a portion of the requests <NUM> sufficient to be representative of the totality of the requests <NUM>. The rule violation detector <NUM>, using the sampled requests <NUM>, determines whether the requests <NUM> violate a traffic ramp-up rule <NUM>. The traffic ramp-up rule <NUM> outlines, for example, the maximum rate that user traffic (i.e., requests <NUM>) may increase over arbitrary key-ranges to avoid performance degradation.

Referring now to <FIG>, in some implementations, the rule violation detector <NUM> includes a delta detector <NUM>, a zero-history detector <NUM>, and a full-history detector <NUM>. In some examples, the sampled requests <NUM> may not characterize all the trends in traffic, but instead only the most significant or notable load variations in traffic. Various sampling techniques may be implemented to help control and/or minimize sampling error. The rule violation detector <NUM> receives the sampled requests <NUM> at the delta detector <NUM>. In some examples, the delta detector <NUM> receives sampled requests <NUM> (herein also referred to generically as "traffic") for a period of time at least as long as a reference window <NUM> (<FIG>). In some examples, the reference window <NUM> is equivalent to an amount of time the information retrieval system <NUM> will maintain capacity after a split operation minus the amount of time the information retrieval system <NUM> requires to perform a split operation. The time period in which the system <NUM> will maintain capacity is herein referred to as the RPS history, while the time period required by the system <NUM> to increase capacity is herein referred to as the RPS delay <NUM> (<FIG>). For example, when the information retrieval system <NUM> requires five (<NUM>) minutes to perform a split operation (i.e., increase capacity in response to increased traffic) and maintains the increases capacity for <NUM> hours before performing a merge operation, the reference window <NUM> may have a duration of <NUM> hours and <NUM> minutes. As used herein, the terms "requests per second (RPS)" and "queries per second (QPS)" may be used interchangeably.

Because the traffic ramp-up rule <NUM> has a historical dependency in the past as long as the RPS history, the reference window <NUM> is sized to encompass all of the necessary history from the current time. Put another way, because of the historical dependency of the traffic ramp-up rule <NUM>, in order to determine a violation of the traffic ramp-up rule <NUM> at time ts, all of the traffic and the traffic limits for a previous period of time equivalent to the RPS history (<NUM> hours in this example) is used. In some examples, a period of recent time may not be relevant (e.g., RPS delay <NUM>) as the system has not yet had time to respond to traffic increases. Thus, the reference window <NUM> provides a sliding window of time to determine violations at an instance in time. It is understood that the specific values used herein are exemplary and may be substituted with any values unless otherwise noted. The sampled requests <NUM> received by the delta detector <NUM> may be representative of all traffic during the reference window <NUM>.

Referring now to <FIG>, in some implementations, the sampled traffic is placed in a grid <NUM> of grid elements <NUM>, 402a-n. The x-axis of the grid may represent time in seconds, with each grid element <NUM> representing a fixed length "time-bucket" <NUM>, 420a-n. Each time-bucket <NUM> represents all the sampled traffic that occurred during a set amount of time. For example, each time-bucket <NUM> (i.e., the x-axis of each grid element <NUM>) may represent <NUM> seconds of time. The length of the time-buckets <NUM> is tunable (i.e., adjustable). When the reference window <NUM> is <NUM> hours and <NUM> minutes (i.e., the RPS history minus the RPS delay <NUM>), the grid <NUM> would have an x-axis length of <NUM> elements (one grid element <NUM> for each <NUM> seconds of the <NUM> hour and <NUM> minute hour reference window <NUM>). In some examples, the delta detector <NUM> sequentially grids portions of the reference window <NUM> in order to minimize the size of the grid <NUM>. That is, the length of the grid <NUM> may represent only a portion of the reference window <NUM>. In some examples, the length of the grid may be a ratio of the reference window <NUM>. For example, the delta detector <NUM> may generate the grid <NUM> for the first <NUM> hour portion of the reference window <NUM> and analyze or process the data. After completion, the delta detector <NUM> may generate the grid <NUM> for the next <NUM> hours portion of the reference window <NUM> and so on until the entire reference window <NUM> is processed. In some implementations, the generated grids <NUM> may not completely align or match on key-bucket boundaries. By tuning grid generation parameters and using approximation techniques, the necessary metrics may be derived across the grids <NUM> with an acceptable level of error.

The y-axis of the grid <NUM> may represent at least a portion of the keyspace <NUM> of the information retrieval system <NUM>. The keyspace <NUM> represents all of the potential shard key values <NUM> and the y-axis, in some examples, represents the entire keyspace <NUM> (i.e., from a minimum shard key value <NUM> to a maximum shard key value <NUM>), and in other examples represents only a relevant portion of the keyspace <NUM>. Each grid element <NUM> may represent a key-bucket <NUM>, 430a-n (i.e., the "height" of the grid element <NUM> represents a range of keys). A key-bucket <NUM> is defined as a narrow range or narrow band of keys with a start key and an end key. For example, if the keyspace <NUM> consisted of all whole numbers between <NUM> and <NUM>, one key-bucket <NUM> may represent shard-key values between <NUM> and <NUM>. Put another way, each grid element <NUM> represents a slice of the total keyspace <NUM> (i.e., a key-bucket <NUM>) for a period of time (i.e., a time bucket <NUM>). In some examples, each key-bucket <NUM> is the same size (i.e., represents an equal amount of the keyspace <NUM>). In other examples, each key-bucket <NUM> is sized such that each key-bucket <NUM> represents approximately the same amount of traffic. For example, each key-bucket <NUM> may represent keyspace that experiences roughly an average of <NUM> RPS over the length of the grid <NUM> (which may be a portion, e.g., <NUM> hours, of the reference window <NUM>). It is not important that each key-bucket <NUM> represents exactly the same amount of traffic and rough estimates suffice. Requests per second may also be referred to as queries per second (QPS). Thus, each grid element <NUM> of the grid <NUM> may represent a number of requests <NUM> for a given key-range (i.e., key-bucket <NUM>) over a given time period (i.e., a time-bucket <NUM>). This number of requests <NUM> may be referred to as the RPS <NUM> for that key-bucket <NUM> at that time-bucket <NUM>. In some examples, the RPS <NUM> is equivalent to the average RPS multiplied by the length of the time-bucket <NUM>. For example, when the average RPS is fifty and each time-bucket represents <NUM> seconds, each grid element <NUM> would represent <NUM> requests.

Using the grid <NUM>, the delta detector <NUM> may determine a moving average of each key-bucket <NUM>. The moving average is referred to herein as a RPS load <NUM> (<FIG>). The moving average (i.e., the RPS load <NUM>) is determined over a period of time referred to as a RPS load duration <NUM> (<FIG>). In some examples, the RPS load duration <NUM> is five minutes. Here, for each grid element <NUM>, the moving average of the previous five minutes is determined as the RPS load <NUM> for the respective key-bucket <NUM>. In some implementations, the delta detector <NUM> determines that a delta violation <NUM> occurred whenever the RPS <NUM> (<FIG>) at a point in time exceeds the RPS load <NUM> at a point in time equivalent to the RPS delay <NUM> before the same point in time multiplied by a delta weight <NUM> (e.g., <NUM>) (<FIG>). The RPS load <NUM> multiplied by the delta weight <NUM> at a point in time (i.e., ts) after RPS delay <NUM> (i.e., ts - RPS delay) may be referred to as a delta RPS limit <NUM> at time ts (<FIG>). That is, the RPS limit at timestamp ts may be the delta weight <NUM> multiplied by the RPS load <NUM> at (ts - RPS delay). The delta weight <NUM> may model capacity increase after a split operation (i.e., one or more shards are added). In some examples, the RPS <NUM> may be a second moving average over a different time length than RPS load <NUM>. That is, in some examples, a delta violation <NUM> may be determined based on two moving averages with different lengths (e.g., <NUM> minutes and <NUM> minute).

Referring now to <FIG>, a plot <NUM> with an x-axis of time (in seconds) and a y-axis in RPS illustrates the relationship between the RPS <NUM>, the RPS load <NUM>, and the delta RPS limit <NUM> when user traffic ramps up at the maximum amount without violating the delta RPS limit <NUM>. At time <NUM> and until approximately <NUM> seconds, the RPS <NUM> remains constant at "<NUM>". Because the RPS <NUM> is constant, the RPS load <NUM> (i.e., the moving average of RPS <NUM>) is also constant at "<NUM>". In this example, the delta weight <NUM> is equal to about "<NUM>", and therefore, the delta RPS limit <NUM> is equal to the result of "<NUM>" multiplied by "<NUM>" (i.e., <NUM>). At time = <NUM> seconds, the RPS <NUM> increases to the delta RPS limit <NUM> of "<NUM>". After a period of time (i.e., the RPS delay <NUM>), the delta RPS limit <NUM> increases and the RPS <NUM> (i.e., the user traffic) and the RPS load <NUM> increased to match the delta RPS limit <NUM>. The delta RPS limit <NUM> increase trails the increase in RPS <NUM> due to RPS delay. That is, this lagging models the behavior of the information retrieval system <NUM>, as the system <NUM> will have a delay before additional resources can be added (e.g., adding shards <NUM>). <FIG> illustrates a plot <NUM> with the same data as the plot <NUM>, but with a greatly increased time scale for the x-axis. This time scale makes it apparent that the delta RPS limit <NUM> increases at an approximately exponential rate. In the example shown in <FIG> and <FIG>, the RPS <NUM> never exceeds the delta RPS limit <NUM>, and thus the delta detector <NUM> would not determine the existence of a delta violation <NUM>.

Referring now to <FIG>, another plot <NUM> provides an example of a different traffic pattern from <FIG> and <FIG>. Here, the x-axis again is time (in seconds) and the y-axis is requests per second. At time <NUM>, the RPS <NUM> and the delta RPS limit <NUM> are stable at "<NUM>" and "<NUM>" respectively. In this case, at time ≈ <NUM> seconds, the user traffic (represented by RPS <NUM>) rapidly increases to "<NUM>", which exceeds the delta RPS limit <NUM> of "<NUM>". The user traffic then, at time ≈ <NUM> seconds, returns to <NUM> RPS. Shortly after the first traffic spike (i.e., the RPS delay <NUM>), the delta RPS limit <NUM> increases to "<NUM>" (i.e., <NUM> multiplied by the delta weight <NUM> of <NUM>). In this example, the delta detector <NUM> would detect a delta violation <NUM> starting at the traffic spike at time ≈ <NUM> seconds and lasting until the delta RPS limit <NUM> is no longer exceeded by the RPS <NUM> (at t ≈ <NUM> seconds). The increase in the delta RPS limit <NUM> (due to the increase of the RPS load <NUM>) causes the remaining portion of the traffic spike (from t ≈ <NUM> seconds to t ≈ <NUM> seconds) to not be a delta violation <NUM>. After the traffic spike, the RPS load <NUM> returns to <NUM> RPS and the delta RPS limit <NUM> returns to <NUM> RPS.

Referring back to <FIG>, while a delta violation <NUM> does not necessarily result in a violation of the traffic ramp-up rule violation (as explained in more detail below), the delta detector <NUM> may efficiently analyze vast quantities of data (i.e., user traffic) and quickly identify periods of traffic to specific key ranges that may indicate a traffic ramp-up rule violation (i.e., a full-history violation <NUM>). Put another way, the delta detector <NUM> detects all the areas in the traffic that may have experienced a sudden increase in load. The delta detector <NUM> may detect a delta violation <NUM> across nearly any range of the keyspace <NUM>.

The delta detector <NUM> also may determine the widest key-range delta violation <NUM> (i.e., a wide-band delta violation) by combining narrower key-range violations (i.e., key-buckets <NUM> or narrow-band delta violations). In other words, when a heavy load increase corresponds to a wide key-range, narrower key-ranges, when combined with other delta violations <NUM> near each other (in keyspace), construct the wider key-range and experience a similar trend in traffic. Thus, the delta detector <NUM> may determine delta violations <NUM> that are candidates to be a violation of the traffic ramp-up rule <NUM>. That is, the delta detector <NUM> may determine narrow-band candidate delta violations <NUM>, and from the narrow-band candidate delta violations, determine a wide-band candidate delta violation from the narrow-band candidate delta violations. The delta detector <NUM> may apply additional traffic rules to determine whether combined delta violations <NUM> (i.e., the wide key-range delta violations) experience an impactful amount of traffic load increases. For example, the delta detector <NUM> considers an intensity of the increased load in addition to the peak to provide additional filtering.

Thus, the delta detector <NUM> detects delta violations <NUM> over the entire keyspace <NUM> and constructs wide-band delta violations from narrow-band delta violations. The delta detector <NUM> avoids the need for limit derivations over arbitrary key-ranges, which greatly reduces computation complexity, while simultaneously significantly trimming the search space for traffic ramp-up rule violations.

With continued reference to <FIG>, the delta detector <NUM> sends any detected delta violations <NUM> and any relevant data (i.e., timestamps, key-range, etc.) to the zero-history detector <NUM>. In some implementations, delta violations <NUM> do not fully capture the dynamics of the model of the key-range capacity auto-scaling systems, as delta violations <NUM> only identify areas in the grid <NUM> that have had an impactful increase in traffic levels. That is, a violation of the traffic ramp-up rule <NUM> begins with a delta violation <NUM>, but not every delta violation <NUM> corresponds to a full-history violation <NUM>.

The delta detector <NUM> uses the delta RPS limit <NUM> for simplicity (i.e., to efficiently reduce the search space), but, in some examples, the delta RPS limit <NUM> does not represent the actual rate the RPS limit for the model of the key-range capacity auto-scaling systems increases. Instead, a zero-history RPS limit <NUM> (<FIG>) may be used to more accurately model the traffic rule <NUM>. For example, instead of the RPS load <NUM> multiplied by the delta weight <NUM> (i.e., the delta RPS limit <NUM>) at an instance in time (i.e., an RPS delay amount of time prior to the timestamp of interest), the zero-history RPS limit <NUM> may instead be a function of the minimum of the RPS load <NUM> and the zero-history RPS limit <NUM> at the same instance in time (i.e., a historical zero-history RPS limit <NUM>) multiplied by an RPS increase ratio <NUM> (<FIG>). That is, the increase of the zero-history RPS limit <NUM> may be capped by previous limits and thus may take longer to respond to large traffic spikes.

Referring now to <FIG>, a plot <NUM> illustrates the relationship between the RPS <NUM>, the RPS load <NUM>, and the zero-history RPS limit <NUM>. The plot <NUM> again has an x-axis of time (in seconds) and a y-axis in RPS. Here, the RPS increase ratio <NUM> is equal to "<NUM>". While in this example, the RPS increase ratio <NUM> is the same as the delta weight <NUM> in previous examples, the values may also be different. At time <NUM>, the RPS <NUM> and RPS load <NUM> are stable at <NUM> RPS. The zero-history RPS limit <NUM> is <NUM> RPS, as the RPS load <NUM> (i.e., <NUM>) multiplied by the RPS increase ratio <NUM> (i.e., <NUM>) is equal to <NUM> RPS. At roughly time <NUM> seconds, the RPS <NUM> increases instantaneously to <NUM> RPS. After the time period associated with the RPS load duration <NUM> passes (e.g., <NUM> minutes), the RPS load <NUM> also arrives at <NUM> RPS. However, in this example, the zero-history RPS limit <NUM> increases in intervals of the RPS delay <NUM>. Due to the drastic increase in the RPS <NUM>, the minimum between the RPS <NUM> and the previous zero-history RPS limit <NUM> is the previous zero-history RPS limit <NUM> until over <NUM> seconds have passed.

In this example, the delta detector <NUM> would detect a delta violation <NUM> beginning at <NUM> seconds (i.e., when the traffic suddenly increased) with a duration of <NUM> minutes (i.e., the RPS load duration <NUM>). In contrast, a zero-history violation <NUM>, while beginning at the same point as the delta violation <NUM> (i.e., at approximately <NUM> seconds), has a length equivalent to the time period until the RPS <NUM> no longer exceeds the zero-history RPS limit <NUM> (i.e., at approximately <NUM> seconds). Thus, in this example, the zero-history violation <NUM> is longer in duration than the corresponding delta violation <NUM>. In some examples, a zero-history violation <NUM> corresponds to multiple delta violations <NUM>, and thus a total number of zero-history violations <NUM> may be less than or equal to a total number of delta violations <NUM>. For example, when there is a stepwise increase in traffic (i.e., RPS <NUM>), the head of each step may be flagged as a delta violation <NUM>, but the entire traffic spike may be detected as a single zero-history violation <NUM>.

Because all zero-history violations <NUM> include a delta violation <NUM> at the head, prior detections of delta violations <NUM> (e.g., by the delta detector <NUM>) greatly simplifies detection of corresponding zero-history violations <NUM>. This process can also merge multiple delta-violations into a single zero-history violation.

Referring again back to <FIG>, the zero-history detector <NUM> sends the detected zero-history violations <NUM> to the full-history detector <NUM> along with any relevant information (e.g., timestamps, key-ranges, etc.). In some implementations, increasing the capacity of a key range (e.g., via adding a shard <NUM>) in response to a traffic spike takes a relatively short period of time (e.g., <NUM> minutes), while the information retrieval system <NUM> may retain the increased capacity for a significant period of time (e.g., <NUM> day) even if the traffic immediately subsides to pre-spike levels. This behavior may be modeled by a full-history RPS limit <NUM> (<FIG>). Using the full-history RPS limit <NUM>, not all zero-history violations <NUM> will correspond to full-history violations <NUM>, as the zero-history violations <NUM> do not account for the history of the entire reference window <NUM>. The full-history RPS limit <NUM> may be referred to as a maximum conforming load for the key range. The maximum conforming load may be dependent upon implementation of autoscaling resources (i.e., splitting and merging shards). That is, a key-range capacity (i.e., the maximum conforming load for each key range) may be determined by the load variations where autoscaling allows for increasing level of load or a number of partitions that the respective key-range corresponds to due to the amount of data the key-range holds.

In some examples, a zero-history violation <NUM> includes multiple full-history violations <NUM>. For example, a zero history violation <NUM> (from one or more delta violations <NUM>) with the interval [zh_start, zh_end] has a traffic pattern for a select key-range that is generally increasing but is wavy and it has two intense maximums within the interval. Between the maximums, the traffic decreases and trends near the zero history limit <NUM> but does not equal it, which results in a single violation period for a zero-history violation <NUM>. When determining full-history violations <NUM>, each timestamp (e.g., at an interval of duration of the time-buckets <NUM>) within the zero-history violation interval may be compared to the maximum conforming load within the current reference window <NUM>, as each timestamp has a different reference window <NUM> that moves or slides with the timestamp. Depending on historical levels of load within these reference windows <NUM>, areas around the two maximums may be derived as two separate full-history violation periods while the local minimum in between each maximum conforms to the maximum conforming load.

The full-history detector <NUM> detects full-history violations <NUM> which correspond to violations of the traffic ramp-up rule <NUM>. A full-history violation <NUM> may correspond to a zero-history violation <NUM> that lacks prior levels of conforming workload within the corresponding reference window <NUM>. More specifically, when examining a zero history violation period of [zh_start, zh _end], at any given timestamp ts belonging to this period, a full history limit may be re-derived equal to the RPS increase ratio <NUM> multiplied by the maximum conforming load of the corresponding reference window <NUM>. This new limit may be used to determine if this instance in time is a full history violation <NUM>. In some examples, only a portion (e.g., the most intense of this interval may be processed as a heuristic. The full-history detector <NUM>, in some examples, only processes regions corresponding to zero-history violations <NUM> in order to detect full-history violations <NUM>. Because any historical dependency for a zero-history violation <NUM> resets as soon as traffic returns to below the zero-history RPS limit <NUM> and because of the extended increased capacity in response to increased traffic, a zero-history violation <NUM> may not account for some conforming workloads.

In some implementations, the full-history detector <NUM> also receives the grid <NUM>. The high resolution grid <NUM> (e.g., generated by the delta detector <NUM>) enables the full-history detector <NUM> to derive bounds for the previous levels of load for any key-range. Each zero-history violation <NUM> corresponds to a sudden increase in levels of traffic. When there are no comparable levels of non-violating (i.e., conforming) load in the reference window <NUM>, the full-history detector <NUM> determines that a zero-history violation <NUM> is a full-history violation <NUM>.

Referring now to <FIG>, a plot <NUM> illustrates the relationship between the RPS <NUM>, the RPS load <NUM>, and the full-history RPS limit <NUM>. As with the previous examples, the plot <NUM> has an x-axis of time in seconds and a y-axis in RPS. Here, four traffic spikes are illustrated that rapidly increase traffic from about <NUM> RPS to about <NUM> RPS. Here, user traffic (i.e., RPS <NUM>) is assumed stable for a long period of time prior to time = <NUM> (e.g., for longer than the reference window <NUM> period). While all four spikes may be detected as delta violations <NUM> and zero-history violations <NUM>, due to the maintained capacity increase (represented by the full-history RPS limit <NUM>), the full-history detector <NUM> may determine that only the first spike is a full-history violation <NUM>.

Referring now to <FIG>, a primary challenge to detecting violations of the traffic ramp-up rule <NUM> (i.e., the full-history violations <NUM>) is the unbounded historical dependency of the traffic ramp-up rule <NUM>. That is, whether a violation has occurred at a specific time is dependent upon traffic behavior prior to the specific time. Clearly, this poses an issue in determining an initial full-history RPS limit <NUM> at the beginning of the reference window <NUM>. In order to solve this historical dependency, the rule violation detector <NUM> may implement a bootstrapping technique. That is, prior to the rule violation detector <NUM> sampling sufficient data to satisfy the RPS history (e.g., when the rule violation detector <NUM> has been sampling data for less than <NUM> hours), the bootstrapping technique may be used to initialize the full-history RPS limit <NUM>.

Due to the nature of the full-history RPS limit <NUM>, when a given reference window <NUM> has no violation, then determining the full-history RPS limit <NUM> only requires RPS load <NUM> values (and not the history of the full-history RPS limit <NUM>). Put another way, a reference window <NUM> without a violation may act as a "history reset" event such that history prior to the reference window is irrelevant.

Referring now to <FIG>, in some implementations, the rule violation detector <NUM> selects a bootstrap window <NUM> of sufficient size to ensure that there is a high probability that at least on reference window <NUM> with the bootstrap window <NUM> has no full-history violation <NUM>. The rule violation detector <NUM> may begin at the start of the bootstrap window <NUM> and determine the full-history RPS limit <NUM> (using just the RPS load <NUM> to start). Because of the high probability that there was a reset event within the bootstrap window <NUM>, the rule violation detector <NUM> may trust the full-history RPS limit <NUM> at the end of the bootstrap window <NUM>. Thus, prior to the rule violation detector <NUM> detecting full-history violations <NUM> within a reference window <NUM>, the rule violation detector <NUM> may bootstrap the full-history RPS limit <NUM> by selecting a bootstrap window <NUM> prior in time to the reference window <NUM>.

<FIG> is a flowchart of an exemplary arrangement of operations for a method <NUM> of detecting a traffic ramp-up rule violation within an information retrieval system. The method <NUM> starts at operation <NUM> with receiving, at data processing hardware <NUM>, data element retrieval requests <NUM> each requesting at least one data element <NUM> from an information retrieval system <NUM>. The information retrieval system <NUM> includes a plurality of data elements <NUM>. The method <NUM> includes, at operation <NUM>, determining, by the data processing hardware <NUM>, a requests per second (RPS) <NUM> for a key range <NUM> of the information retrieval system <NUM> based on a number of the data element retrieval requests <NUM> received. At operation <NUM>, the method <NUM> includes determining, by the data processing hardware <NUM>, a moving average of RPS <NUM> for the key range <NUM> of the information retrieval system <NUM> over a first time period (e.g., RPS load duration of <FIG>) <NUM> based on the number of the data element retrieval requests <NUM> received. The method <NUM>, at operation <NUM>, includes determining, by the data processing hardware <NUM>, a number of delta violations <NUM>. Each delta violation <NUM> includes a respective beginning instance in time when the RPS <NUM> exceeded a delta RPS limit <NUM>. The delta RPS limit <NUM> is based on the moving average of RPS <NUM>.

For each delta violation <NUM>, the method <NUM> includes, at operation <NUM>, determining, by the data processing hardware <NUM>, a maximum conforming load <NUM> for the key range <NUM> over a second time period <NUM> and, at operation <NUM>, determining, by the data processing hardware <NUM>, whether the RPS <NUM> exceeded the maximum conforming load <NUM> for the key range <NUM> based on the beginning instance in time of the respective delta violation <NUM>. When the RPS <NUM> exceeded the maximum conforming load <NUM> for the key range <NUM>, the method <NUM> includes, at operation <NUM>, determining, by the data processing hardware <NUM>, that the delta violation <NUM> corresponds to a full-history violation <NUM>. The full-history violation <NUM> is indicative of a degradation of performance of the information retrieval system <NUM>.

For example, it may be implemented as a standard server 1300a or multiple times in a group of such servers 1300a, as a laptop computer 1300b, or as part of a rack server system 1300c.

Claim 1:
A method (<NUM>) for detecting traffic ramp-ups in a distributed storage system indicating a potential for performance degradation in the distributed storage system, the method comprising:
receiving, at data processing hardware (<NUM>), data element retrieval requests (<NUM>) each requesting at least one data element (<NUM>) from an information retrieval system (<NUM>) executing on the distributed storage system, the information retrieval system (<NUM>) comprising a plurality of data elements (<NUM>), wherein the information retrieval system (<NUM>) includes a dynamic range-sharded information retrieval system;
determining, by the data processing hardware (<NUM>), a requests per second, RPS, (<NUM>) for a key range (<NUM>) of the information retrieval system (<NUM>) based on a number of the data element retrieval requests (<NUM>) received;
determining, by the data processing hardware (<NUM>), a moving average of RPS (<NUM>) for the key range (<NUM>) of the information retrieval system (<NUM>) over a first time period (<NUM>) based on the number of the data element retrieval requests (<NUM>) received;
determining, by the data processing hardware (<NUM>), a number of delta violations (<NUM>), each delta violation (<NUM>) comprising a respective beginning instance in time when the RPS (<NUM>) exceeded a delta RPS limit (<NUM>), the delta RPS limit (<NUM>) based on the moving average of RPS (<NUM>); and
for each delta violation (<NUM>):
determining, by the data processing hardware (<NUM>), a maximum conforming load (<NUM>) for the key range (<NUM>) over a second time period (<NUM>);
determining, by the data processing hardware (<NUM>), whether the RPS (<NUM>) exceeded the maximum conforming load (<NUM>) for the key range (<NUM>) based on the beginning instance in time of the respective delta violation (<NUM>); and
when the RPS (<NUM>) exceeded the maximum conforming load (<NUM>) for the key range (<NUM>), determining, by the data processing hardware (<NUM>), that the delta violation (<NUM>) corresponds to a full-history violation (<NUM>), the full-history violation (<NUM>) indicative of a degradation of performance of the information retrieval system (<NUM>).