A computer-implemented method comprising: determining that a quantity of shards (104 A-N) in a multi-shard system has changed; in response to determining that the quantity of shards has changed, transitioning a client (102 A-N) 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 (102 A-N) is in the rebalancing state, determining (304, 404, 504), 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; wherein moving the one or more data items from the source shards to the destination shards comprises: incrementing a system-wide version number; and for each first data item having a version number that, is less than the system-wide version number, determining, based at least in part on a quantity of shards in the multi-shard system following the shard quantity change, a first destination shard on which the first data item is to be located after the shard quantity change; for each second data item that (a) has a version number that is less than the system-wide version number and (b) is located on a source shard that differs from a second destination shard on which the second data item is to be located after the shard quantity change, inserting, into the second destination shard, a copy of the second data item having the system- wide version number; for each third data item that (a) has a version number that is less than the system- wide version number and (b) is already located on a third destination shard on which the third data item is to be located after the shard quantity change, changing a version number of the third data item to the system- wide version number. determining that a quantity of shards (104 A-N) in a multi-shard system has changed; in response to determining that the quantity of shards has changed, transitioning a client (102 A-N) 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 (102 A-N) is in the rebalancing state, determining (304, 404, 504), 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; wherein moving the one or more data items from the source shards to the destination shards comprises: incrementing a system-wide version number; and for each first data item having a version number that, is less than the system-wide version number, determining, based at least in part on a quantity of shards in the multi-shard system following the shard quantity change, a first destination shard on which the first data item is to be located after the shard quantity change; for each second data item that (a) has a version number that is less than the system-wide version number and (b) is located on a source shard that differs from a second destination shard on which the second data item is to be located after the shard quantity change, inserting, into the second destination shard, a copy of the second data item having the system- wide version number; for each third data item that (a) has a version number that is less than the system- wide version number and (b) is already located on a third destination shard on which the third data item is to be located after the shard quantity change, changing a version number of the third data item to the system- wide version number. incrementing a system-wide version number; and for each first data item having a version number that, is less than the system-wide version number, determining, based at least in part on a quantity of shards in the multi-shard system following the shard quantity change, a first destination shard on which the first data item is to be located after the shard quantity change; for each second data item that (a) has a version number that is less than the system-wide version number and (b) is located on a source shard that differs from a second destination shard on which the second data item is to be located after the shard quantity change, inserting, into the second destination shard, a copy of the second data item having the system- wide version number; for each third data item that (a) has a version number that is less than the system- wide version number and (b) is already located on a third destination shard on which the third data item is to be located after the shard quantity change, changing a version number of the third data item to the system- wide version number.