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

• US 9,465,808 B1
• Filed: 12/15/2012
• Issued: 10/11/2016
• 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:
  US13/716,123
• Time in Patent Office: 1,396 Days
• Field of Search: 707/687, 707/692, 707/694
• US Class Current: 1/1
• 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:

storing a plurality of fixed-size data segments on a storage device;

calculating a plurality of stored identifiers, wherein

a first stored identifier of the plurality of stored identifiers identifies a sub-portion of a first fixed-size data segment of the plurality of fixed-size data segments;

calculating a plurality of identifiers for respective sections of a data stream generated by a client, in response to detecting that the data stream is being written, or is selected to be written, to the storage device, wherein

the data stream comprises two variable-length data segments, and

the plurality of identifiers comprise a first identifier for a first section of the data stream;

detecting that the first identifier matches a first stored identifier; and

in response to the detecting, causing an additional reference to be generated instead of writing the first section of the data stream to the storage device as part of a deduplicated data stream, wherein

the deduplicated data stream is associated with a reference stream,

the additional reference is included as part of the reference stream,

the additional reference identifies the sub-portion of the first fixed-size data segment as part of the data stream, and

the first fixed-size data segment has a different length than the first section of the data stream, and

the calculating, the detecting, and the causing are performed by a computing device implementing a deduplication module, wherein

the reference stream identifies every fixed-size data segment of the plurality of fixed-size data segments that comprises at least one portion of a variable-length data segment of the two variable-length data segments even if the first fixed-size data segment comprises data that is not part of the variable-length data segment.

2. The method of claim 1, further comprising:

detecting that a second identifier for a second section of the data stream does not match any of the stored identifiers;

adding the second identifier to the plurality of stored identifiers; and

writing the second section of the data stream to the storage device as one or more additional fixed-size data segments.

3. The method of claim 2, wherein

the adding comprises overwriting one of the plurality of stored identifiers with the second identifier.

4. The method of claim 1, wherein

the causing the additional reference to be generated comprises causing a file system to identify that both the data stream and the plurality of fixed-size data segments include the sub-portion of the first fixed-size data segment.

5. The method of claim 1, wherein

the plurality of fixed-size data segments comprises a first backup stream and the data stream is a second backup stream.

6. The method of claim 5, wherein

the first backup stream is a backup of a first client and the second backup stream is a backup of a second client.

7. The method of claim 1, further comprising

a file system tracking how many data streams include the sub-portion of the first fixed-size data segment and preventing deletion of the sub-portion of the first fixed-size data segment from the storage device as long as any data stream stored on the storage device still includes the sub-portion of the first fixed-size data segment.

8. The method of claim 1, wherein

the reference stream comprises information identifying a portion of the first fixed-size data segment that is part of the variable-length data segment.

9. The method of claim 1, wherein

the client is one of a plurality of clients,

the reference stream is one of a plurality of reference streams, and

each client of the plurality of clients is associated with at least one reference stream of the plurality of reference streams.

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

store a plurality of fixed-size data segments on a storage device;

calculate a plurality of stored identifiers, wherein

a first stored identifier of the plurality of stored identifiers identifies a sub-portion of a first fixed-size data segment of the plurality of fixed-size data segments;

calculate a plurality of identifiers for respective sections of a data stream generated by a client, in response to detecting that the data stream is being written, or is selected to be written, to the storage device, wherein

the data stream comprises two variable-length data segments, and

the plurality of identifiers comprise a first identifier for a first section of the data stream;

detect that the first identifier matches a first stored identifier; and

in response to the detecting, causing an additional reference to be generated instead of writing the first section of the data stream to the storage device as part of a deduplicated data stream, wherein

the deduplicated data stream is associated with a reference stream,

the additional reference is included as part of the reference stream,

the additional reference identifies the sub-portion of the first fixed-size data segment as part of the data stream, and

the first fixed-size data segment has a different length than the first section of the data stream, and

the calculating, the detecting, and the causing are performed by a computing device implementing a deduplication module, wherein

the reference stream identifies every fixed-size data segment of the plurality of fixed-size data segments that comprises at least one portion of a variable-length data segment of the two variable-length data segments even if the first fixed-size data segment comprises data that is not part of the variable-length data segment.

11. The non-transitory computer readable storage medium of claim 10, wherein the program instructions are further executable to:

detect that a second identifier for a second section of the data stream does not match any of the stored identifiers;

add the second identifier to the plurality of stored identifiers; and

write the second section of the data stream to the storage device as one or more additional fixed-size data segments.

12. The non-transitory computer readable storage medium of claim 11, wherein adding the second identifier comprises overwriting one of the plurality of stored identifiers with the second identifier.

13. The non-transitory computer readable storage medium of claim 10, wherein causing the additional reference to be generated comprises causing a file system to identify that both the data stream and the plurality of fixed-size data segments include the sub-portion of the first fixed-size data segment.

14. The non-transitory computer readable storage medium of claim 10, wherein the plurality of fixed-size data segments comprises a first backup stream and the data stream is a second backup stream.

15. The non-transitory computer readable storage medium of claim 14, wherein the first backup stream is a backup of a first client and the second backup stream is a backup of a second client.

16. The non-transitory computer readable storage medium of claim 10, wherein the program instructions are further executable to implement a file system configured to track how many data streams include the sub-portion of the first fixed-size data segment and preventing deletion of the sub-portion of the first fixed-size data segment from the storage device as long as any data stream stored on the storage device still includes the sub-portion of the first fixed-size data segment.

17. A system comprising:

one or more processors; and

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

store a plurality of fixed-size data segments on a storage device;

calculate a plurality of stored identifiers, wherein

a first stored identifier of the plurality of stored identifiers identifies a sub-portion of a first fixed-size data segment of the plurality of fixed-size data segments;

calculate a plurality of identifiers for respective sections of a data stream generated by a client, in response to detecting that the data stream is being written, or is selected to be written, to the storage device, wherein

the data stream comprises two variable-length data segments, and

the plurality of identifiers comprise a first identifier for a first section of the data stream;

detect that the first identifier matches a first stored identifier; and

in response to the detecting, causing an additional reference to be generated instead of writing the first section of the data stream to the storage device as part of a deduplicated data stream, wherein

the deduplicated data stream is associated with a reference stream,

the additional reference is included as part of the reference stream,

the additional reference identifies the sub-portion of the first fixed-size data segment as part of the data stream, and

the first fixed-size data segment has a different length than the first section of the data stream, and

the calculating, the detecting, and the causing are performed by a computing device implementing a deduplication module, wherein

the reference stream identifies every fixed-size data segment of the plurality of fixed-size data segments that comprises at least one portion of a variable-length data segment of the two variable-length data segments even if the first fixed-size data segment comprises data that is not part of the variable-length data segment.

18. The system of claim 17, wherein the program instructions are further executable to:

detect that a second identifier for a second section of the data stream does not match any of the stored identifiers;

add the second identifier to the plurality of stored identifiers; and

write the second section of the data stream to the storage device as one or more additional fixed-size data segments.

19. The system of claim 17, wherein causing the additional reference to be generated comprises causing a file system to identify that both the data stream and the plurality of fixed-size data segments include the sub-portion of the first fixed-size data segment.

20. The system of claim 17, wherein the plurality of fixed-size data segments comprises a first backup stream and the data stream is a second backup stream.

21. The system of claim 20, wherein the first backup stream is a backup of a first client and the second backup stream is a backup of a second client.

22. The system of claim 17, the program instructions are further executable to implement a file system configured to track how many data streams include the sub-portion of the first fixed-size data segment and preventing deletion of the sub-portion of the first fixed-size data segment from the storage device as long as any data stream stored on the storage device still includes the sub-portion of the first fixed-size data segment.

23. A method comprising:

storing a plurality of fixed-size data segments on a storage device, wherein the plurality of fixed-size data segments comprises a first backup data stream associated with a first client;

calculating a plurality of stored identifiers, wherein a first stored identifier of the plurality of stored identifiers identifies a sub-portion of a first fixed-size data segment of the plurality of fixed-size data segments;

calculating a plurality of identifiers for respective sections of a backup data stream generated by a client in response to detecting that the second backup data stream is being written, or is selected to be written, to the storage device, wherein the data stream comprises two variable-length data segments, and wherein the second backup data stream is associated with a second client, and wherein the plurality of identifiers comprise a first identifier for a first section of the second backup data stream;

detecting that the first identifier matches the first stored identifier; and

in response to the detecting, causing an additional reference to be generated instead of writing the first section of a second backup data stream to the storage device as part of a deduplicated data stream, wherein the deduplicated data stream is associated with a reference stream and the additional reference is included as part of the reference stream, wherein the additional reference identifies the sub-portion of the first fixed-size data segment as part of the second backup data stream, wherein the first fixed-size data segment has a different length than the first section of the second backup data stream, and wherein the calculating, the detecting, and the causing are performed by a computing device implementing a deduplication module, wherein

the reference stream identifies every fixed-size data segment of the plurality of fixed-size data segments that comprises at least one portion of a variable-length data segment of the two variable-length data segments even if the first fixed-size data segment comprises data that is not part of the variable-length data segment.