topology aware scheduling doesn't work when scaling up

It seems like topology aware scheduling doesn't properly schedule tasks evenly when scaling up. Take this example: I'm running a service with two placement options "region" and "zone". I have 2 regions, one with 3 zones and the other with 2 zones ( total is 5 zones) . When I launch the service with 3 replicas it works fine, but when i try to scale to 5, one of the regions gets two tasks instead of 1.

Launching a service with three replicas:

$ docker service create \
>   --name pets \
>   --replicas 3 \
>   --mount type=bind,source=/etc/hostname,destination=/tmp/worker/hostname \
>   --publish mode=host,target=5000,published=32000,protocol=tcp \
>   --constraint 'node.role==worker' \
>   --placement-pref 'spread=node.labels.region' \
>   --placement-pref 'spread=node.labels.zone' \
>   dtr.us-west.dcus17.dckr.org/dockercon/pets:v2

Seeing they're spread over:

$ docker service ps pets
ID                  NAME                IMAGE                                           NODE                                DESIRED STATE       CURRENT STATE           ERROR               PORTS
jlu6v7jrag3l        pets.1              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-20-2-220-eu-west-1b   Running             Running 2 minutes ago                       *:32000->5000/tcp
6rbew6twygwj        pets.2              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-20-1-73-eu-west-1a    Running             Running 2 minutes ago                       *:32000->5000/tcp
fz91gc68t7mg        pets.3              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-10-2-28-us-west-2b    Running             Running 2 minutes ago                       *:32000->5000/tcp

Scaling to 5 ( expecting they will be spread across all 5 zones ):

$ docker service ps pets
ID                  NAME                IMAGE                                           NODE                                DESIRED STATE       CURRENT STATE                ERROR               PORTS
jlu6v7jrag3l        pets.1              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-20-2-220-eu-west-1b   Running             Running about an hour ago                        *:32000->5000/tcp
0aauudjh9w3n        pets.2              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-20-2-216-eu-west-1b   Running             Starting 26 seconds ago
fz91gc68t7mg        pets.3              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-10-2-28-us-west-2b    Running             Running about an hour ago                        *:32000->5000/tcp
qpm9ecydauc6        pets.4              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-10-3-239-us-west-2c   Running             Running about a minute ago                       *:32000->5000/tcp
irliapzsmm45        pets.5              dtr.us-west.dcus17.dckr.org/dockercon/pets:v2   ucp-worker-10-20-1-10-eu-west-1a    Running             Starting 26 seconds ago

as you can see zone eu-west-1b got 2/5 tasks and zone us-west-2a got no tasks at all.

cc @aaronlehmann

Reproduce the issue with docker service create, two placement preferences for region and zone, then scale the service from three to five replicas. Start by tracing the topology-aware scheduling path and compare the placement decisions with the expected result: one task in each of the five zones.