Re: Large directories and poor order correlation

[Ted Ts'o <tytso@mit.edu>]

On Tue, Mar 15, 2011 at 02:33:27PM +0100, Rogier Wolff wrote:
> IMHO, the most important part is "up to and including the stat". It
> should be possible to get the directory, and inode info all inside the
> same "16Mb" part of the disk. This would result in (after a few seeks)
> the rest of the accesses coming from the disk's cache.

It depends on your workload.  In the case of dpkg, everything fits in
cache (usually) so after the first operation this is no longer a
concern.  But all of the data blocks of /var/lib/dpkg/info/* is huge,
since not using a real database means that a 4k block is consumed for
300 bytes of data, so fitting all of the data blocks in memory
generally doesn't work, which is why the dpkg folks are sorting by
block number.

> This would mean that you should allocate directory blocks from the end
> PREVIOUS block group.... 

We do something else, which is we group all directory blocks together
at the beginning of each flex_bg.  This tends to reduce free space
fragmentation, and it helps to optimize for large files that are
bigger than a block group, and where you want to have contiguous
regions larger than a bg --- so breaking up the space every bg is not
a great idea.  Again, with general purpose file systems you can't just
optimize for one thing, and life is full of tradeoffs.

      	   	    	    	       	    - Ted