Hash file system and method for use in a commonality factoring system

• US 6,704,730 B2
• Filed: 02/05/2001
• Issued: 03/09/2004
• Est. Priority Date: 02/18/2000
• Status: Expired due to Term

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Avamar Technologies, Inc. (Dell Technologies Inc.)
• Inventors: Whitehill, Stephen B., Moulton, Gregory Hagan
• Primary Examiner(s): Corrielus, Jean M.
• Application Number:
  US09/777,150
• Publication Number:
  US 20010037323A1
• Time in Patent Office: 1,128 Days
• Field of Search: 707/7, 707/6, 707/204, 714/798, 717/139, 341/87, 341/51
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: Y10S 707/99936 Pattern matching access
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A system and method for a computer file system that is based and organized upon hashes and/or strings of digits of certain, different, or changing lengths and which is capable of eliminating or screening redundant copies of aggregate blocks of data (or parts of data blocks) from the system. The hash file system of the present invention utilizes hash values for computer files or file pieces which may be produced by a checksum generating program, engine or algorithm such as industry standard MD4, MD5, SHA or SHA-1 algorithms. Alternatively, the hash values may be generated by a checksum program, engine, algorithm or other means that produces an effectively unique hash value for a block of data of indeterminate size based upon a non-linear probablistic mathematical algorithm.

Claims

1. A computing environment comprising:

at least one list for maintaining portions of digital sequences and corresponding probabilistically unique identifiers for each of said portions of said digital sequences;

at least one new digital sequence;

at least one partitioning mechanism for dividing said new digital sequence into a plurality of shorter digital sequences and producing a probabilistically unique identifier for each of said shorter digital sequences; and

a comparison mechanism for determining if any one of said probabilistically unique identifiers for each of said plurality of shorter digital sequences is currently maintained in said list.

2. The computing environment of claim 1 wherein said at least one list comprises a plurality or lists.

3. The computing environment of claim 2 wherein said plurality of lists, each contain a portion of said probabilistically unique identifiers.

4. The computing environment of claim 2 wherein at least one of said plurality of lists is physically displaced from others of said at least one list.

5. The computing environment of claim 4 wherein said plurality of lists are coupled by means of a network.

6. The computing environment of claim 2 wherein said plurality of lists is partitioned based on said probabilistically unique identifiers.

7. The computing environment of claim 1 wherein said at least one list is physically displaced from said at least one partitioning mechanism.

8. The computing environment of claim 7 wherein said comparison mechanism is operative to utilize at least a portion of said probabilistically unique identifiers for each of said plurality of said shorter digital sequences as a locator correlated with said list partitions.

9. The computing environment of claim 1 wherein said list comprises a physically distributed database.

10. The computing environment of claim 1 wherein said at least one partitioning mechanism and said at least one list are coupled by means of a network.

11. The computing environment of claim 10 wherein said network comprises a public network such as the internet.

12. The computing environment of claim 11 wherein said at least one partitioning mechanism and said at least one list are physically distributed.

13. The computing environment of claim 1 wherein said probabilistically unique identifiers are produced by means of a hash function.

14. The computing environment of claim 13 wherein said hash function comprises an industry standard digest algorithm.

15. The computing environment of claim 14 wherein said has function comprises one of MD4, MD5 SHA or SHA-1 algorithms.

16. The computing environment of claim 13 wherein said probabilistically unique identifiers are produced by means of a checksum.

17. The computing environment of claim 1 wherein said digital sequences are of variable length.

18. The computing environment of claim 1 wherein said digital sequences are of invariable length.

19. The computing environment of claim 1 wherein said digital sequence comprises a data file.

20. The computing environment of claim 1 wherein said digital sequence comprises a data stream.

21. The computing environment of claim 1 wherein said digital sequence comprises an executable file.

22. The computing environment of claim 1 wherein said digital sequence comprises a database record.

23. The computing environment of claim 1 wherein said digital sequence comprises a database index.

24. The computing environment of claim 1 wherein said digital sequence comprises a digital device image.

25. The computing environment of claim 1 wherein said digital sequence comprises a network packet.

26. The computing environment of claim 1 wherein said digital sequence comprises a digitized analog signal.

27. The computing environment of claim 1 wherein any of said probabilistically unique identifiers and corresponding ones of said plurality of shorter digital sequences not determined to be maintained in said at least one list are added to said at least one list.

28. A method for establishing an identifier for at least a portion of a digital sequence comprising:

performing a function on said at least a portion of said digital sequence to produce a probabilistically unique symbol therefore;

establishing a correspondence between said at least a portion of said digital sequence and said probabilistically unique symbol; and

utilizing said probabilistically unique symbol as said identifier.

29. The method of claim 28 wherein said identifier and said corresponding at least a portion of said digital sequence are maintained in at least one data list.

30. The method of claim 29 wherein at least a portion of said identifier is utilizable as a pointer to a location of said corresponding at least a portion of said digital sequence within said at least one data list.

31. The method of claim 28 herein said at least a portion of said digital sequence comprises at least a portion of a data file and said identifier is uniquely related to a content of said at least a portion of said data file.

32. The method of claim 28 wherein said at least a portion of said digital sequence comprises at least a portion of a data stream and said identifier is uniquely related to a content of said at least a portion of said data stream.

33. The method of claim 28 wherein said at least a portion of said digital sequence comprises at least a portion of an executable file and said identifier is uniquely related to a content of said at least a portion of said executable file.

34. The method of claim 28 wherein said step of performing a function is carried out by the step of:

hashing said at least a portion of said digital sequence to produce said probabilistically unique symbol.

35. The method of claim 34 wherein said step of hashing is carried out by means of an industry standard digest algorithm.

36. The method of claim 35 wherein said step of hashing is carried out by means of one of an MD4, MD5, SHA or SHA-1 algorithm.

37. A computer program product comprising:

a computer usable medium having computer readable code embodied therein for establishing an identifier for at least a portion of a digital sequence comprising;

computer readable program code devices configured to cause a computer to effect performing a function on said at least a portion of said digital sequence to produce a probabilistically unique symbol therefore;

computer readable program code devices configured to cause a computer to effect establishing a correspondence between said at least a portion of said digital sequence and said probabilistically unique symbol; and

computer readable program code devices configured to cause a to effect utilizing said probabilistically unique symbol as said identifier.

38. The computer program product of claim 37 wherein said identifier and said corresponding at least a portion of said digital sequence are maintained in at least one data list.

39. The computer program product of claim 38 wherein at least a portion of said identifier is utilizable as a pointer to a location of said corresponding at least a portion of said digital sequence within said at least one data list.

40. The computer program product of claim 37 wherein said at least a portion of said digital sequence comprises at least a portion of a data file and said identifier is uniquely related to a content of said at least a portion of said data file.

41. The computer program product of claim 37 wherein said at least a portion of said digital sequence comprises at least a portion of a data stream and said identifier is uniquely related to a content of said at least a portion of said data stream.

42. The computer program product of claim 37 wherein said at least a portion of said digital sequence comprises at least a portion of an executable file and said identifier is uniquely related to a content of said at least a portion of said executable file.

43. The computer program product of claim 37 wherein said computer readable program code devices configured to cause a computer to effect performing a function is carried out by:

computer readable program code devices configured to cause a computer to effect hashing said at least a portion of said digital sequence to produce said probabilistically unique symbol.

44. The computer program product of claim 43 wherein said computer readable program code devices configured to cause a computer to effect hashing is carried out by means of an industry standard digest algorithm.

45. The computer program product of claim 44 wherein said computer readable program code devices configured to cause a computer to effect hashing is carried out by means of one of an MD4, MD5, SHA or SHA-1 algorithm.