Re: Feature requests: online backup - defrag - change RAID level

[webmaster@zedlx.com]

Quoting Qu Wenruo <quwenruo.btrfs@gmx.com>:

> On 2019/9/10 上午9:24, webmaster@zedlx.com wrote:
>>
>> Quoting Qu Wenruo <quwenruo.btrfs@gmx.com>:
>>
>>>>> Btrfs defrag works by creating new extents containing the old data.
>>>>>
>>>>> So if btrfs decides to defrag, no old extents will be used.
>>>>> It will all be new extents.
>>>>>
>>>>> That's why your proposal is freaking strange here.
>>>>
>>>> Ok, but: can the NEW extents still be shared?
>>>
>>> Can only be shared by reflink.
>>> Not automatically, so if btrfs decides to defrag, it will not be shared
>>> at all.
>>>
>>>> If you had an extent E88
>>>> shared by 4 files in different subvolumes, can it be copied to another
>>>> place and still be shared by the original 4 files?
>>>
>>> Not for current btrfs.
>>>
>>>> I guess that the
>>>> answer is YES. And, that's the only requirement for a good defrag
>>>> algorithm that doesn't shrink free space.
>>>
>>> We may go that direction.
>>>
>>> The biggest burden here is, btrfs needs to do expensive full-backref
>>> walk to determine how many files are referring to this extent.
>>> And then change them all to refer to the new extent.
>>
>> YES! That! Exactly THAT. That is what needs to be done.
>>
>> I mean, you just create an (perhaps associative) array which links an
>> extent (the array index contains the extent ID) to all the files that
>> reference that extent.
>
> You're exactly in the pitfall of btrfs backref walk.
>
> For btrfs, it's definitely not an easy work to do backref walk.
> btrfs uses hidden backref, that means, under most case, one extent
> shared by 1000 snapshots, in extent tree (shows the backref) it can
> completely be possible to only have one ref, for the initial subvolume.
>
> For btrfs, you need to walk up the tree to find how it's shared.
>
> It has to be done like that, that's why we call it backref-*walk*.
>
> E.g
>           A (subvol 257)     B (Subvol 258, snapshot of 257)
>           |    \        /    |
>           |        X         |
>           |    /        \    |
>           C                  D
>          / \                / \
>         E   F              G   H
>
> In extent tree, E is only referred by subvol 257.
> While C has two referencers, 257 and 258.
>
> So in reality, you need to:
> 1) Do a tree search from subvol 257
>    You got a path, E -> C -> A
> 2) Check each node to see if it's shared.
>    E is only referred by C, no extra referencer.
>    C is refered by two new tree blocks, A and B.
>    A is refered by subvol 257.
>    B is refered by subvol 258.
>    So E is shared by 257 and 258.
>
> Now, you see how things would go mad, for each extent you must go that
> way to determine the real owner of each extent, not to mention we can
> have at most 8 levels, tree blocks at level 0~7 can all be shared.
>
> If it's shared by 1000 subvolumes, hope you had a good day then.

Ok, let's do just this issue for the time being. One issue at a time.  
It will be easier.

The solution is to temporarily create a copy of the entire  
backref-tree in memory. To create this copy, you just do a preorder  
depth-first traversal following only forward references.

So this preorder depth-first traversal would visit the nodes in the  
following order:
A,C,E,F,D,G,H,B

Oh, it is not a tree, it is a DAG in that example of yours. OK,  
preorder is possible on DAG, too. But how did you get a DAG, shouldn't  
it be all trees?

When you have the entire backref-tree (backref-DAG?) in memory, doing  
a backref-walk is a piece of cake.

Of course, this in-memory backref tree has to be kept in sync with the  
filesystem, that is it has to be updated whenever there is a write to  
disk. That's not so hard.