Deduplication featuring variable-size duplicate data detection and fixed-size data segment sharing
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.
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.