[Top] [All Lists]

RE: Limits on agi->agi_level (and other btree depths?)

To: Eric Sandeen <sandeen@xxxxxxxxxxx>, xfs-oss <xfs@xxxxxxxxxxx>
Subject: RE: Limits on agi->agi_level (and other btree depths?)
From: Shaun Gosse <sgosse@xxxxxxx>
Date: Thu, 13 Feb 2014 01:01:50 +0000
Accept-language: en-US
Delivered-to: xfs@xxxxxxxxxxx
In-reply-to: <52FC09AB.3030209@xxxxxxxxxxx>
References: <52FC09AB.3030209@xxxxxxxxxxx>
Thread-index: AQHPKE3EXpXBTYd/LUmeWaMJV72/rpqyVtHQ
Thread-topic: Limits on agi->agi_level (and other btree depths?)
>  (cue dchinner working out that 9 levels is 59 bazillion jillion items, and 
> will never be hit?)

I don't know the XFS code and how it does B-trees. This is a very rough initial 
estimate that would apply to any sort of tree. Since we want to know when we're 
required to exceed a depth of 8, presume a full tree for simplicity. Say your 
branching factor for the whole tree is equal to the maximum depth. If it's 
higher, you have more room of course. But if it is equal, then you have 8**8 
leaf nodes (calling the root node a depth of zero) before you have to add a 
depth 9 (or increase your branching factor; if there is a limit that might be 
hit, this would be the way to go to avoid more depth).

That gives you about 16 and three quarters million leaf nodes to work with. Of 
course if you're storing multiple entries per node, that gives you a constant 
factor on top.

In any event, sounds like it may be worth considering whether the limit could 
ever be reached and how to extend it if so. Given the discussion that's 
occurred about stack size, I could see where recursing on ever-deeper trees 
could be problematic, although perhaps it would be possible to use 
tail-recursion in anything which doesn't need to scan the full tree at least 
(if that's not already done).

Given that XFS has a theoretical maximum filesystem size of 18 Exabytes, for a 
hypothetical filesystem composed of 1k sized files (just to be maximally 
difficult; worst-case analysis), that's about 2 x 10**16 inodes to store. I'm 
sure this would make a lot of other things break first, but it would also blow 
past the number of leaves you can have in a tree of maximum height of 8, unless 
your branching factor goes above 50. And I doubt more than 100-1000 entries are 
being squeezed into a leaf, if that.

Sorry, I don't normally jump into the discussions on here, just follow along, 
since I'm not very familiar with the XFS code, but this seemed like an 
interesting question which could be partially addressed without any familiarity 
with the internals.

I will be curious to read what XFS is actually doing in this area in greater 
detail. And I look forward to the XFS test (and rig) that can manage to break 
it / exercise the limit...is there any known limit to the number of files? 
just lists max file size and file system size. If nothing else, it would be 
worth determining the limit and documenting it.


<Prev in Thread] Current Thread [Next in Thread>