Dynamic n-dimensional cubes for hosted analytics

• US 10,430,438 B2
• Filed: 09/23/2014
• Issued: 10/01/2019
• Est. Priority Date: 06/20/2014
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Kalki, Santosh, Raghavan, Srinivasan Sundar, Rath, Timothy Andrew, Karnik, Mukul Vijay, Devgan, Amol, Sivasubramanian, Swaminathan
• Primary Examiner(s): Featherstone, Mark D
• Assistant Examiner(s): Doraiswamy, Ranjit P
• Application Number:
  US14/494,506
• Publication Number:
  US 20150370881A1
• Time in Patent Office: 1,834 Days
• CPC Class Codes: G06F 16/185 Hierarchical storage management [HSM] systems, e.g. file migration or policies thereof details of archiving G06F16/11
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/26 Visual data mining; Browsing structured data
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/282 Hierarchical databases, e.g. IMS, LDAP data stores or Lotus Notes
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 21/6236 between heterogeneous systems
• CPC Class Codes: H04L 63/10 for controlling access to devices or network resources

Abstract

An online analytical processing system may comprise an n-dimensional cube structured using slice-based partitioning in which each slice comprises one or more hierarchies of data points. A region of a hierarchy may be classified according to computational demands associated with the region. A scaling or replication mechanism may be applied to the region based on the computational demands associated with that region.

Claims

1. A system, comprising:

one or more memories comprising computer-readable instructions that, upon execution by a computing device, cause the system at least to;

store a slice of an n-dimensional cube on a plurality of computing nodes comprising a first one or more computing nodes and a second one or more computing nodes, the slice comprising a hierarchy of data points and additional data points corresponding to intersections of one or more fixed dimensions and one or more variable dimensions, wherein the system is to;

store a first portion of the slice comprising a first subset of the hierarchy of data points on the first one or more computing nodes, wherein data points are included in the first subset based at least in part on a data point of the hierarchy being associated with a first classification of computational demands associated with maintaining data points in the n-dimensional cube; and

store a second portion of the slice comprising a second subset of the hierarchy of data points on the second one or more computing nodes, wherein data points are included in the second subset based at least in part on a data point of the hierarchy being associated with a second classification of computational demands; and

process a first request to access a data point of the hierarchy by processing the request on the first one or more computing nodes, wherein the first one or more computing nodes are configured with a scaling mechanism based at least in part on the first classification of computational demands.

2. The system of claim 1, wherein the first classification is based on a high write frequency and the scaling mechanism comprises horizontally partitioning data points in the first subset of the hierarchy among the first one or more computing nodes.

3. The system of claim 1, wherein the first classification is based on a high read frequency and the scaling mechanism comprises the first one or more computing nodes including at least one read-only replica of data points of the first subset of the hierarchy.

4. The system of claim 1, further comprising one or more memories comprising computer-readable instructions that, upon execution, cause the system at least to:

classify a region of the hierarchy based at least in part on mapping between a dimension associated with the hierarchy and one or more computational demands associated with the dimension.

5. The system of claim 1, further comprising one or more memories comprising computer-readable instructions that, upon execution, cause the system at least to:

identify a path in the hierarchy based at least in part on a frequency of access for data points in the path; and

maintain the data points associated with the path in main memory while the frequency of access is above a threshold level.

6. A computer-implemented method, comprising:

storing a slice of an n-dimensional cube on a plurality of computing nodes comprising a first computing node and a second computing node, the slice comprising a hierarchy of data points and additional data points corresponding to intersections of one or more fixed dimensions and one or more variable dimensions, wherein storing the slice comprises;

identifying a first subset of the hierarchy of data points, wherein the subset is identified based at least in part on a computational demand associated with a data point in the first subset of the hierarchy, wherein the computational demand is associated with maintaining data points in the n-dimensional cube;

selecting a scaling mechanism based at least in part on the computational demand associated with the data point; and

storing the first subset of the hierarchy on at least the first computing node and the second computing node, wherein the first subset of the hierarchy is at least partitioned or replicated between the first computing node and the second computing node based on the selected scaling mechanism.

7. The method of claim 6, wherein the scaling mechanism is selected based at least in part on write frequency being high relative to read frequency.

8. The method of claim 7, further comprising:

horizontally partitioning data points of the first subset of the hierarchy between at least the first computing node and the second computing node.

9. The method of claim 6, wherein the scaling mechanism is selected based at least in part on read frequency being high relative to a capacity of the first computing node to respond to requests to read data in the first subset of the hierarchy.

10. The method of claim 9, further comprising:

replicating at least a portion of the first subset of the hierarchy on the second computing node, wherein the at least a portion of the first subset of the hierarchy is maintained on the first computing node.

11. The method of claim 6, further comprising:

classifying a region of the hierarchy based at least in part on a mapping between a dimension associated with the hierarchy and a computational demand associated with the dimension.

12. The method of claim 6, further comprising:

identifying a path in the hierarchy based at least in part on a frequency of access for data points in the path; and

maintaining the data points associated with the path in main memory while the frequency of access is above a threshold level.

13. The method of claim 6, further comprising:

selecting a second scaling mechanism for an additional subset of the hierarchy, based at least in part on computational demands associated with data points in the additional subset.

14. A non-transitory computer-readable storage medium comprising instructions that, upon execution by one or more computing devices, cause the one or more computing devices at least to:

determine to store a slice of an n-dimensional cube on a plurality of computing nodes comprising a first one or more computing nodes and a second one or more computing nodes, the slice comprising a hierarchy of data points and additional data points corresponding to intersections of one or more fixed dimensions and one or more variable dimensions;

store a first subset of the hierarchy of data points on the first one or more computing nodes, wherein data points are included in the first subset based at least in part on a data point in the hierarchy being associated with a first classification of computational demands, wherein the data points included in the first subset are at least partitioned or replicated, between computing nodes of the first one or more computing nodes, based at least in part on the first classification of computational demands associated with maintaining data points in the n-dimensional cube; and

store a second subset of the hierarchy of data points on the second one or more computing nodes, wherein data points are included in the second subset based at least in part on a data point in the hierarchy being associated with a second classification of computational demands.

15. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

determine to relocate a portion of the first subset of the hierarchy of data points from the first one or more computing nodes, the determining based at least in part on monitoring computational demands associated with the data point.

16. The non-transitory computer-readable storage medium of claim 14, wherein the first classification is based on a high write frequency and data points of the first subset of the hierarchy are horizontally partitioned among the first one or more computing nodes.

17. The non-transitory computer-readable storage medium of claim 14, wherein the first classification is based on a high read frequency and the first one or more computing nodes comprise a writeable partition and a read-only replica.

18. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

classify a region of the hierarchy based at least in part on mapping between a dimension associated with the hierarchy and one or more computational demands associated with the dimension.

19. The non-transitory computer-readable storage medium of claim 14, comprising further instructions that, upon execution by the one or more computing devices, cause the one or more computing devices to at least:

identify a path in the hierarchy based at least in part on a frequency of access for data points in the path; and

maintain the data points associated with the path in main memory while the frequency of access is above a threshold level.