DISTRIBUTED STREAM PROCESSING IN THE CLOUD

• US 20160006779A1
• Filed: 07/01/2014
• Published: 01/07/2016
• Est. Priority Date: 07/01/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhou, Jingren, Qian, Zhengping, Zabback, Peter, Lin, Wei
• Granted Patent: US 9,641,580 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1438 Restarting or rejuvenating
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: H04L 65/60 Network streaming of media packets

Abstract

A low-latency cloud-scale computation environment includes a query language, optimization, scheduling, fault tolerance and fault recovery. An event model can be used to extend a declarative query language so that temporal analysis of event of an event stream can be performed. Extractors and outputters can be used to define and implement functions that extend the capabilities of the event-based query language. A script written in the extended query language can be translated into an optimal parallel continuous execution plan. Execution of the plan can be orchestrated by a streaming job manager which schedules vertices on available computing machines. The streaming job manager can monitor overall job execution. Fault tolerance can be provided by tracking execution progress and data dependencies in each vertex. In the event of a failure, another instance of the failed vertex can be scheduled. An optimal recovery point can be determined based on checkpoints and data dependencies.

Claims

1. A system comprising:

at least one processor;

a memory connected to the at least one processor; and

at least one program module comprising a streaming job manager that monitors execution information about streaming jobs executed by a plurality of vertices executing on a plurality of computing devices, the streaming job manager receiving execution progress information and data dependencies for the plurality of vertices.

2. The system of claim 1, the streaming job manager scheduling a new vertex in response to detecting a failed vertex of the plurality of vertices, the streaming job manager determining a closest checkpoint from which to resume processing on the new vertex.

3. The system of claim 2, the streaming job manager calculating a minimum sequence number of event sequence numbers from which the new vertex resumes processing.

4. The system of claim 1, further comprising at least one program module comprising a script processor that receives a script written in a declarative query language, the declarative query language supporting distributed stream processing through temporal analysis of input event streams.

5. The system of claim 1, further comprising at least one program module comprising a streaming execution plan optimizer that receives a compiled script written in a declarative query language, the declarative query language having a capability to receive user-defined functions to consume event streams.

6. The system of claim 1, further comprising at least one program module that assigns a monotonically increasing sequence number to an event of a plurality of events in an event stream.

7. The system of claim 1, further comprising at least one program module that assigns a sequence number to an event in an event stream to track dependencies between input, output and state of a vertex.

8. A method comprising:

receiving by a processor of a computing device, execution progress information associated with streaming jobs executed by a plurality of vertices executing on a plurality of computing devices;

in response to detecting a vertex failure among the plurality of vertices, scheduling a new vertex; and

determining a closest checkpoint from which to resume processing on the new vertex from monotonically increasing sequence numbers assigned to events in an event stream.

9. The method of claim 8, further comprising:

performing failure recovery by calculating a minimum sequence number of event sequence numbers from which the new vertex resumes processing.

10. The method of claim 8, further comprising:

receiving a script in a query language extended to support distributed stream processing through temporal analysis of event streams; and

generating an optimized streaming execution plan from the script, the script comprising a stream extractor that converts information from a continuous input source into event streams.

11. The method of claim 8, further comprising:

receiving a script in a query language extended to support distributed stream processing through temporal analysis of event streams; and

generating an optimized streaming execution plan from the script, the script comprising a stream outputter that performs user-defined actions processing streaming output events.

12. The method of claim 8, further comprising:

receiving a sequence number associated with a last consumed or a last produced event from a vertex of the plurality of vertices.

13. The method of claim 8, further comprising:

receiving dependency information associated with a plurality of executing streaming jobs.

14. A computer-readable storage medium comprising computer-readable instructions which when executed cause at least one processor of a computing device to:

receive data dependency information associated with streaming jobs executed by a plurality of vertices executing on a plurality of computing devices;

in response to detecting a vertex failure among the plurality of vertices, perform job recovery by scheduling a new vertex; and

determine a closest checkpoint from which to resume processing on the new vertex using sequence numbers assigned to events in an event stream.

15. The computer-readable storage medium of claim 14, comprising further computer-readable instructions which when executed cause the at least one processor to:

calculate a minimum sequence number of event sequence numbers from which the new vertex resumes processing based on stored checkpointing data.

16. The computer-readable storage medium of claim 15, comprising further computer-readable instructions which when executed cause the at least one processor to:

generate an optimized streaming execution plan from a script written in a query language extended to support distributed stream processing through temporal analysis of input event streams.

17. The computer-readable storage medium of claim 14, comprising further computer-readable instructions which when executed cause the at least one processor to:

generate an optimized streaming execution plan from a script written in a query language having a capability to receive user-defined functions to consume event streams.

18. The computer-readable storage medium of claim 14, comprising further computer-readable instructions which when executed cause the at least one processor to:

generate an optimized streaming execution plan from a script written in a query language having a capability to receive user-defined functions to produce event streams.

19. The computer-readable storage medium of claim 14, comprising further computer-readable instructions which when executed cause the at least one processor to:

receive execution progress information comprising last event processed and last event produced from a vertex of a plurality of vertices.

20. The computer-readable storage medium of claim 19, comprising further computer-readable instructions which when executed cause the at least one processor to:

assign a monotonically increasing sequence number to each event in an event stream.