Efficient chunking algorithm

• US 20060047855A1
• Filed: 05/13/2004
• Published: 03/02/2006
• Est. Priority Date: 05/13/2004
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Bjorner, Nikolaj S., Teodosiu, Dan, Gurevich, Yuri
• Application Number:
  US10/844,893
• Publication Number:
  US 20060047855A1
• Time in Patent Office: Days
• US Class Current: 709/247
• CPC Class Codes: G06F 16/182 Distributed file systems
• CPC Class Codes: H04L 63/123 received data contents, e.g. message integrity

Abstract

The present invention provides a method for chunking an object. The method is arranged to provide efficient chunking of objects such that objects can be efficiently updated between a remote machine and a local machine over a network. The chunking algorithm is applicable in networked application such as file synchronization using remote differential compression (RDC) techniques. The chunking algorithm provides enhanced efficiencies by locating chunk boundaries around local maxima.

Claims

1. A method for partitioning an object into chunks, comprising:

calculating fingerprint values at each position within the object;

evaluating an offset associated with each possible cut-point location;

evaluating the fingerprint values located within a horizon around each position within the object;

identifying a cut-point location in response to the evaluated fingerprint values; and

partitioning the object into chunks based on the identified cut-point locations.

2. The method of claim 1, wherein calculating the fingerprint values at each position within the object further comprises applying a fingerprint function to object data contained within a small window around each position.

3. The method of claim 2, wherein applying the fingerprint function further comprises using at least one of:

a Rabin polynomial;

an Adler hash; and

a random hash with cyclic shifting.

4. The method of claim 1, further comprising adjusting the size of the horizon based on at least one of:

a data type associated with the object;

the size of the object;

an environmental constraint; and

a usage model associated with the object.

5. The method of claim 2, further comprising adjusting the size of the small window based on at least one of:

a data type associated with the object;

the size of the object;

an environmental constraint; and

a usage model associated with the object.

6. The method of claim 1, wherein evaluating the fingerprint values located within the horizon, further comprises applying a mathematical function to the fingerprint values and identifying a cut-point location when the mathematical function is satisfied.

7. The method of claim 6, wherein applying the mathematical function further comprises:

using a predicate to map fingerprint values into Boolean values;

partitioning fingerprint values into a small domain;

determining a maximum value within the horizon;

determining a minimum value within the horizon;

evaluating differences between fingerprint values within the horizon; and

summing fingerprint values within the horizon.

8. The method of claim 2, wherein evaluating the fingerprint values located within the horizon further comprises:

applying a mathematical function on fingerprint values; and

identifying a cut-point location at a given offset when the mathematical function attains a pre-determined value at a given offset and attains other pre-determined values at a predetermined number of previous offsets.

9. The method of claim 8, wherein the mathematical function comprises at least one of:

a predicate; and

a function that partitions fingerprint values into a suitable small domain.

10. The method of claim 2, wherein applying the mathematical function further comprises determining a local maximum fingerprint value within the horizon.

11. The method of claim 10, further comprising:

allocating a first flag array and a second flag array of length equal to the horizon and initializing the flag arrays to Boolean false;

allocating a first fingerprint array and a second fingerprint array of length equal to the horizon and initializing the fingerprint array to zero;

allocating a first offset array and a second offset array of length equal to the horizon and initializing the offset arrays to zero;

initializing an index l to zero;

initializing an index k to zero; and

initializing a current offset into the object to zero.

12. The method of claim 11, further comprising:

traversing the object in intervals batches of size h and within each interval;

setting the value of the first index into the first flag array to true;

setting the value of the first index into the first offset array to the last offset of the current interval batch;

setting the value of the first index into the fingerprint arrays to the fingerprint at the last offset of the current interval; and

decrementing the offset to the last position of the current interval.

13. The method of claim 12, further comprising:

as long as the current value of the last offset of the current interval is greater than the value of the second offset array at index l plus the value of h, then updating the value of the first flag array at position k to false provided the fingerprint value at the current value of the last offset is equal to the value of the first fingerprint array at position k;

if the fingerprint value at the current value of the last offset is greater than the value of the first fingerprint array at position k, then incrementing k and setting the value of the first offset array at index k to the value of the current last offset;

setting the value of the first flag array at index k to true, and setting the value of the first hash array at index k to the current value of the last offset; and

decrementing the offset to the last position of the current interval.

14. The method of claim 12, further comprising:

as long as the current value of the offset is not less than the offset to the beginning of the current interval then updating the value of the first flag array at position k to false, provided the fingerprint value at the current value of the last offset is equal to the value of the first fingerprint array at position k;

if the fingerprint value at the current value of the last offset is greater than the value of the first fingerprint array at position k, then incrementing k and setting the value of the first offset array at index k to the value of the current last offset, setting the value of the first flag array at index k to true, and setting the value of the first hash array at index k to the current value of the last offset;

if the value of the second fingerprint array at index l is no larger than the fingerprint value at the current value of the last offset, then setting the value of the second flag array at index l to false and decrementing the offset to the last position of the current interval.

15. The method of claim 14, further comprising updating the value of the first flag array at index k to false if it is already false or when there exists an index j between 0 and l, inclusive, where the value of the second offset array at index j plus the value of h is at least as big as the value of the first offset array at index k, and the value of the second fingerprint array at index j is at least the value of the first fingerprint array at index k.

16. The method of claim 15, further comprising setting the value of the second offset array at index l to a cut-point if the value of the second flag array at position l is true.

17. The method of claim 16, further comprising exchanging the reference to the first and second offset, fingerprint arrays, and flag arrays before the next interval is processed.

18. The method of claim 10, further comprising:

allocating a flag array of length equal to the horizon and initializing the flag array to Boolean false;

allocating a fingerprint array of length equal to the horizon and initializing the fingerprint array to zero;

allocating an offset array of length equal to the horizon and initializing the offset array to zero;

initializing a min index to zero;

initializing a max index to zero; and

initializing a current offset into the object to zero.

19. The method of claim 18, further comprising when the current offset is identified as being equal to the value of the offset array entry at max index plus the horizon plus one:

finding a local maximum at the offset given by the value of the offset array at max index, if the value of the flag array entry at max index is Boolean true; and

setting the max index to a value that is determined by the max index decremented by one modulo the horizon.

20. The method of claim 19, further comprising when the fingerprint value associated with the current offset is less than the value of the fingerprint array entry at min index:

decrementing the min index modulo the horizon;

setting the value of the flag array entry at min index to Boolean false;

setting the value of the fingerprint array entry at min index to the fingerprint value associated with the current offset; and

setting the value of the offset array entry at min index to the current offset.

21. The method of claim 20, further comprising when the fingerprint value associated with the current offset is equal to the value of the fingerprint array entry at min index:

setting the value of the flag array entry at min index to Boolean false;

setting the value of the fingerprint array entry at min index to the fingerprint value associated with the current offset; and

setting the value of the offset array entry at min index to the current offset.

22. The method of claim 21, further comprising when the fingerprint value associated with the current offset is greater than the value of the fingerprint array entry at min index, and when the min index is different from the max index:

incrementing the min index by one modulo the horizon.

23. The method of claim 22, further comprising when the fingerprint value associated with the current offset is greater than the value of the fingerprint array entry at min index, and when the min index is equal to the max index:

setting the flag array entry at min index to Boolean true;

setting the fingerprint array entry at min index to the fingerprint value associated with the current offset; and

setting the offset array entry at min index to the current offset.

24. The method of claim 23, further comprising incrementing the current offset once the previous determinations have been completed.

25. A computer-readable medium having computer executable instructions for partitioning an object into chunks, comprising:

calculating fingerprint values at each position within the object;

evaluating an offset associated with each possible cut-point location;

evaluating the fingerprint values located within a horizon around each position within the object;

identifying a cut-point location in response to the evaluated fingerprint values; and

partitioning the object into chunks based on the identified cut-point locations.

26. The computer-readable medium of claim 25, wherein calculating the fingerprint values at each position within the object further comprises applying a fingerprint function to object data contained within a small window around each position.

27. The computer-readable medium of claim 26, wherein applying the fingerprint function further comprises using at least one of:

a Rabin polynomial;

an Adler hash; and

a random hash with cyclic shifting.

28. The computer-readable medium of claim 25, further comprising adjusting the size of the horizon based on at least one of:

a data type associated with the object;

the size of the object;

an environmental constraint; and

a usage model associated with the object.

29. The computer-readable medium of claim 26, further comprising adjusting the size of the small window based on at least one of:

a data type associated with the object;

the size of the object;

an environmental constraint; and

a usage model associated with the object.

30. The computer-readable medium of claim 25, wherein evaluating the fingerprint values located within the horizon, further comprises applying a mathematical function to the fingerprint values and identifying a cut-point location when the mathematical function is satisfied.

31. The computer-readable medium of claim 30, wherein applying the mathematical function further comprises:

using a predicate to map fingerprint values into Boolean values;

partitioning fingerprint values into a small domain;

determining a maximum value within the horizon;

determining a minimum value within the horizon;

evaluating differences between fingerprint values within the horizon; and

summing fingerprint values within the horizon.

32. The computer-readable medium of claim 26, wherein evaluating the fingerprint values located within the horizon further comprises:

applying a mathematical function on fingerprint values; and

identifying a cut-point location at a given offset when the mathematical function attains a pre-determined value at a given offset and attains other pre-determined values at a predetermined number of previous offsets.

33. The computer-readable medium of claim 32, wherein the mathematical function comprises at least one of:

a predicate; and

a function that partitions fingerprint values into a suitable small domain.

34. The computer-readable medium of claim 26, wherein applying the mathematical function further comprises determining a local maximum fingerprint value within the horizon.

35. The computer-readable medium of claim 34, further comprising:

allocating a first flag array and a second flag array of length equal to the horizon and initializing the flag arrays to Boolean false;

allocating a first fingerprint array and a second fingerprint array of length equal to the horizon and initializing the fingerprint array to zero;

allocating a first offset array and a second offset array of length equal to the horizon and initializing the offset arrays to zero;

initializing an index l to zero;

initializing an index k to zero; and

initializing a current offset into the object to zero.

36. The computer-readable medium of claim 35, further comprising:

traversing the object in intervals batches of size h and within each interval;

setting the value of the first index into the first flag array to true;

setting the value of the first index into the first offset array to the last offset of the current interval batch;

setting the value of the first index into the fingerprint arrays to the fingerprint at the last offset of the current interval; and

decrementing the offset to the last position of the current interval.

37. The computer-readable medium of claim 36, further comprising:

as long as the current value of the last offset of the current interval is greater than the value of the second offset array at index l plus the value of h, then updating the value of the first flag array at position k to false provided the fingerprint value at the current value of the last offset is equal to the value of the first fingerprint array at position k;

if the fingerprint value at the current value of the last offset is greater than the value of the first fingerprint array at position k, then incrementing k and setting the value of the first offset array at index k to the value of the current last offset;

setting the value of the first flag array at index k to true, and setting the value of the first hash array at index k to the current value of the last offset; and

decrementing the offset to the last position of the current interval.

38. The computer-readable medium of claim 36, further comprising:

as long as the current value of the offset is not less than the offset to the beginning of the current interval then updating the value of the first flag array at position k to false, provided the fingerprint value at the current value of the last offset is equal to the value of the first fingerprint array at position k;

if the fingerprint value at the current value of the last offset is greater than the value of the first fingerprint array at position k, then incrementing k and setting the value of the first offset array at index k to the value of the current last offset, setting the value of the first flag array at index k to true, and setting the value of the first hash array at index k to the current value of the last offset;

if the value of the second fingerprint array at index l is no larger than the fingerprint value at the current value of the last offset, then setting the value of the second flag array at index l to false and decrementing the offset to the last position of the current interval.

39. The computer-readable medium of claim 36, further comprising updating the value of the first flag array at index k to false if it is already false or when there exists an index j between 0 and l, inclusive, where the value of the second offset array at index j plus the value of h is at least as big as the value of the first offset array at index k, and the value of the second fingerprint array at index j is at least the value of the first fingerprint array at index k.

40. The computer-readable medium of claim 39, further comprising setting the value of the second offset array at index l to a cut-point if the value of the second flag array at position l is true.

41. The computer-readable medium of claim 40, further comprising exchanging the reference to the first and second offset, fingerprint arrays, and flag arrays before the next interval is processed.

42. The computer-readable medium of claim 34, further comprising:

allocating a flag array of length equal to the horizon and initializing the flag array to Boolean false;

allocating a fingerprint array of length equal to the horizon and initializing the fingerprint array to zero;

allocating an offset array of length equal to the horizon and initializing the offset array to zero;

initializing a min index to zero;

initializing a max index to zero; and

initializing a current offset into the object to zero.

43. The computer-readable medium of claim 42, further comprising when the current offset is identified as being equal to the value of the offset array entry at max index plus the horizon plus one:

finding a local maximum at the offset given by the value of the offset array at max index, if the value of the flag array entry at max index is Boolean true; and

setting the max index to a value that is determined by the max index decremented by one modulo the horizon.

44. The computer-readable medium of claim 43, further comprising when the fingerprint value associated with the current offset is less than the value of the fingerprint array entry at min index:

decrementing the min index modulo the horizon;

setting the value of the flag array entry at min index to Boolean false;

setting the value of the fingerprint array entry at min index to the fingerprint value associated with the current offset; and

setting the value of the offset array entry at min index to the current offset.

45. The computer-readable medium of claim 44, further comprising when the fingerprint value associated with the current offset is equal to the value of the fingerprint array entry at min index:

setting the value of the flag array entry at min index to Boolean false;

setting the value of the fingerprint array entry at min index to the fingerprint value associated with the current offset; and

setting the value of the offset array entry at min index to the current offset.

46. The computer-readable medium of claim 45, further comprising when the fingerprint value associated with the current offset is greater than the value of the fingerprint array entry at min index, and when the min index is different from the max index:

incrementing the min index by one modulo the horizon.

47. The computer-readable medium of claim 46, further comprising when the fingerprint value associated with the current offset is greater than the value of the fingerprint array entry at min index, and when the min index is equal to the max index:

setting the flag array entry at min index to Boolean true;

setting the fingerprint array entry at min index to the fingerprint value associated with the current offset; and

setting the offset array entry at min index to the current offset.

48. The computer-readable medium of claim 47, further comprising incrementing the current offset once the previous determinations have been completed.