You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@subversion.apache.org by Jim Blandy <ji...@zwingli.cygnus.com> on 2001/03/05 22:13:49 UTC
getting nodes by ID
DAV wants to be able to retrieve nodes by DAV-ID. This DAV-ID doesn't
have to be a Subversion FS node revision ID --- it can be any
arbitrary string of bytes such that:
1) if two nodes' DAV-ID's are equal, their contents are equal, and
2) it's reasonably fast to retrieve a node given a DAV-ID.
The idea, I think, is that when you ask for the contents of a
directory, you'd get back a list of (name, DAV-ID) pairs, and then you
could retrieve the contents you were interested in by DAV-ID. A
caching proxy would use DAV-ID's to recognize text it had seen before.
So we should add the following property:
3) As often as possible, if a node's contents have not changed, its
DAV-ID shouldn't change.
The first idea was that we'd simply use filesystem node revision ID's
as DAV-ID's. That certainly meets the requirements above. But that
won't work, because the filesystem can't tell whether you are
authorized to access a file without knowing the path through which you
reached it --- if you don't have permission to read some parent
directory, you shouldn't be able to read its contents, no matter what
the permissions are on them. So we need to add:
4) Given a DAV-ID, there must be a quick way to determine whether the user
is authorized to access the node.
The next suggestion was to use a pair (PATH, NODE-REV-ID). But PATH
is useless without a revision or transaction whose root we can start
from. The database isn't indexed to quickly answer questions like "in
what revisions does PATH refer to NODE-REV_ID?" (I think such an
index would completely duplicate the directory structure, unless
someone thinks of something clever.)
Another possibility would be to use a pair (REV, PATH), where REV is
the oldest revision in which PATH refers to the node we want. This
satisfies all four properties, but there's no quick way to choose the
right REV, without trying them all. Since the "oldest" part is only
necessary to satisfy condition 3), we can relax it a bit to "the
oldest revision we can find". But this is still a mess. We're doing
an unbounded number of path traversals in the database. So we need to
clarify:
5) It should be quick to compute a suitable DAV-ID for each node as we
traverse the filesystem.
Would it be possible to change DAV to remove condition 2)? That is,
can we use DAV-ID's to notice cache hits, but supply extra information
to get the real thing when we miss? That way, we could use node
revision ID's for DAV-ID's, but also supply a (ROOT, PATH) pair that
could be looked up easily.
Also, it seems to me like the problems we're having in implementing
this aren't really unique to Subversion. Can you show us a system
where DAV-ID's are easy to implement, with all the desireable
properties? For example, what if I'm implementing DAV on CVS --- what
kind of DAV-ID would you use there? You could use (PATH, RCS-NUMBER),
but only because CVS doesn't really allow you to delete directories,
or support renaming. I guess I'm beginning to wonder if this isn't a
half-baked idea in general, not just a problematic case for
Subversion.
Re: getting nodes by ID
Posted by Karl Fogel <kf...@galois.collab.net>.
Jim Blandy <ji...@zwingli.cygnus.com> writes:
> DAV wants to be able to retrieve nodes by DAV-ID. This DAV-ID doesn't
> have to be a Subversion FS node revision ID --- it can be any
> arbitrary string of bytes such that:
> 1) if two nodes' DAV-ID's are equal, their contents are equal, and
> 2) it's reasonably fast to retrieve a node given a DAV-ID.
Requirement (1) is not only useful for DAV, it is useful for users as
well -- it's essentially the per-file "change number" we've talked a
bit about in the past.
In CVS, the revision numbers naturally have this property, and it's
really handy. Two people can quickly establish that they have the
same file contents just by comparing revision numbers (assuming no
local mods).
SVN revision numbers are different, of course. I could have revision
12 of foo.c, you could have revision 363, and yet the file might be
the same in those two revisions. If each file tracked which commits
affected it, or stored a number indicating how many times it had been
committed, then people would have this information as conveniently in
Subversion as in CVS.
I'm not sure yet how this affects Jim's points below, I just thought
it worth mentioning early.
-K
> The idea, I think, is that when you ask for the contents of a
> directory, you'd get back a list of (name, DAV-ID) pairs, and then you
> could retrieve the contents you were interested in by DAV-ID. A
> caching proxy would use DAV-ID's to recognize text it had seen before.
> So we should add the following property:
>
> 3) As often as possible, if a node's contents have not changed, its
> DAV-ID shouldn't change.
>
> The first idea was that we'd simply use filesystem node revision ID's
> as DAV-ID's. That certainly meets the requirements above. But that
> won't work, because the filesystem can't tell whether you are
> authorized to access a file without knowing the path through which you
> reached it --- if you don't have permission to read some parent
> directory, you shouldn't be able to read its contents, no matter what
> the permissions are on them. So we need to add:
>
> 4) Given a DAV-ID, there must be a quick way to determine whether the user
> is authorized to access the node.
>
> The next suggestion was to use a pair (PATH, NODE-REV-ID). But PATH
> is useless without a revision or transaction whose root we can start
> from. The database isn't indexed to quickly answer questions like "in
> what revisions does PATH refer to NODE-REV_ID?" (I think such an
> index would completely duplicate the directory structure, unless
> someone thinks of something clever.)
>
> Another possibility would be to use a pair (REV, PATH), where REV is
> the oldest revision in which PATH refers to the node we want. This
> satisfies all four properties, but there's no quick way to choose the
> right REV, without trying them all. Since the "oldest" part is only
> necessary to satisfy condition 3), we can relax it a bit to "the
> oldest revision we can find". But this is still a mess. We're doing
> an unbounded number of path traversals in the database. So we need to
> clarify:
>
> 5) It should be quick to compute a suitable DAV-ID for each node as we
> traverse the filesystem.
>
> Would it be possible to change DAV to remove condition 2)? That is,
> can we use DAV-ID's to notice cache hits, but supply extra information
> to get the real thing when we miss? That way, we could use node
> revision ID's for DAV-ID's, but also supply a (ROOT, PATH) pair that
> could be looked up easily.
>
> Also, it seems to me like the problems we're having in implementing
> this aren't really unique to Subversion. Can you show us a system
> where DAV-ID's are easy to implement, with all the desireable
> properties? For example, what if I'm implementing DAV on CVS --- what
> kind of DAV-ID would you use there? You could use (PATH, RCS-NUMBER),
> but only because CVS doesn't really allow you to delete directories,
> or support renaming. I guess I'm beginning to wonder if this isn't a
> half-baked idea in general, not just a problematic case for
> Subversion.
Re: getting nodes by ID
Posted by Greg Stein <gs...@lyra.org>.
On Mon, Mar 12, 2001 at 11:46:22PM -0500, Jim Blandy wrote:
>
> (Is there a better term than DAV-ID? I'm happy to use the real DAV
> terminology, but I don't know what it is.)
There isn't a term for it. We are using a "DAV-ID" as a component of a
Version Resource URL (VR URL). The latter is our goal, and as long as the
URL retrieves a resource, it should retrieve exactly the same resource. I
don't think we want to have a VR that disappears in normal operation. That
capability is present for version control systems that delete (intermediate)
versions; we might use it when we archive old revisions, and remove them
from the repository. But in normal operation, a VR URL will always exist and
always point to the same thing.
The problem that we're seeing is that a VR URL which just uses an (ID, PATH)
pair can be insufficient for ACL processing (because we don't know which
root to use with PATH).
>...
> At the moment, there's a requirement that a DAV-ID alone is sufficient
> to efficiently retrieve a node: a request can just take a DAV-ID and
> hand you back its contents, quickly.
>
> What if we changed that rule so that the DAV-ID alone was sufficient
> to check identity --- "Okay, this file you've asked for is the same as
> one I've already got" --- but you need additional information to
> actually get the file, if the identities don't match. Then we could
> use node revision ID's as DAV-ID's --- if two node revision ID's are
> identical, then you've got a cache hit --- and supply a (REV,PATH)
> pair for retrieval. So you haven't lost condition 1.1 ("if their
> contents are equal(*), their DAV-IDs are equal."), since you're only
> comparing node revision ID's.
The VR URL is the thing used for retrieving the resource. The importance of
identity is twofold: 1) the client knows the VR URL for the resource in the
WC, so it can easily determine whether a new VR URL identifies a new one
resource (which needs to be fetched); 2) a cache uses a URL as a key, so
stability in the URL improves caching (where identity means the contents are
the same).
I think what you're saying is that we have two URLs. One that isn't really
used for fetching, but acts as an way to check identity. Another to actually
perform the fetch. The fetching URL would blow off caching because it
includes REV in the URL.
And to recap: if a resource doesn't change between revisions 3 and 4, we
want the client and any caches to keep their contents. Since these are keyed
by the URL, any change in the URL (s/3/4/) is going to cause a refetch or a
cache miss.
> > > Also, it seems to me like the problems we're having in implementing
> > > this aren't really unique to Subversion. Can you show us a system
> > > where DAV-ID's are easy to implement, with all the desireable
> > > properties?
> >
> > A table mapping UUIDs to (REV, PATH) pairs.
To clarify the above: I meant we return UUIDs as a means of uniquely
identifying (REV, PATH) pairs. This scheme is being used by some systems
where /a/b/foo.c can exist as rev 1.33, get deleted, and brought back
starting at rev 1.1. Thus, a URL which has (say) /a/b/foo.c?rev=1.33 will
not be unique over time. Using a UUID provides for distinguishing between
the two generations of foo.c.
Our problem is that a change to foo.c spawns a "logical" change to bar.c
(the global revision number bump). We are trying to avoid the caching and
identity problems around that implicit bump.
> So, each time I commit a new node revision as part of some
> transaction, I place a flag or property on that node revision giving
> the REV and PATH in which it first appears. Easy enough. From then
> on, DAV can use that (REV, PATH) as the DAV-ID, even when accessing
> revisions in which that path no longer exists, or no longer refers to
> that node revision.
I don't get this sentence. We'd use the (REV, PATH) pair to access just that
(old) revision and path. If a later revision deletes that PATH, then we
won't be attempting to fetch the resource any more. And if the node revision
changes, then presumably we have a new (REV, PATH) pair to fetch the new
node revision.
> And unlike a node revision ID, the filesystem can
> check authorization properly given a (REV,PATH) pair. So that meets
> all our requirements, I think.
Yes, this works. In one of my solutions, I mentioned storing the ROOT-ID on
the node. When ID is looked up, we fetch the ROOT-ID, and examine PATH for
ACLs. Storing a (REV, PATH) is about the same: use the REV to fetch ROOT-ID,
then examine PATH. Unfortunately, we want the DAV-ID to be different for two
PATH values so that we check the appropriate ACLs.
[ and yes: maybe we decide we *don't* want them different... if you can't
access the node via one path, then should they be allowed to access via a
different path? IOW, are ACLs applied to nodes rather than paths? ]
> The problem here is that if someone sets an ACL on some old revision,
> making it inaccessible, then suddenly all the nodes in new revisions
> whose DAV-ID's happen to refer to the now-restricted revision become
> inaccessible.
Woah. I always assumed that an ACL change was a property change (thus
requiring a revision bump), yet it sounds like you're saying they occur
outside the realm of node revisions.
Well... no matter. Recall, the problem is to identify a (ROOT-ID, PATH) pair
to process the ACLs. The ACL processing is orthogonal to the DAV-ID.
Ah. I see what you're saying. We apply an ACL to *just* revision 3, but want
to leave revision 4 open. If people are accessing rev4 using DAV-IDs that
refer to rev3, then they're SOL.
Yes... that is the problem that I was trying to solve in my "sidetrack". How
do we detect ACL changes so that we can generate a DAV-ID that identifies
the "correct" (ROOT-ID, PATH) pair. However, I always assumed that ACLs
could not be retroactively applied. *If* we were to allow that, then we are
going to have a very tricky problem to solve.
My current position on the problem is generating a DAV-ID that can be
defined pretty much as:
The DAV-ID for node N should identify a (ROOT-ID, PATH) pair such that
ROOT-ID is the "earliest" ID of all revision roots which specify N at PATH
and have the same ACLs along PATH as the "latest" ID of those revision
roots.
This effectively means the ACLs for access to N is defined by the youngest
of all roots which specify that N at PATH. Once you have N+1, then a
different set of ACLs apply.
Hmm... I just realized that we don't want to determine the ACL set to apply
based on DAV-ID. Somebody could just use an old VR URL to avoid any recent
ACL changes (not to mention, that I'd still hope the VR URL remains
unchanged for optimal caching on clients and proxies). It appears the
problem is about finding the right set of ACLs given an arbitrary node.
Sigh... harder.
> > If you have a versioning system which stores a new file for each change,
> > then you'd just use the internal pathname to that file.
>
> I think this has the same problems as using node revision ID's. Let
> me work the analogy through and see if it applies:
>
> There are two possibilities: either different revisions of a tree
> share or don't share these per-change files. I'm not assuming
> Subversion's global revision number model here. I just mean, select a
> tree by date or by tag or by branch or whatever: do the same internal
> pathnames appear in different trees?
You would ask the server for the set of VR URLs that match some criteria.
Then you go and fetch them. There isn't a "tree" that is exposed for all
possible queries. So yes, the same VR URLs could appear in all the different
query responses.
> They must, or else you've lost requirement 1.1, which is the whole
> point of the game.
>
> So if they do share them, and we support directory renaming and
> deletion, then given a particular internal pathname, it must have more
> than one "parent" path --- I mean a parent in the version controlled
> tree, not a parent in the internal tree structure. And the more trees
> in which it appears, the more parents it may have.
You're talking about "Versioned Collections" here. If you don't have
versioned collections, then you don't have multiple (logical) trees. You
just have COLL with a bunch of versioned members. There aren't two versions
of COLL, each with their own set of members.
When you throw versioned collections into the mix: yes, there are
significant problems :-)
> So when I present a DAV server with one of these DAV-ID's, how can it
> determine whether I am actually authorized to access it? It doesn't
> know which path of parents to check.
In HTTP (DAV, DeltaV), the ACL model applies to a singular resource. Yes,
internally it may have inherited a bunch, or it may scan a bunch of data for
it, but to the *client* of the server, there is only a single question: "can
I perform METHOD on RESOURCE?" And it isn't really even a question -- you
just try it and get success or failure. There are some query operations to
fetch information to help you determine whether it will work or not, but the
final arbiter is just performing METHOD.
The implications of above is simply that which/what/how ACLs are determined
and applied are "out of scope". There is a WebDAV ACL spec, but it is still
focused around "apply THIS ACL to THAT resource." In the presence of
versioning, and versioned collections, and whatever else, it doesn't provide
for the full rules.
So the short answer to "how can it determine..." is simply "beats me; that
is up to the server to figure out." Granted, not helpful, but that is the
meat of it.
> > If you had a database of files, with a file per row (nodes!), then
> > you could use the node id. (we're throwing acls into the mix, which
> > bungles up this approach, but I bet that is about the data modelling
> > rather than a statement about the validity of the requirement)
>
> Well, but that's exactly my question: I can't figure out how to
> implement DAV-ID's without throwing away some of the ACL behavior
> which we had thought was reasonable. If you think we should revise
> that part of the ACL idea, so that one can access nodes even if one
> doesn't have "execute" access (or whatever we call it) to its parents,
> then that's a point to discuss. But I think folks will be surprised
> to learn where that requirement comes from.
Oh, I agree: parents should apply. My statement above was about constructing
DAV-ID values (well, VR URLs) from available data. Not a statement about the
validity of ACLs.
>...
> What I meant was, "this works, but it doesn't help us, because we
> don't have that simplification." My whole point is that DAV-ID's
> don't seem to mix (as far as I can tell) with ACL's on parents that
> restrict access to children (as, say, Unix execute permissions on
> directories do), when a child can appear in multiple parents.
Partially agree: with our current system, they don't appear to mix well. But
I think that is caused by two problems:
1) we don't have a firm grasp of what we want the ACL model to be, within
the space of multiple access paths to a given node
2) our data modelling
Once we decide on (1), then we can figure out (2). If (2) doesn't match what
we currently have, then we change the data model, or we change our ACL
rules, or we live with some caveats, or whatever. But we aren't there yet.
[ I'm bringing in data modelling because it can easily be said that part of
our problem is the inability to easily answer questions like "what is the
latest revision where PATH points to N" as part of the ACL application ]
>...
> > It should not be hard to compute OLDEST-REV for any given node. Just record
> > it in the node when it is created. The obvious problem is that we only have
> > TXN when we're creating the node, not REV. This would imply the need for
> > retaining a TXN -> REV mapping; to compute OLDEST-REV, you'd take the nodes'
> > TXN and pass it thru the mapping to get a REV. The mappings could sit in the
> > transactions table (possibly by storing a skel such as ("committed" REV)),
> > or a fourth table could be used.
>
> As I said above, I'd be happy to record this info in the node revision
> when it's created. That's equivalent to your suggestion, I think.
> The problem is that now the user needs to be authorized to traverse
> both of two distinct paths to reach a node --- both the path in the
> revision he's actually working in, and the path in OLDEST-REV. We
> only want the former to matter.
Well, that's a discussion point :-) ... Only the former? Then what use is
the ACL, if they can simply use a different REV or PATH to access the
resource? Do we take the set of all (REV, PATH) that access N and compute
the strictest or the least-strict ACL for N? etc.
>...
> > Storing the ROOT-ID should allow us to use (ID, PATH) as the DAV-ID, which
> > meets every condition that we've specified.
>
> Yep. Same problem as (OLDEST-REV, PATH), though. (Equivalent, I think.)
Yes.
> I didn't really understand your Answer #2 and Answer #3. But you
> raise a critical point: we don't really know how ACL's are going to
> work --- frankly, I think it might be a challenge to get useful
> semantics, so we may see some severe hair --- and since the exact
> problem here is the interaction between authorization and DAV-ID's, we
> need to understand how ACL's are going to work before we can tackle
> this. Just recognizing that there's an interesting interaction there
> is a good thing.
Agreed :-)
> Pending the addition of ACL's to the system, I don't see any reason
> not to use node revision ID's as DAV ID's.
That is certainly a good intermediate step. And since we'll be treating VR
URLs as opaque entities, we can change it on the server without a problem.
(the client could end up with "stale" VR URLs, but it is possible to refetch
new ones from the server)
I also note that we appear to be stretching past our mantra of "for 1.0,
meet CVS's features, yet pass it for low-hanging fruit". CVS simply has "if
you can authenticate with this server, then you're allowed." People
typically layer on per-module ACL support, but they apply at a very gross
level and quite independently of the revisions. We can *match* that
capability just with Apache's ACLs; no need for ACLs in the FS.
I'm going to capture a few of the key issues in a notes/acl-issues.txt for
later discussion. Until we tackle that, I'll use (ID, PATH) within the VR
URLs.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/
Re: getting nodes by ID
Posted by Jim Blandy <ji...@zwingli.cygnus.com>.
(Is there a better term than DAV-ID? I'm happy to use the real DAV
terminology, but I don't know what it is.)
Greg Stein <gs...@lyra.org> writes:
> > Would it be possible to change DAV to remove condition 2)?
>
> Well, it is reasonable assumption that the user will typically be fetching
> the latest. IOW, heuristics will typically make this fast.
I think we're miscommunicating. What I meant is:
At the moment, there's a requirement that a DAV-ID alone is sufficient
to efficiently retrieve a node: a request can just take a DAV-ID and
hand you back its contents, quickly.
What if we changed that rule so that the DAV-ID alone was sufficient
to check identity --- "Okay, this file you've asked for is the same as
one I've already got" --- but you need additional information to
actually get the file, if the identities don't match. Then we could
use node revision ID's as DAV-ID's --- if two node revision ID's are
identical, then you've got a cache hit --- and supply a (REV,PATH)
pair for retrieval. So you haven't lost condition 1.1 ("if their
contents are equal(*), their DAV-IDs are equal."), since you're only
comparing node revision ID's.
> > Also, it seems to me like the problems we're having in implementing
> > this aren't really unique to Subversion. Can you show us a system
> > where DAV-ID's are easy to implement, with all the desireable
> > properties?
>
> A table mapping UUIDs to (REV, PATH) pairs.
So, each time I commit a new node revision as part of some
transaction, I place a flag or property on that node revision giving
the REV and PATH in which it first appears. Easy enough. From then
on, DAV can use that (REV, PATH) as the DAV-ID, even when accessing
revisions in which that path no longer exists, or no longer refers to
that node revision. And unlike a node revision ID, the filesystem can
check authorization properly given a (REV,PATH) pair. So that meets
all our requirements, I think.
The problem here is that if someone sets an ACL on some old revision,
making it inaccessible, then suddenly all the nodes in new revisions
whose DAV-ID's happen to refer to the now-restricted revision become
inaccessible.
> If you have a versioning system which stores a new file for each change,
> then you'd just use the internal pathname to that file.
I think this has the same problems as using node revision ID's. Let
me work the analogy through and see if it applies:
There are two possibilities: either different revisions of a tree
share or don't share these per-change files. I'm not assuming
Subversion's global revision number model here. I just mean, select a
tree by date or by tag or by branch or whatever: do the same internal
pathnames appear in different trees?
They must, or else you've lost requirement 1.1, which is the whole
point of the game.
So if they do share them, and we support directory renaming and
deletion, then given a particular internal pathname, it must have more
than one "parent" path --- I mean a parent in the version controlled
tree, not a parent in the internal tree structure. And the more trees
in which it appears, the more parents it may have.
So when I present a DAV server with one of these DAV-ID's, how can it
determine whether I am actually authorized to access it? It doesn't
know which path of parents to check.
> If you had a database of files, with a file per row (nodes!), then
> you could use the node id. (we're throwing acls into the mix, which
> bungles up this approach, but I bet that is about the data modelling
> rather than a statement about the validity of the requirement)
Well, but that's exactly my question: I can't figure out how to
implement DAV-ID's without throwing away some of the ACL behavior
which we had thought was reasonable. If you think we should revise
that part of the ACL idea, so that one can access nodes even if one
doesn't have "execute" access (or whatever we call it) to its parents,
then that's a point to discuss. But I think folks will be surprised
to learn where that requirement comes from.
> > For example, what if I'm implementing DAV on CVS --- what
> > kind of DAV-ID would you use there? You could use (PATH, RCS-NUMBER),
> > but only because CVS doesn't really allow you to delete directories,
> > or support renaming.
>
> That is exactly what I'd use because it works very well. "but only" is moot.
> It's the CVS design, and we can take advantage of it.
What I meant was, "this works, but it doesn't help us, because we
don't have that simplification." My whole point is that DAV-ID's
don't seem to mix (as far as I can tell) with ACL's on parents that
restrict access to children (as, say, Unix execute permissions on
directories do), when a child can appear in multiple parents.
> > I guess I'm beginning to wonder if this isn't a
> > half-baked idea in general, not just a problematic case for
> > Subversion.
>
> It is emphatically NOT half-baked.
Relax --- I'm just trying to figure out how to implement what you
want. I honestly don't see the solution.
> It should not be hard to compute OLDEST-REV for any given node. Just record
> it in the node when it is created. The obvious problem is that we only have
> TXN when we're creating the node, not REV. This would imply the need for
> retaining a TXN -> REV mapping; to compute OLDEST-REV, you'd take the nodes'
> TXN and pass it thru the mapping to get a REV. The mappings could sit in the
> transactions table (possibly by storing a skel such as ("committed" REV)),
> or a fourth table could be used.
As I said above, I'd be happy to record this info in the node revision
when it's created. That's equivalent to your suggestion, I think.
The problem is that now the user needs to be authorized to traverse
both of two distinct paths to reach a node --- both the path in the
revision he's actually working in, and the path in OLDEST-REV. We
only want the former to matter.
> Let's take a different approach here. We don't need to answer the question
> of "what is the oldest revision this node appears in?", but we need to
> answer "what are the ACLs that apply to this node?" We posited this in (4),
> but kept trying to answer the former question.
>
> How about this: when a node is created, we record the ROOT-ID (of the txn)
> in the node. To determine the ACLs that apply to any given node (and PATH!),
> we bounce up to the node's ROOT-ID, then traverse the PATH for ACLs.
>
> Storing the ROOT-ID should allow us to use (ID, PATH) as the DAV-ID, which
> meets every condition that we've specified.
Yep. Same problem as (OLDEST-REV, PATH), though. (Equivalent, I think.)
I didn't really understand your Answer #2 and Answer #3. But you
raise a critical point: we don't really know how ACL's are going to
work --- frankly, I think it might be a challenge to get useful
semantics, so we may see some severe hair --- and since the exact
problem here is the interaction between authorization and DAV-ID's, we
need to understand how ACL's are going to work before we can tackle
this. Just recognizing that there's an interesting interaction there
is a good thing.
Pending the addition of ACL's to the system, I don't see any reason
not to use node revision ID's as DAV ID's.
Re: getting nodes by ID
Posted by Greg Stein <gs...@lyra.org>.
On Mon, Mar 05, 2001 at 05:13:49PM -0500, Jim Blandy wrote:
>
> DAV wants to be able to retrieve nodes by DAV-ID. This DAV-ID doesn't
> have to be a Subversion FS node revision ID --- it can be any
> arbitrary string of bytes such that:
> 1) if two nodes' DAV-ID's are equal, their contents are equal, and
Yes. And:
1.1) if their contents are equal(*), their DAV-IDs are equal.
(*) equal in the sense that the nodes have some relationship; if two files
*happen* to have the same content, then there is no expectation of
"equality" here; and "node" needs to be defined better -- it could refer to
"node means rev/path pair" or "dag_node"; two dag_nodes will almost
invariably not be equal.
> 2) it's reasonably fast to retrieve a node given a DAV-ID.
Define "fast". I would hope that you don't have to do linear searches to
retrieve the node. I'd hope for O(1).
IOW, "fast" == "not linear time"
> The idea, I think, is that when you ask for the contents of a
> directory, you'd get back a list of (name, DAV-ID) pairs, and then you
> could retrieve the contents you were interested in by DAV-ID. A
> caching proxy would use DAV-ID's to recognize text it had seen before.
Exactly.
> So we should add the following property:
>
> 3) As often as possible, if a node's contents have not changed, its
> DAV-ID shouldn't change.
Yes.
> The first idea was that we'd simply use filesystem node revision ID's
> as DAV-ID's. That certainly meets the requirements above. But that
> won't work, because the filesystem can't tell whether you are
> authorized to access a file without knowing the path through which you
> reached it --- if you don't have permission to read some parent
> directory, you shouldn't be able to read its contents, no matter what
> the permissions are on them.
Yup to all.
> So we need to add:
>
> 4) Given a DAV-ID, there must be a quick way to determine whether the user
> is authorized to access the node.
Define "quick" :-) ... again, I'd say "not linear time".
> The next suggestion was to use a pair (PATH, NODE-REV-ID). But PATH
> is useless without a revision or transaction whose root we can start
> from. The database isn't indexed to quickly answer questions like "in
> what revisions does PATH refer to NODE-REV_ID?" (I think such an
> index would completely duplicate the directory structure, unless
> someone thinks of something clever.)
All right. We'll posit this as "not feasible" for now...
> Another possibility would be to use a pair (REV, PATH), where REV is
> the oldest revision in which PATH refers to the node we want. This
> satisfies all four properties, but there's no quick way to choose the
> right REV, without trying them all. Since the "oldest" part is only
> necessary to satisfy condition 3), we can relax it a bit to "the
> oldest revision we can find". But this is still a mess. We're doing
> an unbounded number of path traversals in the database.
Yup.
> So we need to
> clarify:
>
> 5) It should be quick to compute a suitable DAV-ID for each node as we
> traverse the filesystem.
Yup.
> Would it be possible to change DAV to remove condition 2)?
Well, it is reasonable assumption that the user will typically be fetching
the latest. IOW, heuristics will typically make this fast.
> That is,
> can we use DAV-ID's to notice cache hits, but supply extra information
> to get the real thing when we miss? That way, we could use node
> revision ID's for DAV-ID's, but also supply a (ROOT, PATH) pair that
> could be looked up easily.
If ROOT appears within the DAV-ID, then you've lost condition 1.1.
> Also, it seems to me like the problems we're having in implementing
> this aren't really unique to Subversion. Can you show us a system
> where DAV-ID's are easy to implement, with all the desireable
> properties?
A table mapping UUIDs to (REV, PATH) pairs. The UUID design has already been
discussed as an approach (I'd say somebody is planning to use it, but most
people on the DeltaV list are proprietary vendors and barely even say what
they're building, let alone their design).
If you have a versioning system which stores a new file for each change,
then you'd just use the internal pathname to that file.
If you had a database of files, with a file per row (nodes!), then you could
use the node id. (we're throwing acls into the mix, which bungles up this
approach, but I bet that is about the data modelling rather than a statement
about the validity of the requirement)
> For example, what if I'm implementing DAV on CVS --- what
> kind of DAV-ID would you use there? You could use (PATH, RCS-NUMBER),
> but only because CVS doesn't really allow you to delete directories,
> or support renaming.
That is exactly what I'd use because it works very well. "but only" is moot.
It's the CVS design, and we can take advantage of it.
> I guess I'm beginning to wonder if this isn't a
> half-baked idea in general, not just a problematic case for
> Subversion.
It is emphatically NOT half-baked.
The DAV-ID concept is really just another name for a version resource URL.
These URLs are intended to be "stable" forever. That is, they don't
disappear and their contents don't change. Ever. I can send you one of these
URLs, and I don't need to worry about later updates blowing over what I
sent. The part about keeping them the same is to prevent the implication
that changes have occurred (you make value judgements given VR1 and VR2
without needing to fetch both of them).
The network performance implications are tremendous, if we can meet
condition 1. And I mean BIG.
[ just ask me how happy SourceForge would be, to be able to use a farm of
caching reverse proxies in front of their SVN servers; or a group of
people using transatlantic links via a caching proxy ]
As Karl points out, if you have (R1, PATH) and (R2, PATH), and you want to
know that they are equivalent, then how would you do it? We're answering it
using DAV-ID, but that is just a means to an end. IOW, the comparison is the
important part (ie. comparison leads to dav-id, not the other way), and it
has happened to be exposed through our DAV operation.
[ that said: I'm not entirely sure of the "proper" way for the server to
expose the concept; for example, how does it work over ra_local ]
It should not be hard to compute OLDEST-REV for any given node. Just record
it in the node when it is created. The obvious problem is that we only have
TXN when we're creating the node, not REV. This would imply the need for
retaining a TXN -> REV mapping; to compute OLDEST-REV, you'd take the nodes'
TXN and pass it thru the mapping to get a REV. The mappings could sit in the
transactions table (possibly by storing a skel such as ("committed" REV)),
or a fourth table could be used.
Let's take a different approach here. We don't need to answer the question
of "what is the oldest revision this node appears in?", but we need to
answer "what are the ACLs that apply to this node?" We posited this in (4),
but kept trying to answer the former question.
How about this: when a node is created, we record the ROOT-ID (of the txn)
in the node. To determine the ACLs that apply to any given node (and PATH!),
we bounce up to the node's ROOT-ID, then traverse the PATH for ACLs.
Storing the ROOT-ID should allow us to use (ID, PATH) as the DAV-ID, which
meets every condition that we've specified.
-------- Sidetrack Start
Now, there is one more, very subtle "gotcha". Let's say that I have a node
that is unchanged between R1 and R2. The delta for R1 -> R2 is simply an ACL
change on the root directory to disable reads. We now have a problem in that
the DAV-ID for (R2, PATH) is effectively (R1, PATH), so the ACL change won't
take effect. Oops! :-)
Answer: the DAV-ID becomes (ID, PATH, ACL-MD5), where ACL-MD5 represents an
MD5 checksum of all ACLs on PATH. Effectively, we're saying that a node's
state is more than just its contents: it also includes all the ACLs on its
parents.
Of course, the above "answer" doesn't work. We don't have a way to recover
the appropriate ROOT-ID for a given DAV-ID (i.e. we can't recover R2).
Answer #2: if the ACL-MD5 for (REV, PATH) is the same as the ACL-MD5 for
(ROOT-ID, PATH), then we use (ID, PATH) as the DAV-ID. If they are unequal,
then we use (ID, PATH, REV). Of course, this bungs things up because once an
ACL changes, then the DAV-ID tracks REV, which breaks condition 1.1.
Answer #3: this one gets a bit more complicated, and is not O(depth), but
needs to scan some nodes during DAV-ID construction. Essentially, the DAV-ID
becomes (ID-1, ID-2, ..., ID-n) (one for each component in PATH) such that
ID-i is the oldest revision where the ACL-MD5 for the tail-path matches the
ACL-MD5 for the current revision.
-------- Sidetrack End
The problem is that a given resource state varies based on external factors.
If I'm referring to some node ID, its "value" changes based on things
happening elsewhere in the tree.
If you stop and consider that the R1 -> R2 change imposed a different set of
ACLs on the same (unchanged) resource FOO, then the *effective* ACL is the
less restrictive of the ACLs on FOO's PATH in R1 and R2. Let's say that I
added restrictions. No big deal, I can back up to R1 and fetch the file; the
additional restrictions in R2 are useless. Let's say that I relax the
restrictions, then I can move forward to R2 to get the resource, where I
couldn't thru R1.
I believe that to section in "Sidetrack" needs to wait on an answer to
whether/how we want to solve the application of changing ACLs on the
parent(s) of a given resource. For example, we could state the policy as
"access to (ID, PATH) is based on the least restrictive set of ACLs on PATH
for each REV that selects ID at PATH." Or we could say "access is based on
the ACLs on PATH for the oldest REV that selects ID at PATH." Or the latest
REV.
The basic issue is one of:
1) if the ACL applied is based on the ("desired"-REV, PATH) pair, thus
allowing success/failure even though (OTHER-REV, PATH) is different, then
we need to distinguish every single (REV, PATH) pair so that each one can
have is own success/failure conditions.
[ and including REV busts 1.1 ]
2) if the ACL applied is unified/specified in some way to be "the ACL from
THIS-REV", then we just need a way to calculate THIS-REV (based on our
policy assertion) at DAV-ID construction time.
When we form a policy, then we go back to solving DAV-ID.
I'm not sure on what I'd suggest for an ACL application policy. I think we
mentioned the different-ACL-via-different-paths possibility before, but I
never *really* thought about the full implications until now. At this point,
I don't have a feeling for the "right" user model here. I believe that I'm
tending towards "apply the ACL from the latest REV that selects (ID, PATH)"
on the basis that the later ACLs are your true intent for the tree.
Hmm. Actually, I'm pretty solid in that camp. Consider doing a "tag"
operation for a release. You copy /main to /tags/1.0b1 and commit (as 1704).
Then you decide to make it read-only, so you plop a read-only ACL on the
directory (and commit as 1705). We want everything in that directory to use
the new ACL. No changing the release via 1704.
Assuming we use this policy, then I can craft an algorithm for DAV-ID
computation.
Cheers,
-g
--
Greg Stein, http://www.lyra.org/