Synchronization of storage using comparisons of fingerprints of blocks

• US 9,904,601 B2
• Filed: 06/24/2016
• Issued: 02/27/2018
• Est. Priority Date: 05/13/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Patterson, R. Hugo
• Primary Examiner(s): Mackes, Kris
• Assistant Examiner(s): Bui, Tiffany
• Application Number:
  US15/192,500
• Publication Number:
  US 20160306703A1
• Time in Patent Office: 613 Days
• Field of Search: 707639
• CPC Class Codes: G06F 11/1446 Point-in-time backing up or restoration of persistent data
• 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/00 Information retrieval; Database structures therefor; File system structures therefor
• 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/13 File access structures, e.g. distributed indices arrangements of input from, or output to, record carriers G06F3/06
• 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 17/00 Digital computing or data processing equipment or methods, specially adapted for specific functions information retrieval, database structures or file system structures therefor G06F16/00
• CPC Class Codes: G06F 2201/83 the solution involving signatures
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A system for processing data includes a data storage device and a processor. The data storage device stores a set of data. The processor is configured to divide the set of data in the data storage system into a set of segments; compute a set of fingerprints, wherein the set of fingerprints comprises a fingerprint for each segment of the set of segments; store the set of fingerprints in a new snapshot; identify a second set of fingerprints in the new snapshot that are not already in a fingerprint index; cause a second set of segments associated with the second set of fingerprints to be stored in a backup data storage system; and cause the second set of fingerprints to be added to the fingerprint index.

Claims

1. A system for processing data comprising:

a data storage device, wherein the data storage device stores a set of data; and

a processor is configured to;

divide the set of data in the data storage device into a set of segments;

compute a set of fingerprints, wherein the set of fingerprints comprises a fingerprint for each segment of the set of segments;

store the set of fingerprints in a new snapshot stored in the data storage device, wherein the new snapshot comprises an indication of the set of segments at a given point in time;

identify a second set of fingerprints in the new snapshot that are not already in a fingerprint index including comparing each fingerprint in the new snapshot with each fingerprint in the fingerprint index;

cause a second set of segments associated with the second set of fingerprints to be stored in a backup data storage system;

cause the second set of fingerprints to be added to the fingerprint index;

identify a third set of fingerprints in the new snapshot that are not found in a list of fingerprints in a target snapshot;

delete a first subset of data stored in the data storage device, wherein the first subset of data are associated with the third set of fingerprints;

retrieve a second subset of data from the backup data storage system, wherein the second subset of data are associated with fingerprints that are found in the list of fingerprints in the target snapshot; and

insert the second subset of data into appropriate locations in the data storage device.

2. The system as in claim 1, wherein the data storage device for storing data comprises a block storage system.

3. The system as in claim 1, wherein the backup data storage system comprises a deduplicating storage system.

4. The system as in claim 1, wherein a block is associated with one or more segments of the set of segments.

5. The system as in claim 4, wherein the block is restored by reading the one or more segments from the backup data storage system and used to reconstruct the block.

6. The system as in claim 5, wherein the processor is further configured to transfer the one or more segments from the backup data storage system to the data storage device.

7. The system as in claim 6, wherein transferring the one or more segments comprises transferring the one or more segments requested by a user.

8. The system as in claim 1, wherein the new snapshot is one of a plurality of snapshots.

9. The system as in claim 1, wherein the new snapshot is associated with a snapshot time.

10. A method for processing data, comprising:

dividing a set of data in a data storage device into a set of segments;

computing, using a processor, a set of fingerprints, wherein the set of fingerprints comprises a fingerprint for each segment of the set of segments;

storing the set of fingerprints in a new snapshot stored in the data storage device, wherein the new snapshot comprises an indication of the set of segments at a given point in time;

identifying a second set of fingerprints in the new snapshot that are not already in a fingerprint index including comparing each fingerprint in the new snapshot with each fingerprint in the fingerprint index;

causing a second set of segments associated with the second set of fingerprints to be stored in a backup data storage system;

causing the second set of fingerprints to be added to the fingerprint index;

identifying a third set of fingerprints in the new snapshot that are not found in a list of fingerprints in a target snapshot;

deleting a first subset of data stored in the data storage device, wherein the first subset of data are associated with the third set of fingerprints;

retrieving a second subset of data from the backup data storage system, wherein the second subset of data are associated with fingerprints that are found in the list of fingerprints in the target snapshot; and

inserting the second subset of data into appropriate locations in the data storage device.

11. The method as in claim 10, wherein the data storage device for storing data comprises a block storage system.

12. The method as in claim 10, wherein the backup data storage system comprises a deduplicating storage system.

13. The method as in claim 10, wherein a block is associated with one or more segments of the set of segments.

14. The method as in claim 13, wherein the block is restored by reading the one or more segments from the backup data storage system and used to reconstruct the block.

15. The method as in claim 14, further comprising transferring the one or more segments from the backup data storage system to the data storage device.

16. The method as in claim 15, wherein transferring the one or more segments comprises transferring the one or more segments requested by a user.

17. The method as in claim 10, wherein the new snapshot is one of a plurality of snapshots.

18. The method as in claim 10, wherein the new snapshot is associated with a snapshot time.

19. A computer program product for processing data, the computer program product being embodied in a non-transitory computer readable storage medium and comprising computer instructions for:

dividing a set of data in a data storage device into a set of segments;

computing, using a processor, a set of fingerprints, wherein the set of fingerprints comprises a fingerprint for each segment of the set of segments;

storing the set of fingerprints in a new snapshot stored in the data storage device, wherein the new snapshot comprises an indication of the set of segments at a given point in time;

identifying a second set of fingerprints in the new snapshot that are not already in a fingerprint index including comparing each fingerprint in the new snapshot with each fingerprint in the fingerprint index;

causing a second set of segments associated with the second set of fingerprints to be stored in a backup data storage system;

causing the second set of fingerprints to be added to the fingerprint index;

identifying a third set of fingerprints in the new snapshot that are not found in a list of fingerprints in a target snapshot;

deleting a first subset of data stored in the data storage device, wherein the first subset of data are associated with the third set of fingerprints;

retrieving a second subset of data from the backup data storage system, wherein the second subset of data are associated with fingerprints that are found in the list of fingerprints in the target snapshot; and

inserting the second subset of data into appropriate locations in the data storage device.