Metadata for managing I/O and storage for a virtualization

• US 8,850,130 B1
• Filed: 08/10/2011
• Issued: 09/30/2014
• Est. Priority Date: 08/10/2011
• Status: Active Grant

• Current Assignee: Nutanix Incorporated
• Original Assignee: Nutanix Incorporated
• Inventors: Aron, Mohit, Bhardwaj, Rishi, Guturi, Venkata Ranga Radhanikanth
• Primary Examiner(s): Bradley, Matthew
• Assistant Examiner(s): Goldschmidt, Craig
• Application Number:
  US13/207,357
• Time in Patent Office: 1,147 Days
• Field of Search: None
• US Class Current: 711/150
• CPC Class Codes: G06F 12/1466 Key-lock mechanism
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0665 at area level, e.g. provisioning of virtual or logical volumes
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0685 Hybrid storage combining heterogeneous device types, e.g. hierarchical storage, hybrid arrays
• CPC Class Codes: G06F 3/0689 Disk arrays, e.g. RAID, JBOD
• CPC Class Codes: G06F 9/52 Program synchronisation; Mutual exclusion, e.g. by means of semaphores

Abstract

Disclosed is an improved approach for using advanced metadata to implement an architecture for managing I/O operations and storage devices for a virtualization environment. According to some embodiments, a Service VM is employed to control and manage any type of storage device, including directly attached storage in addition to networked and cloud storage. The advanced metadata is used to track data within the storage devices. A lock-free approach is implemented in some embodiments to access and modify the metadata.

Claims

1. A method for performing lock free processing of metadata for storage devices in a virtualization system, comprising:

identifying metadata for the virtualization system, wherein the metadata comprises a first map corresponding to virtual disks, a second map corresponding to extent identifiers, and a third map corresponding to groups of extents;

using a processor to perform lock-free access of the metadata in a first order comprising first accessing the first map, then accessing the second map, followed by accessing the third map; and

performing lock-free modification of the metadata in a second order comprising first accessing the third map, then accessing the second map, followed by accessing the first map.

2. The method of claim 1 in which the first map corresponding to the virtual disks comprises a mapping between extents and a virtual disk address space.

3. The method of claim 2 in which the first map can be used to identify the extent identifier using a virtual disk identifier and an offset within the virtual disk.

4. The method of claim 1 in which the second map corresponding to the extent identifiers comprises a mapping between an extent identifier and an extent group identifier.

5. The method of claim 1 in which the third map corresponding to the groups of extents comprises a mapping between an extent group identifier and information regarding the extents associated with the extent group identifier.

6. The method of claim 1 in which the groups of extents comprises a file having multiple extents.

7. The method of claim 1 in which the third map comprises information pertaining to at least one of a disk identifier for an extent group, a list of extents in an extent group, replica information, or extent information.

8. The method of claim 7 in which the extent information comprises a reference count, a checksum, or an offset location.

9. The method of claim 1 in which an extent is de-duplicated, and the metadata comprises an indication of de-duplication for the extent.

10. The method of claim 9 in which an update to a virtual disk address space causes replacement of an existing extent with a replacement extent.

11. The method of claim 9 in which de-duplicated extents have the same extent identifier.

12. The method of claim 1 in which a reference count is maintained to indicate a number of references for an extent.

13. The method of claim 1 in which a non-deduplicated extent has an entry in the first map that identifies a corresponding extent group identifier, so that the second map does not need to be accessed to identify the corresponding extent group identifier.

14. The method of claim 1 further comprising the performance of garbage collection to remove extraneous or dangling items in the metadata.

15. The method of claim 1 in which a race condition is identified, and accessing of the metadata is restarted.

16. The method of claim 15 in which the race condition is identified because of an inconsistency in the metadata.

17. The method of claim 16 in which a check is made whether the inconsistency is resolved after the restart, wherein an error condition is identified if the inconsistency is not resolved.

18. The method of claim 1 in which an update operation to an item of metadata is performed such that the item is confirmed not to have been changed by another entity from start of the update operation to conclusion of the update operation.

19. The method of claim 18 in which a compare and swap procedure is performed to perform the update operation.

20. The method of claim 1 in which an intent to update an item of metadata is recorded, where the intent can be accessed by other operations.

21. A storage system comprising storage devices in a virtualization system, comprising:

a processor to handle computing instructions to access the storage devices; and

a computer readable medium comprising metadata for the virtualization system, wherein the metadata comprises a first map corresponding to virtual disks, a second map corresponding to extent identifiers, and a third map corresponding to groups of extents;

using the processor to perform lock-free access of the metadata in a first order comprising first accessing the first map, then accessing the second map, followed by accessing the third map; and

using the processor to perform lock-flee modification of the metadata in a second order comprising first accessing the third map, then accessing the second map, followed by accessing the first map.

22. The system of claim 21 in which the metadata is capable of being accessed without locks.

23. The system of claim 21 in which the first map corresponding to the virtual disks comprises a mapping between extents and a virtual disk address space.

24. The system of claim 23 in which the first map can be used to identify the extent identifier using a virtual disk identifier and an offset within the virtual disk.

25. The system of claim 21 in which the second map corresponding to the extent identifiers comprises a mapping between an extent identifier and an extent group identifier.

26. The system of claim 21 in which the third map corresponding to the groups of extents comprises a mapping between an extent group identifier and information regarding the extents associated with the extent group identifier.

27. The system of claim 21 in which the groups of extents comprises a file having multiple extents.

28. The system of claim 21 in which the third map comprises information pertaining to at least one of a disk identifier for an extent group, a list of extents in an extent group, replica information, or extent information.

29. The system of claim 28 in which the extent information comprises a reference count, a checksum, or an offset location.

30. The system of claim 21 in which an extent is de-duplicated, and the metadata comprises an indication of de-duplication for the extent.

31. The system of claim 30 in which an update to a virtual disk address space causes replacement of an existing extent with a replacement extent.

32. The system of claim 30 in which de-duplicated extents have the same extent identifier.

33. The system of claim 21 in which a reference count is maintained to indicate a number of references for an extent.

34. The system of claim 21 in which a non-deduplicated extent has an entry in the first map that identifies a corresponding extent group identifier, so that the second map does not need to be accessed to identify the corresponding extent group identifier.

35. A computer program product embodied on a non-transitory computer usable medium, the computer readable medium having stored thereon a sequence of instructions which, when executed by a processor causes the processor to execute a method for performing lock free processing of metadata for storage devices in a virtualization system, the method comprising:

identifying metadata for the virtualization system, wherein the metadata comprises a first map corresponding to virtual disks, a second map corresponding to extent identifiers, and a third map corresponding to groups of extents;

using a processor to perform lock-free access of the metadata in a first order comprising first accessing the first map, then accessing the second map, followed by accessing the third map; and

performing lock-free modification of the metadata in a second order comprising first accessing the third map, then accessing the second map, followed by accessing the first map.

36. The computer program product of claim 35 in which the first map corresponding to the virtual disks comprises a mapping between extents and a virtual disk address space.

37. The computer program product of claim 36 in which the first map can be used to identify the extent identifier using a virtual disk identifier and an offset within the virtual disk.

38. The computer program product of claim 35 in which the second map corresponding to the extent identifiers comprises a mapping between an extent identifier and an extent group identifier.

39. The computer program product of claim 35 in which the third map corresponding to the groups of extents comprises a mapping between an extent group identifier and information regarding the extents associated with the extent group identifier.

40. The computer program product of claim 35 in which the groups of extents comprises a file having multiple extents.

41. The computer program product of claim 35 in which the third map comprises information pertaining to at least one of a disk identifier for an extent group, a list of extents in an extent group, replica information, or extent information.

42. The computer program product of claim 41 in which the extent information comprises a reference count, a checksum, or an offset location.

43. The computer program product of claim 35 in which an extent is de-duplicated, and the metadata comprises an indication of de-duplication for the extent.

44. The computer program product of claim 43 in which an update to a virtual disk address space causes replacement of an existing extent with a replacement extent.

45. The computer program product of claim 43 in which de-duplicated extents have the same extent identifier.

46. The computer program product of claim 35 in which a reference count is maintained to indicate a number of references for an extent.

47. The computer program product of claim 35 in which a non-deduplicated extent has an entry in the first map that identifies a corresponding extent group identifier, so that the second map does not need to be accessed to identify the corresponding extent group identifier.

48. The computer program product of claim 35 further comprising the performance of garbage collection to remove extraneous or dangling items in the metadata.

49. The computer program product of claim 35 in which a race condition is identified, and accessing of the metadata is restarted.

50. The computer program product of claim 49 in which the race condition is identified because of an inconsistency in the metadata.

51. The computer program product of claim 50 in which a check is made whether the inconsistency is resolved after the restart, wherein an error condition is identified if the inconsistency is not resolved.

52. The computer program product of claim 35 in which an update operation to an item of metadata is performed such that the item is confirmed not to have been changed by another entity from start of the update operation to conclusion of the update operation.

53. The computer program product of claim 52 in which a compare and swap procedure is performed to perform the update operation.

54. The computer program product of claim 35 in which an intent to update an item of metadata is recorded, where the intent can be accessed by other operations.