Optimize task queueing

[drexin]

Currently an app is being added n times to the task queue during a deployment. It would be a lot more efficient to add it only once and include a counter, so that we only match it once against an offer.

[sttts]

Just for my understanding: what exactly is so expensive that it deserves this big optimization of the task queue? What's the complexity of the offer comparison?

Which order of magnitude of tasks can we expect? 10000?

[drexin]

I think we can expect hundreds of thousands of tasks on up to hundreds of thousands of machines. Finding a matching task has quadratic complexity, so if we just add the same app N times, we have a worst case of 100.000 x 100.000 calls to the matching function. Matching also is very expensive. We have seen cases, where Marathon couldn't catch up with the offers.

[sttts]

Ok, O(n^2) is a good reason.

What I saw a lot throughout the code are linear loops over lists of tasks. When calling those indirectly we easily also get bad runtime behavior, but harder to spot.