On Wed, May 07, 2014 at 04:09:27PM +0200, David Sterba wrote:
> On Tue, May 06, 2014 at 05:43:24PM +0100, Hugo Mills wrote:
> > > >So in my case when I hit that case, I had to use dusage=0 to recover.
> > > >Anything above that just didn't work.
> > >
> > > I suspect when using more than zero the first chunk it wanted to balance
> > > wasn't empty - and it had nowhere to put it. Then when you did dusage=0,
> > > it
> > > didn't need a destination for the data. That is actually an interesting
> > > workaround for that case.
> >
> > I've actually looked into implementing a "smallest=n" filter that
> > would taken only the n least-full chunks (by fraction) and balance
> > those. However, it's not entirely trivial to do efficiently with the
> > current filtering code.
>
> I've prototyped something similar, to limit the number of balanced
> chunks by a number. To achieve "n least-full chunks" would be an
> iterative process of increasing the usage filter and limiting the number
> of chunks until the desired N is reached.
>
> N=n
> F=0
> while (N > 0) {
> balance -dusage=F,limit=N
> N -= <number of balanced chunks>
> F++
> }
>
> The patch is in branch dev/balance-limit in my git repos.
>
> We can then implement the n-least-full as a synthetic filter from
> userspace.This is inefficient, because we've got an O(m) pass through all the chunks for every call. If we reduce the number of calls by increasing the increment of F (F+=3, say), then we risk overbalancing, or missing out on smaller chunks we could have balanced earlier. From a practical point of view, it may make little difference, but the computer scientist in me is going "ewwwww". The other method, for small n only, would be to construct the list first, an O(m log n) operation for a filesystem of size m, requiring O(n) storage, and then iterate over just those chunks. The problem with that is the storage requirements, and keeping track of the state of the list for restart purposes. [actually, there's probably an O(m) algorithm to get the n smallest items, but those are a bit complicated] Hugo. -- === Hugo Mills: hugo@... carfax.org.uk | darksatanic.net | lug.org.uk === PGP key: 65E74AC0 from wwwkeys.eu.pgp.net or http://www.carfax.org.uk --- A diverse working environment: Di longer you vork here, di --- verse it gets.
signature.asc
Description: Digital signature
