US 10,592,153 B1Granted

Redistributing a data set amongst partitions according to a secondary hashing scheme

AssigneeAmazon Technologies, Inc.

InventorsNaveen Anand Subramaniam, Jacob Shannan Carr, Aaron Ben Fernandes, Gaurav Gupta, Brian Thomas Kachmarck

Life of this patent

Estimating the term…

Loading patent…

Abstract

Items within a data set can be redistributed to different partitions of a distributed data store according to modified hash values. A redistribution event may, in some embodiments, trigger the redistribution of a data set. Modified hash values for items in the data set may be generated according to a secondary hashing scheme to be used for identifying the location of a new partition to store the item instead of hash values based on current key values that identify a current partition that stores the item. Access can be provided to items based on the modified hash values to determine the new partition that stores the item after redistribution.

Claims20

Dependent claims

A system, comprising:

at least one processor;
a memory, comprising program instructions that when executed by the at least one processor cause the at least one processor to implement a request router for routing access requests to different partitions of a data set;
wherein the data set comprises a plurality of items stored across a plurality of partitions in a distributed data store, wherein the items are distributed across the partitions according to respective hash values generated from an application of a hash function to respective key values for the items;
wherein the request router is configured to:
detect a redistribution event for the data set;
in response to the detection of the redistribution event, generate respective modified key values for the items to redistribute the items among the plurality of partitions upon application of the hash function to the respective modified key values for the items;
in response to a receipt of an access request for one of the items:
identify one of the partitions according to a hash value generated from an application of the hash function to the modified key value for the one item;
and
route the request for processing with respect to the identified partition.

7 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 implement:

storing a plurality of items of a data set across a plurality of partitions in a distributed data store, wherein the items are distributed across the partitions according to respective hash values generated from an application of a hash function to respective key values for the items;
generating respective modified hash values for the items to redistribute the items among the plurality of partitions according to a secondary hashing scheme based, at least in part, on the respective key values for the items;
receiving an access request for one of the items in the data set;
in response to receiving the access request:
identifying one of the partitions of the distributed data store that includes the one item according to the modified hash value generated for the one item according to the secondary hashing scheme;
and
sending the access request for processing with respect to the identified partition.

4 more elements

Dependencies are inferred from the claim text.