1. A computer-implemented method comprising: determining a change in a quantity of shards in a multi-shard system that has a plurality of shards; in response to determining the change in the quantity of shards, transitioning a client from a normal state to a rebalancing state, wherein during the normal state, the client performs a type of operation relative to data items stored in the multi-shard system in a first manner, wherein during the rebalancing state, the client performs the type of operation relative to the data items stored in the multi-shard system in a second manner, wherein the second manner is different than the first manner, wherein during the rebalancing state, the client performs the type of operation without the client acquiring one or more exclusive locks relative to any of the data items, and wherein during the rebalancing state, the type of operation is performed based on: a first shard in the multi-shard system, the first shard including a data item stored at a first memory location in the first shard before the change in the quantity of shards, wherein the data item is one of the data items; and a second shard in the multi-shard system, the second shard including the data item stored at a second memory location in the second shard after the change in the quantity of shards; while the client is in the rebalancing state, determining, for one or more data items of the data items, one or more destination shards that are separate from one or more source shards, wherein the one or more source shards store the one or more data items during the normal state prior to transitioning the client from the normal state to the rebalancing state; and moving the one or more data items from the one or more source shards to the one or more destination shards while the client is in the rebalancing state.