Re: radix tree implementation for quota ?

[Adam Hoka <adam.hoka%gmail.com@localhost>]

On Sun, 28 Nov 2010 09:31:47 -0800
Matt Thomas <matt%3am-software.com@localhost> wrote:

> 
> On Nov 28, 2010, at 9:27 AM, Manuel Bouyer wrote:
> 
> > On Sun, Nov 28, 2010 at 05:21:52PM +0000, Sad Clouds wrote:
> >> On Sun, 28 Nov 2010 17:53:59 +0100
> >> Manuel Bouyer <bouyer%antioche.eu.org@localhost> wrote:
> >> 
> >>> One open question is how to store quota informations on disk.
> >>> At this time we use one big array indexed by uid or gid. This can
> >>> be very space-consuming if you have a very sparse uid/gid allocation,
> >>> this is why I don't think this simple format is suitable any more
> >>> (especially with 32bits uid/gid, and 64bit storage for various values).
> >>> Linux uses a radix tree for this, and I coudln't come up with a better 
> >>> idea :)
> >> 
> >> 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.
> 
> If you just read and write on mount/unmount/fsck, a linear text file 
> would work that you convert into a rb-tree or p-tree on mount and then
> read the tree and emit a text file on close.
> 
> This does assume you are going to cache the entire quota file while
> the file system is mounted.

online quota changes are desired for a new implementation

-- 
NetBSD - Simplicity is prerequisite for reliability