Tracking data of virtual disk snapshots using tree data structures

Patent metadata

Field	Value
Publication number	US-9881040-B2
Application number	US-201514831808-A
Country	US
Kind code	B2
Filing date	Aug 20, 2015
Priority date	Aug 20, 2015
Publication date	Jan 30, 2018
Grant date	Jan 30, 2018

Abstract

User data of different snapshots for the same virtual disk are stored in the same storage object. Similarly, metadata of different snapshots for the same virtual disk are stored in the same storage object, and log data of different snapshots for the same virtual disk are stored in the same storage object. As a result, the number of different storage objects that are managed for snapshots do not increase proportionally with the number of snapshots taken. In addition, any one of the multitude of persistent storage back-ends can be selected as the storage back-end for the storage objects according to user preference, system requirement, snapshot policy, or any other criteria. Another advantage is that the storage location of the read data can be obtained with a single read of the metadata storage object, instead of traversing metadata files of multiple snapshots.

First claim

What is claimed is:

1. A method of processing write requests to a virtual disk for which a first snapshot has been taken, comprising:
in response to a first write request received after taking the first snapshot and prior to taking a second snapshot, accessing a root node of a first tree data structure, traversing the first tree data structure starting at the root node to find a node associated with a logical address targeted by the first write request, issuing a first write command to store first write data associated with the first write request in a snapshot data storage object, and updating the first tree data structure to add a new node that includes a pointer to a location in the snapshot data storage object where the first write data is stored; and
in response to a second write request received after taking the second snapshot, accessing a root node of a second tree data structure, traversing the second tree data structure starting at the root node to find a node associated with a logical address targeted by the second write request, issuing a second write command to store second write data associated with the second write request in the snapshot data storage object, and updating the second tree data structure to add a new node that includes a pointer to a location in the snapshot data storage object where the second write data is stored,
wherein the snapshot data storage object is identified by a first object identifier (OID) and the first and second tree data structures are stored in the same snapshot metadata storage object that is identified by a second OID.

2. The method of claim 1 , wherein storage space for the snapshot data storage object is allocated in units of N megabytes, N being a configurable number, and each unit of N megabytes of data in the snapshot data storage object correspond to a contiguous range of logical addresses of the virtual disk.

3. The method of claim 1 , wherein storage locations of the root node of the first and second tree data structures are each stored in a snapshot management data structure as an OID and corresponding offset, and a mapping of each OID to a storage location of the corresponding storage object is also stored in the snapshot management data structure.

4. The method of claim 3 , wherein each of the first OID and the second OID maps to a storage object that is of a type different that of the virtual disk.

5. The method of claim 3 , wherein the virtual disk is a file and the first OID and the second OID also map to files.

6. The method of claim 1 , wherein the second tree data structure includes the root node, index nodes, and leaf nodes, each of the leaf nodes including a pointer to a data location, and the second tree data structure is traversed from the root node to one of the leaf nodes associated with the logical address targeted by the second write request, through one or more of the index nodes.

7. The method of claim 6 , wherein the root node of the second tree data structure includes pointers to a lower level node, and each of the pointers of the root node are indicated as being of first or second type, the first type being indicated if the root node from the first tree data structure has a pointer to the same lower level node, and the second type being indicated if the root node from the first tree data structure does not have a pointer to the same lower level node.

8. The method of claim 7 , further comprising:
if the second tree data structure is traversed from the root node to a lower level node of the first type, updating the second tree data structure to add an index node of the second type that replaces the lower level node of the first type and to redirect the pointer in the root node that points to the lower level node of the first type to the added index node.

9. The method of claim 8 , wherein the added index node includes a pointer to the new node that includes the pointer to the location in the snapshot data storage object where the second write data is stored.

10. The method of claim 7 , further comprising:
if the second tree data structure is traversed from the root node to a lower level node of the first type and the lower level node is an index node, updating the second tree data structure to add multiple index nodes of the second type and to redirect the pointer in the root node that points to the lower level node of the first type to one of the added index nodes,
wherein one of the added index nodes includes a pointer to the new node that includes the pointer to the location in the snapshot data storage object where the second write data is stored.

11. A non-transitory computer readable medium comprising instructions to be executed in a computer system to carry out a method of processing write requests to a virtual disk for which a first snapshot has been taken, said method comprising:
in response to a first write request received after taking the first snapshot and prior to taking a second snapshot, accessing a root node of a first tree data structure, traversing the first tree data structure starting at the root node to find a node associated with a logical address targeted by the first write request, issuing a first write command to store first write data associated with the first write request in a snapshot data storage object, and updating the first tree data structure to add a new node that includes a pointer to a location in the snapshot data storage object where the first write data is stored; and
in response to a second write request received after taking the second snapshot, accessing a root node of a second tree data structure, traversing the second tree data structure starting at the root node to find a node associated with a logical address targeted by the second write request, issuing a second write command to store second write data associated with the second write request in the snapshot data storage object, and updating the second tree data structure to add a new node that includes a pointer to a location in the snapshot data storage object where the second write data is stored,
wherein the snapshot data storage object is identified by a first object identifier (OID) and the first and second tree data structures are stored in the same snapshot metadata storage object that is identified by a second OID.

12. The non-transitory computer readable medium of claim 11 , wherein storage locations of the root node of the first and second tree data structures are each stored in a snapshot management data structure as an OID and corresponding offset, and a mapping of each OID to a storage location of the corresponding storage object is also stored in the snapshot management data structure.

13. The non-transitory computer readable medium of claim 12 , wherein the first OID and the second OID maps to a storage object that is of a type different that of the virtual disk.

14. The non-transitory computer readable medium of claim 12 , wherein the virtual disk is a file and the first OID and the second OID also maps to files.

15. The non-transitory computer readable medium of claim 11 , wherein the second tree data structure includes the root node, index nodes, and leaf nodes, each of the leaf nodes including a pointer to a data location, and the second tree data structure is traversed from the root node to one of the leaf nodes associated with the logical address targeted by the second write request, through one or more of the index nodes.

16. The non-transitory computer readable medium of claim 15 , wherein the root node of the second tree data structure includes pointers to a lower level node, and each of the pointers of

Assignees

• Vmware Inc

Inventors

• Rawat Mayank
• Shukla Ritesh
• Ding Li
• Pashenkov Serge
• Ahuja Raveesh

Classifications

• G06F3/067 Primary

  Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS] · CPC title

• G06F3/0641

  De-duplication techniques · CPC title

• G06F17/30327 Primary

  Physics · mapped topic

• G06F17/30088

  Physics · mapped topic

• G06F3/0608

  Saving storage space on storage systems · CPC title