Calling stat with millions of files

Calling stat with millions of files

[Ross Skaliotis]

We have a backup system (backupPC) that is responsible for backing up
millions of files and holding over 2 TB of data. The backup system saves
space by creating hard links where it can. This actually reduces the total
size down to 200 GB, however there are still millions of files/hard links.

What does this have to do with reiserfs? Well, the partition runs reiserfs
3.6. Over the course of a few months (and the addition of millions more
files/hard links) the performance of the filesystem has become painfully
slow.

In a directory of ~1000 files, running 'ls -l' or 'stat *' takes 45
seconds to complete (assuming nothing is previously cached). We are using
the r5 hash, and mount the filesystem with noatime. No one directory has
(or will ever have) more than about 2000 files and hard links inside.

Is this performance decrease when calling stat to be expected with
increasing millions of files/hard links? Would XFS or another filesystem
get around this somehow? I'd rather not use reiserfs4, as this is a
production backup server and needs to be as stable as possible.

Thanks very much for your help,

-Ross Skaliotis

Re: Calling stat with millions of files

[Vladimir Saveliev]

Hello

On Tue, 2004-06-08 at 01:54, Ross Skaliotis wrote:
> We have a backup system (backupPC) that is responsible for backing up
> millions of files and holding over 2 TB of data. The backup system saves
> space by creating hard links where it can. This actually reduces the total
> size down to 200 GB, however there are still millions of files/hard links.
> 
> What does this have to do with reiserfs? Well, the partition runs reiserfs
> 3.6. Over the course of a few months (and the addition of millions more
> files/hard links) the performance of the filesystem has become painfully
> slow.
> 
> In a directory of ~1000 files, running 'ls -l' or 'stat *' takes 45
> seconds to complete (assuming nothing is previously cached). We are using
> the r5 hash, and mount the filesystem with noatime. No one directory has
> (or will ever have) more than about 2000 files and hard links inside.

The problem is probably that reiserfs allocates on-disk inodes (reiserfs
calls it stat data) dynamically, so they get spread all over whole
filesystem. 

> Is this performance decrease when calling stat to be expected with
> increasing millions of files/hard links? Would XFS or another filesystem
> get around this somehow? 

I guess that filesystem which stores on-disk inodes groupped together
would perform better for this kind of workload.

> I'd rather not use reiserfs4, as this is a
> production backup server and needs to be as stable as possible.
> 
> Thanks very much for your help,
> 
> -Ross Skaliotis
> 

Re: Calling stat with millions of files

[Heinz-Josef Claes]

> On Tue, 2004-06-08 at 01:54, Ross Skaliotis wrote:
> > We have a backup system (backupPC) that is responsible for backing up
> > millions of files and holding over 2 TB of data. The backup system saves
> > space by creating hard links where it can. This actually reduces the total
> > size down to 200 GB, however there are still millions of files/hard links.
> > 
> > What does this have to do with reiserfs? Well, the partition runs reiserfs
> > 3.6. Over the course of a few months (and the addition of millions more
> > files/hard links) the performance of the filesystem has become painfully
> > slow.
> > 
> > In a directory of ~1000 files, running 'ls -l' or 'stat *' takes 45
> > seconds to complete (assuming nothing is previously cached). We are using
> > the r5 hash, and mount the filesystem with noatime. No one directory has
> > (or will ever have) more than about 2000 files and hard links inside.
> 

Do you have these problems only if you have a lot of files in a
directory or also with smaller directories. I'm using storebackup (which
also uses hard links) for a backup and never had these problems - even
on a slow machine. (I'm using reiserfs 3.6 _with_ tail packing and r5
hash.)

Do you also have these problems when performing a backup?

> > Is this performance decrease when calling stat to be expected with
> > increasing millions of files/hard links? Would XFS or another filesystem
> > get around this somehow? 
> 
> I guess that filesystem which stores on-disk inodes groupped together
> would perform better for this kind of workload.
> 
> > I'd rather not use reiserfs4, as this is a
> > production backup server and needs to be as stable as possible.
> > 
> > Thanks very much for your help,
> > 
> > -Ross Skaliotis
> > 
-- 
Heinz-Josef Claes                     hjclaes@web.de
project: http://sourceforge.net/projects/storebackup
      -> snapshot-like backup to another disk

Re: Calling stat with millions of files

[Hans Reiser]

Ross Skaliotis wrote:

>We have a backup system (backupPC) that is responsible for backing up
>millions of files and holding over 2 TB of data. The backup system saves
>space by creating hard links where it can. This actually reduces the total
>size down to 200 GB, however there are still millions of files/hard links.
>
>What does this have to do with reiserfs? Well, the partition runs reiserfs
>3.6. Over the course of a few months (and the addition of millions more
>files/hard links) the performance of the filesystem has become painfully
>slow.
>
>In a directory of ~1000 files, running 'ls -l' or 'stat *' takes 45
>seconds to complete (assuming nothing is previously cached). We are using
>the r5 hash, and mount the filesystem with noatime. No one directory has
>(or will ever have) more than about 2000 files and hard links inside.
>
>Is this performance decrease when calling stat to be expected with
>increasing millions of files/hard links? Would XFS or another filesystem
>get around this somehow? I'd rather not use reiserfs4, as this is a
>production backup server and needs to be as stable as possible.
>
>Thanks very much for your help,
>
>-Ross Skaliotis
>
>
>  
>
hardlinks destroy locality of reference for stat data, this is probably 
your problem.

Probably the readahead for the directory is broken by hard links also.

Likely could be optimized but nobody else is complaining about it so I 
can't really afford to do it just for you, sorry.

Re: Calling stat with millions of files

[Chris Mason]

On Tue, 2004-06-08 at 12:28, Hans Reiser wrote:
> Ross Skaliotis wrote:
> 
> >We have a backup system (backupPC) that is responsible for backing up
> >millions of files and holding over 2 TB of data. The backup system saves
> >space by creating hard links where it can. This actually reduces the total
> >size down to 200 GB, however there are still millions of files/hard links.
> >
> >What does this have to do with reiserfs? Well, the partition runs reiserfs
> >3.6. Over the course of a few months (and the addition of millions more
> >files/hard links) the performance of the filesystem has become painfully
> >slow.
> >
> >In a directory of ~1000 files, running 'ls -l' or 'stat *' takes 45
> >seconds to complete (assuming nothing is previously cached). We are using
> >the r5 hash, and mount the filesystem with noatime. No one directory has
> >(or will ever have) more than about 2000 files and hard links inside.
> >
Mount with -o nodiratime as well.

> >Is this performance decrease when calling stat to be expected with
> >increasing millions of files/hard links? Would XFS or another filesystem
> >get around this somehow? I'd rather not use reiserfs4, as this is a
> >production backup server and needs to be as stable as possible.
> >
> >Thanks very much for your help,
> >
> hardlinks destroy locality of reference for stat data, this is probably 
> your problem.
> 
> Probably the readahead for the directory is broken by hard links also.
> 
> Likely could be optimized but nobody else is complaining about it so I 
> can't really afford to do it just for you, sorry.
> 
> 

You'll get better results with the new block allocator in 2.6.7-rcX-mm,
but in the end the stat information for the file isn't horribly close to
the directory entries, and performance won't be perfect.

Hans, I thought reiser4 was going to be good at this kind of thing?

-chris

Re: Calling stat with millions of files

[Hans Reiser]

Chris Mason wrote:

>On Tue, 2004-06-08 at 12:28, Hans Reiser wrote:
>  
>
>>Ross Skaliotis wrote:
>>
>>    
>>
>>>We have a backup system (backupPC) that is responsible for backing up
>>>millions of files and holding over 2 TB of data. The backup system saves
>>>space by creating hard links where it can. This actually reduces the total
>>>size down to 200 GB, however there are still millions of files/hard links.
>>>
>>>What does this have to do with reiserfs? Well, the partition runs reiserfs
>>>3.6. Over the course of a few months (and the addition of millions more
>>>files/hard links) the performance of the filesystem has become painfully
>>>slow.
>>>
>>>In a directory of ~1000 files, running 'ls -l' or 'stat *' takes 45
>>>seconds to complete (assuming nothing is previously cached). We are using
>>>the r5 hash, and mount the filesystem with noatime. No one directory has
>>>(or will ever have) more than about 2000 files and hard links inside.
>>>
>>>      
>>>
>Mount with -o nodiratime as well.
>
>  
>
>>>Is this performance decrease when calling stat to be expected with
>>>increasing millions of files/hard links? Would XFS or another filesystem
>>>get around this somehow? I'd rather not use reiserfs4, as this is a
>>>production backup server and needs to be as stable as possible.
>>>
>>>Thanks very much for your help,
>>>
>>>      
>>>
>>hardlinks destroy locality of reference for stat data, this is probably 
>>your problem.
>>
>>Probably the readahead for the directory is broken by hard links also.
>>
>>Likely could be optimized but nobody else is complaining about it so I 
>>can't really afford to do it just for you, sorry.
>>
>>
>>    
>>
>
>You'll get better results with the new block allocator in 2.6.7-rcX-mm,
>but in the end the stat information for the file isn't horribly close to
>the directory entries, and performance won't be perfect.
>
>Hans, I thought reiser4 was going to be good at this kind of thing?
>
>-chris
>
>
>
>
>  
>
what in reiser4 optimizes accesses to hard links to files whose stat 
data is stored in other directories?  Maybe the stat data being stored 
near other stat data instead of near file bodies will help,.  Hmmm.  
Could be, have to try it to see.

Re: Calling stat with millions of files

[Chris Mason]

On Tue, 2004-06-08 at 12:47, Hans Reiser wrote:
> really afford to do it just for you, sorry.
> >
> >You'll get better results with the new block allocator in 2.6.7-rcX-mm,
> >but in the end the stat information for the file isn't horribly close to
> >the directory entries, and performance won't be perfect.
> >
> >Hans, I thought reiser4 was going to be good at this kind of thing?
> >
> >
> what in reiser4 optimizes accesses to hard links to files whose stat 
> data is stored in other directories?  Maybe the stat data being stored 
> near other stat data instead of near file bodies will help,.  Hmmm.  
> Could be, have to try it to see.

He said above that it creates hard links "when it can", not sure what
percentage of the time this actually happens.

-chris

Re: Calling stat with millions of files

[Hans Reiser]

Chris Mason wrote:

>On Tue, 2004-06-08 at 12:47, Hans Reiser wrote:
>  
>
>>really afford to do it just for you, sorry.
>>    
>>
>>>You'll get better results with the new block allocator in 2.6.7-rcX-mm,
>>>but in the end the stat information for the file isn't horribly close to
>>>the directory entries, and performance won't be perfect.
>>>
>>>Hans, I thought reiser4 was going to be good at this kind of thing?
>>>
>>>
>>>      
>>>
>>what in reiser4 optimizes accesses to hard links to files whose stat 
>>data is stored in other directories?  Maybe the stat data being stored 
>>near other stat data instead of near file bodies will help,.  Hmmm.  
>>Could be, have to try it to see.
>>    
>>
>
>He said above that it creates hard links "when it can", not sure what
>percentage of the time this actually happens.
>
>-chris
>
>
>
>
>  
>
Probably reiser4 will indeed do much better at this.  Wish I had more 
guys working on the debugging.....;-)

Re: Calling stat with millions of files

[Ross Skaliotis]

> On Tue, 2004-06-08 at 12:47, Hans Reiser wrote:
> > really afford to do it just for you, sorry.
> > >
> > >You'll get better results with the new block allocator in 2.6.7-rcX-mm,
> > >but in the end the stat information for the file isn't horribly close to
> > >the directory entries, and performance won't be perfect.
> > >
> > >Hans, I thought reiser4 was going to be good at this kind of thing?
> > >
> > >
> > what in reiser4 optimizes accesses to hard links to files whose stat
> > data is stored in other directories?  Maybe the stat data being stored
> > near other stat data instead of near file bodies will help,.  Hmmm.
> > Could be, have to try it to see.
>
> He said above that it creates hard links "when it can", not sure what
> percentage of the time this actually happens.

Most files have several hard links. Common files shared between many
backed up computers (windows system files, etc.) can have up to 500 hard
links.

>hardlinks destroy locality of reference for stat data, this is probably
>your problem.

So this would be a problem with any filesystem, right? I don't understand
filesystems nearly as well as others on this list, but am I correct in
assuming the stat data would stay "near" the original file? If I can make
my backup system only need to stat original files (which may have hard
links linked to _them_) would my performance issues go away?

Thanks and sorry for my ignorance,

-Ross

Re: Calling stat with millions of files

[Mike Benoit]

I'm currently using the "Rsync Snapshot" 

http://www.mikerubel.org/computers/rsync_snapshots/

backup method with a 340Gb RAID5 array on a PIII-800 with 256mb RAM.
Currently used is about 200gb in 68 million files. I would guess over
75% are hard links.

My mount options are: notail,noatime,nodiratime
Kernel: 2.6.3-7mdk

The Performance I'm seeing is pretty good, I don't have any complaints. 

My directory structure looks like this:

backup/ <-- main directory, no hard links at all
backup_May_22_2004-12_11_23/ 
backup_May_22_2004-19_09_15/
backup_May_23_2004-12_06_29/
backup_May_23_2004-19_07_10/
backup_May_24_2004-12_06_11/
backup_May_24_2004-19_07_05/
backup_May_25_2004-12_14_06/
backup_May_25_2004-19_17_25/
...

Now I'll pick the main directory (backup) the oldest directory, and the
newest directory to do "ls -lR" tests on:

[backup/]# time ls -lR | wc
13.41user 11.89system 1:12.13elapsed 35%CPU (0avgtext+0avgdata
0maxresident)k
0inputs+0outputs (0major+4316minor)pagefaults 0swaps
 384035 3170729 22214505

[backup_February_01_2004-19_06_01/]# time ls -lR | wc
9.33user 8.98system 0:39.44elapsed 46%CPU (0avgtext+0avgdata
0maxresident)k
0inputs+0outputs (0major+2855minor)pagefaults 0swaps
 278517 2271694 15731940

[backup_June_07_2004-12_19_57/]# time ls -lR | wc
13.57user 12.14system 1:15.01elapsed 34%CPU (0avgtext+0avgdata
0maxresident)k
0inputs+0outputs (0major+4317minor)pagefaults 0swaps
 383918 3169608 22207182

~60 seconds to "ls -lR" over 300,000 files seems pretty decent. Much
better then 45 seconds to do 1000 files that for sure.

Hope this helps to at least give you another data point. 


On Mon, 2004-06-07 at 17:54 -0400, Ross Skaliotis wrote:
> We have a backup system (backupPC) that is responsible for backing up
> millions of files and holding over 2 TB of data. The backup system saves
> space by creating hard links where it can. This actually reduces the total
> size down to 200 GB, however there are still millions of files/hard links.
> 
> What does this have to do with reiserfs? Well, the partition runs reiserfs
> 3.6. Over the course of a few months (and the addition of millions more
> files/hard links) the performance of the filesystem has become painfully
> slow.
> 
> In a directory of ~1000 files, running 'ls -l' or 'stat *' takes 45
> seconds to complete (assuming nothing is previously cached). We are using
> the r5 hash, and mount the filesystem with noatime. No one directory has
> (or will ever have) more than about 2000 files and hard links inside.
> 
> Is this performance decrease when calling stat to be expected with
> increasing millions of files/hard links? Would XFS or another filesystem
> get around this somehow? I'd rather not use reiserfs4, as this is a
> production backup server and needs to be as stable as possible.
> 
> Thanks very much for your help,
> 
> -Ross Skaliotis
-- 
Mike Benoit <ipso@snappymail.ca>

Re: Calling stat with millions of files

[Henning Westerholt]

Am Dienstag, 8. Juni 2004 20:58 schrieb Mike Benoit:
> I'm currently using the "Rsync Snapshot"
>
> http://www.mikerubel.org/computers/rsync_snapshots/
>
> backup method with a 340Gb RAID5 array on a PIII-800 with 256mb RAM.
> Currently used is about 200gb in 68 million files. I would guess over
> 75% are hard links.
>
> My mount options are: notail,noatime,nodiratime
> Kernel: 2.6.3-7mdk
>
> The Performance I'm seeing is pretty good, I don't have any complaints.

I'm using the same backup method like Mike. The machine is a 2.5 GHz P4 with 
Suse kernel 2.4.20, and a Raid5 array filled with ~100 GB data. 

A "ls -lR" on the oldest snapshot (150000 files) needs 2m40s, probably because 
i use no special mount options, and the data in this directory is from four 
different machines. 
But otherwise i'm satisfied with the performance of reiserfs. So i think there 
must been a other problem with your system.

Best regards,

Henning

Re: Calling stat with millions of files

[Carl-Daniel Hailfinger]

Chris Mason wrote:
> On Tue, 2004-06-08 at 12:47, Hans Reiser wrote:
> 
>>really afford to do it just for you, sorry.
>>
>>>You'll get better results with the new block allocator in 2.6.7-rcX-mm,
>>>but in the end the stat information for the file isn't horribly close to
>>>the directory entries, and performance won't be perfect.
>>>
>>>Hans, I thought reiser4 was going to be good at this kind of thing?
>>>
>>>
>>
>>what in reiser4 optimizes accesses to hard links to files whose stat 
>>data is stored in other directories?  Maybe the stat data being stored 
>>near other stat data instead of near file bodies will help,.  Hmmm.  
>>Could be, have to try it to see.
> 
> 
> He said above that it creates hard links "when it can", not sure what
> percentage of the time this actually happens.

A good test for this would be

bk clone bk://linux.bkbits.net/linux-2.6
bk lclone linux-2.6 linux-test
# wait a few days for the repo to get out of sync
cd linux-2.6
bk pull

This should give you two trees which are only partially hardlinked and the
scenario should be halfway common for kernel developers.

Regards,
Carl-Daniel
-- 
http://www.hailfinger.org/

Re: Calling stat with millions of files

[Hans Reiser]

Ross Skaliotis wrote:

>>On Tue, 2004-06-08 at 12:47, Hans Reiser wrote:
>>    
>>
>>>really afford to do it just for you, sorry.
>>>      
>>>
>>>>You'll get better results with the new block allocator in 2.6.7-rcX-mm,
>>>>but in the end the stat information for the file isn't horribly close to
>>>>the directory entries, and performance won't be perfect.
>>>>
>>>>Hans, I thought reiser4 was going to be good at this kind of thing?
>>>>
>>>>
>>>>        
>>>>
>>>what in reiser4 optimizes accesses to hard links to files whose stat
>>>data is stored in other directories?  Maybe the stat data being stored
>>>near other stat data instead of near file bodies will help,.  Hmmm.
>>>Could be, have to try it to see.
>>>      
>>>
>>He said above that it creates hard links "when it can", not sure what
>>percentage of the time this actually happens.
>>    
>>
>
>Most files have several hard links. Common files shared between many
>backed up computers (windows system files, etc.) can have up to 500 hard
>links.
>
>  
>
>>hardlinks destroy locality of reference for stat data, this is probably
>>your problem.
>>    
>>
>
>So this would be a problem with any filesystem, right? I don't understand
>filesystems nearly as well as others on this list, but am I correct in
>assuming the stat data would stay "near" the original file? If I can make
>my backup system only need to stat original files (which may have hard
>links linked to _them_) would my performance issues go away?
>  
>
In reiser4 it would probably cure it, probably not in reiser3, though it 
might help, and I could be wrong....

>Thanks and sorry for my ignorance,
>
>-Ross
>
>
>  
>