Seeking to address some misconceptions on the subject of deduplication, Joerg Moellenkamp's blog "To dedup or not to dedup - that results in a lot of questions" provides a primer on the process. There are two major ways to deduplicate, he writes: synchronous and asynchronous. The synchronous variant does the deduplication while writing to the disks, so duplicates aren't written to disk; the asynchronous variant writes every block to the disk and later on it deletes duplicated blocks by searching possible candidates.

There is more than one method of finding candidate files, Moellenkamp continues, identifying one as "the brute force method," which he labels as inefficient. Another approach involves mathematical algorithms called hash algorithms that allow users to condense a large set of data to a small set of data. One calculates them for every block, and puts them in a table. When you write a new block, you calculate the hash, look if there is already a block with the checksum and so you have a candidate block for deduplication, Moellenkamp explains.

He also identifies two variants of the hash-based algorithms: Hash-only and Hash-and-compare. Hash-only, he continues, is based on the assumption, that with a hash function with a low probability of hash collision, you can assume, that two blocks with equal hashes are indeed equal and thus deduplicatable. Hash-and-compare doesn't trust the hash, and compares possible candidates for deduplication with the block that should end in a pointer instead of a entirely written block. Only in the case of proven duplication does it get deduplicated, he reports.

So, the decision synchronous/asynchronous is made on the foundation of the time to make the decision to dedup or not to dedup, according to Moellenkamp. If you can make this decision in a very short time, you can do it synchronously. If the decision is resource-intensive and/or takes a long time, you do it asynchronously, he maintains.

No fan of the brute force method, Mollenkamp notes that the needed time for deduplication is to find a candidate and to check its having been duplicated. The brute force method would take a long time and would be implemented in an asynchronous way.

On the other hand, the hashing method is a little bit more complex, he continues. With a modern CPU you can safely ignore the time to compute the hashes. Furthermore, finding candidates for deduplication is done with tables. When the database fits in memory it's extremely fast; if you have to access your disks, it gets slower, which is the reason why ZFS deduplication is speeded up by SSD L2ARC by a large margin with large filesystems, he observes.

This said, Moellenkamp asserts that the hash gets important: Finding candidates is fast with any hash algorithm. So this phase is irrelevant for your design decision if you use synchronous or asynchronous deduplication. The second phase - checking for duplication - is the interesting one.

With a weak checksum, you will find many possible candidates as each hash bucket is filled with many blocks, though only one is a real duplicate, however, so you have to read many blocks to check for this real duplicate, Moellenkamp writes, noting that this takes time and eats away your precious resource IOPS. So you do it asynchronously in times where you have some spare IOPS.

With a strong checksum, on the other hand, the possibility is high that a deduplication candidate is really a duplicate: The stronger the checksum, the higher the probability. When you do asynchronous deduplication, you may find several candidates, but with strong checksums the probability is high that blocks have the same content. With synchronous deduplication you will find just one, as other duplicates have been deduplicated before.

The obvious advantage of the strong checksum is that it gets viable to do deduplication while writing. You have two possibilities here, too: You trust the checksum, and don't do a comparative read, or you read the block you want to point to, make a bit-wise comparison, and when it's a real duplicate you just store a pointer, Moellenkamp suggests.

Still, even with this comparative read the probability of a false duplicate isn't zero. It's the probability that an undetected error occurs on the way from the rotating rust to the cpu register in the process of reading the block, resulting in a byte-for-byte comparison that signals duplication, although it was just a read error, he writes.

In Moellenkamp's view, asynchronous and synchronous deduplication can be combined freely with hash-only and hash-and-compare deduplication. Reusing weak hashes, which were introduced as checksums only, mandates asynchronous (because of numerous potential dedup candidates) hash-and-compare (because of the high probability of hash collisions) checksums.

With ZFS dedup there is strong checksum (256-bit) synchronous deduplication with selectable hash-only and hash-and-compare modes of operation. So if your are in fear of hash collisions, you can switch on the hash-and-compare mode of operation. Given the low probability of a hash collision with current storage sizes it's a viable option to forget about the compare run, he suggests.

By contrast, NetApp dedup is weak checksum (16-bit) asynchronous deduplication with mandatory hash-and-compare mode of operation. Moellenkamp does the math to explain the mandatory aspect of this operation.

Finally, even with only a one percent probability of having a false positive, you would be just able to dedup a 36 blocks device with a 16 bit checksum. There is no way to work with hash-only dedup when your hash is just 16 bit, he argues.

More Information

"To dedup or not to dedup - that results in a lot of questions" - Moellenkamp's blog entry

Look Before You Leap into Data DeDupe

Blending Tape Virtualization and Data Deduplication

Performance Comparison of Dedpued Disk Vendors [...read more...]

		fullsource
Print Email Current Profile Archive Blog Generate newsletter