Rate-limiting based on cardinality computation

A cloud-based service records time-series data of a plurality of metrics from a plurality of tenants. The time-series data comprises a series of measures of a metric at sequential points in time. The time-series data is recorded in database tables in a manner that consumes more resources when the cardinality of the time-series data is high. When the cardinality of the data for the tenant is too high, the tenant is blacklisted and further data for the tenant is not stored. In addition to identifying incoming time-series data by the tenant that produced it, the data may also identify its type. In this case, the cardinality of each type of data may be determined and the types of data may be individually allowed or blacklisted for the tenant.

TECHNICAL FIELD

The subject matter disclosed herein generally relates to cloud computing. Specifically, in some example embodiments, the present disclosure addresses mechanisms to compute cardinality for a tenant and to limit data processed based on the cardinality computation.

BACKGROUND

Metric data storage stores time-series data reported by clients. The total data storage needed is impacted more by the cardinality of the data than by the number of time-series entries stored. As the cardinality of the data increases, additional shards are added to the database cluster storing the time-series data.

DETAILED DESCRIPTION

Example methods and systems are directed to computing cardinality for a tenant and limiting data processed based on the cardinality computation. Examples merely typify possible variations. Unless explicitly stated otherwise, components and functions are optional and may be combined or subdivided, and operations may vary in sequence or be combined or subdivided. In the following description, for purposes of explanation, numerous specific details are set forth to provide a thorough understanding of example embodiments. It will be evident to one skilled in the art, however, that the present subject matter may be practiced without these specific details.

A cloud-based service records time-series data of a plurality of metrics from a plurality of tenants. Each tenant is a logical entity (e.g., a business, charity, non-profit, department, or other organizational group) comprising one or more client devices. The time-series data comprises a series of measures of a metric at sequential points in time. The source of data may be identified using a tenant identifier or a client identifier that is used to determine the corresponding tenant. The cloud-based service stores the time-series data for later use. Example uses of the time-series data include anomaly detection, intrusion detection, resource allocation, and the like.

The time-series data is recorded in database tables in a manner that consumes more resources when the cardinality of the time-series data is high. In general, the cardinality of a data set is the number of different values in the data set. By contrast, the size of a data set is the number of values in the data set. Thus, the size and the cardinality of a data set are the same only when every value in the data set is different. As used herein, the phrase “cardinality of time-series data” refers to the number of distinct time-series. For example, if one thousand client devices associated with a first tenant are reporting CPU usage data every minute, the cardinality of the time-series data for the first tenant is one thousand. If the one thousand client devices were reporting both CPU usage data and memory usage data, the cardinality of the time-series data for the first tenant would be two thousand—the product of the number of client devices for the tenant that are reporting time-series data with the number of time-series data being reported by each client. As another example, if five thousand client devices associated with a second tenant are reporting CPU usage data every five minutes, the cardinality of the time-series data for the second tenant is five thousand. Note that the total amount of time-series data provided by the first and second tenants are the same, with an average of one thousand data values being provided every minute.

Furthermore, a single client device may report multiple time-series data of the same type, which further increases cardinality. For example, if a client device were, in error, running three copies of the same application that reports time-series data, those three sets of time-series data would increase the cardinality by three instead of only by one. As another example, multiple sets of time-series data may be treated as being of the same type, increasing the cardinality of that type. To illustrate, if CPU usage data is reported for each processor on a multi-processor client device, the cardinality increase for CPU usage data resulting from data reported by the single device is the number of processors, not just one. As another illustration, data may be reported as multiple values (e.g., as a histogram of observations since data was last reported, with the observations divided into predetermined ranges). Each of the separate values reported with each entry in the time-series data increases the cardinality.

Existing systems are able to block further incoming data from a tenant when the size of the data set from the tenant exceeds a threshold, but do not perform rate-limiting (i.e., limiting the rate at which data is accepted by the cloud-based service) in response to a cardinality computation. Many storage solutions respond to a high degree of cardinality by allocating additional database shards to a cluster of database shards in a distributed database, thus keeping the cardinality per shard below the threshold. However, this solution requires additional hardware to be allocated for the tenant. Using the systems and methods described herein, a cardinality for a tenant is determined across all database clusters and, using the cardinality and a threshold, excessive cardinality for the tenant is detected. When the cardinality of the data for the tenant is too high, the tenant is blacklisted and further data for the tenant is not stored. Additionally, the tenant may be informed of the blacklisting, to allow for correction of the problem.

In addition to identifying incoming time-series data by the tenant that produced it, the data may also identify its type, allowing differentiation between data streams produced by the same tenant. In this case, the cardinality of each type of data may be determined and the types of data may be individually allowed or blacklisted for the tenant. In this way, a problem that causes excessive cardinality for only one metric can be responded to by blocking only the time-series data for that metric while time-series data for other metrics are unaffected. When considering the cardinality of a single type of time-series data for a tenant, the number of time-series data is 1. Since the cardinality of time-series data is the product of the number of client devices reporting the time series data with the number of time-series data, the cardinality of a single type of time-series data is just the number of client devices reporting the time-series data for the tenant. For example, a tenant may have one thousand client devices, with five hundred of them reporting one type of time-series data and all one thousand reporting another type of time-series data. Accordingly, the cardinality of the first type of time-series data is less than the cardinality of the second type of time-series data and, depending on the threshold used, further data of the second type may be blocked while data of the first type continues to be processed. Individual metric threshold-based blacklisting is managed, in some example embodiments, by custom policy profiles maintained at the more granular metric level. The threshold for an individual metric may be the same for all tenants or defined on a tenant-specific basis.

To determine the cardinality of a data set over multiple clusters, a cardinality server on each shard of each cluster intercepts the incoming time-series data and determines the cardinality of the time-series data stored on the shard. A central assessment service reads all cardinality information from all shards and, based on the read data, determines the cardinality of the time-series data from the tenant. In some example embodiments, the central assessment service determines the cardinality of the time-series data from the tenant to be the highest cardinality reported by the shards. Based on the cardinality and a predetermined threshold, the cardinality server determines whether to allow or block further time-series data from the tenant.

Technical problems exist with respect to handling incoming time-series data for database storage efficiently. The systems and methods described herein seek to address these problems by using cardinality servers in combination with a central assessment service to detect and block high-cardinality data streams. As a result of this technical improvement, anomalous is behavior is detected quickly and affected tenants are notified, and hardware resources that would be used in storing the high-cardinality data are saved.

Additionally, computing resources may be saved by using the systems and methods described herein, which is a further technical improvement. Examples of such computing resources include processor cycles, network traffic, memory usage, data storage capacity, power consumption, and cooling capacity. As just one example, by blocking high-cardinality data from being processed, network, storage, and processing resources will be saved that would have been consumed by processing the blocked data, saving processor cycles, memory usage, network bandwidth or other computing resources associated with handling network traffic.

FIG. 1is a network diagram illustrating a network environment100suitable for computing cardinality for a tenant and rate-limiting based on the cardinality computation, according to some example embodiments. The network environment100includes a central server110, clusters120A and120B, and devices130A,130B, and130C communicatively coupled to each other via networks140A,140B,140C, and140D. The clusters120A-120B may be collectively referred to as “clusters120” or generically referred to as a “cluster120.” The devices130A-130C may be collectively referred to as “devices130,” or generically referred to as a “device130.” The networks140A-140D may be collectively referred to as “networks140” or generically referred to as a “network140.” The devices130may interact with the central server110using a web client150A or an app client150B. The central server110and the devices130may each be implemented in a computer system, in whole or in part, as described below with respect toFIG. 2. Though shown as single elements, the clusters120A and120B may be composed of multiple computing devices, each operating as a shard of a distributed database, and each of which may be implemented in a computer system as described below with respect toFIG. 2.

The central server110provides a cardinality service that determines the cardinality of time-series data provided by devices130of a tenant. The time-series data is stored on the clusters120. Each of the clusters120determines the cardinality of the portion of the time-series data stored on the cluster and communicates the cardinality for the cluster to the central server110. The central server110determines, based on the received cardinalities from the clusters120, a cardinality for the time-series data from the tenant. Based on the cardinality, the central server110allows further time-series data from the tenant to be stored or blocks the further time-series data.

As an example, a server of each of the clusters120determines a cardinality for the portion of the data stored by the cluster120using the HyperLogLog algorithm. The server may publish its cardinality information on a hypertext transport protocol (HTTP) endpoint. For example, using the uniform resource locator, http://${hostname}:8091/admin/cardinality. In this example, ${hostname} is the name of the host of the data and 8091 is the port through which the data is accessed.

The basis of the HyperLogLog algorithm is the observation that the cardinality of a multiset of uniformly distributed random numbers can be estimated by calculating the maximum number of leading zeros in the binary representation of each number in the set. If the maximum number of leading zeros observed is n, an estimate for the number of distinct elements in the set is 2n. In the HyperLogLog algorithm, a hash function is applied to each element in the original multiset to obtain a multiset of uniformly distributed random numbers with the same cardinality as the original multiset. The cardinality of this randomly distributed set can then be estimated using the algorithm above. The simple estimate of cardinality obtained using the algorithm above has the disadvantage of a large variance. In the HyperLogLog algorithm, the variance is minimized by splitting the multi set into numerous subsets, calculating the maximum number of leading zeros in the numbers in each of these subsets, and using a harmonic mean to combine these estimates for each subset into an estimate of the cardinality of the whole set.

A cardinality for the set of devices is determined, by the central server110based on the cardinality for the tenant received from each of the clusters120and sums the received cardinalities to determine a cardinality for the tenant over all clusters120.

The web client150A or the app client150B provides a user interface to view cardinality data, to view or modify the blacklist status of tenants, or both. Additionally, the web client150A or the app client150B may operate without user intervention to provide time-series data to the central server110, a cluster120, or both.

Also shown inFIG. 1are users170A,170B, and170C that may be referred to generically as “a user170” or collectively as “users170.” Each user170may be a human user (e.g., a human being), a machine user (e.g., a computer configured by a software program to interact with the devices130and the central server110), or any suitable combination thereof (e.g., a human assisted by a machine or a machine supervised by a human). The users170are not part of the network environment100but are each associated with one or more of the devices130and may be users of the devices130(e.g., the user170A may be an owner of the device130A, the user170B may be an owner of the device130B, and the user170C may be an owner of the device130C). For example, the device130A may be a desktop computer, a vehicle computer, a tablet computer, a navigational device, a portable media device, or a smartphone belonging to the user170A.

Any of the machines, databases, or devices shown inFIG. 1may be implemented in a general-purpose computer modified (e.g., configured or programmed) by software to be a special-purpose computer to perform the functions described herein for that machine, database, or device. For example, a computer system able to implement any one or more of the methodologies described herein is discussed below with respect toFIG. 2. As used herein, a “database” is a data storage resource that stores data structured as a text file, a table, a spreadsheet, a relational database (e.g., an object-relational database, a NoSQL database, a network or graph database), a triple store, a hierarchical data store, a key-value store, or any suitable combination thereof. Additionally, data accessed (or stored) via an application programming interface (API) or remote procedure call (RPC) may be considered to be accessed from (or stored to) a database. Moreover, any two or more of the machines, databases, or devices illustrated inFIG. 1may be combined into a single machine, database, or device, and the functions described herein for any single machine, database, or device may be subdivided among multiple machines, databases, or devices.

Each network140may be any network that enables communication between or among machines, databases, and devices (e.g., the central server110, the clusters120, and the devices130). Accordingly, each network140may be a wired network, a wireless network (e.g., a mobile or cellular network), or any suitable combination thereof. Each network140may include one or more portions that constitute a private network, a public network (e.g., the Internet), or any suitable combination thereof.

FIG. 2is a block diagram illustrating components of a computer200(e.g., the central server110), according to some example embodiments. All components need not be used in various embodiments. For example, clients, servers, autonomous systems, and cloud-based network resources may each use a different set of components, or, in the case of servers for example, larger storage devices.

One example computing device in the form of the computer200(also referred to as a computing device200and a computer system200) includes a processor205, a computer-storage medium210, removable storage215, and non-removable storage220, all connected by a bus240. Although the example computing device is illustrated and described as the computer200, the computing device may be in different forms in different embodiments. For example, the computing device200may instead be a smartphone, a tablet, a smartwatch, or another computing device including elements the same as or similar to those illustrated and described with regard toFIG. 2. Devices such as smartphones, tablets, and smartwatches are collectively referred to as “mobile devices.” Further, although the various data storage elements are illustrated as part of the computer200, the storage may also or alternatively include cloud-based storage accessible via a network, such as the Internet, or server-based storage.

The computer-storage medium210includes volatile memory245and non-volatile memory250. The volatile memory245or the non-volatile memory250stores a program255. The computer200may include, or have access to, a computing environment that includes a variety of computer-readable media, such as the volatile memory245, the non-volatile memory250, the removable storage215, and the non-removable storage220. Computer storage includes random-access memory (RAM), read-only memory (ROM), erasable programmable read-only memory (EPROM) and electrically erasable programmable read-only memory (EEPROM), flash memory or other memory technologies, compact disc read-only memory (CD ROM), digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium capable of storing computer-readable instructions.

The computer200includes or has access to a computing environment that includes an input interface225, an output interface230, and a communication interface235. The output interface230interfaces to or includes a display device, such as a touchscreen, that also may serve as an input device. The input interface225interfaces to or includes one or more of a touchscreen, a touchpad, a mouse, a keyboard, a camera, one or more device-specific buttons, one or more sensors integrated within or coupled via wired or wireless data connections to the computer200, and other input devices. The computer200may operate in a networked environment using the communication interface235to connect to one or more remote computers, such as database servers. The remote computer may include a personal computer (PC), server, router, network PC, peer device or other common network node, or the like. The communication interface235may connect to a local-area network (LAN), a wide-area network (WAN), a cellular network, a WiFi network, a Bluetooth network, or other networks.

The program255may further be transmitted or received over the networks140using a transmission medium via the communication interface235and utilizing any one of a number of well-known transfer protocols (e.g., HTTP). Examples of networks140include a local area network (LAN), a wide area network (WAN), the Internet, mobile telephone networks, plain old telephone service (POTS) networks, and wireless data networks (e.g., WiFi, LTE, and WiMAX networks). The term “transmission medium” shall be taken to include any intangible medium that is capable of storing, encoding, or carrying instructions for execution by the computer200, and includes digital or analog communications signals or other intangible media to facilitate communication of such software.

The program255is shown as including a cardinality module260, a blacklist module265, and a route module270. Any one or more of the modules described herein may be implemented using hardware (e.g., a processor of a machine, an application-specific integrated circuit (ASIC), an FPGA, or any suitable combination thereof). Moreover, any two or more of these modules may be combined into a single module, and the functions described herein for a single module may be subdivided among multiple modules. Furthermore, according to various example embodiments, modules described herein as being implemented within a single machine, database, or device may be distributed across multiple machines, databases, or devices.

The cardinality module260of the central server110interacts with the cardinality module260of a server of the clusters120to determine a cardinality for time-series data from a tenant. For example, the devices130A and130C may be associated with a single tenant identifier and provide time-series data to the clusters120for storage. The cardinality module260of a server of each cluster120determines a cardinality for the portion of the time-series data stored on the cluster and provides the cardinality to the cardinality module260of the central server110. While in some example embodiments, a tenant corresponds to a client device, more commonly multiple client devices are assigned to a single tenant identifier. Based on the received cardinalities for the clusters120, the cardinality module260of the central server110determines a cardinality for the time-series data across all clusters120. In some example embodiments, the cardinality determined by the cardinality module260of the central server110is the sum of the received cardinalities.

The blacklist module265determines which time-series data is blacklisted based on a cardinality determined by the cardinality module260and a predetermined threshold (e.g., an administrator-defined threshold on a per tenant, per data type, or per data type per tenant basis). The blacklisting may be for a tenant or for a particular type of data for a tenant. The blacklisting may be permanent (until reversed by user interaction) or for a predetermined period of time (e.g., an hour, a day, or a week).

The route module270intercepts incoming requests to write time-series data to a database stored on the clusters120. Based on a tenant identifier of the time-series data and blacklist data provided by the blacklist module265, the route module270determines whether to allow the received time-series data to be stored or not.

FIG. 3is a block diagram illustrating a database schema300suitable for recording cardinality of data provided by tenants and identifying tenants blacklisted based on the cardinality of the data provided, according to some example embodiments. The database schema300is suitable for use by the cardinality module260, the blacklist module265, and the route module270. The database schema300includes a blacklist table310, a cardinality table340, and a threshold table370. The blacklist table310is defined by a table definition320, including a tenant identifier field, a data identifier field, a start time field, and an expiration field. The blacklist table310includes rows330A and330B. The cardinality table340is defined by a table definition350, including a tenant identifier field, a data type field, and a cardinality field. The cardinality table340includes rows360A,360B,360C, and360D. The threshold table370is defined by a table definition380, including a tenant identifier field, a data type field, and a cardinality field. The threshold table370includes rows390A,390B,390C, and390D.

Each of the rows330A-330B stores information for a blacklisted tenant. The tenant identifier field stores a unique identifier for the blacklisted tenant. The data identifier field comprises one or more identifiers for the types of data that are blacklisted for the tenant. Thus, the row330A indicates that all data is blacklisted for the tenant identifier101and the row330B indicates that data of type1003is blacklisted for the tenant identifier103. The start time and expiration fields indicate when the blacklisting began and when it expires. In some example embodiments, a NULL entry in the expiration field indicates that the blacklisting does not expire and continues indefinitely. As shown inFIG. 3, the blacklisting may be for different periods of time in different rows. The period of time for blacklisting is based on the tenant identifier, the data identifier, the cardinality for the tenant, the cardinality of the time-series data, or any suitable combination thereof. The blacklist table310may be populated by the blacklist module265and accessed by the route module270.

Each of the rows360A-360D stores information for a cardinality for a data type for a tenant. The data type corresponds to the data identifier of the blacklist table310. By way of example, the cardinality table340shows cardinalities for data types of total latency, query count, error count, and row count, for four different tenants. The cardinality table340may be populated by the cardinality module260and accessed by the blacklist module265.

Each row of the threshold table370stores information for a threshold cardinality for a data type for a tenant. The data type corresponds to the data type of the cardinality table340and the data identifier of the blacklist table310. The row390A indicates that when the total cardinality for tenant101exceeds 7.5 million, all further data for the tenant is to be blacklisted. The row390B indicates that when the cardinality for data type1002for tenant102exceeds 8 million, data type1002is blacklisted for tenant102. The row390C indicates that when the cardinality for data type1003for tenant103exceeds 7 million, data type103is blacklisted for tenant103. The row390D indicates that when the total cardinality for tenant103exceeds 8 million, all further data for the tenant is to be blacklisted. As can be seen fromFIG. 3, the entries in the blacklist table310are consistent with the observed cardinalities stored in the cardinality table340and the blacklisting thresholds stored in the threshold table370.

In some example embodiments, the cardinality table340stores cardinality data relating to data received over a particular period of time (e.g., one day), rather than to all data stored. In these example embodiments, the blacklists are set to expire at the end of the period of time (e.g., at midnight each night) and the thresholds apply to each period of time separately. In this way, cardinality is metered within each period of time rather than over all time.

FIG. 4is a flow diagram illustrating operations by the central server110in a method400of measuring and using cardinalities to block data from a tenant, according to some example embodiments. The method400includes operations410,420,430, and440and allows the central server110to block data from tenants providing time-series data of excessive cardinality while causing time-series data from other tenants to be stored on one or more of the clusters120. By way of example and not limitation, the method400is described as being performed by the systems, modules, and databases ofFIGS. 1-3.

In operation410, communication interface235of the central server110serially receives a plurality of data from a set of devices (e.g., one or more of the devices130). As an example, daemons running on a set of devices sharing a tenant identifier send time-series data to the central server110for storage. The data is received by one or more ingress daemons running on the central server110.

The communication interface235of the central server110, in operation420, provides the received data to the clusters120. As an example, the route module270of the central server110selects one of the clusters120for each entry in the time-series data and instructs the selected cluster120to store the entry. In some example embodiments, the selection of the cluster120is based on a hash of the entry or a hash of a portion of the entry. Thus, each cluster120handles a distinct portion of the time-series data, as allocated by the central server110.

As an example, the cardinality module260of a server of each of the clusters120determines a cardinality for the portion of the data stored by the cluster120using the HyperLogLog algorithm. The server may publish its cardinality information on an HTTP endpoint. For example, using the uniform resource locator, http://{hostname}:8091/admin/cardinality. In this example, ${hostname} is the name of the host of the data and 8091 is the port through which the data is accessed.

The information may be provided from the HTTP endpoint using the example data format:

The cardinality information identifies the range of time over which the information was computed in “startime” and “endtime.” namespaces[ ]→namespaces→count indicates the cardinality on the cluster for a tenant. namespaces[ ]→namespaces→names[ ]→count indicates the cardinality of an individual metric. In some example embodiments, the data reported in the names[ ] array is for the top K metric names for the tenant. K may be a predetermined number or the metrics exceeding a predetermined threshold may be reported, allowing K to vary.

A cardinality of the plurality of data is determined, in operation430, by the cardinality module260of the central server110based on the received plurality of data. The cardinality module260of the central server110requests the cardinality for the tenant from each of the clusters120and sums the received cardinalities to determine a cardinality for the tenant over all clusters120. The determined cardinality may be stored in the cardinality table340.

In operation440, the blacklist module265of the central server110, based on the cardinality and a predetermined threshold, blocks at least some further data from the set of devices. As an example, the predetermined threshold is 8,388,608 and all further data from the tenant is blocked when the cardinality for the tenant exceeds the threshold until an administrator removes the block. As another example, the threshold is applied to a specific type of time-series data, the cardinality for the tenant is determined for the specific type of time-series data, and only the specific type of time-series data is blocked when the cardinality for the type of time-series data exceeds the predetermined threshold for cardinality for the type of time-series data. In some example embodiments, the blocking of the tenant (or the type of data for the tenant) is for a predetermined period of time (e.g., an hour, a day, or a week). The blocking of the data may be indicated by a row in the blacklist table310. In some example embodiments, the data is only blocked if a system clock indicates that the current time is before the time in the expiration column. Thus, receipt of data for the tenant resumes at a time determined when the row was added to the blacklist table310.

The central server110exposes blacklist information on an HTTP endpoint, e.g., http://${central hostname}/blacklist.” Information on the blacklisted tenants and metrics may be provided by the HTTP endpoint using the example data format:

In some example embodiments, in addition to operation440or as an alternative to operation440, the central server110, based on the cardinality and the predetermined threshold, sends a notification to an administrator account of the set of devices. The notification may allow the administrator to address the high cardinality of supplied data. If the notification is provided before the set of devices are blacklisted (e.g., a first threshold is used to trigger the sending of the notification and a second threshold is used to trigger the blacklisting), the notification may allow the administrator to correct the issue before blacklisting occurs. If the notification is provided after the set of devices are blacklisted (e.g., a single threshold is used to trigger both the sending of the notification and the blacklisting), the notification may allow the administrator to correct the issue and request manual removal of the blacklisting status before the expiration time.

Thus, by use of the method400, the central server110, in cooperation with the clusters120, is able to monitor the cardinality of data provided by tenants and block data based on the cardinality and a predetermined threshold. As a result, data series of high cardinality are blocked, preventing the clusters120from allocating additional hardware resources to store the high-cardinality data series, thus saving hardware resources and improving performance for the unblocked time-series data being stored.

FIG. 5is a flow diagram illustrating operations by the central server110in a method500of measuring and using cardinalities to block data from a tenant, according to some example embodiments. The method500includes the method400and operations510,520, and530and may be used to enhance the method400. By way of example and not limitation, the method500is described as being performed by the systems, modules, and databases ofFIGS. 1-3.

In operation510, the communication interface235of the central server110serially receives a second plurality of data from a second set of devices. As an example, a second set of devices sharing a second tenant identifier sends time-series data to the central server110for storage. The received data may be routed by the route module270to one or more clusters120. The plurality of data and the second plurality of data may be interleaved. As an example, each device of the set of devices and the second set of devices periodically (e.g., once per second, once per minute, once per hour, or once per day) sends data representing information about the state of the device to the central server110. Thus, the serially receiving of the plurality of data (in operation410) and of the second plurality of data (in operation510) may be overlapping and may each extend over a period of time.

The cardinality module260of the central server110, in operation520, determines a second cardinality of the second plurality of data. As in operation430, this may be performed by having the cardinality module260of a server of each cluster120determine the cardinality for the portion of the second plurality of data stored on the cluster120and determining, by the cardinality module260of the central server110, the total cardinality across all clusters120.

In operation530, based on the second cardinality and a second predetermined threshold, the route module270of the central server110causes second further data from the second set of devices to be stored while blocking the at least some further data from the set of devices. As an example and with reference to the cardinality table340, the first plurality of data has cardinality 7,974,287 as shown in the row360A and the second plurality of data has cardinality 7,074,135 as shown in the row360D. Using a threshold of 7,500,000 for both tenants101and104, the cardinality for tenant101has exceeded the threshold and the cardinality for tenant104has not. Accordingly, the blacklist table310includes the row330A, showing that all data for tenant101is blocked, and does not include a row that indicates that data for tenant104is blocked. As a result, the route module270routes further received data for the tenant104to the clusters120while blocking further data from the tenant101. In this example, the threshold for both tenants is the same, but the threshold may be determined on a per-tenant basis, a per-type basis, or a per-tenant-per-type basis.

Though the method500is described as handling two tenants, operations510-530may be repeated with appropriate modification for additional types of data and additional tenants. Thus, arbitrary numbers of tenants and data types may be supported, with arbitrary amounts of data being blocked according to the blacklist table310and the remaining time-series data stored in the clusters120. Additionally, the use of a whitelist (indicating tenants that are allowed to store data) in addition to or instead of a blacklist is contemplated.

FIG. 6is a flow diagram illustrating operations by one or more servers (e.g., the central server110in conjunction with servers of the clusters120) in a method600of determining a cardinality, according to some example embodiments. The method600includes operations610,620,630,640, and650. By way of example and not limitation, the method600is described as being performed by the systems, modules, and databases ofFIGS. 1-3.

In operation610, the cardinality module260of each shard of a first database cluster (e.g., the cluster120A) determines a first shard cardinality for a tenant or for a type of time-series data for the tenant. The shard cardinality indicates the number of different data values (for the tenant or for the type of time-series data for the tenant) that are stored on the shard. Operation610may be performed periodically (e.g., once per hour) or continuously (e.g., with a cardinality that is updated upon the receipt of each new piece of data).

The cardinality module260of a server of the first database cluster, in operation620, determines, for the first database cluster, a first cluster cardinality based on the first shard cardinalities. The first cluster cardinality may be the maximum of the first shard cardinalities or the sum of the first shared cardinalities. Operation620may be performed periodically (e.g., by querying each shard once per hour) or continuously (e.g., by receiving a notification from each shard whenever the shard updates a cardinality).

Operations630and640repeat operations610and620for a second database cluster, resulting in a second cluster cardinality. In operation650, the cardinality module260of the central server110determines a cardinality based on the first cluster cardinality and the second cluster cardinality. For example, the cardinality may be the sum of the first cluster cardinality and the second cluster cardinality. The cardinality may be stored in the cardinality table340.

Thus, by use of the method600, the operations to determine the cardinality of time-series data are divided among shards, servers, and the central server110. This division of labor allows for accurate cardinalities to be determined without overtaxing any one server and causing computation delays. Accordingly, use of the method600improves over prior art systems that accessed all time-series data by a single server to determine a cardinality for the time-series data.

FIG. 7is a flow diagram illustrating operations by a central server in a method700of measuring and using cardinalities to block data from a tenant, according to some example embodiments. The method700includes operations710,720,730,740,750,760, and770. By way of example and not limitation, the method700is described as being performed by the systems, modules, and databases ofFIGS. 1-3.

In operation710, the communication interface235of the central server110or a server of a cluster120receives data from a tenant, the data being of a type. The data may include a type identifier, a tenant identifier, a user identifier, a device identifier, a time stamp, a data value, or any suitable combination thereof.

The blacklist module265of the receiving server determines, in operation720, if the type of data is blacklisted for the tenant. As an example, the blacklist table310is accessed to determine if the type field of a row for the tenant indicates that the type of data is blacklisted. If the type of data is not blacklisted, the method700proceeds with operation730. If the type of data is blacklisted, the method700proceeds with operation770.

In operation730, the route module270stores the data in a database. As an example, a receiving server of a cluster120causes the data to be stored in the cluster120. As another example, data received by the central server110is provided via a network140to a cluster120for storage.

The cardinality module260, in operation740, updates a cardinality for the type of data for the tenant. In some example embodiments, the cardinality is updated by the central server110and stored in the cardinality table340in response to the receipt of the data. In other example embodiments, a cardinality for a shard or a cluster is updated in response to the receipt of the data and later accessed by the central server110for use in determining the cardinality for storage in the cardinality table340(e.g., by using the method600).

In operation750, the blacklist module265determines if the cardinality for the type of data for the tenant exceeds a predetermined threshold. If the threshold is exceeded, the method700continues with operation760. If the threshold is not exceeded, the method700returns to operation710.

The blacklist module265, in operation760, adds the type of data for the tenant to a blacklist (e.g., by adding or updating a row in the blacklist table310). After the blacklist is updated, the method700returns to operation710.

In operation770, resulting from a determination that the type of data is blacklisted for the tenant in operation720, the route module270refrains from storing the data in the database and the method700returns to operation710.

After execution of operation750,760, or770returns the method700to operation710, the method700is repeated for data of the same type and tenant, a different type and the same tenant, the same type and a different tenant, or a different type and a different tenant. Thus, over multiple iterations, incoming data from multiple tenants and of multiple types is stored in a database so long as the cardinality for the particular type/tenant combination does not exceed the predetermined threshold.

In some example embodiments, the cardinality for each type of data for a tenant is summed to generate a cardinality for the tenant. The cardinality for the tenant is compared to a predetermined threshold and, if the cardinality exceeds the threshold, further data of all types is blocked for the tenant.

Further, the methods of blacklisting tenants and tenant/type pairs discussed herein may be implemented in combination with methods of dealing with high cardinality by allocating additional database shards. Thus, when the cardinality of a type of data for a tenant (or for all data for the tenant) exceeds a first predetermined threshold, an additional database shard is allocated for the data for the tenant. Multiple intermediate thresholds may be used to allocate multiple additional database shards. When the cardinality of the data increases beyond a second predetermined threshold, the data type for the tenant or the tenant as a whole is blacklisted.

The systems and methods described herein monitor the cardinality of data provided by tenants and block data based on the cardinality and a predetermined threshold. As a result of this technical improvement, data series of high cardinality are blocked, preventing the clusters120from allocating additional hardware resources to store the high-cardinality data series, thus saving hardware resources and improving performance for the unblocked time-series data being stored.

When these effects are considered in aggregate, one or more of the methodologies described herein may obviate a need for certain efforts or computing resources that otherwise would be involved in processing and storing time-series data. Additional computing resources used by one or more machines, databases, or devices (e.g., within the network environment100) are saved by rate-limiting based on the cardinality computation. Examples of such computing resources include processor cycles, network traffic, memory usage, data storage capacity, power consumption, and cooling capacity.

In example embodiments, operations may be performed by one or more programmable processors executing a computer program to perform functions by operating on input data and generating output. Method operations can also be performed by, and apparatus of example embodiments may be implemented as, special-purpose logic circuitry (e.g., an FPGA or an ASIC).