Re: optimizing fsfs: reverse diffs?

Mark,

  Thanks for the design info, that helps a lot. So under FSFS a checkout of the latest revision takes O(lg(N)) on avg instead of O(N) as I had assumed. Still, if you always stored the latest revision of a file in full & stored the transactions as reverse diffs, checkout latest would be an O(1) operation. Even better.

  One could certainly cook up a skip-delta scheme for this. Each skip-delta path terminates in a full copy of the file. A commit overwrites this copy, but not before a reverse delta is added behind it. Perhaps the real problem is more of an architectural clash; I can't say because I'm not an svn developer.

  It just seems to me that checkouts may not be as optimized for the common case as they could be. As an svn admin & very interested follower of the project, I've heard "checkouts are slow" quite a lot, and know of at least one large opensource project (open exchange) that have delayed their migration to svn until things improve in that department.

On Fri, Apr 08, 2005 at 11:03:24AM -0400, Mark Phippard wrote:
> Alan Grow <agrow@thegotonerd.com> wrote on 04/08/2005 10:44:39 AM:
>
> > FSFS is great, but I'm a little worried about checkout slowdown,
> especially
> > as a project ages. Instead of reconstructing the current revision each
> time
> > from an ever-lengthening sequence of forward diffs, why doesn't FSFS
> optimize
> > for the common case and store the full current revision and a sequence
> of
> > reverse diffs? (Ala rdiff-backup: http://www.nongnu.org/rdiff-backup/.)
> >
> > I'll pack my bags & go to dev with this question if you think I
> should. :)
> > Thought I'd try here first though.
>
> FSFS doesn't work quite the way you think. It uses something called
> skip-deltas. The bad thing about reverse diffs is that the database has
> to be constantly rewritten. FSFS wanted to support a permissions
> structure where you only need to have enough permission to write a new
> file. Existing files are in the database are NEVER updated after they
> have been written. This also makes for a good incremental backup
> solution.
>
> The skip-deltas approach is a great compromise. It yields good
> performance, and better space utilization. Read the design notes.
>
> http://svn.collab.net/repos/svn/trunk/notes/skip-deltas
>
> Mark
>
>
>
>
>
>
> _____________________________________________________________________________
> Scanned for SoftLanding Systems, Inc. by IBM Email Security Management Services powered by MessageLabs.
> _____________________________________________________________________________
>

-- 
Alan Grow
Software Engineer / 
Opensource Consultant
402-304-0568
---------------------------------------------------------------------
To unsubscribe, e-mail: users-unsubscribe@subversion.tigris.org
For additional commands, e-mail: users-help@subversion.tigris.org