To avoid the catastrophic reshuffle caused by Modulo arithmetic, systems like Amazon DynamoDB and Apache Cassandra use an algorithm called Consistent Hashing.
Instead of mapping keys to an array index like 0, 1, 2, 3, Consistent Hashing maps both the servers AND the data keys onto an abstract Ring (a circle where the highest hash value wraps around to 0).
When a read or write request comes in for a key:
The brilliance of this algorithm is what happens when you add or remove a node. Watch the simulator below.
The ring has 3 nodes (A, B, C) and several data points (dots). Click "Add Node D". Watch closely which data points turn red and migrate.
When you added Node D to the ring, only the data points immediately counter-clockwise to D had to move. Nodes A and C were completely unaffected! In a massive cluster, adding or removing a node only requires migrating a tiny fraction of the data (specifically, 1/N of the data), rather than 100% of it.
When you removed Node B, only its immediate clockwise neighbor (Node C) had to take over its data. The rest of the ring didn't even notice.
In practice, physical servers aren't just placed on the ring once. A powerful server might be placed on the ring 100 times, while a weaker server is placed 20 times. These are called Virtual Nodes (vnodes), and they ensure that data is perfectly evenly distributed, and that the load of a dead node is evenly absorbed by the entire cluster, rather than crushing a single neighbor.