Computer implemented method for dynamic sharding
The present disclosure relates to systems and methods for dynamic sharding of a database comprising data identifiable by keys comprised within a global ordered range. When handling a request for data of at least one key: providing the request to a predetermined shard store; the predetermined shard store verifying, by means of its local subrange collection, whether the at least one key is present in a local subrange of a shard stored on the predetermined shard store; and when at least one key is not present in a local subrange of a shard stored on the predetermined shard store, returning a message comprising the local subrange collection of the predetermined shard store.
1. A computer implemented method for dynamic sharding of a database comprising data identifiable by keys comprised within a global ordered range, the keys comprising an alphanumeric data object identifier, wherein the method comprises:
providing a plurality of shard stores, each of the plurality of shard stores comprising a shard store identifier and each of the plurality of shard stores being limited by a storage capacity limit;
providing a plurality of shards, each of the plurality of shards configured to handle requests for data of at least one key within a local subrange, wherein the local subrange comprises an ordered subrange of the global ordered range;
providing the plurality of shards on the plurality of shard stores so that a single shard does not extend beyond a single shard store;
providing on each of the plurality of shard stores a local subrange collection, each local subrange collection comprising one or more local subranges of the plurality of shards stored on a corresponding shard store;
providing a shard router, connected to the plurality of shard stores and adapted to handle the requests for data of at least one key;
providing on the shard router a global subrange collection adapted to correlate global subranges of the global ordered range to shard store identifiers; and
handling a request for data of at least one key by:
providing the request to the shard router;
the shard router determining that the shard store identifier is correlated to a global subrange comprising the at least one key of the request;
the shard router providing the request to a predetermined shard store associated with the correlated shard store identifier;
the predetermined shard store determining, by means of its local subrange collection, whether the at least one key is present in the local subrange of a shard stored on the predetermined shard store; and
in response to determining that the at least one key is not present in the one or more local subranges of the plurality of shards stored on the predetermined shard store;
returning a message comprising the local subrange collection of the predetermined shard store; and
the shard router updating its global subrange collection as a function of the message by correlating the shard store identifier of the predetermined shard store to the global subranges corresponding to local subranges of the local subrange collection of the message.
2. The computer implemented method according to claim 1 , further comprising:
in response to returning the message by the predetermined shard store, providing the request to a further shard store.
3. The computer implemented method according to claim 1 , wherein the local subrange collection of the predetermined shard store handling the request further comprises an external subrange collection, the external subrange collection comprising one or more external subranges of shards stored on other shard stores correlated to their respective shard store identifiers, and wherein the computer implemented method further comprises:
handling the request by the predetermined shard store, in response to determining that the at least one key is not present in the one or more local subranges of the shards stored on the predetermined shard store, wherein handling the request includes:
returning the message comprising the local subrange collection;
determining whether the at least one key of the request is comprised within a predetermined external subrange of the external subrange collection of the local subrange collection; and
providing the request subsequently to a further shard store of which the shard store identifier is correlated to the external subrange.
4. The computer implemented method according to claim 3 , further comprising:
in response to determining that the at least one key is not present in the one or more local subranges of the plurality of shards stored on the predetermined shard store:
the shard router further updating its global subrange collection as a function of the message by correlating the shard store identifier of the further shard store to a global subrange corresponding to the predetermined external subrange of the external subrange collection of the message.
5. The computer implemented method according to claim 1 , further comprising:
performing a move operation of a move shard comprising data of all keys within a move subrange from the predetermined shard store to a further shard store, wherein the move operation results in the move subrange being removed from the local subrange collection of the predetermined shard store and being added to an external subrange collection of the predetermined shard store as an external subrange correlated to the shard store identifier of the further shard store.
6. The computer implemented method according to claim 5 , wherein the move operation of the move shard comprising the data of all keys within the move subrange from the predetermined shard store to the further shard store results in the move subrange being added to the local subrange collection of the further shard store as a local subrange.
7. The computer implemented method according to claim 6 , wherein during the move operation only the local subrange collection of the predetermined shard store and the further shard store involved in the move operation are updated as a function of the move subrange.
8. The computer implemented method according to claim 5 , wherein the predetermined shard store and the further shard store involved in the move operation comprise a public local subrange collection and a private local subrange collection, and wherein the method further comprises, during the move operation:
the predetermined shard store updating its public local subrange collection as a function of the move subrange;
the predetermined shard store sending the move shard to the further shard store;
the further shard store receiving the move shard from the predetermined shard store;
in response to receiving the move shard, the further shard store:
updating both its public local subrange collection and its private local subrange collection as a function of the move subrange; and
sending a first move acknowledgment message to the predetermined shard store; and
in response to the predetermined shard store receiving the first move acknowledgment message from the further shard store, the predetermined shard store updating its private local subrange collection and deleting the move shard.
9. The computer implemented method according to claim 8 , further comprising:
in response to the predetermined shard store detecting, a predetermined time period after performing the move operation, that its public local subrange collection differs from its private local subrange collection, the predetermined shard store resending the move shard to the further shard store.
10. The computer implemented method according to claim 9 , further comprising:
in response to the further shard store being offered the move shard by the predetermined shard store and the move subrange being already present in the further shard store public local subrange collection, the further shard store sending a second move acknowledgment message to the predetermined shard store without receiving the move shard.
11. The computer implemented method according to claim 5 , wherein the move shard comprises at least an ordered subset of a shard of the predetermined shard store.
12. The computer implemented method according to claim 1 , further comprising:
in response to a move job that is provided for moving at least an ordered subset of a shard of which the size of exceeds a move size threshold, generating a plurality of move operations as a function of the move job so that the size of move shards of each of the plurality of move operations is less than or equal to the move size threshold, wherein the move job comprises a request for moving the ordered subset of the shard from the predetermined shard store to a further shard store until the plurality of move operations have resulted in moving:
a move job key range;
a move job amount of keys; and
a move job size of the ordered subset of the shard.
13. The computer implemented method according to claim 1 , further comprising:
in response to detecting that, for a predetermined shard, a further shard is available on a same shard store of which the local subrange is contiguous with the local subrange of the predetermined shard;
merging the predetermined shard with the further shard thus forming a merged shard; and
updating the local subrange collection by merging both contiguous local subranges of the predetermined shard and the further shard to a merged local subrange of the merged shard.
14. A non-transitory computer readable medium comprising software code which, when executed by a processor, causes the processor to perform a method for dynamic sharding of a database comprising data identifiable by keys comprised within a global ordered range, the keys comprising an alphanumeric data object identifier, wherein the method comprises:
providing a plurality of shard stores, each of the plurality of shard stores comprising a shard store identifier and each of the plurality of shard stores being limited by a storage capacity limit;
providing a plurality of shards, each of the plurality of shards configured to handle requests for data of at least one key within a local subrange, wherein the local subrange comprises an ordered subrange of the global ordered range;
providing the plurality of shards on the plurality of shard stores so that a single shard does not extend beyond a single shard store;
providing on each of the plurality of shard stores a local subrange collection, each local subrange collection comprising one or more local subranges of the plurality of shards stored on a corresponding shard store;
providing a shard router, connected to the plurality of shard stores and adapted to handle the requests for data of at least one key;
providing on the shard router a global subrange collection adapted to correlate global subranges of the global ordered range to shard store identifiers; and
handling a request for data of at least one key by:
providing the request to the shard router;
the shard router determining the shard store identifier correlated to a global subrange comprising the at least one key of the request;
the shard router providing the request to a predetermined shard store associated with the shard store identifier correlated to the global subrange;
the predetermined shard store determining, by means of its local subrange collection, whether the at least one key is present in the local subrange of a shard stored on the predetermined shard store; and
in response to determining that the at least one key is not present in the one or more local subranges of the plurality of shards stored on the predetermined shard store;
returning a message comprising the local subrange collection of the predetermined shard store; and
the shard router updating its global subrange collection as a function of the message by correlating the shard store identifier of the predetermined shard store to the global subranges corresponding to local subranges of the local subrange collection of the message.
15. The non-transitory computer readable medium of claim 14 , wherein the software code when executed by the processor causes the processor to perform the method further comprising:
in response to returning the message by the predetermined shard store, providing the request to a further shard store.
16. The non-transitory computer readable medium of claim 14 , wherein the local subrange collection of the predetermined shard store handling the request further comprises an external subrange collection, the external subrange collection comprising one or more external subranges of shards stored on other shard stores correlated to their respective shard store identifiers, and wherein the software code when executed by the processor causes the processor to perform the method further comprising:
handling the request by the predetermined shard store, in response to determining that the at least one key is not present in the one or more local subranges of the shards stored on the predetermined shard store, wherein handling the request includes:
returning the message comprising the local subrange collection;
determining whether the at least one key of the request is comprised within a predetermined external subrange of the external subrange collection of the local subrange collection; and
providing the request subsequently to a further shard store of which the shard store identifier is correlated to the external subrange.
17. The non-transitory computer readable medium of claim 16 , wherein the software code when executed by the processor causes the processor to perform the method further comprising:
in response to determining that the at least one key is not present in the one or more local subranges of the plurality of shards stored on the predetermined shard store:
the shard router further updating its global subrange collection as a function of the message by correlating the shard store identifier of the further shard store to a global subrange corresponding to the predetermined external subrange of the external subrange collection of the message.
18. The non-transitory computer readable medium of claim 14 , wherein the software code when executed by the processor causes the processor to perform the method further comprising:
performing a move operation of a move shard comprising data of all keys within a move subrange from the predetermined shard store to a further shard store, wherein the move operation results in the move subrange being removed from the local subrange collection of the predetermined shard store and being added to an external subrange collection of the predetermined shard store as an external subrange correlated to the shard store identifier of the further shard store.
19. The non-transitory computer readable medium of claim 18 , wherein the move operation of the move shard comprising the data of all keys within the move subrange from the predetermined shard store to the further shard store results in the move subrange being added to the local subrange collection of the further shard store as a local subrange.
20. The non-transitory computer readable medium of claim 19 , wherein during the move operation only the local subrange collection of the predetermined shard store and the further shard store involved in the move operation are updated as a function of the move subrange.
21. The non-transitory computer readable medium of claim 18 , wherein the predetermined shard store and the further shard store involved in the move operation comprise a public local subrange collection and a private local subrange collection, and wherein the software code when executed by the processor causes the computer to perform the method further comprising, during the move operation:
the predetermined shard store updating its public local subrange collection as a function of the move subrange;
the predetermined shard store sending the move shard to the further shard store;
the further shard store receiving the move shard from the predetermined shard store;
in response to receiving the move shard, the further shard store:
updating both its public local subrange collection and its private local subrange collection as a function of the move subrange; and
sending a first move acknowledgment message to the predetermined shard store; and
in response to the predetermined shard store receiving the first move acknowledgment message from the further shard store, the predetermined shard store updating its private local subrange collection and deleting the move shard.
22. The non-transitory computer readable medium of claim 21 , wherein the software code when executed by the processor causes the processor to perform the method further comprising:
in response to the predetermined shard store detecting, a predetermined time period after performing the move operation, that its public local subrange collection differs from its private local subrange collection, the predetermined shard store resending the move shard to the further shard store.
23. The non-transitory computer readable medium of claim 22 , wherein the software code when executed by the processor causes the processor to perform the method further comprising:
in response to the further shard store being offered the move shard by the predetermined shard store and the move subrange being already present in the further shard store public local subrange collection, the further shard store sending a second move acknowledgment message to the predetermined shard store without receiving the move shard.
24. The non-transitory computer readable medium of claim 18 , wherein the move shard comprises at least an ordered subset of a shard of the predetermined shard store.
25. The non-transitory computer readable medium of claim 14 , wherein the software code when executed by the processor causes the processor to perform the method further comprising:
in response to a move job that is provided for moving at least an ordered subset of a shard of which the size of exceeds a move size threshold, generating a plurality of move operations as a function of the move job so that the size of move shards of each of the plurality of move operations is less than or equal to the move size threshold, wherein the move job comprises a request for moving the ordered subset of the shard from the predetermined shard store to a further shard store until the plurality of move operations have resulted in moving:
a move job key range;
a move job amount of keys; and
a move job size of the ordered subset of the shard.
26. The non-transitory computer readable medium of claim 14 , wherein the software code when executed by the processor causes the processor to perform the method further comprising:
in response to detecting that, for a predetermined shard, a further shard is available on a same shard store of which the local subrange is contiguous with the local subrange of the predetermined shard;
merging the predetermined shard with the further shard thus forming a merged shard; and
updating the local subrange collection by merging both contiguous local subranges of the predetermined shard and the further shard to a merged local subrange of the merged shard.