REAL-TIME ANALYTICS FOR LARGE DATA SETS

• US 20130191523A1
• Filed: 07/18/2012
• Published: 07/25/2013
• Est. Priority Date: 01/19/2012
• Status: Abandoned Application

• Current Assignee: EvoApp, Inc.
• Original Assignee: EvoApp, Inc.
• Inventors: Buck, Leonard Jerome, Burnette, Charles Boyd, Davy, Joseph Patrick, Melnichenko, Alexey Alexeyevich
• Application Number:
  US13/552,435
• Publication Number:
  US 20130191523A1
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 9/5066 Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs mappping at compile time, see G06F8/451

Abstract

A cloud computing system is described herein that enables fast processing of queries over massive amounts of stored data. The system is characterized by the ability to scan tens of billions of data items and to perform aggregate calculations like counts, sums, and averages in real-time (less than three seconds). Ad hoc queries are supported including grouping, sorting, and filtering without the need to predefine queries by providing highly efficient loading and processing of data items across an arbitrarily large number of processors. The system does not require any fixed schema, thus the system supports any type of data. Calculations made to satisfy a query may be distributed across a large number of processors to parallelize the work. In addition, an optimal blob size for storing multiple serialized data items is determined, and existing blobs that are too large or too small are proactively redistributed or coalesced to increase performance.

Claims

1. A cloud computing system comprising:

a plurality of processor nodes, each processor node having access to a local memory device and persistent storage devices;

a blob storage service implemented on the persistent storage devices;

the blob storage service operable to store a plurality of value blobs, each value blob of the plurality of value blobs containing one or more serialized data items;

a key management service operable to store a plurality of keys, each key of the plurality of keys associated with a collection descriptor comprising one or more unique value blob identifiers.

2. The cloud computing system of claim 1,

wherein a set of data items stored by the blob storage service have at least one common attribute and a first data item and a second data item of the set of data items are stored within a common value blob;

the blob storage service further operable to organize the common value blob along a dimension that corresponds to a range of values, the range of values including values of the at least one common attribute of the first data item and the second data item.

3. The cloud computing system of claim 2, wherein the set of data items stored by the blob storage service has a plurality of common attributes;

the blob storage service further operable to;

a) receive a request to store a new data item;

b) identify a plurality of dimensions relevant to the new data item, each dimension of the plurality of dimensions corresponding to an attribute of a plurality of attributes of the new data item; and

c) for each dimension of the plurality of dimensions;

1) allocate a new value blob associated with said each dimension;

2) store a copy of the new data item in the new value blob;

3) generate a unique identifier for the new value blob;

4) identify a particular key corresponding to a range of values in said each dimension, wherein the range of values includes the value of an attribute of the new data item, wherein said attribute corresponds to said each dimension; and

5) insert the unique identifier of the new value blob into the collection descriptor associated with the particular key.

4. The cloud computing system of claim 1, wherein a collection descriptor associated with a key further includes a version indicator that represents a version of the key, and the system further comprising:

a first process running on a processor node retrieving a first key associated with a range of values in a particular dimension, wherein the range of values includes a requested range of values, and a collection descriptor associated with said first key including a first version indicator;

a second process running on a processor node retrieving a second key associated with said range of values in said particular dimension, wherein a collection descriptor associated with said second key including a second version indicator;

wherein the first version indicator is not the same as the second version indicator; and

wherein the first process and the second process run substantially concurrently.

5. The cloud computing system of claim 1, wherein the key management service comprises a key management module operable to assign a name to a key that is associated with a range of attribute values for a particular attribute, wherein the key name is generated based on the range of values and a unique identifier;

wherein the range of values is based on values of data items stored in value blobs referenced by a collection descriptor associated with the named key.

6. The cloud computing system of claim 1, wherein the key management module is further operable to allocate a blob as a key blob, and store a collection descriptor associated with a key in the key blob.

7. The cloud computing system of claim 6, wherein the key management service is operable to issue a lease on a key, ensuring that the lease holder has exclusive access to update data stored in the collection descriptor.

8. The cloud computing system of claim 1, wherein data stored within a value blob is immutable in the value blob;

and

adding a new data item having a value that lies within a range of values represented by a particular key comprises;

allocating a new value blob and storing the new data item in the new value blob;

creating a new version of the particular key; and

storing an identifier of the new value blob in the collection descriptor associated with the new version of the particular key.

9. The cloud computing system of claim 8, wherein a first identifier to a first value blob is stored in a collection descriptor for a first version of the particular key, and changing data stored within the first value blob comprises:

allocating a second value blob having a second identifier;

creating a copy of the first data stored within the first value blob, and changing the copy of the first data to create second data;

storing the second data in a second value blob;

creating a second version of the particular key;

replacing the first identifier with the second identifier in a collection descriptor associated with the second version of the particular key.

10. A cloud computing system comprising:

a plurality of processor nodes, each processor node having access to a local memory device and persistent storage devices;

a blob storage service storing data items having a plurality of dimensions;

a plurality of keys, each key of the plurality of keys corresponding to a particular dimension of the plurality of dimensions and identifying a collection of data items having the particular dimension; and

a query manager operable to;

a) determine a primary dimension referenced by a query expression;

b) identify a set of keys corresponding to the primary dimension;

c) select a set of processor nodes to evaluate a subquery of the incoming query;

d) assign each processor node of the set of processor nodes a set of keys corresponding to the primary dimension, wherein said each processor node evaluates the query expression over the collection of data items identified by each key in the set keys assigned to said each processor node.

11. The cloud computing system of claim 10, wherein

a first set of keys assigned to a first processor and a second set of keys assigned to a second processor are disjoint sets of keys.

12. The cloud computing system of claim 10, wherein

selecting the set of processor nodes includes selecting a particular processor node of the set of processor nodes based at least on presence of data item objects within local memory accessible to the particular processor node, wherein the data item objects are required to evaluate the query.

13. The cloud computing system of claim 10, wherein

determining the primary dimension comprises:

a) identifying a plurality of dimensions referenced by the query expression;

b) determining a cost to evaluate the query expression in each dimension of the plurality of dimensions referenced by the query expression;

c) selecting the primary dimension based on the cost to evaluate the query expression on each dimension;

wherein the primary dimension is a dimension corresponding to a data view,

wherein the data view comprises copies of each data item stored in a value blob that is organized along the primary dimension; and

evaluating the query expression comprises loading data into local memory from the data view corresponding to the primary dimension.

14. A cloud computing system comprising a blob storage manager that stores data items in a blob of a minimum size and a maximum size, wherein the minimum size and the maximum size are determined based at least on a size of local memory or performance data for inflating blobs of a plurality of sizes.

15. The cloud computing system of claim 14, wherein

the maximum size is further determined based at least on a size, when inflated, of the data items stored within a blob.

16. The cloud computing system of claim 14, wherein

the blob storage manager is operable to receive network performance data;

and

the minimum size and the maximum size is determined based at least on the network performance data.

17. The cloud computing system of claim 16, wherein

the network performance data includes at least one of network bandwidth, latency, or error characteristics.

18. The cloud computing system of claim 14, wherein

the maximum size and the minimum size of a value blob used to store data items for a particular data view is further based on an access hit rate for the particular data view;

wherein the access hit rate for the particular data view is based on a number of data items referenced through the particular data view within a time period and a number of data items stored together within a value blob.

19. The cloud computing system of claim 14, wherein

a first maximum size and a first minimum size of a value blob used to store data items for a first data view is different from a second maximum size and a second minimum size of a value blob used to store data items for a second data view.

20. The cloud computing system of claim 14, wherein

the blob storage manager is further operable to:

discover an existing value blob that is larger than said determined maximum size; and

copy each data item stored within the existing value blob into a new value blob of a set of new value blobs, wherein a size of each new value blob is less than or equal to said determined maximum size.

21. The cloud computing system of claim 14, wherein

the blob storage manager is further operable to:

discover an existing value blob that is smaller than said determined minimum size; and

copy each data item stored within the existing value blob into a target value blob of a set of target value blobs, wherein the resulting size of each target value blob of the set of target value blobs is greater than or equal to the determined minimum size and less than or equal to said determined maximum size.

22. A cloud computing system comprising:

a plurality of processor nodes, each processor node having access to a memory device and persistent storage devices;

the persistent storage devices storing a plurality of value blobs, each value blob of the plurality of value blobs containing one or more serialized data items;

a data de-serialization library generator operable to;

a) receive a structure definition for a specific type of data item;

b) based on the structure definition, generate machine-executable instructions comprising a de-serialization library corresponding to the specific type of data item, which when executed, de-serializes a data item of the specific type; and

c) store the de-serialization library in a value blob; and

an object inflation module that, in response to a request to copy a particular data item from persistent storage into a memory device, is operable to retrieve from a value blob a de-serialization library for a particular data item type and execute the library to create and load a data item object into the memory device.