System and method for backing up data

• US 9,032,171 B2
• Filed: 02/04/2013
• Issued: 05/12/2015
• Est. Priority Date: 01/22/2003
• Status: Active Grant

• Current Assignee: FalconStor, Inc (Hale Capital Management LP)
• Original Assignee: FalconStor, Inc (Hale Capital Management LP)
• Inventors: Lam, Wai T., Niles, Roland S.
• Primary Examiner(s): SONG, HUA JASMINE
• Application Number:
  US13/758,705
• Publication Number:
  US 20130151472A1
• Time in Patent Office: 827 Days
• Field of Search: 711161-162, 707/640, 707646-647
• US Class Current: 711/162
• CPC Class Codes: G02B 15/04 by changing a part
• CPC Class Codes: G02B 26/004 based on a displacement or a deformation of a fluid
• CPC Class Codes: G02B 27/646 compensating for small deviations, e.g. due to vibration or shake movement of one or more optical elements for control of motion blur in cameras, projectors or printers G03B2205/0007; image stabilisation in cameras peculiar to the presence or use of an electronic image sensor H04N23/68
• CPC Class Codes: G02B 7/102 controlled by a microcomputer cameras with interchangeable lenses G03B17/14
• CPC Class Codes: G03B 17/17 with reflectors arranged in beam forming the photographic image, e.g. for reducing dimensions of camera
• CPC Class Codes: G03B 2205/0046 Movement of one or more optical elements for zooming
• CPC Class Codes: G03B 2205/0069 using electromagnetic actuators, e.g. voice coils
• CPC Class Codes: G03B 3/10 Power-operated focusing
• CPC Class Codes: G03B 5/00 Adjustment of optical system relative to image or object surface other than for focusing
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: G06F 16/11 File system administration, e.g. details of archiving or snapshots file system backup G06F11/14
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/951 Indexing; Web crawling techniques
• CPC Class Codes: G06F 21/56 Computer malware detection or handling, e.g. anti-virus arrangements
• CPC Class Codes: G06F 21/564 by virus signature recognition
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: G06Q 20/4012 Verifying personal identification numbers [PIN]
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity
• CPC Class Codes: H04L 63/145 : the attack involving the propagation of malware through the network, e.g. viruses, trojans or worms
• CPC Class Codes: H04L 9/0643 : Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: Y10S 707/99953 : Recoverability
• CPC Class Codes: Y10S 707/99955 : Archiving or backup

Abstract

A hash-optimized backup system and method takes data blocks and generates a probabilistically unique digital fingerprint of the content of each data block using a substantially collision-free algorithm. The process compares the generated fingerprint to a database of stored fingerprints and, if the generated fingerprint matches a stored fingerprint, the data block is determined to already have been backed up, and therefore does not need to be backed up again. Only if the generated fingerprint does not match a stored fingerprint is the data block backed up, at which point the generated fingerprint is added to the database of stored fingerprints. Because the algorithm is substantially collision-free, there is no need to compare actual data content if there is a hash-value match. The process can also be used to audit software license compliance, inventory software, and detect computer-file tampering such as viruses and malware.

Claims

1. A method for backing up a data block having a data block location, the method comprising:

comparing a digital fingerprint of a data block in a data block location in a first storage device to digital fingerprints stored in a database in a second storage separate from the first storage device, by at least one processing device; and

if the digital fingerprint does not match one of the stored digital fingerprints, backing up the data block in a third storage separate from the first storage device and adding to the database the digital fingerprint and the data block location, by the at least one processing device.

2. The method of claim 1, comprising:

if the digital fingerprint matches one of the stored digital fingerprints, updating the database to associate the digital fingerprint with the data block location.

3. The method of claim 1, comprising:

if the digital fingerprint matches one of the stored fingerprints, updating a set of recorded locations stored in association with the one stored digital fingerprint to include the data block location, each recorded location representing a respective location of the data block.

4. The method of claim 1, comprising:

generating the digital fingerprint by the at least one processing device.

5. The method of claim 4, comprising:

generating the digital fingerprint by a source computer including at least one processing device.

6. The method of claim 4, comprising:

generating the digital fingerprint by a backup server.

7. The method of claim 6, comprising:

generating the digital fingerprint by the backup server by a substantially collision free algorithm.

8. The method of claim 1, comprising generating the digital fingerprint by a substantially collision free algorithm.

9. The method of claim 8, wherein the algorithm comprises a hash function.

10. The method of claim 9, wherein the hash function is MD5 or SHA-1.

11. The method of claim 1, wherein the second storage and third storage are part of the same storage device.

12. The method of claim 1, wherein the processing device is part of a backup server.

13. A system for backing up a data block having a data block location in a first storage device, the system comprising:

a backup server;

second storage separate from the first storage device, the second storage defining a digital fingerprint database;

the backup server being configured to;

compare a digital fingerprint of a data block in the first storage device to digital fingerprints in the digital fingerprint database;

back up the data block in third storage, if the digital fingerprint of the data block does not match any digital fingerprint stored in the database; and

add to the database the digital fingerprint and the data block location in the first storage device, if the digital fingerprint does not match any digital fingerprint stored in the database.

14. The system according to claim 13, wherein the data block has a location in the first storage device and if the digital fingerprint matches a digital fingerprint stored in the database, the backup server updates the database to associate the digital fingerprint with the data block location.

15. The system according to claim 13, wherein the second storage is connected to the backup server.

16. The system according to claim 13, wherein the third storage is connected to the backup server.

17. The system of claim 13, wherein the second storage and the third storage are on the same storage device.

18. The system of claim 13, wherein the backup server is configured to generate the digital fingerprint by a substantially collision free algorithm.

19. The system of claim 13, further comprising:

a source computer coupled to the backup computer via a communication path, wherein the source computer is configured to generate the digital fingerprint of the data block by a substantially collision free algorithm.

20. The system according to claim 19, wherein:

the communication path comprises a network.

21. The system according to claim 20, wherein the network comprises a local area network, a wide area network, or the Internet.

22. A system for backing up a data block having a data block location, the system comprising:

means for comparing a digital fingerprint of a data block in a first storage device to digital fingerprints of backed up data blocks stored in a database in a second storage device; and

means for backing up the data block and adding to the database the digital fingerprint and the data block location in a third storage separate from the first storage device, if the digital fingerprint does not match one of the stored digital fingerprints.

23. A system for backing up a data block, comprising

first storage to store a digital fingerprint database;

at least one processing device having access to the digital fingerprint database, the at least one processing device being configured to;

compare a digital fingerprint of a data block stored in second storage separate from the first storage, to digital fingerprints stored in the digital fingerprint database;

back up the data block to third storage separate from the second storage; and

if the digital fingerprint of the data block does not match a digital fingerprint in the digital fingerprint database;

add the fingerprint to the digital fingerprint database; and

add a location of the data block in the second storage to the digital fingerprint database.

24. The system of claim 23, further comprising at least one second processing device configured to generate the digital fingerprint of the data block by a substantially collision free algorithm.

25. The system of claim 23, further comprising:

a source computer coupled to at least one processing device via a communication path;

wherein;

the second storage is associated with the source computer; and

the second processing device is part of the source computer.

26. The system of claim 23, wherein the second storage comprises local storage of the source computer.

30. The system of claim 23, wherein the first storage device and the third storage device are the same.

27. The system of 23, further comprising:

a backup server;

wherein at least one first processing device is part of the backup server.

28. The system of claim 27, wherein the at least one first processing device generates the digital fingerprint via an agent that accesses the second storage device via a communication path.

29. The system of claim 28, wherein the communication path comprises a network.