Maintaining hole boundary information for restoring snapshots from parity

• US 10,078,549 B2
• Filed: 05/19/2015
• Issued: 09/18/2018
• Est. Priority Date: 05/19/2015
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Karamanolis, Christos, Berinde, Radu, Wang, Wenguang
• Primary Examiner(s): Blair, April Ying Shan
• Assistant Examiner(s): Tang, Rong
• Application Number:
  US14/716,740
• Publication Number:
  US 20160342468A1
• Time in Patent Office: 1,218 Days
• 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/14 Error detection or correction of the data by redundancy in operation G06F11/16 takes precedence
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/16 Error detection or correction of the data by redundancy in hardware
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 2211/104 Metadata, i.e. metadata associated with RAID systems with parity
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD

Abstract

Exemplary methods, apparatuses, and systems maintain hole boundary information by calculating a block attribute parity value. For example, a request is received to write to a first block of a stripe of data. A block attribute of a second block is determined. The block attribute of the second block indicates whether the second block includes written data or is a hole. A block attribute parity value is calculated based upon both the block attribute of the first block and the block attribute of the second block. The block attribute of the first block indicates the first block includes written data based upon the received request. The block attribute parity value and the data parity value are stored on one of the physical storage devices in response to the received write request. As a result, if a disk is lost, holes can be recovered using the block attribute parity value.

Claims

1. A computer-implemented method, comprising:

receiving a request to write to a first block of a stripe of data stored across different physical storage devices;

determining a block attribute of a second block in the stripe of data, wherein the block attribute of the second block indicates whether the second block includes written data or is a hole;

calculating a block attribute parity value based upon both a block attribute of the first block and the block attribute of the second block, wherein the block attribute of the first block indicates the first block includes data written based upon the request;

calculating a data parity value for blocks within the stripe based upon contents of the first block and contents of the second block;

storing the block attribute parity value and the data parity value on one of the physical storage devices in response to the request; and

in response to determining that a storage device storing the second block cannot be reached, recovering the second block by calculating the block attribute value of the second block using the block attribute of the first block and the block attribute parity value.

2. The computer-implemented method of claim 1, further comprising:

determining the stripe of data is a part of a snapshot, wherein the snapshot represents a difference between a current state of stored data and a previous state of the stored data, and wherein the hole within the stripe represents a block of a stored data that remained unchanged from the previous state to the current state and was not copied to the snapshot.

3. The computer-implemented method of claim 1, wherein calculating the block attribute parity value includes calculating an XOR of the block attribute of the first block and the block attribute of the second block.

4. The computer-implemented method of claim 1, further comprising:

determining the request to write to the first block is a part of request to write to less than all blocks of the stripe; and

in response to determining that the request to write to less than all blocks of the stripe is directed to more than a threshold amount of the stripe, determining a block attribute of each block not being written, wherein calculating the block attribute parity value is further based upon the block attribute of each block not being written.

5. The computer-implemented method of claim 1, further comprising:

determining the request to write to the first block is a part of request to write to less than all blocks of the stripe; and

in response to determining that the request to write to less than all blocks of the stripe is directed to less than a threshold amount of the stripe, determining a previous block attribute parity value, wherein calculating the block attribute parity value is further based upon the previous block attribute parity value.

6. The computer-implemented method of claim 1, wherein determining the block attribute of the second block in the stripe includes requesting a local storage manager provide an indication of whether the second block includes written data or is a hole.

7. A non-transitory computer-readable medium storing instructions, which when executed by a processing device, cause the processing device to perform a method comprising:

receiving a request to write to a first block of a stripe of data stored across different physical storage devices;

determining a block attribute of a second block in the stripe of data, wherein the block attribute of the second block indicates whether the second block includes written data or is a hole;

calculating a block attribute parity value based upon both a block attribute of the first block and the block attribute of the second block, wherein the block attribute of the first block indicates the first block includes data written based upon the request;

calculating a data parity value for blocks within the stripe based upon contents of the first block and contents of the second block;

storing the block attribute parity value and the data parity value on one of the physical storage devices in response to the request; and

in response to determining that a storage device storing the second block cannot be reached, recovering the second block by calculating the block attribute value of the second block using the block attribute of the first block and the block attribute parity value.

8. The non-transitory computer-readable medium of claim 7, the method further comprising:

determining the stripe of data is a part of a snapshot, wherein the snapshot represents a difference between a current state of stored data and a previous state of the stored data, and wherein the hole within the stripe represents a block of a stored data that remained unchanged from the previous state to the current state and was not copied to the snapshot.

9. The non-transitory computer-readable medium of claim 7, wherein calculating the block attribute parity value includes calculating an XOR of the block attribute of the first block and the block attribute of the second block.

10. The non-transitory computer-readable medium of claim 7, the method further comprising:

determining the request to write to the first block is a part of request to write to less than all blocks of the stripe; and

in response to determining that the request to write to less than all blocks of the stripe is directed to more than a threshold amount of the stripe, determining a block attribute of each block not being written, wherein calculating the block attribute parity value is further based upon the block attribute of each block not being written.

11. The non-transitory computer-readable medium of claim 7, the method further comprising:

determining the request to write to the first block is a part of request to write to less than all blocks of the stripe; and

in response to determining that the request to write to less than all blocks of the stripe is directed to less than a threshold amount of the stripe, determining a previous block attribute parity value, wherein calculating the block attribute parity value is further based upon the previous block attribute parity value.

12. The non-transitory computer-readable medium of claim 7, wherein determining the block attribute of the second block in the stripe includes requesting a local storage manager provide an indication of whether the second block includes written data or is a hole.

13. An apparatus comprising:

a processing device; and

a memory coupled to the processing device, the memory storing instructions which, when executed by the processing device, cause the apparatus to;

receive a request to write to a first block of a stripe of data stored across different physical storage devices;

determine a block attribute of a second block in the stripe of data, wherein the block attribute of the second block indicates whether the second block includes written data or is a hole;

calculate a block attribute parity value based upon both a block attribute of the first block and the block attribute of the second block, wherein the block attribute of the first block indicates the first block includes data written based upon the request;

calculate a data parity value for blocks within the stripe based upon contents of the first block and contents of the second block;

store the block attribute parity value and the data parity value on one of the physical storage devices in response to the request; and

in response to determining that a storage device storing the second block cannot be reached, recover the second block by calculating the block attribute value of the second block using the block attribute of the first block and the block attribute parity value.

14. The apparatus of claim 13, wherein the instructions further cause the host computer to:

determining the stripe of data is a part of a snapshot, wherein the snapshot represents a difference between a current state of stored data and a previous state of the stored data, and wherein the hole within the stripe represents a block of a stored data that remained unchanged from the previous state to the current state and was not copied to the snapshot.

15. The apparatus of claim 13, wherein calculating the block attribute parity value includes calculating an XOR of the block attribute of the first block and the block attribute of the second block.

16. The apparatus of claim 13, wherein the instructions further cause the host computer to:

determining the request to write to the first block is a part of request to write to less than all blocks of the stripe; and

in response to determining that the request to write to less than all blocks of the stripe is directed to more than a threshold amount of the stripe, determining a block attribute of each block not being written, wherein calculating the block attribute parity value is further based upon the block attribute of each block not being written.

17. The apparatus of claim 13, wherein the instructions further cause the host computer to:

determining the request to write to the first block is a part of request to write to less than all blocks of the stripe; and

in response to determining that the request to write to less than all blocks of the stripe is directed to less than a threshold amount of the stripe, determining a previous block attribute parity value, wherein calculating the block attribute parity value is further based upon the previous block attribute parity value.