Cost-aware replication of intermediate data in dataflows

Patent metadata

Field	Value
Publication number	US-8949558-B2
Application number	US-201113097200-A
Country	US
Kind code	B2
Filing date	Apr 29, 2011
Priority date	Apr 29, 2011
Publication date	Feb 3, 2015
Grant date	Feb 3, 2015

Abstract

Described herein are methods, systems, apparatuses and products for cost-aware replication of intermediate data in dataflows. An aspect provides receiving at least one measurement indicative of a reliability cost associated with executing a dataflow; computing a degree of replication of at least one intermediate data set in the dataflow based on the reliability cost; and communicating at least one replication factor to at least one component of a system responsible for replication of the at least one intermediate data set in the dataflow; wherein the at least one intermediate data set is replicated according to the replication factor. Other embodiments are disclosed.

First claim

What is claimed is:

1. A computer program product comprising:
a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising:
computer readable program code configured to receive at least one measurement indicative of a reliability cost associated with executing a dataflow;
computer readable program code configured to compute a degree of replication of at least one intermediate data set in the dataflow based on the reliability cost;
wherein the reliability cost comprises a metric based at least on a sum of two sub-costs, the two sub-costs comprising a cost of replication for the at least one intermediate data set in the dataflow and a cost of regeneration for the at least one intermediate data set in the dataflow;
computer readable program code configured to minimize the reliability cost; and
computer readable program code configured to communicate at least one replication factor, corresponding to the computed degree of replication, to at least one component responsible for replication of the at least one intermediate data set in the dataflow;
wherein the at least one intermediate data set is replicated according to the replication factor.

2. The computer program product according to claim 1 , wherein the at least one measurement indicative of a reliability cost associated with executing the dataflow includes at least one measurement relevant to determining how much intermediate data to replicate at one or more stages of the dataflow.

3. The computer program product according to claim 1 , wherein to compute at least one replication factor further comprises solving a constrained optimization problem.

4. The computer program product according to claim 3 , wherein the constrained optimization problem takes into account at least one of the cost of replication for the at least one intermediate data set in the dataflow and the cost of regeneration for the at least one intermediate data set in the dataflow.

5. The computer program product according to claim 4 , wherein the cost of replication comprises a cost incurred for at least one of creating or destroying replicas of the at least one intermediate data set in the dataflow.

6. The computer program product according to claim 4 , wherein the cost of regeneration comprises a cost of regenerating the at least one intermediate data set in the dataflow.

7. The computer program product according to claim 1 , wherein the at least one measurement indicative of a reliability cost associated with executing the dataflow is obtained from at least one sensor that monitors compute stages in the dataflow at run time.

8. The computer program product according to claim 1 , wherein the computer readable program code configured to compute a degree of replication of at least one intermediate data set in the dataflow is further configured to compute a degree of replication responsive to at least one of:
a predetermined, periodic timing mechanism; and
a completion of a compute stage in the dataflow.

9. The computer program product according to claim 1 , wherein the at least one replication, factor comprises at least one of:
an instruction to replicate an intermediate data set of the dataflow for a particular stage; and
an instruction to delete a replica for an intermediate data set of the dataflow already replicated for a particular stage.

10. The computer program product according to claim 1 , wherein the dataflow comprises a stage wise data computation process in which at least one subsequent stage depends on an intermediate data set computed at a preceding stage.

11. The computer program product according to claim 1 , further comprising computer readable program code configured to provide software as a service in a distributed computing environment.

12. A method comprising:
receiving at least one measurement indicative of a reliability cost associated with executing a dataflow;
computing a degree of replication of at least one intermediate data set in the dataflow based on the reliability cost;
wherein the reliability cost comprises a metric based at least on a sum of two sub-costs, the two sub-costs comprising a cost of replication for the at least one intermediate data set in the dataflow and a cost of regeneration for the at least one intermediate data set in the dataflow;
minimizing the reliability cost; and
communicating at least one replication factor, corresponding to the computed degree of replication, to at least one component responsible for replication of the at least one intermediate data set in the dataflow;
wherein the at least one intermediate data set is replicated according to the replication factor.

13. The method according to claim 12 , wherein to compute at least one replication factor further comprises solving a constrained optimization problem.

14. The method according to claim 13 , wherein the constrained optimization problem takes into account at least one of the cost of replication for the at least one intermediate data set in the dataflow and the cost of regeneration for the at least one intermediate data set in the dataflow.

15. The method according to claim 14 , wherein the cost of replication comprises a cost incurred for at least one of creating or destroying replicas of the at least one intermediate data set in the dataflow.

16. The method according to claim 14 , wherein the cost of regeneration comprises a cost of regenerating the at least one intermediate data set in the dataflow.

17. The method according to claim 12 , wherein the at least one measurement indicative of a reliability cost associated with executing the dataflow is obtained from at least one sensor that monitors compute stages in the dataflow at run time.

18. The method according to claim 12 , wherein computing a degree of replication of at least one intermediate data set in the dataflow further comprises computing a degree of replication responsive to at least one of:
a predetermined, periodic timing mechanism; and
a completion of a compute stage in the dataflow.

19. The method according to claim 12 , wherein the at least one replication factor comprises at least one of:
an instruction to replicate an intermediate data set of the dataflow for a particular stage; and
an instruction to delete a replica for an intermediate data set of the dataflow already replicated for a particular stage.

20. The method according to claim 12 , wherein the dataflow comprises a stage wise data computation process in which at least one subsequent stage depends on an intermediate data set computed at a preceding stage.

21. The method according to claim 12 , further comprising providing software as a service in a distributed computing environment.

22. A system comprising:
at least one processor; and
a memory device operatively connected to the at least one processor;
wherein, responsive to execution of program instructions accessible to the at least one processor, the at least one processor is configured to:
receive at least one measurement indicative of a reliability cost associated with executing a dataflow;
compute a degree of replication of at least one intermediate data set in the dataflow based on the reliability cost;
wherein the reliability cost comprises a metric based at least on a sum of two sub-costs, the two sub-costs comprising a cost of replication for the at least one intermediate data set in the dataflow and a cost of regeneration for the a

Assignees

• Castillo Claris
• Steinder Malgorzata
• Tantawi Asser Nasreldin
• IBM

Inventors

• Castillo Claris
• Steinder Malgorzata
• Tantawi Asser Nasreldin

Classifications

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F17/30575

  Physics · mapped topic

• G06F17/30

  Physics · mapped topic

• G06F12/02 Primary

  Addressing or allocation; Relocation (program address sequencing G06F9/00; arrangements for selecting an address in a digital store G11C8/00) · CPC title

• G06F9/5066

  Algorithms for mapping a plurality of inter-dependent sub-tasks onto a plurality of physical CPUs (mappping at compile time, see G06F8/451) · CPC title