1. A computer-implemented method comprising: determining that a quantity of shards in a multi-shard system has changed; in response to determining that the quantity of shards has changed, transitioning a client from a normal state, in which the client performs a particular type of operation relative to data items stored in the system in a first manner, to a rebalancing state, in which the client performs the particular type of operation relative to data items stored in the system in a second manner that differs from the first manner and without the client acquiring exclusive locks relative to any data items; while the client is in the rebalancing state, determining, for one or more particular data items, destination shards that are separate from source shards on which the one or more particular data items were stored prior to the client's transition to the rebalancing state; and moving the one or more data items from the source shards to the destination shards while the client is in the rebalancing state.