Changing filesystem resize patterns

They already tend to, though there are maximum size bounds for "internal structures" that pose limits. The problem is that once the structures are laid down on disk, they are fixed for the life of the filesystem. Growing can only replicate more of those same sized structures, and that's where all the problems lie.

> Have I over-simplified too much?

No, but you've assumed that the filesystems don't already do that. The problem is this scaling happens at mkfs time and that sets a lot of things in stone that have been assumed will never change.

> So: could we scale these tables based on their location instead of the total size?

Yes, we could, but that involves changing the on disk format to add a bunch of new metadata to support both variable size structures and structures of unpredictable, unknown locations.

I'll speak for XFS here, because the common question is "why can't we just implement variable size allocation groups?" and that's exactly what you are asking here.

The size of the AG is fixed at mkfs time. On a 2GB fs, that's 500MB. Grow that out to 10TB, and we have 20,000 AGs and it's the AG count that causes issues for us. AGs can be up to 1TB in size - a 10TB filesystem will be laid out with 10x1TB AGs, or if it on RAID5/6 it will have 32x~300GB AGs (because RAID has more disks and can handle more concurrency). So you can see the difference in layout between 20,000x500MB AGs vs 10x1TB AGs.

The problem is not the size of the AG - they are all indexed by btrees, so there is very little in way of performance difference between maintiain free space indexes in a 500MB AG and a 1TB AG. They scale with size just fine and we already support different sized AGs at runtime - they have an internal length variable in their headers and the last AG never fits neatly into the device and so is always shorter than the rest.

But the problem here is that all the algorithms that assume that all AGs are teh same size. e.g if we know the size and the AG number, right now we know exactly where it is located on the block device. We know it is equal to all other AGs, too, so algorithms do linear AG iteration because no one AG is more likely to be better than any other based on physical characteristics. As such, we have one variable in the superblock that tells us what the size of an AG is, and another that tells us the AG count. Our backup for that information for disaster recovery is in the AG headers - we have secondary superblock in the first sector of every AG.

So let's look at disaster recovery - the first requirement for any filesystem design is to be able to recover from loss of key structures. Right now, if we lose the primary superblock and AG 0 headers (say someone wipes out the first 64kB of the block device) then we have to do a sector-by-sector search to find the first secondary superblock in AG #1. We optimise the search based on device size and what mkfs defaults would do (so might only take a single IO to find a valid secondary), but if that doesn't work we have to read every single sector out past the first TB to find the start of the second AG. Then we can recover the size of the AGs, grab all the other secondary superblocks, validate them and recover the primary.

Now, if we have variable size AGs, how do we recover from the loss of the superblock and/or the AG location/size index tree? How do we find the start of all the AGs in the filesystem and validate they are correct? We can't play mkfs tricks or just find the secondary SB in AG#1 - we have to read every single sector of the block device to find every AG header.

How long does that take if we have a PB scale filesystem? At a scan rate of 1GB/s, just that scan will take roughly a day per PB. IOWs, even if we solve these problems, recovering from the loss or corruption of the AG indexing structure can be catastrophically bad from a disaster recovery POV - if it's going to take a week just to find the AG headers, we may as well just throw it away and restore from backups.

> So: could we scale these tables based on their location instead of the total size?

Sure, we could do that, but that still brings a host of other problems with it and introduces a whole set of new ones.

e.g. allocation algorithms that select AGs with larger free spaces first then always try exact or near locality allocations for all followup allocations to that inode. That changes the filesystem fill algorithms from low->high to high->low because all the AGs with large free spaces are high up in the address space. i.e. on physical disks we change from filling the outer edge (fastest) first, to filling from the inner edge (slowest) first.

Changes like this also have implications for AG lock ordering which only allows multiple AGs to be locking in ascending order. If we allocate from the highest AG first and it ENOSPCs mid operation, we need to allocate from another AG to complete it. If the only Ags we can chose from are lower down, then we can deadlock with other multi-ag allocations. The only answer there is *suprious ENOSPC*, because shutting down the filesystem when stuff like this happens is not an option. This spurious ENOSPC normally only happens when the filesystem is nearly full, so it generally isn't an unexpected result. But variable AG sizes will bring this behaviour out much earlier when the filesystem is nowhere near full.

There's there's just the general variable AG size issues, like the internal sparse adress space that XFS uses for inodes and filesystem block addressing (detect a trend here?). We encode the AG number into the high bits, and the block number in the AG into the low bits (i.e. AGNO|AGBNO). The number of bits each use is actually variable and based on the size of the AG set at mkfs time. Inode numbers are similar in being "AGNO|AGBNO|Inode in chunk" - it's a sparse encoding of it's location in the address space and so we can go straight from inode number to it's physical location just with a couple of shifts and some masking.

Hence if the AG is going to be variable size, then we always have to reserve 32 bits for the AGBNO in this address space so we can always support 1TB AG sizes in the address space. This means the every AG will actually consume 1TB address space, regardless of it's actual size.

At this point, the maximum size of the filesystem drops - it's no longer 8EB, it's 8EB - all the unused address space. IOWs, even just calculating the actual physical capacity of the filesystem becomes hard - we have to add up the size of each individual AG rather than just multiplying 2 numbers together. When we support 2^32 AGs, that's a non-trivial problem.

Then there is inode numbers instantly going over 32 bits. If the AG #0 is only 500MB in size, and the user selects the "inode32" allocator, they now only have a maximum of 500MB of storage for inodes in the entire filesystem. That's because inode numbers are sparse and putting them in AG #1 will use 33 bits of address space and hence have a 33bit inode number. With the current layout, there's 200 AGs that inodes could be placed in (a full 1TB of storage) before the inode address space goes over 32 bits...

Hence going to variable size AGs based on size of the device has user visible implications, even for users that haven't used grow and will never use grow. Put that on top of having to make serious changes to the on disk format, tools, disaster recovery algorithms and redesign runtime algorithms to support variable sizes sanely - we are effectively talking about redesigning the entire core of the filesystem.

> But it seems a lot less than "designing a new filesystem".

The effort is on the same level of on-disk format changes that the ext3->ext4 transition involved. I'll leave you to decide if that's less effort than "designing a new filesystem" given the years of work that involved.

-Dave.