Mapping structure for maintaining metadata for snapshots in a virtualized storage environment

• US 9,720,921 B1
• Filed: 05/15/2014
• Issued: 08/01/2017
• Est. Priority Date: 08/10/2011
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Khot, Vinayak Hindurao, Memon, Tabrez Parvez, Bhattacharyya, Manosiz, Muthukkaruppan, Kannan
• Primary Examiner(s): Wu, Yicun
• Application Number:
  US14/278,429
• Time in Patent Office: 1,174 Days
• 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 16/1873 Versioning file systems, temporal file systems, e.g. file system supporting different historic versions of files
• CPC Class Codes: G06F 2009/45562 Creating, deleting, cloning virtual machine instances
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 2009/45575 Starting, stopping, suspending or resuming virtual machine instances
• CPC Class Codes: G06F 2009/45579 I/O management, e.g. providing access to device drivers or storage
• CPC Class Codes: G06F 2009/45583 Memory management, e.g. access or allocation
• CPC Class Codes: G06F 2009/45595 Network integration; Enabling network access in virtual machine instances
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• CPC Class Codes: G06F 3/0638 Organizing or formatting or addressing of data
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/45533 Hypervisors; Virtual machine monitors
• CPC Class Codes: G06F 9/45558 Hypervisor-specific management and integration aspects
• CPC Class Codes: G06F 9/48 Program initiating; Program switching, e.g. by interrupt
• CPC Class Codes: G06F 9/4806 Task transfer initiation or dispatching
• CPC Class Codes: G06F 9/4843 by program, e.g. task dispatcher, supervisor, operating system
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4856 : resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: G06F 9/4881 : Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06F 9/50 : Allocation of resources, e.g. of the central processing unit [CPU]
• CPC Class Codes: G06F 9/5005 : to service a request
• CPC Class Codes: G06F 9/5011 : the resources being hardware resources other than CPUs, Servers and Terminals
• CPC Class Codes: G06F 9/5016 : the resource being the memory
• CPC Class Codes: G06F 9/5022 : Mechanisms to release resources
• CPC Class Codes: G06F 9/5027 : the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5061 : Partitioning or combining of resources
• CPC Class Codes: G06F 9/5072 : Grid computing
• CPC Class Codes: G06F 9/5077 : Logical partitioning of resources; Management or configuration of virtualized resources specific details on emulation or internal functioning of virtual machines G06F9/455
• CPC Class Codes: G06F 9/5083 : Techniques for rebalancing the load in a distributed system
• CPC Class Codes: G06F 9/5088 : involving task migration
• CPC Class Codes: H04L 49/356 : for storage area networks

Abstract

A method for maintaining a mapping structure for maintaining metadata for snapshots in a virtualized storage environment, includes taking a snapshot of a virtual disk, generating an entry in a metadata structure for the snapshot, wherein the entry includes metadata for blocks in the snapshot that have been modified since a preceding snapshot and lazily generating an entry in the mapping structure for the snapshot, wherein the entry includes values for each block in the snapshot, wherein a value for a block indicates a presence of metadata in the metadata structure for the block or an absence of metadata in the metadata structure for the block.

Claims

1. A method for maintaining a mapping structure for maintaining metadata for snapshots in a virtualized storage environment, comprising:

taking a snapshot of a virtual disk;

generating an entry in a metadata structure for the snapshot, wherein the entry includes metadata for blocks in the snapshot that have been modified since a preceding snapshot, wherein the metadata comprise information indicating locations of physical data associated with the blocks in the snapshot; and

lazily generating an entry in the mapping structure for the snapshot, wherein the entry includes values for each block in the snapshot, wherein a value for a block indicates a presence of metadata in the metadata structure for the block or an absence of metadata in the metadata structure for the block, the value for the block is either an on-bit or an off-bit, wherein a background process lazily generates the entry in the mapping structure for the snapshot at a later time after taking the snapshot.

2. The method of claim 1, wherein taking the snapshot of the virtual disk comprises:

providing a name and version number for the snapshot;

marking the snapshot immutable; and

causing a live version of the virtual disk to be a child of the snapshot.

3. The method of claim 1, wherein the mapping structure is a bitmap.

4. The method of claim 1, wherein the metadata structure is a vDisk Block Map and the mapping structure is a vDisk Block Bitmap.

5. The method of claim 1, wherein an on-bit for the block indicates the presence of metadata for the block in the metadata structure for the snapshot and an ID of a parent snapshot for the block for the snapshot indicates the absence of metadata for the block in the metadata structure for the snapshot.

6. The method of claim 1, wherein an I/O request on the virtual disk causes the mapping structure to be consulted for determining which entries in the metadata structure include the needed metadata.

7. The method of claim 1, wherein the entry in the mapping structure is merged with one or more other entries in the mapping structure in response to corresponding snapshots of the virtual disk being merged.

8. The method of claim 7, wherein merging the entries in the mapping structure comprises collapsing values for each block in the entries into a nearest child entry that will remain after the merge is complete.

9. The method of claim 7, wherein the entry is merged with one other entry.

10. The method of claim 7, wherein the entry is merged with a group of other entries.

11. A computer program product embodied on a non-transitory computer readable medium, the non-transitory computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for maintaining a mapping structure for maintaining metadata for snapshots in a virtualized storage environment, comprising:

taking a snapshot of a virtual disk;

generating an entry in a metadata structure for the snapshot, wherein the entry includes metadata for blocks in the snapshot that have been modified since a preceding snapshot, wherein the metadata comprise information indicating locations of physical data associated with the blocks in the snapshot; and

lazily generating an entry in the mapping structure for the snapshot, wherein the entry includes values for each block in the snapshot, wherein a value for a block indicates a presence of metadata in the metadata structure for the block or an absence of metadata in the metadata structure for the block, the value for the block is either an on-bit or an off-bit, wherein a background process lazily generates the entry in the mapping structure for the snapshot at a later time after taking the snapshot.

12. The computer program product of claim 11, wherein taking the snapshot of the virtual disk comprises:

providing a name and version number for the snapshot;

marking the snapshot immutable; and

causing a live version of the virtual disk to be a child of the snapshot.

13. The computer program product of claim 11, wherein the mapping structure is a bitmap.

14. The computer program product of claim 11, wherein the metadata structure is a vDisk Block Map and the mapping structure is a vDisk Block Bitmap.

15. The computer program product of claim 11, wherein an on-bit for the block indicates the presence of metadata for the block in the metadata structure for the snapshot and an ID of a parent snapshot for the block for the snapshot indicates the absence of metadata for the block in the metadata structure for the snapshot.

16. The computer program product of claim 11, wherein an I/O request on the virtual disk causes the mapping structure to be consulted for determining which entries in the metadata structure include the needed metadata.

17. The computer program product of claim 11, wherein the entry in the mapping structure is merged with one or more other entries in the mapping structure in response to corresponding snapshots of the virtual disk being merged.

18. The computer program product of claim 17, wherein merging the entries in the mapping structure comprises collapsing values for each block in the entries into a nearest child entry that will remain after the merge is complete.

19. The computer program product of claim 17, wherein the entry is merged with one other entry.

20. The computer program product of claim 17, wherein the entry is merged with a group of other entries.

21. A system, comprising:

a processor; and

a memory comprising computer code executed using the processor, in which the computer code implements a method for maintaining a mapping structure for maintaining metadata for snapshots in a virtualized storage environment, the method comprising;

taking a snapshot of a virtual disk,

generating an entry in a metadata structure for the snapshot, wherein the entry includes metadata for blocks in the snapshot that have been modified since a preceding snapshot, wherein the metadata comprise information indicating locations of physical data associated with the blocks in the snapshot, and

lazily generating an entry in the mapping structure for the snapshot, wherein the entry includes values for each block in the snapshot, wherein a value for a block indicates a presence of metadata in the metadata structure for the block or an absence of metadata in the metadata structure for the block, the value for the block is either an on-bit or an off-bit, wherein a background process lazily generates the entry in the mapping structure for the snapshot at a later time after taking the snapshot.

22. The system of claim 21, wherein taking the snapshot of the virtual disk comprises:

providing a name and version number for the snapshot;

marking the snapshot immutable; and

causing a live version of the virtual disk to be a child of the snapshot.

23. The system of claim 21, wherein the mapping structure is a bitmap.

24. The system of claim 23, wherein the metadata structure is a vDisk Block Map and the mapping structure is a vDisk Block Bitmap.

25. The system of claim 21, wherein an on-bit for the block indicates the presence of metadata for the block in the metadata structure for the snapshot and an ID of a parent snapshot for the block for the snapshot indicates the absence of metadata for the block in the metadata structure for the snapshot.

26. The system of claim 21, wherein an I/O request on the virtual disk causes the mapping structure to be consulted for determining which entries in the metadata structure include the needed metadata.

27. The system of claim 21, wherein the entry in the mapping structure is merged with one or more other entries in the mapping structure in response to corresponding snapshots of the virtual disk being merged.

28. The system of claim 27, wherein merging the entries in the mapping structure comprises collapsing values for each block in the entries into a nearest child entry that will remain after the merge is complete.

29. The system of claim 27, wherein the entry is merged with one other entry.

30. The system of claim 27, wherein the entry is merged with a group of other entries.