US 11,030,169 B1Granted

Data re-sharding

AssigneeAmazon Technologies, Inc.

InventorsMing-Chuan Wu, Sandeep Bhatia, Andrew Whitaker

Life of this patent

Estimating the term…

Loading patent…

Abstract

Processing and storage responsibility for a data set may be split according to separately stored shards of the data set. As one or more loads associated with shards of the dataset grow a re-sharding operation may be performed to reduce loading of particular shards and nodes that host the particular shards. A re-sharding operation may cause only a sub-set of as set of shards of the dataset to be split and only cause second portions of the split shards to be stored in additional computing nodes. In some embodiments, a number of shards to be included in the sub-set of shards to be split may be selected based on an overall number of shards in the set and a largest number in the Fibonacci sequence that is less than the overall number of shards in the set.

Claims20

Dependent claims

A system, comprising:

one or more computer systems comprising computer hardware configured to implement a resource manager to:
cause a set of shards of a common dataset to be stored in storages of a first set of computing nodes;
determine a number of new shards to add for the common dataset, wherein the number is determined based on a current number of shards in the set and is less than the current number;
and
create the determined number of new shards for the common dataset, wherein create the determined number of new shards for the common dataset comprises:
identify an equivalent number of existing shards from the set of shards as a sub-set of shards to split;
cause only each shard of the sub-set of the set of shards stored in the storages of the first set of computing nodes to be split into a first portion and a second portion;
and
cause only the second portions of the first and second portions to be stored in storages of a second set of computing nodes.

6 more elements

A non-transitory, computer-readable storage medium, storing program instructions that when executed by one or more computing devices cause the one or more computing devices to:

cause a set of shards of a common dataset to be stored in storages of a first set of computing nodes;
determine a number of new shards to add for the common dataset, wherein the number is determined based on a current number of shards in the set and is less than the current number;
and
create the determined number of new shards for the common dataset, wherein create the determined number of new shards for the common dataset comprises:
identify an equivalent number of existing shards from the set of shards as a sub-set of shards to split;
cause only each shard of the sub-set of shards of the set of shards stored in the storages of the first set of computing nodes to be split into a first portion and a second portion;
and
cause only the second portions of the first and second portions to be stored in storages of a second set of computing nodes.

5 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/452,587Filed 7 Mar 2017
Granted: 8 Jun 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification7 codes

G06F 16/22
Of structured data, e.g. relational data: indexing; Data structures therefor; Storage structures
G06F 16/24554
Of query operations: unary operations; Data partitioning operations
G06F 16/278
Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system…: data…
H04L 67/1031
For accessing one among a plurality of replicated servers: controlling of the operation of servers by a load balancer, e.g. adding or removing…

Family

No related US applications are recorded in the indexed filing history.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key