Fastest way to "find / -mtime +7".....

Fastest way to "find / -mtime +7".....

[Ed Walker]

I've got a lot of small maildir files stored on a reiser-fs  
partition.  Currently we expire out the old stuff using
     find /mail -mtime +7 -type f -print0 | xargs -0 rm -rf

this is pretty slow on reiser, at least compared with ext2/3, and I  
understand that it may be because the find command returns the names  
in a non-optimal order (ie readdir order?).

Is there something we can do to speed it up?  Any suggestions?

Thanks-

Ed

Re: Fastest way to "find / -mtime +7".....

[Jonathan Briggs]

[-- Attachment #1: Type: text/plain, Size: 971 bytes --]

On Tue, 2005-07-19 at 10:55 -0700, Ed Walker wrote:
> I've got a lot of small maildir files stored on a reiser-fs  
> partition.  Currently we expire out the old stuff using
>      find /mail -mtime +7 -type f -print0 | xargs -0 rm -rf
> 
> this is pretty slow on reiser, at least compared with ext2/3, and I  
> understand that it may be because the find command returns the names  
> in a non-optimal order (ie readdir order?).
> 
> Is there something we can do to speed it up?  Any suggestions?
> 
> Thanks-
> 
> Ed

I think Reiser3 is slow more because with mtime, find has to stat each
file.  I did a couple ad-hoc tests and it seems to be about 40x slower
on directory list with stat than just plain directory lists.  I didn't
try ext2/3.

I believe the reiser3 directory order problems with maildir are related
to something else, like not finding new mail at the end of the
readdir()? 
-- 
Jonathan Briggs <jbriggs@esoft.com>
eSoft, Inc.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Fastest way to "find / -mtime +7".....

[Ragnar Kjørstad]

On Tue, Jul 19, 2005 at 12:48:53PM -0600, Jonathan Briggs wrote:
> > this is pretty slow on reiser, at least compared with ext2/3, and I  
> > understand that it may be because the find command returns the names  
> > in a non-optimal order (ie readdir order?).
> 
> I think Reiser3 is slow more because with mtime, find has to stat each
> file. 

The two issues are related.

Readdir will return the filenames in hash order. Find will then go and
stat each file, still in hash order.

Problem is, the inodes are not sorted in directory hash order on the
disk. They tend to be in approximate creation order. So, the disk access
pattern is nearly random access, meaning every stat is likely to touch a
new block and readahead is completely useless.



I once wrote a new hash for reiserfs3 specifically for maildir. This
hash caused files to be order in approximate creating order, matching
the inode order much closer. 


You will find both the patch and some benchmark results if you search
the archive (messageid 20010628030201.E380@vestdata.no), but speeded up
my testcase by a factor of 6. (My testcase read all the data too though.
I don't think I ever tested just "find . -ls")


In reiserfs3 the usefullness of the hash is limited as hashes are per
filesystem settings. (So it is only useful if you have a dedicated
maildir filesystem). I've lost track of reiserfs4 features - maybe you
can select hashes per directory now? Or maybe the whole thing is made
obsolete by putting the inodes with the directoryentries?




-- 
Ragnar Kjørstad
Software Engineer
Scali - http://www.scali.com
Scaling the Linux Datacenter

Re: Fastest way to "find / -mtime +7".....

[Jonathan Briggs]

[-- Attachment #1: Type: text/plain, Size: 1296 bytes --]

On Tue, 2005-07-19 at 22:09 +0200, Ragnar Kjørstad wrote:
> On Tue, Jul 19, 2005 at 12:48:53PM -0600, Jonathan Briggs wrote:
> > > this is pretty slow on reiser, at least compared with ext2/3, and I  
> > > understand that it may be because the find command returns the names  
> > > in a non-optimal order (ie readdir order?).
> > 
> > I think Reiser3 is slow more because with mtime, find has to stat each
> > file. 
> 
> The two issues are related.
> 
> Readdir will return the filenames in hash order. Find will then go and
> stat each file, still in hash order.
> 
> Problem is, the inodes are not sorted in directory hash order on the
> disk. They tend to be in approximate creation order. So, the disk access
> pattern is nearly random access, meaning every stat is likely to touch a
> new block and readahead is completely useless.
[snip]
How about some kind of stat-data readahead logic?  If the first two or
three directory entries are stat'd, queue up the rest (or next
hundred/thousand) of them.  If the disk queue is given the whole pile of
stat requests at once instead of one at a time, it should be able to
sort them into a reasonable order.

This might even be a VFS thing to do instead of per-FS.
-- 
Jonathan Briggs <jbriggs@esoft.com>
eSoft, Inc.

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Fastest way to "find / -mtime +7".....

[Alexander G. M. Smith]

Jonathan Briggs wrote on Tue, 19 Jul 2005 16:00:23 -0600:
> On Tue, 2005-07-19 at 22:09 +0200, Ragnar Kjørstad wrote:
> > Readdir will return the filenames in hash order. Find will then go and
> > stat each file, still in hash order.
> > 
> > Problem is, the inodes are not sorted in directory hash order on the
> > disk. They tend to be in approximate creation order. So, the disk access
> > pattern is nearly random access, meaning every stat is likely to touch a
> > new block and readahead is completely useless.
> [snip]
> How about some kind of stat-data readahead logic?  If the first two or
> three directory entries are stat'd, queue up the rest (or next
> hundred/thousand) of them.  If the disk queue is given the whole pile of
> stat requests at once instead of one at a time, it should be able to
> sort them into a reasonable order.
> 
> This might even be a VFS thing to do instead of per-FS.

I noticed the same limitation for reading large numbers of attributes in BeOS
(like icons for all the files in a directory or in the result set from a query).
My idea is to expand ReadDir to return more than just the file names in the
directory/query.  You would specify which metadata you wanted (mtime, filename,
attribute name, etc) and then SuperReadDir would traverse the directory/query
and pack all the requested data items into one memory buffer for the calling
program to use.  Thus avoiding the overhead of multiple kernel calls for each
individual file.  Suddenly displaying a file browser window with a directory
with thousands of files is many times faster!

But for full functionality this needs a global metadata naming and typing
system, so you can find out what data types are available, and how to process
them.  It would describe mtime as being a 4 byte integer time, SMALL_ICON as
being a bitmap, FILE_NAME as being a variable length string and so on.  This
can be related to the file type system (like the nice one Apple now has in
OS X Tiger), so that file types and metadata types can be described by a
common API.  Unfortunately BeOS has them as separate systems (a list of four
character codes for the metadata types, MIME strings for the files).  Then
there's the issue of cross platform type sharing, an enum with different values
here and there for the metadata type codes will make it hard to share data
discs, so something more sophisticated is needed...

- Alex

Re: Fastest way to "find / -mtime +7".....

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 738 bytes --]

On Jul 19, 2005  16:00 -0600, Jonathan Briggs wrote:
> How about some kind of stat-data readahead logic?  If the first two or
> three directory entries are stat'd, queue up the rest (or next
> hundred/thousand) of them.  If the disk queue is given the whole pile of
> stat requests at once instead of one at a time, it should be able to
> sort them into a reasonable order.
> 
> This might even be a VFS thing to do instead of per-FS.

This is something I would be very interested in.  Having a pipeline of
stats generated when an app does readdir + in-order stat would help
reduce latency a great deal for network filesystems.

Cheers, Andreas
--
Andreas Dilger
Principal Software Engineer
Cluster File Systems, Inc.


[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: Fastest way to "find / -mtime +7".....

[Ragnar Kjørstad]

On Wed, Jul 20, 2005 at 12:26:44PM -0400, Andreas Dilger wrote:
> On Jul 19, 2005  16:00 -0600, Jonathan Briggs wrote:
> > How about some kind of stat-data readahead logic?  If the first two or
> > three directory entries are stat'd, queue up the rest (or next
> > hundred/thousand) of them.  If the disk queue is given the whole pile of
> > stat requests at once instead of one at a time, it should be able to
> > sort them into a reasonable order.
> > 
> > This might even be a VFS thing to do instead of per-FS.
> 
> This is something I would be very interested in.  Having a pipeline of
> stats generated when an app does readdir + in-order stat would help
> reduce latency a great deal for network filesystems.

What about just adding an asyncron stat to aio ?



-- 
Ragnar Kjørstad
Software Engineer
Scali - http://www.scali.com
Scaling the Linux Datacenter