DEDUPLICATING STORAGE WITH ENHANCED FREQUENT-BLOCK DETECTION

• US 20130290277A1
• Filed: 04/30/2012
• Published: 10/31/2013
• Est. Priority Date: 04/30/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Chambliss, David D., Constantinescu, Mihail C., Glider, Joseph S., Lu, Maohua
• Granted Patent: US 9,177,028 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/955 using information identifiers, e.g. uniform resource locators [URL]

Abstract

Detecting data duplication comprises maintaining a fingerprint directory including one or more entries, each entry including a data fingerprint and a data location for a data chunk. Each entry is associated with a seen-count attribute which is an indication of how often the fingerprint has been seen in arriving data chunks. Higher-frequency entries in the directory are retained, while also taking into account recency of data accesses. A data duplication detector detects that the data fingerprint for a new chunk is the same as the data fingerprint contained in an entry in the fingerprint directory.

Claims

1. A method for detecting data duplication, comprising:

maintaining a fingerprint directory comprising one or more entries, each entry including a data fingerprint and a data location for a data chunk;

associating each said entry with a seen-count attribute which is an indication of how often the fingerprint has been seen in arriving data chunks;

retaining higher-frequency entries, while also taking into account recency of data accesses; and

detecting that the data fingerprint for a new chunk is the same as the data fingerprint contained in an entry in the fingerprint directory.

2. The method of claim 1, wherein:

the fingerprint directory comprises a multiply-seen entry which has been found, and a once-seen entry which is inserted more recently, and the fingerprint module discards the once-seen entry substantially sooner than the multiply-seen entry; and

the seen-count attribute provides the distinction between a multiply-seen entry and a once-seen entry.

3. The method of claim 2, further comprising:

maintaining a shadow list module including a shadow list comprising a record of fingerprint values not contained in the fingerprint directory;

detecting that the data fingerprint for a new chunk is contained in the shadow list;

removing the data fingerprint for said new chunk from the shadow list; and

adding to the fingerprint directory an entry containing the data fingerprint and the data location of the new chunk.

4. The method of claim 3, further comprising:

adding to the shadow list the data fingerprint for a new chunk whose data fingerprint was not found in the fingerprint directory by the duplicate detection module.

5. The method of claim 3, further comprising:

discarding a once-seen entry from the fingerprint directory and adding to the shadow list the data fingerprint from the discarded entry.

6. The method of claim 3, wherein:

the shadow list further comprises a probabilistic set-object data structure with a bounded error rate.

7. The method of claim 6, wherein:

the probabilistic set-object data structure comprises a set-object data structure on a collapsed key.

8. The method of claim 6, wherein:

the probabilistic set-object data structure comprises a Bloom filter.

9. A computer program product for detecting data duplication, the computer program product comprising:

a tangible storage medium readable by a computer system and storing instructions for execution by the computer system for performing a method comprising;

maintaining a fingerprint directory comprising one or more entries, each entry including a data fingerprint and a data location for a data chunk;

associating each said entry with a seen-count attribute which is an indication of how often the fingerprint has been seen in arriving data chunks;

retaining higher-frequency entries, while also taking into account recency of data accesses; and

detecting that the data fingerprint for a new chunk is the same as the data fingerprint contained in an entry in the fingerprint directory.

10. The computer program product of claim 9, wherein:

the fingerprint directory comprises a multiply-seen entry which has been found, and a once-seen entry which is inserted more recently, and the fingerprint module discards the once-seen entry substantially sooner than the multiply-seen entry; and

the seen-count attribute provides the distinction between a multiply-seen entry and a once-seen entry.

11. The computer program product of claim 10, further comprising:

maintaining a shadow list module including a shadow list comprising a record of fingerprint values not contained in the fingerprint directory;

detecting that the data fingerprint for a new chunk is contained in the shadow list;

removing the data fingerprint for said new chunk from the shadow list; and

adding to the fingerprint directory an entry containing the data fingerprint and the data location of the new chunk.

12. The computer program product of claim 11, wherein:

the shadow list further comprises a probabilistic set-object data structure.

13. A system for detecting data duplication, comprising:

a fingerprint controller that maintains a fingerprint directory comprising one or more entries, each entry including a data fingerprint and a data location for a data chunk in a storage device;

wherein each entry is associated with a seen-count attribute which is an indication of how often the fingerprint has been seen in arriving data chunks, and wherein the fingerprint controller retains higher-frequency entries, while also taking into account recency of data accesses; and

a duplicate detector that detects if the data fingerprint for a new chunk is the same as the data fingerprint contained in an entry in the fingerprint directory.

14. The system of claim 13, wherein:

the fingerprint directory comprises a multiply-seen entry which has been found, and a once-seen entry which is inserted more recently, and the fingerprint controller discards the once-seen entry substantially sooner than the multiply-seen entry; and

the seen-count attribute provides the distinction between a multiply-seen entry and a once-seen entry.

15. The system of claim 14, further comprising:

a shadow list controller maintaining a shadow list comprising a record of fingerprint values not contained in the fingerprint directory;

wherein the shadow list controller detects that the data fingerprint for a new chunk is contained in the shadow list, removes the data fingerprint for said new chunk from the shadow list, and adds to the fingerprint directory an entry containing the data fingerprint and the data location of the new chunk.

16. The system of claim 15, wherein:

the shadow list controller adds to the shadow list the data fingerprint for a new chunk whose data fingerprint was not found in the fingerprint directory by the duplicate detector.

17. The system of claim 15, wherein:

fingerprint controller discards a once-seen entry from the fingerprint directory and adds to the shadow list the data fingerprint from the discarded entry.

18. The system of claim 15, wherein:

the shadow list further comprises a probabilistic set-object data structure with a bounded error rate.

19. The system of claim 18, wherein the probabilistic set-object data structure comprises a set-object data structure on a collapsed key.

20. The system of claim 18, wherein the probabilistic set-object data structure comprises a Bloom filter.