Horizontal scaling of time series data
AssigneeAmazon Technologies, Inc.
InventorsRobert Mark Waugh, Emmanuel Pierre Devillard, Daniel Vassallo, Nitin Kesarwani, Greg Sterin, Hongqi Wang
Life of this patent
Estimating the term…
Abstract
A leader host obtains individual distributions of data sets ingested by individual hosts of a fleet of hosts over a domain. The leader host compiles the individual distributions over the domain to generate a compiled distribution. The leader host then partitions the domain based at least in part on the generated compiled distribution. These partitions of the partitioned domain are distributed to individual hosts of the fleet of hosts, which causes the individual hosts to process a portion of the distributed date set according to their respective partitions.
Claims20
A system, comprising:
- a leader host of a fleet of physical hosts that:
- receives, from a physical host of the fleet of physical hosts, a data histogram that indicates a distribution of time series data over time;
- compiles a plurality of received data histograms that include the received data histogram to generate a compiled data histogram that indicates a compiled distribution of time series data over a time interval;
- partitions the time interval to a plurality of time sub-intervals;
- distributes the plurality of time sub-intervals among physical hosts of the fleet of physical hosts such that a first time sub-interval is distributed to a first physical host that had a highest relative contribution to the first time sub-interval;
- distributes the plurality of time sub-intervals among physical hosts of the fleet of physical hosts such that the first time sub-interval is distributed to the first physical host, wherein the first physical host is selected based on having at least as high a contribution of time series data to the first time sub-interval as other physical hosts;
- and
- the first physical host further:
- receives, from the leader host, information identifying the first time sub-interval;
- communicates with other physical hosts of the fleet of physical hosts to obtain data for the first time sub-interval to generate an aggregated set of data for the first time sub-interval;
- and
- sorts the aggregated set of data.
A computer-implemented method, under control of one or more computer systems configured with executable instructions, comprising:
- obtaining individual distributions of data sets for respective individual computer systems of a fleet of computer systems, the individual distributions of data sets being over a domain and the data sets forming a distributed data set;
- compiling the individual distributions of data sets over the domain to generate a compiled distribution;
- partitioning the domain into a partitioned domain based at least in part on the compiled distribution;
- distributing individual domain partitions of the partitioned domain to individual computer systems of the fleet of computer systems, wherein the fleet of computer systems comprises a first individual computer system and wherein a first individual domain partition is distributed to the first individual computer system if a contribution of data by the first individual computer system to the first individual domain partition is at least as great a contribution to the first individual domain partition as a contribution from another individual computer system of the fleet of computer systems;
- and
- processing, by the individual computer systems, their respective individual partitions so as to sort a portion of the distributed data set.
A non-transitory computer-readable storage medium having stored thereon executable instructions that, when executed by one or more processors of a computer system, cause the computer system to at least:
- obtain data points;
- generate information indicating a distribution of the data points over a domain;
- provide the information to another computer system;
- receive, from the other computer system, information indicating a sub-domain of the domain;
- obtain, from other computer systems of a fleet of computer systems, additional data for the sub-domain of the domain;
- combine the additional data with locally stored data for the sub-domain to form a combined data set corresponding to the sub-domain, wherein the locally stored data comprises at least as much data as data from another computer system;
- and
- perform an operation on the combined data set so as to sort the combined data set.
Dependencies are inferred from the claim text.