LeastShardAllocationStrategy takes maxSimultaneousRebalance - rebalanceInProgress.size shards on rebalance, which causes shards "flapping" in case when maxSimultaneousRebalance is considerably higher than rebalanceThreshold. The strategy deallocates a lot (maxSimultaneousRebalance) of shards and then allocates most of them on the same node (which becomes a node with the least amount of shards after this massive deallocation).

I'd suggest to change

if (mostShards.size - leastShards.size >= rebalanceThreshold)
          Future.successful(mostShards.take(maxSimultaneousRebalance - rebalanceInProgress.size).toSet)

to

val difference = mostShards.size - leastShards.size
        if (difference >= rebalanceThreshold)
          Future.successful(mostShards.take(math.min(difference, maxSimultaneousRebalance - rebalanceInProgress.size)).toSet)

I can PR this.