Method and apparatus for reducing redundant storing of blocks of data on a server

• US 8,176,015 B1
• Filed: 06/14/2004
• Issued: 05/08/2012
• Est. Priority Date: 06/14/2004
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Operating Corporation (Gen Digital Inc.)
• Inventors: Somerville, Robert
• Primary Examiner(s): LY, CHEYNE D
• Application Number:
  US10/867,611
• Time in Patent Office: 2,885 Days
• Field of Search: 707/100, 707/661
• US Class Current: 707/661
• 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/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/00 Information retrieval; Database structures therefor; File system structures therefor
• CPC Class Codes: G06F 16/1752 based on file chunks
• CPC Class Codes: G06F 21/565 by checking file integrity

Abstract

A method and apparatus for selectively storing data on a server. The method operates by accessing a computer file and defining a data block as a current block of data. The current block is subsequently checksummed using a rolling error identification code. The method then determines if the calculated checksum for the current block has been previously stored in a database. If a matching checksum for the data is found in the database, then a duplicate of the current block already exists and the process repeats by selecting a new block of data. Alternatively, if the calculated checksum is absent from the checksum and the process has advanced one block length, the process moves back one block length and stores the current block in an archive. Otherwise, the checksum advances one byte forward to form a new current block of data and the process repeats.

Claims

1. A method for selectively storing blocks of data, comprising:

(a) accessing a computer file comprising a plurality of bytes of data;

(b) defining a block of data as a current block, wherein the block of data comprises the plurality of bytes;

(c) calculating a checksum from a rolling error identification code for the current block;

(d) identifying that the checksum does not exist in a database;

(e) determining whether the method has advanced one block length through the computer file;

(f) if the method has advanced one block length through the computer file, moving back one block length to form a unique block of data, defining the unique block of data as the current block, and storing the current block into an archive file; and

(g) otherwise, advancing one byte to form a new block of data, defining the new block of data as the current block, and returning to step (c).

2. The method of claim 1, wherein step (f) further comprises:

calculating a verification value for the current block, adding the verification value and the checksum of the current block to the database.

3. The method of claim 1, wherein the rolling error identification code is a rolling cyclic redundancy check.

4. The method of claim 2, wherein the verification value is produced by a message digest algorithm.

5. The method of claim 4, wherein the message digest algorithm is a MD5 algorithm.

6. The method of claim 4, wherein the verification value comprises at least one of a MD4, MD5 and SHA-1 signature.

7. The method of claim 1, wherein the computer file is an image file.

8. The method of claim 1, wherein the checksum from the rolling error identification code is stored in the database.

9. The method of claim 1, wherein the step of advancing one byte further comprises:

dropping a last byte from the current block and adding a new byte to the beginning of the current block, thereby forming a new block of data.

10. A method for reducing redundant storing of blocks of data, comprising:

(a) accessing a computer file comprising a plurality of bytes of data;

(b) defining a block of data as a current block, wherein the block of data comprises the plurality of bytes;

(c) calculating a verification value for the current block;

(d) determining if the verification value for the current block is stored in a database;

(e) if the verification value is absent from the database, advancing one byte to form a new block of data, defining the new block of data as the current block, and returning to step (c); and

,

(f) otherwise, incrementing a reference count in the database, selecting an original block of data, defining the original block of data as the current block, and returning to step (c).

11. The method of claim 10, wherein the step (b) further comprises:

(g) calculating a checksum from a rolling error identification code for the current block;

(h) determining if the checksum for the current block is stored in the database;

(i) if the checksum is absent from the database, determining whether the method has advanced one block length through the computer file;

(j) if the method has advanced one block length through the computer file, moving back one block length to form a unique block of data, defining the unique block of data as the current block, and storing the current block into an archive; and

(k) otherwise, advancing one byte to form a new block of data, defining the new block of data as the current block, and returning to step (c).

12. The method of claim 11, wherein the rolling error identification code is a rolling cyclic redundancy check.

13. The method of claim 10, wherein the verification value is produced by a message digest algorithm.

14. The method of claim 13, wherein the message digest algorithm is a MD5 algorithm.

15. The method of claim 14, wherein the verification value comprises at least one of a MD4, MD5 and SHA-1 signature.

16. The method of claim 10, wherein the computer file is an image file.

17. The method of claim 11, wherein the step of advancing one byte further comprises:

dropping off a last byte from the current block and adding one byte to the beginning of the current block, thereby forming a new block of data.

18. The method of claim 10, wherein the original block of data is a next consecutive block of data.

19. An apparatus for selectively storing blocks of data to a backup server comprising:

means for accessing a computer file comprising a plurality of bytes of data;

means for defining a block of data as a current block;

means for calculating a checksum from a rolling error identification code for the current block;

means for determining if the checksum for the current block is stored in a database;

means for determining whether one block length has been advanced in the computer file;

means for moving back one block length to form a unique block of data, defining the unique block of data as the current block, and storing the current block in an archive file, in response to the block length having been advanced in the computer file; and

means for advancing one byte to form a new block of data and defining the new block of data as the current block in response to the block length not having been advanced in the computer file.

20. The apparatus of claim 19 further comprising:

means for calculating a verification value for the current block;

means for adding a verification block to the database;

means for determining whether the verification value is present in the database; and

means for incrementing a reference count in the database in response to the presence of the verification value of the current block in the database.