Providing strong ordering in multi-stage streaming processing

• US 10,191,768 B2
• Filed: 12/31/2015
• Issued: 01/29/2019
• Est. Priority Date: 09/16/2015
• Status: Active Grant

• Current Assignee: Salesforce.com, Inc.
• Original Assignee: Salesforce.com, Inc.
• Inventors: Bishop, Elden Gregory, Chao, Jeffrey
• Primary Examiner(s): Puente, Emerson C
• Assistant Examiner(s): Labud, Jonathan R
• Application Number:
  US14/986,365
• Publication Number:
  US 20170075721A1
• Time in Patent Office: 1,125 Days
• CPC Class Codes: G06F 2209/484 Precedence
• CPC Class Codes: G06F 2209/485 Resource constraint
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

The technology disclosed relates to providing strong ordering in multi-stage processing of near real-time (NRT) data streams. In particular, it relates to maintaining current batch-stage information for a batch at a grid-scheduler in communication with a grid-coordinator that controls dispatch of batch-units to the physical threads for a batch-stage. This includes operating a computing grid, and queuing data from the NRT data streams as batches in pipelines for processing over multiple stages in the computing grid. Also included is determining, for a current batch-stage, batch-units pending dispatch, in response to receiving the current batch-stage information; identifying physical threads that processed batch-units for a previous batch-stage on which the current batch-stage depends and have registered pending tasks for the current batch-stage; and dispatching the batch-units for the current batch-stage to the identified physical threads subsequent to complete processing of the batch-units for the previous batch-stage.

Claims

1. A method of providing strong ordering in multi-stage processing of data streams, the method including:

receiving, by a grid coordinator operating a computing grid that includes a plurality of physical threads which process data from one or more data streams in batches, current batch-stage information from a grid-scheduler comprising current-batch units and downstream batch-units that depend on completion of the current-batch units;

determining, for a current batch-stage identified in the current batch-stage information a batch-unit pending dispatch from the downstream batch-units;

identifying one or more physical threads that processed batch-units for the current batch-stage on which the batch unit pending dispatch depends and have registered pending tasks for the current batch-stage; and

dispatching the batch unit pending dispatch to the one or more identified physical threads subsequent to complete processing of the batch-units for the current batch-stage.

2. The method of claim 1, further comprising:

executing multiple processing stages for the batches where the processing stages lack dependencies with each other.

3. The method of claim 1, further including:

registering, at the grid-coordinator, a number of batch-units emitted by respective grid-sources for processing by a physical thread in the one or more physical threads during the current batch-stage;

tracking a number of batch-units processed to completion by the one or more physical threads during the current batch-stage;

responsive to initiation of a next batch-stage by the grid-scheduler, validating, using a by the grid-coordinator, whether, for the current batch-stage, the tracked number of batch-units match a registered number of batch-units; and

responsive to a mismatch, reloading the current batch-stage for complete processing of the registered number of batch-units by the one or more physical threads.

4. The method of claim 1, wherein the grid scheduler queues a batch in a pipeline of a plurality of pipelines and wherein the pipeline processes the batch over multiple stages in the computing grid.

5. The method of claim 1, wherein the grid scheduler assigns a pipeline identifier to a pipeline of a plurality of pipelines in the computing grid.

6. The method of claim 1, wherein the grid scheduler assigns a batch identifier to a batch in the batches.

7. The method of claim 1, wherein the grid scheduler assigns a stage identifier to each processing stage of a batch in the batches.

8. The method of claim 1, wherein the grid scheduler communicates to the grid coordinator a batch identifier for a batch in the batches, a stage identifier of each processing stage of a batch in the batches, and a pipeline identifier of a pipeline of a plurality of pipelines in the computing grid.

9. A system including one or more processors coupled to memory, the memory loaded with computer instructions to provide strong ordering in multi-stage processing of data streams, the instructions, when executed on the processors, implement actions comprising:

receiving, by a grid coordinator operating a computing grid that includes a plurality of physical threads which process data from one or more data streams in batches, current batch-stage information from a grid-scheduler comprising current-batch units, and downstream batch-units that depend on completion of the current-batch units;

determining, for a current batch-stage identified in the current batch-stage information a batch-unit pending dispatch from the downstream batch-units;

identifying one or more physical threads that processed batch-units for the current a previous on which the batch-unit pending dispatch depends and have registered pending tasks for the current batch-stage; and

dispatching the batch unit pending dispatch to the one or more identified physical threads subsequent to complete processing of the batch-units for the current batch-stage.

10. The system of claim 9, the one or more processors further configured to:

execute multiple processing stages for the batches where the processing stages lack dependencies with each other.

11. The system of claim 9, the one or more processors further configured to:

registering, at the grid-coordinator, a number of batch-units emitted by respective grid-sources for processing by a physical thread in the one or more physical threads during the current batch-stage;

tracking a number of batch-units processed to completion by the physical thread during the current batch-stage;

responsive to initiation of a next batch-stage by the grid-scheduler, validating, by the grid-coordinator, whether, for the current batch-stage, the tracked number of batch-units match a registered number of batch-units; and

responsive to a mismatch, reloading the current batch-stage for complete processing of the registered number of batch-units by the physical thread.

12. The system of claim 9, wherein the grid scheduler queues a batch in a pipeline of a plurality of pipelines and wherein the pipeline processes the batch over multiple stages in the computing grid.

13. The system of claim 9, wherein the grid scheduler assigns a pipeline identifier to a pipeline of a plurality of pipelines in the computing grid.

14. The system of claim 9, wherein the grid scheduler assigns a batch identifier to a batch in the batches.

15. The system of claim 9, wherein the grid scheduler assigns a stage identifier to each processing stage of a batch in the batches.

16. The system of claim 9, wherein the grid scheduler communicates to the grid coordinator a batch identifier for a batch in the batches, a stage identifier of each processing stage of a batch in the batches, and a pipeline identifier of a pipeline of a plurality of pipelines in the computing grid.

17. A non-transitory computer readable storage medium impressed with computer program instructions to provide strong ordering in multi-stage processing of data streams, the instructions, when executed on a processor, implement a method comprising:

receiving, by a grid coordinator operating a computing grid that includes a plurality of physical threads which process data from one or more data streams in batches, current batch-stage information from a grid-scheduler comprising current-batch units and downstream batch-units that depend on completion of the current-batch units;

determining, for a current batch-stage identified in the current batch-stage information a batch-unit pending dispatch from the downstream batch-units;

identifying one or more physical threads that processed batch-units for the current batch-stage on which the batch unit pending dispatch depends and have registered pending tasks for the current batch-stage; and

dispatching the batch unit pending dispatch to the one or more identified physical threads subsequent to complete processing of the batch-units for the current batch-stage.

18. The non-transitory computer readable storage medium of claim 17, the operations further comprising:

executing multiple processing stages for the batches where the processing stages lack dependencies with each other.

19. The non-transitory computer readable storage medium of claim 17, the operations further comprising:

registering, at the grid-coordinator, a number of batch-units emitted by respective grid-sources for processing by a physical thread in the one or more physical threads during the current batch-stage;

tracking a number of batch-units processed to completion by the physical thread during the current batch-stage;

responsive to initiation of a next batch-stage by the grid-scheduler, validating, by the grid-coordinator, whether, for the current batch-stage, the tracked number of batch-units match a registered number of batch-units; and

responsive to a mismatch, reloading the current batch-stage for complete processing of the registered number of batch-units by the physical thread.

20. The non-transitory computer readable storage medium of claim 17, the operations further comprising:

maintaining strong ordering among the batches by ensuring that current batch-units are processed before the downstream batch-units that depend on the current batch-units.