System and method for key-value shard creation and management in a key-value store

1 . A method for key-value shard creation and management in a key-value store, the method comprising the steps of:

partitioning the key-value store including a plurality of key spaces into a plurality of shards, the plurality of shards including a coordinator shard;

receiving a first shard assignment value for a first key-value pair from a key-value store client, the key-value store client having access to the key-value store, wherein the first shard assignment value is algorithmically determined by the key-value store client to balance data collocation and collision probability;

creating a first shard using the first shard assignment value, the first shard including a data structure configured to allow lock-free concurrent read access;

assigning the first key-value pair to the first shard based on the first shard assignment value; and

updating the coordinator shard to reference to the first shard by storing a mapping from the first shard assignment value to a root pointer of the first shard.

2 . The method of claim 1 , wherein the method further comprises a step of writing the first shard to a storage device.

3 . The method of claim 1 , wherein the method further comprises a step of storing modifications to the first shard in a modified version of the first shard while the first shard remains unmodified.

4 . The method of claim 3 , wherein the step of storing modifications is completed using a redirected write operation.

5 . The method of claim 1 , wherein the data structure includes a b+ tree.

6 . The method of claim 1 , wherein the first shard includes a first keyspace shard.

7 . The method of claim 1 , wherein each shard within the plurality of shards includes logically independent key-values from any other shard within the plurality of shards.

8 . The method of claim 1 , wherein each shard within the plurality of shards is independently modifiable from any other shard within the plurality of shards.

9 . The method of claim 1 , wherein the method further comprises a step of generating a second shard, the second shard including a persistent redirected replica of the first shard.

10 . The method of claim 9 , wherein the second shard includes a second shard epoch that references to a first data payload of the first shard.

11 . The method of claim 9 , wherein the method further comprises a step of updating the coordinator shard to reference to the second shard.

12 . A method for key-value shard creation and management in a key-value store, the method comprising the steps of:

partitioning the key-value store including a plurality of keyspaces into a plurality of shards, the plurality of shards including a coordinator shard and a first shard, the coordinator shard referencing to the first shard, the first shard including a first data structure, the first data structure including a first key-value pair;

creating a second key-value pair;

receiving a second shard assignment value for the second key-value pair from a key-value store client, the key-value store client having access to the key-value store, wherein the second shard assignment value is algorithmically determined by the key-value store client;

creating a second shard using the second shard assignment value, the second shard including a second data structure;

assigning the second key-value pair to the second shard based on the second shard assignment value;

updating the first shard to reference to the second shard using a redirected write operation that creates a modified version of the first shard while the first shard remains unmodified; and

updating the coordinator shard to reference to the second shard by storing a mapping from the second shard assignment value to a root pointer of the second shard.

13 . The method of claim 12 , wherein the method further comprises a step of writing the second shard to a storage device.

14 . The method of claim 12 , wherein the method further comprises a step of storing modifications to the second shard in a modified version of the second shard while the second shard remains unmodified.

15 . The method of claim 14 , wherein the step of storing modifications is completed using a redirected write operation.

16 . The method of claim 12 , wherein each of the data structures includes a b+ tree.

17 . The method of claim 12 , wherein the second shard includes a value shard.

18 . The method of claim 12 , wherein the second shard assignment value is algorithmically determined.

19 . A method for key-value shard creation and management in a key-value store, the method comprising the steps of:

partitioning the key-value store including a plurality of keyspaces into a plurality of shards, the plurality of shards including a coordinator shard;

receiving a first shard assignment value for a first key-value pair from a key-value store client, the key-value store client having access to the key-value store, wherein the first shard assignment is algorithmically determined by the key-value store client;

creating a first shard using the first shard assignment value, the first shard including a data structure;

assigning the first key-value pair to the first shard based on the first shard assignment value;

updating the coordinator shard to reference to the first shard by storing a mapping from the first shard assignment value to a root pointer of the first shard;

creating a second key-value pair;

receiving a second shard assignment value for the second key-value pair from the key-value store client, wherein the second shard assignment is algorithmically determined by the key-value store client;

assigning the second key-value pair to a second shard based on the second shard assignment value;

updating the first shard to reference to the second shard;

updating the coordinator shard to reference to the second shard by storing a mapping from the second shard assignment value to a root pointer of the second shard;

generating a third shard that includes a persistent redirected replica of the first shard, the third shard including a third epoch that references to a first data payload of the first data structure; and

updating the coordinator shard to reference to the third shard.