Suggestion: preventing inode crowding with FSFS

[Kean Johnston <jk...@sco.com>]

All,

I am about to convert a fairly large CVS repository over to
svn (yay - thats hwta SVN aims at eh?). I'm going to be using
FSFS. I have been doing some tests, and I think I recall the
doc even talking about this, but as I understand it, each new
revision lands in a new file in revs/. Ofbviously, with
hundreds, thousands or even hundreds of thousands of revs,
this doesn't scale well on many platforms where you start
paying a severe penalty when a single directory has too many
inodes in it.

Did the designers consider a scheme similar to what Squid
does (it has the same problem, wants to put thousands of
cached files into a database)? An effective way to do this
is thus. Convert the revision number to a 8-digit hex number.
Take the very last digit as a top level directory. Take the
next two digits as a second tier directory. The create the
file inside that directory. This spreads the load out fairly
evenly, and I would image it would be pretty trivial to
imnplement.

If anyone likes the idea and can point me in the approximate
direction of the right place in teh code, I will work on a
patch to do so. However, fi this idea has been previously
suggested and subsequently rejected for some reason, I'd
be curious why it was rejected.

Kean

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

["Ph. Marek" <ph...@bmlv.gv.at>]

On Friday 07 October 2005 21:04, Greg Hudson wrote:
> On Fri, 2005-10-07 at 12:47 -0500, kfogel@collab.net wrote:
> > Greg Hudson <gh...@MIT.EDU> writes:
> > > The new layout cannot be on by default until 2.0.
> >
> > I'm not advocating that we implement a new layout, but if we do, why
> > would it have to wait till 2.0 to be the default?  I thought such a
> > change could happen in a new minor release.  From hacking.html:
>
> Because one of the usage modes of FSFS is to put it in a shared
> filesystem and access it from multiple clients, which might not be in
> version-sync, it's adviseable to avoid backward-incompatible layout
> changes when we can.
>
> But you're right that it's not a hard requirement.

If such a change is made, I'd like to ask that the transactions are treated 
equally.

In fsvs I'm checking whole machine installations in at once (eg. 150 000 
files), and that results in 300000 files in the transaction-subdirectories 
(one for file-data, and another for the properties per file).

Thank you!


Regards,

Phil

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

[Greg Hudson <gh...@MIT.EDU>]

On Fri, 2005-10-07 at 12:47 -0500, kfogel@collab.net wrote:
> Greg Hudson <gh...@MIT.EDU> writes:
> > The new layout cannot be on by default until 2.0.
> 
> I'm not advocating that we implement a new layout, but if we do, why
> would it have to wait till 2.0 to be the default?  I thought such a
> change could happen in a new minor release.  From hacking.html:

Because one of the usage modes of FSFS is to put it in a shared
filesystem and access it from multiple clients, which might not be in
version-sync, it's adviseable to avoid backward-incompatible layout
changes when we can.

But you're right that it's not a hard requirement.


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

[kf...@collab.net]

Greg Hudson <gh...@MIT.EDU> writes:
> The new layout cannot be on by default until 2.0.

I'm not advocating that we implement a new layout, but if we do, why
would it have to wait till 2.0 to be the default?  I thought such a
change could happen in a new minor release.  From hacking.html:

   Working copy and repository formats are backward- and
   forward-compatible for all patch releases in the same minor series.
   They are forward-compatible for all minor releases in the same
   major series; however, a minor release is allowed to make a working
   copy or repository that doesn't work with previous minor releases,
   where "make" could mean "upgrade" as well as "create".

Is there some other concern I'm missing?

-Karl

-- 
www.collab.net  <>  CollabNet  |  Distributed Development On Demand

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

[Kean Johnston <jk...@sco.com>]

> Perhaps you mean quadratic?  If access time doubles for every 4096
Perhaps I did :) I cant even add 1 + 1 without the aid of bc
or my trusty HP11C :) I'm mathematically challenged. Considering
your FQDN, I suspect you are not :)

> inodes, then SCO is more broken than one might expect. :)
No argument here :) But the new versions use Veritas VxFS, which
isn't thus constrained but still I'd like to add the feature, for
a few reasons. First, I'm a firm believer in contributing, even
if something small like this, to stuff I use. Second, Id really
like to start getting to know the internals of svn better, and
third, it does actually scale better. If nothing else, it makes
a casual 'ls' quicker as it doesnt have to sort hundreds of
thousands of entries :)

Kean

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

[Greg Hudson <gh...@MIT.EDU>]

On Fri, 2005-10-07 at 11:59 +0200, Peter N. Lundblad wrote:
> > > We might prefer something simpler; I'm not sure if the load-spreading
> > > goal of the Squid cache layout is of any great value to a Subversion
> > > repository.  Also, although 2^64 is "plenty" of revisions, the current
> > > FSFS layout does not impose an upper limit on the number of revisions,
> > > and it would be nice to keep that property.
> > The FSFS layout may not impose such a limitation but the data
> > type for a revision does. In fact, it limits it to 2^31 on
> > a 32-bit platform or 2^63 on a 64 bit one (its a long int).
> 
> Heh, it seems that you could commit a revision per millisecond for some
> hundred million years before hitting that 2^64 revisions limit. Greg, is
> this only a theoretical concern, or are you expecting bug reports from the
> future? :-)

It's just more elegant not to have the layout imposing size
restrictions.  Yes, the data type used in the implementation also
imposes a restriction, but persistent data formats need to be more
conscious of this issue than implementations.

> > I could do almost all the rest except for that bit. I just
> > dont "get" Python (but admittedly havent tried too hard either).

> To me this seems more like a nice-to-have than a must-have.

Yes; I don't think a conversion script is a pre-condition to having this
in the code base.

> > Its a nice exponential degradation for each multiple of 4096 inodes.

Perhaps you mean quadratic?  If access time doubles for every 4096
inodes, then SCO is more broken than one might expect. :)


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

["Peter N. Lundblad" <pe...@famlundblad.se>]

On Fri, 7 Oct 2005, Kean Johnston wrote:

> >   * Provide a Python script to convert an existing repository to the new
> > layout.  (An sh script would be simpler, but wouldn't work on Windows.)
> I could do almost all the rest except for that bit. I just
> dont "get" Python (but admittedly havent tried too hard either).
>
To me this seems more like a nice-to-have than a must-have. You can always
dump/load to get the new format. But it can't be a big script.


>
> > We might prefer something simpler; I'm not sure if the load-spreading
> > goal of the Squid cache layout is of any great value to a Subversion
> > repository.  Also, although 2^64 is "plenty" of revisions, the current
> > FSFS layout does not impose an upper limit on the number of revisions,
> > and it would be nice to keep that property.
> The FSFS layout may not impose such a limitation but the data
> type for a revision does. In fact, it limits it to 2^31 on
> a 32-bit platform or 2^63 on a 64 bit one (its a long int).

Heh, it seems that you could commit a revision per millisecond for some
hundred million years before hitting that 2^64 revisions limit. Greg, is
this only a theoretical concern, or are you expecting bug reports from the
future? :-)

Thanks,
//Peter

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

[Kean Johnston <jk...@sco.com>]

> So far I've seen a fair number of people worrying about the problem, but
> not many people experiencing it.
I suspect that most people are actually using approximately
modern filesystems, where its less likely to be an issue.
On the platform I care about (SCO, which means almost no-one
else does), the FS does indeed slow down drastically after
4096 inodes in a directory. Its a nice exponential degradation
for each multiple of 4096 inodes.

>   * Provide a Python script to convert an existing repository to the new
> layout.  (An sh script would be simpler, but wouldn't work on Windows.)
I could do almost all the rest except for that bit. I just
dont "get" Python (but admittedly havent tried too hard either).


> We might prefer something simpler; I'm not sure if the load-spreading
> goal of the Squid cache layout is of any great value to a Subversion
> repository.  Also, although 2^64 is "plenty" of revisions, the current
> FSFS layout does not impose an upper limit on the number of revisions,
> and it would be nice to keep that property.
The FSFS layout may not impose such a limitation but the data
type for a revision does. In fact, it limits it to 2^31 on
a 32-bit platform or 2^63 on a 64 bit one (its a long int).
So at the point where you must do a sprintf of the revision to
get to the name (%d most likely) the limitation is implied.

I will look at all the other code you pointed me at. Thanks
for the pointers Greg.

Kean

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org

Re: Suggestion: preventing inode crowding with FSFS

[Greg Hudson <gh...@MIT.EDU>]

On Fri, 2005-10-07 at 00:12 -0700, Kean Johnston wrote:
> Ofbviously, with
> hundreds, thousands or even hundreds of thousands of revs,
> this doesn't scale well on many platforms where you start
> paying a severe penalty when a single directory has too many
> inodes in it.

So far I've seen a fair number of people worrying about the problem, but
not many people experiencing it.

That said, we would be interested in code to support a more complex
layout as an option--at least if the code came with performance
measurements showing that the code would actually benefit someone.  It
would go something like this:

  * Design the new layout in such a way that it can be recognized when
an FS is opened.
  * Add an option to svnadmin create to use the new layout.
  * Provide a Python script to convert an existing repository to the new
layout.  (An sh script would be simpler, but wouldn't work on Windows.)

The new layout cannot be on by default until 2.0.

> Did the designers consider a scheme similar to what Squid
> does (it has the same problem, wants to put thousands of
> cached files into a database)? An effective way to do this
> is thus. Convert the revision number to a 8-digit hex number.
> Take the very last digit as a top level directory. Take the
> next two digits as a second tier directory. The create the
> file inside that directory. This spreads the load out fairly
> evenly, and I would image it would be pretty trivial to
> imnplement.

We might prefer something simpler; I'm not sure if the load-spreading
goal of the Squid cache layout is of any great value to a Subversion
repository.  Also, although 2^64 is "plenty" of revisions, the current
FSFS layout does not impose an upper limit on the number of revisions,
and it would be nice to keep that property.

> If anyone likes the idea and can point me in the approximate
> direction of the right place in teh code, I will work on a
> patch to do so. However, fi this idea has been previously
> suggested and subsequently rejected for some reason, I'd
> be curious why it was rejected.

Relevant code:

  svnadmin/main.c -- to add the svnadmin option; see how existing BDB
options are handled

  libsvn_fs_fs/fs.h -- add a field to fs_fs_data_t tracking whether the
repository is using the new layout

  libsvn_fs_fs/fs.c -- fs_create and fs_open are here

  libsvn_fs_fs/fs_fs.c -- svn_fs_fs__path_rev needs adjustment, and
path_revproprs probably needs to be changed to take a revision number so
that it can be similarly adjusted.  Some callers would need to be
changed to ensure the containing directory exists.

When creating directories to place rev files into, make sure to copy the
mode of a reference directory (the one containing rev 0, perhaps) so
that the umask of the current user doesn't prevent other users in the
group from accessing the repository.  See
libsvn_fs_fs/lock.c:ensure_dir_exists() for an example; that function
might want to move to fs_fs.c and be exported so that it can be used
within fs_fs.c.


---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@subversion.tigris.org
For additional commands, e-mail: dev-help@subversion.tigris.org