Skip to contentSkip to conversation

cross-subvolume cp --reflink

DISCUSSION Norbert Scheibner 8 participants 20 messages Apr 1, 2012 – Aug 21, 2012 2 messages not in the archive Btrfs file system

lore
Share & tools
lore
#0 lore raw

Gl=C3=BCck Auf!
I know its been discussed more then ones, but as a user I really would = like to see the patch for allowing this in the kernel.

Some users tested this patch successfully for weeks or months in 2 or 3=
kernel versions since then, true?

I'd say by creating a snapshot, it's nothing else in the end. More then=
one file or tree sharing the same data on disc, or am I wrong?

So why not?
Norbert
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#1 lore raw

On =CE=9A=CF=85=CF=81=CE=B9=CE=B1=CE=BA=CE=AE, 1 =CE=91=CF=80=CF=81=CE=AF= =CE=BB=CE=B9=CE=BF=CF=82 2012 6:27:49 =CE=BC=CE=BC, Norbert Scheibner w= rote:

Quoted 2 lines

Gl=C3=BCck Auf!
I know its been discussed more then ones, but as a user I really woul=

d like to see the patch for allowing this in the kernel.

Quoted 2 lines

Some users tested this patch successfully for weeks or months in 2 or=

3 kernel versions since then, true?

Quoted 1 line

+1 from me too, i would save enormous amounts of space with a patch=20 like that, at least until dedupe is implemented. We could call it "poor= =20
man's dedupe"

Quoted 1 line

I'd say by creating a snapshot, it's nothing else in the end. More th=

en one file or tree sharing the same data on disc, or am I wrong?

Quoted 5 lines

So why not?
Norbert
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs=

" in

Quoted 2 lines

the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#2 lore raw
Quoted 5 lines

On: Sun, 01 Apr 2012 18:30:13 +0300 Konstantinos Skarlatos wrote

+1 from me too, i would save enormous amounts of space with a patch like that, at least until dedupe is implemented. We could call it "poor man's dedupe"

That's my point. This poor man's dedupe would solve my problems here very well. I don't need a zfs-variant of dedupe. I can implement such a file-based dedupe with userland tools and would be happy.

It's there, it's tested, it doesn't break another thing. Use it!

Greetings
Norbert

#3 lore raw

On =CE=9A=CF=85=CF=81=CE=B9=CE=B1=CE=BA=CE=AE, 1 =CE=91=CF=80=CF=81=CE=AF= =CE=BB=CE=B9=CE=BF=CF=82 2012 7:41:36 =CE=BC=CE=BC, Norbert Scheibner w= rote:

Quoted 4 lines
Quoted 4 lines

On: Sun, 01 Apr 2012 18:30:13 +0300 Konstantinos Skarlatos wrote

+1 from me too, i would save enormous amounts of space with a patch like that, at least until dedupe is implemented. We could call it "p=

oor

Quoted 3 lines
Quoted 1 line

man's dedupe"

That's my point. This poor man's dedupe would solve my problems here =

very well. I don't need a zfs-variant of dedupe. I can implement such a= file-based dedupe with userland tools and would be happy.

do you have any scripts that can search a btrfs filesystem for dupes=20 and replace them with cp --reflink?

Quoted 6 lines

It's there, it's tested, it doesn't break another thing. Use it!

Greetings
Norbert

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#4 lore raw
Quoted 8 lines

On: Sun, 01 Apr 2012 19:45:13 +0300 Konstantinos Skarlatos wrote

Quoted 1 line

That's my point. This poor man's dedupe would solve my problems here

very well. I don't need a zfs-variant of dedupe. I can implement such a file-based dedupe with userland tools and would be happy.

do you have any scripts that can search a btrfs filesystem for dupes and replace them with cp --reflink?

Nothing really working and tested very well. After I get to known the missing cp --reflink feature I stopped to develop the script any further.

I use btrfs for my backups. Ones a day I rsync --delete --inplace the complete system to a subvolume, snapshot it, delete some tempfiles in the snapshot. In addition to that I wanted to shrink file-duplicates.

What the script should do:
1. I md5sum every file
2. If the checksums are identical, I compare the files
3. If 2 or more files are really identical:
- move one to a temp-dir
- cp --reflink the second to the position and name of the first
- do a chown --reference, chmod --reference and touch --reference to copy owner, file mode bits and time from the orginal to the reflink-copy and then delete the original in temp-dir

Everything could be done with bash. Thinkable is the use of a database for the md5sums, which could be used for other purposes in the future.

#5 lore raw

On =CE=9A=CF=85=CF=81=CE=B9=CE=B1=CE=BA=CE=AE, 1 =CE=91=CF=80=CF=81=CE=AF= =CE=BB=CE=B9=CE=BF=CF=82 2012 8:07:54 =CE=BC=CE=BC, Norbert Scheibner w= rote:

Quoted 3 lines
Quoted 3 lines

On: Sun, 01 Apr 2012 19:45:13 +0300 Konstantinos Skarlatos wrote

Quoted 1 line

That's my point. This poor man's dedupe would solve my problems her=

e

Quoted 1 line
Quoted 1 line

very well. I don't need a zfs-variant of dedupe. I can implement suc=

h a

Quoted 6 lines
Quoted 4 lines

file-based dedupe with userland tools and would be happy.

do you have any scripts that can search a btrfs filesystem for dupes and replace them with cp --reflink?

Nothing really working and tested very well. After I get to known the=

missing cp --reflink feature I stopped to develop the script any furth= er.

Quoted 2 lines

I use btrfs for my backups. Ones a day I rsync --delete --inplace the=

complete system to a subvolume, snapshot it, delete some tempfiles in = the snapshot.

In my setup I rsync --inplace many servers and workstations, 4-6 times=20 a day into a 12TB btrfs volume, each one in its own subvolume. After=20 every backup a new ro snapshot is created.

I have many cross-subvolume duplicate files (OS files, programs, many=20 huge media files that are copied locally from the servers to the=20 workstations etc), so a good "dedupe" script could save lots of space,=20 and allow me to keep snapshots for much longer.

Quoted 12 lines

In addition to that I wanted to shrink file-duplicates.

What the script should do:
1. I md5sum every file
2. If the checksums are identical, I compare the files
3. If 2 or more files are really identical:
- move one to a temp-dir
- cp --reflink the second to the position and name of the first
- do a chown --reference, chmod --reference and touch --reference to copy owner, file mode bits and time from the orginal to the reflink-copy and then delete the original in temp-dir

Quoted 1 line

Everything could be done with bash. Thinkable is the use of a databas=

e for the md5sums, which could be used for other purposes in the future= =2E

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#6 lore raw
Quoted 6 lines

On: Sun, 01 Apr 2012 20:19:24 +0300 Konstantinos Skarlatos wrote

Quoted 1 line

I use btrfs for my backups. Ones a day I rsync --delete --inplace the

complete system to a subvolume, snapshot it, delete some tempfiles in the snapshot.

Quoted 8 lines

In my setup I rsync --inplace many servers and workstations, 4-6 times a day into a 12TB btrfs volume, each one in its own subvolume. After every backup a new ro snapshot is created.

I have many cross-subvolume duplicate files (OS files, programs, many huge media files that are copied locally from the servers to the workstations etc), so a good "dedupe" script could save lots of space, and allow me to keep snapshots for much longer.

So the script should be optimized not to try to deduplicate the whole fs everytime but the newly written ones. You could take such a file list out of the rsync output or the btrfs subvolume find-new command.

Albeit the reflink patch, You could use such a bash-script inside one subvolume, after the rsync and before the snapshot. I don't know how much space it saves for You in this situation, but it's worth a try and a good way to develop such a script, because before You write anything to disc You can see how many duplicates are there and how much space could be freed.

MfG
Norbert

#7 lore raw
Quoted 16 lines · Norbert Scheibner
Quoted 7 lines

On: Sun, 01 Apr 2012 20:19:24 +0300 Konstantinos Skarlatos wrote

Quoted 2 lines

I use btrfs for my backups. Ones a day I rsync --delete --inplace the

complete system to a subvolume, snapshot it, delete some tempfiles in the snapshot.

Quoted 8 lines

In my setup I rsync --inplace many servers and workstations, 4-6 times a day into a 12TB btrfs volume, each one in its own subvolume. After every backup a new ro snapshot is created.

I have many cross-subvolume duplicate files (OS files, programs, many huge media files that are copied locally from the servers to the workstations etc), so a good "dedupe" script could save lots of space, and allow me to keep snapshots for much longer.

Quoted 5 lines

So the script should be optimized not to try to deduplicate the whole fs everytime but the newly written ones. You could take such a file list out of the rsync output or the btrfs subvolume find-new command.

a cron task with btrfs subvolume find-new would be ideal i think

Quoted 8 lines

Albeit the reflink patch, You could use such a bash-script inside one subvolume, after the rsync and before the snapshot. I don't know how much space it saves for You in this situation, but it's worth a try and a good way to develop such a script, because before You write anything to disc You can see how many duplicates are there and how much space could be freed.

MfG Norbert

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

A message that is not in the archive (sent off-list or not yet received): [email protected]

#9 lore raw
Quoted 9 lines

On: Sun, 01 Apr 2012 19:22:42 +0200"Klaus A. Kreil" wrote

I am just an interested reader on the btrfs list and so far have never posted or sent a message to the list, but I do have a dedup bash script that searches for duplicates underneath a directory (provided as an argument) and hard links identical files.

It works very well for an ext3 filesystem, but I guess the basics should be the same for a btrfs filesystem.

Everyone feel free to correct me here, but:
At the moment there is a little problem with the maximum number of hard links in a directory. So I wouldn't use them wherever possible to avoid any thinkable problems in the near future.

Plus to hard link 2 files means, that change one file You change the other one. It's something You either don't want to happen or something, which could be done in better ways. The cp --reflink method on a COW-fs is a much smarter method.

Plus hard links across subvolumes do match the case of hard links across devices on a traditional fs, which is forbidden.

Plus hard links In my opinion should really be substituted by soft links, because hard links are not transparent at the first sight and can not be copied as it.

So no, I'd rather want the patch to allow cross-subvolume cp --reflink in the kernel and I will wait for that to happen.

Greetings
Norbert

#10 lore raw
Quoted 3 lines · Norbert Scheibner
Quoted 3 lines

On: Sun, 01 Apr 2012 19:22:42 +0200"Klaus A. Kreil" wrote

I am just an interested reader on the btrfs list and so far have nev=

er

Quoted 1 line
Quoted 1 line

posted or sent a message to the list, but I do have a dedup bash scr=

ipt

Quoted 4 lines
Quoted 4 lines

that searches for duplicates underneath a directory (provided as an argument) and hard links identical files.

It works very well for an ext3 filesystem, but I guess the basics sh=

ould

Quoted 1 line
Quoted 1 line

be the same for a btrfs filesystem.

Thanks for the nice script, it works fine here!
I just added a du -sh "$1" line at the beginning and end to see how muc= h=20
space it saves.

Quoted 3 lines

Everyone feel free to correct me here, but:
At the moment there is a little problem with the maximum number of ha=

rd links in a directory. So I wouldn't use them wherever possible to av= oid any thinkable problems in the near future.

Quoted 2 lines

Plus to hard link 2 files means, that change one file You change the =

other one. It's something You either don't want to happen or something,= which could be done in better ways. The cp --reflink method on a COW-f= s is a much smarter method.
thats true, cp --reflink is much better. Also am I wrong that btrfs has= =20
a limitation on the number of hard links that can only be fixed with a=20 disk format change?

Quoted 2 lines

Plus hard links across subvolumes do match the case of hard links acr=

oss devices on a traditional fs, which is forbidden.

Quoted 2 lines

Plus hard links In my opinion should really be substituted by soft li=

nks, because hard links are not transparent at the first sight and can = not be copied as it.

Quoted 2 lines

So no, I'd rather want the patch to allow cross-subvolume cp --reflin=

k in the kernel and I will wait for that to happen.

Quoted 3 lines

Greetings
Norbert

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#11 lore raw
Quoted 3 lines · Konstantinos Skarlatos

thats true, cp --reflink is much better. Also am I wrong that btrfs has a limitation on the number of hard links that can only be fixed with a disk format change?

There's patch in development to lift the limit and it does not need the disk format change but adds an incompatibility bit.

david

#12 lore raw
In reply to Norbert Scheibner
Quoted 1 line · Norbert Scheibner

Some users tested this patch successfully for week,s or months in 2 or 3 kernel versions since then, true?

If this feature must be implented in VFS in another patch, why not just activate what works and make the future patch disable it again?

#13 lore raw
Quoted 5 lines · On Sunday 01 of April 2012 11:42:23 Jérôme Poulin wrote:
Quoted 2 lines · Norbert Scheibner

Some users tested this patch successfully for week,s or months in 2 or 3 kernel versions since then, true?

If this feature must be implented in VFS in another patch, why not just activate what works and make the future patch disable it again?

Why would (should) it be impleemented in VFS? reflink copy is completely different from normal copy and hard link.

Subvolumes in btrfs are barriers *only* in btrfs and not visible in VFS.

IMHO it's strictly btrfs business and not supporting reflink copy between arbitrary directories is a bug.

Regards,

Signature · 5 lines
Hubert Kario
QBS - Quality Business Software
02-656 Warszawa, ul. Ksawerów 30/85
tel. +48 (22) 646-61-51, 646-74-24
www.qbs.com.pl
#14 lore raw

Am 29.04.2012, 01:53 Uhr, schrieb Hubert Kario <[email protected]>:

Quoted 2 lines · On Sunday 01 of April 2012 11:42:23 J=E9r=F4me Poulin wrote:
Quoted 1 line

On Sun, Apr 1, 2012 at 11:27 AM, Norbert Scheibner <[email protected]> wr=

ote:

Quoted 1 line
Quoted 1 line
Quoted 1 line

Some users tested this patch successfully for week,s or months in =

2 =20

Quoted 6 lines
Quoted 4 lines

or 3

Quoted 1 line

kernel versions since then, true?

If this feature must be implented in VFS in another patch, why not just activate what works and make the future patch disable it again?

Why would (should) it be impleemented in VFS? reflink copy is complet=

ely

Quoted 1 line

different from normal copy and hard link.

I wouldn't make a VFS issue out of that. That should be another discuss= ion.

But:

Quoted 1 line

Subvolumes in btrfs are barriers *only* in btrfs and not visible in V=

=46S.

That is just a bug in my opinion, so it should work anyway, but to look=
at =20
it from VFS point of view is strengthening me in wanting the outstandin= g =20
patches integrated, as this feature could be supported by VFS in the =20 future.

Quoted 1 line

IMHO it's strictly btrfs business and not supporting reflink copy bet=

ween

Quoted 1 line

arbitrary directories is a bug.

I don't know exactly, but I think ZFS is another candidate for "cp =20 --reflink". For some of the log-structured filesystems this could be =20 usefull too, but I don't know if some of them already supports this or = =20
plan to support this in the future.

Greetings
Norbert
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" = in
the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#15 lore raw

dunno if this thread is dead, but im inclined to patch in cp --reflink to "fdupes" prog. It currently does provide a poor-man's dedupe via md5sum and hardlink, or delete.

all the better if the distro-kernels can backport cross-snapshot reflinks sooner than later.

Quoted 45 lines · Norbert Scheibner

Am 29.04.2012, 01:53 Uhr, schrieb Hubert Kario <[email protected]>:

Quoted 6 lines · On Sunday 01 of April 2012 11:42:23 Jérôme Poulin wrote:
Quoted 5 lines · Norbert Scheibner
Quoted 3 lines

Some users tested this patch successfully for week,s or months in 2 or 3
kernel versions since then, true?

Quoted 6 lines
Quoted 2 lines

If this feature must be implented in VFS in another patch, why not just activate what works and make the future patch disable it again?

Why would (should) it be impleemented in VFS? reflink copy is completely different from normal copy and hard link.

I wouldn't make a VFS issue out of that. That should be another discussion.

But:

Quoted 1 line

Subvolumes in btrfs are barriers *only* in btrfs and not visible in VFS.

That is just a bug in my opinion, so it should work anyway, but to look at it from VFS point of view is strengthening me in wanting the outstanding patches integrated, as this feature could be supported by VFS in the future.

Quoted 2 lines

IMHO it's strictly btrfs business and not supporting reflink copy between arbitrary directories is a bug.

I don't know exactly, but I think ZFS is another candidate for "cp --reflink". For some of the log-structured filesystems this could be usefull too, but I don't know if some of them already supports this or plan to support this in the future.

Greetings
Norbert

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

#16 lore raw
Quoted 6 lines · james northrup

dunno if this thread is dead, but im inclined to patch in cp --reflink to "fdupes" prog. It currently does provide a poor-man's dedupe via md5sum and hardlink, or delete.

all the better if the distro-kernels can backport cross-snapshot reflinks sooner than later.

So, I'd love for cp --reflink to bring back a deleted VM (huge file) from a snapshot back to trunk without duplicating it.
But how would fdupes help? I can't hardlink between two snapshots, can I?

gandalfthegreat:/mnt/btrfs_pool1# ln usr_weekly_20120812_00\:02\:01/svn-commit.tmp  usr/test
ln: failed to create hard link `usr/test' => `usr_weekly_20120812_00:02:01/svn-commit.tmp': Invalid cross-device link

So, is there anything user space can do without kernel support?

Marc

Quoted 50 lines · Norbert Scheibner
Quoted 38 lines

Am 29.04.2012, 01:53 Uhr, schrieb Hubert Kario <[email protected]>:

Quoted 6 lines · On Sunday 01 of April 2012 11:42:23 Jérôme Poulin wrote:
Quoted 5 lines · Norbert Scheibner
Quoted 3 lines

Some users tested this patch successfully for week,s or months in 2 or 3
kernel versions since then, true?

Quoted 6 lines
Quoted 2 lines

If this feature must be implented in VFS in another patch, why not just activate what works and make the future patch disable it again?

Why would (should) it be impleemented in VFS? reflink copy is completely different from normal copy and hard link.

I wouldn't make a VFS issue out of that. That should be another discussion.

But:

Quoted 1 line

Subvolumes in btrfs are barriers *only* in btrfs and not visible in VFS.

That is just a bug in my opinion, so it should work anyway, but to look at it from VFS point of view is strengthening me in wanting the outstanding patches integrated, as this feature could be supported by VFS in the future.

Quoted 2 lines

IMHO it's strictly btrfs business and not supporting reflink copy between arbitrary directories is a bug.

I don't know exactly, but I think ZFS is another candidate for "cp --reflink". For some of the log-structured filesystems this could be usefull too, but I don't know if some of them already supports this or plan to support this in the future.

Quoted 7 lines

Greetings
Norbert

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Signature · 4 lines
"A mouse is a device used to point at the xterm you want to type in" - A.S.R.
Microsoft is to operating systems ....
                                      .... what McDonalds is to gourmet cooking
Home page: http://marc.merlins.org/  
#17 lore raw
Quoted 8 lines · Marc MERLIN
Quoted 6 lines · james northrup

dunno if this thread is dead, but im inclined to patch in cp --reflink to "fdupes" prog. It currently does provide a poor-man's dedupe via md5sum and hardlink, or delete.

all the better if the distro-kernels can backport cross-snapshot reflinks sooner than later.

Quoted 9 lines

So, I'd love for cp --reflink to bring back a deleted VM (huge file) from a snapshot back to trunk without duplicating it.
But how would fdupes help? I can't hardlink between two snapshots, can I?

gandalfthegreat:/mnt/btrfs_pool1# ln usr_weekly_20120812_00\:02\:01/svn-commit.tmp  usr/test
ln: failed to create hard link `usr/test' => `usr_weekly_20120812_00:02:01/svn-commit.tmp': Invalid cross-device link

So, is there anything user space can do without kernel support?

A cross-subvolume copy patch has made it into 3.6_rc

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux.git;a=commit;h=362a20c5e27614739c4

This patch will allow cp --reflink across subvolumes, as long as the copy does not cross mount points.

#18 lore raw
Quoted 19 lines · Mitch Harder
Quoted 8 lines · Marc MERLIN
Quoted 6 lines · james northrup

dunno if this thread is dead, but im inclined to patch in cp --reflink to "fdupes" prog. It currently does provide a poor-man's dedupe via md5sum and hardlink, or delete.

all the better if the distro-kernels can backport cross-snapshot reflinks sooner than later.

Quoted 9 lines

So, I'd love for cp --reflink to bring back a deleted VM (huge file) from a snapshot back to trunk without duplicating it.
But how would fdupes help? I can't hardlink between two snapshots, can I?

gandalfthegreat:/mnt/btrfs_pool1# ln usr_weekly_20120812_00\:02\:01/svn-commit.tmp  usr/test
ln: failed to create hard link `usr/test' => `usr_weekly_20120812_00:02:01/svn-commit.tmp': Invalid cross-device link

So, is there anything user space can do without kernel support?

Quoted 6 lines

A cross-subvolume copy patch has made it into 3.6_rc

http://git.kernel.org/?p=linux/kernel/git/torvalds/linux.git;a=commit;h=362a20c5e27614739c4

This patch will allow cp --reflink across subvolumes, as long as the copy does not cross mount points.

I missed that, that's great news, thanks to all those involved in getting this in.

Marc

Signature · 4 lines
"A mouse is a device used to point at the xterm you want to type in" - A.S.R.
Microsoft is to operating systems ....
                                      .... what McDonalds is to gourmet cooking
Home page: http://marc.merlins.org/  

A message that is not in the archive (sent off-list or not yet received): CAPkEcwgSZ8umbFeuZ-fQAFAprBubL58eFSf4TQ=Z13ks8i9DOQ@mail.gmail.com

#20 lore raw
Quoted 6 lines · james northrup

dunno if this thread is dead, but im inclined to patch in cp --reflink to "fdupes" prog.
It currently does provide a poor-man's dedupe via md5sum and hardlink, or delete.

all the better if the distro-kernels can backport cross-snapshot reflinks sooner than later.

I was also wondering if it is possible for a program like fdupes to use BTRFS checksum to make searching for duplicates much faster as you wouldn't need to calculate checksum if BTRFS own checksum was mismatched between 2 groups of checksum blocks?

#21 lore raw
Quoted 9 lines · Jérôme Poulin
Quoted 6 lines · james northrup

dunno if this thread is dead, but im inclined to patch in cp --reflink to "fdupes" prog.
It currently does provide a poor-man's dedupe via md5sum and hardlink,
or delete.

Quoted 8 lines
Quoted 3 lines

all the better if the distro-kernels can backport cross-snapshot reflinks sooner than later.

I was also wondering if it is possible for a program like fdupes to use BTRFS checksum to make searching for duplicates much faster as you wouldn't need to calculate checksum if BTRFS own checksum was mismatched between 2 groups of checksum blocks?

source in question is here..

http://code.google.com/p/fdupes/source/browse/trunk/fdupes.c

i consider cp --reflink an option for this code. it doesn't strike me as scalable at first glance and i wouldnt want to spend more than a few minutes adding a new option.

i like the idea of something a little more scalable to populate a radix tree with extent-checksums abound and to link them without regard to order or associative. i dont have this project in mind myself.