Merged collections

• US 8,126,852 B1
• Filed: 12/01/2008
• Issued: 02/28/2012
• Est. Priority Date: 12/07/2007
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Patterson, R. Hugo
• Primary Examiner(s): Hashemi, Sana Al
• Application Number:
  US12/315,374
• Time in Patent Office: 1,184 Days
• Field of Search: 707/615, 707/680, 707/791, 707/795, 707/803, 707/812, 707/825
• US Class Current: 707/680
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/1748 De-duplication implemented within the file system, e.g. based on file segments de-duplication techniques in storage systems for the management of data blocks G06F3/0641
• CPC Class Codes: G06F 16/1844 Management specifically adapted to replicated file systems

Abstract

A method of determining whether a data segment is a duplicate using cooperating deduplicators is disclosed. The data segment is received. A first deduplicator is operated to to determine whether the incoming data segment is a duplicate based on first information available to the first deduplicator regarding stored data segments that are stored in a memory. A second deduplicator is selectively operated to determine whether the incoming data segment is a duplicate based on second information available to the second deduplicator; wherein the selective operation of the second deduplicator depends on the determination made by the first deduplicator.

Claims

1. A method of determining whether a data segment is a duplicate using cooperating deduplicators, including:

receiving the data segment;

operating a first deduplicator to determine whether the incoming data segment is a duplicate based on first information available to the first deduplicator regarding stored data segments that are stored in a memory by generating a digital signature for the incoming data segment and comparing it to the first information;

in the event the first deduplicator determines the data segment is a duplicate;

     1) avoiding operating a second deduplicator and

     2) adding a mapping for the incoming data segment to the first information; and

in the event the first deduplicator determines the data segment is not a duplicate;

operating a second deduplicator to determine whether the incoming data segment is a duplicate based on second information available to the second deduplicator.

3. A method of claim 1, wherein the first deduplicator is a primary deduplicator and the second deduplicator is a secondary deduplicator.

4. A method of claim 3, wherein a deduplicator, when operating, determines whether a specific data segment is a duplicate based in part on deduplicator information, wherein deduplicator information comprises a set of references associated with segments.

5. A method of claim 3, wherein the primary deduplicator sends a reference associated with the data segment to the secondary deduplicator that includes an indication whether the data segment was determined to be a duplicate by the primary deduplicator.

6. A method of claim 3, wherein the primary deduplicator sends a reference associated with the data segment to the secondary deduplicator that implies whether the data segment was determined to be a duplicate by the primary deduplicator.

7. A method of claim 3, wherein the primary deduplicator stores in a primary deduplicator memory a first set of data segments comprising all data segments referenced in the primary information.

8. A method of claim 3, wherein the primary deduplicator stores in a primary deduplicator memory a first set of data segments comprising one or more data segments referenced in the primary information.

9. A method of claim 3, wherein the primary deduplicator stores in a primary deduplicator memory no data segments.

10. A method of claim 3, wherein the secondary deduplicator stores data segments in the memory.

11. A method of claim 3, wherein the primary deduplicator sends a list of references to segments to the secondary deduplicator.

12. A method of claim 3, wherein the primary deduplicator sends an increment to a list of references to segments to the secondary deduplicator, wherein an increment comprises an indication for a new entry to the list.

13. A method of claim 3, wherein the primary deduplicator sends an increment to a list of references to segments to the secondary deduplicator, wherein an increment comprises an indication for an expired entry from the list.

14. A method of claim 3, wherein the primary information is associated with a greater number of segments than the secondary information.

15. A method of claim 3, wherein the primary information is associated with a lesser number of segments than the secondary information.

16. A method of claim 3, wherein the primary information is associated with an equal number of segments than the secondary information.

17. A method of claim 3, wherein the primary deduplicator and the secondary deduplicator are part of a combined system.

18. A method of claim 3, further including selectively operating the primary deduplicator to determine whether a specified data segment is a duplicate, wherein the selective operation of the primary deduplicator and the specified data segment depend on the determination made by the secondary deduplicator.

19. A method of claim 3, wherein the determination of the primary deduplicator includes a fingerprint for the incoming data segment.

20. A method of claim 3, wherein the determination of the primary deduplicator includes a fingerprint for the incoming data segment grouped in a stream order.

21. A method of claim 3, further including:

operating a second primary deduplicator to determine whether the incoming data segment is a duplicate based on a second primary information available to the second primary deduplicator regarding stored data segments that are stored in a memory; and

wherein the selective operation of the secondary deduplicator depends also on the determination made by the second primary deduplicator.

22. A method of claim 3, wherein the primary deduplicator is part of a primary storage system and the secondary deduplicator is part of a replica storage system.

23. A method of claim 22, wherein the primary storage system sends a reference associated with the data segment to the replica storage system that includes an indication whether the data segment was determined to be a duplicate by the primary storage system.

24. A method of claim 22, wherein the primary storage system sends a reference associated with the data segment to the replica storage system that implies whether the data segment was determined to be a duplicate by the primary storage system.

25. A method of claim 22, further including:

operating a second primary deduplicator to determine whether the incoming data segment is a duplicate based on a second primary information available to the second primary deduplicator regarding stored data segments that are stored in a memory;

wherein the selective operation of the secondary deduplicator depends also on the determination made by the second primary deduplicator; and

wherein the second primary deduplicator is part of a second primary storage system.

26. A method of claim 3, further including:

selectively operating a tertiary deduplicator to determine whether the incoming data segment is a duplicate based on tertiary information available to the tertiary deduplicator;

wherein the selective operation of the tertiary deduplicator depends on the determination made by the secondary deduplicator.

27. A method of claim 3, further including:

operating a second primary deduplicator to determine whether a second incoming data segment is a duplicate based on second primary information available to the second primary deduplicator regarding stored data segments that are stored in a second memory;

selectively operating a second secondary deduplicator to determine whether the second incoming data segment is a duplicate based on second secondary information available to the second secondary deduplicator;

wherein the selective operation of the second secondary deduplicator depends on the determination made by the second primary deduplicator;

selectively operating the secondary deduplicator to determine whether the second incoming data segment is a duplicate based on third secondary information available to the secondary deduplicator;

wherein the selective operation of the secondary deduplicator depends on the determination made by the second primary deduplicator; and

selectively operating the second secondary deduplicator to determine whether the incoming data segment is a duplicate based on fourth secondary information available to the second secondary deduplicator;

wherein the selective operation of the second secondary deduplicator depends on the determination made by the primary deduplicator.

2. A system of determining whether a data segment is a duplicate, including:

a primary deduplicator configured to operate to determine whether an incoming data segment is a duplicate based on primary information available to the primary deduplicator regarding stored data segments that are stored in a memory by generating a digital signature for the incoming data segment and comparing it to the first information, wherein in the event the first deduplicator determines the data segment is a duplicate, a mapping is added for the incoming data segment to the first information; and

a secondary deduplicator configured to;

in the event the first deduplicator determines the data segment is a duplicate;

avoid operating; and

in the event the first deduplicator determines the data segment is not a duplicate;

determine whether the incoming data segment is a duplicate based on secondary information available to the secondary deduplicator.