System and method for sharing storage resources between multiple files

• US 7,269,689 B2
• Filed: 06/17/2004
• Issued: 09/11/2007
• Est. Priority Date: 06/17/2004
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Eshghi, Kave, Tang, Hsiu-Khuern
• Primary Examiner(s): Peugh; Brian R.
• Assistant Examiner(s): Farrokh; Hashem
• Application Number:
  US10/870,783
• Publication Number:
  US 20050283500A1
• Time in Patent Office: 1,181 Days
• Field of Search: 711/112
• US Class Current: 711/112
• CPC Class Codes: G06F 16/1752 based on file chunks

Abstract

An improved sliding window chunking apparatus and method comprising comparing a fingerprint value of each position in a data set to a second set of criteria, at least in instances when it doesn'"'"'t satisfy a first set of criteria, and, if the value satisfies the second set of criteria, identifying the position as a potential breakpoint. Subsequently, if a fingerprint value that satisfies the first set of criteria is not found before a maximum chunk size is reached, the potential breakpoint can be designated as a breakpoint. Further improvement is possible by imposing minimum and maximum sizes on chunks. In some instances, more than two sets of criteria may be used to identify additional potential chunks to be used should subsets having fingerprint values satisfying either of the first two sets of criteria not be found.

Claims

1. A processor-based method for creating one or more chunks in a machine readable medium from a sequence of values in the machine readable medium, each chunk representing a portion of the sequence of values between at least two breakpoints, the method comprising:

obtaining a fingerprint value for a position in the sequence of values in the machine readable medium;

designating positions within the sequence of values as breakpoints where each breakpoint is the beginning or end of a chunk in the machine readable medium and a position is designated as a breakpoint if at least one of the following breakpoint conditions is true;

(a) the fingerprint value at the position is a D1-match

(b) the fingerprint value at the position is a D2-match, and the distance between the prior breakpoint, if any, and any subsequent D1-match breakpoint is greater than a pre-determined maximum value M1;

(c) the distance between the prior breakpoint, if any, and the position is equal to the maximum value M1, wherein

a value is a D1-match if a function D1Match returns ‘

true’

when applied to the fingerprint value;

a value is a D2-match if a function D2Match returns ‘

true’

when applied to the fingerprint value;

D1Match and D2Match are Boolean functions mapping integers to Boolean values; and

when applied to a random integer, a probability that D1Match returns ‘

true’

is smaller than a probability that D2Match returns ‘

true’

.

2. The method of claim 1 wherein obtaining a fingerprint value for a position in the sequence comprises obtaining a hash value for a sequence of data values contained in a window containing the position for which the fingerprint value is to be obtained.

3. The method of claim 2 wherein the position is not designated as a breakpoint even if at least one of the breakpoint conditions is true if the distance between the position and any prior breakpoint is less than a pre-determined minimum value M2.

4. The method of claim 3 wherein the last position of each chunk is a breakpoint or the last position in the sequence of values.

5. The method of claim 3 wherein the first position of each chunk is a breakpoint or the first position in the sequence of values.

6. The method of claim 3 further comprising designating breakpoints in the sequence of values by determining fingerprint values beginning at or near one end of the sequence of values and progressing through to the other end of the sequence of values.

7. The method of claim 6 wherein the sequence of values is a sequence of integer values and D1, D2, R1, and R2 are integers.

8. The method of claim 7 wherein D1 is even, and D2 is one half of D1, or D1 is odd, and D2 is the next integer larger or smaller than D1 divided by two.

9. The method of claim 1 wherein:

the function D1Match returns ‘

true’

if the value divided by a first divisor D1 results in a remainder having a value R1;

the function D2Match returns ‘

true’

if the value divided by a second divisor D2 results in a remainder having a value R2;

D1 is not equal to D2; and

D1, D2, R1, and R2 have pre-detennined values.

10. The method of claim 1 wherein the method is performed by a computer.

11. The method of claim 1 further comprising determining, if the fingerprint value is not a D1-match or a D2-match, whether the fingerprint value divided by at least one additional divisor DN results in a remainder having a value RN where DN and RN have predetermined values, DN is not equal to D1 or D2, and RN corresponds to DN.

12. An apparatus comprising;

a machine readable medium containing instructions which, when executed by a machine, causes the machine to perform operations for creating a plurality of chunks in a machine readable medium from a sequence of values in the machine readable medium where each chunk is a smaller sequence of values between at least two breakpoints, the operations comprising;

obtaining a fingerprint value for a position in the sequence of values in the machine readable medium;

grouping the sequence into a plurality of adjacent, non-overlapping chunks in the machine readable medium wherein each chunk begins or ends on a breakpoint, the breakpoint satisfying at least one of the following conditions;

(a) the fingerprint value at the position is a D2-match, and the distance between the prior breakpoint, if any, and any subsequent D1-match breakpoint is greater than a pre-determined maximum value M1;

(b) the distance between the prior breakpoint if any, and the position is equal to the maximum value M1, wherein

a value is a D1-match if a function D1Match returns ‘

true’

when applied to the fingerprint value;

p1 a value is a D2-match if a function D2Match returns ‘

true’

when applied to the fingerprint value;

D1Match and D2Match are pre-determined Boolean functions mapping integers to Boolean values; and

when applied to a random integer, the probability that D1 Match returns ‘

true’

is smaller than the probability that D2Match returns ‘

true’

.

13. The apparatus of claim 12 wherein the apparatus is adapted to electronically transfer the set of instructions to another apparatus.

14. The apparatus of claim 13 wherein the machine readable medium comprises at least one of the following:

volatile solid state memory, non-volatile solid state memory;

an optical disk, a magnetic disk, a magneto-optical disk, RAM, PROM, EPROM, magnetic tape, an electronic circuit, and/or is a RAID, DAS, NAS, or SAN apparatus.

15. The apparatus of claim 12 wherein the apparatus is adapted to electronically transfer a set of fingerprint values to another apparatus wherein each fingerprint value in the set corresponds to a chunk of a divided sequence.

16. An apparatus comprising:

a machine readable medium for storing a fingerprint value representing a position in a sequence of values, the a sequence of values organized into a plurality of chunks in the machine readable medium wherein each chunk begins or ends on a position in the machine readable medium that satisfies at least one of the following breakpoint conditions;

the fingerprint value at the position is a D1-match;

the fingerprint value at the position is a D2-match, and the distance between a prior breakpoint, if any, and any subsequent D1-match breakpoint is greater than a pre-determined maximum value M1; and

the distance between the prior breakpoint, if any, and the position is equal to the maximum value M1;

wherein

a value is a D1-match if the value divided by a first divisor D1 results in a remainder having a value R1;

a value is a D2-match if the value divided by a second divisor D2 results in a remainder having a value R2;

D1 is not equal to D2; and

D1, D2, R1, and R2 have specific values.

17. The apparatus of claim 16 wherein the apparatus has or is adapted to obtain a hash value for each chunk, and is adapted to compare the hash values with the hash values of previously stored chunks to determine which, if any of the chunks is to be stored.

18. The apparatus of claim 16 wherein the apparatus is adapted to transmit the organized sequence by first transmitting hash values for the chunks to a receiving apparatus, and only transmitting chunks not already stored on the receiving apparatus.