Hash-based snapshots

• US 9,239,841 B2
• Filed: 07/16/2013
• Issued: 01/19/2016
• Est. Priority Date: 07/16/2013
• Status: Active Grant

• Current Assignee: Vmware LLC (Broadcom, Inc.)
• Original Assignee: VMware, Inc. (Broadcom, Inc.)
• Inventors: Arnaudov, Antoan, Tomov, Rosen
• Primary Examiner(s): OBISESAN, AUGUSTINE KUNLE
• Application Number:
  US13/943,717
• Publication Number:
  US 20150026132A1
• Time in Patent Office: 917 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• 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/137 Hash-based content-based indexing of textual data G06F16/31
• 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

Abstract

Methods and systems configured to provide hash-based snapshot services for a virtual storage are provided. The system includes a processor and memory coupled with the processor. The memory is configured to provide the processor with instructions for maintaining, by a hash-based snapshot module executing on the system, a file system of the virtual storage. The file system is associated with a plurality of data blocks. The virtual storage is supported by a hash-storage having a hash base-file and a hash-database. The hash-database is configured for storing the plurality of data blocks. And the hash base-file includes hash codes generated by applying a hash function to the plurality of data blocks. The memory is further configured to provide the processor with instructions for accessing, by the hash-based snapshot module, the file system using hash codes contained in the hash base-file to identify data blocks stored in the hash-database; creating, by the hash-based snapshot module, a first snapshot for the file system, wherein the first snapshot is associated with a first hash snapshot file copied based on the hash base-file; and accessing, by the hash-based snapshot module, the first snapshot using hash codes contained in the first hash snapshot file to identify data blocks stored in the hash-database.

Claims

1. A system configured to provide hash-based snapshot services for a virtual storage, the system comprising a processor and memory coupled with the processor, wherein the memory is configured to provide the processor with instructions for

maintaining, by a hash-based snapshot module executing on the system, a file system of the virtual storage, wherein the file system is associated with a plurality of data blocks, the virtual storage is supported by a hash-storage having a hash base-file and a hash-database, the hash-database is configured for storing the plurality of data blocks, and the hash base-file includes hash codes generated by applying a hash function to the plurality of data blocks;

accessing, by the hash-based snapshot module, the file system using hash codes contained in the hash base-file to identify corresponding data blocks stored in the hash-database;

creating, by the hash-based snapshot module, a first snapshot for the file system, wherein the first snapshot is associated with a first hash snapshot file copied based on the hash base-file wherein the first hash snapshot file contains a first plurality of hash entities each of which is associated with a corresponding one of the plurality of data blocks;

accessing, by the hash-based snapshot module, the first snapshot using hash codes contained in the first hash snapshot file to identify corresponding data blocks stored in the hash-database;

in response to a read request to retrieve a first data block from the first snapshot locating a first hash entity from the first plurality of hash entities based on the first data block'"'"'s address and locating the first data block in the hash-database based on a first hash code and a first collision count retrieved from the first hash entity; and

in response to an update request to write a second data block to the first snapshot, locating a second hash entity from the first plurality of hash entities based on the second data block'"'"'s address, generating a second hash code for the second hash entity by applying the hash function to the second data block'"'"'s data, generating a second collision count for the second hash entity based on a number of data blocks stored in the hash-database having corresponding hash codes that are identical to the second hash code and storing the second data block along with the second hash code and the second collision count in the hash-database.

2. The system of claim 1, wherein accessing the first snapshot further comprises:

storing a reference count with the second data block in the hash-database, wherein the reference count is generated based on a number of data blocks stored in the hash-database that have identical data as the second data block.

3. The system of claim 1, wherein the hash-database contains a plurality of hash data blocks, and creating the first snapshot comprises:

for each hash data block in the plurality of hash data blocks that is referenced by one of the first plurality of hash entities, incrementing the hash data block'"'"'s associated reference count by one.

4. The system of claim 1, wherein the memory is further configured to provide the processor with instructions for creating a second snapshot based on the first snapshot, wherein the second snapshot is associated with a second hash snapshot file copied based on the first hash snapshot file;

and accessing the second snapshot using hash codes contained in the second hash snapshot file to identify corresponding data blocks stored in the hash-database.

5. The system of claim 4, wherein the second hash snapshot file contains a second plurality of hash entities, the hash-database contains a plurality of hash data blocks, and creating the second snapshot comprises:

for each hash data block in the plurality of hash data blocks that is referenced by one of the second plurality of hash entities, incrementing the hash data block'"'"'s associated reference count by one.

6. The system of claim 4, wherein the second hash snapshot file contains a second plurality of hash entities, the hash-database contains a plurality of hash data blocks, and the memory is further configured to

provide the processor with instructions for deleting the second snapshot by removing the second hash snapshot file;

and

for each hash data block in the plurality of hash data blocks that is referenced by one of the second plurality of hash entities, reducing the hash data block'"'"'s associated reference count by one.

7. The system of claim 4, wherein the first hash snapshot file contains a first plurality of hash entities, the hash-database contains a plurality of hash data blocks, and the memory is further configured to

provide the processor with instructions for collapsing the first snapshot by replacing the first hash snapshot file with the second hash snapshot file;

for each hash data block in the plurality of hash data blocks that is referenced by one of the first plurality of hash entities, reducing the hash data block'"'"'s associated reference count by one; and

accessing the first snapshot via the replaced first hash snapshot file.

8. The system of claim 1, wherein the hash base-file contains a plurality of hash entities, the hash-database contains a plurality of hash data blocks, and the memory is further configured to

provide the processor with instructions for collapsing the hash-storage by replacing the hash base-file with the first hash snapshot file;

for each hash data block in the plurality of hash data blocks that is referenced by one of the plurality of hash entities,

reducing the hash data block'"'"'s associated reference count by one; and

accessing the file system via the replaced hash base-file.

9. A system configured to provide hash-based snapshot services for a virtual storage, the system comprising a processor and memory coupled with the processor, and the system further comprising:

a hash-based snapshot module coupled with the processor and the memory, wherein the hash-based snapshot module is configured to maintain a file system located in the virtual storage, and the file system is associated with a plurality of data blocks; and

a hash-storage coupled with the hash-based snapshot module and configured for storing a hash base-file and a hash-database, wherein the hash-database is configured for storing the plurality of data blocks, and the hash base-file includes hash codes generated by applying a hash function to the plurality of data blocks,

wherein the hash-based snapshot module is further configured to access the file system using hash codes contained in the hash base-file to identify corresponding data blocks stored in the hash-database, create a snapshot for the file system by copying the hash base-file to a hash snapshot file wherein the hash snapshot file is configured with a plurality of hash entities each of which is associated with a corresponding one of the plurality of data blocks, store the hash snapshot file to the hash-storage wherein the hash-storage is configured with a plurality of hash data blocks and access the snapshot using hash codes contained in the hash snapshot file to identify corresponding data blocks stored in the hash-database,

wherein, in response to a read request to retrieve a first data block from the snapshot, the hash-based snapshot module is further configured to locate a first hash entity from the plurality of hash entities based on the first data block'"'"'s address, locate a first hash data block from the plurality of hash data blocks based on a first hash code and a first collision count stored in the first hash entity, wherein the first hash code is generated by applying the hash function to the first data block'"'"'s data, and retrieve the first data block from the first hash data block.

10. The system as recited in claim 9, wherein

in response to an update request to write a second data block to the first snapshot, the hash-based snapshot module is further configured to

locate a second hash entity from the plurality of hash entities based on the second data block'"'"'s address,

generate a second hash code for the second hash entity by applying the hash function to the second data block'"'"'s data,

locate a second hash data block from the plurality of hash data blocks based on the second hash code, and

store the second hash code and the second data block in the second hash data block.

11. The system as recited in claim 10, wherein the hash-based snapshot module is further configured to

generate a collision count for the second hash entity by incrementing by one a number of hash data blocks in the hash-database having corresponding hash codes that are identical to the second hash code, wherein the second hash code and the collision count are configured for uniquely identifying the second data block'"'"'s data;

and

store the collision count in the second hash data block.

12. The system as recited in claim 11, wherein the hash-based snapshot module is further configured to

increment a reference count for the second hash data block, wherein the reference count is configured for counting a number of times the hash data block is referenced by the plurality of data blocks and by one or more snapshots.

13. A non-transitory computer-readable storage medium, containing a set of instructions which, when executed by a processor, cause the processor to perform a method for providing hash-based snapshot services for a virtual storage, the method comprising:

maintaining, by a hash-based snapshot module executing on the system, a file system located in the virtual storage, wherein

the file system is associated with a plurality of data blocks,

the virtual storage is supported by a hash-storage having a hash base-file and a hash-database,

the hash-database is configured for storing the plurality of data blocks, and

the hash base-file is configured for accessing the stored plurality of data blocks in the hash-database based on hash codes generated by applying a hash function to the plurality of data blocks;

creating, by the hash-based snapshot module, a first snapshot for the file system by copying the hash base-file to a first hash snapshot file and storing the first hash snapshot file to the hash-storage;

accessing, by the hash-based snapshot module, the first snapshot via the first hash snapshot file;

creating a second snapshot based on the first snapshot by copying the first hash snapshot file to a second hash snapshot file and storing the second hash snapshot file to the hash-storage; and

accessing the second snapshot via the second hash snapshot file.

14. The non-transitory computer-readable storage medium as recited in claim 13, wherein the method further comprises:

collapsing the first snapshot by replacing the first hash snapshot file with the second hash snapshot file; and

accessing the first snapshot via the replaced first hash snapshot file.

15. The non-transitory computer-readable storage medium as recited in claim 13, wherein the method further comprises:

collapsing the hash-storage by replacing the hash base-file with the first hash snapshot file; and

accessing the file system via the replaced hash base-file.