Duplicate management

• US 9,535,624 B1
• Filed: 08/04/2005
• Issued: 01/03/2017
• Est. Priority Date: 09/13/2004
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Inventors: Patterson, R. Hugo, Zhu, Ming Benjamin, Lee, Edward K.
• Primary Examiner(s): Rigol, Yaima
• Application Number:
  US11/197,126
• Time in Patent Office: 4,170 Days
• Field of Search: 711/154, 711/159, 711/118, 711/133, 707/101, 707/102, 707/203, 707/204
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1453 using de-duplication of the data
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0641 De-duplication techniques
• CPC Class Codes: G06F 3/0673 Single storage device

Abstract

A method of managing duplicate segments from a segmented file storage system is disclosed. The method comprises indexing a segment according to a key for the segments wherein the index includes an identification of a first data location where the segment is stored and identifying a duplicate segment having the same key that is stored in a second location. The method further comprises determining that the duplicate segment is an undesired duplicate segment and eliminating the undesired duplicate segment.

Claims

1. A method of managing duplicate segments from a segmented file storage system including:

indexing each of a plurality of segments with a correspondingly associated key, the index including an identification of a first data location where a first segment is stored;

identifying a duplicate segment associated with a duplicate key matching a first key associated with the first segment and stored in a second data location;

determining whether the duplicate segment is an undesired duplicate segment based at least in part on an amount of time that has passed since an operation associated with the duplicate segment;

eliminating the duplicate segment if the duplicate segment is determined to be an undesired duplicate segment, wherein the duplicate segment is an undesired duplicate segment in the event the amount of time has passed since the operation associated with the duplicate segment; and

retaining the duplicate segment if the duplicate segment is not determined to be an undesired duplicate segment, wherein the duplicate segment is not an undesired duplicate segment in the event the amount of time has not passed since the operation associated with the duplicate segment.

2. A method as in claim 1, wherein the key is a hash function of content of the segment.

3. A method as in claim 1, wherein a duplicate segment is an undesired duplicate segment if the segment is not one of a predetermined number of most recently stored segments.

4. A method as in claim 1, wherein a duplicate segment is an undesired duplicate segment if the segment was not accessed more recently than a predetermined time.

5. A method as in claim 1, wherein a duplicate segment is an undesired duplicate segment if the segment was not stored more recently than a predetermined time.

6. A method as in claim 1, wherein the identification of the first data location is a container ID.

7. A method as in claim 1, wherein determining that the duplicate segment is an undesired duplicate segment includes noting segments to eliminate.

8. A method as in claim 1, wherein determining that the duplicate segment is an undesired duplicate segment includes noting segments to keep.

9. A method as in claim 1, wherein determining that the duplicate segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not determined undesired duplicate segments.

10. A method as in claim 1, wherein determining that the duplicate segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not identified undesired duplicates and wherein the live instance summary vector gives a probabilistic indication that segments are not undesired duplicate segments.

11. A method as in claim 9, wherein determining that the duplicate segment is an undesired duplicate segment includes creating a live summary vector of segments that are referenced and comparing segments to the live summary vector and the live instance summary vector.

12. A method as in claim 1, further including repacking data containers having eliminated segments.

13. A method as in claim 1, wherein the operation associated with the duplicate segment includes:

storing the duplicate segment and accessing the duplicate segment.

14. A method of managing duplicate segments from a segmented file storage system including:

identifying a first segment that is stored in a first data location;

identifying a second segment as being a duplicate of the first segment that is stored in a second data location;

determining whether the second segment is an undesired duplicate segment based at least in part on an amount of time that has passed since an operation associated with the second segment;

eliminating the second segment if the second segment is determined to be an undesired duplicate segment, wherein the second segment is an undesired segment in the event the amount of time has passed since the operation associated with the second segment; and

retaining the second segment if the second segment is not determined to be an undesired duplicate segment, wherein the second segment is not an undesired duplicate segment in the event the amount of time has not passed since the operation associated with the second segment,

wherein identifying the second segment as being a duplicate of the first segment includes loading and analyzing indexes for data segments.

15. A method as in claim 14, wherein identifying a second segment as being a duplicate of the first segment uses a summary vector.

16. A method as in claim 14, wherein a second segment is an undesired duplicate segment if the segment is not one of a predetermined number of most recently stored segments.

17. A method as in claim 14, wherein a second segment is an undesired duplicate segment if the segment was not stored more recently than a predetermined time.

18. A method as in claim 14, wherein a second segment is an undesired duplicate segment if the segment was not accessed more recently than a predetermined time.

19. A method as in claim 14, wherein determining that the second segment is an undesired duplicate segment includes noting segments to eliminate.

20. A method as in claim 14, wherein determining that the second segment is an undesired duplicate segment includes noting segments to keep.

21. A method as in claim 14, wherein determining that the second segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not determined undesired duplicate segments.

22. A method as in claim 21, wherein determining that the second segment is an undesired duplicate segment includes creating a live summary vector of segments that are referenced and comparing segments to the live summary vector and the live instance summary vector.

23. A method as in claim 14, wherein determining that the second segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not identified undesired duplicates and wherein the live instance summary vector gives a probabilistic indication that segments are not undesired duplicate segments.

24. A method as in claim 14, further including repacking data containers having eliminated segments.

25. A computer program product for managing duplicate segments from a segmented file storage system, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:

indexing each of a plurality of segments with a correspondingly associated key, the index including an identification of a first data location where a first segment is;

identifying a duplicate segment associated with a duplicate key matching a first key associated with the first segment and stored in a second data location;

determining whether the duplicate segment is an undesired duplicate segment based at least in part on an amount of time that has passed since an operation associated with the duplicate segment;

eliminating the duplicate segment if the duplicate segment is determined to be an undesired duplicate segment, wherein the duplicate segment is an undesired duplicate segment in the event the amount of time has passed since the operation associated with the duplicate segment; and

retaining the duplicate segment if the duplicate segment is not determined to be an undesired duplicate segment, wherein the duplicate segment is not an undesired duplicate segment in the event the amount of time has not passed since the operation associated with the duplicate segment.

26. A computer program product as recited in claim 25, wherein the key is a hash function of the segment content.

27. A computer program product as recited in claim 25, wherein a duplicate segment is an undesired duplicate segment if the segment is not one of a predetermined number of most recently stored segments.

28. A computer program product as recited in claim 25, wherein a duplicate segment is an undesired duplicate segment if the segment was not accessed more recently than a predetermined time.

29. A computer program product as recited in claim 25, wherein a duplicate segment is an undesired duplicate segment if the segment was not stored more recently than a predetermined time.

30. A computer program product as recited in claim 25, wherein the identification of the first data location is a container ID.

31. A computer program product as recited in claim 25, wherein determining that the duplicate segment is an undesired duplicate segment includes noting segments to eliminate.

32. A computer program product as recited in claim 25, wherein determining that the duplicate segment is an undesired duplicate segment includes noting segments to keep.

33. A computer program product as recited in claim 25, wherein determining that the duplicate segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not determined undesired duplicate segments.

34. A computer program product as recited in claim 33, wherein determining that the duplicate segment is an undesired duplicate segment includes creating a live summary vector of segments that are referenced and comparing segments to the live summary vector and the live instance summary vector.

35. A computer program product as recited in claim 25, wherein determining that the duplicate segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not identified undesired duplicates and wherein the live instance summary vector gives a probabilistic indication that segments are not undesired duplicate segments.

36. A computer program product as recited in claim 25, further including repacking data containers having eliminated segments.

37. A computer program product for managing duplicate segments from a segmented file storage system, the computer program product being embodied in a non-transitory computer readable medium and comprising computer instructions for:

identifying a first segment that is stored in a first data location;

identifying a second segment as being a duplicate of the first segment that is stored in a second data location;

determining whether the second segment is an undesired duplicate segment based at least in part on an amount of time that has passed since an operation associated with the second segment;

eliminating the second segment if the second segment is determined to be an undesired duplicate segment, wherein the second segment is an undesired duplicate segment in the event the amount of time has passed since the operation associated with the second segment; and

retaining the second segment if the second segment is not determined to be an undesired duplicate segment, wherein the second segment is not an undesired duplicate segment in the event the amount of time has not passed since the operation associated with the second segment.

38. A computer program product as recited in claim 37, wherein identifying a second segment as being a duplicate of the first segment uses a summary vector.

39. A computer program product as recited in claim 37, wherein a second segment is an undesired duplicate segment if the segment is not one of a predetermined number of most recently stored segments.

40. A computer program product as recited in claim 37, wherein a second segment is an undesired duplicate segment if the segment was not stored more recently than a predetermined time.

41. A computer program product as recited in claim 37, wherein a second segment is an undesired duplicate segment if the segment was not accessed more recently than a predetermined time.

42. A computer program product as recited in claim 37, wherein determining that the second segment is an undesired duplicate segment includes noting segments to eliminate.

43. A computer program product as recited in claim 37, wherein determining that the second segment is an undesired duplicate segment includes noting segments to keep.

44. A computer program product as recited in claim 37, wherein determining that the second segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not determined undesired duplicate segments.

45. A computer program product as recited in claim 44, wherein determining that the second segment is an undesired duplicate segment includes creating a live summary vector of segments that are referenced and comparing segments to the live summary vector and the live instance summary vector.

46. A computer program product as recited in claim 37, wherein determining that the second segment is an undesired duplicate segment includes creating a live instance summary vector of segments that are not identified undesired duplicates and wherein the live instance summary vector gives a probabilistic indication that segments are not undesired duplicate segments.

47. A computer program product as recited in claim 37, further including repacking data containers having eliminated segments.

48. A system for managing duplicate segments from a segmented file storage system including:

an indexer having one or more processors for indexing each of a plurality of segments with a correspondingly associated key, the index including an identification of a first data location where a first segment is stored;

an identifier having one or more processors for identifying a duplicate segment associated with a duplicate key matching a first key associated with the first segment and stored in a second data location;

a determiner having one or more processors for determining whether the duplicate segment is an undesired duplicate segment based at least in part on an amount of time that has passed since an operation associated with the duplicate segment; and

an eliminator having one or more processors for eliminating the duplicate segment if the duplicate segment is determined to be an undesired duplicate segment, wherein the duplicate segment is an undesired duplicate segment in the event the amount of time has passed since the operation associated with the duplicate segment, and retaining the duplicate segment if the duplicate segment is not determined to be an undesired duplicate segment, wherein the duplicate segment is not an undesired duplicate segment in the event the amount of time has not passed since the operation associated with the duplicate segment.

49. A system for managing duplicate segments from a segmented file storage system including:

an identifier having one or more processors identifying a first segment that is stored in a first data location, and identifying a second segment as being a duplicate of the first segment that is stored in a second data location;

a determiner having one or more processors for determining whether the second segment is an undesired duplicate to an object based at least in part on an amount of time that has passed since an operation associated with the second segment; and

an eliminator having one or more processors for eliminating the second segment if the second segment is determined to be an undesired duplicate segment, wherein the second segment is an undesired duplicate segment in the event the amount of time has passed since the operation associated with the second segment, and retaining the second segment if the second segment is not determined to be an undesired duplicate segment, wherein the second segment is not an undesired duplicate segment in the event the amount of time has not passed since the operation associated with the second segment,

wherein identifying the second segment as being a duplicate of the first segment includes loading and analyzing indexes for segments.