Platform for Continuous Mobile-Cloud Services

• US 20120297249A1
• Filed: 05/16/2011
• Published: 11/22/2012
• Est. Priority Date: 05/16/2011
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Yang, Fan, Qian, Zhengping, Chen, Xiuwei, Beschastnikh, Ivan, Zhou, Lidong, Shen, Guobin, Zhuang, Li
• Granted Patent: US 8,745,434 B2
• Time in Patent Office: Days
• US Class Current: 714/19
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 11/1482 by means of middleware or OS functionality
• CPC Class Codes: G06F 9/5072 Grid computing

Abstract

Data that is collected and disseminated by mobile devices typically has to be processed, correlated with other data, aggregated, and then transmitted back to the mobile device users before the information becomes stale or otherwise irrelevant. These operations may be performed in a cloud-based solution that manages dataflow. The cloud-based solutions may be scalable and implemented in a fault-tolerant distributed system to support user-facing continuous sensing and processing services in the cloud-computing system. A system may monitor execution of data and shift workloads (i.e., balancing) in response to spatial and temporal load imbalances that occur in a continuous computing environment. A failure recovery protocol may be implemented that uses a checkpoint-based partial rollback recovery mechanism with selective re-execution, which may allow recovery of the continuous processing after an error while avoiding large amounts of downtime and re-execution.

Claims

1. A method of managing workload of a data stream, the method comprising:

receiving the data stream from a plurality of mobile devices;

translating a logical plan for processing the data stream into a physical plan that enables deployment of a plurality of workers in a cloud-computing system to process the data stream;

assigning the data stream to the plurality of workers for processing based at least in part on the physical plan;

reallocating work between the plurality of workers to maintain a utilization of each worker between a minimum threshold and a maximum threshold; and

creating checkpoints during the processing of the data stream to enable failure recovery by rolling back to a last checkpoint during a recovery process after occurrence of a failure by at least one of the plurality of workers.

2. The method as recited in claim 1, further comprising deploying additional workers to process the data stream when the utilization of the plurality of workers exceeds the maximum threshold.

3. The method as recited in claim 1, further comprising, in response to the fault, rolling back to a latest checkpoint and then re-executing processing by the plurality of the workers who read from the locally stored output in their input workers.

4. The method as recited in claim 3, further comprising using a combination of partial rollback recover and map/reduce style re-computation from previous states based at least in part on the checkpoints to balance between run-time overhead and recovery cost during the processing of the data stream.

5. The method as recited in claim 1, further comprising performing a garbage collection process after incoming data logs for the data stream are determined to be stable at an end of a computation performed by the plurality of workers.

6. The method as recited in claim 1, further comprising storing the data stream in distributed storage before the assigning, and wherein the assigning is at least temporarily delayed after a receipt of a surge of the data stream that, when distributed to the plurality of workers, would result in a utilization of the plurality of workers that surpasses a maximum threshold.

7. A method comprising:

receiving a data stream from a plurality of mobile devices;

allocating the data stream to distributed storage devices for at least temporary storage;

assigning processing of the data stream from the distributed storage to workers in a cloud-computing system; and

reallocating work between the workers when the utilization of a worker reaches or exceeds a maximum threshold.

8. The method as recited in claim 7, further comprising:

aggregating results over the processed data; and

transmitting the aggregated results to at least a portion of the plurality of mobile devices.

9. The method as recited in claim 7, further comprising deploying or removing workers based at least in part on the utilization of the workers.

10. The method as recited in claim 7, wherein the data stream is a substantially continuous data stream, and wherein the data stream is stored in the distributed storage for additional time after receipt of a surge of the data stream to avoid a utilization of the workers that reaches or exceeds a maximum threshold.

11. The method as recited in claim 7, further comprising checkpointing to enable rollback after a failure.

12. The method as recited in claim 11, further comprising:

rolling back computation to a latest checkpoint after detecting the failure; and

re-executing processing by the workers of the data stream based at least in part on the latest checkpoint.

13. The method as recited in claim 7, wherein the assigning processing of the data stream includes determining a window of time or amount of data for a continuous incremental computation to be processed by the workers.

14. The method as recited in claim 7, further comprising translating a logical plan for processing the data stream into a physical plan that enables deployment of the workers to process the data stream.

15. The method as recited in claim 7, further comprising providing a same set of stream-based interfaces for stream operation and mobile-cloud communication for use by developers to implement the stream operation and the mobile-cloud communication.

16. One or more computer-readable media storing computer-executable instructions that, when executed on one or more processors, causes the one or more processors to perform acts comprising:

dispatching a data stream to a distributed storage;

assigning the data stream stored in the distributed storage to workers in a cloud-computing system for processing of the data stream; and

creating checkpoints to enable fault recovery after a fault by rolling back to a latest checkpoint and re-executing processing of the data streams.

17. The one or more computer-readable media as recited in claim 16, further comprising reallocating work between the plurality of workers to maintain a utilization of each worker between a minimum threshold and a maximum threshold.

18. The one or more computer-readable media as recited in claim 16, further comprising deploying additional workers to process the data stream when the utilization of the plurality of workers exceeds the maximum threshold.

19. The one or more computer-readable media as recited in claim 16, further comprising using a combination of partial rollback recover and map/reduce style re-computation from previous states based at least in part on the checkpoints.

20. The one or more computer-readable media as recited in claim 16, wherein the assigning is at least temporarily delayed after receipt of a surge of the data stream which, when distributed to the workers, would result in a utilization of the workers that reaches or exceeds a maximum threshold.