Btrfs offline deduplication

Btrfs offline deduplication

[Timofey Titovets]

Good time of day.
I have several questions about data deduplication on btrfs.
Sorry if i ask stupid questions or waste you time %)

What about implementation of offline data deduplication? I don't see
any activity on this place, may be i need to ask a particular person?
Where the problem? May be a can i try to help (testing as example)?

I could be wrong, but as i understand btrfs store crc32 checksum one
per file, if this is true, may be make a sense to create small worker
for dedup files? Like worker for autodefrag?
With simple logic like:
if sum1 == sum2 && file_size1 == file_size2; then
if (bit_to_bit_identical(file1,2)); then merge(file1, file2);
This can be first attempt to implement per file offline dedup
What you think about it? could i be wrong? or this is a horrible crutch?
(as i understand it not change format of fs)

(bedup and other tools, its cool, but have several problem with these
tools and i think, what kernel implementation can work better).

-- 
Best regards,
Timofey.

Re: Btrfs offline deduplication

[Austin S Hemmelgarn]

[-- Attachment #1: Type: text/plain, Size: 1913 bytes --]

On 07/31/2014 07:54 PM, Timofey Titovets wrote:
> Good time of day.
> I have several questions about data deduplication on btrfs.
> Sorry if i ask stupid questions or waste you time %)
> 
> What about implementation of offline data deduplication? I don't see
> any activity on this place, may be i need to ask a particular person?
> Where the problem? May be a can i try to help (testing as example)?
> 
> I could be wrong, but as i understand btrfs store crc32 checksum one
> per file, if this is true, may be make a sense to create small worker
> for dedup files? Like worker for autodefrag?
> With simple logic like:
> if sum1 == sum2 && file_size1 == file_size2; then
> if (bit_to_bit_identical(file1,2)); then merge(file1, file2);
> This can be first attempt to implement per file offline dedup
> What you think about it? could i be wrong? or this is a horrible crutch?
> (as i understand it not change format of fs)
> 
> (bedup and other tools, its cool, but have several problem with these
> tools and i think, what kernel implementation can work better).
> 
I think there may be some misunderstandings here about some of the
internals of BTRFS.  First of all, checksums are stored per block, not
per file, and secondly, deduplication can be done on a much finer scale
than individual files (you can deduplicate individual extents).

I do think however that having the option of a background thread doing
deduplication asynchronously is a good idea, but then you would have to
have some way to trigger it on individual files/trees, and triggering on
writes like the autodefrag thread does doesn't make much sense.  Having
some userspace program to tell it to run on a given set of files would
probably be the best approach for a trigger.  I don't remember if this
kind of thing was also included in the online deduplication patches that
got posted a while back or not.


[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 2967 bytes --]

Re: Btrfs offline deduplication

[David Sterba]

On Fri, Aug 01, 2014 at 06:17:44AM -0400, Austin S Hemmelgarn wrote:
> I do think however that having the option of a background thread doing
> deduplication asynchronously is a good idea, but then you would have to
> have some way to trigger it on individual files/trees, and triggering on
> writes like the autodefrag thread does doesn't make much sense.  Having
> some userspace program to tell it to run on a given set of files would
> probably be the best approach for a trigger.  I don't remember if this
> kind of thing was also included in the online deduplication patches that
> got posted a while back or not.

IIRC the proposed implementation only merged new writes with existing
data.

For the out-of-band ("off-line") dedup there's bedup
(https://github.com/g2p/bedup) or Mark's duperemove tool
(https://github.com/markfasheh/duperemove) that work on a set of files.

Re: Btrfs offline deduplication

[Austin S Hemmelgarn]

[-- Attachment #1: Type: text/plain, Size: 1240 bytes --]

On 2014-08-01 09:23, David Sterba wrote:
> On Fri, Aug 01, 2014 at 06:17:44AM -0400, Austin S Hemmelgarn wrote:
>> I do think however that having the option of a background thread doing
>> deduplication asynchronously is a good idea, but then you would have to
>> have some way to trigger it on individual files/trees, and triggering on
>> writes like the autodefrag thread does doesn't make much sense.  Having
>> some userspace program to tell it to run on a given set of files would
>> probably be the best approach for a trigger.  I don't remember if this
>> kind of thing was also included in the online deduplication patches that
>> got posted a while back or not.
> 
> IIRC the proposed implementation only merged new writes with existing
> data.
> 
> For the out-of-band ("off-line") dedup there's bedup
> (https://github.com/g2p/bedup) or Mark's duperemove tool
> (https://github.com/markfasheh/duperemove) that work on a set of files.
> 
Something kernel-side to do the work asynchronously would be nice,
especially if it could leverage the check-sums that BTRFS already stores
for the blocks.  Having a userspace interface for offline deduplication
similar to that for scrub operations would even better.


[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 2967 bytes --]

Re: Btrfs offline deduplication

[Mark Fasheh]

On Fri, Aug 01, 2014 at 10:16:08AM -0400, Austin S Hemmelgarn wrote:
> On 2014-08-01 09:23, David Sterba wrote:
> > On Fri, Aug 01, 2014 at 06:17:44AM -0400, Austin S Hemmelgarn wrote:
> >> I do think however that having the option of a background thread doing
> >> deduplication asynchronously is a good idea, but then you would have to
> >> have some way to trigger it on individual files/trees, and triggering on
> >> writes like the autodefrag thread does doesn't make much sense.  Having
> >> some userspace program to tell it to run on a given set of files would
> >> probably be the best approach for a trigger.  I don't remember if this
> >> kind of thing was also included in the online deduplication patches that
> >> got posted a while back or not.
> > 
> > IIRC the proposed implementation only merged new writes with existing
> > data.
> > 
> > For the out-of-band ("off-line") dedup there's bedup
> > (https://github.com/g2p/bedup) or Mark's duperemove tool
> > (https://github.com/markfasheh/duperemove) that work on a set of files.
> > 
> Something kernel-side to do the work asynchronously would be nice,
> especially if it could leverage the check-sums that BTRFS already stores
> for the blocks.  Having a userspace interface for offline deduplication
> similar to that for scrub operations would even better.

Why does this have to be kernel side? There's userspace software already to
dedupe that can be run on a regular basis. Exporting checksums is a
differnet story (you can do that via ioctl) but running the dedupe software
itself inside the kernel is exactly what we want to avoid by having the
dedupe ioctl in the first place.
	--Mark

--
Mark Fasheh

Re: Btrfs offline deduplication

[Austin S Hemmelgarn]

[-- Attachment #1: Type: text/plain, Size: 2524 bytes --]

On 08/01/2014 02:55 PM, Mark Fasheh wrote:
> On Fri, Aug 01, 2014 at 10:16:08AM -0400, Austin S Hemmelgarn wrote:
>> On 2014-08-01 09:23, David Sterba wrote:
>>> On Fri, Aug 01, 2014 at 06:17:44AM -0400, Austin S Hemmelgarn wrote:
>>>> I do think however that having the option of a background thread doing
>>>> deduplication asynchronously is a good idea, but then you would have to
>>>> have some way to trigger it on individual files/trees, and triggering on
>>>> writes like the autodefrag thread does doesn't make much sense.  Having
>>>> some userspace program to tell it to run on a given set of files would
>>>> probably be the best approach for a trigger.  I don't remember if this
>>>> kind of thing was also included in the online deduplication patches that
>>>> got posted a while back or not.
>>>
>>> IIRC the proposed implementation only merged new writes with existing
>>> data.
>>>
>>> For the out-of-band ("off-line") dedup there's bedup
>>> (https://github.com/g2p/bedup) or Mark's duperemove tool
>>> (https://github.com/markfasheh/duperemove) that work on a set of files.
>>>
>> Something kernel-side to do the work asynchronously would be nice,
>> especially if it could leverage the check-sums that BTRFS already stores
>> for the blocks.  Having a userspace interface for offline deduplication
>> similar to that for scrub operations would even better.
> 
> Why does this have to be kernel side? There's userspace software already to
> dedupe that can be run on a regular basis. Exporting checksums is a
> differnet story (you can do that via ioctl) but running the dedupe software
> itself inside the kernel is exactly what we want to avoid by having the
> dedupe ioctl in the first place.
> 	--Mark
> 
> --
> Mark Fasheh
> 
Based on the same logic however, we don't need scrub to be done kernel
side, as it wouldn't take but one more ioctl to be able to tell it which
block out of a set to treat as valid.  I'm not saying that things need
to be done in the kernel, but duperemove doesn't use the ioctl interface
even if it exists, and bedup is buggy as hell (unless it's improved
greatly in the last two weeks), and neither of them is at all efficient.
 I do understand that this isn't something that is computationally
simple (especially on x86 with it's defficiency of registers), but rsync
does almost the same thing for data transmission over the network, and
it does so seemingly much more efficiently than either option available
at the moment.


[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 2967 bytes --]

Re: Btrfs offline deduplication

[Mark Fasheh]

On Fri, Aug 01, 2014 at 03:18:46PM -0400, Austin S Hemmelgarn wrote:
> > Why does this have to be kernel side? There's userspace software already to
> > dedupe that can be run on a regular basis. Exporting checksums is a
> > differnet story (you can do that via ioctl) but running the dedupe software
> > itself inside the kernel is exactly what we want to avoid by having the
> > dedupe ioctl in the first place.
> > 	--Mark
> > 
> > --
> > Mark Fasheh
> > 
> Based on the same logic however, we don't need scrub to be done kernel
> side, as it wouldn't take but one more ioctl to be able to tell it which
> block out of a set to treat as valid.  I'm not saying that things need
> to be done in the kernel, but duperemove doesn't use the ioctl interface
> even if it exists, and bedup is buggy as hell (unless it's improved
> greatly in the last two weeks), and neither of them is at all efficient.

Duperemove absolutely *does* use the ioctl interface for offline dedupe.


>  I do understand that this isn't something that is computationally
> simple (especially on x86 with it's defficiency of registers), but rsync
> does almost the same thing for data transmission over the network, and
> it does so seemingly much more efficiently than either option available
> at the moment.

None of the problems you mentioned get solved by pushing the entirety of
offline deduplication into the kernel. If anything, it's more dangerous tod
o that as bugs tend to be far more critical when we hit them from kernel.

Regarding duperemove there's a series to fix up some performance issues that
I'm working on importing at the moment.
	--Mark

--
Mark Fasheh