Replace modulo sharding with consistent hashing: a ring with virtual nodes that moves few keys when servers come and go, then replicas and weighted servers.
The ring
Servers as virtual-node points on a ring; each key belongs to the first point clockwise.
Replicas and weights
The first n distinct servers for a key, and servers with more points for more capacity.
Bounded loads
Hot keys overload one server. Implement consistent hashing with bounded loads.
What a hash function does, how hash sets give fast lookups, why hash mod n reshuffles everything when servers change, and how a consistent hash ring with virtual nodes fixes it.