Incremental block level backup

• US 9,558,073 B2
• Filed: 04/13/2015
• Issued: 01/31/2017
• Est. Priority Date: 10/18/2013
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Cantwell, Jared, Holiday, Matt
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): TESSEMA, AIDA Z
• Application Number:
  US14/684,966
• Publication Number:
  US 20150220402A1
• Time in Patent Office: 659 Days
• Field of Search: None
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 16/14 Details of searching files based on file metadata
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/9027 Trees
• CPC Class Codes: G06F 2201/80 Database-specific techniques

Abstract

Disclosed are systems, computer-readable mediums, and methods for incremental block level backup. An initial backup of a volume is created at a backup server, where creating the initial backup includes retrieving an original metadata file from a metadata server, and retrieving a copy of all data of the volume based on the original metadata file. A first incremental backup of the volume is then created at the backup server, where creating the first incremental backup includes retrieving a first metadata file, where the first metadata file was created separately from the original metadata file. A block identifier of the first metadata file is compared to a corresponding block identifier of the original metadata file to determine a difference between the first and original block identifiers, and a copy of a changed data block of the volume is retrieved based on the comparison of the first and original block identifiers.

Claims

1. A system comprising:

a backup server comprising one or more processors configured to;

retrieve an original metadata file from a metadata server, wherein the metadata file comprises an ordered list of block identifiers for data blocks of the volume, wherein each block identifier is used to access a data block stored on a block server, and wherein each block identifier is a hash based on content of its corresponding data block;

retrieve a copy of all data of the volume based on the original metadata file;

retrieve a first metadata file, wherein the first metadata file was created separately from the original metadata file;

compare a block identifier of the first metadata file to a corresponding block identifier of the original metadata file to determine a difference between the first and original block identifiers, wherein the difference indicates that a data block corresponding to the first block identifier has changed;

retrieve, using the block identifier that identifies a storage location of the changed data block, the changed data block based on the comparison of the first and original block identifiers, wherein the original metadata file comprises an original hash tree, wherein the first metadata file comprises a first hash tree;

determine a subtree root node of the first hash tree is different than an original root node of the original hash tree;

add child nodes of the subtree root node to a first data structure;

for each child node in the data structure;

determine a corresponding node in the original hash tree;

determine if the child node is different than the corresponding node;

determine if the child node is a leaf node or a non-leaf node based on the determination that the child node is different than the corresponding node;

add the child node to the first data structure based on the determination that the child node is a non-leaf node; and

add the child node to a second data structure based on the determination that the child node is a leaf node; and

for each node in the second data structure retrieve a corresponding data block using the block identifier.

2. The system of claim 1, wherein the one or more processors are further configured to:

determine a size of the volume has increased;

determine a location of a subtree within the first hash tree that has a subtree root node corresponding to the original root node of the original hash tree;

determine all leaf nodes of the first hash tree that are not within the subtree;

retrieve data blocks corresponding to all leaf nodes of the first hash tree that are not within the subtree.

3. The system of claim 1, wherein the one or more processors are further configured to:

retrieve a second metadata file, wherein the second metadata file was created separately from the first metadata file;

compare a block identifier of the second metadata file to a corresponding block identifier of the first metadata file to determine a difference between the second and first block identifiers, wherein the difference between the second and first block identifiers indicates that a data block corresponding to the second block identifier has changed; and

retrieve the changed data block corresponding to the second block identifier based on the comparison of the second and first block identifiers.

4. The system of claim 1, wherein the data of the volume is compressed data.

5. The system of claim 1, wherein the one or more processors are further configured to create the initial backup or the incremental backup in response to a request received via an application programming interface (API) of the backup server.

6. The system of claim 1, wherein data is retrieved by the one or more processors of the backup server according a protocol of at least one of small computer system interface (SCSI), Internet small computer system interface (ISCSI), fibre channel (FC), common Internet file system (CIFS), network file system (NFS), hypertext transfer protocol (HTTP), hypertext transfer protocol secure (HTTPS), web-based distributed authoring and versioning (WebDAV), and a custom protocol.

7. A method comprising:

creating an initial backup of a volume at a backup server, wherein creating the initial backup comprises;

retrieving an original metadata file from a metadata server, wherein the metadata file comprises an ordered list of block identifiers for data blocks of the volume, wherein each block identifier is used to access a data block stored on a block server, and wherein each block identifier is a hash based on content of its corresponding data block; and

retrieving a copy of all data of the volume based on the original metadata file; and

creating a first incremental backup of the volume at the backup server, wherein creating the first incremental backup comprises;

retrieving a first metadata file, wherein the first metadata file was created separately from the original metadata file;

comparing a block identifier of the first metadata file to a corresponding block identifier of the original metadata file to determine a difference between the first and original block identifiers, wherein the difference indicates that a data block corresponding to the first block identifier has changed; and

retrieving, using the block identifier that identifies a storage location of the changed data block, the changed data block based on the comparison of the first and original block identifiers, wherein the original metadata file comprises an original hash tree, wherein the first metadata file comprises a first hash tree;

determining a subtree root node of the first hash tree is different than an original root node of the original hash tree;

adding child nodes of the subtree root node to a first data structure;

for each child node in the data structure;

determining a corresponding node in the original hash tree;

determining if the child node is different than the corresponding node;

determining if the child node is a leaf node or a non-leaf node based on the determination that the child node is different than the corresponding node;

adding the child node to the first data structure based on the determination that the child node is a non-leaf node; and

adding the child node to a second data structure based on the determination that the child node is a leaf node; and

for each node in the second data structure retrieving a corresponding data block using the block identifier.

8. The method of claim 7, further comprising:

determining a size of the volume has increased;

determining a location of a subtree within the first hash tree that has a subtree root node corresponding to the original root node of the original hash tree;

determining all leaf nodes of the first hash tree that are not within the subtree;

retrieving data blocks corresponding to all leaf nodes of the first hash tree that are not within the subtree.

9. The method of claim 7, further comprising creating a second incremental backup of the volume, wherein creating the second incremental backup comprises:

retrieving a second metadata file, wherein the second metadata file was created separately from the first metadata file;

comparing a block identifier of the second metadata file to a corresponding block identifier of the first metadata file to determine a difference between the second and first block identifiers, wherein the difference between the second and first block identifiers indicates that a data block corresponding to the second block identifier has changed; and

retrieving the changed data block corresponding to the second block identifier based on the comparison of the second and first block identifiers.

10. The method of claim 7, wherein the data of the volume is compressed data.

11. The method of claim 7, wherein the initial backup or the incremental backup are created in response to a request received via an application programming interface (API) of the backup server.

12. The method of claim 7, wherein data is retrieved according a protocol of at least one of small computer system interface (SCSI), Internet small computer system interface (ISCSI), fibre channel (FC), common Internet file system (CIFS), network file system (NFS), hypertext transfer protocol (HTTP), hypertext transfer protocol secure (HTTPS), web-based distributed authoring and versioning (WebDAV), and a custom protocol.

13. A non-transitory computer-readable medium having instructions stored thereon, that when executed by a computing device cause the computing device to perform operations comprising:

creating an initial backup of a volume at a backup server, wherein creating the initial backup comprises;

retrieving an original metadata file from a metadata server, wherein the metadata file comprises an ordered list of block identifiers for data blocks of the volume, wherein each block identifier is used to access a data block stored on a block server, and wherein each block identifier is a hash based on content of its corresponding data block; and

retrieving a copy of all data of the volume based on the original metadata file; and

creating a first incremental backup of the volume at the backup server, wherein creating the first incremental backup comprises;

retrieving a first metadata file, wherein the first metadata file was created separately from the original metadata file;

comparing a block identifier of the first metadata file to a corresponding block identifier of the original metadata file to determine a difference between the first and original block identifiers, wherein the difference indicates that a data block corresponding to the first block identifier has changed; and

retrieving, using the block identifier that identifies a storage location of the changed data block, the changed data block based on the comparison of the first and original block identifiers, wherein the original metadata file comprises an original hash tree, wherein the first metadata file comprises a first hash tree;

determining a subtree root node of the first hash tree is different than an original root node of the original hash tree;

adding child nodes of the subtree root node to a first data structure;

for each child node in the data structure;

determining a corresponding node in the original hash tree;

determining if the child node is different than the corresponding node;

determining if the child node is a leaf node or a non-leaf node based on the determination that the child node is different than the corresponding node;

adding the child node to the first data structure based on the determination that the child node is a non-leaf node; and

adding the child node to a second data structure based on the determination that the child node is a leaf node; and

for each node in the second data structure retrieving a corresponding data block using the block identifier.

14. The non-transitory computer-readable medium of claim 13, wherein the operations further comprise:

determining a size of the volume has increased;

determining a location of a subtree within the first hash tree that has a subtree root node corresponding to the original root node of the original hash tree;

determining all leaf nodes of the first hash tree that are not within the subtree;

retrieving data blocks corresponding to all leaf nodes of the first hash tree that are not within the subtree.

15. The non-transitory computer-readable medium of claim 13, wherein the operations further comprise creating a second incremental backup of the volume, wherein creating the second incremental backup comprises:

retrieving a second metadata file, wherein the second metadata file was created separately from the first metadata file;

comparing a block identifier of the second metadata file to a corresponding block identifier of the first metadata file to determine a difference between the second and first block identifiers, wherein the difference between the second and first block identifiers indicates that a data block corresponding to the second block identifier has changed; and

retrieving the changed data block corresponding to the second block identifier based on the comparison of the second and first block identifiers.

16. The non-transitory computer-readable medium of claim 13, wherein the data of the volume is compressed data.

17. The non-transitory computer-readable medium of claim 13, wherein the initial backup or the incremental backup are created in response to a request received via an application programming interface (API) of the backup server.