Method, system, and program for personal data management using content-based replication

• US 8,341,117 B2
• Filed: 11/18/2008
• Issued: 12/25/2012
• Est. Priority Date: 08/26/2003
• Status: Active Grant

• Current Assignee: JP Morgan Chase Bank, N.A. (JP Morgan Chase & Co)
• Original Assignee: Arkeia Software, Inc. (Western Digital Corporation)
• Inventors: Ram, Tamir, Kubo, Lawrence Hiroshi
• Primary Examiner(s): NGUYEN, MERILYN P
• Application Number:
  US12/273,339
• Publication Number:
  US 20090265396A1
• Time in Patent Office: 1,498 Days
• Field of Search: 707/690, 707/695, 707/697, 707/698, 707/699, 707/610, 707/625, 707/638, 707/639, 707/640, 707/692
• US Class Current: 707/625
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• 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 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

Provided herein are data management systems and methods for storing, cataloging, and protecting data on a computer using software and a portable data storage device. The technology can back up, manage, and protect data for any operating or file system by checking files for block-level or byte-level changes and storing only new data. By storing only new data and cataloging information within a comprehensive backup archive composed of these blocks, the size of each backup is minimized.

Claims

1. A system for managing data, said system comprising:

a processor, said processor configured to perform;

a) receiving data from a data source;

b) generating a data block from the data;

c) generating a data block checksum of the data block;

d) comparing the data block checksum to a collection of stored data block checksums of a collection of stored data blocks, wherein the data source comprises a plurality of files and a stored data block is shared by more than one file of the plurality of files;

e) determining if the data block checksum is the same as a stored data block checksum of the collection of stored data block checksums;

f) if the data block checksum is the same as the stored data block checksum, generating a data block message digest;

g) comparing the data block message digest to a collection of stored data block message digests of the collection of stored data blocks;

h) determining if the data block message digest is the same as a stored data block message digest of the collection of stored data block message digests;

i) if the data block message digest is the same as the stored data block message digest, storing in a backup file a pointer to a stored data block of the collection of stored data blocks without adding the data block to the collection of stored data blocks; and

j) if the data block checksum is not the same as any stored data block checksum or if the data block message digest is not the same as any stored data block message digest, storing the data block in the collection of stored data blocks and storing in a backup file a pointer to the data block and a data block fingerprint of the data block,

wherein the collection of stored data blocks comprises a data block that was not generated from a previous version of the data received in step a.

2. The system of claim 1, wherein the plurality of files is stored on more than one data source.

3. The system of claim 1, wherein the processor is furthermore configured in steps i and j to store in the backup file data block metadata.

4. The system of claim 3, wherein the data block fingerprint is a unique data block identifier constructed from the data block checksum, the data block message digest, and the data block metadata.

5. The system of claim 3, wherein the data block metadata comprises one or more members chosen from a set consisting of a time stamp, a file name, an application source, a size, and a file extension.

6. The system of claim 1, wherein a size of the data block is smaller than a size of the data.

7. The system of claim 1, wherein the collection of stored data blocks and the backup file are compressed.

8. The system of claim 1, wherein if the data block is not identical with any stored data block, the system is further configured to:

k) generate a byte from the data block;

l) generate a byte checksum of the byte;

m) generate a byte message digest of the byte;

n) compare the byte checksum to a collection of stored byte checksums;

o) compare the byte message digest to a collection of stored byte message digests;

p) if the byte is identical with a stored byte, store in a backup file a pointer to the stored byte without storing the byte in the collection of stored bytes; and

q) if the byte is not identical with any stored byte, add the byte to the collection of stored bytes and store in a backup file a pointer to the stored byte and a byte fingerprint of the byte.

9. The system of claim 8, wherein a stored byte is shared by more than one data block.

10. The system of claim 8, wherein the processor is furthermore configured in steps p and q to store in the backup file byte metadata.

11. A method for managing data comprising the steps of:

a) receiving data from a data source;

b) generating a data block from the data;

c) generating a data block checksum of the data block;

d) comparing the data block checksum to a collection of stored data block checksums of a collection of stored data blocks, wherein the data source comprises a plurality of files and a stored data block is shared by more than one file of the plurality of files;

e) determining if the data block checksum is the same as a stored data block checksum of the collection of stored data block checksums;

f) if the data block checksum is the same as the stored data block checksum, generating a data block message digest;

g) comparing the data block message digest to a collection of stored data block message digests of the collection of stored data blocks;

h) determining if the data block message digest is the same as a stored data block message digest of the collection of stored data block message digests;

i) if the data block message digest is the same as the stored data block message digest, storing in a backup file a pointer to a stored data block of the collection of stored data blocks without adding the data block to the collection of stored data blocks; and

j) if the data block checksum is not the same as any stored data block checksum or if the data block message digest is not the same as any stored data block message digest, storing the data block in the collection of stored data blocks and storing in a backup file a pointer to the data block and a data block fingerprint of the data block,

wherein the collection of stored data blocks comprises a data block that was not generated from a previous version of the data received in step a; and

wherein the method is performed by a processor.

12. The method of claim 11, wherein the plurality of files is stored on more than one data source.

13. The method of claim 11, wherein steps i and j further comprise storing data block metadata.

14. The method of claim 13, wherein the data block fingerprint is a unique data block identifier constructed from the data block checksum, the data block message digest, and the data block metadata.

15. The method of claim 13, wherein the data block metadata comprises one or more members chosen from a set consisting of a time stamp, a file name, an application source, a size, and a file extension.

16. The method of claim 11, wherein a size of the data block is smaller than a size of the data.

17. The method of claim 11, wherein the collection of stored data blocks and the backup file are compressed.

18. The method of claim 11, wherein the step of generating a message digest is performed only if the checksums are the same.

19. The method of claim 11, wherein if the data block is not identical with any stored data block, the method further comprises the steps of:

k) generating a byte from the data block;

l) generating a byte checksum of the byte;

m) comparing the byte checksum to a collection of stored byte checksums of a collection of stored bytes;

n) determining if the byte checksum is the same as a stored byte checksum of the collection of stored byte checksums;

o) if the byte checksum is the same as the stored byte checksum, generating a byte message digest;

p) comparing the byte message digest to a collection of stored byte message digests of the collection of stored bytes;

q) determining if the byte message digest is the same as a stored byte message digest of the collection of stored byte message digests;

r) if the byte message digest is the same as the stored byte message digest, storing in a backup file a pointer to a stored byte of the collection of stored bytes without storing the byte in the collection of stored bytes; and

s) if the byte checksum is not the same as any stored byte checksum or if the byte message digest is not the same as any stored byte message digest, storing the byte in the collection of stored bytes and storing in a backup file a pointer to the byte and a byte fingerprint of the byte.

20. The method of claim 19, wherein a stored byte is shared by more than one data block.

21. The method of claim 19, wherein steps r and s further comprise storing in the backup file byte metadata.