IcedChunker

RAMChunk (Widodo & Atiquzzaman)

Relies on a simple self-adapating mechanism for determining when to break a chunk:

• Read each byte in the chunk, AND
• Check if its equal or higher to the highest byte seen so far, AND
• Check if the chunk would be larger or equal than the minimum chunk size, THEN
• Split the input in to a chunk here

This method should be somewhat amenable to acceleration as well.

SampleByte

Not implemented.

Relies on a table mapping each byte to an "in" or "out" group.

• Read each byte in the chunk, AND
• If the byte is within the "in" group, THEN
• Take a fixed-size window of bytes as a chunk. Hash the window and store in a content-addressed storage table.
• Advance input by half the skip size.

Can be used with a randomly initialized grouping table¹ or tuned for specific workloads.

Rabin Fingerprints

Not implemented.

Relies on a "rolling hash" where bytes entering and exiting the window are added/subtracted.

Often explained very terribly (often invoking words like "Galois field") but is a relatively short math function relying on modulos.

Rsync, Buzzhash, etc

Relies on a "rolling hash" where bytes entering and exiting the window are added/subtracted. A much less mathematical (compared to Rabin) method is used to check if a split should be here: check the number of zero bits at the head or tail of the rolling hash.

Not implemented.

References

• R.N.S. Widodo, H. Lim, M. Atiquzzaman, A new content-defined chunking algorithm for data deduplication in cloud storage, Future Generation Computer Systems (2017), http://dx.doi.org/10.1016/j.future.2017年02月01日3
• EndRE: An End-System Redundancy Elimination Service for Enterprises