Explore De-duplication options

[tasket]

Update: There are now 4 different dedup methods. See #8 (comment) for initial details.

---

Looking for ideas about a possible deduplication feature.

1. One simple idea that I've already tried manually with find | uniq | ln is to find the duplicate hashes in the manifests and link their files together on the destination, thus saving disk space. This unsophisticated approach has low CPU & IO overhead but the prospective space savings is lackluster.

2. It is also possible to retain and correlate more detailed metadata from thin_dump which indicates where source volumes share blocks. However, I've seen complaints about the CPU power needed to process these large xml files (that is not to say they couldn't be cleverly pre-processed to reduce overhead).

3. More advanced dedup techniques include sliding hash window comparisons. At this point the dedup is actively doing new forms of compression and its not clear this is worth the trade-offs for most users. At the very least it appears beyond what Python can do efficiently.

4. Detecting when a bkchunk is updated only at its start or end may save significant space (at least when lvm chunks are small). This would require special routines using extra bandwidth in merge and receive functions.

Not sure de-deduplication (whatever method) is worth it: I know the tool is meant for more general usage than Qubes OS but the area with most duplicated data would be the root volumes of similar templates. And Qubes OS or not, I'm not sure that identical blocks could be detected as such because of fs/block alignment discrepancies (but I could be wrong).

And even with deduplication, the savings for Qubes users would not really be significant: there's no benefit with the default setup (1 template) and in my case - 3 fedora templates - I've computed I'd be saving 7G max. That's really not much compared to my private volumes size (200+ G) that have barely any duplicated data. Moreover a lot of resources would be lost when the de-duplication algorithm goes over hundreds of gigabytes of non-duplicated data.

That said deduplication would help with multiple MS Windows VMs (again, if fs alignment with the underlying block device doesn't pose an issue).

And last, there's the problem of encryption: deduplication would require cleartext access to all the data, or at least to manifests. That would be a problem when using different keys.

FWIW I'm using hardlink to deduplicate files from servers backups. There might be some interesting implementation ideas that could be reused for hashes, should de-duplication be implemented.

[tasket]

I'm initially inclined to agree about root volumes being the main source of overlap. But I can imagine many situations (a large minority of them) where the user feels it necessary to clone certain appVMs with large initial data sets and then make unique adjustments to each clone ...and then include them all in the backups. Luckily, this sort of overlap information should be readily available from lvm.

This corner-case also suggests that method 1 (the quick/easy one) is worthwhile. But it should only try to dedup under specific conditions or user command to avoid bogging down.

Significant alignment will tend to be there when the dups are from cloning, otherwise there will still be some small set of incidental alignment even when the addresses differ. Its even possible to have sparsebak accept a 'cloning clue' from an OS hook and then remember whether 2 or more configured volumes are related by cloning.

Encryption is not an issue for method 1 where all that's needed is sorting the manifests; might not be for method 2 as well.

[tasket]

Try for an optional type-1 dedup feature in 0.5 when encryption is introduced.

[tasket]

Initial tests with simple hash-comparison and hardlink, when using the new default 64k chunk size, are quite positive.

Observations

1. With no cloned volumes/data in a 2-month old daily archive, an overall 13% reduction in disk usage is achieved.
2. Incremental send operations often see reduction in the 30-40% range.
3. Cloned volumes are often reduced >50% and can see a 100% reduction if the clone is unmodified.

See Testing Notes in the Readme for brief usage instructions.

I've done some tests with send --testing-dedup on a fedora template that was cloned from a "minimal" template months ago and had quite a few additional packages installed. For info the original "minimal" template data size is ~1.5GB and the cloned one is ~2.2GB.

• the (real) time to complete a backup without dedup was ~3 minutes and I could work with the laptop while the backup was being completed.
• the time with dedup was ~7:50s and the laptop was almost irresponsive during the whole backup duration. I noticed approx. +1GB swap usage so heavy I/O swap is likely culprit here (I have restricted dom0's total mem to only 1GB to free up memory for vms - it worked fine until now - so I'll have to reboot with more ram and see how dedup fares).
• size reduction was ~700MB (32% of total / ~50% of the "shared" content), which is not bad at all given that the template was cloned months ago.

By the way quite a bit of time is spent with --testing-dedup after "'Done.'" is displayed, even when the volume didn't change since the last backup. send without dedup takes 2 seconds on a test volume (without changes) while it takes more than 3 minutes with --testing-dedup (and CPU/memory usage increase significantly during that step).

Given --testing-dedup's significant use of resources it seemed to make more sense to use "standard" backups and run sparsebak.py testing-dedup-existing ... unattended every once in a while (BTW that's how I backup all my servers: daily rsync without deduplication and a hardlink run every Sunday).
Half of my backup data is from -private volumes that have hardly any files in common so there's no point in spending resources to try to deduplicate them (side question: any idea what is the memory usage growth compared to the data set size ? Quadratic ?).
The other half is mainly from cloned MS Windows vms, and a few cloned linux templates so it made sense to restrict testing-dedup-existing to specific subsets of volumes. I did a quick test with my vm-win7-*root volumes backups: it took only 48 seconds - this time without trashing my laptop - and size reduction was extremely good considering how/when vms were cloned and which software/updates were installed:

7.4G  7.3G   (1%)  vm-win7-r4-clean-fullupdate-root
3.7G  688M  (19%) vm-win7-r4-clean-root
7.4G  994M  (13%) vm-win7-r4-work-root
4.7G  4.5G  (1%) vm-win7-template-root

vm-win7-r4-clean is a "clean" (eg. no updates) win7 VM I created on R4 long ago. I've cloned it into vm-win7-r4-work where I installed additional software as well as into vm-win7-r4-clean-fullupdate which has seen a full Windows Update cycle. vm-win7-template was imported from R3.2 and there wasn't any size reduction for that one (probably because of a different disk alignment ; it's interesting that there is a bit of deduplication though - those were probably found at other places in the same disk).

Let me know if you'd like me to do more specific tests.

(As usual - great work !)

[tasket]

Thanks for the report! This initial attempt at indexing was a bit naive, but even so deduplicating large sets has a reputation for being a memory hog (many people found this out when trying zfs dedup).

I have dom0 capped at 1.5G, and with my smaller archive saw less swapping; I don't think it was churning so you might want to increase your dom0 memory to this amount.

There's an update that reduces index memory use, with ints and object refs instead of strings. The reduction is between 30-50% but CPU use has gone up slightly (Python dicts are known to be optimized for strings). I may get it down by 3/4 if I can somehow use ctypes or other traditional integer types. You can compare the process memory use of the old and new index types with the test1 and test2 commands. The send and dedup-existing routines have been moved to the new index, but I'm leaving the old one there presently for comparison.

Though I haven't thought that deeply about it yet, I believe (maybe wrong) the index size is sub-quadratic bc the base of the exponent never reaches 2 under normal operating conditions (entropy is moderate).

Improving the dedup conditions with some type of affinity setting, as you suggest, is certainly possible and I believe this is another use case for multiple archive sets... having volumes in the same set will indicate dedup affinity. The archive set is all about the characteristics of the (dest) storage such as where its located, it can also hold the parameters that affect storage efficiency (you will also be able to set the chunk size, compression params and overall cap on allocated space).

[tasket]

BTW, I don't mind discussion in qubes-users and elsewhere (this is not a Qubes-specific tool :) ) just keep in mind its at "leaving experimental" phase and due for a name change.