Benchmark : ext3 vs reiser4 and effects of fragmentation.

Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Will Smith]

I've spent the last 2 days coding and running benchmarks
on the effects of fragmentation on both ext3 and
reiser4 performance.

Explanation and source code is at
http://www.willsmith.org/opensource/reiser4/fragperf/

Results and graphs are at
http://www.willsmith.org/opensource/reiser4/fragperf/test1/


Dataset is a kernel source (~200Mb) in a small 350Mb
partition, with random deletes, copies and overwrites
to cause fragmentation.

In conclusion:

1) reiser4 is slightly faster than ext3 in some cases, but
    much faster in others (no surprise).  However,
    deletes are slightly slower.

2) ext3 degrades badly from fragmentation when running
    ordered (non-random) access patterns.  reiser4
    also degrades but not as much.

3) the repacker can bring performance of reiser4 back
    to full speed, but only if run several times.

4) the repacker is not yet stable - I had to run fsck
    a few times after repacking, and once got a kernel
    stack trace during repacking resulting in an
    un-unmountable filesystem.


I'll gladly rerun with different parameters and/or change
the script if requested.


Will Smith

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Alex Zarochentsev]

On Thu, Sep 16, 2004 at 06:02:54AM +0800, Will Smith wrote:
> I've spent the last 2 days coding and running benchmarks
> on the effects of fragmentation on both ext3 and
> reiser4 performance.
> 
> Explanation and source code is at
> http://www.willsmith.org/opensource/reiser4/fragperf/
> 
> Results and graphs are at
> http://www.willsmith.org/opensource/reiser4/fragperf/test1/
> 
> Dataset is a kernel source (~200Mb) in a small 350Mb
> partition, with random deletes, copies and overwrites
> to cause fragmentation.
> 
> In conclusion:
> 
> 1) reiser4 is slightly faster than ext3 in some cases, but
>    much faster in others (no surprise).  However,
>    deletes are slightly slower.
> 
> 2) ext3 degrades badly from fragmentation when running
>    ordered (non-random) access patterns.  reiser4
>    also degrades but not as much.
> 
> 3) the repacker can bring performance of reiser4 back
>    to full speed, but only if run several times.

yes, we had similar results.  it is so cool that reiser4 repacker effect
is visible outside namesys :)

> 
> 4) the repacker is not yet stable - I had to run fsck
>    a few times after repacking, and once got a kernel
>    stack trace during repacking resulting in an
>    un-unmountable filesystem.

unmergable units shouldn't be problem for the reiser4 kernel code.

but what was the stack trace?  Was there "nikita-3532: Sibling nodes on the
different levels" message?

> I'll gladly rerun with different parameters and/or change
> the script if requested.
> 
> Will Smith

Thanks

-- 
Alex.

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[mjt]

On Thu, Sep 16, 2004 at 12:52:49PM +0400, Alex Zarochentsev wrote:

>> 3) the repacker can bring performance of reiser4 back
>>    to full speed, but only if run several times.
>yes, we had similar results.  it is so cool that reiser4 repacker effect
>is visible outside namesys :)

S'cuse me, but why does it have to be run several times?
A bug to be fixed?

>> 4) the repacker is not yet stable - I had to run fsck
>>    a few times after repacking, and once got a kernel
>>    stack trace during repacking resulting in an
>>    un-unmountable filesystem.
>unmergable units shouldn't be problem for the reiser4 kernel code.

What are their significance; what do they mean?

Basically warnings are scary, even if they were harmless :)

Thanks!

-- 
mjt

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Will Smith]

Markus Törnqvist wrote:

>>yes, we had similar results.  it is so cool that reiser4 repacker effect
>>is visible outside namesys :)
> 
> S'cuse me, but why does it have to be run several times?

I don't pretend to know the maths/logic of why, but from the reiser4 
description (http://www.namesys.com/v4/v4.html#repacker)

"This repacker goes through the entire tree ordering, from left to right 
and then from right to left, alternating each time it runs."

"In the absence of FS activity the effect of this over time is to sort 
by tree order (defragment), and to pack with perfect efficiency."


My testing showed that this is indeed the case -

If I ran the repacker once (say left to right), the fragmentation was 
not fully reduced.

If I ran the repacker several times (left->right, right->left, and
repeat) then fragmentation fell down to almost 0.


Userspace Tool for Repacker
----------------------------

I take it from an earlier comment by Hans that the repacker is not
intended to be used yet?  If it is indeed ready for primetime,
is anybody working on userspace tools
(/etc/cron.daily/repacker.reiser4 or similar?)  I'd be happy to
write these if nobody else is - but it will be in /bin/bash shell.

My proposed design specs would include:

1) runs in /etc/cron.daily near the end (since cron causes lots of
    disk activity)
2) the last-run-direction should be persistently stored per filesystem
3) parallel operation on multiple filesystems where possible,
    but filesystems on a single physical device should
    run in serial (same as /sbin/fsck -A)
4) some kind of config file in /etc/, parameters could include
     o) maximum run time, global and per filesystem
     o) run/dont run flag, global and per filesystem


Any thoughts?  Shall I go ahead and write a first cut?



Will Smith

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[mjt]

On Thu, Sep 16, 2004 at 10:50:43PM +0800, Will Smith wrote:
>
>"This repacker goes through the entire tree ordering, from left to right 
>and then from right to left, alternating each time it runs."

This is the default behavior, or?
I thought it scans through once per run and remembers which direction
was the last one.

But maybe I should look into the repacker some more before "opening my
mouth" ;)

>If I ran the repacker several times (left->right, right->left, and
>repeat) then fragmentation fell down to almost 0.

So I take it the direction oopses were fixed, good good :)

>(/etc/cron.daily/repacker.reiser4 or similar?)  I'd be happy to
>write these if nobody else is - but it will be in /bin/bash shell.

There are some drawbacks. Sure essentially every Linux distro has
/bin/sh -> /bin/bash, but still it's a bit fishy to force bash.
Still I agree that bash is superior to sh.

I'd write it in Python, to have niftier getopts handling...

>2) the last-run-direction should be persistently stored per filesystem

This is not stored in /sys?
Is it truly important to store it more persistently?

>3) parallel operation on multiple filesystems where possible,
>   but filesystems on a single physical device should
>   run in serial (same as /sbin/fsck -A)

Should be quite trivial.

>4) some kind of config file in /etc/, parameters could include
>    o) maximum run time, global and per filesystem
>    o) run/dont run flag, global and per filesystem

Direction per run as well?

>Any thoughts?  Shall I go ahead and write a first cut?

Please do, although I think it should be reimplemented in C sooner
or later, just to make sure it's an integral part of the reiser4progs
package :)

-- 
mjt

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Christian Mayrhuber]

On Thursday 16 September 2004 00:02, Will Smith wrote:
> I've spent the last 2 days coding and running benchmarks
> on the effects of fragmentation on both ext3 and
> reiser4 performance.
> 
> Explanation and source code is at
> http://www.willsmith.org/opensource/reiser4/fragperf/
> 
> Results and graphs are at
> http://www.willsmith.org/opensource/reiser4/fragperf/test1/
> 
> 
> Dataset is a kernel source (~200Mb) in a small 350Mb
> partition, with random deletes, copies and overwrites
> to cause fragmentation.
> 
> In conclusion:
> 
> 1) reiser4 is slightly faster than ext3 in some cases, but
>     much faster in others (no surprise).  However,
>     deletes are slightly slower.
> 
> 2) ext3 degrades badly from fragmentation when running
>     ordered (non-random) access patterns.  reiser4
>     also degrades but not as much.
> 
> 3) the repacker can bring performance of reiser4 back
>     to full speed, but only if run several times.
> 
> 4) the repacker is not yet stable - I had to run fsck
>     a few times after repacking, and once got a kernel
>     stack trace during repacking resulting in an
>     un-unmountable filesystem.
> 
> 
> I'll gladly rerun with different parameters and/or change
> the script if requested.
> 
> 
> Will Smith

It would be interesting how the current production version reiserfs (v3.6) 
compares to these results, now that Chris Masons block allocator 
optimizations are in 2.6.8.

-- 
lg, Chris

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Alex Zarochentsev]

On Thu, Sep 16, 2004 at 04:08:09PM +0300, Markus Törnqvist wrote:
> On Thu, Sep 16, 2004 at 12:52:49PM +0400, Alex Zarochentsev wrote:
> 
> >> 3) the repacker can bring performance of reiser4 back
> >>    to full speed, but only if run several times.
> >yes, we had similar results.  it is so cool that reiser4 repacker effect
> >is visible outside namesys :)
> 
> S'cuse me, but why does it have to be run several times?

because the current repacker is too dumb :)  It needs a room to place blocks
there in right order.  So, backward run frees space at the beginning of the
disk, next forward run has enough space for its work. 

I don't want to advocate that algorithm too much, but it was simple enough to
be placed into kernel space.  

We are not going to add more intelligence to the in-kernel repacker module but
design an interface between repacker and user-space programs and implement
reisizing alg. in user-space. 

> A bug to be fixed?
> 
> >> 4) the repacker is not yet stable - I had to run fsck
> >>    a few times after repacking, and once got a kernel
> >>    stack trace during repacking resulting in an
> >>    un-unmountable filesystem.
> >unmergable units shouldn't be problem for the reiser4 kernel code.
> 
> What are their significance; what do they mean?

two extent units (start1, len1), (start2, len2) can be merged into one (start1,
len1 + len2) because start1 + len1 == start2.  I think no reiser4 kernel code
depends on that mergable extents do not exist.

> Basically warnings are scary, even if they were harmless :)
> 
> Thanks!
> 
> -- 
> mjt
> 

-- 
Alex.

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[mjt]

On Thu, Sep 16, 2004 at 07:38:36PM +0400, Alex Zarochentsev wrote:

>We are not going to add more intelligence to the in-kernel repacker module but
>design an interface between repacker and user-space programs and implement
>reisizing alg. in user-space. 

This sounds a bit fishy; is it about having two repackers then?
One in kernelspace and one in userspace?
Will the kernelspace one be obsoleted?

>> >unmergable units shouldn't be problem for the reiser4 kernel code.
>> What are their significance; what do they mean?
>two extent units (start1, len1), (start2, len2) can be merged into one (start1,
>len1 + len2) because start1 + len1 == start2.  I think no reiser4 kernel code
>depends on that mergable extents do not exist.

Unmergable units are then (start1 + len1) != start2 because the repacker
messed this up? 

The kernel finds the extent units from their "old places" without optimizing
them to one unit?

-- 
mjt

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Hans Reiser]

Well, I am going to try being honest and see what happens.

I am more than 170k in debt, and Namesys is doing badly fiscally.  A 
technical great success being stabilized now, but then there is my 
ongoing fiscal disaster.  Once again, we are missing payroll.  My wife 
is divorcing me in part because I keep going deeper into debt, and I 
thank her for divorcing me now rather than later.  Unfortunately she is 
making the divorce messy enough to keep me from pulling Namesys out of 
the fiscal tailspin by consuming all my time with things like proving I 
am not making the fantastic amounts of money she claims I am.  I hope 
next month is better.

The consistent tendency of large corporations to buy service contracts 
only for proprietary software and not buy it for free software of equal 
importance to their business is decisive in making our business not 
viable fiscally.  Knowing that it is irrational of them economically 
does not keep me in business.

So we need something to entice them into cutting a check, to which they 
can then add support.  At the same time we want to avoid harming users 
who cannot pay, or who don't care enough about the FS to bother to pay.

The repacker/resizer seems perfect for that.  Nobody has to have it, and 
yet sysadmins of large corporations will pay for it.  I want them to pay 
5% of their storage hardware costs, which means disk drives plus raid 
cards, and if the machine is primarily a file server it means the whole 
computer.  For this they get a resizer, a repacker, and priority 
support, with cell phone numbers of developers if they pay more than $1000.

I keep experimenting with open source business models, trying to make 
them work.  One of the possibilities for us is a blended model, in which 
all the essentials are free, and the fripperies are for a fee.

There is nothing less essential than an online repacker/resizer.  Yet it 
is desirable enough to pay for.

Reiser4 without an online repacker/resizer is better than ext3 by a 
lot.  The money from the repacker will help us increase that lead 
further.  An online  repacker/resizer could pay for the semantic 
enhancements that are really important to users, and could allow us to 
make those free.    I am worried that because of finances we are not 
going to beat WinFS to market when we otherwise could have done so.

Money is like food.  The difference between a fine restaurant, and just 
having a full refridgerator with ordinary vegetables and meat, is not a 
lot.  The difference between a full refridgerator and an empty one is a lot.

Charity is best if made a part time job of, not because men need money, 
but because families need money, and men need to fulfill that obligation 
well enough that the refridgerator is full.

Hans

PS

We need to have a better understanding of why reiser4 is not doing a 
good enough job with just allocation on flush.  I suspect it should be 
doing better.  Next month I hope to be able to take the time to look 
into it.  I am spending all of my time dealing with divorce and money 
issues and the code is just going unsupervised, sigh....

Will Smith wrote:

>
> Markus Törnqvist wrote:
>
>>> yes, we had similar results.  it is so cool that reiser4 repacker 
>>> effect
>>> is visible outside namesys :)
>>
>>
>> S'cuse me, but why does it have to be run several times?
>
>
> I don't pretend to know the maths/logic of why, but from the reiser4 
> description (http://www.namesys.com/v4/v4.html#repacker)
>
> "This repacker goes through the entire tree ordering, from left to 
> right and then from right to left, alternating each time it runs."
>
> "In the absence of FS activity the effect of this over time is to sort 
> by tree order (defragment), and to pack with perfect efficiency."
>
>
> My testing showed that this is indeed the case -
>
> If I ran the repacker once (say left to right), the fragmentation was 
> not fully reduced.
>
> If I ran the repacker several times (left->right, right->left, and
> repeat) then fragmentation fell down to almost 0.
>
>
> Userspace Tool for Repacker
> ----------------------------
>
> I take it from an earlier comment by Hans that the repacker is not
> intended to be used yet?  If it is indeed ready for primetime,
> is anybody working on userspace tools
> (/etc/cron.daily/repacker.reiser4 or similar?)  I'd be happy to
> write these if nobody else is - but it will be in /bin/bash shell.
>
> My proposed design specs would include:
>
> 1) runs in /etc/cron.daily near the end (since cron causes lots of
>    disk activity)
> 2) the last-run-direction should be persistently stored per filesystem
> 3) parallel operation on multiple filesystems where possible,
>    but filesystems on a single physical device should
>    run in serial (same as /sbin/fsck -A)
> 4) some kind of config file in /etc/, parameters could include
>     o) maximum run time, global and per filesystem
>     o) run/dont run flag, global and per filesystem
>
>
> Any thoughts?  Shall I go ahead and write a first cut?
>
>
>
> Will Smith
>
>
>
>
>
>
>

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Hans Reiser]

Markus Törnqvist wrote:

>On Thu, Sep 16, 2004 at 07:38:36PM +0400, Alex Zarochentsev wrote:
>
>  
>
>>We are not going to add more intelligence to the in-kernel repacker module but
>>design an interface between repacker and user-space programs and implement
>>reisizing alg. in user-space. 
>>    
>>
>
>This sounds a bit fishy; is it about having two repackers then?
>One in kernelspace and one in userspace?
>Will the kernelspace one be obsoleted?
>  
>
The kernel will perform transactions requested by user space.  These 
transactions will be composed by the user space program.

We will start with the simple algorithm we currently use, and then Zam 
and I will go read Knuth and Woods and the web to seriously research 
sorting algorithms which we haven't done yet. 

>>>>unmergable units shouldn't be problem for the reiser4 kernel code.
>>>>        
>>>>
>>>What are their significance; what do they mean?
>>>      
>>>
>>two extent units (start1, len1), (start2, len2) can be merged into one (start1,
>>len1 + len2) because start1 + len1 == start2.  I think no reiser4 kernel code
>>depends on that mergable extents do not exist.
>>    
>>
>
>Unmergable units are then (start1 + len1) != start2 because the repacker
>messed this up? 
>
>The kernel finds the extent units from their "old places" without optimizing
>them to one unit?
>
>  
>

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Alex Zarochentsev]

On Thu, Sep 16, 2004 at 06:52:48PM +0300, Markus Törnqvist wrote:
> On Thu, Sep 16, 2004 at 07:38:36PM +0400, Alex Zarochentsev wrote:
> 
> >We are not going to add more intelligence to the in-kernel repacker module but
> >design an interface between repacker and user-space programs and implement
> >reisizing alg. in user-space. 
> 
> This sounds a bit fishy; is it about having two repackers then?
> One in kernelspace and one in userspace?
> Will the kernelspace one be obsoleted?

on-line defragmenter requires its part to be in kernel space. at least node
locks cannot be exported _safely_ to the user space, I think.

> 
> >> >unmergable units shouldn't be problem for the reiser4 kernel code.
> >> What are their significance; what do they mean?
> >two extent units (start1, len1), (start2, len2) can be merged into one (start1,
> >len1 + len2) because start1 + len1 == start2.  I think no reiser4 kernel code
> >depends on that mergable extents do not exist.
> 
> Unmergable units are then (start1 + len1) != start2 because the repacker
> messed this up? 

it can be so because of regular fs activity.   Current block allocation (and
flush algorithm) is not good for appending to existing files.  A free space
after well-allocated reiser4 tree or a well-allocated part of the reiser4 tree
(in case of repacker) can be allocated randomly between new data blocks for
those files.

My opinion -- reiser4 is good in (re)allocating slums.  In case of allocation
many small slums it may be not effective.  The idea of the reiser4 repacker is
to create large slums and allow flush code to do its work.

> 
> The kernel finds the extent units from their "old places" without optimizing
> them to one unit?

in some places, yes, those extents will be merged into one. but i agree, we
can't allow number of those units to grow unlimitedly.  IMHO it would be enough
if the repacker will scan units and do what now is done by fsck -- merging of
mergeable units.

> -- 
> mjt

-- 
Alex.

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[mjt]

On Thu, Sep 16, 2004 at 10:38:31PM +0400, Alex Zarochentsev wrote:
>
>on-line defragmenter requires its part to be in kernel space. at least node
>locks cannot be exported _safely_ to the user space, I think.

What if it was like 
echo -n "Killer Algo by Zam" > /sys/fs/reiser4/hda1/repacker/algorithm
or something to get rid of the risk of having two really separate
mechanisms, and if it can't be in userspace either way...

This is also probably related to what Nik said back in the days about
an online-fsck being impossible :)

-- 
mjt

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Chris Mason]

On Thu, 2004-09-16 at 15:00, Markus TXrnqvist wrote:
> On Thu, Sep 16, 2004 at 10:38:31PM +0400, Alex Zarochentsev wrote:
> >
> >on-line defragmenter requires its part to be in kernel space. at least node
> >locks cannot be exported _safely_ to the user space, I think.
> 
> What if it was like 
> echo -n "Killer Algo by Zam" > /sys/fs/reiser4/hda1/repacker/algorithm
> or something to get rid of the risk of having two really separate
> mechanisms, and if it can't be in userspace either way...
> 
> This is also probably related to what Nik said back in the days about
> an online-fsck being impossible :)

It seems sensible to break up the algorithm somewhat between kernel and
userland.  The problem is just in finding units of work for the userland
code to advise on.  For files this is easy, for metadata and tree
indexes it is somewhat harder.

-chris

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Hans Reiser]

Markus Törnqvist wrote:

>On Thu, Sep 16, 2004 at 10:38:31PM +0400, Alex Zarochentsev wrote:
>  
>
>>on-line defragmenter requires its part to be in kernel space. at least node
>>locks cannot be exported _safely_ to the user space, I think.
>>    
>>
>
>What if it was like 
>echo -n "Killer Algo by Zam" > /sys/fs/reiser4/hda1/repacker/algorithm
>or something to get rid of the risk of having two really separate
>mechanisms, and if it can't be in userspace either way...
>
>This is also probably related to what Nik said back in the days about
>an online-fsck being impossible :)
>
>  
>
Online fsck is possible.  Will do it for SuSE for 200k.;-)

It is a very serious task.  I would not do it just for fun.  It is, 
however, feasible.

Hans

Re: Benchmark : ext3 vs reiser4 and effects of fragmentation.

[Philippe Gramoullé]

Hello Hans,

On Thu, 16 Sep 2004 19:29:27 -0700
Hans Reiser <reiser@namesys.com> wrote:

  | >This is also probably related to what Nik said back in the days about
  | >an online-fsck being impossible :)
  | >
  | >  
  | >
  | Online fsck is possible.  Will do it for SuSE for 200k.;-)
  | 
  | It is a very serious task.  I would not do it just for fun.  It is, 
  | however, feasible.

i really wonder why big layers haven't invested the money, because to me this is such a killer feature.

It would have saved us so many times :)

Thanks,

Philippe