Current coverage is 54.76% (diff: 100%)

Merging #1473 into master will decrease coverage by 0.05%

@@             master      #1473   diff @@
==========================================
  Files           107        107          
  Lines         17607      17607          
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
- Hits           9651       9642     -9   
- Misses         6779       6791    +12   
+ Partials       1177       1174     -3   

Powered by Codecov. Last update f6a679d...e5701b8

Design LGTM.

I discussed this with @stevvooe and concluded that there are a number of things that should change in this proposal.

• Making the notion of precedence absolute is too rigid. If one datacenter experiences a problem that causes all of its tasks to fail immediately, tasks will keep getting assigned to it indefinitely, and they will never get scheduled to the datacenter that's still working properly.
• There should be a notion of weighting to give relative strength to the different preferences (i.e. "I want to balance tasks over racks, but it's 20x more important to me to keep tasks balanced between datacenters"). This is distinct from weights that we may eventually add on individual label values ("prefer datacenter A over datacenter B by factor X").
• It is difficult to describe the current proposal mathematically, and to implement it efficiently.

I think all three problems can be addressed well by moving to a weighted random selection algorithm. Based on the initial state, the user's preferences, and the number of tasks being scheduled, we could compute relative weights for the nodes that would guide the final state towards the distribution we want. Then we would assign each task with a Monte Carlo approach. I'm going to think more about an approach along these lines and change the proposal if it works out.

To be honest, not a fan.

Last time we implemented random relative weight distribution it was for the agent weighted peers. Then we hit problems. Can't remember the exact issue, it was the agent taking forever to reconnect on manager failure. It took a lot of effort from @LK4D4 and @aaronlehmann (IIRC) to debug and fix. Long story short, it took longer to implement, was harder to debug, less predictable and more difficult to tweak to real life scenarios.

In hindsight, a simple round robin would have been the better choice.

Making the notion of precedence absolute is too rigid. If one datacenter experiences a problem that causes all of its tasks to fail immediately, tasks will keep getting assigned to it indefinitely, and they will never get scheduled to the datacenter that's still working properly.

I think we're mixing two different problems. This feature is not about federation and multi datacenter, it's just about having a user defined spreading factor.

Nodes failing (even if it's a set of nodes sharing a common label) should be handled by the node failure system already in place. Eventually those nodes would be marked as down. We also have another proposal in place to quarantine nodes (due to the swarm2k issue).

There should be a notion of weighting to give relative strength to the different preferences

The complexity (not just in terms of implementation but also of operability) far outweighs the advantages.

I want to balance tasks over racks, but it's 20x more important to me to keep tasks balanced between datacenters

Then list datacenter first and rack later. Ask the user to list the preferences by importance rather than specifying relative weight.

It is difficult to describe the current proposal mathematically, and to implement it efficiently.

Isn't this basically a multisort function?

Nodes failing (even if it's a set of nodes sharing a common label) should be handled by the node failure system already in place. Eventually those nodes would be marked as down. We also have another proposal in place to quarantine nodes (due to the swarm2k issue).

I don't think I'm familiar with this. Is there an issue or design document about quarantining nodes?

Then list datacenter first and rack later. Ask the user to list the preferences by importance rather than specifying relative weight.

That was the plan in this proposal, but now I think it could be too limiting. If there's some problem that prevents one of the criteria you listed from getting balanced, the scheduler will try to do that forever, and never consider any of the lower-precedence criteria that was given by the user.

Isn't this basically a multisort function?

Yes, exactly. But the moment you assign a task, it could totally change the rankings (for example, if the nodes are evenly split between two datacenter, and I assign a new task to one of the datacenters, all the nodes in the other datacenter will move to the top half of the rankings). So far I haven't found a good way to avoid doing a full scan over the nodes for every task that's assigned. It seems possible, but it gets really complicated. With the naive approach, scheduling n tasks on m nodes is O(m*n).

Just curious, do you like the proposal as currently stated?

Last time we implemented random relative weight distribution it was for the agent weighted peers. Then we hit problems.

These problems had nothing to do with the use of random weighting and the time spent by @aaronlehmann and @LK4D4 were mostly due to ranging errors in observable failure reporting.

But the moment you assign a task, it could totally change the rankings (for example, if the nodes are evenly split between two datacenter, and I assign a new task to one of the datacenters, all the nodes in the other datacenter will move to the top half of the rankings).

This is similar to the issue of assigning k tasks to n sorted feasible nodes. Instead of keep finding the best node, I think it ok just to assign each node a task the top k nodes. With a dynamic environment, trying to achieve best option is not really useful.

This is similar to the issue of assigning k tasks to n sorted feasible nodes. Instead of keep finding the best node, I think it ok just to assign each node a task the top k nodes. With a dynamic environment, trying to achieve best option is not really useful.

I don't think this approach really makes sense. Suppose I have 10 nodes in each of two AZs. I start with only one replica, in AZ 1. Now I want to scale up to 10 replicas. The nodes from AZ 2 will all rank highest when I sort. So I'll end up with 9 tasks in AZ 2 and only 1 in AZ 1, which is a really bad outcome.

I don't think this approach really makes sense. Suppose I have 10 nodes in each of two AZs. I start with only one replica, in AZ 1. Now I want to scale up to 10 replicas. The nodes from AZ 2 will all rank highest when I sort. So I'll end up with 9 tasks in AZ 2 and only 1 in AZ 1, which is a really bad outcome.

I'm thinking a different approach. In topology aware scenario, a total order of the nodes isn't that useful. In stead we may have the nodes in buckets. If there are 2 AZs, they could split the tasks (weighted or not) first. Then select nodes for tasks within each AZ.

Reopening, this is still under active discussion.

With the node labels scheduler could construct a topology architecture as a tree. The tasks from a service start splitting in a top down approach. In this example, the root assigns tasks to rows, the rows assign tasks to racks, the racks then select nodes for the tasks.

There are 2 approaches in the assignment. It could be equal at each level, or weighted (depends on how many nodes eligible for the tasks).

For the sake of exploration, I implemented the deterministic approach described in the original proposal based on @dongluochen's bucket tree suggestion above: aaronlehmann@db2c93c

It's not tested or very clean or optimized yet, but it should completely handle all the cases (i.e. resource-limited cases where we have to backtrack and assign a task to a different place in the tree than we concluded was best).

I'm still not fully sure whether I prefer the deterministic or Monte Carlo approach, so I'm trying to experiment with designs and see how things turn out. The fact that I could put this together this reasonably efficient implementation in a few hours and it's actually fairly comprehensible makes me feel better about the deterministic approach than I felt this morning.

Also added a stupidly simple test that spreads over two values of a label that have an uneven number of nodes associated with them: aaronlehmann@aa776e6

BTW, while this proof of concept implementation is deterministic, I don't think it would be a very big change to add random jitter to the way tasks are distributed at each level of the tree. This could be desirable to avoid situations where we deterministically schedule tasks to the same bad node indefinitely. On the other hand, it could be undesirable in other cases ("Why did my 2-replica service get scheduled to the same node?"). In general, I think randomization would better suit large scale deployments that can average out the outliers, and determinism is better for tiny swarms. Perhaps there should be a user preference on whether to add randomness, or even a user-specified jitter factor. The downside is that providing this option locks us in to scheduling tasks in a particular way.

self ping @aluzzardi

LGTM

@aluzzardi: I've updated this to better match the code in #1512. I tweaked the protobuf definitions to exactly match the additions there, and updated the behavioral description.

I also renamed the document to design/topology.md, and reworded it to change it from a proposal to a specification (future tense into present, etc). I removed the alternative proposal and the CLI discussion (which is out of scope).

Are there any changes we should consider before merging this?

Making the notion of precedence absolute is too rigid. If one datacenter experiences a problem that causes all of its tasks to fail immediately, tasks will keep getting assigned to it indefinitely, and they will never get scheduled to the datacenter that's still working properly.

Is this case handled?

Also, are we handling the "default" algorithm (HA) as a spread over node.id or is it special cased?

Regarding the above, I think we could work around that by skipping empty sets. For instance, while spreading over the datacenter label, we should be able to see that there are no nodes under a given datacenter label value.

Making the notion of precedence absolute is too rigid. If one datacenter experiences a problem that causes all of its tasks to fail immediately, tasks will keep getting assigned to it indefinitely, and they will never get scheduled to the datacenter that's still working properly.

Is this case handled?

Not explicitly. It was dropped from the design discussion in response to your earlier comments (#1473 (comment))

To the extent that individual nodes are being marked as down, the problem is handled. But the spread algorithm doesn't do any randomization or failure monitoring of its own.

Also, are we handling the "default" algorithm (HA) as a spread over node.id or is it special cased?

We should probably discuss the implementation over in #1512, but basically the way it works is we build a tree with a level for each spread directive, and spread evenly between the branches at each level. The leaves are individual nodes.

Regarding the above, I think we could work around that by skipping empty sets. For instance, while spreading over the datacenter label, we should be able to see that there are no nodes under a given datacenter label value.

I'm not sure this is necessary. We only consider the label values found among nodes that are up. So if the only place a certain label value appears is on a dead node, the scheduler won't even be aware of that value.

Code was merged

👏

@aaronlehmann @aluzzardi @dongluochen,

Some input on the deterministic vs monte-carlo/how-to-do-scheduling discussion:

There seem to be two different use cases here, which can be summed up as:
--placement-pref 'spread='
and
--placement-req 'spread='

Placement preferences:

• Scheduling should ignore failed/offline nodes.
• Many tasks can be scheduled per node (by default).
• Always yields to requirements, only serving to score requirement-satisfying nodes.

Placement requirements:

• Should be very strictly enforced.
• Only one task can be scheduled per node (by default).
• This can be used for the HA scenario.
• Always takes precedence over preferences, immediately failing nodes.

Both:

• Choose randomly between nodes that have the same score. No unbalanced scheduling. (no 2v0 in a 2-node swarm)
• Higher-importance constraints are ignored

There has also been a proposal for a --max-replicas-per-node moby/moby#26259 This could be strictly applied whether using preferences, requirements, or both.

I think the goal is to give users tools to decide how scheduling should work, instead of deciding for them.

Last thing: The all-powerful, all-capable, has-all-the-features scheduling algorithm can definitely do better than O(m*n). Off the top of my head:

1. Calculate score for each node.
2. Place all nodes in a sorted list. (Something here to randomize same-cost nodes)
3. Pop the "best" node.
4. Schedule task on node.
5. Calculate new node score.
6. Re-add node to the list (maintain randomness of same-cost nodes).
7. Repeat 3-6 until done all tasks, or negative score found.

Complexity: ~O(n*log(n) + t*log(n)) where n=nodes, t=tasks

Am I missing anything?

Last thing: The all-powerful, all-capable, has-all-the-features scheduling algorithm can definitely do better than O(m*n). Off the top of my head:

Calculate score for each node.
Place all nodes in a sorted list. (Something here to randomize same-cost nodes)
Pop the "best" node.
Schedule task on node.
Calculate new node score.
Re-add node to the list (maintain randomness of same-cost nodes).
Repeat 3-6 until done all tasks, or negative score found.

There are two different scenarios we can discuss: scheduling a set of unrelated tasks, or scheduling a group of tasks that can be treated as interchangable (i.e. multiple replicas of the same service).

The former is difficult to do efficiently without constraining the algorithm. The scores of the nodes would depend on the particular task being scheduled.

If the tasks can be treated as identical, you can redefine the scheduling problem as "how many tasks should be scheduled on each node?", instead of iterated scheduling of individual tasks. This is what we do now (after a step that groups idential tasks), and it ends up looking pretty similar to what you suggested. We do a single sort, then assign tasks to nodes with the lowest "scores" until the scores all match, then do round-robin scheduling from that point if there are still more tasks to schedule.