Patent ID: 8429162
Filing Date: 2013-04-23
Classification: G06F

Abstract:
1. A non-transitory computer-readable medium embodying a program executable in a computing device, the program comprising: code that maintains a database that is stored in a plurality of physical data stores through horizontal partitioning, the database including a plurality of data items; code that assigns each one of the data items to one of a plurality of first buckets by generating a respective hash code from a standardized portion of the one of the data items and determining the hash code modulo the number of first buckets, wherein a first fixed number of the first buckets are stored in each of the physical data stores according to a mapping; code that reassigns each one of the data items to one of a plurality of second buckets by determining the hash code modulo the number of second buckets, the number of second buckets corresponding to a multiple of the number of first buckets plus a positive integer; code that updates the mapping to map a second fixed number of the second buckets to each of the physical data stores, wherein the data items are unmoved between the physical data stores by updating the mapping; code that adds at least one physical data store to the plurality of physical data stores; code that migrates the data items which are assigned to a subset of the second buckets to the at least one physical data store added by the code that adds; and code that updates the mapping to map a third fixed number of the second buckets to each of the physical data stores, wherein an even distribution of the second buckets is achieved among the physical data stores.