Adaptive compression using a sampling based heuristic

• US 8,806,062 B1
• Filed: 03/27/2009
• Issued: 08/12/2014
• Est. Priority Date: 03/27/2009
• Status: Active Grant

• Current Assignee: Veritas Technologies, LLC (Whitehouse Group Ltd.)
• Original Assignee: Symantec Corporation (NortonLifeLock Inc.)
• Inventors: Vertongen, Mark, Stougie, Bastiaan, Christiaens, Mark
• Primary Examiner(s): Dharia, Rupal
• Assistant Examiner(s): MCADAMS, BRAD
• Application Number:
  US12/413,137
• Time in Patent Office: 1,964 Days
• Field of Search: 709/247, 341/50
• US Class Current: 709/247
• CPC Class Codes: G06F 11/1451 by selection of backup contents
• CPC Class Codes: G06F 11/1464 for networked environments
• CPC Class Codes: H04L 67/5651 Reducing the amount or size of exchanged application data
• CPC Class Codes: H04L 69/04 Protocols for data compression, e.g. ROHC

Abstract

Various methods and systems for using adaptive data compression in a backup system are disclosed. One method involves detecting whether to compress a unit of storage that is to be backed up. The detecting involves attempting to compress a portion of the unit of storage. If the attempt to compress the portion of the unit of storage meets a specified compression performance threshold, i.e., if the unit of storage is compressible, the unit of storage is compressed. Otherwise the unit of storage is not compressed.

Claims

1. A method comprising:

detecting that a unit of storage from a backup client is to be backed up to a storage system;

in response to the detecting, determining whether to compress the unit of storage,

 

wherein the determining comprises

 

identifying a location within the unit of storage, wherein

the identifying comprises

scanning the unit of storage, wherein

the scanning comprises comparing density of data stored in

the unit of storage with a specified data density criterion, and

the specified data density criterion comprises a ratio of written storage location to unwritten storage locations,

determining whether the density of the data stored at the location meets the specified data density criterion prior to attempting to compress the data stored at the location, and

calculating an offset from the beginning of the unit of storage to the location,

selecting a portion of the unit of storage beginning at the offset, wherein data stored in the portion of the unit of storage comprises the data stored at the location,

the portion of the unit of storage is smaller than the unit of storage, and

the portion of the unit of storage begins at the offset from the beginning of the unit of storage and ends before the end of the unit of storage, and

attempting to compress the data stored in the portion of the unit of storage; and

if the attempting is successful for the portion of the unit of storage, compressing the entirety of the unit of storage.

2. The method of claim 1, wherein the detecting comprises:

detecting at least one of a modification of data in the unit of storage and the occurrence of a specified time interval.

3. The method of claim 1, wherein the detecting comprises:

calculating a hash value for the unit of storage; and

using the calculated hash value to detect whether the unit of storage exists on a backup server.

4. The method of claim 3, wherein the detecting is performed in parallel with the determining.

5. The method of claim 1, wherein the determining comprises calculating at least one of a compression efficiency and a compression time.

6. The method of claim 5, wherein

calculating the compression efficiency comprises calculating a ratio between a size of the portion after compression and a size of the portion prior to compression.

7. The method of claim 1, further comprising:

selecting a first compression algorithm for compressing the data stored in the portion based on a speed of the first compression algorithm; and

selecting a second compression algorithm for compressing the unit of storage based on an efficiency of the second compression algorithm, wherein

the first compression algorithm and second compression algorithm are different from one another.

8. The method of claim 1, further comprising:

encrypting the unit of storage; and

transmitting the unit of storage to a backup server.

9. A non-transitory computer readable storage medium storing program instructions, wherein the program instructions are executable by one or more processors to:

detect that a unit of storage from a backup client is to be backed up to a storage system;

in response to the detecting, determining whether to compress the unit of storage,

 

wherein the determining comprises

 

identifying a location within the unit of storage, wherein

the identifying comprises

scanning the unit of storage, wherein

the scanning comprises comparing density of data stored in

the unit of storage with a specified data density criterion, and

the specified data density criterion comprises a ratio of written storage location to unwritten storage locations,

determining whether the density of the data stored at the location meets the specified data density criterion prior to attempting to compress the data stored at the location, and

calculating an offset from the beginning of the unit of storage to the location,

selecting a portion of the unit of storage beginning at the offset, wherein data stored in the portion of the unit of storage comprises the data stored at the location,

the portion of the unit of storage is smaller than the unit of storage, and

the portion of the unit of storage begins at the offset from the beginning of the unit of storage and ends before the end of the unit of storage, and

attempting to compress the data stored in the portion of the unit of storage; and

if the attempting is successful for the portion of the unit of storage, compressing the entirety of the unit of storage.

10. The non-transitory computer readable storage medium of claim 9, wherein the detecting comprises:

detecting at least one of a modification of data in the unit of storage and the occurrence of a specified time interval.

11. The non-transitory computer readable storage medium of claim 9, wherein the detecting comprises:

calculating a hash value for the unit of storage; and

using the calculated hash value to detect whether the unit of storage exists on a backup server.

12. The non-transitory computer readable storage medium of claim 11, wherein the detecting is performed in parallel with the determining.

13. The non-transitory computer readable storage medium of claim 9, wherein the determining comprises:

calculating at least one of a compression efficiency and a compression time.

14. The non-transitory computer readable storage medium of claim 13, wherein calculating the compression efficiency comprises calculating a ratio between a size of the portion after compression and a size of the portion prior to compression.

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

select a first compression algorithm for compressing the data stored in the portion based on a speed of the first compression algorithm; and

select a second compression algorithm for compressing the unit of storage based on an efficiency of the second compression algorithm, wherein

the first compression algorithm and second compression algorithm are different from one another.

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

encrypt the unit of storage; and

transmit the unit of storage to a backup server.

17. A system comprising:

a storage system;

one or more processing means coupled to the storage system;

a backup client coupled to the storage system, the backup client comprising

means for detecting that a unit of storage is to be backed up;

means for determining whether to compress the unit of storage, wherein the determining is performed in response to the detecting and the determining comprises

 

identifying a location within the unit of storage, wherein

the identifying comprises

scanning the unit of storage, wherein

the scanning comprises comparing density of data stored in the unit of storage with a specified data density criterion, and

the specified data density criterion comprises a ratio of written storage locations to unwritten storage locations,

determining whether the density of the data stored at the location meets the specified data density criterion prior to attempting to compress the data stored at the location, and

calculating an offset from the beginning of the unit of storage,

 

selecting a portion of the unit of storage beginning at the offset, wherein

data stored in the portion of the unit of storage comprises the data stored at the location,

the portion of the unit of storage is smaller than the unit of storage, and

the portion of the unit of storage begins at the offset from the beginning of the unit of storage and ends before the end of the unit of storage, and

 

attempting to compress the data stored in the portion of the unit of storage; and

means for compressing the entirety of the unit of storage if the determining means indicates that the attempting is successful for the portion of the unit of storage.

18. The system of claim 17, further comprising:

means for selecting a first compression algorithm for compressing the data stored in the portion based on a speed of the first compression algorithm; and

means for selecting a second compression algorithm for compressing the unit of storage based on an efficiency of the second compression algorithm, wherein

the first compression algorithm and second compression algorithm are different from one another.