Depends how things are replicated. In Dynamo style replication everything isn't replicated everywhere. Based on consistent hashing, and how vnodes etc are configured, a key lands itself in more than one nodes so that things are generally available. So scale-out in a dynamo-like system happens more gracefully.