You make a large number of virtual shards. Each virtual shard is mapped to some machine. When you add a new machine, you move some shards to the new real machine.

Presumably consistent hashing is also helpful here.