Processing data feeds

• US 8,595,234 B2
• Filed: 11/18/2011
• Issued: 11/26/2013
• Est. Priority Date: 05/17/2010
• Status: Active Grant

• Current Assignee: Walmart Apollo, LLC (WalMart Inc.)
• Original Assignee: Wal-Mart Stores Texas LLC (WalMart Inc.)
• Inventors: Siripurapu, Taraka Subrahmanya Prasad, Lamba, Digvijay Singh, Rajaraman, Anand, Lam, Wang Chee
• Primary Examiner(s): DANG, THANH HA T
• Application Number:
  US13/300,524
• Publication Number:
  US 20120131139A1
• Time in Patent Office: 739 Days
• Field of Search: 707/737
• US Class Current: 707/737
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: H04L 65/60 Network streaming of media packets

Abstract

Exemplary embodiments allow performance of stream computations on real-time data streams using one or more map operations and/or one or more update operations. A map operation is a stream computation in which stream events in one or more real-time data streams are processed in a real-time manner to generate zero, one or more new stream events. An update operation is a stream computation in which stream events in one or more real-time data streams are processed in a real-time manner to create or update one or more static “slate” data structures that are stored in a durable manner.

Claims

1. A computer-implemented method for processing of real-time data streams, the method comprising:

receiving in a real-time manner, at a first worker process, a first input stream event in a first real-time input data stream comprising a plurality of stream events

processing in a real-time manner, at the first worker process, the first input stream event in a first map operation to generate first intermediate output data;

transforming the first intermediate output data at the first worker process, to generate a first intermediate stream event associated with at least one slate that records a set of related stream events;

transmitting in a real-time manner, using the first worker process, the first intermediate stream event in a first real-time intermediate data stream;

receiving in a real-time manner, at a second worker process, the first intermediate stream event in the first real-time intermediate data stream;

processing in a real-time manner, at the second worker process, the first intermediate output data in the first intermediate stream event in a first update operation to generate first final output data; and

storing the first final output data in a first data structure associated with the first intermediate output data on a storage device.

2. The computer-implemented method of claim 1, wherein the first map operation is subscribed to receive the plurality of stream events in the first real-time input data stream, and wherein the first update operation is subscribed to receive stream events from the first real-time intermediate data stream.

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

receiving, at a conductor process, the first input stream event in the first real-time input data stream;

determining that the first map operation is subscribed to receive the plurality of stream events in the first real-time input data stream;

scheduling the first map operation for performance on the first worker process; and

transmitting the first input stream event to the first worker process.

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

receiving, at a conductor process, the first intermediate stream event in the first real-time intermediate data stream;

determining that the first update operation is subscribed to receive stream events in the first real-time intermediate data stream;

scheduling the first update operation for performance on the second worker process; and

transmitting the first intermediate stream event to the second worker process.

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

determining a computational load at one or more worker nodes on a network; and

scheduling the first and second worker processes on first and second worker nodes with the lowest computation loads.

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

assigning a first worker node as a primary worker node for performing the first update operation associated with the first data structure; and

storing the first data structure in memory at the first worker node for access after performing the update operation.

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

receiving in a real-time manner, at a third worker process, a second input stream event in a second real-time input data stream comprising a plurality of stream events;

processing in a real-time manner, at the third worker process, the second input stream event in a second map operation to generate second intermediate output data;

generating, at the third worker process, a second intermediate stream event corresponding to the second input stream event and comprising the second intermediate output data;

transmitting, using the third worker process, the second intermediate stream event in a second real-time intermediate data stream in a real-time manner;

receiving in a real-time manner, at a fourth worker process, the second intermediate stream event in the second real-time intermediate data stream;

processing in a real-time manner, at the fourth worker process, the second intermediate output data in the second intermediate stream event in a second update operation to generate second final output data; and

storing the second final output data in a second data structure associated with the second intermediate output data on a storage device.

8. The computer-implemented method of claim 7, wherein the first worker process and the third worker process operate concurrently to perform the first and second map operations, respectively.

9. The computer-implemented method of claim 7, wherein the second worker process and the fourth worker process operate concurrently to perform the first and second update operations, respectively.

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

transmitting, using the second worker process, a second intermediate stream event comprising the first final output data in a second intermediate real-time data stream in a real-time manner;

receiving in a real-time manner, at a third worker process, the second intermediate stream event in the second real-time intermediate data stream;

processing in a real-time manner, at the third worker process, the first final output data in the second intermediate stream event in a second update operation to generate second final output data; and

storing the second final output data in a second data structure associated with the second intermediate output data on a storage device.

11. The computer-implemented method of claim 1, wherein the first input stream event is a unit of data transmitted in the first real-time input data stream in a real-time manner, and wherein the first intermediate stream event is a unit of data transmitted in the first real-time intermediate data stream in a real-time manner.

12. A distributed computational system, comprising:

a computer-readable storage device for storing computer-executable code associated with a first map operation and a first update operation, and for storing static data output by the first update operation;

a scheduling module for scheduling the first map operation to run on a first worker node and the first update operation to run on a second worker node;

the first worker node programmed to;

receive in a real-time manner a first input stream event in a first real-time input data stream comprising a plurality of stream events,

run the first map operation to process in a real-time manner the first input stream event to generate first intermediate output data,

generate a first intermediate stream event associated with at least one slate that records a set of related stream events, and

transmit the first intermediate stream event in a first real-time intermediate data stream in a real-time manner; and

the second worker node programmed to;

receive in a real-time manner the first intermediate stream event in the first real-time intermediate data stream,

run the first update operation to process in a real-time manner the first intermediate output data in the first intermediate stream event to generate first final output data, and

store the first final output data in a first data structure associated with the first intermediate output data on the storage device.

13. The distributed computational system of claim 12, wherein the first map operation is subscribed to receive the plurality of stream events in the first real-time input data stream, and wherein the first update operation is subscribed to receive stream events from the first real-time intermediate data stream.

14. The distributed computational system of claim 12, wherein the scheduling module is programmed to:

receive the first input stream event in the first real-time input data stream;

determine that the first map operation is subscribed to receive the plurality of stream events in the first real-time input data stream;

schedule the first map operation for performance on the first worker process; and

transmit the first input stream event to the first worker process.

15. The distributed computational system of claim 12, wherein the scheduling module is programmed to:

receiving the first intermediate stream event in the first real-time intermediate data stream;

determining that the first update operation is subscribed to receive stream events in the first real-time intermediate data stream;

scheduling the first update operation for performance on the second worker process; and

transmitting the first intermediate stream event to the second worker process.

16. One or more non-transitory computer-readable storage media having encoded thereon computer-executable instructions for performing a method for processing real-time data streams, the method comprising:

receiving in a real-time manner, at a first worker process, a first input stream event in a first real-time input data stream comprising a plurality of stream events;

processing in a real-time manner, at the first worker process, the first input stream event in a first map operation to generate first intermediate output data;

transforming the first intermediate output data, at the first worker process, to generate a first intermediate stream event associated with at least one slate that records a set of related stream events;

transmitting in a real-time manner, using the first worker process, the first intermediate stream event in a first real-time intermediate data stream;

receiving in a real-time manner, at a second worker process, the first intermediate stream event in the first real-time intermediate data stream;

processing in a real-time manner, at the second worker process, the first intermediate output data in the first intermediate stream event in a first update operation to generate first final output data; and

storing the first final output data in a first data structure associated with the first intermediate output data on a storage device.

17. The one or more non-transitory computer-readable storage media of claim 16, wherein the first map operation is subscribed to receive the plurality of stream events in the first real-time input data stream, and wherein the first update operation is subscribed to receive stream events from the first real-time intermediate data stream.

18. The one or more non-transitory computer-readable storage media of claim 16, wherein the method further comprises:

receiving, at a conductor process, the first input stream event in the first real-time input data stream;

determining that the first map operation is subscribed to receive the plurality of stream events in the first real-time input data stream;

scheduling the first map operation for performance on the first worker process; and

transmitting the first input stream event to the first worker process.

19. The one or more non-transitory computer-readable storage media of claim 16, wherein the method further comprises:

receiving, at a conductor process, the first intermediate stream event in the first real-time intermediate data stream;

determining that the first update operation is subscribed to receive stream events in the first real-time intermediate data stream;

scheduling the first update operation for performance on the second worker process; and

transmitting the first intermediate stream event to the second worker process.

20. The one or more non-transitory computer-readable storage media of claim 16, wherein the method further comprises:

receiving in a real-time manner, at a third worker process, a second input stream event in a second real-time input data stream comprising a plurality of stream events;

processing in a real-time manner, at the third worker process, the second input stream event in a second map operation to generate second intermediate output data;

generating, at the third worker process, a second intermediate stream event associated with at least one slate that records a set of related stream events

transmitting, using the third worker process, the second intermediate stream event in a second real-time intermediate data stream in a real-time manner;

receiving in a real-time manner, at a fourth worker process, the second intermediate stream event in the second real-time intermediate data stream;

processing in a real-time manner, at the fourth worker process, the second intermediate output data in the second intermediate stream event in a second update operation to generate second final output data; and

storing the second final output data in a second data structure associated with the second intermediate output data on a storage device.

21. The one or more non-transitory computer-readable storage media of claim 20, wherein the first worker process and the third worker process operate concurrently to perform the first and second map operations, respectively.

22. The one or more non-transitory computer-readable storage media of claim 20, wherein the second worker process and the fourth worker process operate concurrently to perform the first and second update operations, respectively.

23. The one or more non-transitory computer-readable storage media of claim 16, wherein the method further comprises:

transmitting, using the second worker process, a second intermediate stream event comprising the first final output data in a second intermediate real-time data stream in a real-time manner;

receiving in a real-time manner, at a third worker process, the second intermediate stream event in the second real-time intermediate data stream;

processing in a real-time manner, at the third worker process, the first final output data in the second intermediate stream event in a second update operation to generate second final output data; and

storing the second final output data in a second data structure associated with the second intermediate output data on a storage device.

24. The one or more non-transitory computer-readable storage media of claim 16, wherein the method further comprises:

assigning a first worker node as a primary worker node for performing the first update operation associated with the first data structure; and

storing the first data structure in memory at the first worker node for access after performing the update operation.

25. A computer-implemented method for processing of real-time data streams, the method comprising:

receiving in a real-time manner, at a first worker process running on a first computational device, a first stream event in a first real-time data stream;

processing in a real-time manner, at the first worker process at the first computational device, the first stream event in a first map operation to generate first output data;

transforming the first output data, at the first worker process at the first computational device, to generate a second stream event associated with at least one slate that records a set of related stream events; and

transmitting the second stream event in a real-time manner using the first worker process at the first computational device.

26. A computer-implemented method for processing of real-time data streams, the method comprising:

receiving in a real-time manner, at a first worker process running on a first computational device, a first stream event in a first real-time data stream, the first stream event comprising first input data;

processing in a real-time manner, at the first worker process at the first computational device, the first input data contained in the first stream event in a first map operation to generate first output data;

transforming the first output data, at the first worker process at the first computational device, to generate or update a first data structure associated with at least one slate that records a set of related stream events; and

storing the first data structure on a durable storage device.