Systems and methods for distributing a workplan for data flow execution based on an arbitrary graph describing the desired data flow

• US 20050278152A1
• Filed: 06/30/2004
• Published: 12/15/2005
• Est. Priority Date: 05/24/2004
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Blaszczak, Michael A.
• Granted Patent: US 7,930,432 B2
• Time in Patent Office: Days
• US Class Current: 703/1
• CPC Class Codes: G06F 16/254 Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Various embodiments of the present invention are directed to the creation of multiple redundant chains of transforms, each on a separate processing thread, for a data flow execution (DFE) of a data transformation pipeline (DTP). For certain of these embodiments, a “distributor” receives a buffer as input and directs that buffer to one of several parallel identical threads to process that buffer. A scheduler would create each of these multiple threads, each thread having an identical (redundant) strings of transforms (chains) downstream from the distributor, and all of which would lead even further downstream to a collector that is responsible for collecting and, if necessary, ordering the buffers processed by the previous redundant chains. In this way, the distributors and collectors provide increased scalability for the pipeline by implicitly partitioning (distributing) individual buffers to one of many threads for at least a part of their execution/processing.

Claims

1. A method for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said method comprising;

creating at least one replica of said original chain (the “

replica chain”

);

adding a distributor immediately upstream from, and coupled to, said original chain and said replica chain; and

adding a collector immediately downstream from, and coupled to, said original chain and said replica chain.

2. The method of claim 1 further comprising:

said distributor receiving a set of buffers;

said distributor distributing a first subset of said set of buffers to said original chain; and

said distributor distributes a second subset of said set of buffers to said replica chain.

3. The method of claim 1 further comprising:

said collector receiving a first subset of buffers from said original chain;

said collector receiving a second subset of buffers from said replica chain; and

said collector sending a set of buffers to a component downstream from said collector, said set of buffers comprising said first subset of buffers and said second subset of buffers.

4. The method of claim 3, wherein said set of buffers comprise an order, said method further comprising said collector reordering said set of buffers based on said order.

5. The method of claim 1 wherein said original chain executes as a first thread and said replica chain executes as a second thread.

6. A method for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said method comprising;

creating at least redundant replicas of said original chain (the “

replica chain”

);

for a set of buffers comprising a plurality of individual buffers, distributing each individual buffer to either said original chain or said replica chain.

7. A system for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said system comprising at least one subsystem for;

creating at least one replica of said original chain (the “

replica chain”

);

adding a distributor immediately upstream from, and coupled to, said original chain and said replica chain; and

adding a collector immediately downstream from, and coupled to, said original chain and said replica chain.

8. The system of claim 7 further comprising at least one subsystem for:

said distributor receiving a set of buffers;

said distributor distributing a first subset of said set of buffers to said original chain; and

said distributor distributes a second subset of said set of buffers to said replica chain.

9. The system of claim 7 further comprising at least one subsystem for:

said collector receiving a first subset of buffers from said original chain;

said collector receiving a second subset of buffers from said replica chain; and

said collector sending a set of buffers to a component downstream from said collector, said set of buffers comprising said first subset of buffers and said second subset of buffers.

10. The system of claim 9, wherein said set of buffers comprise an order, said method further comprising at least one subsystem for said collector to reorder said set of buffers based on said order.

11. The system of claim 7 further comprising at least one subsystem whereby said original chain executes as a first thread and said replica chain executes as a second thread.

12. A system for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said system comprising at least one subsystem for;

creating at least redundant replicas of said original chain (the “

replica chain”

);

for a set of buffers comprising a plurality of individual buffers, distributing each individual buffer to either said original chain or said replica chain.

13. A computer-readable medium comprising computer-readable instructions for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said computer-readable instructions comprising instructions for;

creating at least one replica of said original chain (the “

replica chain”

);

adding a distributor immediately upstream from, and coupled to, said original chain and said replica chain; and

adding a collector immediately downstream from, and coupled to, said original chain and said replica chain.

14. The computer-readable medium of claim 13 further comprising instructions for:

said distributor receiving a set of buffers;

said distributor distributing a first subset of said set of buffers to said original chain; and

said distributor distributes a second subset of said set of buffers to said replica chain.

15. The computer-readable medium of claim 13 further comprising instructions for:

said collector receiving a first subset of buffers from said original chain;

said collector receiving a second subset of buffers from said replica chain; and

said collector sending a set of buffers to a component downstream from said collector, said set of buffers comprising said first subset of buffers and said second subset of buffers.

16. The computer-readable medium of claim 15, wherein said set of buffers comprise an order, said method further comprising instructions whereby said collector reorders said set of buffers based on said order.

17. The computer-readable medium of claim 13 further comprising instructions whereby said original chain executes as a first thread and said replica chain executes as a second thread.

18. A computer-readable medium comprising computer-readable instructions for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said computer-readable instructions comprising instructions for;

creating at least redundant replicas of said original chain (the “

replica chain”

);

for a set of buffers comprising a plurality of individual buffers, distributing each individual buffer to either said original chain or said replica chain.

19. A hardware control device for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said hardware control device comprising means for;

creating at least one replica of said original chain (the “

replica chain”

);

adding a distributor immediately upstream from, and coupled to, said original chain and said replica chain; and

adding a collector immediately downstream from, and coupled to, said original chain and said replica chain.

20. The hardware control device of claim 19 further comprising means for:

said distributor receiving a set of buffers;

said distributor distributing a first subset of said set of buffers to said original chain; and

said distributor distributes a second subset of said set of buffers to said replica chain.

21. The hardware control device of claim 19 further comprising means for:

said collector receiving a first subset of buffers from said original chain;

said collector receiving a second subset of buffers from said replica chain; and

said collector sending a set of buffers to a component downstream from said collector, said set of buffers comprising said first subset of buffers and said second subset of buffers.

22. The hardware control device of claim 21, wherein said set of buffers comprise an order, said hardware control device further comprising means for said collector reordering said set of buffers based on said order.

23. The hardware control device of claim 19 further comprising means whereby said original chain executes as a first thread and said replica chain executes as a second thread.

24. A hardware control device for distributing a workplan for a data flow execution (DFE), said DFE comprising at least one chain of distributable transforms (the “

original chain”

), said hardware control device comprising means for;

creating at least redundant replicas of said original chain (the “

replica chain”

);

for a set of buffers comprising a plurality of individual buffers, distributing each individual buffer to either said original chain or said replica chain.