Data synchronization of multiple remote storage

• US 20050198453A1
• Filed: 03/02/2004
• Published: 09/08/2005
• Est. Priority Date: 03/02/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Hitachi, Ltd.
• Inventors: Osaki, Nobuyuki
• Granted Patent: US 7,111,139 B2
• Time in Patent Office: Days
• US Class Current: 711/162
• CPC Class Codes: G06F 11/2058 using more than 2 mirrored copies
• CPC Class Codes: G06F 11/2071 using a plurality of controllers
• CPC Class Codes: G06F 11/2074 Asynchronous techniques
• CPC Class Codes: G06F 11/2082 Data synchronisation
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99955 Archiving or backup

Abstract

A storage system comprises a plurality of storage subsystems. One storage subsystem as a succeeding subsystem is configured to receive and store one or more blocks of data from another storage subsystem as a preceding subsystem. Each block of data has an associated sequence number in ascending order. The memory in each storage subsystem includes a queue to store the blocks of data and a sequence number associated with each block of data, a record to store a last sequence number associated with a last block of data received by the queue, and a table to store last sequence numbers stored in the last sequence number record gathered from each succeeding storage system. In some embodiments, a smallest last sequence number is determined from the last sequence numbers associated with the blocks of data in the storage subsystems. Blocks of data in the queue of each storage subsystem having associated sequence numbers less than or equal to the determined smallest last sequence number are deleted. In case of a failure of one or more storage subsystems, blocks of data are copied from the surviving storage subsystem having associated sequence numbers higher than the last sequence number of other surviving storage subsystems.

Claims

1. A storage system comprising a plurality of storage subsystems,

wherein the plurality of storage subsystems each include a memory and a storage medium for storing data,

wherein the plurality of storage subsystems include at least one first storage subsystem and at least one second storage subsystem, the first storage subsystem being connected to the second storage subsystem which is configured to receive and store one or more blocks of data from the first storage subsystem, the first storage subsystem being a preceding storage subsystem to the second storage subsystem, the second storage subsystem being a succeeding storage subsystem to the first storage subsystem;

wherein each block of data being copied has an associated sequence number in ascending order,

wherein the memory in each of the storage subsystems includes a queue to receive and store the one or more blocks of data and a sequence number associated with each block of data, a last sequence number record to store a last sequence number associated with a last block of data received by the queue, and a table to store a last sequence number received from each succeeding storage system connected to the storage subsystem.

2. The storage system of claim 1 wherein the plurality of storage subsystems include at least one third storage system which is connected to the second storage system to receive and store one or more blocks of data from the second storage subsystem, the second storage subsystem being a preceding storage subsystem to the third storage subsystem, the third storage subsystem being a succeeding storage subsystem to the second storage subsystem.

3. The storage system of claim 1 wherein each storage subsystem includes a processor configured to search the smallest last sequence number in the table.

4. The storage system of claim 3 wherein the processor is configured to report the smallest last sequence number of the storage subsystem to any preceding storage subsystem.

5. The storage system of claim 3 wherein the processor is configured to report the smallest last sequence number of the storage subsystem to each succeeding storage subsystem if the storage subsystem has no preceding storage subsystem.

6. The storage system of claim 5:

wherein if a storage subsystem has a preceding storage subsystem, the processor of the storage subsystem is configured, upon receiving the smallest last sequence number from the preceding storage system, to delete blocks of data in the queue of the storage subsystem having associated sequence numbers less than or equal to the received smallest last sequence number; and

wherein if a storage subsystem has no preceding storage subsystem, the processor of the storage subsystem is configured, upon determining the smallest last sequence number of the storage system, to delete blocks of data in the queue of the storage subsystem having associated sequence numbers less than or equal to the received smallest last sequence number.

7. The storage system of claim 1 wherein each storage subsystem includes a processor configured, in case of a failure of one or more storage subsystems, to compare the last sequence number stored in the last sequence number record of the storage subsystem with the last sequence numbers stored in the last sequence number record of other surviving storage subsystems and, if the last sequence number stored in any one of the other surviving storage subsystems is larger than the last sequence number stored in the storage subsystem, to copy blocks of data from the one surviving storage subsystem having associated sequence numbers higher than the last sequence number of the storage subsystem to the queue of the storage subsystem.

8. A method for managing data stored in a storage system having a plurality of storage subsystems each including a memory and a storage medium for storing data, the plurality of storage subsystems including at least one first storage subsystem and at least one second storage subsystem, the first storage subsystem being connected to the second storage subsystem which is configured to receive and store one or more blocks of data from the first storage subsystem, the first storage subsystem being a preceding storage subsystem to the second storage subsystem, the second storage subsystem being a succeeding storage subsystem to the first storage subsystem, each block of data having an associated sequence number in ascending order, the method comprising:

copying one or more blocks of data from one storage subsystem to a succeeding storage subsystem connected to the one storage subsystem and storing each block of data copied and the associated sequence number in a queue in the memory of the succeeding storage subsystem;

storing a last sequence number in a last sequence number record in the memory of the succeeding storage subsystem; and

storing in a table in the memory of each storage subsystem a last sequence number in the last sequence number record of each succeeding storage system connected to the storage subsystem.

9. The method of claim 8 further comprising searching the smallest last sequence number in the table.

10. The storage system of claim 8 further comprising reporting the smallest last sequence number of the storage subsystem to any preceding storage subsystem.

11. The method of claim 10 further comprising reporting the smallest last sequence number of the storage subsystem to each succeeding storage subsystem if the storage subsystem has no preceding storage subsystem.

12. The method of claim 11 further comprising:

if a storage subsystem has a preceding storage subsystem, upon receiving the smallest last sequence number from the preceding storage system, deleting blocks of data in the queue of the storage subsystem having associated sequence numbers less than or equal to the received smallest last sequence number; and

if a storage subsystem has no preceding storage subsystem, upon determining the smallest last sequence number of the storage system, deleting blocks of data in the queue of the storage subsystem having associated sequence numbers less than or equal to the received smallest last sequence number.

13. The method of claim 8 further comprising, in case of a failure of one or more storage subsystems:

comparing the last sequence number stored in the last sequence number record of the storage subsystem with the last sequence numbers stored in the last sequence number record of other surviving storage subsystems; and

if the last sequence number stored in any one of the other surviving storage subsystems is larger than the last sequence number stored in the storage subsystem, copying blocks of data from the one surviving storage subsystem having associated sequence numbers higher than the last sequence number of the storage subsystem to the queue of the storage subsystem.

14. A method for managing data stored in a storage system having a plurality of storage subsystems each including a memory and a storage medium for storing data, the plurality of storage subsystems including at least one first storage subsystem and at least one second storage subsystem, the first storage subsystem being connected to the second storage subsystem which is configured to receive and store one or more blocks of data from the first storage subsystem, the first storage subsystem being a preceding storage subsystem to the second storage subsystem, the second storage subsystem being a succeeding storage subsystem to the first storage subsystem, each block of data having an associated sequence number in ascending order, the method comprising:

copying one or more blocks of data from one storage subsystem to a succeeding storage subsystem connected to the one storage subsystem and storing each block of data copied and the associated sequence number in a queue in the memory of the succeeding storage subsystem;

determining a smallest last sequence number from the last sequence numbers associated with the blocks of data in the storage subsystems; and

deleting blocks of data in the queue of each storage subsystem having associated sequence numbers less than or equal to the determined smallest last sequence number.

15. The method of claim 14 further comprising:

storing a last sequence number in a last sequence number record in the memory of each storage subsystem; and

storing in a table in the memory of each storage subsystem a last sequence number received from each succeeding storage system connected to the storage subsystem.

16. The method of claim 15 wherein determining the smallest last sequence number further comprises searching the smallest last sequence number in the table of each storage subsystem.

17. The method of claim 16 wherein determining the smallest last sequence number further comprises comparing the smallest last sequence number in the table of each storage subsystem and a smallest last sequence number identified in each succeeding storage subsystem to determine the smallest last sequence number of the storage subsystem.

18. The method of claim 17 further comprising:

reporting the smallest last sequence number of the each storage subsystem to each succeeding storage subsystem and any preceding storage subsystem.

19. The method of claim 18 wherein deleting blocks of data comprising:

if a storage subsystem has a preceding storage subsystem, upon receiving the smallest last sequence number from the preceding storage system, deleting blocks of data in the queue of the storage subsystem having associated sequence numbers less than or equal to the received smallest last sequence number; and

if a storage subsystem has no preceding storage subsystem, upon determining the smallest last sequence number of the storage system, deleting blocks of data in the queue of the storage subsystem having associated sequence numbers less than or equal to the received smallest last sequence number.

20. The method of claim 15, further comprising, in case of a failure of one or more storage subsystems:

comparing the last sequence number stored in the last sequence number record of the storage subsystem with the last sequence numbers stored in the last sequence number record of other surviving storage subsystems; and

if the last sequence number stored in any one of the other surviving storage subsystems is larger than the last sequence number stored in the storage subsystem, copying blocks of data from the one surviving storage subsystem having associated sequence numbers higher than the last sequence number of the storage subsystem to the queue of the storage subsystem.