Re: simple Chunk allocator like calculation to replace Factor based calculation

[Hugo Mills <hugo@carfax.org.uk>]

   Oh, I forgot: the write-up of this algorithm, sich as it is, is at
https://carfax.org.uk/files/btrfs-usage.pdf, if anyone's interested.
It's incomplete because I was unable to complete a formal proof of its
correctness.

   Hugo.

On Fri, Oct 02, 2020 at 11:13:13AM +0100, Hugo Mills wrote:
>    We can do this calculation precisely, in at most O(n^2) time, where
> n is the number of *devices* in the FS.
> 
> Inner step:
> 
>    Let s be the number of devices allocated in a single allocation step(*).
> 
>    Sort the n devices in decreasing order of size, c[i].
> 
>    For each device i, let b[i] = floor(sum c[j] / (s-i)), where the
>       sum is taken over all devices smaller than i.
> 
>    Throw out values of b[i] where c[i] < b[i].
> 
>    Let B = floor(sum c[j] / n), where the sum is taken over all devices.
> 
>    Let t_max be the smallest value of B and the remaining b[i].
> 
>    t_max is the number of allocations that can be performed on the
>    filesystem using an allocation size of s.
> 
> Outer step:
> 
>    If the RAID level has a fixed s value, run the inner step and stop.
> 
>    If the RAID level can vary, run the inner step, setting s to the
>    number of devices with free space on at each iteration.
> 
> 
> (*) single:       s = 1
>     RAID1(c3,c4): s = 2(,3,4)
>     RAID10:       s = 4
>     RAID0,5,6:    s = the number of devices with free space
> 
>    This is the algorithm used in the carfax btrfs-usage calculator,
> and has been fairly comprehensively battle-tested over the years,
> although I was unable to prove its correctness mathematically.
> 
>    Hugo.
> 
> On Fri, Oct 02, 2020 at 05:06:14PM +0800, Wang Yugui wrote:
> > Hi,
> > 
> > We have another user case difficult to process.
> > 
> > #with a fix of RAID10 to RAID1C4
> > #for RAID10, the iteration number is not big.
> > #but for RAID1C4,the iteration number is big.
> > 
> > Use case: 
> > Add 10T disk * 4  to near full  full RAID1C4 10T *4;
> > free space maybe be such as 10T,10T,10T,10T,2G,2G,2G,2G.
> > 
> > There maybe a lot of iterations for this case because of 2G chunk size,
> > and then result in bad performance?
> > 
> > 
> > Best Regards
> > 王玉贵
> > 2020/10/02
> > 
> > > 
> > > 
> > > On 2020/10/2 上午9:59, Wang Yugui wrote:
> > > > Hi,
> > > > 
> > > > 
> > > >>> such as
> > > >>> 1) RAID10 with 8T,1T,1T,1T,1T
> > > >>>     the virtal chunk size of 1st iteration:	1T or 0.33T?
> > > >>>     1T    chunk will use 4T at most
> > > >>>     0.33T chunk will use 5.33T at most?
> > > >>
> > > >> You didn't get the point.
> > > >> For the each loop we:
> > > >> - Sort the devices with their free space.
> > > >>   In this case, it's 8, 1, 1, 1, 1.
> > > >>
> > > >> - Round down to dev increament
> > > >>   Then we got 8, 1, 1, 1.
> > > >>
> > > >> - Then allocate chunk
> > > >>   Since the biggest unallocated space is 1T, we allocate a RAID10 with
> > > >>   1T stripe size, which will be a 2T chunk.
> > > >>
> > > >>   The remaining size is 7, 0, 0, 0, 1.
> > > > 
> > > > That is the problem.  1T chunk size is too big for this case.
> > > > 
> > > > if we use 1/3T chunk size, the result will be same as 1G chunk size.
> > > > 
> > > > 1st:	8T - 1/3T     2/3T, 2/3T, 2/3T, 1T
> > > > 2nd:	8T -2/3T     2/3T, 1/3T, 1/3T, 2/3T
> > > > 3rd:	8T -1T        1/3T, 1/3T, 0T, 1/3T
> > > > 4th:	8T -4/3T     0T,     0T,   0T,  0T
> > > 
> > > You're right, smaller balloon chunk size would make the allocation more
> > > accurate to real chunk allocator.
> > > 
> > > However that would slow down the calculation, don't forget that we need
> > > to run that calculation on each chunk allocation.
> > > Changing the balloon chunk allocation size dynamically may improve this.
> > > 
> > > But please also keep in mind that, with less and less space left, our
> > > predication will be more and more accurate, and under estimate is always
> > > less a problem.
> > > 
> > > So I'll keep your suggestion for future enhancement.
> > > 
> > > Thanks for pointing out the pitfall of current calculation,
> > > Qu
> > > 
> > > > 
> > > > Best Regards
> > > > 王玉贵
> > > > 2020/10/02
> > > > 
> > > >>
> > > >> - We go to next round.
> > > >>   No way to allocate new chunk.
> > > >>
> > > >> In this case, we can only get 2T chunk.
> > > >> Just as the chunk allocator do.
> > > >>
> > > >>>
> > > >>> 2) RAID10 with 8T,1T,1T,1T,0.5T
> > > >>>     the virtal chunk size of 1st iteration:0.5T or smaller?
> > > >>
> > > >> Still the same, 2T chunk can be allocated using the largest 4 devices.
> > > >>
> > > >> Thanks,
> > > >> Qu
> > > >>
> > > >>>
> > > >>> Best Regards
> > > >>> 王玉贵
> > > >>> 2020/10/02
> > > >>>
> > > >>>
> > > >>> --------------------------------------
> > > >>> 北京京垓科技有限公司
> > > >>> 王玉贵	wangyugui@e16-tech.com
> > > >>> 电话：+86-136-71123776
> > > >>>
> > > >>
> > > > 
> > > > --------------------------------------
> > > > 北京京垓科技有限公司
> > > > 王玉贵	wangyugui@e16-tech.com
> > > > 电话：+86-136-71123776
> > > > 
> > > 
> > 
> > --------------------------------------
> > 北京京垓科技有限公司
> > 王玉贵	wangyugui@e16-tech.com
> > 电话：+86-136-71123776
> > 
> 

-- 
Hugo Mills             | Gomez, darling, don't torture yourself.
hugo@... carfax.org.uk | That's my job.
http://carfax.org.uk/  |
PGP: E2AB1DE4          |                                       Morticia Addams