Page History

...

Algorithm incremental-rebalancing

Input Set of Tasks,
	  Set of Instances,
      Set of Workers,

      Where each worker contains:
		Set of active Tasks,
		Set of standby Tasks,
		owned by which instance

Main Function
	Separate out Tasks into stateful bucket and stateless bucket
	
	Assign Stateful active tasks: (if any)
		To instances with learner tasks that indicates "ready"
		To previous owners
		To unready learner tasks owners
  	 	To instances with standby tasks
		To resource available instances

 	AssignPick Statelesslearner tasks: (if any)
		To previous owners
  	 	To instances with standby tasks
		To resource available instances

 out of heaviest loaded instances
 
	Assign learner tasks: (if any)
		To previous owners (no half way bounce at least in the first version)
		To new -coming instances with abundant resource (first version)
		MoveTo tasksinstances outwith ofcorresponding heaviest loaded instances first standby tasks

	Assign standby tasks: (if any)
		To instances without matching active tasks
			To previous active task owners
		To resource available instances
		Based on num.standby.task config, this could take multiple rounds

Output Finalized Task Assignment

...

A detailed analysis and benchmark support need to be built before fully devoting effort to this feature. Intuitively most applications should be able to tolerate minor discrepancy of task replaying time, while the cost of extra rebalances and increased debugging complexity are definitely things we are not in favor of. 

The success of version 3.0 is upon version 1.0 success. This work , and could be done concurrently with version 2.0.

Version 4.0 (Stretch)

Delivery goal: eventual workload balance

The 4.0 and the final version will take application eventual load balance into consideration. If we define a balancing factor x, the total number of tasks each instance owns should be within the range of +-x% of the expected number of tasks, which buffers some capacity in order to avoid imbalance.

As long as the group members/ number of tasks are not changing, there should be a defined balanced stage instead of forever rebalancing.
Instances with standby tasks have higher priority to be chosen as learner task assignor. The standby task will convert to learner task immediately.

...

A stream.imbalance.percentage will be provided for the user to configure. The smaller this number sets to, the more strict the assignment will behave.

We also want to balance the load separately for stateful tasks and stateless tasks. 

As we could see, there should be only exactly one learner task after each round of rebalance, and there should be exactly one corresponding active task at the same time. 

Algorithm Trade-offs

We open a special section to discuss the trade-offs of the new algorithm, because it's important to understand the change motivation and make the proposal more robust. 

...

...