Skip to contentSkip to conversation

Trying to understand duperemove failure to deduplicate

DISCUSSION Andy Smith 2 participants 4 messages Mar 9, 2022 Btrfs file system

lore
Share & tools
lore

Andy Smith

author
#0 lore raw

Hi,

I was hoping to use duperemove to dedupe a set of large backups on a btrfs fs.

I did a test run and saw hardly any savings. I expected several hundred GB to be found; duperemove actually reported about 98GB but "df" only shows around 30GB. So I looked a bit harder.

FS mount options:

/dev/mapper/backupenc /data/backup btrfs rw,noatime,compress=zstd:15,space_cache,subvolid=5,subvol=/ 0 0

Kernel version 5.10.0-11-amd64, Debian 11.

Take for example these two files:

$ stat daily.{0,1}/cacti/var/lib/debconf_selections 
  File: daily.0/cacti/var/lib/debconf_selections
  Size: 94065           Blocks: 184        IO Block: 4096   regular file
Device: 26h/38d Inode: 136346107   Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2022-01-26 01:45:24.281602018 +0000
Modify: 2019-11-12 08:25:03.528065556 +0000
Change: 2022-03-08 11:28:27.862447446 +0000
 Birth: 2022-03-08 11:28:27.834447672 +0000
  File: daily.1/cacti/var/lib/debconf_selections
  Size: 94065           Blocks: 184        IO Block: 4096   regular file
Device: 26h/38d Inode: 134478113   Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2022-01-26 01:45:24.281602018 +0000
Modify: 2019-11-12 08:25:03.528065556 +0000
Change: 2022-03-07 20:37:22.993579274 +0000
 Birth: 2022-03-07 20:37:22.993579274 +0000

They have identical content:

$ md5sum daily.{0,1}/cacti/var/lib/debconf_selections 
c5633915f9d847394a6640c77c55f83a  daily.0/cacti/var/lib/debconf_selections
c5633915f9d847394a6640c77c55f83a  daily.1/cacti/var/lib/debconf_selections

They don't currently share extents:

$ filefrag -v daily.[01]/cacti/var/lib/debconf_selections
Filesystem type is: 9123683e
File size of daily.0/cacti/var/lib/debconf_selections is 94065 (23 blocks of 4096 bytes)
 ext:     logical_offset:        physical_offset: length:   expected: flags:
   0:        0..      22:  374427125.. 374427147:     23:             last,encoded,eof
daily.0/cacti/var/lib/debconf_selections: 1 extent found
File size of daily.1/cacti/var/lib/debconf_selections is 94065 (23 blocks of 4096 bytes)
 ext:     logical_offset:        physical_offset: length:   expected: flags:
   0:        0..      19:     399511..    399530:     20:             encoded,shared
   1:       20..      22:     306304..    306306:      3:     399531: last,encoded,shared,eof
daily.1/cacti/var/lib/debconf_selections: 2 extents found

So I would expect if I ran duperemove on these two files it would work out that these 3 extents could be replaced by 1 or 2. But:

$ sudo /usr/local/sbin/duperemove -b 4096 -drhv daily.{0,1}/cacti/var/lib/debconf_selections
Increased open file limit from 1024 to 1048576.
Using 4K blocks
Using hash: murmur3
Using extent-based hashing
Gathering file list...
Using 8 threads for file hashing phase
[1/2] (50.00%) csum: /data/backup/daily.0/cacti/var/lib/debconf_selections
[2/2] (100.00%) csum: /data/backup/daily.1/cacti/var/lib/debconf_selections
Total files:  2
Total extent hashes: 3
Loading only duplicated hashes from hashfile.
Found 0 identical extents.
Simple read and compare of file data found 0 instances of extents that might benefit from deduplication.
Nothing to dedupe.

Am I misunderstanding something about how dedupe works in btrfs, or duperemove itself?

Is it because this filesystem has compression enabled? Though after reading the earlier really useful reply from Zygo about dedupe and compression I had thought this wasn't going to be much of an issue with duperemove.

I haven't yet tried bees to see if it sees things differently.

Thanks,
Andy

#1 lore raw
Quoted 43 lines · Andy Smith

Hi,

I was hoping to use duperemove to dedupe a set of large backups on a btrfs fs.

I did a test run and saw hardly any savings. I expected several hundred GB to be found; duperemove actually reported about 98GB but "df" only shows around 30GB. So I looked a bit harder.

FS mount options:

/dev/mapper/backupenc /data/backup btrfs rw,noatime,compress=zstd:15,space_cache,subvolid=5,subvol=/ 0 0

Kernel version 5.10.0-11-amd64, Debian 11.

Take for example these two files:

$ stat daily.{0,1}/cacti/var/lib/debconf_selections
   File: daily.0/cacti/var/lib/debconf_selections
   Size: 94065           Blocks: 184        IO Block: 4096   regular file
Device: 26h/38d Inode: 136346107   Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2022-01-26 01:45:24.281602018 +0000
Modify: 2019-11-12 08:25:03.528065556 +0000
Change: 2022-03-08 11:28:27.862447446 +0000
  Birth: 2022-03-08 11:28:27.834447672 +0000
   File: daily.1/cacti/var/lib/debconf_selections
   Size: 94065           Blocks: 184        IO Block: 4096   regular file
Device: 26h/38d Inode: 134478113   Links: 1
Access: (0644/-rw-r--r--)  Uid: (    0/    root)   Gid: (    0/    root)
Access: 2022-01-26 01:45:24.281602018 +0000
Modify: 2019-11-12 08:25:03.528065556 +0000
Change: 2022-03-07 20:37:22.993579274 +0000
  Birth: 2022-03-07 20:37:22.993579274 +0000

They have identical content:

$ md5sum daily.{0,1}/cacti/var/lib/debconf_selections
c5633915f9d847394a6640c77c55f83a  daily.0/cacti/var/lib/debconf_selections
c5633915f9d847394a6640c77c55f83a  daily.1/cacti/var/lib/debconf_selections

They don't currently share extents:

Quoted 11 lines
$ filefrag -v daily.[01]/cacti/var/lib/debconf_selections
Filesystem type is: 9123683e
File size of daily.0/cacti/var/lib/debconf_selections is 94065 (23 blocks of 4096 bytes)
  ext:     logical_offset:        physical_offset: length:   expected: flags:
    0:        0..      22:  374427125.. 374427147:     23:             last,encoded,eof
daily.0/cacti/var/lib/debconf_selections: 1 extent found
File size of daily.1/cacti/var/lib/debconf_selections is 94065 (23 blocks of 4096 bytes)
  ext:     logical_offset:        physical_offset: length:   expected: flags:
    0:        0..      19:     399511..    399530:     20:             encoded,shared
    1:       20..      22:     306304..    306306:      3:     399531: last,encoded,shared,eof
daily.1/cacti/var/lib/debconf_selections: 2 extents found

The problem is in duperemove, not btrfs. Basically in the default mode of operation duperemove works based on extents, however those 2 files have identical content but its logical structure is different 1 vs 2 extents. Unfortunately duperemove is not able to cope with this, if you want to dedupe those file you should be using the block-based dedupe mode. This is explained in duperemove's FAQ in the man page:

.SS I got two identical files, why are they not deduped?

Duperemove by default works on extent granularity. What this means is if there are two files which are logically identical (have the same content) but are laid out on disk with different extent structure they won't be deduped. For example if 2 files are 128k each and their content are identical but one of them consists of a single 128k extent and the other of 2 x 64k extents then they won't be deduped. This behavior is dependent on the current implementation and is subject to change as duperemove is being improved.

<snip>

Quoted 3 lines

Thanks,
Andy

author
#2 lore raw

Hi Nikolay,

Quoted 3 lines · Nikolay Borisov

The problem is in duperemove, not btrfs. Basically in the default mode of operation duperemove works based on extents, however those 2 files have identical content but its logical structure is different 1 vs 2 extents.

Ah okay, thanks.

Quoted 2 lines

Unfortunately duperemove is not able to cope with this, if you want to dedupe those file you should be using the block-based dedupe mode.

Is that a mode of duperemove or did you mean to use a different tool?

I saw duperemove's "--lookup-extents" option and tried with that:

$ sudo /usr/local/sbin/duperemove -b 4096 -drhv --lookup-extents=no test/daily.{0,1}/cacti/var/lib/debconf_selections
Increased open file limit from 1024 to 1048576.
Using 4K blocks
Using hash: murmur3
Using block-based hashing
Gathering file list...
Using 8 threads for file hashing phase
[1/2] (50.00%) csum: /data/backup/test/daily.0/cacti/var/lib/debconf_selections
[2/2] (100.00%) csum: /data/backup/test/daily.1/cacti/var/lib/debconf_selections
Total files:  2
Total extent hashes: 46
Loading only duplicated hashes from hashfile.
Hashing completed. Using 4 threads to calculate duplicate extents. This may take some time.
Process 2 files.
Compare files "/data/backup/test/daily.1/cacti/var/lib/debconf_selections" and "/data/backup/test/daily.0/cacti/var/lib/debconf_selections"
Compare files "/data/backup/test/daily.1/cacti/var/lib/debconf_selections" and "/data/backup/test/daily.0/cacti/var/lib/debconf_selections"
Process 2 files.
Removing overlapping extents
Simple read and compare of file data found 1 instances of extents that might benefit from deduplication.
Showing 2 identical extents of length 91.9KB with id ab62a5e4
Start           Filename
0.0B    "/data/backup/test/daily.1/cacti/var/lib/debconf_selections"
0.0B    "/data/backup/test/daily.0/cacti/var/lib/debconf_selections"
Using 8 threads for dedupe phase
[0x5597f1e7b1e0] (1/1) Try to dedupe extents with id ab62a5e4
[0x5597f1e7b1e0] Add extent for file "/data/backup/test/daily.1/cacti/var/lib/debconf_selections" at offset 0.0B (3)
[0x5597f1e7b1e0] Add extent for file "/data/backup/test/daily.0/cacti/var/lib/debconf_selections" at offset 0.0B (4)
[0x5597f1e7b1e0] Dedupe 1 extents (id: ab62a5e4) with target: (0.0B, 91.9KB), "/data/backup/test/daily.1/cacti/var/lib/debconf_selections"
Kernel processed data (excludes target files): 91.9KB
Comparison of extent info shows a net change in shared extents of: 207.7KB

This does seem to have now resulted in a deduplication:

$ filefrag -v test/daily.{0,1}/cacti/var/lib/debconf_selections
Filesystem type is: 9123683e
File size of test/daily.0/cacti/var/lib/debconf_selections is 94065 (23 blocks of 4096 bytes)
 ext:     logical_offset:        physical_offset: length:   expected: flags:
   0:        0..      19:     399511..    399530:     20:             encoded,shared
   1:       20..      22:     306304..    306306:      3:     399531: last,encoded,shared,eof
test/daily.0/cacti/var/lib/debconf_selections: 2 extents found
File size of test/daily.1/cacti/var/lib/debconf_selections is 94065 (23 blocks of 4096 bytes)
 ext:     logical_offset:        physical_offset: length:   expected: flags:
   0:        0..      19:     399511..    399530:     20:             encoded,shared
   1:       20..      22:     306304..    306306:      3:     399531: last,encoded,shared,eof
test/daily.1/cacti/var/lib/debconf_selections: 2 extents found

So now I've got 2 extents total instead of 3, and that seemed to work, but perhaps there is a better tool.

Quoted 4 lines

This is explained in duperemove's FAQ in the man page:

.SS I got two identical files, why are they not deduped?

Ah right, I had missed that - the man page on duperemove's web site is out of date but I see it in the locally-installed copy.

Thanks,
Andy

#3 lore raw
Quoted 7 lines · Andy Smith

Hi Nikolay,

Quoted 3 lines · Nikolay Borisov

The problem is in duperemove, not btrfs. Basically in the default mode of operation duperemove works based on extents, however those 2 files have identical content but its logical structure is different 1 vs 2 extents.

Quoted 8 lines

Ah okay, thanks.

Quoted 2 lines

Unfortunately duperemove is not able to cope with this, if you want to dedupe those file you should be using the block-based dedupe mode.

Is that a mode of duperemove or did you mean to use a different tool?

I saw duperemove's "--lookup-extents" option and tried with that:

Yes, using lookup-extents=no makes duperemove utilize the block-dedupe mode of operation.

<snip>