Skip to content

btrfs: Introduce new incompat feature SKINNY_BG_TREE to hugely reduce mount time

Qu Wenruo linux-btrfs 4 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest7 patches 8 repliesIn review
  2. v33 patches 13 repliesSuperseded
  3. v23 patches 14 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v12 patches5 repliesSuperseded

Changes in v4 from the cover letter

- Move to skinny bg tree design
Since we're going to introduce an incompatible feature, it's better to do it to extreme.

- Refactor block group item operations into their own functions So that block group item operations would hide the skinny bg item and regular bg item operations from callers, making code much easier to read.

- Add tree checker patch

Patches in v4 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/7btrfs: block-group: Don't set the wrong READA flag for btrfs_read_block_groups()fs/btrfs/block-group.c+0 -10 replies
2/7btrfs: block-group: Refactor how we read one block group itemfs/btrfs/block-group.c+32 -150 replies
3/7btrfs: block-group: Refactor how we delete one block group itemfs/btrfs/block-group.c+25 -123 replies
4/7btrfs: block-group: Refactor how we insert a block group itemfs/btrfs/block-group.c+25 -161 reply
5/7btrfs: block-group: Rename write_one_cahce_group()fs/btrfs/block-group.c+12 -112 replies
6/7btrfs: Introduce new incompat feature, SKINNY_BG_TREE, to hugely reduce mount timefs/btrfs/block-group.c fs/btrfs/block-rsv.c fs/btrfs/ctree.h +4 more+190 -161 reply
7/7btrfs: tree-checker: Introduce checks for skinny block group itemfs/btrfs/tree-checker.c+51 -50 replies

Reviews trailers per patch

3 of 7 patches have a Reviewed-by or Acked-by.

PatchJohannes Thumshirn
1/7
2/7
3/7R-b
4/7R-b
5/7R-b
6/7
7/7

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v4 thread

Cover letter [PATCH v4 0/7] btrfs: Introduce new incompat feature SKINNY_BG_TREE to hugely reduce mount time

This patchset can be fetched from:
https://github.com/adam900710/linux/tree/skinny_bg_tree
Which is based on david/misc-next branch.

This patchset will hugely reduce mount time of large fs by putting all block group items into its own tree, and further compact the block group item design to take full usage of btrfs_key.

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.
This can be improved to RO compatible, as long as btrfs can go skip_bg automatically (another patchset needed)

Either specify it at mkfs time, or use btrfs-progs offline convert tool.

[[Benchmark]]
Since I have upgraded my rig to all NVME storage, there is no HDD test result.

Physical device: NVMe SSD
VM device: VirtIO block device, backup by sparse file
Nodesize: 4K (to bump up tree height)
Extent data size: 4M
Fs size used: 1T

All file extents on disk is in 4M size, preallocated to reduce space usage (as the VM uses loopback block device backed by sparse file)

Without patchset:
Use ftrace function graph:

 7)               |  open_ctree [btrfs]() {
 7)               |    btrfs_read_block_groups [btrfs]() {
 7) @ 805851.8 us |    }
 7) @ 911890.2 us |  }

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

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

 5)               |  open_ctree [btrfs]() {
 5)               |    btrfs_read_block_groups [btrfs]() {
 5) * 63395.75 us |    }
 5) @ 143106.9 us |  }

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

The reason is pretty obvious when considering how many tree blocks needs to be read from disk:

| Extent tree | Skinny bg tree |
----------+---------------+-------------------

  nodes   |            55 |                1 |
  leaves  |          1025 |                7 |
  total   |          1080 |                8 |

Not to mention all the tree blocks readahead works pretty fine for bg tree, as we will read every item.
While readahead for extent tree will just be a diaster, as all block groups are scatter across the whole extent tree.

Changelog:
(v2~v3 are all original bg-tree design)
v2:
- Rebase to v5.4-rc1
Minor conflicts due to code moved to block-group.c
- Fix a bug where some block groups will not be loaded at mount time It's a bug in that refactor patch, not exposed by previous round of tests.
- Add a new patch to remove a dead check
- Update benchmark to NVMe based result
Hardware upgrade is not always a good thing for benchmark.

v3:
- Add a separate patch to fix possible memory leak
- Add Reviewed-by tag for the refactor patch
- Reword the refactor patch to mention the change of use btrfs_fs_incompat()

v4:
- Move to skinny bg tree design
Since we're going to introduce an incompatible feature, it's better to do it to extreme.

- Refactor block group item operations into their own functions So that block group item operations would hide the skinny bg item and regular bg item operations from callers, making code much easier to read.

- Add tree checker patch

Qu Wenruo (7):
btrfs: block-group: Don't set the wrong READA flag for
btrfs_read_block_groups()
btrfs: block-group: Refactor how we read one block group item
btrfs: block-group: Refactor how we delete one block group item
btrfs: block-group: Refactor how we insert a block group item
btrfs: block-group: Rename write_one_cahce_group()
btrfs: Introduce new incompat feature, SKINNY_BG_TREE, to hugely
reduce mount time
btrfs: tree-checker: Introduce checks for skinny block group item

 fs/btrfs/block-group.c          | 317 +++++++++++++++++++++++++-------
 fs/btrfs/block-rsv.c            |   2 +
 fs/btrfs/ctree.h                |   4 +-
 fs/btrfs/disk-io.c              |  18 +-
 fs/btrfs/sysfs.c                |   2 +
 fs/btrfs/tree-checker.c         |  56 +++++-
 include/uapi/linux/btrfs.h      |   1 +
 include/uapi/linux/btrfs_tree.h |  11 ++
 8 files changed, 335 insertions(+), 76 deletions(-)
Signature · 1 line
2.26.2