lkml.org 
[lkml]   [1998]   [Jan]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: Filesystem optimization..
Date
From

In message <uflnwu4fap.fsf@dax.dcs.ed.ac.uk>, Stephen C. Tweedie writes:
> Hi,
>
> Michael O'Reilly <michael@metal.iinet.net.au> writes:
>
> > While staring dejectedly at a filesystem holding a tad of 3 million
> > files,
>
> OUCH!
>
> > and looking at the 'orrible latency to open a file, it occured
> > to me that with most usage patterns, two things are true:
>
> > ...
>
> > So: Why not embed the inode directly into the directory itself?
>
> Ted has answered most of the reasons why not! A directory lookup *must*
> include permissions checks. The _real_ solution is to allow optional
> btree-structured directories for really large filesets, so we wouldn't
> have to make the hack of doing multi-dir-level hashing ourselves. An
> application is never going to be able to fake fast lookup as well as the
> kernel ought to be able to do it.

Hmm. I think there's a few misconceptions here. The main problem with
such a large fileset (from what I've been able to measure) is not the
directory lookup, but the actual open of the file itself. The
directories mostly get cached, but the file inode set is way too big
to cache. The terrible cache locality means that we need do physical
I/O to read the file inode a relatively huge percentage of the time.

The inode emedding in the directory doesn't affect the permissions
check at all.

Logic is something like:

When opening a file:
do normal directory search, skipping dead space in directories
as normal.
find inode number for file.

block = inode number / (sizeof(block) / sizeof(inode));
offset = inode number % (sizeof(block) / sizeof(inode));

read_block(block); /* almost certainly in cache, cos it's
going to be the same block the
filename was in. */

inode = (struct inode *) ((char*) block + offset);

continue as normal.
[ assumption is the inodes are sizeof(inode) aligned in the block ]

As far as the lookup code goes, it doesn't even notice that the inode is
actually embedded in the directory. It just does an inode read.

The only function that takes a major change is the code to actually
allocate the inode. There is does:
open directory where file is being created.
allocate (probably from end of block) space of sizeof(inode).
Mark the space as dead + unusable as far as the directory is
concerned.
inode number = munge(block,offset) as per above.

No permissions issues here. (if you have write access to the
directory, you have write access to the directory for allocating inode
space).

The complication is when deleting a directory, and a fairly simply
scheme is:

Use 2 bits per block in the free block bitmap.
Call 1 bit 'used'.
Call the other 'inode'.
When allocating an inode in a directory block, set the 'inode' bit.
When allocating a block for anything set the 'used' bit.
When deleting a block from file/dir, reset the 'used' bit.
When free'ing an inode, and this is the last inode in the block, reset
the 'inode' bit. (easy enough to. If an inode is embedded in a block,
you're guarenteed the block is directory structured).

and voilo! :) This gives you enough redundancy to do a meaningful
fsck(8) too, at the cost of doubling the free-space bitmap.

Hopefully this clarifys things a lot.

> There is one thing which has been at the back of my mind for a while
> which could help, though. Although ext2 has remarkably good performance
> at small block sizes, it does suffer if files start small and get
> extended a little at a time --- each extent can add more fragmentation,
> and so the file grows all over the disk.
>
> This is particularly bad for directories, which under many typical loads
> (caches, news spools, home dirs) grow in a haphazard fassion over time.
> If directory lookups dominate performance, then this performance penalty
> can become quite severe.

Interesting and useful. In my application it wouldn't do anything tho.
The directories tend to stay constant sizes, are created and filled
in-order, and the files are all written in one block, and don't get
appended to. :(

Michael.

\
 
 \ /
  Last update: 2005-03-22 13:41    [W:0.024 / U:0.160 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site