Agressive selective pre-allocation

Agressive selective pre-allocation

[Ragnar Kjørstad]

Hi


A lot of filesystems have files that grow slowly over time, and this is
causing serious fragmentation, and thus performance-problems in some
situations.

A defragmentation-utility could potentially solve this, but maybe there
is a better way?

Some files, for instance MBOX-type mailboxes and logfiles, are known to
the user/administrator to grow over time. It is possible to preallocate
diskspace by creating large files with just zeroes in them, but this is
not very flexible and requires the application to be awere.

An alternative would be the possibility to tell the fs about the
properties of the files. Maybe an ioctl to notify the fs that for this
particular file the fs should allocate X blocks at the time? That would
ensure that the files only get limited fragmentation and performance
stays optimal.

Does the metadata-format support blocks beeing allocated but not used
yet? Is it sufficient to add them to the extent-map, mark them free,
without changing the size of the file?

An even better way would be to mark the blocks as "preallocated" without
assigning them to the file. This would allow preallocation without
actually locking the blocks - so if the disk went full the allocator
could override the preallocation and use them for other data. 

Blocks are managed in extents in reiserfs4, right? So I assume there is
an extent-list for free blocks? So maybe one could add an extra
extent-list for "preallocated blocks", and the change the allocator to
search that list if, and only if, it is appending to file on the
previous block or if there are no blocks in the free-list?


I have no time to try to implement this right now, but I just got the
idea and figgured I should write it down while fresh in memory. Any
reason why this wouldn't work? 

Personally I think fragmentation is one of the most serious
performance-problems for filesystems, and this could potentially help a
lot at least for the slow-growing files like logfiles and mboxes.



-- 
Ragnar Kjørstad

Re: Agressive selective pre-allocation

[Russell Coker]

On Tue, 10 Dec 2002 07:46, Ragnar Kjørstad wrote:
> A lot of filesystems have files that grow slowly over time, and this is
> causing serious fragmentation, and thus performance-problems in some
> situations.

Yes.  Or even files that grow rapidly.  Consider the case of an application 
which creates 10 files and starts appending data to each of them in turn in 
chunks of a few K (slapd does this).  Your file system will be 100% 
fragmented if you don't do something smart about allocation.

> Some files, for instance MBOX-type mailboxes and logfiles, are known to
> the user/administrator to grow over time. It is possible to preallocate
> diskspace by creating large files with just zeroes in them, but this is
> not very flexible and requires the application to be awere.

Most applications will either have an error condition if the file is longer 
than they expect, treat it as all data (and leave a hole in the file), or 
truncate it to the length that they want.

> An alternative would be the possibility to tell the fs about the
> properties of the files. Maybe an ioctl to notify the fs that for this
> particular file the fs should allocate X blocks at the time? That would
> ensure that the files only get limited fragmentation and performance
> stays optimal.

Another possibility is that you have a file system created for a specific data 
type.  When I create a file system for an LDAP directory I know ahead of time 
that I will have a small number of large files that are all growing slowly.  
An option to the mkfs and tunefs programs to set this would do for me (and 
it's easy to implement and get included in the kernel).  If I could set my 
LDAP partitions to have disk space allocation in chunks of 4M then I'd be 
happy.

> Does the metadata-format support blocks beeing allocated but not used
> yet? Is it sufficient to add them to the extent-map, mark them free,
> without changing the size of the file?

You shouldn't need anything in the meta-data if you just do it in allocation 
algorithms, every time you are about to grow a file and you can't grow it 
contiguously then you search for a large free region.

> Personally I think fragmentation is one of the most serious
> performance-problems for filesystems, and this could potentially help a
> lot at least for the slow-growing files like logfiles and mboxes.

mbox's aren't an issue, if you have them then you probably don't care too much 
about performance anyway.

-- 
http://www.coker.com.au/selinux/   My NSA Security Enhanced Linux packages
http://www.coker.com.au/bonnie++/  Bonnie++ hard drive benchmark
http://www.coker.com.au/postal/    Postal SMTP/POP benchmark
http://www.coker.com.au/~russell/  My home page

Re: Agressive selective pre-allocation

[Ragnar Kjørstad]

On Tue, Dec 10, 2002 at 08:26:36AM +0100, Russell Coker wrote:
> Yes.  Or even files that grow rapidly.  Consider the case of an application 
> which creates 10 files and starts appending data to each of them in turn in 
> chunks of a few K (slapd does this).  Your file system will be 100% 
> fragmented if you don't do something smart about allocation.

allocate on flush should handle this pretty well, don't you think?
Unless the writes are syncrounous.

But yes, the same principle applies. Files that grow over time (large
number of independent writes) is probably more accurate than slow-growing 
files.

> > An alternative would be the possibility to tell the fs about the
> > properties of the files. Maybe an ioctl to notify the fs that for this
> > particular file the fs should allocate X blocks at the time? That would
> > ensure that the files only get limited fragmentation and performance
> > stays optimal.
> 
> Another possibility is that you have a file system created for a specific data 
> type.  When I create a file system for an LDAP directory I know ahead of time 
> that I will have a small number of large files that are all growing slowly.  
> An option to the mkfs and tunefs programs to set this would do for me (and 
> it's easy to implement and get included in the kernel).  If I could set my 
> LDAP partitions to have disk space allocation in chunks of 4M then I'd be 
> happy.

That would work very well on things like logs - and it's probably a lot easier
to do than pr-file allocation policy.

> > Does the metadata-format support blocks beeing allocated but not used
> > yet? Is it sufficient to add them to the extent-map, mark them free,
> > without changing the size of the file?
> 
> You shouldn't need anything in the meta-data if you just do it in allocation 
> algorithms, every time you are about to grow a file and you can't grow it 
> contiguously then you search for a large free region.

Hmm, so still only allocate 1 block, but do it at a location that has a larger
region available?

> > Personally I think fragmentation is one of the most serious
> > performance-problems for filesystems, and this could potentially help a
> > lot at least for the slow-growing files like logfiles and mboxes.
> 
> mbox's aren't an issue, if you have them then you probably don't care too much 
> about performance anyway.

I know some that do, because some old mail-clients don't support maildir.


-- 
Ragnar Kjørstad

Re: Agressive selective pre-allocation

[Stefan Fleiter]

Hi!

> mbox's aren't an issue, if you have them then you probably don't care too
> much about performance anyway.

I switched some large mailing lists with thousands of messages from mbox to
maildir with mutt. Changing mailboxes lasted maybe 2 or 3 times longer,
so I switched back to mbox *for speed*.

Greetings,
Stefan

Re: Agressive selective pre-allocation

[Hans Reiser]

Ragnar Kjørstad wrote:

>Hi
>
>
>A lot of filesystems have files that grow slowly over time, and this is
>causing serious fragmentation, and thus performance-problems in some
>situations.
>
>A defragmentation-utility could potentially solve this, but maybe there
>is a better way?
>
>Some files, for instance MBOX-type mailboxes and logfiles, are known to
>the user/administrator to grow over time. It is possible to preallocate
>diskspace by creating large files with just zeroes in them, but this is
>not very flexible and requires the application to be awere.
>
>An alternative would be the possibility to tell the fs about the
>properties of the files. Maybe an ioctl to notify the fs that for this
>particular file the fs should allocate X blocks at the time? That would
>ensure that the files only get limited fragmentation and performance
>stays optimal.
>
Veritas did this, and then their architect regretted that nobody 
actually used that code and advised me not to do it.  You may have an 
advantage with open source though in that you can modify the important 
user space programs to use it.

We have some block preallocation code in V3 for files that are kept open 
while being written to.  You can look at that code if you want.  You can 
also write a plugin for v4 that does what you want.

While I will not take someone off another task to work on this, I will 
be open to patches from others.

>
>Does the metadata-format support blocks beeing allocated but not used
>yet? Is it sufficient to add them to the extent-map, mark them free,
>without changing the size of the file?
>
>An even better way would be to mark the blocks as "preallocated" without
>assigning them to the file. This would allow preallocation without
>actually locking the blocks - so if the disk went full the allocator
>could override the preallocation and use them for other data. 
>
>Blocks are managed in extents in reiserfs4, right? So I assume there is
>an extent-list for free blocks? So maybe one could add an extra
>extent-list for "preallocated blocks", and the change the allocator to
>search that list if, and only if, it is appending to file on the
>previous block or if there are no blocks in the free-list?
>
>
>I have no time to try to implement this right now, but I just got the
>idea and figgured I should write it down while fresh in memory. Any
>reason why this wouldn't work? 
>
>Personally I think fragmentation is one of the most serious
>performance-problems for filesystems, and this could potentially help a
>lot at least for the slow-growing files like logfiles and mboxes.
>
>
>
>  
>

Re: Agressive selective pre-allocation

[Bruce A. Mallett]

It seems to me that it would be better to have the file system keep 
track of this itself.  If the following is known about each file:
   original creation date
   current file size
   number of times extended
 
then it might be possible to compute a growth policy.  For example when 
extending a small file, just move and extend it.  As the file and 
extention frequencies increase then create larger new extents.

But the problem really is that apps don't actually "grow"these files but 
instead rebuilds them.  Thus the file system sees a request to open a 
new file and not to extend an existing one.  This would make tracking 
the above parameters way beyond difficult.



Ragnar Kjørstad wrote:

>Hi
>
>
>A lot of filesystems have files that grow slowly over time, and this is
>causing serious fragmentation, and thus performance-problems in some
>situations.
>
>A defragmentation-utility could potentially solve this, but maybe there
>is a better way?
>
>Some files, for instance MBOX-type mailboxes and logfiles, are known to
>the user/administrator to grow over time. It is possible to preallocate
>diskspace by creating large files with just zeroes in them, but this is
>not very flexible and requires the application to be awere.
>
>An alternative would be the possibility to tell the fs about the
>properties of the files. Maybe an ioctl to notify the fs that for this
>particular file the fs should allocate X blocks at the time? That would
>ensure that the files only get limited fragmentation and performance
>stays optimal.
>
>Does the metadata-format support blocks beeing allocated but not used
>yet? Is it sufficient to add them to the extent-map, mark them free,
>without changing the size of the file?
>
>An even better way would be to mark the blocks as "preallocated" without
>assigning them to the file. This would allow preallocation without
>actually locking the blocks - so if the disk went full the allocator
>could override the preallocation and use them for other data. 
>
>Blocks are managed in extents in reiserfs4, right? So I assume there is
>an extent-list for free blocks? So maybe one could add an extra
>extent-list for "preallocated blocks", and the change the allocator to
>search that list if, and only if, it is appending to file on the
>previous block or if there are no blocks in the free-list?
>
>
>I have no time to try to implement this right now, but I just got the
>idea and figgured I should write it down while fresh in memory. Any
>reason why this wouldn't work? 
>
>Personally I think fragmentation is one of the most serious
>performance-problems for filesystems, and this could potentially help a
>lot at least for the slow-growing files like logfiles and mboxes.
>
>
>
>  
>

Re: Agressive selective pre-allocation

[Anders Widman]

> It seems to me that it would be better to have the file system keep 
> track of this itself.  If the following is known about each file:
>    original creation date
>    current file size
>    number of times extended
 
> then it might be possible to compute a growth policy.  For example when 
> extending a small file, just move and extend it.  As the file and 
> extention frequencies increase then create larger new extents.

> But the problem really is that apps don't actually "grow"these files but 
> instead rebuilds them.  Thus the file system sees a request to open a 
> new file and not to extend an existing one.  This would make tracking 
> the above parameters way beyond difficult.

Actually,  It is impossible to predict how an application will use the
filesystem.  The  very  best  and  easiest would be if the application
itself  allocated  enough  space  to  fit  the  entire file. Either by
telling  the  FS  that  the  final  size  of  the file, or by actually
creating a large empty file and internally keep a pointer where in the
it should write.

The  filesystem   writers   and  "followers"  could  try  to  persuade
application developers to do this. Maybe as Hans suggested, by using a 
plug-in system or something similar.

//Anders

Re: Agressive selective pre-allocation

[Ragnar Kjørstad]

On Tue, Dec 10, 2002 at 12:12:28PM +0100, Stefan Fleiter wrote:
> > mbox's aren't an issue, if you have them then you probably don't care too
> > much about performance anyway.
> 
> I switched some large mailing lists with thousands of messages from mbox to
> maildir with mutt. Changing mailboxes lasted maybe 2 or 3 times longer,
> so I switched back to mbox *for speed*.

Yes, maildir is not always faster.

First problem is disk-layout. The way it works with reiserfs3.6 and
default hashes the inodes and files are written in different orders and
the disk does a lot of unneeded seeks. A workaround is to use a hash
that automagicly orders inodes and files the same way. A better way is
probably to store the stat-data with the directory-data. I think that is
on the schedule, is it not?

It is also important that readdir-order matches the ondisk layout, but
that is perhaps already the case?

Possible the overhead of the systemcalls is also significant, but my
guess is that it is negletable compared to io-performance.

Next problem is readahead. When the whole mailbox is in a single file
the OS is able to use readahead to improve performance, but it doesn't
seem to work as well when reading a whole directory. This is perhaps the
thoughest one to solve, IMHO.


However, the single most important fix would be the mail-clients. If I'm
not mistaken mutt reads the whole mail, and that's simply not required.
It should only read the headers. That will speed things up by a huge
factor when you have mails with attachments and so on.  It must also learn 
that it shouldn't reread the folder everytime it's updated!

Right now the case is pretty much that none or few of the potential
performance-benefits of maildir are made use of, and the drawbacks are
hitting much harder then they ought to. I bet it's only temporary
though. Reiserfs has the potential to make faster mailsystems with
the use of maildir! :-)



-- 
Ragnar Kjørstad

Re: Agressive selective pre-allocation

[Hans Reiser]

Ragnar Kjørstad wrote:

>On Tue, Dec 10, 2002 at 12:12:28PM +0100, Stefan Fleiter wrote:
>  
>
>>>mbox's aren't an issue, if you have them then you probably don't care too
>>>much about performance anyway.
>>>      
>>>
>>I switched some large mailing lists with thousands of messages from mbox to
>>maildir with mutt. Changing mailboxes lasted maybe 2 or 3 times longer,
>>so I switched back to mbox *for speed*.
>>    
>>
>
>Yes, maildir is not always faster.
>
>First problem is disk-layout. The way it works with reiserfs3.6 and
>default hashes the inodes and files are written in different orders and
>the disk does a lot of unneeded seeks. 
>
You mean the names are written in an order different from the stat data 
and file bodies, and the stat data and file bodies have the same order.

This is because we sort filenames by filename, and  sort stat data and 
file bodies by objectid which tends to be ordered by creation time.

We should implement a plugin that sorts filenames by creation time, and 
that will cause our performance to resemble ext2 more (meaning that for 
large directories the performance will fall apart, but for small 
directories there might be some advantage from not sorting by name).  I 
think that sorting file bodies by filename would require a larger key, 
so I hesitate at that, but maybe it would be interesting to explore also.

>A workaround is to use a hash
>that automagicly orders inodes and files the same way. A better way is
>probably to store the stat-data with the directory-data. I think that is
>on the schedule, is it not?
>
No, not yet, it didn't make the 4.0 code freeze....  patches are 
welcomed....

>
>It is also important that readdir-order matches the ondisk layout, but
>that is perhaps already the case?
>
If you copy a directory, then after the copy the readdir order matches 
the ondisk layout.

>
>Possible the overhead of the systemcalls is also significant, but my
>guess is that it is negletable compared to io-performance.
>
>Next problem is readahead. When the whole mailbox is in a single file
>the OS is able to use readahead to improve performance, but it doesn't
>seem to work as well when reading a whole directory. This is perhaps the
>thoughest one to solve, IMHO.
>
It is not very hard to solve if we use packing locality readahead.

>
>
>However, the single most important fix would be the mail-clients. If I'm
>not mistaken mutt reads the whole mail, and that's simply not required.
>It should only read the headers. That will speed things up by a huge
>factor when you have mails with attachments and so on.  It must also learn 
>that it shouldn't reread the folder everytime it's updated!
>
>Right now the case is pretty much that none or few of the potential
>performance-benefits of maildir are made use of, and the drawbacks are
>hitting much harder then they ought to. I bet it's only temporary
>though. Reiserfs has the potential to make faster mailsystems with
>the use of maildir! :-)
>
>
>
>  
>

Re: Agressive selective pre-allocation

[Ragnar Kjørstad]

On Thu, Dec 12, 2002 at 05:46:08PM +0300, Hans Reiser wrote:
> >Yes, maildir is not always faster.
> >
> >First problem is disk-layout. The way it works with reiserfs3.6 and
> >default hashes the inodes and files are written in different orders and
> >the disk does a lot of unneeded seeks. 
> >
> You mean the names are written in an order different from the stat data 
> and file bodies, and the stat data and file bodies have the same order.
> 
> This is because we sort filenames by filename, and  sort stat data and 
> file bodies by objectid which tends to be ordered by creation time.

Exactly.

> We should implement a plugin that sorts filenames by creation time, and 
> that will cause our performance to resemble ext2 more (meaning that for 
> large directories the performance will fall apart, but for small 
> directories there might be some advantage from not sorting by name). 

Yes, or you could do as I did in my maildir-specific hash - make a hash
that tends to resemble creation-order. For maildir this can be done
pretty easily as filenames can be predicted and actually contain
information about creation-order.

> I 
> think that sorting file bodies by filename would require a larger key, 
> so I hesitate at that, but maybe it would be interesting to explore also.

That would be _really_ interesting, but I don't understand exactly what
would be needed. 

Am I right to assume that there are actually several seperate entities
that are related to the allocation/ordering:
- the reiserfs-key idenitfying the inode
- tree-nodes that hold the allocation-information about the file
  (I guess extent-lists in reiserfs4)
- the blocks actually allocated for the data.

So both the choice of the inode-key and the allocation-policy for new
tree-nodes and data-blocks could affect file-ordering? Since the key is
generated from the hash that should already be in directory-entry-order,
but what about the other two?

Frankly last time I checked I found the way that directories and
allocation work not too well documented. Perhaps I just didn't look the
right places... Or maybe I must just be prepared to take the time to
read the source properly to understand this.


> >It is also important that readdir-order matches the ondisk layout, but
> >that is perhaps already the case?
> >
> If you copy a directory, then after the copy the readdir order matches 
> the ondisk layout.

Yes, that's what I do now when my maildirs get too slow. It makes a
huge difference.


-- 
Ragnar Kjørstad

Re: Agressive selective pre-allocation

[Ragnar Kjørstad]

On Tue, Dec 10, 2002 at 05:13:13PM +0300, Hans Reiser wrote:
> >An alternative would be the possibility to tell the fs about the
> >properties of the files. Maybe an ioctl to notify the fs that for this
> >particular file the fs should allocate X blocks at the time? That would
> >ensure that the files only get limited fragmentation and performance
> >stays optimal.
>
> Veritas did this, and then their architect regretted that nobody 
> actually used that code and advised me not to do it.  You may have an 
> advantage with open source though in that you can modify the important 
> user space programs to use it.

I was more thinking along the lines of:
find /var/log -type f | xargs ioctl REISERFS_SLOW_GROWING

But I guess syslog or whatever is used would have to be modified
for it to happen automaticly on new files. My guess is that
syslog-maintainers would not take patches for features like this unless
it was done in a more generic way that could potentially be used by
other filesystems as well. 


> We have some block preallocation code in V3 for files that are kept open 
> while being written to.  You can look at that code if you want.  You can 
> also write a plugin for v4 that does what you want.

Are you talking about the allocate on flush code? I'll check that out;
allthough at this point it is of course more interesting to write code
for reiserfs4 than v3 - in particular if the new improved infrastructure
makes it easier.

> While I will not take someone off another task to work on this, I will 
> be open to patches from others.

As I wrote in my original mail I don't have time to really work on this
now, but maybe later.



-- 
Ragnar Kjørstad

Re: Agressive selective pre-allocation

[Ragnar Kjørstad]

On Tue, Dec 10, 2002 at 11:43:02AM -0500, Bruce A. Mallett wrote:
> But the problem really is that apps don't actually "grow"these files but 
> instead rebuilds them.  Thus the file system sees a request to open a 
> new file and not to extend an existing one.  This would make tracking 
> the above parameters way beyond difficult.

That's definitively not true for logfiles. Neither do I think it's true
for mail deliviery. It may very well be true for some mail-clients when
the user deletes old emails, but if that is the case then the whole file
will be written at once and the original problem does not exist.



-- 
Ragnar Kjørstad