I may be stating the obvious there, but using 4-byte chunks (and for that matter anything lower than 64-byte chunks) is not only inefficient but also not space-saving at all.

You're also storing the names of chunks needed to reassemble the objects, each name using 256 bits or 32 bytes of space (or as you're probably storing hex strings, 64 bytes). So with any chunk size lower than or equal to 64 bytes, the space needed to store chunk names for an object is bigger or equal to the object size.

Hey Steve,

You're describing something quite similar to Venti - see http://en.wikipedia.org/wiki/Venti

Yes, using 4-byte chunks was really a test of the worst-possible setup, rather than a serious suggestion.

As you note the overhead makes it ludicrious since the filename of my chunks is 64-bytes meaning the space goes up by 8-times even before we consider the database.

Venti I'd never heard of before, so thanks for the link!

Anyway my conclusion was that this approach has merit, but if you're uploading random files then you're lucky if you get any useful collision and space-saving using chunk-sizes that seem sane (512-2048 bytes in size) - and that actually surprised me.

I'm not sure what you're trying to build, and you may already know all this, but when doing de-duplication using fixed-size chunks, it is usually a problem that files that only differ by some additions/removals still lead to a lot of duplication because the chunk boundaries do not align.

The usual remedy for this problem is to use variable-size chunks; the key idea is that when splitting up the file in chunks you look at the actual data for some kind of marker pattern (say the sequence "000") where you end the current chunk and start a new chunk. By aligning the chunk boundaries on patterns in the data, the de-duplication becomes much more robust against small additions and removals.

When implementing this idea, a marker pattern is usually detected using a rolling checksum, which is a checksum of the last window of N bytes; this can be calculated very efficiently (just a few operations for each new byte that you read). When the checksum matches a specific bitmask M, the last N bytes amount to a marker, and it's time to start a new chunk.

By configuring N and M you can tune the statistical frequency of markers in the data, and thus the average chunk size. There, you still have the same tradeoff (smaller chunks have better deduplication but more overhead).

Some modern backup solutions such as Attic or zbackup variable-size chunk deduplication.

I've done some reading recently, Bruno, because all that was new to me. I always assumed that collisions were done on a fixed-block basis, but having seen how poorly that performs I guess rolling makes more sense.

I will have to experiment with that approach and see how it changes things.

@Bruno, I've often wondered how a rolling-checksum scheme would solve the offset problem. Thanks for the info! Have you got any references?

This problem is why de-duplication is often not recommended under ZFS. It is a feature of ZFS, but Allan Jude, of the TechSNAP podcast often states it doesn't help in most cases. ZFS now supports direct compression of data as a more useful space saving measure. Deduplication seems to be an early but not generally useful feature of ZFS. It may have been used by certain customers, just a neat feature natural to ZFS development.

It seems better suited as a following stage to another encoding which handles the indexing of variable chunks. In big data situations, the index to an encoding dictionary could be very large. Spectral data, a full Unicode aware dictionary or molecular analysis could generate huge indexes. Yet data sets of the same kind would have similar huge indexes. It seems this method could deduplicate the raw indexes of wide spectrum data sets. Experience would guide scaling the first and second stage encodings.