SEAMLESS FAULT TOLERANCE VIA BLOCK REMAPPING AND EFFICIENT RECONCILIATION

• US 20190065062A1
• Filed: 12/22/2017
• Published: 02/28/2019
• Est. Priority Date: 08/28/2017
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: KNAUFT, Eric, SHAH, Mansi, ZHANG, Jin, DICKMANN, Christian, RENAULD, Pascal, VULLIKANTI, Radhika, KARAMANOLIS, Christos
• Granted Patent: US 10,642,526 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 11/0709 in a distributed system consisting of a plurality of standalone computer nodes, e.g. clusters, client-server systems
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS], H04L67/1097
• CPC Class Codes: G06F 11/0751 Error or fault detection not based on redundancy power supply failures G06F1/30; network fault management H04L41/06
• CPC Class Codes: G06F 11/0793 Remedial or corrective actions recovery from an exception in an instruction pipeline G06F9/3861; by retry G06F11/1402; for recovering from a failure of a protocol instance or entity H04L69/40
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/2087 with a common controller
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 2009/45583 Memory management, e.g. access or allocation
• CPC Class Codes: G06F 2201/815 Virtual middleware or OS functionality using virtual machines to implement generic software techniques for error detection or fault masking G06F11/1484
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0617 in relation to availability
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors

Abstract

In a storage cluster having nodes, blocks of a logical storage space of a storage object are allocated flexibly by a parent node to component nodes that are backed by physical storage. The method includes maintaining a first allocation map for the parent node, and second and third allocation maps for the first and second component nodes, respectively, executing a first write operation on the first component node and updating the second allocation map to indicate that the first block is a written block, and upon detecting that the first component node is offline, executing a second write operation that targets a second block of the logical storage space, which is allocated to the first component node, on the second component node and updating the third allocation map to indicate that the second block is a written block.

Claims

1. In a storage cluster having nodes that are arranged hierarchically, the nodes including a parent node and component nodes that are child nodes of the parent node, the component nodes including a first component node and a second component node, a method of allocating blocks of a logical storage space of a storage object by the parent node to one of the component nodes, comprising:

maintaining a first allocation map for the parent node, wherein second and third allocation maps are also maintained for the first and second component nodes, respectively;

communicating with the first component node to execute the received first write operation on the first component node and update the second allocation map to indicate that the first block is a written block; and

upon detecting that the first component node is offline, communicating with the second component node to execute a second write operation that targets a second block of the logical storage space, which is allocated to the first component node, on the second component node, and update the third allocation map to indicate that the second block is a written block.

2. The method of claim 1, further comprising:

upon detecting that the first component node has come back online, communicating with the first component node to update the second allocation map using the third allocation map.

3. The method of claim 1, further comprising:

upon detecting that the first component node has permanently failed, communicating with the second component node to update the third allocation map using a fourth allocation map.

4. The method of claim 1, wherein the storage object is a virtual disk object that is mirrored across a first mirror node and a second mirror node and the parent node is the first mirror node and the fourth allocation map is maintained for the second mirror node.

5. The method of claim 1, wherein the first allocation map is stored in volatile memory of the parent node and the second and third allocations maps are stored in non-volatile memory of the first and second component nodes, respectively.

6. The method of claim 1, wherein

a log sequence number is recorded in the non-volatile memory of the first component node each time the second allocation map is updated and in the non-volatile memory of the second component node each time the third allocation map is updated, and

the log sequence number is incremented each time the log sequence number is recorded in the non-volatile memory of any of the component nodes.

7. The method of claim 1, further comprising:

upon detecting that the first component node has come back online, determining a conflict between the second allocation map and the third allocation map, and determining that the second allocation map is stale based on the log sequence numbers recorded in the non-volatile memory of the first and second component nodes.

8. The method of claim 1, wherein the first allocation map allocates blocks to the component nodes at a granularity of a block.

9. The method of claim 1, wherein the first allocation map allocates blocks to the component nodes at a granularity of multiple blocks.

10. A non-transitory computer readable medium comprising instructions that are executable in a computer system, which is a parent node in a storage cluster having a plurality of hierarchically arranged nodes, the nodes further including component nodes that are child nodes of the parent node, the component nodes including a first component node and a second component node, wherein the instructions when executed in the computer system cause the computer system to carry out a method of allocating blocks of a logical storage space of a storage object to one of the component nodes, said method including the steps of:

maintaining a first allocation map for the parent node, wherein second and third allocation maps are also maintained for the first and second component nodes, respectively;

communicating with the first component node to execute the received first write operation on the first component node and update the second allocation map to indicate that the first block is a written block; and

upon detecting that the first component node is offline, communicating with the second component node to execute a second write operation that targets a second block of the logical storage space, which is allocated to the first component node, on the second component node, and update the third allocation map to indicate that the second block is a written block.

11. The non-transitory computer readable medium of claim 10, wherein the method further includes:

upon detecting that the first component node has come back online, communicating with the first component node to update the second allocation map using the third allocation map.

12. The non-transitory computer readable medium of claim 10, wherein the method further includes:

upon detecting that the first component node has permanently failed, communicating with the second component node to update the third allocation map using a fourth allocation map.

13. The non-transitory computer readable medium of claim 10, wherein the storage object is a virtual disk object that is mirrored across a first mirror node and a second mirror node and the parent node is the first mirror node and the fourth allocation map is maintained for the second mirror node.

14. The non-transitory computer readable medium of claim 10, wherein the method further includes:

upon detecting that the first component node has come back online, determining a conflict between the second allocation map and the third allocation map, and determining that the second allocation map is stale based on the log sequence numbers recorded in the non-volatile memory of the first and second component nodes.

15. The non-transitory computer readable medium of claim 10, wherein the first allocation map allocates blocks to the component nodes at a granularity of a block.

16. The non-transitory computer readable medium of claim 10, wherein the first allocation map allocates blocks to the component nodes at a granularity of multiple blocks.

17. A storage cluster having nodes that are arranged hierarchically, the nodes comprising:

a parent node; and

component nodes that are child nodes of the parent node, the component nodes including a first component node and a second component node,

wherein the parent node is programmed to carry out a method of allocating blocks of a logical storage space of a storage object to one of the component nodes, said method including the steps of;

maintaining a first allocation map for the parent node, wherein second and third allocation maps are also maintained for the first and second component nodes, respectively;

communicating with the first component node to execute the received first write operation on the first component node and update the second allocation map to indicate that the first block is a written block; and

upon detecting that the first component node is offline, communicating with the second component node to execute a second write operation that targets a second block of the logical storage space, which is allocated to the first component node, on the second component node, and update the third allocation map to indicate that the second block is a written block.

18. The storage cluster of claim 17, wherein the method further includes the step of:

upon detecting that the first component node has come back online, communicating with the first component node to update the second allocation map using the third allocation map.

19. The storage cluster of claim 17, wherein the method further includes the step of:

upon detecting that the first component node has permanently failed, communicating with the second component node to update the third allocation map using a fourth allocation map.

20. The storage cluster of claim 17, wherein the storage object is a virtual disk object that is mirrored across a first mirror node and a second mirror node and the parent node is the first mirror node.