[lkml]   [1997]   [Dec]   [28]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
Messages in this thread
SubjectFilesystem optimization..

While staring dejectedly at a filesystem holding a tad of 3 million
files, and looking at the 'orrible latency to open a file, it occured
to me that with most usage patterns, two things are true:

1) There are very few inodes that have more than one parent
(i.e. more than one filename pointing to them)
2) The vast majority of the time, the inode is read
immediately following the filename.
3) On most modern hard disks, the cost of reading 4K as
opposed to reading 1K is minute (it's dominated by
seek times etc).

So: Why not embed the inode directly into the directory itself?

The obvious drawback that suggested itself was addressing. I first
thought of just using the byte offset from the beginning of the file
system, but this is impractical (you don't want to force all your
inodes to be in the first 4 Gig of the filesystem).

Then it occured to me that if you force aligning inodes on 64 byte
boundries, the addressable filesystem goes to 256gig (probably enough
for now).

The change should dramatically improve path lookups (the inode for the
next directory segment is inline with the name, so saves you a seek
per segment), random open()'s (saves you a seek per open), find(1)'s
all over, etc etc.

It also means that inodes are allocated dynamically, that you don't
need to pre-allocate vast numbers of inodes 'in case', which saves a
fair bit of space on large file systems. Also no inode bitmaps etc.

In theory, this should be pretty simple to implement..... :)

The sole cost I can think of is that directories holding a _large_
number of files will be slower to read (I.e. the size of the directory
is such that the read time dominates the seek time).

The complicating factor is: What do you do when
file X is created.
hard link from file Y in another directory is make to X.
X and the directory containing X are removed.

Because the inode for Y is in the directory containing X, you can't
free the directory.

Possible solutions:
Move the inode to the directory containing Y.
Reference count the directory?

Comments?? (people dying to implement such a beast? :)


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