Virtual machine snapshot backup based on multilayer de-duplication

• US 10,565,063 B2
• Filed: 09/06/2016
• Issued: 02/18/2020
• Est. Priority Date: 08/15/2012
• Status: Active Grant

• Current Assignee: Alibaba Group Holding Ltd.
• Original Assignee: Alibaba Group Holding Ltd.
• Inventors: Zhang, Wei, Tang, Hong, Jiang, Hao, Zeng, Yue, Li, Xiaogang
• Primary Examiner(s): Mofiz, Apu M
• Assistant Examiner(s): Nguyen, Cindy
• Application Number:
  US15/257,194
• Publication Number:
  US 20160378613A1
• Time in Patent Office: 1,260 Days
• 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/1464 for networked environments
• CPC Class Codes: G06F 11/1466 to make the backup process non-disruptive
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/128 Details of file system snapshots on the file-level, e.g. snapshot creation, administration, deletion use of snapshots for error detection or correction G06F11/14, G06F11/16
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/805 Real-time
• 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 2201/82 Solving problems relating to consistency ensuring consistency in mirrored systems G06F11/2064
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data

Abstract

The present disclosure provides an example method and system for virtual machine backup based on multilayer de-duplication. A virtual machine snapshot is divided into multiple child data blocks. Each child data block is divided into multiple data segments. Multilayer de-duplication is applied to the virtual machine snapshot to exclude data causing duplicate backup in the virtual machine snapshot. The remaining virtual machine snapshot data after the processing of the multilayer de-duplication is stored.

Claims

1. A computer-implemented method for virtual machine snapshot backup, comprising:

dividing a virtual machine snapshot of a virtual machine into one or more child data blocks;

applying a child data block de-duplication to exclude all child data blocks that are determined as unchanged since last snapshot;

dividing each of child data blocks marked as revised into a number of data segments;

applying a data segment de-duplication on each of the child data blocks to exclude from the number of data segments all data segments that are determined as unchanged since last snapshot;

applying a public data set de-duplication on data segments of the child data blocks that are determined as revised after the data segment de-duplication to exclude data segments that belong to a public data set; and

storing child data blocks and data segments that are not excluded as a virtual machine snapshot backup for the virtual machine snapshot, so as to exclude data causing duplicate backup in the virtual machine snapshot.

2. The computer-implemented method according to claim 1, wherein the public data set stores one or more data segments selected based on historical data of backup storage file system.

4. The computer-implemented method according to claim 1, wherein the public data set is centrally stored without considering boundaries of the child data blocks.

5. The computer-implemented method according to claim 1, wherein applying the child data block de-duplication further includes:

using accessing information recorded by one or more virtual disks to determine portions of one or more virtual disks that have not changed since last snapshot;

determining child data blocks of the unchanged portions as unchanged child data blocks since last snapshot;

creating a new snapshot index to the unchanged child data blocks and directly linking to corresponding child data blocks of last snapshot; and

excluding the unchanged child data blocks from further de-duplication.

6. The computer-implemented method according to claim 1, wherein dividing each of child data blocks marked as revised further includes:

based on a variant length cutting algorithm based on data content characteristics, dividing each of child data blocks marked as revised into a substantially large number of data segments.

7. The computer-implemented method according to claim 1, wherein applying the data segment de-duplication further includes:

based on an index of a corresponding previous child data block in last snapshot at a location of a current child data block, comparing data fingerprints of the previous child data blocks and the current child data block to determine which data segments in the current child data block are revised; and

directly linking an index of the current child data block to the data segment determined as unchanged.

8. The computer-implemented method according to claim 1, wherein applying the public data set de-duplication further includes:

calculating data fingerprints of the data segments using a predetermined algorithm;

sending the data fingerprints to the public data set to determine data segments that are existent in the public data set as unchanged data segments; and

excluding the unchanged data segments.

9. The computer-implemented method according to claim 8, wherein the predetermined algorithm is an SHAI hash algorithm.

10. The computer-implemented method according to claim 1, wherein the virtual machine snapshot comprises data fingerprints, sizes, and data points of the one or more child data blocks.

11. The computer-implemented method according to claim 1, wherein respective child data block comprises data fingerprints, sizes, and data points of the number of data segments.

12. The computer-implemented method according to claim 1, further comprising:

writing into a log deletion information of an index of the virtual machine snapshot backup;

when deletion information volume in the log is larger than a preset threshold, determining that a condition for deletion is met; and

deleting the virtual machine snapshot backup.

3. A computer-implemented method for virtual machine snapshot backup, comprising:

dividing a virtual machine snapshot of a virtual machine into one or more child data blocks;

applying a child data block de-duplication to exclude all child data blocks that are determined as unchanged since last snapshot;

dividing each of child data blocks marked as revised into a number of data segments;

applying a data segment de-duplication on each of the child data blocks to exclude from the number of data segments all data segments that are determined as unchanged since last snapshot;

applying a public data set de-duplication on data segments of the child data blocks that are determined as revised after the data segment de-duplication to exclude data segments that belong to a public data set, wherein the public data set stores one or more data segments with repetition rates higher than a preset threshold in a backup storage file system; and

storing child data blocks and data segments that are not excluded as a virtual machine snapshot backup for the virtual machine snapshot, so as to exclude data causing duplicate backup in the virtual machine snapshot.

13. A system for virtual machine snapshot backup, comprising:

a processor; and

a memory coupled to the processor for storing computer programs to be executed by the processor, wherein the processor is configured to;

divide a virtual machine snapshot of a virtual machine into one or more child data blocks;

apply a child data block de-duplication to exclude all child data blocks that are determined as unchanged since last snapshot;

divide each of child data blocks marked as revised into a number of data segments;

apply a data segment de-duplication on each of the child data blocks to exclude from the number of data segments all data segments that are determined as unchanged since last snapshot;

apply a public data set de-duplication on data segments of the child data blocks that are determined as revised after the data segment de-duplication to exclude data segments that belong to a public data set; and

store child data blocks and data segments that are not excluded as a virtual machine snapshot backup for the virtual machine snapshot, so as to exclude data causing duplicate backup in the virtual machine snapshot.

14. The system according to claim 13, wherein the public data set stores one or more data segments selected based on historical data of the backup storage file system.

15. The system according to claim 14, wherein the one or more data segments are selected as those with repetition rates higher than a preset threshold in the backup storage file system.

16. The system according to claim 13, wherein the public data set is centrally stored without considering boundaries of the child data blocks.

17. The system according to claim 13, wherein, to apply the child data block de-duplication, the processor is further configured to:

use accessing information recorded by one or more virtual disks to determine portions of one or more virtual disks that have not changed since last snapshot;

determine child data blocks of the unchanged portions as unchanged child data blocks since last snapshot;

create a new snapshot index to the unchanged child data blocks and directly linking to corresponding child data blocks of last snapshot; and

exclude the unchanged child data blocks from further de-duplication.

18. The system according to claim 13, wherein, to divide each of child data blocks marked as revised, the processor is further configured to:

based on a variant length cutting algorithm based on data content characteristics, divide each of child data blocks marked as revised into a substantially large number of data segments.

19. The system according to claim 13, wherein, to apply the data segment de-duplication, the processor is further configured to:

based on an index of a corresponding previous child data block in last snapshot at a location of a current child data block, compare data fingerprints of the previous child data blocks and the current child data block to determine which data segments in the current child data block are revised; and

directly link an index of the current child data block to the data segment determined as unchanged.

20. The system according to claim 13, wherein, to apply the public data set de-duplication, the processor is further configured to:

calculate data fingerprints of the data segments using a predetermined algorithm;

send the data fingerprints to the public data set to determine data segments that are existent in the public data set as unchanged data segments; and

exclude the unchanged data segments.