Systems and methods for the repartitioning of data

• US 7,921,424 B2
• Filed: 09/13/2005
• Issued: 04/05/2011
• Est. Priority Date: 05/27/2003
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Nichols, Elizabeth Ann, Shutt, David R.
• Primary Examiner(s): Portka; Gary J
• Application Number:
  US11/225,626
• Publication Number:
  US 20060031268A1
• Time in Patent Office: 2,030 Days
• Field of Search: None
• US Class Current: 718/105
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

Various embodiments of the present invention are directed toward extending a federation of servers and balancing the data load of said federation of servers, in order to improve accessibility and scope of the system by moving the first backup data structure on the second server to the new server, creating a second data structure on the new server, and creating a second backup data structure for the second data structure on the second server. To balance the load, certain embodiments employ a method comprising suspending writes to the selected logical partitions, copying selected logical partitions to the new physical partition, redirecting reads and writes to the logical partitions in the new physical partition, and removing the original selected logical partitions. Alternative embodiments for balancing data load comprise the substitute steps of creating a temporary replication stream for the selected logical partitions to the new physical partition, copying selected logical partitions to the new physical partition, deconflicting inconsistencies in the logical partitions on the new physical partition, redirecting reads and writes for the selected logical partitions to the logical partitions in the new physical partition, and removing the original selected logical partitions that were copied to the new physical partition.

Claims

1. A method for balancing data load on a federation of servers, the method comprising:

creating a new physical partition on a new server in a federation of servers; and

utilizing the new server to balance data load, wherein utilizing the new server comprises;

selecting a first logical partition and a second logical partition from different existing servers in the federation of servers to be moved to the new physical partition on the new server;

concurrently suspending writes to the selected logical partitions of the different existing servers;

after suspending writes to the selected logical partitions, copying the selected logical partitions to the new physical partition;

redirecting reads and writes for the selected logical partitions on the different existing servers to the copied logical partitions in the new physical partition; and

removing the selected logical partitions from the different existing servers that were copied to the new physical partition;

wherein the new physical partition on the new server comprises a primary data structure for storing primary data residing on a first server of the plurality of existing servers of the federation of servers and a secondary data structure for storing a backup of the primary data residing on a second server of the plurality of existing servers of the federation of servers; and

wherein the selected logical partitions comprise a subset of the primary data on said first server to be stored in the primary data structure of the new physical partition and a corresponding subset of the backup of the primary data in said second server to be stored in the secondary data structure of the new physical partition.

2. The method of claim 1 wherein the step of suspending writes to selected logical partitions comprises holding the writes in a buffer and redirecting that buffer to the logical partitions in the new physical partition, and said method further comprising a step of re-enabling writes to the logical partitions in the new physical partition.

3. The method of claim 1 wherein the step of suspending writes to selected logical partitions comprises rejecting the writes and sending an error to an originating source of the write, said error to be handled by said originating source.

4. The method of claim 3 wherein the originating source handles the error by resending the write.

15. The method of claim 1, further comprising the following step:

accessing the secondary data structure when the primary data structure is unavailable.

16. The method of claim 1, wherein the physical partition further comprises additional secondary data structures residing on additional servers of the federation of servers wherein no more than one secondary data structure resides on a single server.

5. A system for balancing load on a federation of servers, the system comprising:

means for creating a new physical partition on a new server in a federation of servers; and

means for utilizing the new server to balance data load, wherein the means for utilizing the new server comprises;

means for selecting a first logical partition and a second logical partition from different existing servers of the federation of servers to be moved to the new physical partition on the new server;

means for concurrently suspending writes to the selected logical partitions of the different existing servers;

means for copying, after suspending writes to the selected logical partitions, the selected logical partitions to the new physical partition;

means for redirecting reads and writes for the selected logical partitions on the different existing servers to the copied logical partitions in the new physical partition; and

means for removing the selected logical partitions from the different existing servers that were copied to the new physical partition;

wherein the new physical partition on the new server comprises a primary data structure for storing primary data residing on a first server of the plurality of existing servers of the federation of servers, and a secondary data structure for storing a backup of the primary data residing on a second server of the plurality of existing servers of the federation of servers; and

wherein the selected logical partitions comprise a subset of the primary data on said first server to be stored in the primary data structure of the new physical partition and a corresponding subset of the backup of the primary data in said second server to be stored in the secondary data structure of the new physical partition.

6. The system of claim 5 wherein the means for suspending writes to selected logical partitions comprises means for holding the writes in a buffer and redirecting that buffer to the logical partitions in the new physical partition, and said system further comprising means for re-enabling writes to the logical partitions in the new physical partition.

7. The system of claim 5 wherein the means for suspending writes to selected logical partitions comprises means for rejecting the writes and sending an error to an originating source of the write, said error to be handled by said originating source.

8. The system of claim 7 wherein the originating source handles the error by resending the write.

17. The system of claim 5, further comprising:

means for accessing the secondary data structure when the primary data structure is unavailable.

18. The system of claim 5, wherein the physical partition further comprises additional secondary data structures residing on additional servers of the federation of servers wherein no more than one secondary data structure resides on a single server.

9. A computer-readable storage medium for use with a federation of servers, the computer-readable storage medium comprising computer-readable instructions that are executable by a computer for causing performance of acts for balancing data load on a federation of servers, the acts comprising:

creating a new physical partition on a new server in a federation of servers; and

utilizing the new server to balance data load, wherein utilizing the new server comprises;

selecting a first logical partition and a second logical partition from different existing servers in the federation of servers to be moved to the new physical partition on the new server;

concurrently suspending writes to the selected logical partitions of the different existing servers;

after suspending writes to the selected logical partitions, copying the selected logical partitions to the new physical partition;

redirecting reads and writes for the selected logical partitions on the different existing servers to the copied logical partitions in the new physical partition; and

removing the selected logical partitions from the different existing servers that were copied to the new physical partition;

wherein the new physical partition on the new server comprises a primary data structure for storing primary data residing on a first server of the plurality of existing servers of the federation of servers and a secondary data structure for storing a backup of the primary data residing on a second server of the plurality of existing servers of the federation of servers; and

wherein the selected logical partitions comprise a subset of the primary data on said first server to be stored in the primary data structure of the new physical partition and a corresponding subset of the backup of the primary data in said second server to be stored in the secondary data structure of the new physical partition.

10. The computer-readable storage medium of claim 9, wherein the computer-readable instructions for suspending writes to selected logical partitions comprise computer-readable instructions for holding the writes in a buffer and redirecting that buffer to the logical partitions in the new physical partition, and the computer-readable medium further comprising computer-readable instructions for re-enabling writes to the logical partitions in the new physical partition.

11. The computer-readable storage medium of claim 9, wherein the computer-readable instructions for suspending writes to selected logical partitions comprise computer-readable instructions for rejecting the writes and sending an error to an originating source of the write, the error to be handled by the originating source.

12. The computer-readable storage medium of claim 11, wherein the originating source handles the error by resending the write.

13. The computer-readable storage medium of claim 9, further comprising computer-readable instructions for:

accessing the secondary data structure when the primary data structure is unavailable.

14. The computer-readable storage medium of claim 9, wherein the physical partition further comprises additional secondary data structures residing on additional servers of the federation of servers wherein no more than one secondary data structure resides on a single server.