Re: radix tree implementation for quota ?

[Joerg Sonnenberger <joerg%britannica.bec.de@localhost>]

On Sun, Nov 28, 2010 at 05:53:59PM +0100, Manuel Bouyer 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 :)

A radix tree is kind of a bad choice for this purpose. The easiest
approach is most likely to have two levels. The lower level consists of
pairs (uid, value) sorted by uid. Blocks don't have to full, e.g. a uid
of -1 is considered unused. Alternatively, special case the uid of 0.
The upper level consists of (uid,block) offsets with the guarantee that
the block starts with the entry for that uid. Keep this sorted as well.
On insert split a block if there is no space for the new uid. This keeps
disk usage to >= 50% if no removal is desired. Look up is bsearch()+read()
+bsearch() if the upper level is kept in memory. With a block size of 4KB,
this requires one block for ~32k users per filesystem as permanent
kernel memory.

Joerg