Back to results
US 10,884,644 B2Granted
Dynamic distributed data clustering
AssigneeAmazon Technologies, Inc.
InventorsTimothy Andrew Rath, Mustafa Ozan Ozen
Life of this patent
Estimating the term…
Abstract
Techniques are described for clustering data at the point of ingestion for storage using scalable storage resources. The clustering techniques described herein are used to cluster time series data in a manner such that data that is likely to be queried together is localized to a same partition, or to a minimal set of partitions if the data set is large, where the partitions are mapped to physical storage resources where the data is to be stored for subsequent processing. Among other benefits, the clustered storage of the data at the physical storage resources can reduce an amount of data that needs to be filtered by many types of queries, thereby improving the performance of any applications or processes that rely on querying the data.
Claims19
A computer-implemented method comprising:
- generating a partition table used to cluster a plurality of data points based on attribute values associated with the plurality of data points, wherein the partition table is used to cluster the plurality of data points based on attribute values associated with one attribute of a hierarchy of attributes included with the plurality of data points, and wherein the partition table includes a first set of partitions defining a first segmentation of a total range of ordered values;
- receiving a data point including an attribute value;
- determining that the first set of partitions does not include a partition mapped to the attribute value and that there is not an available partition of the first set of partitions to which the attribute value can be mapped;
- generating a second set of partitions by bifurcating each partition of the first set of partitions, the second set of partitions defining a second segmentation of the total range of ordered values;
- mapping the attribute value to an available partition of the second set of partitions;
- mapping the available partition of the second set of partitions to one or more physical storage resources;
- and
- storing the data point at the one or more physical storage resources.
5 more elements
A computer-implemented method comprising:
- generating a partition table used to cluster a plurality of time series data points during ingestion of the plurality of time series data points, wherein the partition table is used to cluster the plurality of time series data points based on attribute values associated with one attribute of a hierarchy of attributes included with the plurality of time series data points, the partition table including a first set of partitions defining a first segmentation of a total range of ordered values, wherein each partition of the first set of partitions can be mapped to a single attribute value of a plurality of attribute values associated with the plurality of time series data points;
- receiving a time series data point generated by a computing device;
- identifying an attribute value associated with the time series data point;
- determining that the first set of partitions does not include a partition mapped to the attribute value and that there is not an available partition of the first set of partitions to which the attribute value can be mapped;
- generating a second set of partitions by bifurcating a subrange associated with each partition of the first set of partitions, the second set of partitions defining a second segmentation of the total range of ordered values;
- mapping the attribute value to an available partition of the second set of partitions;
- mapping the available partition of the second set of partitions to one or more physical storage resources;
- and
- storing the time series data point at the one or more physical storage resources.
6 more elements
A system comprising:
- an ingestion router implemented by a first one or more electronic devices, the ingestion router including instructions that upon execution cause the ingestion router to:
- generate a partition table used to cluster a plurality of data points based on attribute values associated with the plurality of data points, wherein the partition table is used to cluster the plurality of data points based on attribute values associated with one attribute of a hierarchy of attributes included with the plurality of data points, the partition table including a first set of partitions defining a first segmentation of a total range of ordered values;
- receive a data point including an attribute value;
- determine that the first set of partitions does not include a partition mapped to the attribute value and that there is not an available partition of the first set of partitions to which the attribute value can be mapped;
- generate a second set of partitions by bifurcating each partition of the first set of partitions, the second set of partitions defining a second segmentation of the total range of ordered values;
- map the attribute value to an available partition of the second set of partitions;
- map the available partition of the second set of partitions to one or more physical storage resources of a storage service;
- and
- send the data point for storage by the storage service;
- the storage service implemented by a second one or more electronic devices, the storage service including instructions that upon execution cause the storage to:
- receive the data point;
- and
- store the data point at the one or more physical storage resources mapped to the available partition of the second set of partitions.
10 more elements
Dependencies are inferred from the claim text.