One other trick is just a negative cache:

Each in memory directory has a bucket list in it
for power of two up until MAXFILELEN.

If you have to do a scan, just populate the negative
entries.

Then only "fix" the negative entries if you delete something.

Then you'll avoid repeated scans when there's no space.


* Alfred Perlstein <bright@mu.org> [050119 21:14] wrote:
> 
> There's two ways to solve this, one is easy but wastes space, the
> other is hard but more space effecient.
> 
> Easy way:
> Keep track of the amount of free space in a directory versus its
> size.
> 
> If the amount of free space is below a threshold then just
> append to the directory.
> 
> (this should make creating large numbers of files very fast
> as we'll always be full or near full so we'll just append to
> the directory)
> 
> 
> Hard way:
> Keep an in memory bucket list of available sizes.
> 
> The bucket list can be N offsets into the directory for
> sizes that are power of two up to MAXFILELEN.
> 
> Tune the bucket structure to the size of the directory.
> 
> Make sure to keep a "negative entry" for sizes not seen.
> 
> Whenever you delete make sure to update your bucket structures to
> include the deleted space or mark the bucket as overflowed if all
> the entries for a particular size have been taken.
> 
> Then finding a free space is easy.  Do a best fit.
> 
> -- 
> - Alfred Perlstein
> - Research Engineering Development Inc.
> - email: bright@mu.org cell: 408-480-4684

-- 
- Alfred Perlstein
- Research Engineering Development Inc.
- email: bright@mu.org cell: 408-480-4684