Deduplication featuring variable-size duplicate data detection and fixed-size data segment sharing

• US 10,656,858 B1
• Filed: 10/07/2016
• Issued: 05/19/2020
• Est. Priority Date: 12/15/2012
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Inventors: Karr, Ronald, Bromley, Graham, Patil, Deepak
• Primary Examiner(s): Jami, Hares
• Application Number:
  US15/288,001
• Time in Patent Office: 1,320 Days
• Field of Search: 707687, 707692, 707694
• 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/1752 based on file chunks
• CPC Class Codes: G06F 3/06 Digital input from, or digital output to, record carriers , e.g. RAID, emulated record carriers or networked record carriers
• 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/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]

Abstract

A hybrid deduplication system operates to detect variable-sized deduplication matches, while performing the storage deduplication on fixed-size segments of data. The hybrid deduplication system calculates unique identifiers for variable-sized sections of data within a data stream being written to a deduplicated data store. The hybrid deduplication system then compares those newly-calculated identifiers to identifiers of variable-sized sections of data that have already been stored within the deduplicated data store. If a match is found, the hybrid deduplication system identifies the location of each of the fixed-size data segment(s), already stored in the deduplicated data store, that include the identified variable-sized section of data. Instead of writing the sections that match already-existing sections to the deduplicated data store, the hybrid deduplication system simply causes the creation of a reference to the identified storage locations, indicating that the data stream being written includes the data in these pre-existing storage locations.

Claims

1. A method comprising:

receiving a data stream;

dividing the data stream into a plurality of variable-sized sections;

calculating a fingerprint for a first variable-sized section of the plurality of variable-sized sections, wherein

the fingerprint is calculated as a function of all data within the first variable-sized section;

determining whether the fingerprint matches a stored fingerprint;

in response to determining that the fingerprint matches the stored fingerprint, identifying a fixed-length data segment in storage that contains a copy of data in the first variable-sized section, wherein

the fixed-length data segment comprises

the copy, and

additional data that is not found in the first variable-sized section;

replacing the first variable-sized section with a plurality of references including a reference to the fixed-length data segment; and

updating a reference file to identify

the fixed-length data segment,

a first portion of data in the fixed-length data segment that corresponds to the copy, and

a second portion of data in the fixed-length data segment that corresponds to the additional data.

2. The method of claim 1, further comprising:

calculating a second fingerprint corresponding to a second variable-sized section of the plurality of variable-sized sections;

determining that the second fingerprint does not match any stored fingerprint;

in response to determining that the second fingerprint does not match any stored fingerprint, store fixed-length data segments of the second variable-sized section in the storage; and

replacing the second variable-sized section with a plurality of references including the references to the fixed-length data segments of the second variable-sized section in the storage.

3. The method of claim 1, wherein

at least two or more of the plurality of variable-sized sections comprise unaligned common data.

4. A non-transitory computer readable storage medium comprising program instructions executable by one or more processors to perform a method comprising:

receiving a data stream;

dividing the data stream into a plurality of variable-sized sections;

calculating a fingerprint for a first variable-sized section of the plurality of variable-sized sections, wherein

the fingerprint is calculated as a function of all data within the first variable-sized section;

determining whether the fingerprint matches a stored fingerprint;

in response to determining that the fingerprint matches the stored fingerprint, identifying a fixed-length data segment in storage that contains a copy of data in the first variable-sized section, wherein

the fixed-length data segment comprises

the copy, and

additional data that is not found in the first variable-sized section;

replacing the first variable-sized section with a plurality of references including a reference to the fixed-length data segment; and

updating a reference file to identify

the fixed-length data segment,

a first portion of data in the fixed-length data segment that corresponds to the copy, and

a second portion of data in the fixed-length data segment that corresponds to the additional data.

5. The non-transitory computer readable storage medium of claim 4, wherein the method further comprises:

calculating a second fingerprint corresponding to a second variable-sized section of the plurality of variable-sized sections;

determining that the second fingerprint does not match any stored fingerprint;

in response to determining that the second fingerprint does not match any stored fingerprint, store fixed-length data segments of the second variable-sized section in the storage; and

replacing the second variable-sized section with a plurality of references including the references to the fixed-length data segments of the second variable-sized section in the storage.

6. The non-transitory computer readable storage medium of claim 4, wherein

at least two or more of the plurality of variable-sized sections comprise unaligned common data.

7. A system comprising:

one or more processors; and

a memory storing program instructions executable by the one or more processors to perform a method comprising;

receiving a data stream;

dividing the data stream into a plurality of variable-sized sections;

calculating a fingerprint for a first variable-sized section of the plurality of variable-sized sections, wherein

the fingerprint is calculated as a function of all data within the first variable-sized section;

determining whether the fingerprint matches a stored fingerprint;

in response to determining that the fingerprint matches the stored fingerprint, identifying a fixed-length data segment in storage that contains a copy of data in the first variable-sized section, wherein

the fixed-length data segment comprises

the copy, and

additional data that is not found in the first variable-sized section;

replacing the first variable-sized section with a plurality of references including a reference to the fixed-length data segment; and

updating a reference file to identify

the fixed-length data segment,

a first portion of data in the fixed-length data segment that corresponds to the copy, and

a second portion of data in the fixed-length data segment that corresponds to the additional data.

8. The system of claim 7, wherein the method further comprises:

calculating a second fingerprint corresponding to a second variable-sized section of the plurality of variable-sized sections;

determining that the second fingerprint does not match any stored fingerprint;

in response to determining that the second fingerprint does not match any stored fingerprint, store fixed-length data segments of the second variable-sized section in the storage; and

replacing the second variable-sized section with a plurality of references including the references to the fixed-length data segments of the second variable-sized section in the storage.

9. The system of claim 7, wherein

at least two or more of the plurality of variable-sized sections comprise unaligned common data.