You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Zack Weinberg <za...@wolery.cumb.org> on 2000/06/03 21:03:11 UTC
Re: [subversion-dev] Subversion design document up
On Sat, Jun 03, 2000 at 12:28:14AM -0500, Karl Fogel wrote:
> Okay, answers to a lot of questions can now be found at:
>
> http://subversion.tigris.org/project_docs.html
>
> Programmers looking for design and API descriptions, this is the place.
>
> We're going to start coding now. It would of course be silly to ask
> for volunteers before we have running code or even header files :-),
> but if anyone has comments/thoughts on the design so far, please post.
I have a number of suggestions. Some of them may already be covered
but it's not immediately obvious.
There are two separate merge schemes described. One handles merges
between branches (clones), another is for when you have edited your
working copy and someone else commits changes under your feet. The
latter scheme is substantially less powerful, but handles the common
case; this is bad.
A better arrangement would be to cause an implicit branch to occur
when the conflict is detected. If B is the base, Z is my changes and
Y is yours, create this subtree:
B --- Z
\--- Y
Then merge Y into Z using the branch-merge algorithm. There are
multiple advantages to this approach. First, the branch-merge
algorithm has more information available to it and is therefore less
likely to mangle the merge. Second, if you go on working on your
implicit branch and don't pick up my changes:-
B --- Z -- M
\ /
--- Y ------ Y2
then I can pick up Y2 using the ancestor-set algorithm to avoid
merging the changes from Y again. Third, it's possible to recover
the original Z, which did not include the changes in Y. If I discover
that Y is unusable, I can go back to Z and continue working on my own
code until the Y branch becomes functional again.
------ Z2 .... Zn
/ \
B --- Z -- M M2
\ / /
--- Y ------ Y2 .... Yn
Obviously a scheme like this is going to use lots of implicit
branches. I *think* the clone mechanism can handle them just fine,
and if it can't it should be made to do so - you really don't want
multiple branch abstractions.
You may or may not have noticed that this requires "working
repositories". That's listed under blue sky items at the moment,
probably because you don't see why it's a critical feature. The
psychological comfort is _not_ the important reason for personal
repositories. The primary reason is that it makes the above merge
technique *possible*. You cannot implement it unless Z is a
full-fledged version instead of a set of modified working files.
Another reason to do working repositories immediately is that it gets
you mirror repositories for free. A mirror is just a working
repository with an active server to export it to the world. And that,
in turn, means you can distribute your own personal hacks on top of
some tree. Sounds like a marginal feature? Not so. Consider this
hierarchy:
linus
/ | \
alan ingo davem
/ \
rik ingo
... All the lower nodes being people who have maintained diffs
relative to the 'official' kernel tree - or relative to someone else's
modified tree! - for extended periods of time. Or, try this one on
for size:
4.4
| \
F N
| X | \
F N O
| X | X |
F N O
: : :
which doesn't convey either the exact history or the extent of the
patches being lobbed back and forth, but what do you expect from ASCII
art...
And another reason why you want working repositories is it cuts the
number of primitive operations over the network down to one. Yes,
one. It's called "resync", and it works rather like rsync (hence the
name). Each root node must have a unique identifier for this - in the
presence of distributed repositories, the serial number does not
suffice. Anyway, a resync has a source and a destination. The
destination sends to the source a list of all its node IDs. The
source calculates the set of all nodes present in its repository which
the destination does not have, and sends the deltas for those nodes
back. Destination applies those nodes, possibly resolving conflicts.
The conflict-resolution algorithm is just the normal branch-merge
algorithm.
Optionally, source can send back a list of nodes that destination
has but it doesn't, and destination can send those to source. Also
optionally, destination can remember all the nodes known to be present
in both trees, so it doesn't have to send a complete list to source.
But the lists are going to be small, anyway.
Creating a mirror or personal repository is just the special case
where the destination's list is empty. You probably want a special
transfer protocol for this case, which doesn't break everything down
into deltas and build it up again at the end.
---
There isn't a lot of discussion of how data and metadata are going to
be stored on disk. (One offhand mention of berkeley DB and/or a full
blown SQL database - either one seems like overkill to me, frankly.)
I would suggest that each node in the tree be two files. One contains
metadata and is only ever appended to. Another contains the file data
(if any - directory nodes don't need this) and is updated by writing a
new copy and renaming it into place. You may or may not need a
per-file locking protocol.
Everything should be checksummed. Exercise: Pick any large CVS
repository. Scan through all of the files. I guarantee you will find
at least one file which has lost at least one disk block: 2^n bytes
will have been overwritten with nulls. Odds are that happened so long
ago that no backup records the original contents of that block. No
one has noticed because no one's wanted a revision back that far -
yet.
For storing file data, I'd recommend looking at the "weave" algorithm
used by SCCS. It stores the file as an array of lines with
annotations which say whether or not a given line belongs in some
revision. This has two major wins over the current+reverse diffs
format used by RCS. First, all revisions take the same time to
extract, and you do not have to edit the working file in memory. A
single linear scan over the archive file, selecting lines and writing
them out, suffices. This is particularly desirable if you have many
branches. Second, it provides the concept of included and excluded
deltas, which let you do many merge operations just by adding an entry
to the file index - no modification to the archive is needed.
The trouble with the weave algorithm is it's line oriented and
therefore won't play nice with vcdiff. SCCS itself handles binary
files horribly (it uuencodes them and then tries to diff the results,
yuck). But SCCS' real problem with binaries is it uses \n\001 as an
escape sequence. You could trivially avoid that, and with a bit more
effort I bet weave could be made to work on arbitrary byte runs
instead of lines.
zw
Re: [subversion-dev] Subversion design document up
Posted by Zack Weinberg <za...@wolery.cumb.org>.
On Mon, Jun 05, 2000 at 01:07:46PM -0500, Karl Fogel wrote:
> Regarding the local-repository-branching issue you mentioned:
>
> I think there's general agreement that it's an important thing to
> support, but everything that comes before it is necessary
> understructure anyway. In other words, saying "We need to have this
> feature in the 1.0 release" would be more a matter of shifting the
> "1.0" label moment than about changing when implementation of the
> feature actually happens.
>
> Since our stated goal for 1.0 has simply been to support basically
> what CVS supports, this feature would go in the "immediate post-1.0"
> category.
Okay, this is fair. You might need more networking code that way, but
given your stated intention of making it be client-server even on a local
repository, you'll need it anyway.
> Along with "cvs annotate" functionality, local-repos branch
> support is probably our highest priority following the initial
> release.
Oh, did I mention that 'cvs annotate' is trivial with the SCCS file format?
zw
Re: [subversion-dev] Subversion design document up
Posted by Karl Fogel <kf...@galois.collab.net>.
Regarding the local-repository-branching issue you mentioned:
I think there's general agreement that it's an important thing to
support, but everything that comes before it is necessary
understructure anyway. In other words, saying "We need to have this
feature in the 1.0 release" would be more a matter of shifting the
"1.0" label moment than about changing when implementation of the
feature actually happens.
Since our stated goal for 1.0 has simply been to support basically
what CVS supports, this feature would go in the "immediate post-1.0"
category. Along with "cvs annotate" functionality, local-repos branch
support is probably our highest priority following the initial
release.
Regarding storage: it has to work, and not corrupt data, yes. :-)
-Karl
Zack Weinberg <za...@wolery.cumb.org> writes:
> I have a number of suggestions. Some of them may already be covered
> but it's not immediately obvious.
>
> There are two separate merge schemes described. One handles merges
> between branches (clones), another is for when you have edited your
> working copy and someone else commits changes under your feet. The
> latter scheme is substantially less powerful, but handles the common
> case; this is bad.
>
> A better arrangement would be to cause an implicit branch to occur
> when the conflict is detected. If B is the base, Z is my changes and
> Y is yours, create this subtree:
>
> B --- Z
> \--- Y
>
> Then merge Y into Z using the branch-merge algorithm. There are
> multiple advantages to this approach. First, the branch-merge
> algorithm has more information available to it and is therefore less
> likely to mangle the merge. Second, if you go on working on your
> implicit branch and don't pick up my changes:-
>
> B --- Z -- M
> \ /
> --- Y ------ Y2
>
> then I can pick up Y2 using the ancestor-set algorithm to avoid
> merging the changes from Y again. Third, it's possible to recover
> the original Z, which did not include the changes in Y. If I discover
> that Y is unusable, I can go back to Z and continue working on my own
> code until the Y branch becomes functional again.
>
> ------ Z2 .... Zn
> / \
> B --- Z -- M M2
> \ / /
> --- Y ------ Y2 .... Yn
>
> Obviously a scheme like this is going to use lots of implicit
> branches. I *think* the clone mechanism can handle them just fine,
> and if it can't it should be made to do so - you really don't want
> multiple branch abstractions.
>
> You may or may not have noticed that this requires "working
> repositories". That's listed under blue sky items at the moment,
> probably because you don't see why it's a critical feature. The
> psychological comfort is _not_ the important reason for personal
> repositories. The primary reason is that it makes the above merge
> technique *possible*. You cannot implement it unless Z is a
> full-fledged version instead of a set of modified working files.
>
> Another reason to do working repositories immediately is that it gets
> you mirror repositories for free. A mirror is just a working
> repository with an active server to export it to the world. And that,
> in turn, means you can distribute your own personal hacks on top of
> some tree. Sounds like a marginal feature? Not so. Consider this
> hierarchy:
>
> linus
> / | \
> alan ingo davem
> / \
> rik ingo
>
> ... All the lower nodes being people who have maintained diffs
> relative to the 'official' kernel tree - or relative to someone else's
> modified tree! - for extended periods of time. Or, try this one on
> for size:
>
> 4.4
> | \
> F N
> | X | \
> F N O
> | X | X |
> F N O
> : : :
>
> which doesn't convey either the exact history or the extent of the
> patches being lobbed back and forth, but what do you expect from ASCII
> art...
>
> And another reason why you want working repositories is it cuts the
> number of primitive operations over the network down to one. Yes,
> one. It's called "resync", and it works rather like rsync (hence the
> name). Each root node must have a unique identifier for this - in the
> presence of distributed repositories, the serial number does not
> suffice. Anyway, a resync has a source and a destination. The
> destination sends to the source a list of all its node IDs. The
> source calculates the set of all nodes present in its repository which
> the destination does not have, and sends the deltas for those nodes
> back. Destination applies those nodes, possibly resolving conflicts.
> The conflict-resolution algorithm is just the normal branch-merge
> algorithm.
>
> Optionally, source can send back a list of nodes that destination
> has but it doesn't, and destination can send those to source. Also
> optionally, destination can remember all the nodes known to be present
> in both trees, so it doesn't have to send a complete list to source.
> But the lists are going to be small, anyway.
>
> Creating a mirror or personal repository is just the special case
> where the destination's list is empty. You probably want a special
> transfer protocol for this case, which doesn't break everything down
> into deltas and build it up again at the end.
>
> ---
>
> There isn't a lot of discussion of how data and metadata are going to
> be stored on disk. (One offhand mention of berkeley DB and/or a full
> blown SQL database - either one seems like overkill to me, frankly.)
> I would suggest that each node in the tree be two files. One contains
> metadata and is only ever appended to. Another contains the file data
> (if any - directory nodes don't need this) and is updated by writing a
> new copy and renaming it into place. You may or may not need a
> per-file locking protocol.
>
> Everything should be checksummed. Exercise: Pick any large CVS
> repository. Scan through all of the files. I guarantee you will find
> at least one file which has lost at least one disk block: 2^n bytes
> will have been overwritten with nulls. Odds are that happened so long
> ago that no backup records the original contents of that block. No
> one has noticed because no one's wanted a revision back that far -
> yet.
>
> For storing file data, I'd recommend looking at the "weave" algorithm
> used by SCCS. It stores the file as an array of lines with
> annotations which say whether or not a given line belongs in some
> revision. This has two major wins over the current+reverse diffs
> format used by RCS. First, all revisions take the same time to
> extract, and you do not have to edit the working file in memory. A
> single linear scan over the archive file, selecting lines and writing
> them out, suffices. This is particularly desirable if you have many
> branches. Second, it provides the concept of included and excluded
> deltas, which let you do many merge operations just by adding an entry
> to the file index - no modification to the archive is needed.
>
> The trouble with the weave algorithm is it's line oriented and
> therefore won't play nice with vcdiff. SCCS itself handles binary
> files horribly (it uuencodes them and then tries to diff the results,
> yuck). But SCCS' real problem with binaries is it uses \n\001 as an
> escape sequence. You could trivially avoid that, and with a bit more
> effort I bet weave could be made to work on arbitrary byte runs
> instead of lines.
>
> zw
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> "Jonathan S. Shapiro" <sh...@eros-os.org> writes:
> > Where do you see the efficiency issue? I'm clearly missing something.
>
> When you update a subdirectory, I think.
There are two reasons to do localized updates: performance and intent. The
performance rationale is always a bad one, and reflects the need to work
around a deficiency in the tool. The intent case is important.
Let me describe how this is handled in DCMS and I think it will be apparent
that there isn't a performance issue in selective update.
DCMS keeps a file on the client side that describes the state of the
workspace. This file contains, for each object (in this case for each file)
the SHA-1 hash of that file. When I type:
dcms update
the default behavior is to find the "top" of the workspace and update
everything in the workspace. That is, commands are presumed to be about the
workspace, not about the current directory.
The user agent checks to see if a new branch exists. If so, it does a
three-way merge between the new branch, the branch I had checked out, and
the current state of the workspace. The time consuming part of this is
downloading the file that describes the new branch, not identifying the
triples for the merge.
Because the workspace file contains the SHA-1 hash of each file as of the
time it was checked out, identifying the files that are locally changed
requires no communication with the server. I was initially concerned about
the expense of recomputing the checksums, but it's a non-issue. The "dcms
status" command (which is essentially what is being done here) is very fast,
and can be done offline.
If you want selective update, you state the directory name (or the file
name). In that case, the update is restricted to those files whose fsName
matches the pattern on the command line. It's purely a "glob" style match,
and requires no remote communication.
If you have enough entities in the workspace that checking their names is a
serious performance bottleneck, it seems likely that the pattern match isn't
where the performance problem is :-)
In the "laptop" case, there is an additional issue, which is that we assume
there is a repository on the laptop that is a partial clone of some
"official" repository. Think of it as a cache. The new branch is downloaded
through it, as are any changed entities. Note that because cryptographic
hashes are used as an internal naming mechanism it is never necessary to
download material that you already have.
shap
Re: [subversion-dev] Subversion design document up
Posted by Karl Fogel <kf...@galois.collab.net>.
"Jonathan S. Shapiro" <sh...@eros-os.org> writes:
> Where do you see the efficiency issue? I'm clearly missing something.
When you update a subdirectory, I think.
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> Our starting point was that there's nothing wrong with the CVS model
> (in which directories are indeed first-class objects in the
> repository, although not versioned enough unfortunately).
They are indeed first-class. In some sense my question is whether this is a
bug or a feature. I can make a case both ways, but I claim that in the
majority of situations the containership model isn't what I want to use to
capture the *intent* of the workspace.
> CVS is -- well, wants to be -- a system for versioning directory
> trees. This may be less general than versioning arbitrary namespaces,
> but who's to say we'd make the right "cuts" if we tried to cover many
> models instead of one model... Versioning directory trees is a very
> useful thing, even if not the only thing.
This argument sounds a bit backwards to me. It seems to me that if I want
confidence that I'm doing the right "cuts" then I want to have a general
model for versioning namespaces in which the case of explicitly directories
is merely one case. I might or might not implement the general model, but
I'ld start there.
> We did consider a scheme exactly like the one you describe, where the
> directory hierarchy is implicit in the names, and much pattern
> matching happens. We decided against it for efficiency reasons.
That's interesting, because I *adopted* the approach I did for efficiency
reasons. The pattern matching case is exceptionally rare. In practice, it is
almost always of the form "take things matching this leading substring from
that branch and version". However, it's almost never done.
The reason I did NOT do directories as first class objects is that I wanted
an updated version of a file to result in modification to only one "content"
object in the repository (as opposed to a metadata object such as the object
that holds the members of a given configuration). Part of the reason is that
I wanted the system to be robust in the fact of connection failure. In DCMS,
it should be possible to get halfway through the upload of a commit
consisting of several new file states, lose the connection before making it
to the closing transaction (actually a compare and swap), and restart
without needing to upload the successfully transferred files again. If
directories need to be updated, then we face the problem of not knowing what
state they are in when this line loss occurs, given which it seems that we
sort of have to assume that they are all wrong and upload them all again. I
decided that directories were emergent rather than essential, and ditched
directories.
It's clear that DCMS is going to need a container model. It's just not clear
how widely it should be used in the versioning logic.
Where do you see the efficiency issue? I'm clearly missing something.
Re: [subversion-dev] Subversion design document up
Posted by Karl Fogel <kf...@galois.collab.net>.
Our starting point was that there's nothing wrong with the CVS model
(in which directories are indeed first-class objects in the
repository, although not versioned enough unfortunately). So our goal
is "Make it like CVS, but with all the bugs fixed."
CVS is -- well, wants to be -- a system for versioning directory
trees. This may be less general than versioning arbitrary namespaces,
but who's to say we'd make the right "cuts" if we tried to cover many
models instead of one model... Versioning directory trees is a very
useful thing, even if not the only thing.
We did consider a scheme exactly like the one you describe, where the
directory hierarchy is implicit in the names, and much pattern
matching happens. We decided against it for efficiency reasons.
-K
"Jonathan S. Shapiro" <sh...@eros-os.org> writes:
> I want to ask a (perhaps naive) question about how the subversion design
> handles directories. It's different from the design for DCMS, and I'ld like
> to understand the pros and cons of the respective designs.
>
> In subversion, it appears that each directory is a container object, and
> that there is an object in the repository representing the directory. In
> many respects, this seems quite natural, but it introduces the need to
> update multiple objects atomically when performing a check-in, which is what
> originally led me away from it.
>
> In DCMS, the only objects that exist in the repository in the usual case are
> the "leaf" objects -- i.e. the files. A branch version consists of a set of
> (fsName, repositoryName) pairs [plus some other gorp]. The directory
> structure is implicit in the fsName, and containing directories are created
> as necessary during checkout. The convention about the implicit creation of
> directories in the workspace is that this part of the checkout semantics is
> purely the responsibility of the user agent.
>
> This reflects the following assumptions:
>
> 1. In general, the directory structure of the source tree exists purely to
> provide containership; most of the time there is no semantic content to the
> permissions or ownership of these directories, and indeed most of the time
> we would like these things to be determined by the developer's environment,
> not the CM system.
>
> 2. In the exceptional case, it may be desirable to have leaf directories. In
> such cases we can add entries for them.
>
> 3. Files are not the only thing we may wish to handle, and it is undesirable
> to build into the name binding mechanism any implicit assumption that the
> developer namespace is a file name space as opposed to (e.g.) a class name
> space.
>
> A disadvantage to the DCMS approach is that you cannot refer easily to "the
> current state of a given directory and it's descendants". My personal
> feeling is that this is a problem for which pattern matching is a better
> solution, but the "container+descendants" thing is something that many
> people seem to feel is important.
>
> So finally my question: is there any reason at all for directories to exist
> as independent entities? Aren't they just an accident of the namespace
> conventions of the development environment? What advantage is obtained by
> representing them explicitly?
>
>
> shap
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
I want to ask a (perhaps naive) question about how the subversion design
handles directories. It's different from the design for DCMS, and I'ld like
to understand the pros and cons of the respective designs.
In subversion, it appears that each directory is a container object, and
that there is an object in the repository representing the directory. In
many respects, this seems quite natural, but it introduces the need to
update multiple objects atomically when performing a check-in, which is what
originally led me away from it.
In DCMS, the only objects that exist in the repository in the usual case are
the "leaf" objects -- i.e. the files. A branch version consists of a set of
(fsName, repositoryName) pairs [plus some other gorp]. The directory
structure is implicit in the fsName, and containing directories are created
as necessary during checkout. The convention about the implicit creation of
directories in the workspace is that this part of the checkout semantics is
purely the responsibility of the user agent.
This reflects the following assumptions:
1. In general, the directory structure of the source tree exists purely to
provide containership; most of the time there is no semantic content to the
permissions or ownership of these directories, and indeed most of the time
we would like these things to be determined by the developer's environment,
not the CM system.
2. In the exceptional case, it may be desirable to have leaf directories. In
such cases we can add entries for them.
3. Files are not the only thing we may wish to handle, and it is undesirable
to build into the name binding mechanism any implicit assumption that the
developer namespace is a file name space as opposed to (e.g.) a class name
space.
A disadvantage to the DCMS approach is that you cannot refer easily to "the
current state of a given directory and it's descendants". My personal
feeling is that this is a problem for which pattern matching is a better
solution, but the "container+descendants" thing is something that many
people seem to feel is important.
So finally my question: is there any reason at all for directories to exist
as independent entities? Aren't they just an accident of the namespace
conventions of the development environment? What advantage is obtained by
representing them explicitly?
shap
Re: [subversion-dev] Re: SCCS vs RCS
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> The version I worked on is (finally!) available in public beta from
> bitkeeper.com.
Terrific! Any chance that it will also be made available under an open
source license? I'm not interested in debating the Bitkeeper license.
Whether you think it good, bad, or indifferent, it has not yet established
broad acceptance within the community. For DCMS we have decided to stick to
GPL and compatible licenses.
shap
Re: [subversion-dev] Re: SCCS vs RCS
Posted by Zack Weinberg <za...@wolery.cumb.org>.
On Mon, Jun 05, 2000 at 12:43:50PM -0400, Jonathan S. Shapiro wrote:
> > We ran tests...
> > I'll believe that the original SCCS was slower than RCS after a few
> > hundred deltas, but only because the implementation was lame.
>
> Hmm. That's actually tremendously useful to know, and thank you. Is there an
> implementation of SCCS these days that is not lame?
The version I worked on is (finally!) available in public beta from
bitkeeper.com.
zw
Re: SCCS vs RCS
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> We ran tests...
> I'll believe that the original SCCS was slower than RCS after a few
> hundred deltas, but only because the implementation was lame.
Hmm. That's actually tremendously useful to know, and thank you. Is there an
implementation of SCCS these days that is not lame?
shap
Re: [subversion-dev] Subversion design document up
Posted by Bill Frantz <fr...@communities.com>.
At 08:31 PM 6/7/00 -0400, Jonathan S. Shapiro wrote:
>> I like the idea of the SHA-1 hashes for a binary repository very much.
>> I'm
>> not sure that it applies as neatly to a "human readable" repository,
>> where
>> easily identifiable file names/objects would make debugging a hell of a
>> lot
>> easier.
>
>You are right. In building a replicatable repository, it is necessary to
>construct an object name space that does not have collisions.
>Human-generated names don't satisfy this requirement. For subversion, this
>is not an immediate objective, but I wonder if it wouldn't be useful to
>ponder briefly how replication would eventually be implemented in order to
>ensure that the repository name space isn't a problem.
>
>You may be emphasizing the debugging problem unduly. Given the structure of
>the DCMS repository, it is very easy to write a script that will tell you,
>for each reachable object in the repository, the branch, version, and file
>name of that object. That is, a repository browser just isn't that hard to
>build, and in light of this the advantages of universally unique names
>seemed compelling.
>
>Independent of the merits of SHA hashes, it's useful to have the object name
>space and the workspace name space be different. There is no inherent reason
>to believe that the most convenient storage of objects in the repository
>naturally follows from the history of the development. Also, a level of
>indirection at this place in the architecture appears necessary to do a good
>job on rename.
We are playing with a similar system. Two points:
* We are currently using symbolic links to link the human-readable name to
the hashed file. A one-to-many linking structure would be better.
* MacOS (before 9) only supports 31 character names. We use a 5 bit per
character code for representing the binary names, which results in 32
characters for SHA1. Truncating one character might not be a problem, but
we chose to use MD5 instead, leaving room for a reasonable file extension.
(We will need extensions for Windows in our application.)
Cheers - Bill
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> I like the idea of the SHA-1 hashes for a binary repository very much.
> I'm
> not sure that it applies as neatly to a "human readable" repository,
> where
> easily identifiable file names/objects would make debugging a hell of a
> lot
> easier.
You are right. In building a replicatable repository, it is necessary to
construct an object name space that does not have collisions.
Human-generated names don't satisfy this requirement. For subversion, this
is not an immediate objective, but I wonder if it wouldn't be useful to
ponder briefly how replication would eventually be implemented in order to
ensure that the repository name space isn't a problem.
You may be emphasizing the debugging problem unduly. Given the structure of
the DCMS repository, it is very easy to write a script that will tell you,
for each reachable object in the repository, the branch, version, and file
name of that object. That is, a repository browser just isn't that hard to
build, and in light of this the advantages of universally unique names
seemed compelling.
Independent of the merits of SHA hashes, it's useful to have the object name
space and the workspace name space be different. There is no inherent reason
to believe that the most convenient storage of objects in the repository
naturally follows from the history of the development. Also, a level of
indirection at this place in the architecture appears necessary to do a good
job on rename.
shap
Re: [subversion-dev] Subversion design document up
Posted by "Daniel L. Rall" <dl...@collab.net>.
> > I'm glad to hear you agree with me that strong checksums are necessary.
> I'd
> > settle for CRC or adler32, but SHA sure would be nice.
>
> I'm not using checksums. I'm using cryptographic hashes. The difference is
> significant. CRCs and adler32's provide a good means of integrity checking,
> but they collide too frequently to serve as *names*. In the DCMS repository,
> the "repository name" of an object *is* its SHA-1 hash. One effect of this
> is to greatly simplify transaction and replication handling.
I like the idea of the SHA-1 hashes for a binary repository very much.
I'm
not sure that it applies as neatly to a "human readable" repository,
where
easily identifiable file names/objects would make debugging a hell of a
lot
easier.
--
Daniel Rall <dl...@collab.net>
http://collab.net/ | open source | do the right thing
Re: [subversion-dev] Subversion design document up
Posted by Greg Stein <gs...@lyra.org>.
On Tue, Jun 06, 2000 at 06:27:04PM -0400, Jonathan S. Shapiro wrote:
>...
> > I'm glad to hear you agree with me that strong checksums are necessary.
> > I'd settle for CRC or adler32, but SHA sure would be nice.
>
> I'm not using checksums. I'm using cryptographic hashes. The difference is
> significant. CRCs and adler32's provide a good means of integrity checking,
> but they collide too frequently to serve as *names*. In the DCMS repository,
> the "repository name" of an object *is* its SHA-1 hash. One effect of this
> is to greatly simplify transaction and replication handling.
Ooh. That is a spiffy idea. If you're computing SHA1 hashes anyhow (for
integrity and robustness), then yah... it does provide a unique value.
(well, as much as any 160-bit random value can be called "unique" :-)
I'm not entirely sure that I would want to depend on that, however. One
chance in a bazillion and you (effectively) have a corrupted DB. There
really ought to be another key-portion in there.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> ... I will say that you seem to be using a stricter
> definition of 'text' than me. When I say 'text' I mean simply 7-bit
ASCII,
> no control characters. In particular, it would be perfectly fine to
insist
> on Unix-style line endings...
This relates to somebody else's comments on possibly using MIME types, so
let me expand on my view of this in case it's helpful down the road.
I see a CM system as having a number of layers. At the bottom, it manages a
bunch of objects purely in terms of bits. It's job is to get a consistent
set of bit-bundles to the next layer up. At this layer, I feel there should
be no interpretation of content, and consequently no typing. This is why I
want a (conceptually) binary-only repository. My one exception to the "no
interpretation" is that the repository at this layer is free to use
compressed representations as a matter of internal storage convenience. Such
compression should not (in principle) be externally visible -- not least
because making it visible screws up delta handling.
At the next conceptual layer up there is some input and output filtering
that needs to happen. This handles things like newline canonicalization and
variable expansion. To my mind, the execution of such filters is the job of
the user agent. The repository server shouldn't have anything to do with it.
At the level of MIME types, we run into a couple of problems. First, there
isn't a good way to reliably extract MIME types from content or fsName of an
object. We can use heuristics, but ultimately this is the kind of thing that
wants to be stored as a per-object attribute somewhere. I think the idea of
being able to record MIME types and use them to drive things like
visualizers is cool, but I think it's none of the repository's business.
This attribution is purely a convention between the user agents. The
repository's role is merely to store the attribute(s) along with the object.
After a while, I concluded that the "type" of an object at the repository
level consists of the set of trigger behaviors that the object exhibits in
response to configuration actions (e.g. checkout, commit). This is different
from the type of the content, though the two will in practice be closely
related. The previously mentioned filters are an example of such triggers.
But consider this (real) example: I have one source tree that contains an
autorun.inf file for a CD. This file is (to all appearances) a text file,
but it must be preserved in MS newline format, even when used on a UNIX
system. This doesn't change it's MIME type at all.
So I basically think that the notion of "type" is quite complicated. One
goal for DCMS is to have a platform-independent scripting language that lets
triggers be written which behave the same on all platforms.
Sorry if this seems slightly disjointed -- my attention is divided at the
moment.
> I'm glad to hear you agree with me that strong checksums are necessary.
I'd
> settle for CRC or adler32, but SHA sure would be nice.
I'm not using checksums. I'm using cryptographic hashes. The difference is
significant. CRCs and adler32's provide a good means of integrity checking,
but they collide too frequently to serve as *names*. In the DCMS repository,
the "repository name" of an object *is* its SHA-1 hash. One effect of this
is to greatly simplify transaction and replication handling.
> Incidentally, where can I find more information about your DCMS?
There is a mailing list: dcms-dev@eros-os.org. At the moment there is no
design document, though I am in the process of drafting one. Version 0.1 is
still in progress.
Re: [subversion-dev] Subversion design document up
Posted by Zack Weinberg <za...@wolery.cumb.org>.
On Mon, Jun 05, 2000 at 12:57:59PM -0400, Jonathan S. Shapiro wrote:
> > > We have a significant disagreement here. In my opinion, the archive file
> > > format is the business of the archive, and it's none of the user's
> business
> > > whether that format is binary, ascii, or morse code.
> >
> > I agree with the first half of that sentence but not the second. It
> > is the user's business. Why? Most obviously, because the repository
> > *will* get corrupted. Not because of filesystem or disk problems, but
> > because of bugs in the VC system. It is infinitely easier to debug a
> > text file.
>
> First, let me say that I agree with you -- the VC system definitely will
> corrupt things on occasion, and recoverability is a serious concern. I'm not
> altogether convinced that text formats make recoverability inherently
> easier. I think that it depends alot on the complexity of the file format.
> In the DCMS case the file format is simple enough that I'm not much
> concerned about software-generated corruption errors in the metadata, and I
> don't really expect that binary vs. text will have much of an impact on
> errors in the content.
>
> That said, let me add that I went for binary format for exactly the reason
> that you prefer ascii: concern about corruption. My experience suggests that
> the software is only the *second* most likely source of corruption.
> Corruption most commonly comes from having users who think they know what is
> going on edit things that they shouldn't touch. Binary formats tend to
> discourage this, and eliminate the need to deal with unpredictable string
> length management in the lexer (which in turn eliminates a major class of
> bugs). Also, binary formats eliminate the need for all of the programs to be
> neutral to line-end conventions. Finally, binary formats eliminate the need
> for a layer of canonicalization rules that must be applied to generate
> reproducible cryptographic hashes.
All these are fair points. I will say that you seem to be using a stricter
definition of 'text' than me. When I say 'text' I mean simply 7-bit ASCII,
no control characters. In particular, it would be perfectly fine to insist
on Unix-style line endings, or design the file such that you always know
how long the strings are -- I agree that's a major class of bugs it would be
nice to avoid. It doesn't have to be particularly human-readable either.
I'm glad to hear you agree with me that strong checksums are necessary. I'd
settle for CRC or adler32, but SHA sure would be nice.
The main reason I'm leery of binary files is that when they get mangled, the
dump utility usually can't cope any better than the real programs can, and
you wind up grovelling through hex dumps. But with a sufficiently robust
file format it might be possible to avoid that...
Incidentally, where can I find more information about your DCMS?
> > A secondary but still important reason is that a text file can be
> > embedded in email with no special care...
>
> I've seen enough mailers mangle enough text in enough creative ways that I
> would file this claim under "plausible, but falsified by bitter experience."
Good point.
> Independent of that, I question the wisdom of using email as a transport for
> this sort of thing -- large emails don't survive modem line loss rates, and
> small emails don't lend themselves to ensuring consistency across
> collections of changes.
I'm mainly concerned with being able to mail a short (less than a few hundred
lines, no major file juggling) patch to a client, in a format that they can
inspect visually before they do anything with it. Context diffs do this
reasonably well; whatever we come up with should be no worse.
> Please understand: I don't dispute the merit of a text representation. I've
> just made a different engineering choice and I thought it might have value
> to articulate some of why I did this.
I do understand. Thanks for explaining so thoroughly.
zw
Re: [subversion-dev] Subversion design document up
Posted by "Daniel L. Rall" <dl...@finemaltcoding.com>.
> Please understand: I don't dispute the merit of a text representation. I've
> just made a different engineering choice and I thought it might have value
> to articulate some of why I did this.
I really enjoyed hearing your argument Jonathan--you made very good
points. Regardless of which way SVN implementation goes, I find input
like that is valuable. :)
--
Daniel Rall <dl...@finemaltcoding.com>
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> > We have a significant disagreement here. In my opinion, the archive file
> > format is the business of the archive, and it's none of the user's
business
> > whether that format is binary, ascii, or morse code.
>
> I agree with the first half of that sentence but not the second. It
> is the user's business. Why? Most obviously, because the repository
> *will* get corrupted. Not because of filesystem or disk problems, but
> because of bugs in the VC system. It is infinitely easier to debug a
> text file.
First, let me say that I agree with you -- the VC system definitely will
corrupt things on occasion, and recoverability is a serious concern. I'm not
altogether convinced that text formats make recoverability inherently
easier. I think that it depends alot on the complexity of the file format.
In the DCMS case the file format is simple enough that I'm not much
concerned about software-generated corruption errors in the metadata, and I
don't really expect that binary vs. text will have much of an impact on
errors in the content.
That said, let me add that I went for binary format for exactly the reason
that you prefer ascii: concern about corruption. My experience suggests that
the software is only the *second* most likely source of corruption.
Corruption most commonly comes from having users who think they know what is
going on edit things that they shouldn't touch. Binary formats tend to
discourage this, and eliminate the need to deal with unpredictable string
length management in the lexer (which in turn eliminates a major class of
bugs). Also, binary formats eliminate the need for all of the programs to be
neutral to line-end conventions. Finally, binary formats eliminate the need
for a layer of canonicalization rules that must be applied to generate
reproducible cryptographic hashes.
In the end, I'm less concerned about the file damage being recoverable then
I am about ability to detect corruption to the file. I'm more concerned
about having sufficient redundancy in the repository metadata that it can be
successfully reconstructed when things like directories have been lost.
> A secondary but still important reason is that a text file can be
> embedded in email with no special care...
I've seen enough mailers mangle enough text in enough creative ways that I
would file this claim under "plausible, but falsified by bitter experience."
Independent of that, I question the wisdom of using email as a transport for
this sort of thing -- large emails don't survive modem line loss rates, and
small emails don't lend themselves to ensuring consistency across
collections of changes. While there is need for human-readable patches, I
think that it's possible to build better tools than the ones we are using
today. I'm trying to do so, and we'll just have to see how it works out in
practice. I may be quite wrong about whether the tools I have in mind are
"better" in the field.
> You're confusing treating all files the same with storing the metadata
> in binary. It is easy to treat all files the same and still store the
> metadata as text.
Depends on how the metadata is stored. Some of the metadata should be stored
in the repository with the object itself, for exactly the reasons of
recoverability that you mention. In that case, it's format tends to be
dictated by the object format.
I suppose the bottom line is that I have more confidence in my ability to
get serialization and deserialization right in binary form, where I can
semi-rely on the fact that the user hasn't dicked with things. Also, I'm
relying on cryptographic hashes for naming, and I really want to avoid the
need to read an ascii form, canonicalize the resulting object structure, and
then compute a hash on something that isn't the persistent representation.
Please understand: I don't dispute the merit of a text representation. I've
just made a different engineering choice and I thought it might have value
to articulate some of why I did this.
shap
Re: [subversion-dev] Subversion design document up
Posted by Zack Weinberg <za...@wolery.cumb.org>.
On Mon, Jun 05, 2000 at 07:58:27AM -0400, Jonathan S. Shapiro wrote:
> > On Sun, Jun 04, 2000 at 11:08:29AM -0400, Jonathan S. Shapiro wrote:
> > > The SCCS storage format isn't terribly efficient. Actually, it's famous
> for
> > > having sucky performance.
> >
> > I am certain this is an artifact of the implementation.
>
> Actually, it's the nature of the file format. RCS stores the most recent
> version with deltas to get to old versions. SCCS stores the original and
> requires that all deltas be re-applied on each checkout (and checkin, for
> that matter). The SCCS file format is a bit cleaner, but after 100 deltas or
> so it's a profound loose.
This is not true. It stores all the versions sort of mixed together.
As I said in the original message, it takes the same time to extract
*any* revision, and that time is always the same or better than RCS,
if implemented properly. We ran test repositories with 10,000 deltas
in a file and it was still faster than RCS.
I'll believe that the original SCCS was slower than RCS after a few
hundred deltas, but only because the implementation was lame.
> > I remember being annoyed at some version of PRCS because
> > the archives were always binary... In my opinion, if the data
> > stored in the file is 7-bit ASCII, the entire archive file should
> > be 7-bit ASCII.
>
> We have a significant disagreement here. In my opinion, the archive file
> format is the business of the archive, and it's none of the user's business
> whether that format is binary, ascii, or morse code.
I agree with the first half of that sentence but not the second. It
is the user's business. Why? Most obviously, because the repository
*will* get corrupted. Not because of filesystem or disk problems, but
because of bugs in the VC system. It is infinitely easier to debug a
text file.
A secondary but still important reason is that a text file can be
embedded in email with no special care. If you have a binary file,
you are forced to use MIME or uuencode. This is less important for
the archive files - but I've done tech support for VC, and it was a
great help to be able to ask someone to email me the problem s.file
without needing to explain MIME. It is essential for patches; emailed
distribution of patches _in human readable format_ is central to just
about everyone's development process. Now that format doesn't
necessarily need to be the same as the format used in the update
protocol, but wouldn't it be simpler to have just one?
> A binary convention within the repository actually simplifies things, as the
> server side of the repository system ceases to be conditioned on file type,
> which has proven a useful simplifcation for my stuff.
You're confusing treating all files the same with storing the metadata
in binary. It is easy to treat all files the same and still store the
metadata as text.
zw
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
> On Sun, Jun 04, 2000 at 11:08:29AM -0400, Jonathan S. Shapiro wrote:
> > The SCCS storage format isn't terribly efficient. Actually, it's famous
for
> > having sucky performance.
>
> I am certain this is an artifact of the implementation.
Actually, it's the nature of the file format. RCS stores the most recent
version with deltas to get to old versions. SCCS stores the original and
requires that all deltas be re-applied on each checkout (and checkin, for
that matter). The SCCS file format is a bit cleaner, but after 100 deltas or
so it's a profound loose.
> Xdelta's big claim to fame was handling
> binary files efficiently, yes?
I think you may be confusing xdelta with vdelta, but in any case yes: xdelta
is more efficient.
> I remember being annoyed at some version of PRCS because
> the archives were always binary... In my opinion, if the data
> stored in the file is 7-bit ASCII, the entire archive file should
> be 7-bit ASCII.
We have a significant disagreement here. In my opinion, the archive file
format is the business of the archive, and it's none of the user's business
whether that format is binary, ascii, or morse code. My feeling is that the
right way to handle text files is to introduce the notion of
inbound/outbound filters. The inbound filter canonicalizes the newline
convention and (if appropriate) removes variable expansions. The outbound
filter expands variables and converts everything to client-normal form.
While the CM system must keep track of what filters are required for each
file, it has no need (and indeed no business) being able to manipulate those
files while in the repository itself.
A binary convention within the repository actually simplifies things, as the
server side of the repository system ceases to be conditioned on file type,
which has proven a useful simplifcation for my stuff.
shap
Re: [subversion-dev] Subversion design document up
Posted by Zack Weinberg <za...@wolery.cumb.org>.
On Sun, Jun 04, 2000 at 11:08:29AM -0400, Jonathan S. Shapiro wrote:
> The SCCS storage format isn't terribly efficient. Actually, it's famous for
> having sucky performance.
I am certain this is an artifact of the implementation. I used to
work for a source control firm, whose product was based on the SCCS
file format. Both archive size and time to extract were always equal
to or better than local RCS. Time to check in a new version was
occasionally a bit slower than local RCS, but that was an artifact of
*that* implementation, and in any case checkin time is not nearly as
important.
> An alternative to consider is Josh McDonald's xdelta/xdfs.
I'm not familiar with these. Xdelta's big claim to fame was handling
binary files efficiently, yes? I remember being annoyed at some
version of PRCS because the archives were always binary - not just
because of the compression, either. In my opinion, if the data stored
in the file is 7-bit ASCII, the entire archive file should be 7-bit
ASCII. (With an option to compress the entire file on the fly.)
zw
Re: [subversion-dev] Subversion design document up
Posted by Greg Stein <gs...@lyra.org>.
On Sun, 4 Jun 2000, Jonathan S. Shapiro wrote:
> The SCCS storage format isn't terribly efficient. Actually, it's famous for
> having sucky performance. An alternative to consider is Josh McDonald's
> xdelta/xdfs.
Karl has called dibs on implementing the delta management :-) ... he is
looking at xdelta and at vdelta.
Dunno what xdfs is, tho... off to look it up :-)
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: [subversion-dev] Subversion design document up
Posted by "Jonathan S. Shapiro" <sh...@eros-os.org>.
The SCCS storage format isn't terribly efficient. Actually, it's famous for
having sucky performance. An alternative to consider is Josh McDonald's
xdelta/xdfs.
shap
Re: [subversion-dev] Subversion design document up
Posted by Zack Weinberg <za...@wolery.cumb.org>.
On Sat, Jun 03, 2000 at 02:03:11PM -0700, Zack Weinberg wrote:
...
> For storing file data, I'd recommend looking at the "weave" algorithm
> used by SCCS.
This algorithm should be described in:
Marc J. Rochkind. The Source Code Control System. IEEE Transactions
on Software Engineering, SE-1(4): 364-370, December 1975
Unfortunately, if IEEE has it online, they want you to pay for it. :(
zw