fair workload balancer: smarter tradeoff between migration and balance

[gcristian]

Today I have only two options to presort duties before the clustering by workload. One is by creation date, which gives little to small migrations at all The other is by workload, which causes lot of migrations, what is killer for non-idempotent duties. In case duties are short-term tasks, rebalancing with workload pre-sort is bad. In this case no pre-sort will be better than simply assigning the duty to the less compromised shard. In every scenario, I think we could plan a tradeoff between duty migration and shard workload, in order to keep migration to the minimum while still having balanced nodes, as long as they're under a certain dynamically calculated range of duty workload. So project several strategies, and take the choice with less migration and better balance, considering also those non-idempotent tasks that cannot be moved.

[gcristian]

another unavoidable strategy I think, is to let the rebalance as a sysadmin operation, this aint bad, sometimes duties might not need migration at all, and balancing might be a manual request.

[gcristian]

Why the creation date presort also migrates duties ? think of: s1 = 50 (50) ; s2 = 35 (10,10,10,5) If I add 1 more with workload 30 at the less busy shard s2, in order to balance it, it will move its first duty with workload value 10, to the shard s1. in order to have s1 = 60 and s2 = 55, i.e. balancing at the cost of migrating another duty. This's a quite visible sample, but lot of migration occurs depending on the natural order that different workload duties may appear in time... For this case, range threshold may help a bit, in order to delay migrations

[gcristian]

Now I realize that Minka is lacking of a Capacity workload balancer, no less. That is, a fair algorithm that takes into account the shard's reported maximum weight for each pallet. Brought to light recently by the pallet grouping idea. So instead of working on presorting, the main pivot is the user-defined shard max weight. If every pallet exhausts different physical resources, the max weight varies accordingly to hardware. This lets the user to think in fueling balance given by duties and shards instead of shallow load numbers. Pretty basic really, better late than never.