Re: [PATCH v2 0/7] btrfs-progs: Support for BG_TREE feature

[Qu Wenruo <quwenruo.btrfs@gmx.com>]

[-- Attachment #1.1: Type: text/plain, Size: 7165 bytes --]



On 2019/10/19 上午1:27, David Sterba wrote:
> On Wed, Oct 16, 2019 at 11:19:54AM +0000, Qu WenRuo wrote:
>>>> The most important aspect to me is, to allow real world user of super
>>>> large fs to try this feature, to prove the usefulness of this design,
>>>> other than my on-paper analyse.
>>>>
>>>> That's why I'm pushing the patchset, even it may not pass any review.
>>>> I just want to hold a up-to-date branch so that when some one needs, it
>>>> can grab and try them themselves.
>>>
>>> Ok that's fine and I can add the branch to for-next for ease of testing.
>>> I'm working on a prototype that does it the bg item key way, it compiles
>>> and creates almost correct filesystem, so I have to fix it before
>>> posting. The patches are on top of your bg-tree feature so we could have
>>> both in the same kernel for testing.
>>
>> That's great!
>>
>> As long as we're pushing a solution to the mount time problem, I can't
>> be more happier!
>>
>> Then I guess no matter which version get merged to upstream, the
>> patchset is already meaningful.
> 
> We'll see what works in the end, I'm getting to the point where the
> prototype almost works and am debugging weird problems or making sure
> it's correct. So I'll dump the ideas here and link to the code so you
> can have a look.

That's wonderful.
Although I guess my patchset should provide the hint of where to modify
the code, since there are only a limited number of places we modify
block group item.

> 
> We agree on the point that the block group items must be packed. The key
> approach should move the new BGI to the beginning, ie. key type is
> smaller than anything that appears in the extent tree. I chose 100 for
> the prototype, it could change.
> 
> To keep changes to minimum, the new BGI uses the same block group item,
> so the only difference then becomes how we search for the items.

If we're introducing new block group item, I hope to do a minor change.

Remove the chunk_objectid member, or even flags. to make it more
compact. So that you can make the BGI subtree even smaller.

But I guess since you don't want to modify the BGI structure, and keep
the code modification minimal, it may not be a good idea right now.

> 
> Packing of the items is done by swapping the key objectid and offset.
> 
> Normal BGI has bg.start == key.objectid and bg.length == key.offset. As
> the objectid is the thing that scatters the items all over the tree.
> 
> So the new BGI has bg.length == key.objectid and bg.start == key.offset.
> As most of block groups are of same size, or from a small set, they're
> packed.

That doesn't look optimized enough.

bg.length can be at 1G, that means if extents starts below 1G can still
be before BGIs.

I believe we should have a fixed objectid for this new BGIs, so that
they are ensured to be at the beginning of extent tree.

> 
> The nice thing is that a lot of code can be shared between BGI and new
> BGI, just needs some care with searches, inserts and search key
> advances.

Exactly, but since we're introducing a new key type, I prefer to perfect
it. Not only change the key, but also the block group item structure to
make it more compact.

Although from the design aspect, it looks like BG tree along with new
BGI would be the best design.

New BG key goes (bg start, NEW BGI TYPE, used) no data. It would provide
the most compact on-disk format.

> 
> I'm now stuck a bit at mkfs, where the 8M block groups are separated by
> some METADATA_ITEMs
> 
>  item 0 key (8388608 BLOCK_GROUP_ITEM_NEW 13631488) itemoff 16259 itemsize 24
>          block group NEW used 0 chunk_objectid 256 flags DATA
>  item 1 key (8388608 BLOCK_GROUP_ITEM_NEW 22020096) itemoff 16235 itemsize 24
>          block group NEW used 16384 chunk_objectid 256 flags SYSTEM|DUP
>  item 2 key (22036480 METADATA_ITEM 0) itemoff 16202 itemsize 33
>          refs 1 gen 5 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root CHUNK_TREE
>  item 3 key (30408704 METADATA_ITEM 0) itemoff 16169 itemsize 33
>          refs 1 gen 4 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root FS_TREE

Exactly the problem I described.


>  item 4 key (30474240 METADATA_ITEM 0) itemoff 16136 itemsize 33
>          refs 1 gen 4 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root CSUM_TREE
>  item 5 key (30490624 METADATA_ITEM 0) itemoff 16103 itemsize 33
>          refs 1 gen 4 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root DATA_RELOC_TREE
>  item 6 key (30507008 METADATA_ITEM 0) itemoff 16070 itemsize 33
>          refs 1 gen 4 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root UUID_TREE
>  item 7 key (30523392 METADATA_ITEM 0) itemoff 16037 itemsize 33
>          refs 1 gen 5 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root EXTENT_TREE
>  item 8 key (30539776 METADATA_ITEM 0) itemoff 16004 itemsize 33
>          refs 1 gen 5 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root DEV_TREE
>  item 9 key (30556160 METADATA_ITEM 0) itemoff 15971 itemsize 33
>          refs 1 gen 5 flags TREE_BLOCK
>          tree block skinny level 0
>          tree block backref root ROOT_TREE
>  item 10 key (107347968 BLOCK_GROUP_ITEM_NEW 30408704) itemoff 15947 itemsize 24
>          block group NEW used 114688 chunk_objectid 256 flags METADATA|DUP
> 
> After item 10, the rest of the block group would appear, and basically
> the rest of the extent tree, many other items.
> 
> I don't want
> to make hardcoded assumptins, that maximum objecit is 1G, but so far was
> not able to come up with a generic and reliable formula how to set up
> key for next search to reach item (107347968 BLOCK_GROUP_ITEM_NEW
> 30408704) once (8388608 BLOCK_GROUP_ITEM_NEW 22020096) has been
> processed.
> 
> The swapped objectid and offset is the hard part for search because we
> lose the linearity of block group start.  Advance objectid by one and
> search again ie. (8388608+1 BGI_NEW 22020096) will land on the next
> metadata item. Iterating objectid by one would eventually reach the 1G
> block group item, but what to do after the last 1G item is found and we
> want do decide wheather to continue or not?
> 
> This would be easy with the bg_tree, because we'd know that all items in
> the tree are just the block group items. Some sort of enumeration could
> work for bg_key too, but I don't have something solid.

Why not fixed objectid for BGI and just ignore the bg.len part?

We have chunk<->BGI verification code, no bg.len is not a problem at
all, we can still make sure chunk<->bg is 1:1 mapped and still verify
the bg.used.

Thanks,
Qu

> 
> The WIP is in my github repository branch dev/bg-key. It's not on top of
> the bg_tree branch for now. The kernel part will be very similar once
> the progs side is done.
> 
> Feedback welcome.
> 


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 488 bytes --]