Backup Central

in looking at the pool on our backup machine yesterday, we got to
wondering... currently the pool has paths like:
/big/backuppc/pool/1/2/3/123456789abcdef0

in our case, this leads to leaf directories which are all about
50K large, mostly containing about 1000 files each. since the
final phase of a path lookup is always a linear search
(correct?), mightn't performance be improved by making one or all
of the intermediate path components "wider", i.e., something
like:
/big/backuppc/pool/1/2/34/123456789abcdef0
unless i'm missing something, just doing this would reduce the
leaf directories to more like 3K or 4K bytes, with fewer than a
hundred entries to search.

i'd think that on a ram-limited system this would reduce disk
activity, at the same time that it would reduce cpu time spent
searching the last directory (on any system). i don't claim to
be an expert, but wouldn't better balance to the tree be better?

paul
=---------------------
paul fox, pgf < at > foxharp.boston.ma.us (arlington, ma, where it's 67.6 degrees)


-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

On Wed, 2004-06-09 at 06:57, Paul Fox wrote:
in looking at the pool on our backup machine yesterday, we got to
wondering... currently the pool has paths like:
/big/backuppc/pool/1/2/3/123456789abcdef0

in our case, this leads to leaf directories which are all about
50K large, mostly containing about 1000 files each. since the
final phase of a path lookup is always a linear search
(correct?), mightn't performance be improved by making one or all
of the intermediate path components "wider", i.e., something
like:

Reiserfs builds balanced trees for the directory entries
so they scale up nicely. The directories aren't the problem
as shown by a simple 'ls' being fast. The problem is that
the directories don't contain the inodes. There may be
many (or no) directory entries pointing to each inode.
Reading an uncached inode requires a disk seek, which is
the slow part.

---
Les Mikesell
les < at > futuresource.com




-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

in looking at the pool on our backup machine yesterday, we got to
wondering... currently the pool has paths like:
/big/backuppc/pool/1/2/3/123456789abcdef0

in our case, this leads to leaf directories which are all about
50K large, mostly containing about 1000 files each. since the
final phase of a path lookup is always a linear search
(correct?), mightn't performance be improved by making one or all
of the intermediate path components "wider", i.e., something
like:

Reiserfs builds balanced trees for the directory entries
so they scale up nicely. The directories aren't the problem

does this balanced tree implementation you refer to apply both
on-disk and in-memory. i confess to not having looked at the
linux filesystem code -- does each fs supply their own in-core
directory access routine?

as shown by a simple 'ls' being fast. The problem is that
the directories don't contain the inodes. There may be
many (or no) directory entries pointing to each inode.
Reading an uncached inode requires a disk seek, which is
the slow part.

yes, i understand that. we're buying more memory today. i
guess i was just exhibiting old-dog reactions to huge
directories.

thanks,
paul
=---------------------
paul fox, pgf < at > foxharp.boston.ma.us (arlington, ma, where it's 82.9 degrees)


-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

On 06/09 11:46 , Paul Fox wrote:
Reiserfs builds balanced trees for the directory entries
so they scale up nicely. The directories aren't the problem

does this balanced tree implementation you refer to apply both
on-disk and in-memory. i confess to not having looked at the
linux filesystem code -- does each fs supply their own in-core
directory access routine?

I belive in memory the inodes are stored in a radix tree (which is *very*
fast); but I could be very far off base here.

--
Carl Soderstrom
Systems Administrator
Real-Time Enterprises
www.real-time.com


-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

Reiserfs builds balanced trees for the directory entries
so they scale up nicely. The directories aren't the problem

does this balanced tree implementation you refer to apply both
on-disk and in-memory. i confess to not having looked at the
linux filesystem code -- does each fs supply their own in-core
directory access routine?

I belive in memory the inodes are stored in a radix tree (which is *very*
fast); but I could be very far off base here.

but that's different data than the directory entries.

paul
=---------------------
paul fox, pgf < at > foxharp.boston.ma.us (arlington, ma, where it's 86.4 degrees)


-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

On Wed, 2004-06-09 at 10:46, Paul Fox wrote:

Reiserfs builds balanced trees for the directory entries
so they scale up nicely. The directories aren't the problem

does this balanced tree implementation you refer to apply both
on-disk and in-memory. i confess to not having looked at the
linux filesystem code -- does each fs supply their own in-core
directory access routine?

I'm not an expert on Linux internals but I thought there was
some kind of unified cache so the first lookup happens in
a space shared across different filesystem types. Each type
might add its own unique layer besides that, and then there
should be some raw disk read-ahead space.

yes, i understand that. we're buying more memory today. i
guess i was just exhibiting old-dog reactions to huge
directories.

Yes, I remember old SysV boxes that slowed down dramatically
when you had more than 300 entries in a directory, but that
was back when 4 Megs (yes megs...) was all you could cram into
a box and it cost more than a whole machine does today.

---
Les Mikesell
les < at > futuresource.com




-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

On 06/09 12:16 , Les Mikesell wrote:
I'm not an expert on Linux internals but I thought there was
some kind of unified cache so the first lookup happens in
a space shared across different filesystem types. Each type
might add its own unique layer besides that,

yes.

and then there
should be some raw disk read-ahead space.

this part I don't know about, but I'm not quite sure what you mean.

--
Carl Soderstrom
Systems Administrator
Real-Time Enterprises
www.real-time.com


-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

On Wed, 2004-06-09 at 12:59, Carl Wilhelm Soderstrom wrote:

and then there
should be some raw disk read-ahead space.

this part I don't know about, but I'm not quite sure what you mean.

If you only need a few disk sectors from one spot, I think the low
level disk access will do some amount of read-ahead because it is
fast and the odds are that you will want that next. This isn't
always the case and older unix systems had 'raw' and 'cooked' devices
where the raw ones where completely unbuffered so things like
dedicated databases could control the disk more precisely. Linux
seems to have done away with the difference so I'm not sure how
it really works now.

---
Les Mikesell
les < at > futuresource.com




-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/

On 06/09 01:24 , Les Mikesell wrote:
If you only need a few disk sectors from one spot, I think the low
level disk access will do some amount of read-ahead because it is
fast and the odds are that you will want that next.

yes.
of course, this is *really* tweakable now... there's a lot of different
kernel patches which affect disk scheduling.
it might bear some experimentation, to find out just what kernel options
(low-latency, preemptiveness) and patches (deadline scheduler, CFQ
scheduler, etc) give the best performance boost.
I'm betting it's not that much difference, but I could be very wrong.

This isn't
always the case and older unix systems had 'raw' and 'cooked' devices
where the raw ones where completely unbuffered so things like
dedicated databases could control the disk more precisely. Linux
seems to have done away with the difference so I'm not sure how
it really works now.

there *are* 'raw' devices under linux now; but you shouldn't use them,
unless you're Oracle, Sybase, or *really* know what you're doing.

In the opinion of the top kernel developers, they really aren't needed that
much; most of the time the OS will be more efficient anyway, due to cacheing
and the like.

--
Carl Soderstrom
Systems Administrator
Real-Time Enterprises
www.real-time.com


-------------------------------------------------------
This SF.Net email is sponsored by: GNOME Foundation
Hackers Unite! GUADEC: The world's #1 Open Source Desktop Event.
GNOME Users and Developers European Conference, 28-30th June in Norway
http://2004/guadec.org
_______________________________________________
BackupPC-users mailing list
BackupPC-users < at > lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/backuppc-users
http://backuppc.sourceforge.net/