Background movement of data between nodes in a storage cluster

• US 7,778,960 B1
• Filed: 10/20/2006
• Issued: 08/17/2010
• Est. Priority Date: 10/20/2005
• Status: Active Grant

• Current Assignee: AmZetta Technologies, LLC (American Megatrends International, LLC)
• Original Assignee: American Megatrends Incorporated
• Inventors: Chatterjee, Paresh, Balakrishnan, Narayanan, Mahalingam, Anandh, Subramanian, Srikumar
• Primary Examiner(s): Ali; Mohammad
• Assistant Examiner(s): HASAN, SYED HAROON
• Application Number:
  US11/551,303
• Time in Patent Office: 1,397 Days
• Field of Search: None
• US Class Current: 707/609
• CPC Class Codes: G06F 16/214 Database migration support
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor

Abstract

A method, system, apparatus, and computer-readable medium are described for the background movement of data between nodes in a storage cluster. According to one method, exception tables are generated that include data identifying the areas on each node that need to be migrated to another node and the areas on each node that are to be migrated from another node. The exception tables may be generated in response to the failure of a node in the storage cluster or in other circumstances. A background resynchronization thread utilizes the contents of the exception tables to migrate data between the nodes of the cluster, thereby synchronizing the data stored on the nodes. Input/output operations directed to an area that is to be migrated from another node are redirected to the other node. The methods, systems, apparatus, and computer-readable medium may be utilized with operations including the rebuilding, expansion, contraction, and compaction of a storage cluster.

Claims

1. A method for moving data between nodes of a storage cluster, the method comprising:

creating a positive exception table in a first node of the storage cluster in response to determining that one of the nodes of the storage cluster has failed, the positive exception table comprising a bitmap identifying the areas of the first node that need to be migrated to a destination node in the storage cluster;

creating a negative exception table in the destination node, the negative exception table comprising a bitmap identifying areas of the destination node that need to be migrated from the first node to the destination node; and

executing a background process for migrating data from the first node to the destination node according to the contents of the positive exception table, wherein the background process is configured to

identify based upon the contents of the positive exception table an area of the first node that needs to be migrated to the destination node;

lock the area of the first node containing the data to be migrated;

copy the data to be migrated to a buffer;

write the data from the buffer to an area on the destination node; and

following completion of the write, alter the positive exception table in the first node to indicate that the area of the first node does not need to be migrated to the destination node and alter the negative exception table in the destination node to indicate that the area of the destination node does not need to be migrated from the first node.

2. The method of claim 1, further comprising during the execution of the background process:

receiving an input/output (I/O) operation at the first node, the I/O operation directed to an area of the destination node;

determining based upon the positive exception table whether the area of the destination node identified in the I/O operation needs to be migrated from the first node to the destination node; and

forwarding the I/O operation to the destination node in response to determining that the area of the destination node identified in the I/O operation does not need to be migrated from the first node.

3. The method of claim 1, further comprising during the execution of the background process:

receiving an input/output (I/O) operation at the first node, the I/O operation directed to an area of the destination node;

determining based upon the positive exception table whether the area of the destination node identified in the I/O operation needs to be migrated from the first node to the destination node; and

fielding the I/O operation at the first node in response to determining that the area of the destination node identified in the I/O operation needs to be migrated from the first node to the destination node.

4. The method of claim 1, further comprising during the execution of the background process:

receiving an input/output (I/O) operation at the destination node, the I/O operation directed to an area of the destination node;

determining based upon the negative exception table whether the area of the destination node identified in the I/O operation needs to be migrated from the first node to the destination node; and

forwarding the I/O operation to the first node in response to determining that the area of the destination node identified in the I/O operation needs to be migrated from the first node.

5. The method of claim 1, further comprising during the execution of the background process:

receiving an input/output (I/O) operation at the destination node, the I/O operation directed to an area of the destination node;

determining based upon the negative exception table whether the area of the destination node identified in the I/O operation needs to be migrated from the first node to the destination node; and

fielding the I/O operation at the destination node in response to determining that the area of the destination node identified in the I/O operation does not need to be migrated from the first node.

6. The method of claim 1, wherein the lock operates to queue any input/output (I/O) operations received for the area of the first node to be migrated until the migration of the area is completed.

7. A computer-readable storage medium having computer-executable instructions stored thereon which, when executed by a computer, cause the computer to:

generate a positive exception table for a first node in a storage cluster, the positive exception table comprising a bitmap identifying one or more areas on the first node that need to be synchronized from the first node to a destination node in the storage cluster;

generate a negative exception table for the destination node, the negative exception table comprising a bitmap identifying one or more areas on the destination node that need to be synchronized from other nodes in the storage cluster to the destination node;

execute a background synchronization thread to synchronize the contents of the first node from the first node to the destination node in the storage cluster based upon the data contained in the positive exception table, wherein the background synchronization thread is operative to

identify based upon the contents of the positive exception table an area of the first node that needs to be migrated to the destination node,

lock the area of the first node containing the data to be migrated,

copy the data to be migrated to a buffer,

write the data from the buffer to an area on the destination node, and

following completion of the write, alter the positive exception table in the first node to indicate that the area of the first node does not need to be migrated to the destination node and alter the negative exception table in the destination node to indicate that the area of the destination node does not need to be migrated from the first node;

receive an input/output (I/O) operation directed toward an area of the destination node identified in the negative exception table as requiring synchronization from another node in the storage cluster;

in response to receiving the I/O operation, redirect the I/O operation to the other node in the storage cluster for fielding;

receive an input/output (I/O) operation directed toward an area of the first node identified in the positive exception table as requiring synchronization to the destination node in the storage cluster; and

fielding the I/O operation locally in response to receiving the I/O operation directed toward an area of the first node identified in the positive exception table as requiring synchronization to the destination node.

8. A computer system comprising two or more storage server computers, each storage server computer operating as a storage node, and each storage node configured to generate a first bitmap identifying storage areas for migration to a destination node in the computer system in response to determining that another of the storage nodes has failed, and to execute a background process for migrating the contents of the areas of the storage nodes to the destination node according to the contents of the first bitmap, wherein the destination node contains a second bitmap identifying one or more areas on the destination node that need to be migrated from the storage nodes in the computer system to the destination node and the background process is configured to:

identify based upon the contents of the first bitmap an area of a source storage node that needs to be migrated to the destination node;

lock the area of the source storage node containing the data to be migrated;

copy the data to be migrated to a buffer;

perform a write operation to write the data from the buffer to an area on the destination node; and

following completion of the write operation, alter the first bitmap on the source storage node to indicate that the area of the source storage node does not need to be migrated to the destination node and alter the second bitmap on the destination node to indicate that the area of the destination node does not need to be migrated from the source storage node.

9. The computer system of claim 8, wherein each storage node is further configured to receive an input/output (I/O) request during the execution of the background process, to determine based upon the contents of the bitmap whether the I/O request is directed toward an area of the storage node that needs to be migrated to the destination node, and to field the I/O request locally in response to determining that the I/O request is directed toward an area of the storage node that needs to be migrated to the destination node.

10. The computer system of claim 8, wherein the background process is executed in response to determining that the failed storage node has been replaced and wherein the destination node comprises a replacement storage node for the failed storage node.