Naïve, client-side sharding with online addition of shards
First Claim
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.
1 Assignment
0 Petitions
Accused Products
Abstract
Multiple clients can be enabled to perform operations relative to data items in a shard system asynchronously to each other without the use by those clients of exclusive locks. A rebalancing event, in which data items are redistributed automatically among a set of shards due to a modification of the quantity of shards in the system, can be performed without the use of exclusive locks by clients. Clients can continue to perform operations relative to at least some of the data items in the shard system even while rebalancing processes are redistributing at least some of the data items asynchronously during a system-wide rebalancing event. All of these benefits can be obtained without sacrificing data consistency within the shard system.
182 Citations
20 Claims
-
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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 20)
-
-
18. A system comprising:
-
a plurality of database shards that store data items; a plurality of clients that are configured to transition, in response to a change in a quantity of the plurality of database shards, from a normal state to a rebalancing state, wherein during the normal state, the client performs a type of operation relative to the 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 the plurality of database shards, wherein the data items is of 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 the plurality of database shards; and at least one computing device configured to (a) determine, while the plurality of clients are in the rebalancing state, and 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 while each client of the plurality of clients is in the normal state, and (b) move the one or more data items from the one or more source shards to the one or more destination shards while each client of the plurality of clients is in the rebalancing state.
-
-
19. A non-transitory computer-readable storage memory storing processor-executable instructions comprising:
-
instructions to cause one or more processors to determine a change in a quantity of shards in a multi-shard system that has a plurality of shards; instructions to cause one or more processors to transition a client, in response to determining the change in the quantity of shards, 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 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 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; instructions to cause one or more processors to determine, while the client is in the rebalancing state, and 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 instructions to cause one or more processors to-move 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.
-
Specification