btrfs dedup - available or experimental? Or yet to be?

As titled:

Does btrfs have dedup (on raid1 multiple disks) that can be enabled?

Can anyone relate any experiences?

Is there (or will there be,) a bad penalty of fragmentation?

(For kernel 3.18.9)

Thanks,
Martin

The current state of play is on the wiki:

https://btrfs.wiki.kernel.org/index.php/Deduplication

duperemove is reported as working.

With duperemove, it operates on an extent scale, not at the level
of blocks, so the fragmentation isn't so bad.

Hugo.

Hugo Mills             | ©1973 Unclear Research Ltd
hugo@... carfax.org.uk |
http://carfax.org.uk/  |
PGP: 65E74AC0          |

I hadn't realized that bedup was deprecated.

This seems unfortunate since it seemed to be a lot smarter about detecting what has and hasn't already been scanned, and it also supported defragmenting files while de-duplicating them.

I'll give duperemove a shot. I just packaged it on Gentoo.

--
Rich

Excellent and very rapid packaging, thanks!

Already compiled, installed, and soon to be tried on a test subvolume...

Anyone with any comments on how well duperemove performs for TB-sized volumes?

Does it work across subvolumes? (Presumably not...)

Thanks,
Martin

Took many hours but less than a day for a few TB - I'm not sure whether it is smart enough to take less time on subsequent scans like bedup.

As far as I can tell, yes. Unless you pass a command-line option it crosses filesystem boundaries and even scans non-btrfs filesystems (like /proc, /dev, etc). Obviously you'll want to avoid that since it only wastes time and I can just imagine it trying to hash kcore and such.

Other than being less-than-ideal intelligence-wise, it seemed effective. I can live with that in an early release like this.

--
Rich

Hi just FYI, only rescanning files that have changed since the last scan is a feature I've been working on in duperemove for some time now. I have some rudimentary code that works which will be going into master branch in a week or so (I wanted to finish it this week but other things have kept me busy).

But anyway that should help with the lack of intelligence on what files to scan.

	--Mark

--
Mark Fasheh

https://github.com/markfasheh/duperemove/wiki/Performance-Numbers

That page has some sample performance numbers. Keep in mind that the tests were done on reasonably nice hardware.

TB-size is definitely on the larger end of what I expect it should handling these days. The biggest problem you would see is memory usage - versions 0.09 and below will be storing all hashes in memory so if everything else is fast enough that's likely the first bump you'll hit.

Master branch has some code which reduces our memory consumption dramatically by using a bloom filter and temporarily storing them on disk. That branch needs some more features and bug fixing before I'm ready to call it stable.

Yep it will dedupe across subvolumes for you!

	--Mark

--
Mark Fasheh

This is mainly in there to support deduping across different subvolumes within the same device pool. So I think the idea was neither less-than- ideal, nor unintelligent, and it has nothing to do with performance.

But your warning is still valid: One should take care not to "dedupe" special filesystems (but that is the same with every other tool out there, like rsync, cp, essentially everything that supports recursion), nor is it very effective for the deduplication process to cross a boundary to a non- btrfs device - for one or more exceptions: You may want duperemove to write hashes for a non-btrfs device and use the result for other purposes outside of duperemoves scope, or you are nesting btrfs into non-btrfs into btrfs mounts, or...

Concluding that: duperemove should probably not try to become smart about filesystem boundaries. It should either cross them or not as it is now - the option is left to the user (as is the task to supply proper cmdline arguments with that).

With the planned performance improvements, I'm guessing the best way will become mounting the root subvolume (subvolid 0) and letting duperemove work on that as a whole - including crossing all fs boundaries.

Replies to list only preferred.

Why cross filesystem boundaries by default? If you scan from the root subvolume you're guanteed to traverse every file on the filesystem (which is all that can be deduped) without crossing any filesystem boundaries. Even if you have btrfs on non-btrfs on btrfs there must be some other path that reaches the same files when scanning from subvolid 0.

--
Rich

Yes, the chosen "default" is probably not the best for this kind of utility. But I suppose it follows the principle of least surprise. At least every utility I'm daily using (like find) follows this default route. By the way, I wrote "default" because one should keep in mind that it is not recursive by default (and thus crossing the boundary wouldn't even apply in the default configuration) which only strengthens my point for the principle of least surprise. And I'd leave that open for discussion here to change the default, all I suggested was that duperemove should not try to become smart about it as the only choice (behavior will be undefined otherwise when deploying this on a vast amount of individually configured systems). I could image that there was a cmdline option to make it smart.

The idea for subvolid 0: It is just pure intention how I would use it for my personal purpose. By no means this should be in any default deployments.

Replies to list only preferred.

Couldn't it per default simply cross boundaries just within the same btrfs fs (i.e. amongst all it's subvolumes), since this seems to be the natural choice users want in most cases,... and via --no-xdev option or something like that it would be allowed to pass boundaries?

Cheers,
Chris.

But the default with all these tools is that they operate on the file hierarchy and per default don't care about filesystems at all - or at least not in their original meaning.

dedup is IMHO however a more filesystem internal centric operation... more like defragmentation ore tune2fs.

Cheers.

Hello,

I have been reading on de-duplication and how algorithms such as Bloom and Cuckoo filters are used for this purpose.

Does BTRFS dedup use any of these, or are there plans to incorporate these in future?

Thanks for your guidance!

btrfs dedup currently lives in user space, and there are multiple dedup userspace projects in development.

Administrators can choose the dedup tool, and can use multiple dedup tools on the same filesystem. This is particularly handy if you know something about your data that a naive hashing algorithm might not (e.g. you have two large trees derived from a common base, so you can use a much more efficient algorithm than you would if you knew nothing about the data).

The basic kernel interface for dedup is the extent-same ioctl. A userspace program creates a list of (fd, length, offset) tuples referencing identical content and passes them to the kernel. The kernel locks the file contents, compares them, and replaces identical data copies with references to a single extent in an atomic operation. The kernel also provides interfaces to efficiently discover recently modified extents in a filesystem, enabling deduplicators to follow new data without the need to block writes.

Most btrfs deduplicators are based on a block-level hash table built by scanning files, but every other aspect of the tools (e.g. the mechanism by which files are discovered, block sizes, scalability, use of prefiltering algorithms such as Bloom filters, whether the hash table is persistent or ephemeral, etc) is different from one tool to another, and changing over time as the tools are developed.

Because the kernel interface implies a read of both copies of duplicate data, it is not necessary to use a collision-free hash. Optimizing the number of bits in the hash function for the size of the filesystem and exploiting the statistical tendency for identical blocks to be adjacent to other identical blocks in files enables considerable space efficiency in the hash table--possibly so much that the Bloom/Cuckoo-style pre-filtering benefit becomes irrelevant. I'm not aware of a released btrfs deduplicator that currently exploits these optimizations.