Extent tree v2

[josefbacik]

Existing extent tree

The existing extent tree has a lot of big advantages, but some other disadvantages.

Advantages

• Every block is tracked. We can easily (relatively speaking) find out who points at a particular data extent or metadata block.
• Reference counting is straightforward. We insert a reference for every allocation, we delete a reference for every removal, when the reference counter hits 0 we free the extent to be re-used for allocation.
• Snapshot reference counting is relatively low impact. We only modify references on COW, and thus creating snapshots is a O(1) operation.

However there are some disadvantages that are starting to become more and more of a problem. We also have some other things that are made much worse by the fact that we didn't design a system with the set of features we have today, so I would like to take this opportunity to rethink a few things related to the extent tree in order to set ourselves up better for the future.

Problems that I want to solve

• The extent tree is recursive. Because we track every block, modifying the extent tree creates new references which could potentially create new blocks. In practice there is a steady state, however this makes things like ENOSPC handling very complicated, as we have to reserve a lot of space up front in order to make sure we'll be able to make our reservations.
• The extent tree doesn't scale well to multiple modifiers. I wrote patches a year ago to cut down on the amount of places we run delayed refs, because we could get a bunch of threads trying to run delayed refs and they'd all hit lock contention on the root node. We could be better about our locking here, but in the end this is a single tree for the entire file system. Breaking this out into per-block group would make a huge impact in our parallelism.
• The csum tree is a huge source of lock contention. If you spin up a workload that bombards the system with writing to many files, you'll see latencies for finish_ordered_extent go up because of the threads getting held up in lock contention on the csum tree. Latencies in finish_ordered_extent can cause latencies on anything that needs to wait for ordered extents, like the ENOSPC flushing code or fsync.
• Relocation. Right now relocation is a huge unwieldily beast because we have to create snapshots for everything, and then modify all paths to relocated blocks at once. This generates a lot of delayed refs which can easily push transaction commits into minutes long stalls. This particular thing could be fixed without changing the extent tree, but it's a fragile scary piece of code that's prone to errors.
• Bookend extents. This is explained here in detail, but basically because we track references to full extents, we're unable to reclaim space that we're no longer referring to because we only reference the entire extent, and have no way to split the extents and free unused space.
• Qgroups. Right now the only way to track space is to do a backreference lookup for every single block that we modify. This is hugely expensive, and is a problem mostly because of how we do our reference counting. If a data block only has the original root id reference we have to do a huge lookup to see if there are any roots that point to it from higher up the backreference chain. This could be avoided if we kept track of the amount of space referenced in roots by default, eliminating the need for any backreference lookups.
• RAID5/6. @morbidrsa has a design doc for a stripe-tree to remove the on disk allocation out of the extent tree. As it stands now we use the extent tree to allocate the actual on disk space, and that is just an offset into a block group, and this maps directly to the physical space. Instead if we push the on disk translation down into a lower layer we can translate the logical address from the extent tree into any physical location on disk, and this allows us to be a lot more flexible with our on disk allocation strategies.

Uh, so how does changing the extent tree fix all these problems?

Firstly, it doesn't, at least not all of the problems. I'm wrapping all of these changes under the label "extent tree v2" because it's the biggest part, but it's actually going to be a series of on disk changes. However I do not want to do these things piecemeal because it'll hamper adoption. There needs to be a clear line in the sand where you choose "extent tree v2" and you get all these disk format changes moving forward. This will drastically simplify our testing matrix, as right now we have a lot of "features" that require toggling on and thus we have a lot of different features that can be mixed and matched. This will be a lot of changes, but it will make our lives easier going forward. My plan is to make the following specific changes

• Make the extent tree per-block group. This addresses the parallelism problem.
• Only track data extents and shared metadata blocks in the extent tree. We no longer track cow-only trees in the extent tree, we no longer track non-shared FS tree blocks in the extent tree.
• Introduce a stripe tree to translate between logical addresses and physical addresses. This is me blatantly stealing @morbidrsa's idea for my own reasons, but will allow him to do his stuff as well.
• Track direct and shared bytes per root. This will allow us to get qgroup numbers for free without backreference lookups.
• Change the reference counting rules for data extents such that they only point at their referenced extents. This does away with the bookend extent behavior and allows us to reclaim space on fragmented files.
• Make the free space tree and the csum tree per-block group. This is for the same reason as making the extent tree per-block group, it will increase our parallelism.
• Change relocation to operate on a stripe level instead of logical level. Relocation has to be super careful with it's reference counting, and can actually explode metadata usage with lots of snapshots. In addition the more snapshots you have the longer it takes. What we really care about is being able to move extents out of a block group. We can do this with the stripe tree, we simply remap the physical extents to a new location and copy the extent to the new location. Relocation becomes a matter of just copying the extents and remapping their physical location. We go at the same speed no matter how many snapshots there are.

This all sounds great, are there any downsides?

Scrub

The biggest downside that I can think of right now is scrub. Right now scrub is relatively straightforward, it just marks a block group as read only, finds all the extents in that block group, reads them because you can find the owner easily, and bam you're done. With the extent tree reference counting no longer including information about cowonly trees and non-shared fs blocks we'd have to read all of the trees by searching down them. This means that we would have to keep a cache of fs tree's blocks that we've read in order to make sure we don't scrub the same tree's over and over again. This also makes it tricky because we can no longer just mark a block group read only while we do our work.

This isn't a huge drawback, data would still work the same, and we can simply search the commit roots and skip any blocks that are younger than the generation that we started the scrub with. It will be more memory to track where we've been, but the overall complexity should be relatively minimal.

Backreferences

We would no longer be able to lookup who owns arbitrary metadata blocks. I don't believe this to be a big issue because

1. We will no longer require backreference walking for metadata blocks for qgroups.
2. We will still have the ability to find all roots pointing to a specific data extent.
   I think the only thing this affects is something like scrub, but that's because before we'd read arbitrary locations and use the reference to know which tree it belonged to. With the new scheme we'd be searching down from the tree root, so we'd know which tree we were in, and thus could print the correct information.

The specifics

A block group tree

As indicated in a comment below, our block group items are spread all over the disk and makes mount times a big problem with really large drives. Fix this by making a tree to hold all the block group items. That's it, its pretty straightforward, no other real changes here.

Per-block group trees

This will be easy enough, we know the logical offset of the bytenr we care about, we can find the block group, and thus will be able to lookup the corresponding per-bg root for whatever operation we're doing.

Track only shared blocks and data in the extent tree - CHANGING DRASTICALLY, SEE COMMENT ABOUT DROP TREES

This is the big scary thing. You can find a description of how references currently work here and here. I'm not proposing changing the items as they stand right now, simply the rules around how we change them.

We no longer add extent references for cowonly trees. This is simple and straightforward, we just don't update the extent tree with those references. These blocks only get a ref added on allocation and it removed on deletion, there's no special rules for them.

We no longer add extent references for non-shared fs tree blocks. This is where things get a little tricky. A non-snapshotted fs tree will have 0 entries for its metadata in the extent tree. In practice a non-snapshotted fs tree acts the same as a cowonly tree, we add a ref on allocation, delete it on deletion. The trick comes into play when we snapshot. The same rules will apply as they always have, with a slight change if we are COW'ing down from the owner root.

                  +-------+         +-------+
                  |       |         |       |
                  |   A   |         |   A'  |
           +------+------++---------+-+-----+--------+
           |             |            |              |
           |             |            |              |
           |             |            |              |
           |             |            |              |
           |             |            |              |
           |             |            |              |
         +-v-----+    +--v----+     +-v-----+     +--v----+
         |       |    |       |     |       |     |       |
         |       |    |       |     |       |     |       |
     +---+-------+ +--+-------+ +---+-------++    +-----+-+------------+
     |             |            |            |          |              |
     |             |            |            |          |              |
     |             |            |            |          |              |
     |             |            |            |          |              |
+----v--+     +----v--+    +----v--+     +---v---+   +--v----+     +---v---+
|       |     |       |    |       |     |       |   |       |     |       |
|       |     |       |    |       |     |       |   |       |     |       |
+-------+     +-------+    +-------+     +-------+   +-------+     +-------+

We will have a normal reference at everything at level 1 for A' but not for A. We'll cover two full examples, first cow'ing from A and then A', then the reverse.

COW from A

1. Cow the root, this works normally, no extent references modified.
2. Cow block at level 1.
3. generation < snapshot generation, look up extent reference count.
4. The extent reference count is 1 because of A', we add 1 to this because btrfs_header_owner() == root.
5. btrfs_header_owner() == root and refcount > 1, btrfs_inc_ref(full_backref == 1), set extent flags for this block to FULL_BACKREF.
6. We are at 1 level below root, free our reference to this block for A.
7. Cow block at level 0.
8. generation < snapshot generation, look up extent reference count.
9. The extent reference count is 1 because of the FULL_BACKREF from level 1. Add 1 to this because btrfs_header_owner() == root as this is implied.
10. btrfs_header_owner() == root and refcount > 1, btrfs_inc_ref(full_backref == 1), set extent flags for this block to FULL_BACKREF.

COW from A'

1. Cow the root, this works normally, no extent references modified.
2. Cow block at level 1.
3. generation < snapshot generation, look up extent reference count.
4. Reference count is 1 and FULL_BACKREF is set, btrfs_inc_ref(full_backref == 0) so we push down our normal ref to the children, btrfs_dec_ref(full_backref == 1) so that the full backref is removed from the children.
5. Free our ref for this node, count is now 0, the extent is freed.
6. Cow block at level 0.
7. generation < snapshot generation, look up extent reference count.
8. The extent reference count is 1, FULL_BACKREF is set so we btrfs_inc_ref(full_backref == 0) to push our normal reference to the children, btrfs_dec_ref(full_backref == 1) to remove the full backref reference for the children.
9. We remove our normal reference for this block the block is freed.

And now for the other way, starting with a cow down from A'

COW from A'

1. Cow the root, this works normally, no extent references modified.
2. Cow block at level 1.
3. generation < snapshot generation, lookup extent reference count.
4. We have our reference which is 1, root_objectid != btrfs_header_owner() and FULL_BACKREF isn't set, there's an implied reference for the original owner, which makes our reference count 2.
5. We are not the owner so we btrfs_inc_ref(full_backref == 0) in order to push our reference down to all the children.
6. We free our reference to this block.
7. Cow block at level 0.
8. generation < snapshot generation, lookup extent reference count.
9. We have our reference from the inc_ref before which is 1, root_objectid != btrfs_header_owner() and FULL_BACKREF isn't set, there's an implied reference for the original owner, which makes our reference count 2.
10. We are not the owner so we btrfs_inc_ref(full_backref == 0) in order to push our reference down to all the file extents.
11. We free our reference to this block.

COW from A

1. Cow the root, this works normally, no extent references modified.
2. Cow block at level 1.
3. generation < snapshot generation, lookup extent reference count.
4. There is no extent reference, which means this block isn't shared anymore, don't do anything with the extent references.
5. Free the extent to be re-used.
6. Cow block at level 0.
7. generation < snapshot generation, lookup extent reference count.
8. There is no extent reference, which means this block isn't shared anymore, don't do anything with the extent references.

The implied reference from the original owner is somewhat tricky, so the logic in update_for_cow() would need to be updated to account for these rules, which are simply

1. If root_objectid != btrfs_header_owner() && extent flags != FULL_BACKREF, implied reference.
2. If root_objectid == btrfs_header_owner() && reference exists in the extent tree, we need to convert to FULL_BACKREF and push down as we COW.

Data extent references

Data extent references need to continue to work as before, as we have more complicated operations we can do with data, such as clone. The only change here is we no longer do bookend extents. Currently the way we handle writing to the middle of an existing file extent is this (this is the normal non-compressed/encrypted case)

1. Split the file extent item.
2. The right side has offset == 0, and has it's num_bytes adjusted to reflect the new size we reference.
3. The left side has offset == the end of the split, and we inc a ref to our disk_bytenr because of the new item, using original offset (which is key.offset - file_item->offset) as part of the key.
4. Insert the new file extent that points to the new extent.

The space that is no longer referenced that exists in the slot where the new file extent was placed is now wasted, as it will not be free'd until the left and right side of the extents are eventually freed.

The new scheme will be the following.

1. Free the reference for the original file extent item.
2. Split the file extent item.
3. Add a reference to the left section of the split file extent, the file extent disk_bytenr and disk_num_bytes will be modified to reflect the actual new size of the file extent, offset remains 0.
4. Add a reference to the right section of the split file extent, the file extent disk_bytenr and disk_num_bytes will be modified to reflect the actual new size of the file extent, offset remains 0.
5. Add the new file extent.

The space in the area that the new file extent replaces will be freed to be re-allocated again.

The compression case will remain the same, as we have to have the entire compressed extent to extract the area the file extent points to, but this isn't as bad because we limit our compressed extent sizes to 128k, thus we can only waste 128k-4k worth of space per extent at any given time because of bookend extents, compared to 128m-4k worth of wasted space per extent with the normal case.

Stripe tree - PROBABLY NOT GOING TO DO THIS

EDIT: What I want to accomplish and what @morbidrsa want to accomplish are slightly different things, and trying to combine them will remove flexibility for both of us. I'm still going to tackle relocation, but this idea is being set aside.

This is fairly straightforward, it'll track the phyisical location of the logical address space. Traditionally this was just some math, we had a chunk that mapped the physical offset of a block group, and so we would just take the offset from logical address from the block group and use that offset off of the physical start of the block group.

We would replace this with a stripe tree that actually tracked physical locations for the logical offset, so it could be any arbitrary device and physical offset within that device. This would have the following items, again blatantly ripped off from @morbidrsa with some modifications for my uses as well

struct btrfs_stripe_extent {
        /* btrfs device-id this raid extent lives on */
        __le64 devid;
        /* offset from the devextent start */
        __le64 offset;
} __attribute__ ((__packed__));

key = {
        /* This is the logical address */
        .objectid = logical;
        .type = BTRFS_STRIPE_ITEM;
        .offset = size;
};

struct btrfs_dp_stripe {
        /* Original logical offset, if we were relocated. */
        __le64 original_logical_offset;
        /* How many extents are packed in here */
        __le32 nr_extents;
        /* Reseved for usage later/padding. */
        __le32 resv;
        /* array of RAID stripe extents this stripe is
         * comprised of
         */
        struct btrfs_stripe_extent extents[];
} __attribute__ ((__packed__));

key = {
        .objectid = logical;
        /* This would be less than BTRFS_STRIPE_ITEM so we could find it first. */
        .type = BTRFS_RELOCATION_ITEM;
        .offset = size;
};

/* This would be present if we had remapped a logical extent due to relocation. */
struct btrfs_relocation_extent {
        /* logical address of the new logical address */
       __le64 logical_offset;
};

Relocation - CHANGING FROM MY ORIGINAL IDEA

EDIT: Since I'm not doing the stripe tree I want to handle this in a different way. My plan is to do something sort of like what is described below, but instead make a new REMAP tree. If we relocate a block group we will set a REMAP flag on it's block group flags (maybe, I have to see if I can actually set the flags to something other than data type), and then populate the REMAP tree with where I've relocated the extents inside the block group. On mount this gets loaded up and we will translate any IO to the new logical offset where the extent resides. Once all of the extents have been freed from the block group the remap items will be deleted and the block group itself will be deleted. Of course the chunk will have been reclaimed by the time all of the blocks are remapped in the block group, so the space will be available, just the accounting will be removed later.

The new relocation behavior would be to migrate block groups as normal, but instead of walking the extent tree we would walk the stripe tree finding all stripes that exist in our logical space. We would then go find gaps in other logical areas that could host our stripe, read in the bytes from a btrfs_stripe_extent, and then write them to a new stripe and update the on disk stripe for the extent. We would keep track of the in memory mapping in an extent_map, so the operation would look something like this

1. Mark the block group read only.
2. Look up a btrfs_dp_stripe in that block group.
3. If we find a btrfs_dp_stripe then this is our first relocation.
4. If we find a btrfs_relocation_extent then this is our Nth relocation, pull the logical offset out and look up that dp_stripe.
5. Allocate a new extent in a different block group to give us a new logical offset.
6. Read in data, write data to the new logical offset.
7. Update the location of the new logical offset.
8. If the relocation_extent didn't already exist, insert a new one to point at the new logical extent.
9. If it did exist, update the logical extent.
10. Free the stripe.

Direct and shared bytes tracking per root - PROBABLY NOT GOING TO DO THIS

EDIT: We still have to do lookups after the fact to figure out if a shared extent went from N to 1 references. And we can likely accomplish this behavior with the current qgroup code, just would require some changes to runtime tracking and we don't need to do it on disk.

There is one tricky problem with qgroups, and that is the conversion of a data extent from shared to exclusive. This is tricky because it requires a full backref lookup everytime we modify an extent so that we can determine if we need to convert the file extent bytes from shared to exclusive. There is not much that can be done about this problem unfortunately, however we can make the intermediate tracking much simpler by storing the current shared and exclusive counts in the root items themselves. This would work like the following

1. Every metadata allocation is exclusive, automatically added to the root when it happens.
2. At snapshot time we do the following

orig_root->shared += orig_root->exclusive - nodesize; 
orig_root->exclusive = nodesize;
snap->shared = orig_root->shared;
snap->exlclusive = nodesize;

3. At COW time if we're shared we subtract our ->shared, the ->exclusive gets changed when we allocate a new block for the cow.
4. If the reference count went to 1 we know the root that points at us, or we have a fullbackref. If we have the root we go ahead and convert right there. If we have a fullbackref we mark the block to be looked up.

This will reduce the complexity of tracking these counters across the board, and reduce the amount of backref lookups we have to do.

[Conan-Kudo]

RAID5/6. @morbidrsa has a design doc for a stripe-tree to remove the on disk allocation out of the extent tree. As it stands now we use the extent tree to allocate the actual on disk space, and that is just an offset into a block group, and this maps directly to the physical space. Instead if we push the on disk translation down into a lower layer we can translate the logical address from the extent tree into any physical location on disk, and this allows us to be a lot more flexible with our on disk allocation strategies.

@josefbacik, @morbidrsa: any chance I could take a peek at this design doc? I'm quite interested in reading more about this...

[Zygo]

I, for one, welcome our new non-bookending data extent overlords. It makes dedupe much simpler, and eliminates an entire use case for defrag (where people run defrag to get its wasted-block-discarding side-effect).

Currently the way we handle writing to the middle of an existing file extent is this (this is the normal non-compressed/encrypted case)

...and non-shared case?

Do we figure out block-by-block whether the blocks freed by this write were the last references to those blocks in the data extent? If they were, do we update all the other references to the remaining shared parts of the extent? e.g.

1. write(subA/fileA, 0..4M); // one data extent, 4M long
2. snapshot(subA, subB); // data extent is now shared
3. write(subB/fileA, 1M..2M); // can't delete any blocks because subA still refers to all of them
4. snapshot(subB, subC); // make some more refs to the shared blocks but not the deleted ones
5. snapshot(subB, subD); // make some more snapshots so there are refs in shared metadata pages
6. write(subA/fileA, 1M..2M); // does this free the blocks from 1M..2M in the data extent, rewriting references from subA, subB, subC, subD? Is there a short cut for subC and subD that likely have their refs on a shared page, so we don't unshare shared metadata?

Or do we just fall back to the old behavior when the data extent is shared (i.e. waste the blocks)?

Edit: step 3 can't delete the blocks, but it could update all the references and split the data extent into 3 pieces with different numbers of references. This spends more work in the present to eliminate the need to build a per-block extent reference count map in the future, i.e. all the blocks in any extent are always referenced the same number of times. This might also make things like prealloc and nodatacow faster, as they currently have to build these maps.

[josefbacik]

@Zygo In your example we'd free that 1m-2m area. Here's the step by step of how it would work.

1. reference for subA logical 0-4M.
2. No change as we don't update references until the metadata is modified.
   3.a. The cow of the leaf adds a reference for subB for logical 0-4m.
   3.b. We drop our reference for subB for logical 0-4m, we add a reference for subB for 0-1M, we add a reference for subB for 5m-6m (assuming we allocate sequentially of course) pointing to subB's 1m-2m chunk of that inode, add a reference for subB for 2m-4m.
3. Nothing changes, because again no metadata is modified so we don't update references.
4. Again nothing changes.
   6a. Free reference for 0-4m for subA.
   6.b Add reference for 0-1M for subA, add a reference for 6m-7m for the inode in subA for the 1m-2m chunk, add a reference for 2m-4m for subA.
   6.c We have no reference for 1m-2m anymore, this chunk is freed.

Now say you snapshotted subB before you wrote, the yes we'd still point at the original full extent via subC and subD, but that's expected because they really would point at it.

@Conan-Kudo I'll dig it out at some point, but it's not as fleshed out as this, it's more a general proposal, basically I've watered down what he had into my stripe tree description, while leaving him the spots in the metadata to expand for his own uses in the future.

[Zygo]

OK, so what does the data extent look like after step 3b? Currently it would look like:

• data extent 0..4m, refs 3:
  • subA/fileA bytenr=0 offset=0 length=4M at inode offset 0
  • subB/fileA bytenr=0 offset=0 length=1M at inode offset 0 // lower bookend
  • subB/fileA bytenr=0 offset=2M length=2M at inode offset 2M // upper bookend
• data extent 4m..5m, refs 1:
  • subB/fileA bytenr=4m offset=0 length=1M at inode offset 1M // subB/fileA's new extent

References are currently tracked by bytenr, so when we modified subB we didn't have to change anything in subA.
But that means when we get to step 6, we can't free the space because we know there are several references to the extent but don't know (or don't want to do the IO to find out) whether the blocks are freed in the middle. So after step 6 we would currently have:

• data extent 0..4m, refs 4:
  • subA/fileA bytenr=0 offset=0 length=1M at inode offset 0
  • subA/fileA bytenr=0 offset=2M length=1M at inode offset 2M
  • subB/fileA bytenr=0 offset=0 length=1M at inode offset 0
  • subB/fileA bytenr=0 offset=2M length=2M at inode offset 2M
  • subC and subD trees refer to pages of subB referencing the above
  • no reference to data extent bytenr=0 offset=1M length=1M, these blocks are wasted
• data extent 4m..5m, refs 1:
  • subB/fileA bytenr=4m offset=0 length=1M at inode offset 1M
  • subC and subD trees refer to pages of subB referencing the above
• data extent 5m..6m, refs 1:
  • subA/fileA bytenr=5m offset=0 length=1M at inode offset 1M

Would it look like this after step 3b instead:

• data extent 0..1m, refs 2:
  • subA/fileA bytenr=0 offset=0 length=1M at inode offset 0
  • subB/fileA bytenr=0 offset=0 length=1M at inode offset 0
• data extent 1m..2m, refs 1:
  • subA/fileA bytenr=1m offset=0 length=1M at inode offset 1M
• data extent 2m..4m, refs 2:
  • subA/fileA bytenr=2m offset=0 length=2M at inode offset 2M <- subA is modified here by a write to subB
  • subB/fileA bytenr=2m offset=0 length=2M at inode offset 2M
• data extent 4m..5m, refs 1:
  • subB/fileA bytenr=4m offset=0 length=1M at inode offset 1M // same as we do now

So we solve the wasted space problem because we can clearly see at step 6 that the extent ref count of the 1m..2m extent drops to 0, and we remove the data extent from the extent tree.

But wouldn't this require updating every reference to the data extent whenever a partial reference to the extent is freed? What am I missing here?

As I understand it, after step 5 we have:

• data extent 0..1m, refs 2:
  • subA/fileA bytenr=0 offset=0 length=1M at inode offset 0
  • subB/fileA bytenr=0 offset=0 length=1M at inode offset 0
    • subC and subD's tree references the pages of subB above
• data extent 1m..2m, refs 1:
  • subA/fileA bytenr=1m offset=0 length=1M at inode offset 1M
• data extent 2m..4m, refs 2:
  • subA/fileA bytenr=2m offset=0 length=2M at inode offset 2M
  • subB/fileA bytenr=2m offset=0 length=2M at inode offset 2M
    • subC and subD's tree references the pages of subB above
• data extent 4m..5m, refs 1:
  • subB/fileA bytenr=4m offset=0 length=1M at inode offset 1M // same as we do now

so OK that's fine, as long as we are pruning the bookend extents as we go. Not very interesting.

What if we added step 7 at the end:

7. write(subA/fileA, 3m..4m)

Will that force an update of subB, subC, and subD to match subA's new extent boundaries?

• data extent 0..1m, refs 2:
  • subA/fileA bytenr=0 offset=0 length=1M at inode offset 0
  • subB/fileA bytenr=0 offset=0 length=1M at inode offset 0
  • subC and subD can refer to pages of subB here, nothing changed
• free space 1m..2m, refs 0:
  • this is now unreferenced free space
• data extent 2m..3m, refs 4:
  • subA/fileA bytenr=2m offset=0 length=1M at inode offset 2M
  • subB/fileA bytenr=2m offset=0 length=1M at inode offset 2M // write to subA modifies refs in subB
  • subC/fileA bytenr=2m offset=0 length=1M at inode offset 2M // write to subA modifies refs in subC
  • subD/fileA bytenr=2m offset=0 length=1M at inode offset 2M // this metadata page was shared, now it's not?
• data extent 3m..4m, refs 3:
  • subB/fileA bytenr=3m offset=0 length=1M at inode offset 3M // no longer referenced by subA so we modify subB
  • subC/fileA bytenr=3m offset=0 length=1M at inode offset 3M // page may have been shared by subB, subC, and subD
  • subD/fileA bytenr=3m offset=0 length=1M at inode offset 3M // now suppose there's 100 of these snapshots...
• data extent 4m..5m, refs 1:
  • subB/fileA bytenr=4m offset=0 length=1M at inode offset 1M // same as we do now
• data extent 5m..6m, refs 1:
  • subA/fileA bytenr=5m offset=0 length=1M at inode offset 1M // same as we do now
• data extent 6m..7m, refs 1:
  • subA/fileA bytenr=6m offset=0 length=1M at inode offset 3M // same as we do now

[josefbacik]

This got confusing with all the offsets, and it looks very different from what we do now, I'll write it your way

1. data extetnt 0m-4m, ref 1

• subA/fileA bytenr=0m offset=0 length=4M at inode offset 0m, 1 ref

2. No change, no metadata update.
3. Two references are added for the new bytenr, the original for subB/fileA is split.

• subA/fileA bytenr=0m offset=0 length=4m at inode offset 0m, 1 ref
• subB/fileA bytenr=0m offset=0 length=1m at inode offset 0m, 1 ref
• subB/fileA bytenr=5m offset=0 length=1m at inode offset 1m, 1 ref
• subB/fileA bytenr=2m offset=0 length=2m at inode offset 2m, 1 ref

4. Again no change, there was no metadata upate.
5. We split the original big ref for A, drop the part that's no longer referenced.

• subA/fileA bytenr=0 offset=0 length=4m at inode offset 0m, 0 ref // This is the first thing we drop
• subA/fileA bytenr=0 offset=0 length=1m at inode offset 0m, 1 ref
• subA/fileA bytenr=6m offset=0 length=1m at inode offset 1m, 1 ref
• subA/fileA bytenr=2m offset=0 length=2m at inode offset 2m, 2 ref // one for subA one for subB
• subB's stuff

Before you would never have extent references overlapping in the extent tree. I think that's what you're missing here, I would allow extent ranges to overlap, because every file extent will reference the exact length of the real extent ref they hold in the extent tree. This means you could end up with something wonky like this

[0-65m]
[0-1m]
[5m-65m]
[1m-5m]
[55m-128m]

If I drop [1m-5m] we immediately get that space freed (well "immediately", it'll be pinned of course).

This does make free'ing waaaaay more complicated of course. Because if we do something like

[0-4m]
[1m-2m]
[3m-4m]

and we free [0-4m] we have to go and see if we have any references in that range. I will handle this by using our range locking to lock the extent we're messing with. So I'll lock [0-4m], then look to see if I have any overlaps. If there's any range that gets freed it'll get added to the pinned thing and we'll carry on.

There will clearly be a very robust self-test written for this code, because there will be plenty of dark corners.

[Zygo]

I would allow extent ranges to overlap

Ah, indeed that is the missing piece. Then for free space reclaim we just look at the bytenr range covered by the data extent that hit 0 references, and free any blocks that are not overlapped by another data extent, i.e. we don't need to look at any subvol trees, because everything we need to know about which blocks are referenced is available in the extent tree (though possibly up to 128M-4K before the freed item, so it could be a few hundred pages away in Dave-Chinner-style test cases).

Thanks, I think I see how it works now.

[josefbacik]

Block group tree

(I forgot to add this to my design doc, I will edit it once I'm at a real computer).

We load all of the block groups on mount, which we don't necessarily have to do, but changing it could be annoying. At any rate all of the block groups are indexed by bytenr, so they're spread all out on the disk. This makes mounting very large file systems kind of slow. Fix this by adding a new tree dedicated to the block groups, it'll simple have block group items in it and they'll look exactly like they do today. This way they'll be all closely located to each other and we'll be able to mount a lot faster.

[fdmanana]

Existing extent tree

The existing extent tree has a lot of big advantages, but some other disadvantages.

Advantages

• Every block is tracked. We can easily (relatively speaking) find out who points at a particular data extent or metadata block.
• Reference counting is straightforward. We insert a reference for every allocation, we delete a reference for every removal, when the reference counter hits 0 we free the extent to be re-used for allocation.
• Snapshot reference counting is relatively low impact. We only modify references on COW, and thus creating snapshots is a O(1) operation.

However there are some disadvantages that are starting to become more and more of a problem. We also have some other things that are made much worse by the fact that we didn't design a system with the set of features we have today, so I would like to take this opportunity to rethink a few things related to the extent tree in order to set ourselves up better for the future.

Problems that I want to solve

• The extent tree is recursive. Because we track every block, modifying the extent tree creates new references which could potentially create new blocks. In practice there is a steady state, however this makes things like ENOSPC handling very complicated, as we have to reserve a lot of space up front in order to make sure we'll be able to make our reservations.
• The extent tree doesn't scale well to multiple modifiers. I wrote patches a year ago to cut down on the amount of places we run delayed refs, because we could get a bunch of threads trying to run delayed refs and they'd all hit lock contention on the root node. We could be better about our locking here, but in the end this is a single tree for the entire file system. Breaking this out into per-block group would make a huge impact in our parallelism.
• The csum tree is a huge source of lock contention. If you spin up a workload that bombards the system with writing to many files, you'll see latencies for finish_ordered_extent go up because of the threads getting held up in lock contention on the csum tree. Latencies in finish_ordered_extent can cause latencies on anything that needs to wait for ordered extents, like the ENOSPC flushing code or fsync.

Not anymore for fsync, it's very limited now since it only affects the slow and less common path.

https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=487781796d302266aff993bee17d4e1ddd73445b

[cmurf]

What's the likely conversion method from v1 to v2? Would it be more or less complex than free space cache v1 to v2? Right now we see a wide range of mount time for initial v2 creation, from seconds to many hours. I'm wondering about the scalability of extent tree conversion, but maybe it's too soon to tell.

[josefbacik]

@cmurf it will be an offline conversion tool, the changes are too complicated to do online on mount like what we did with the free space tree.

[josefbacik]

I've edited my original comment to indicate what the plan is now after thinking about it for a month and starting the work. The hilights are

• No more stripe tree. This is because what I want is a little different from what @morbidrsa wants and shoehorning them together is likely to cause more pain than it is to make our lives easier.
• The mechanics of the relocation change is slightly reworked because of the above change. The general plan is still the same, but how it works will be slightly different.
• The qgroup changes are scrapped. I can accomplish the same behavior without on disk changes, and we still have to do backref lookups for N -> 1 changes on shared extents and there's no real good way to eliminate those.
• Added the block group root tree to the original comment.

[Conan-Kudo]

No more stripe tree. This is because what I want is a little different from what @lorddoskias wants and shoehorning them together is likely to cause more pain than it is to make our lives easier.

Who is @lorddoskias?

[josefbacik]

No more stripe tree. This is because what I want is a little different from what @lorddoskias wants and shoehorning them together is likely to cause more pain than it is to make our lives easier.

Who is @lorddoskias?

The wrong fucking person, my bad. I meant @morbidrsa.