Re: radix tree implementation for quota ?

[Manuel Bouyer <bouyer%antioche.eu.org@localhost>]

On Sun, Nov 28, 2010 at 09:34:29PM +0000, David Laight wrote:
> On Sun, Nov 28, 2010 at 06:27:07PM +0100, Manuel Bouyer wrote:
> > > Wouldn't a hash table work?
> > 
> > I think it's too dependant on uid distribution, or even how much uid you
> > have. a tree scales and adapts better.
> 
> I agree, hash tables often degenerate into a linear search.
> This means that it is still linear, just 'n' times faster that a
> simple linear search.
> 
> It might be worth using a simple hash to cache recent lookups into
> the tree.
> 
> OTOH it is worth remembering that there is already a 'per uid' structure
> (IIRC currently hashed % MAXUSERS) used for counting processes per user.
> Would seem relevant to hang the per-mount data of this structure.
> (and maybe use a better lookup than the current hash - it is one of the
> few uses of MXUSERS).

I don't think this would work well for NFS servers, where users have no
process running on the system doing the limit checks, while there may
be lots of different UIDs active at the same time. This is exactly my
use case :)

> 
> On disk, I'm not sure.
> Once you've read a disk block, you might as well do a linear search!

except the quota data may well need several disk blocks.

> More problematical is some kind of log so that you don't need to scan
> the entire fs after a system crash...

it doesn't seem so hard with WAPBL, once the usage data are on the same disk
as filesystem metadata. disk block for usage data update can be integrated in
the same WAPBL transaction which updates filesystem metadata.

-- 
Manuel Bouyer <bouyer%antioche.eu.org@localhost>
     NetBSD: 26 ans d'experience feront toujours la difference
--