Method and system for data handling

Patent metadata

Field	Value
Publication number	US-11741081-B2
Application number	US-201916257458-A
Country	US
Kind code	B2
Filing date	Jan 25, 2019
Priority date	Jan 25, 2019
Publication date	Aug 29, 2023
Grant date	Aug 29, 2023

Abstract

A control module transferring data between a shard and destination shards within a database comprising a plurality of shards, the control module: generating a first hash wheel distribution of shard allocations by applying a defined hashing function to a first integer value per shard allocation; generating a further hash wheel distribution of shard allocations by applying the defined hashing function to a further integer value per shard allocation; determining a range of hash values associated with data to be transferred between the shard and a destination shard, wherein the range of hash values, the shard and the destination shard are defined based on determining a difference between the first hash wheel distribution of shard allocations and the further hash wheel distribution of shard allocations; selecting and controlling the transfer of data associated with the determined range of hash values between the shard and the destination shard.

First claim

The invention claimed is:

1. A control module configured to manage and control transferring data between a first shard and at least one destination shard within a database comprising a plurality of shards, the control module comprising at least one processor and at least one memory including a computer program code, the at least one memory and the computer program code configured to, with the at least one processor, cause the control module at least to:
generate a first distribution of data collections across a plurality of available shards, the one or more available shards including the first shard, the first distribution of data collections defining in which shard a respective data collection is located, wherein the data collections are distributed across the one or more available shards using a first hash wheel distribution which maps a value identifying a respective data collection to a respective shard, the first hash wheel constructed from an integer number of occurrences of one or more available shards of the plurality of shards including the first shard, wherein the first distribution represents a current distribution of data collections;
generate a further distribution of data collections across a plurality of available shards, the one or more available shards including the one or more destination shards, the further distribution of data collections defining in which shard a respective data collection is located, wherein the data collections are distributed across the one or more available shards using a further hash wheel distribution which maps a value identifying a respective data collection to a respective shard, the further hash wheel distribution providing updated shard allocations, the further hash wheel constructed from an integer number of occurrences of one or more available shards of the plurality of shards, including one or more of the destination shards, wherein the further distribution represents an update to the current distribution of data collections;
determine a difference between the first hash wheel distribution of shard allocations and the further hash wheel distribution of shard allocations, the difference providing at least one range of hash values associated with data to be transferred between the first shard and the at least one destination shard; and
select and control the transfer of data associated with the determined at least one range of hash values, which are determined based on the difference between the first hash wheel distribution of shard allocations and the further hash wheel distribution of shard allocations between the first shard and the at least one destination shard.

2. The control module as claimed in claim 1 , wherein the control module is further caused to:
generate a series of auxiliary hash wheel distributions of shard allocations by applying the defined hashing function to a series of auxiliary integer value per shard allocations, wherein a final of the series of auxiliary integer value per shard allocations is a target integer value per shard allocation and the further integer value per shard allocation and auxiliary integer value per shard allocations define a step-wise progression from the first integer value per shard allocation to the final of the series of auxiliary integer value per shard allocations.

3. The control module as claimed in claim 2 , further caused to determine further ranges of hash values associated with data to be transferred between shards, wherein the further ranges of hash values, the first shard and the at least one destination shard are defined based on determining differences between succeeding auxiliary hash wheel distributions of shard allocations.

4. The control module as claimed in claim 1 , caused to select and control the transfer of the determined at least one range of data between the first shard and the at least one destination shard is further caused to generate and store a hash value associated with each key.

5. The control module as claimed in claim 4 , caused to generate the hash value based on one of:
the defined hashing function applied to the key value for each key;
a sum of an additional value and the defined hashing function applied to the key value for each key, wherein the additional value is a pseudorandom value; or
a concatenation of an additional value to the defined hashing function hash wheel function applied to the key value for each key, wherein the additional value is a pseudorandom value.

6. The control module as claimed in claim 1 , caused to select and control the transfer of data associated with the determined at least one range of hash values between the first shard and the at least one destination shard is caused to select rows from database tables based on the determined at least one range of hash values.

7. The control module as claimed in claim 1 , wherein the control module is further caused to generate the first hash wheel distribution of shard allocations by applying a defined hashing function to a first integer value per shard allocation and to generate the further hash wheel distribution of shard allocations by applying the defined hashing function to a further integer value per shard allocation.

8. A method for a control module configured to manage and control transferring data between a shard and at least one destination shard within a database comprising a plurality of shards, the method comprising:
generating a first distribution of data collections across a plurality of available shards, the one or more available shards including the first shard, the first distribution of data collections defining in which shard a respective data collection is located, wherein the data collections are distributed across the one or more available shards using a first hash wheel distribution which maps a value identifying a respective data collection to a respective shard, the first hash wheel constructed from an integer number of occurrences of one or more available shards including the first shard, wherein the first distribution represents a current distribution of data collections;
generating a further distribution of data collections across a plurality of available shards, the one or more available shards including the one or more destination shards, the further distribution of data collections defining in which shard a respective data collection is located, wherein the data collections are distributed across the one or more available shards using a further hash wheel distribution which maps a value identifying a respective data collection to a respective shard, the further hash wheel distribution providing updated shard allocations, the further hash wheel constructed from an integer number of occurrences of one or more available shards of the plurality of shards, including one or more of the destination shards, wherein the further distribution represents an update to the current distribution of data collections;
determining a difference between the first hash wheel distribution of shard allocations and the further hash wheel distribution of shard allocations, the difference providing at least one range of hash values associated with data to be transferred between the first shard and the at least one destination shard; and
selecting and controlling the transfer of data associated with the at least one range of hash values, which are determined based on the difference between the first hash wheel distribution of shard allocations and the further hash wheel distribution of shard allocations, between the first shard and the at least one destination shard.

9. The method as claimed in claim 8 , further comprising:
generating a series of auxiliary hash wheel distributions of shard allocations by applying the defined hashing function

Assignees

• King Com Ltd

Inventors

• Persson Fredrik

Classifications

• G06F16/2379 Primary

  Updates performed during online database operations; commit processing · CPC title

• G06F7/582

  Pseudo-random number generators · CPC title

• G06F16/2315

  Optimistic concurrency control · CPC title

• G06F16/278 Primary

  Data partitioning, e.g. horizontal or vertical partitioning · CPC title

• H04L9/0643

  Hash functions, e.g. MD5, SHA, HMAC or f9 MAC · CPC title