Partitioning and rebalancing data storage

• US 10,360,199 B2
• Filed: 01/22/2018
• Issued: 07/23/2019
• Est. Priority Date: 10/21/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Korycki, Jacek A., Van Brink, David A.
• Primary Examiner(s): Casanova, Jorge A
• Application Number:
  US15/877,287
• Publication Number:
  US 20180144009A1
• Time in Patent Office: 547 Days
• CPC Class Codes: G06F 16/2228 Indexing structures
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/25 Integrating or interfacing systems involving database management systems
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 16/9535 Search customisation based on user profiles and personalisation

Abstract

Techniques are described for partitioning and rebalancing data storage, such as through management of database partitions. In one or more implementations, a database that includes existing partitions is repartitioned to include new partitions. A balancing function that uses a skew factor is implemented that skews new data allocation to the new partitions. In at least some implementations, the skew factor can be removed from new data allocation, such as in response to an indication that data allocation between the new partitions and the existing partitions is unbalanced.

Claims

1. A device comprising:

a processor; and

a memory in communication with the processor, the memory comprising executable instructions that, when executed by the processor, cause the processor to control the device to perform operations for repartitioning a database to increase a storage capacity, the operations including;

creating a first membership record of a plurality of first keys corresponding to a plurality of first data entries, respectively, in a first partition associated with a first partition function, wherein the first data entries represent the database existing prior to adding a new partition;

adding, to the database of the first partition, a second partition associated with a second partition function; and

implementing a composite partition function to the database such that the first data entries existed in the first partition prior to adding the second partition keep their respective locations in the first partition, wherein, upon implementing the composite partition function, the device is controlled to perform operations of;

receiving a first request for a first requested data entry in the database;

applying the first partition function to locate the first requested data entry in the first partition when the first membership record includes a first key corresponding to the first requested data entry; and

applying the second partition function to locate the first requested data entry in the second partition when the first membership record does not include a first key corresponding to the first requested data entry.

2. The device of claim 1, wherein the first partition function includes mapping the plurality of first keys to the first partition, and the second partition function includes mapping a plurality of second keys to the second partition, the plurality of second keys corresponding to a plurality of second data entries, respectively, added to the second partition.

3. The device of claim 1, the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform functions of:

creating a second membership record of a plurality of second keys corresponding to a plurality of second data entries, respectively, added to the second partition;

adding, to the database of the first and second partitions, a third partition associated with a third partition function;

receiving a second request for a second requested data entry in the database;

applying the first partition function when the first membership record includes a first key corresponding to the second requested data entry;

applying the second partition function when the second membership record includes a second key corresponding to the second requested data entry; and

applying the third partition function when the first and second membership records do not include any key corresponding to the second requested data entry.

4. The device of claim 3, wherein the third partition function includes mapping a plurality of third keys to the third partition, the plurality of third keys corresponding to a plurality of third data entries, respectively, added to the third partition.

5. The device of claim 1, wherein the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform functions of rebalancing allocation of new data entries added to the database between the first and second partitions.

6. The device of claim 5, wherein, to rebalance the allocation of the new data entries, the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform a function of distributing the new data entries based on a skew factor to unevenly allocate the new data entries to one of the first and second partitions more frequently than the other partition.

7. The device of claim 6, wherein the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform a function of dynamically altering the skew factor based on relative loads of the first and second partitions.

8. The device of claim 5, wherein, to rebalance the allocation of the new data entries, the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform a function of:

allocating the new data entries to the first partition at a first interval; and

allocating the new data entries to the second partition at a second interval that is different from the first interval.

9. A method for repartitioning a database, comprising:

creating a first membership record of a plurality of first keys corresponding to a plurality of first data entries, respectively, in a first partition associated with a first partition function, wherein the first data entries represent the database existing prior to adding a new partition;

adding, to the database of the first partition, a second partition associated with a second partition function; and

implementing a composite partition function to the database such that the first data entries existed in the first partition prior to adding the second partition keep their respective locations in the first partition, wherein implementing the composite partition function comprises;

receiving a first request for a first requested data entry in the database;

applying the first partition function to locate the first requested data entry in the first partition when the first membership record includes a first key corresponding to the first requested data entry; and

applying the second partition function to locate the first requested data entry in the second partition when the first membership record does not include a first key corresponding to the first requested data entry.

10. The method of claim 9, wherein the first partition function includes mapping the plurality of first keys to the first partition, and the second partition function includes mapping a plurality of second keys to the second partition, the plurality of second keys corresponding to a plurality of second data entries, respectively, added to the second partition.

11. The method of claim 9, further comprising:

creating a second membership record of a plurality of second keys corresponding to a plurality of second data entries, respectively, added to the second partition;

adding, to the database of the first and second partitions, a third partition associated with a third partition function;

receiving a second request for a second requested data entry in the database;

applying the first partition function when the first membership record includes a first key corresponding to the second requested data entry;

applying the second partition function when the second membership record includes a second key corresponding to the second requested data entry; and

applying the third partition function when the first and second membership records do not include any key corresponding to the second requested data entry.

12. The method of claim 11, wherein the third partition function includes mapping a plurality of third keys to the third partition, the plurality of third keys corresponding to a plurality of third data entries, respectively, added to the third partition.

13. The method of claim 9, further comprising rebalancing allocation of new data entries added to the database between the first and second partitions.

14. The method of claim 13, wherein rebalancing the allocation of the new data entries comprises distributing the new data entries based on a skew factor to unevenly allocate the new data entries to one of the first and second partitions more frequently than the other partition.

15. The method of claim 14, further comprising dynamically altering the skew factor based on relative loads of the first and second partitions.

16. The method of claim 13, wherein rebalancing the allocation of the new data entries comprises:

allocating the new data entries to the first partition at a first interval; and

allocating the new data entries to the second partition at a second interval that is different from the first interval.

17. A device comprising:

a processor; and

a memory in communication with the processor, the memory comprising executable instructions that, when executed by the processor, cause the processor to control the device to perform functions for implementing a composite partition function to a database such that data entries existed in a first partition of the database prior to adding a second partition keep their respective locations in the first partition, the functions comprising;

creating a membership record of a plurality of keys corresponding to a plurality of data entries, respectively, in the first partition, the data entries representing the database existing prior to adding the second partition;

receiving a request for a data entry in the database;

determining whether a key corresponding to the requested data entry is found in the membership record;

searching the first partition to locate the requested data entry when it is determined that a key corresponding to the requested data entry is found in the membership record; and

searching the second partition to locate the requested data entry when it is determined that a key corresponding to the requested data entry is not found in the membership record.

18. The device of claim 17, wherein the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform a function of rebalancing allocation of new data entries added to the database between the first and second partitions.

19. The device of claim 18, wherein, to rebalance the allocation of the new data entries, the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform a function of distributing the new data entries based on a skew factor to unevenly allocate the new data entries to one of the first and second partitions more frequently than the other partition, the skew factor being dynamically altered based on relative loads of the first and second partitions.

20. The device of claim 18, wherein, to rebalance the allocation of the new data entries, the instructions further include instructions that, when executed by the processor, cause the processor to control the device to perform functions of:

allocating the new data entries to the first partition at a first interval; and

allocating the new data entries to the second partition at a second interval that is different from the first interval.