Providing snapshots of virtual storage devices

• US 8,966,198 B1
• Filed: 09/04/2012
• Issued: 02/24/2015
• Est. Priority Date: 09/01/2011
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Kadatch, Andrew, Khorun, Sergey, Harris, Matthew S., Hamilton, Carl
• Primary Examiner(s): Choe, Yong
• Application Number:
  US13/602,974
• Time in Patent Office: 903 Days
• Field of Search: 711/103, 711/161, 711/E12.059
• US Class Current: 711/161
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1469 Backup restoration techniques
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 2201/815 Virtual
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/0664 at device level, e.g. emulation of a storage device or system
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

In general, one aspect of the subject matter described in this specification can be embodied in methods that include receiving, at a computer system, a request to create a snapshot of a virtual storage device, wherein the virtual storage device virtually stores data at virtual addresses, the data being physically stored at a plurality of physical storage locations that are managed by an underlying storage system associated with virtual storage device; the methods can further include identifying, by the computer system, one or more regions of the virtual storage device that have been written to since a previous snapshot of the virtual storage device was created; the methods can additionally include generating a unique identifier for the requested snapshot; and creating the requested snapshot using the identified one more regions and the unique identifier.

Claims

1. A method comprising:

receiving, at a computer system, a request to create a snapshot of a virtual storage device, wherein the virtual storage device virtually stores data at virtual addresses, the data being physically stored at a plurality of physical storage locations that are managed by an underlying storage system associated with virtual storage device, the plurality of physical storage locations being associated with physical addresses and being distributed across a plurality of physical storage devices, the underlying storage system managing storage of the data across the plurality of physical storage devices using unique identifiers that are;

i) independent of the plurality of physical storage devices and the plurality of physical storage locations and ii) different from the virtual addresses;

identifying, by the computer system, one or more regions of the virtual storage device that have been written to since a previous snapshot of the virtual storage device was created, wherein data written to the one or more identified regions is stored in the plurality of physical storage locations separately from other stored data that corresponds to other snapshots of the one or more regions;

generating a unique identifier for the requested snapshot; and

creating the requested snapshot using the identified one more regions and the unique identifier, wherein the requested snapshot includes a mapping of the unique identifier to the one or more identified regions of the virtual storage device and does not include any data stored in the virtual storage device.

2. The method of claim 1, further comprising:

receiving a request to write new data to a first region of the virtual storage device, wherein the first region is indicated in the previous snapshot as storing previous data at a first physical storage location of the underlying storage system;

allocating a second physical storage location of the underlying storage system to store the new data in association with the first region of the virtual storage device; and

writing the new data to the second physical storage location.

3. The method of claim 2, wherein the request to write the new data to the first region is received before the request to create the snapshot and after the previous snapshot of the virtual storage device was created, and wherein the one or more identified regions includes the first region.

4. The method of claim 1, further comprising:

after creating the snapshot, receiving a request to access the created snapshot of the virtual storage device;

retrieving the one or more identified regions using the mapping for the created snapshot;

identifying and retrieving most recent versions of other regions of the virtual storage device that are not included in the mapping of the created snapshot, wherein the most recent versions of the other regions are identified using other snapshots of the virtual storage device; and

providing access to the created snapshot using the retrieved one or more identified regions and the most recent versions of the other regions of the virtual storage device.

5. The method of claim 1, further comprising:

receiving a request to delete the previous snapshot of the virtual storage device;

determining whether the previous snapshot includes at least one other region of the virtual storage device that is not included in the mapping; and

when the previous snapshot is determined to include the at least one other region, marking the previous snapshot for deletion at a later time when a new snapshot includes the at least one region.

6. The method of claim 1, wherein the unique identifier comprises a timestamp.

7. The method of claim 1, wherein the mapping includes meta-information that encodes first information identifying the one or more regions and second information to access the data written to the one or more regions from the underlying storage system.

8. A system comprising:

a computer system;

an interface of the computer system to receive a request to create a snapshot of a virtual storage device, wherein the virtual storage device virtually stores data at virtual addresses, the data being physically stored at a plurality of physical storage locations that are managed by an underlying storage system associated with virtual storage device, the plurality of physical storage locations being associated with physical addresses and being distributed across a plurality of physical storage devices, the underlying storage system managing storage of the data across the plurality of physical storage devices using unique identifiers that are;

i) independent of the plurality of physical storage devices and the plurality of physical storage locations and ii) different from the virtual addresses;

a snapshot manager of the computer system to identify one or more regions of the virtual storage device that have been written to since a previous snapshot of the virtual storage device was created, wherein data written to the one or more identified regions is stored in the plurality of physical storage locations separately from other stored data that corresponds to other snapshots of the one or more regions;

a snapshot generator of the computer system i) to generate a unique identifier for the requested snapshot, and ii) to create the requested snapshot using the identified one more regions and the unique identifier, wherein the requested snapshot includes a mapping of the unique identifier to the one or more identified regions of the virtual storage device and does not include any data stored in the virtual storage device.

9. The system of claim 8, wherein the interface is further configured to receive a request to write new data to a first region of the virtual storage device, wherein the first region is indicated in the previous snapshot as storing previous data at a first physical storage location of the underlying storage system;

and

wherein the snapshot manager is further configured to allocate a second physical storage location of the underlying storage system to store the new data in association with the first region of the virtual storage device; and

to write the new data to the second physical storage location.

10. The system of claim 9, wherein the request to write the new data to the first region is received before the request to create the snapshot and after the previous snapshot of the virtual storage device was created, and wherein the one or more identified regions includes the first region.

11. The system of claim 8, wherein the interface is further configured to receive a request to access the created snapshot of the virtual storage device after creating the snapshot;

and

the system further comprising a snapshot recreation module i) to retrieve the one or more identified regions using the mapping for the created snapshot, ii) to identify and retrieve most recent versions of other regions of the virtual storage device that are not included in the mapping of the created snapshot, wherein the most recent versions of the other regions are identified using other snapshots of the virtual storage device, and iii) to provide access to the created snapshot using the retrieved one or more identified regions and the most recent versions of the other regions of the virtual storage device.

12. The system of claim 8, wherein the interface is further configured to receive a request to delete the previous snapshot of the virtual storage device;

the system further comprising a snapshot deletion manager i) to determine whether the previous snapshot includes at least one other region of the virtual storage device that is not included in the mapping, and ii) when the previous snapshot is determined to include the at least one other region, to mark the previous snapshot for deletion at a later time when a new snapshot includes the at least one region.

13. The system of claim 8, wherein the unique identifier comprises a timestamp.

14. The system of claim 8, wherein the mapping includes meta-information that encodes first information identifying the one or more regions and second information to access the data written to the one or more regions from the underlying storage system.

15. A computer program product tangibly embodied on a computer readable medium, the computer program product including instructions that, when executed, cause a computing device to perform operations comprising:

receiving a request to create a snapshot of a virtual storage device wherein the virtual storage device virtually stores data at virtual addresses, the data being physically stored at a plurality of physical storage locations that are managed by an underlying storage system associated with virtual storage device, the plurality of physical storage locations being associated with physical addresses and being distributed across a plurality of physical storage devices, the underlying storage system managing storage of the data across the plurality of physical storage devices using unique identifiers that are;

i) independent of the plurality of physical storage devices and the plurality of physical storage locations and ii) different from the virtual addresses;

identifying one or more regions of the virtual storage device that have been written to since a previous snapshot of the virtual storage device was created, wherein data written to the one or more identified regions is stored in the plurality of physical storage locations separately from other stored data that corresponds to other snapshots of the one or more regions;

generating a unique identifier for the requested snapshot; and

creating the requested snapshot using the identified one more regions and the unique identifier, wherein the requested snapshot includes a mapping of the unique identifier to the one or more identified regions of the virtual storage device and does not include any data stored in the virtual storage device.

16. The computer program product of claim 15, wherein the operations further comprise:

receiving a request to write new data to a first region of the virtual storage device, wherein the first region is indicated in the previous snapshot as storing previous data at a first physical storage location of the underlying storage system;

allocating a second physical storage location of the underlying storage system to store the new data in association with the first region of the virtual storage device; and

writing the new data to the second physical storage location.

17. The computer program product of claim 16, wherein the request to write the new data to the first region is received before the request to create the snapshot and after the previous snapshot of the virtual storage device was created, and wherein the one or more identified regions includes the first region.

18. The computer program product of claim 15, wherein the operations further comprise:

after creating the snapshot, receiving a request to access the created snapshot of the virtual storage device;

retrieving the one or more identified regions using the mapping for the created snapshot;

identifying and retrieving most recent versions of other regions of the virtual storage device that are not included in the mapping of the created snapshot, wherein the most recent versions of the other regions are identified using other snapshots of the virtual storage device; and

providing access to the created snapshot using the retrieved one or more identified regions and the most recent versions of the other regions of the virtual storage device.

19. The computer program product of claim 15, wherein the operations further comprise:

receiving a request to delete the previous snapshot of the virtual storage device;

determining whether the previous snapshot includes at least one other region of the virtual storage device that is not included in the mapping; and

when the previous snapshot is determined to include the at least one other region, marking the previous snapshot for deletion at a later time when a new snapshot includes the at least one region.

20. The computer program product of claim 15, wherein the unique identifier comprises a timestamp.

21. The computer program product of claim 15, wherein the mapping includes meta-information that encodes first information identifying the one or more regions and second information to access the data written to the one or more regions from the underlying storage system.