Deduplication vs. compression: two concepts in data reduction

According to market research company IDC, the amount of data that exists in the world is doubled every 24 months. At this rate, the digital universe is set to have a volume of 44 zettabytes by 2020. This figure is calculating by converting the 44 trillion gigabytes of data produced or copied in one year. This development primarily affects storage techniques, backup procedures, and recovery systems, which must be capable of carrying and handling enormous loads of data. The concept of technical implementation focuses on the reduction of physically stored information, thereby reducing the costs of data management. These methods are essentially based on two concepts: data compression and deduplication. While the loss-free compression uses redundancies within a file to compress data, deduplication algorithms mirror data across files to avoid duplicates. The main application for deduplication is therefore data backups.

Deduplication is a process of data reduction that is essentially based on preventing data redundancies in the storage system. For this, a deduplication engine is used, which generates special algorithms to identify and eliminate redundant files and data blocks. This can be integrated into backup software or hardware used for storing information, or implemented as an intermediary appliance.

The aim of deduplication in storage techniques is to write only as much information on non-volatile storage media as is necessary to be able to reconstruct a file without losses. The more duplicates are deleted, the smaller the data volume that needs to be stored or transferred becomes. The identification of duplicates can be done at file-level with Git or Dropbox, for example. However, a more efficient method is the use of deduplication algorithms, which work on a sub-file level. To do this, files are first broken down into data blocks (chunks) and awarded unique checksums, or hash values. The tracking database, which contains every checksum, acts as the central supervisory entity.

The block-based deduplication methods can be broken down into two variations:

• Deduplication with a fixed block size: for deduplications with a fixed block size, the algorithm divides files into sections of the exact same length. This is generally based on the cluster size of the file or RAID system (typically 4KB), but can also sometimes be configured manually. In this case, the individually-adjusted block size is adopted as the standard size for all data blocks.

• Deduplication with variable block size: with deduplication with variable block sizes, on the other hand, no specific standard size is defined. Instead, the algorithm divides the data into different blocks, whose lengths vary depending on the type of data that is to be processed.

The type of block division has a massive influence on the efficiency of the data duplication. This is especially noticeable when deduplicated files are subsequently modified.

If a data block with fixed block boundaries is extended with additional information, the contents of all subsequent blocks are usually also relocated in relation to the fixed block boundaries. Although the changes only affect one data block, all subsequent segments of a file will also be classified as new due to the change in the block boundaries by the deduplication algorithm. Unless modified bytes are exactly one multiple of the fixed block size. Since these are saved as newly reclassified data blocks, both the computing effort and the capacity of the bandwidth are increased in the case of a backup with a deduplication with a fixed block size.

If, on the other hand, an algorithm uses variable block boundaries, the modifications of an individual data block have no effect on the next segments. Instead, the modified data block is simply extended and stored with the new bytes. This relieves the burden on the network, as less data is transferred during a backup procedure. However, the flexibility of the file changes is more computing-intensive, as the algorithm must first find out how the chunks are split up.

Identifying redundant chunks is based on the assumption that data blocks with identical hash values contain identical information. To filter out redundant chunks, the deduplication algorithm just needs to synchronise newly calculated hash values with the tracking database. If it finds identical checksums, the redundant chunks are replaced by identifying the storage location of the identical data block with a pointer. A pointer like this takes up far less space than the data block itself. The more chunks in a file can be replaced by placeholders, the less memory space is required. However, the efficiency of data reduction can’t by predicted by deduplication algorithms, as this is strongly dependent on the output file and its data structure. In addition, deduplication is only suitable for unencrypted data. Redundancies are intentionally avoided with encryption systems; this makes any pattern recognition impossible.

Deduplication can be carried out either in the storage destination or at the data source.

If redundant data is removed before being transferred to the storage destination, it’s known as source deduplication. In this case, the deduplication engine is integrated into the backup software. Redundant information is eliminated directly in the data source’s file system. To do this, the backup software scans newly-created data blocks at regular intervals and compares them with the ones already saved on the backup server. If a redundant data block is found, it’s skipped during the next backup procedure. If a file is modified, the backup software simply transfers the new parts of the file.

The major advantage of these deduplication methods is that only new information is transferred to the backup server as part of the data backup. This lessens the bandwidth usage as well as the necessary capacity of the storage destination. But unlike deduplication at the storage destination, the source-based method requires a far higher computing effort, so that it is not suitable for every scenario.

The following code can be used for the characters of the example sentence:

While frequently occurring characters such as space, a, and e are only encoded with 3 bits in this example, the lesser used characters such as r, u, and x require 5 bits. In comparison, the ASCII character set, for example, uses 7 bits per character. However, in ASCII-compatible character sets, such as UTF-8 or ISO 8859-1 (Latin-1), an eighth bit is usually added for modern computers, which work with 8, 16, 32, or 64 bits. This demonstrates that texts can be saved far more compactly with Huffman coding.

The following binary sequence shows the example sentence ‘This is an example of a Huffman tree’ according to Huffman coding:

0110 1010 1000 1011 111 1000 1011 111 010 0010 111 000 10010 010 0111 10011 11001 000 111 00110 1101 111 010 111 1010 00111 1101 1101 0111 010 0010 111 0110 11000 000 000

In comparison, below is the bit sequence for the same content according to ASCII coding, with the added eighth bit (the first zero, respectively):

01110100 01101000 01101001 01110011 00100000 01101001 01110011 00100000 01100001 01101110 00100000 01100101 01111000 01100001 01101101 01110000 01101100 01100101 00100000 01101111 01100110 00100000 01100001 00100000 01101000 01110101 01100110 01100110 01101101 01100001 01101110 00100000 01110100 01110010 01100101 01100101

With Huffman coding, data can be reduced to up to 1/3 of its original size, depending on the distribution of character frequency. Users should note, however, that the tree must also be saved for all subsequent decoding.

Huffman coding has other uses besides compressing text files, however; the method can also be used during a JPEG image compression process and in a zip format that is a combination of LZSS and Huffman.

While loss-free data compression is only possible when redundancies are found within a file, lossy data compression, which is based on irrelevance reduction, is always possible ­– if data loss is accepted. As a basic principle, data compression that is subject to loss always comprises of a decision as to which proportion of the original data is dispensable. The theoretical limit for maximum compression can be explored with the rate distortion theory, which describes the relationship between compression and signal quality.

Lossy compression methods are generally adapted to human perception. For example, during the compression of an audio file (i.e. MP3, AAC, or WMA), the frequency components that lie outside of the human auditory range are deleted. One common example of irrelevance reduction in the image sector is the JPEG method, which combines both loss-free and lossy compression methods. The latter includes, for example, the colour conversion of the RGB spectrum into the YCbCr color model, the discrete cosinus transformation (DCT), as well as quantisation.

Deduplication is generally used by companies to implement a backup procedure or to optimise the storage methods in standard file systems. This is because deduplication systems work extremely efficiently if identical files are to be stored.

Data compression methods, on the other hand, generally cause a higher computing effort, requiring far more complex platforms. Storage systems work most effectively in a combination of both data reduction methods. With deduplication, redundancies are first deleted from the files that are to be saved, and the remaining data is subsequently compressed.