Use new incompat feature BG_TREE to hugely reduce mount time

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/bg_tree
Which is based on v4.20-rc1 tag.

This patchset will hugely reduce mount time of large fs by putting all block group items into its own tree.

The old behavior will try to read out all block group items at mount time, however due to the key of block group items are scattered across tons of extent items, we must call btrfs_search_slot() for each block group.

It works fine for small fs, but when number of block groups goes beyond 200, such tree search will become a random read, causing obvious slow down.

On the other hand, btrfs_read_chunk_tree() is still very fast, since we put CHUNK_ITEMS into their own tree and package them next to each other.

Following this idea, we could do the same thing for block group items, so instead of triggering btrfs_search_slot() for each block group, we just call btrfs_next_item() and under most case we could finish in memory, and hugely speed up mount (see BENCHMARK below).

The only disadvantage is, this method introduce an incompatible feature, so existing fs can't use this feature directly.
Either specify it at mkfs time, or use btrfs-progs offline convert tool (*).

*: Mkfs and convert tool are doing the same work, however I haven't decide if I should put this feature to btrfstune.

The RFC tag is for the comprehensive test and sysfs interface. At least during my filling test it definitely works fine.

[[Benchmark]]
Physical device: HDD (7200RPM)
Nodesize: 4K (to bump up tree height)
Used size: 250G
Total size: 500G
Extent data size: 1M

All file extents on disk is in 1M size, ensured by using fallocate.

Without patchset:
Use ftrace function graph:

  3)               |  open_ctree [btrfs]() {
  3)               |    btrfs_read_chunk_tree [btrfs]() {
  3) * 69033.31 us |    }
  3)               |    btrfs_verify_dev_extents [btrfs]() {
  3) * 90376.15 us |    }
  3)               |    btrfs_read_block_groups [btrfs]() {
  2) $ 2733853 us  |    } /* btrfs_read_block_groups [btrfs] */
  2) $ 3168384 us  |  } /* open_ctree [btrfs] */

btrfs_read_block_groups() takes 87% of the total mount time,

With patchset, and use -O bg-tree mkfs option:

  7)               |  open_ctree [btrfs]() {
  7)               |    btrfs_read_chunk_tree [btrfs]() {
  7) # 2448.562 us |    }
  7)               |    btrfs_verify_dev_extents [btrfs]() {
  7) * 19802.02 us |    }
  7)               |    btrfs_read_block_groups [btrfs]() {
  7) # 8610.397 us |    }
  7) @ 113498.6 us |  }

open_ctree() time is only 3% of original mount time.
And btrfs_read_block_groups() only takes 7.6% of total open_ctree() execution time.

Qu Wenruo (2):
btrfs: Refactor btrfs_read_block_groups()
btrfs: Introduce new incompat feature, BG_TREE

 fs/btrfs/ctree.h                |   5 +-
 fs/btrfs/disk-io.c              |  13 ++
 fs/btrfs/extent-tree.c          | 300 ++++++++++++++++++++------------
 include/uapi/linux/btrfs.h      |   1 +
 include/uapi/linux/btrfs_tree.h |   3 +
 5 files changed, 206 insertions(+), 116 deletions(-)

Quoted 25 lines · Qu Wenruo

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/bg_tree
Which is based on v4.20-rc1 tag.

This patchset will hugely reduce mount time of large fs by putting all block group items into its own tree.

The old behavior will try to read out all block group items at mount time, however due to the key of block group items are scattered across tons of extent items, we must call btrfs_search_slot() for each block group.

It works fine for small fs, but when number of block groups goes beyond 200, such tree search will become a random read, causing obvious slow down.

On the other hand, btrfs_read_chunk_tree() is still very fast, since we put CHUNK_ITEMS into their own tree and package them next to each other.

Following this idea, we could do the same thing for block group items, so instead of triggering btrfs_search_slot() for each block group, we just call btrfs_next_item() and under most case we could finish in memory, and hugely speed up mount (see BENCHMARK below).

Quoted 4 lines

The only disadvantage is, this method introduce an incompatible feature, so existing fs can't use this feature directly.
Either specify it at mkfs time, or use btrfs-progs offline convert tool (*).

What if we start recording block group items in the chunk tree?

Would
that bring any benefit without creating yet another tree, though likely we'd still have to use an incompat flag? That way shouldn't BLOCK_GROUP items be chunked together?

Quoted 57 lines

*: Mkfs and convert tool are doing the same work, however I haven't decide if I should put this feature to btrfstune.

The RFC tag is for the comprehensive test and sysfs interface. At least during my filling test it definitely works fine.

[[Benchmark]]
Physical device: HDD (7200RPM)
Nodesize: 4K (to bump up tree height)
Used size: 250G
Total size: 500G
Extent data size: 1M

All file extents on disk is in 1M size, ensured by using fallocate.

Without patchset:
Use ftrace function graph:

  3)               |  open_ctree [btrfs]() {
  3)               |    btrfs_read_chunk_tree [btrfs]() {
  3) * 69033.31 us |    }
  3)               |    btrfs_verify_dev_extents [btrfs]() {
  3) * 90376.15 us |    }
  3)               |    btrfs_read_block_groups [btrfs]() {
  2) $ 2733853 us  |    } /* btrfs_read_block_groups [btrfs] */
  2) $ 3168384 us  |  } /* open_ctree [btrfs] */

btrfs_read_block_groups() takes 87% of the total mount time,

With patchset, and use -O bg-tree mkfs option:

  7)               |  open_ctree [btrfs]() {
  7)               |    btrfs_read_chunk_tree [btrfs]() {
  7) # 2448.562 us |    }
  7)               |    btrfs_verify_dev_extents [btrfs]() {
  7) * 19802.02 us |    }
  7)               |    btrfs_read_block_groups [btrfs]() {
  7) # 8610.397 us |    }
  7) @ 113498.6 us |  }

open_ctree() time is only 3% of original mount time.
And btrfs_read_block_groups() only takes 7.6% of total open_ctree() execution time.

Qu Wenruo (2):
btrfs: Refactor btrfs_read_block_groups()
btrfs: Introduce new incompat feature, BG_TREE

 fs/btrfs/ctree.h                |   5 +-
 fs/btrfs/disk-io.c              |  13 ++
 fs/btrfs/extent-tree.c          | 300 ++++++++++++++++++++------------
 include/uapi/linux/btrfs.h      |   1 +
 include/uapi/linux/btrfs_tree.h |   3 +
 5 files changed, 206 insertions(+), 116 deletions(-)

Quoted 26 lines · Nikolay Borisov

Quoted 25 lines · Qu Wenruo

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/bg_tree
Which is based on v4.20-rc1 tag.

This patchset will hugely reduce mount time of large fs by putting all block group items into its own tree.

The old behavior will try to read out all block group items at mount time, however due to the key of block group items are scattered across tons of extent items, we must call btrfs_search_slot() for each block group.

It works fine for small fs, but when number of block groups goes beyond 200, such tree search will become a random read, causing obvious slow down.

On the other hand, btrfs_read_chunk_tree() is still very fast, since we put CHUNK_ITEMS into their own tree and package them next to each other.

Following this idea, we could do the same thing for block group items, so instead of triggering btrfs_search_slot() for each block group, we just call btrfs_next_item() and under most case we could finish in memory, and hugely speed up mount (see BENCHMARK below).

Quoted 6 lines

Quoted 4 lines

The only disadvantage is, this method introduce an incompatible feature, so existing fs can't use this feature directly.
Either specify it at mkfs time, or use btrfs-progs offline convert tool (*).

What if we start recording block group items in the chunk tree?

Then chunk tree will be too hot.

Currently chunk tree is pretty stable, only get modified at bg creation/deletion time.

Considering how important chunk tree is, I prefer to make chunk root as cold as possible.

On the other hand, block group items are pretty hot (although less hot compared to old extent tree), so it still makes sense to put them into one tree, allow chunk tree to be as cold as ice, while keep block group items relatively safe compared to old extent tree.

Quoted 39 lines · Qu Wenruo

Quoted 26 lines · Nikolay Borisov

Quoted 25 lines · Qu Wenruo

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/bg_tree
Which is based on v4.20-rc1 tag.

This patchset will hugely reduce mount time of large fs by putting all block group items into its own tree.

The old behavior will try to read out all block group items at mount time, however due to the key of block group items are scattered across tons of extent items, we must call btrfs_search_slot() for each block group.

It works fine for small fs, but when number of block groups goes beyond 200, such tree search will become a random read, causing obvious slow down.

On the other hand, btrfs_read_chunk_tree() is still very fast, since we put CHUNK_ITEMS into their own tree and package them next to each other.

Following this idea, we could do the same thing for block group items, so instead of triggering btrfs_search_slot() for each block group, we just call btrfs_next_item() and under most case we could finish in memory, and hugely speed up mount (see BENCHMARK below).

Quoted 6 lines

Quoted 4 lines

The only disadvantage is, this method introduce an incompatible feature, so existing fs can't use this feature directly.
Either specify it at mkfs time, or use btrfs-progs offline convert tool (*).

What if we start recording block group items in the chunk tree?

Then chunk tree will be too hot.

Currently chunk tree is pretty stable, only get modified at bg creation/deletion time.

Quoted 7 lines

Considering how important chunk tree is, I prefer to make chunk root as cold as possible.

On the other hand, block group items are pretty hot (although less hot compared to old extent tree), so it still makes sense to put them into one tree, allow chunk tree to be as cold as ice, while keep block group items relatively safe compared to old extent tree.

A feature like this should come with an analysis of both approaches in advance. Both have pros and cons that we need to weigh. Eg. I'm not more for storing the items in an existing tree, possibly creating a new tree item that would pack the bg items together at the beginning of the tree.

The update frequency of the tree is an aspect that I haven't considered before but I think it's a good point.

The tree holding the bg items can be considered fundamental and requires a backup pointer in the superblock. So this would need more work.

Quoted 1 line · David Sterba

On Fri, Dec 28, 2018 at 05:28:13PM +0800, Qu Wenruo wrote:

Quoted 8 lines

Quoted 8 lines · Nikolay Borisov

Quoted 7 lines · Qu Wenruo

Quoted 6 lines

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/bg_tree
Which is based on v4.20-rc1 tag.

This patchset will hugely reduce mount time of large fs by putting all block group items into its own tree.

Quoted 9 lines

Quoted 9 lines

Quoted 9 lines

Quoted 9 lines

The old behavior will try to read out all block group items at mount time, however due to the key of block group items are scattered across tons of extent items, we must call btrfs_search_slot() for each block group.

It works fine for small fs, but when number of block groups goes beyond 200, such tree search will become a random read, causing obvious slow down.

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

On the other hand, btrfs_read_chunk_tree() is still very fast, since we put CHUNK_ITEMS into their own tree and package them next to each other.

Following this idea, we could do the same thing for block group items, so instead of triggering btrfs_search_slot() for each block group, we just call btrfs_next_item() and under most case we could finish in memory, and hugely speed up mount (see BENCHMARK below).

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

Quoted 4 lines

The only disadvantage is, this method introduce an incompatible feature, so existing fs can't use this feature directly.
Either specify it at mkfs time, or use btrfs-progs offline convert tool (*).

What if we start recording block group items in the chunk tree?

Quoted 7 lines

Quoted 7 lines

Then chunk tree will be too hot.

Currently chunk tree is pretty stable, only get modified at bg creation/deletion time.

Considering how important chunk tree is, I prefer to make chunk root as cold as possible.

Quoted 10 lines

Quoted 4 lines

On the other hand, block group items are pretty hot (although less hot compared to old extent tree), so it still makes sense to put them into one tree, allow chunk tree to be as cold as ice, while keep block group items relatively safe compared to old extent tree.

A feature like this should come with an analysis of both approaches in advance. Both have pros and cons that we need to weigh. Eg. I'm not more for storing the items in an existing tree, possibly creating a new tree item that would pack the bg items together at the beginning of the tree.

Quoted 5 lines

The update frequency of the tree is an aspect that I haven't considered before but I think it's a good point.

The tree holding the bg items can be considered fundamental and requires a backup pointer in the superblock. So this would need more work.

Right, for backup root it indeed makes sense.

However for another key type method, I don't really think there is any pro.

To pack bg items together, new key type is needed anyway.

With new key type, no matter where the new bg items are, older kernel won't be compatible, thus still INCOMPAT feature.

And for whatever the tree holding block group items, it will be as hot as extent tree used to be, bring up the corruption possibility to the whatever the existing is. Or slow down the tree.

So at least from my respect of view, storing (new) bg items in existing tree doesn't make sense.

However I think we should put more discussion on the possible new block group item structure design.
E.g. Remove chunk_objectid member, or even each block group has its own tree.

Hi,

Quoted 6 lines · Qu Wenruo

Quoted 3 lines · David Sterba

Quoted 2 lines · Qu Wenruo

Quoted 1 line · Nikolay Borisov

On 28.12.18 г. 10:37 ч., Qu Wenruo wrote:

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

Quoted 6 lines

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/bg_tree
Which is based on v4.20-rc1 tag.

This patchset will hugely reduce mount time of large fs by putting all block group items into its own tree.

Thanks a lot for writing a proof of concept for this! This is great.

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

Quoted 10 lines

The old behavior will try to read out all block group items at mount time, however due to the key of block group items are scattered across tons of extent items, we must call btrfs_search_slot() for each block group.

It works fine for small fs, but when number of block groups goes beyond 200, such tree search will become a random read, causing obvious slow down.

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

Quoted 8 lines

On the other hand, btrfs_read_chunk_tree() is still very fast, since we put CHUNK_ITEMS into their own tree and package them next to each other.

Following this idea, we could do the same thing for block group items, so instead of triggering btrfs_search_slot() for each block group, we just call btrfs_next_item() and under most case we could finish in memory, and hugely speed up mount (see BENCHMARK below).

+many, this is a usability "bug" that comes up regularly on mailing list and IRC, people asking why their filesystem takes long to mount.

I also have some filesystems that I have to set noauto in fstab, and then after booting mount manually, and then do some other manual tasks, because having them mount automatically during boot causes timeouts and stuff.

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Quoted 6 lines

Quoted 4 lines

The only disadvantage is, this method introduce an incompatible feature, so existing fs can't use this feature directly.
Either specify it at mkfs time, or use btrfs-progs offline convert tool (*).

What if we start recording block group items in the chunk tree?

Quoted 7 lines

Quoted 7 lines

Quoted 7 lines

Then chunk tree will be too hot.

Currently chunk tree is pretty stable, only get modified at bg creation/deletion time.

Considering how important chunk tree is, I prefer to make chunk root as cold as possible.

This makes sense.

Quoted 16 lines

Quoted 15 lines

Quoted 4 lines

On the other hand, block group items are pretty hot (although less hot compared to old extent tree), so it still makes sense to put them into one tree, allow chunk tree to be as cold as ice, while keep block group items relatively safe compared to old extent tree.

A feature like this should come with an analysis of both approaches in advance. Both have pros and cons that we need to weigh. Eg. I'm not more for storing the items in an existing tree, possibly creating a new tree item that would pack the bg items together at the beginning of the tree.

The update frequency of the tree is an aspect that I haven't considered before but I think it's a good point.

The tree holding the bg items can be considered fundamental and requires a backup pointer in the superblock. So this would need more work.

Quoted 1 line

Right, for backup root it indeed makes sense.

I don't really understand why this backup roots mechanism keeps being a thing, because technically btrfs cannot guarantee at all that there will be anything usable left right after the old metadata extents are unpinned...?

Quoted 4 lines

However for another key type method, I don't really think there is any pro.

To pack bg items together, new key type is needed anyway.

Not if the block group items are the only thing in the tree...?

Quoted 8 lines

With new key type, no matter where the new bg items are, older kernel won't be compatible, thus still INCOMPAT feature.

And for whatever the tree holding block group items, it will be as hot as extent tree used to be, bring up the corruption possibility to the whatever the existing is. Or slow down the tree.

Quoted 7 lines

So at least from my respect of view, storing (new) bg items in existing tree doesn't make sense.

However I think we should put more discussion on the possible new block group item structure design.
E.g. Remove chunk_objectid member, or even each block group has its own tree.

Just thinking out loud...

It seems to me that keeping the same key type and btrfs_block_group_item struct and same key values as they have in extent tree would be desirable if both old and new code has to co-exist in the kernel.

This is easy to review...

(quoted diff) +5 -1

-	struct btrfs_root *root = fs_info->extent_root;
+	struct btrfs_root *root;
 
[...]
 
+	if (btrfs_fs_incompat(fs_info, BG_TREE))
+		root = fs_info->bg_root;
+	else
+		root = fs_info->extent_root;

...but creating a new different struct and key type would cause much more invasive code changes and duplication (and bugs) all over the place, or wrappers to handle either scenario.

I mean, who cares about some unused chunk_objectid field on a multi-TiB filesystem...

I'd vote for doing things, and more "design for today".

Otherwise the
same might happen that also happens with some other topics every time... it ends up with the idea to rewrite half btrfs and then in the end nothing happens at all, and the users are still unhappy. ;-)

Even when splitting the extent tree into multiple trees ever, it would still be a good idea to have this BG_TREE.