Distributed storage of aggregated data

• US 9,898,522 B2
• Filed: 12/16/2014
• Issued: 02/20/2018
• Est. Priority Date: 01/13/2012
• Status: Expired due to Fees

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Cole, Richard J., Mock, Alan D.
• Primary Examiner(s): Le, Miranda
• Application Number:
  US14/572,562
• Publication Number:
  US 20150106325A1
• Time in Patent Office: 1,162 Days
• Field of Search: 707607
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Techniques are described for managing aggregation of data in a distributed manner, such as for a particular client based on specified configuration information. The described techniques may include storing aggregated data values for an OLAP cube or other data structure in a distributed manner, such as in some situations in a distributed hash table. The aggregated data values to be stored may be generated in various manners, such as by performing multi-stage data manipulation operations—for example, a map-reduce architecture may be used, with a first stage involving the use of one or more specified map functions to be performed, and with at least a second stage involving the use of one or more specified reduce functions to be performed.

Claims

1. A computer-implemented method comprising:

storing, by one or more configured computing nodes, a plurality of aggregated data values for an OLAP (“

online analytical processing”

) cube that has multiple dimensions by, for each of the plurality of aggregated data values;

determining a hash key for use with the aggregated data value, wherein the determined hash key is based at least in part on a combination of an aggregation metric used for aggregating the aggregated data value and multiple dimension category values for the multiple dimensions that are associated with the aggregated data value;

determining a storage location within a distributed key-value storage structure stored across multiple storage nodes by using the determined hash key as input to a hash function, wherein output of the hash function indicates the determined storage location, and wherein the determined storage location is within a subset of the distributed key-value storage structure that is stored on one of the multiple storage nodes; and

providing the aggregated data value for storage in the determined storage location on the one storage node as part of the OLAP cube; and

after the storing of the plurality of aggregated data values for the OLAP cube,

receiving a request for one or more of the stored aggregated data values, the request indicating one or more dimension category values for the multiple dimensions of the OLAP cube, and

using the indicated one or more dimension category values to obtain and provide the one or more stored aggregated data values from the distributed key-value storage structure in response to the request.

2. The computer-implemented method of claim 1 wherein the obtaining of the one or more stored aggregated data values from the distributed key-value storage structure includes:

identifying one or more hash keys corresponding to the indicated one or more dimension category values; and

for each of the identified hash keys,

determining a storage location within the distributed key-value storage structure by using the identified hash key as input to the hash function; and

retrieving an aggregated data value stored at the determined storage location.

3. The computer-implemented method of claim 1 wherein multiple aggregation metrics are used in generating the plurality of aggregated data values, and wherein each of the plurality of aggregated data values is part of a data record that includes the aggregated data value and that includes an indication of the associated aggregation metric for the aggregated data value.

4. The computer-implemented method of claim 1 wherein each of the plurality of aggregated data values is part of a data record that includes the aggregated data value and that includes indications of the multiple dimension category values associated with the aggregated data value.

5. The computer-implemented method of claim 1 wherein the hash function is an MD5 hash algorithm or a SHA-1 hash algorithm.

6. The computer-implemented method of claim 1 wherein the one or more configured computing nodes are part of an online data aggregation service, and wherein the method further comprises generating the plurality of aggregated data values for the OLAP cube on behalf of a client of the online data aggregation service.

7. The computer-implemented method of claim 6 wherein the multiple storage nodes are external to the data aggregation service and are provided by the client, and wherein the providing of each aggregated data value for storage includes transmitting the aggregated data value over one or more computer networks from the online data aggregation service to the one storage node for the aggregated data value.

8. The computer-implemented method of claim 6 wherein the multiple storage nodes are part of an online storage service that is external to the online data aggregation service and is accessible to the client, and wherein the providing of each aggregated data value for storage includes transmitting the aggregated data value over one or more computer networks from the online data aggregation service to the online storage service.

9. The computer-implemented method of claim 6 wherein the multiple storage nodes are provided by the online data aggregation service.

10. The computer-implemented method of claim 1 wherein the distributed key-value storage structure is a distributed hash table having a plurality of storage locations that are each available to store information for a key-value pair.

11. The computer-implemented method of claim 1 wherein the distributed key-value storage structure is a distributed hierarchical tree structure that includes a plurality of storage locations, and wherein the determining of the storage location by using the determined hash key for an aggregated data value includes:

identifying multiple storage locations based on the output of the hash function, the multiple storage locations being a subset of the plurality of storage locations; and

selecting one of the multiple storage locations as the determined storage location.

12. The computer-implemented method of claim 1 wherein the providing of each aggregated data value for storage in the determined storage location on the one storage node includes storing the aggregated data value and indications of the multiple dimension category values associated with the aggregated data value in the determined storage location, and wherein each of the multiple storage nodes stores at least one of the plurality of aggregated data values.

13. The computer-implemented method of claim 1 further comprising:

determining that multiple of the plurality of aggregated data values have multiple determined storage locations on a single one of the multiple storage nodes; and

accumulating information for each of the multiple aggregated data values, and

wherein the providing of each of the multiple aggregated data values for storage in the determined storage location on the one storage node includes performing a single loading of the accumulated information to the single one storage node for storage in the multiple determined storage locations.

14. A non-transitory computer-readable medium having stored contents that configure one or more computing systems of an online data aggregation service to:

select, by the configured one or more computing systems and on behalf of a client of the online data aggregation service, multiple storage nodes from a plurality of storage nodes provided by the online data aggregation service;

store, by the configured one or more computing systems and on behalf of the client, a plurality of aggregated data values generated by the online data aggregation service that are each associated with multiple dimension category values for multiple dimensions by, for each of the plurality of aggregated data values;

determining a value for use as a hash key with the aggregated data value, the determined value being based at least in part on a combination of an aggregation metric used for aggregating the aggregated data value and the multiple dimension category values associated with the aggregated data value;

determining a storage location within a key-value storage structure stored across the selected multiple storage nodes by using the determined value as a hash key input to a hash function, wherein output of the hash function indicates the determined storage location; and

providing the aggregated data value for storage in the determined storage location; and

after the plurality of aggregated data values are stored,

receive a request for one or more of the stored aggregated data values, the request indicating one or more dimension category values; and

obtain, by the configured one or more computing systems and by using the indicated one or more dimension category values, the one or more stored aggregated data values from the key-value storage structure to provide in response to the request.

15. The non-transitory computer-readable medium of claim 14 wherein the stored contents include software instructions that, when executed, further configure the one or more computing systems to generate the plurality of aggregated data values for an OLAP (“

online analytical processing”

) cube, and wherein each of the multiple storage nodes includes at least one of the plurality of aggregated data values for the OLAP cube.

16. The non-transitory computer-readable medium of claim 15 wherein the generating of the plurality of aggregated data values uses a first stage having one or more specified map functions and uses at least a second stage having one or more specified reduce functions.

17. A system, comprising:

one or more hardware processors of one or more computing systems; and

one or more memories with software instructions that, when executed by at least one of the one or more hardware processors, cause the at least one hardware processor to implement functionality of an online data aggregation service, including;

selecting, on behalf of a client of the online data aggregation service, multiple storage nodes from a plurality of storage nodes provided by the online data aggregation service;

generating, on behalf of the client, a plurality of aggregated data values for an OLAP (“

online analytical processing”

) cube having multiple dimensions, wherein each of the plurality of aggregated data values is further associated with an aggregation metric used for aggregating the aggregated data value; and

storing the plurality of aggregated data values by, for each of the plurality of aggregated data values;

determining a value for use as a hash key with the aggregated data value, the determined value being based at least in part on the aggregation metric used for aggregating the aggregated data value and on a combination of multiple dimension category values that correspond to the multiple dimensions and that are associated with the aggregated data value;

determining a storage location within a key-value storage structure stored across the selected multiple storage nodes, the determining of the storage location including using the determined value as a hash key input to a hash function, the determined storage location being within a subset of the key-value storage structure that is stored on one of the multiple storage nodes; and

providing the aggregated data value for storage in the determined storage location on the one storage node; and

after the storing of the plurality of aggregated data values,

receiving a request for one or more of the stored aggregated data values, the request indicating one or more dimension category values, and

using the indicated one or more dimension category values to obtain and provide the one or more stored aggregated data values from the key-value storage structure in response to the request.

18. The system of claim 17 wherein the generating of the plurality of aggregated data values includes analyzing a plurality of input data groups specified by the client.

19. The system of claim 17 further comprising the multiple storage nodes and the one or more computing systems.