Composite partition functions

• US 9,875,263 B2
• Filed: 10/21/2014
• Issued: 01/23/2018
• 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:
  US14/519,952
• Publication Number:
  US 20160110391A1
• Time in Patent Office: 1,190 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

Composite partition function techniques are described herein that may be used to repartition a database without moving existing data. In one or more implementations, a database is partitioned in a first arrangement associated with a first partition function. The database is repartitioned to form a second arrangement associated with a second partition function. A record of key membership for data entries in the partitions existing at the time of repartitioning is created, which can be used to recognize data corresponding to the first arrangement. A composite partition function is defined for subsequent database operations that is configured to apply the first partition function for data having keys found in the record of key membership and apply the second partition function for other data having keys that are not found in the record of key membership.

Claims

1. A method implemented by a computing device comprising:

partitioning a database with a first partition function; and

repartitioning the database by;

creating a record of key membership for data entries located in partitions existing at a time of repartitioning;

adding one or more new partitions associated with a second partition function;

defining a composite partition function for subsequent database operations configured to;

apply the first partition function for data having key values found in the record of key membership; and

apply the second partition function for data having key values not found in the record of key membership, wherein the repartitioning is performed such that the data entries located in partitions existing at the time of repartitioning keep their respective locations.

2. A method as described in claim 1, wherein the record of key membership is configured to record key values associated with data entries located in the partitions existing at the time of repartitioning.

3. A method as described in claim 1, wherein the record of key membership comprises a compressed data structure configured to identify keys corresponding to data entries existing in the database at the time of repartitioning.

4. A method as described in claim 1, wherein the record of key membership comprises a Bloom filter.

5. A method as described in claim 1, wherein the composite partition function is configured to combine two or more partition functions associated with successive partition arrangements.

6. A method as described in claim 1, wherein the first partition function and the second partition function are configured as hash functions that when applied to key values for data requests return data identifying partitions of the database corresponding to the key values.

7. A method as described in claim 1, wherein the first partition function comprises a prior composite function established for a previous repartitioning of the database to add additional storage capacity, the composite partition function configured to apply the prior composite function for data having key values found in the record of key membership and the second partition function for other data.

8. A method as described in claim 1, wherein the composite partition function is configured to bias allocation of data towards placement of new data entries on the new partitions to balance a distribution of data across partitions of the database.

9. A method as described in claim 1, wherein the composite partition function misrecognizes at least some key values for new data entries as being found in the record of key membership, such that data entries associated with misrecognized key values are allocated to and consistently located within the partitions existing at the time of repartitioning.

10. A computing device comprising:

a processing system; and

one or more modules that, when executed by the processing system, perform operations for repartitioning of a database to increase storage capacity including;

creating a record of key membership for data entries located in partitions of the database existing at the time of repartitioning, partitions of the database existing at a time of repartitioning associated with a first partition function;

adding a new partition associated with a second partition function; and

defining a composite partition function for handling of subsequent database requests configured to;

apply the first partition function for data requests including key values found in the record of key membership; and

apply the second partition function for data requests including key values not found in the record of key membership, such that data entries located in partitions existing at the time of repartitioning keep their respective locations in the partitions existing at the time of repartitioning.

11. The computing device of claim 10, wherein the record of key membership is configured as a Bloom filter having bit values set for keys associated with data entries existing at the time of repartitioning to indicate membership for the keys via the Bloom filter.

12. The computing device of claim 11, wherein:

the Bloom filter produces false positive errors according to a configurable tolerance which causes at least a portion of data entries created after repartitioning to be misrecognized and handled using the first partition function, the false positive errors being consistent such that misrecognized data entries are reliably located using the first partition function; and

a degree of compactness of the Bloom filter depends upon the configurable tolerance.

13. The computing device of claim 10, wherein the composite partition function is configured to combine the second partition function with a plurality of individual partition functions associated with multiple previous operations to repartition the database.

14. The computing device of claim 10, wherein the second partition function is configured to allocate data across partitions of the database existing at the time of repartitioning and the new partition.

15. A method implemented by a computing device comprising:

establishing a record of identifiers for data corresponding to a first partition function associated with a first arrangement of one or more partitions for a database;

reconfiguring the arrangement of partitions for the database to add at least one additional partition to increase storage capacity in a reconfigured arrangement;

generating a composite partition function that combines the first partition function associated with the first arrangement and a second partition function associated with the reconfigured arrangement, the composite partition function configured to use the record of identifiers to ascertain whether to apply the first partition function or the second partition function for routing of data requests between partitions for the database; and

routing data requests using the composite partition function.

16. A method as described in claim 15, wherein routing data requests using the composite partition function comprises for each data request:

using the record of identifiers to ascertain whether an identifier associated with the data request is included in the record of identifiers; and

when the identifier is included, routing the data request using the first partition function;

or

when the identifier is not included, routing the data request using the second partition function.

17. A method as described in claim 15, wherein the data requests comprises requests to access, add, or modify data entries in partitions of the database.

18. A method as described in claim 15, wherein data entries existing prior to the reconfiguring are not moved to different locations as a result of the reconfiguring.

19. A method as described in claim 15, wherein the second partition function comprises a modified hash function configured to incorporate a skew factor to cause allocation of new data to the at least one additional partition added for the reconfigured arrangement more frequently than to the one or more partitions existing for the first arrangement.