Cycles of Doom in Batch Processing Workflows

We integrate new data into our databases via a large batch processing workflow. The execution time of this workflow directly affects the time it takes to get new data to our customers, so keeping the runtime small is of paramount importance to us. There’s an interesting effect that can happen which we’ve dubbed the “cycle of doom” which is critical to understand when optimizing these batch processing workflows.

Let’s look at an example. Let’s say we have a workflow which takes 8 hours to run, and so it processes 8 hours of data each iteration. Let’s say you want to add another piece to the workflow which will add 2 hours to the processing time. So that means the workflow runtime will now be 10 hours, with each iteration processing 10 hours of data.

Wrong.

That additional workflow piece will have a secondary effect on the system. The additional workflow piece added 2 hours to process 8 hours of data. This means that next time the workflow runs, there will be 10 hours of data to process. Since the next iteration has more data, it will take longer to run. Which means the next iteration will have even more data, and so on. This is the “cycle of doom.” How long will this spin out of control? How can we determine whether this stabilizes at some point?

Obviously there’s more to this analysis, so let’s take a more formal look at this effect. First, let’s write an equation for how long it takes one iteration of a workflow to complete:

(ITERATION TIME) = OVERHEAD + (TIME TO PROCESS ONE HOUR OF DATA) * (HOURS OF DATA)

Overhead includes things like time to start jobs, loading bloom filters, fixed network latencies, etc. “Time to process one hour of data” means how much time is spent processing the actual data, minus constant factors such as job-startup time. For simplification, let’s use shorter variable names and write this equation as:

T = O + P * H

At some point, the iteration time will stabilize at a constant runtime. We can determine the stabilization point by plugging in T = H, or in English, when the amount of time it takes to run an iteration is equal to the amount of hours of data processed by the iteration. Solving for T, we get:

T = O + P * T
T = O / (1 – P)

There’s a lot of interesting results we can take from this equation. First, if the amount of time it takes to process one hour of data (minus overhead) is more than an hour, then you will hit a cycle of doom and the iteration time will be infinity.

The more interesting result is the effect of overhead. Overhead gets multiplied. So if you have enough cluster capacity to process one hour of data in half an hour, each hour of overhead will actually add 2 hours to your iteration time. If you barely have enough cluster capacity to process one hour of data (let’s say it takes 59 minutes), then each hour of overhead will add 60 hours to your iteration time. As you can see, anything you can do to decrease overhead or decrease the data processing time (like by adding more machines) can have a huge effect on your performance.

Let’s take a look at a real-world example with Rapleaf’s workflow. We recently replaced a piece of our workflow that was writing large amounts of data to a database locally and then copying that database into HDFS. The database was getting really fragmented, so it would take 10 hours to do that copy. We replaced the database with a different system that does streaming writes which got rid of the fragmentation problem. Our workflow runtime went from 30 hours to 6 hours. So, getting rid of 10 hours of overhead had a 5x improvement on iteration time, even though it only accounted for 30% of the original runtime.

Let’s plug the numbers into our equation. We end up with:

30 = O / (1 – P)
6 = (O-10) / (1 – P)

Solving, we get P = 7/12 and O = 12.5. 10 hours of overhead corresponded to 4/5 of our total overhead, which explains the 5x improvement. We also discovered our “data processing rate” to be about half hour for each hour of data.

This equation doesn’t model everything. One factor not modeled in Rapleaf’s workflow is the fact that every iteration adds data to our database, which will slightly raise query times for the next iteration. There’s also variance in the amount of data we receive each hour which changes the analysis somewhat. Even though this equation is just an approximation, we’ve found it to be a fairly close approximation and it has really helped us understand the fundamental factors affecting our iteration times.