Subject: RE: WebDAV Bindings - Issue Yaron.AtomicDelete

From: "Slein, Judith A" <[email-masked]>
Date: Thu, 27 Jan 2000 11:00:42 -0500

I think maybe we haven't made it clear what we are trying to accomplish by
saying that DELETE must be atomic.  And maybe expressing it that way is
confusing.  Here are the results we want (I think):

1. DELETE removes a single binding.  It does not remove all the bindings to
a resource, only the one identified by the Request-URI.  If it happens to be
the last binding, then what happens about garbage collection of either
content or properties is outside the scope of the spec.  DELETE is just
about removing the binding.

2. In the case where the binding is to a collection, DELETE still means only
remove the binding to that collection.  It is not acceptable to walk the
tree deleting bindings to descendents of that collection.  This would have
disastrous consequences in an environment with multiple bindings to
resources.  To resurrect an example of Jason's:

User UA uses URL /a/C/ to access collection coll1.  User UB uses URL /b/C/
to access the same collection.  Now suppose UA issues a DELETE on /a/C/.
What you want is for UB to be able to continue to use /b/C/ to access the
collection (and all its descendents).  So you can't go deleting the bindings
in coll1 to all its children.  All you want to do is remove the binding
a:(C->coll1) from collection /a/.

Does either of these restrictions cause problems for mod_dav?

--Judy

> -----Original Message-----
> From: Greg Stein [mailto:[email-masked]]
> Sent: Friday, January 21, 2000 5:36 PM
> To: [email-masked]
> Cc: Yaron Goland; [email-masked]
> Subject: Re: WebDAV Bindings - Issue Yaron.AtomicDelete
> 
> 
> On Tue, 18 Jan 2000 [email-masked] wrote:
> >...
> > >>
> >  There are, I freely admit, circumstances in which a client 
> MUST be able to
> > ensure that a DELETE is issued atomically. Clients in those 
> cases will have
> > to choose to not interoperate with many WebDAV servers in 
> order to gain
> > atomic delete.
> > >>
> > These clients can interoperate with an old iterative server 
> just fine if
> > they also include 2518 support.  That's their choice.
> > 
> > We have asked around and it seems that server authors 
> appreciate and are
> > willing to comply with semantic of an "atomic" removal of a 
> single binding.
> 
> I don't recall being asked, nor agreeing with atomic 
> operations. If that
> binding happens to be a collection, then it will definitely 
> be non-atomic.
> 
> [ also assuming this is the "final" removal of the collection ]
> 
> >...
> > >>
> > Let me clarify that DELETE was defined to not be atomic 
> with malice of fore
> > thought. The non-atomic delete language was the result of 
> nearly three
> > years of negotiations and represented a deep and broad 
> consensus built up
> > amongst a huge community. Might I respectfully suggest to 
> the BIND authors
> > that they should not be so ready to overthrow years of 
> careful consensus
> > building.
> > >>
> > We've asked around.  Folks appreciate this behavior and are 
> willing to
> > support it.
> 
> Again: I don't remember being asked. Maybe I missed a post to 
> this list?
> 
> Regardless, I am not willing support atomic deletions of 
> collections OR
> single, member resources. Note that I mentioned member 
> resources here. I
> delete a member resource in two steps: the contents and its 
> properties.
> Definitely non-atomic.
> 
> And with respect to the Apache web server, I will not even 
> begin to think
> of making it atomic (e.g. serialize all requests while a 
> resource is being
> deleted).
> 
> > >>
> > Do not imagine that the lack of screaming on this issue 
> reflects consensus.
> > Rather it reflects the fact that most of the WebDAV 
> community is too busy
> > implementing RFC 2518 to pay much attention to BIND. The BIND
> > functionality, while I believe it will be important to 
> WebDAV, is a bit
> > ahead of the majority of implementers so they just aren't reading or
> > reviewing it, yet.
> > >>
> > We have asked around and we didn't accept silence as a response.
> 
> I was certainly silent. Either that, or I'm going senile and forget
> responding to a question of atomicity. I certainly can't 
> imagine replying
> "sure, I can sure an atomic delete".
> 
> > >>
> > The key reason DELETE was not allowed to be atomic (which 
> certainly would
> > have been a nice thing to be able to do) has to do with the way file
> > systems work. Most file systems do not support depth 
> operations atomically.
> > So, for example, when you delete a directory what actually 
> happens is that
> > the program does a depth first walk of the directory tree 
> and deletes all
> > the individual files, walking backwards up the tree until 
> finally deleting
> > the parent directory.
> > >>
> > You've pointed out that this is a problem on your file 
> system.  We've found
> > no other.   We've tested it and our testing indicates that 
> the MOVE option
> > you mention below works.  (We did not test with ACL's 
> though... or multiple
> > bindings.)    We've also contacted folks at your 
> organization and they
> > didn't see a problem.
> 
> This is an undue complication: generate a unique name, rename 
> the resource
> to that new name, then process its removal. And again, 
> mod_dav couldn't
> even do this because of its separation between properties and 
> contents: I
> could move the contents away, but a PROPFIND could still return
> properties.
> 
> >...
> > >>
> > There is then the third and final issue, WebDAV begins with 
> a "D" for a
> > reason. It's goal is to be distributed. Requiring atomic 
> DELETEs would
> > essentially hinder all but the most expensive of systems 
> from being able to
> > implement distributed namespaces across multiple physical 
> servers. The
> > reason being that the atomic requirement means that these 
> systems will have
> > to establish transactioning systems between themselves in 
> order to issue
> > DELETEs if they share namespace.
> > >>
> > It's only one binding.  The goal isn't to be atomic, that's just a
> > fortunate side effect.
> 
> It is *definitely* not a "side effect." mod_dav certainly 
> does not do a
> rename-then-delete. Therefore, I have to take explicit 
> actions to achieve
> that behavior. I don't even think that I could *ever* 
> guarantee an atomic
> DELETE operation.
> 
> >...
> > >>
> > As such I move that the atomic DELETE language be struck 
> from the BIND spec
> > on the grounds that it destroys interoperability, requires 
> behavior that
> > would preclude file system based systems from supporting WebDAV and
> > significantly increases the cost of implementing WebDAV in 
> a distributed
> > manner.
> > >>
> 
> I agree with Yaron on this one. Strongly.
> 
> > I believe I've addressed all of these above.
> > 
> > It is very clear that DELETE should not be iterative or 
> accept partial
> > results in a server that supports multiple bindings.
> 
> I think it is very clear that it shouldn't.
> 
> Stating your opinion of clarity doesn't make it so, nor does 
> mine. But I
> certainly can tell you right now that I won't be one of the "example
> implementations" required for an IETF Standard.
> 
> > Legacy clients may
> > invoke DELETE without knowledge of the potential dangers.  
> Therefore, a
> > simple DELETE should delete a single binding.  --- There is 
> no compelling
> > reason (so far) not to support single binding delete and it 
> simplifies the
> 
> I believe that I've given you one. With a good chunk of extra work and
> serialization within the server, then it might be possible. 
> But I am not
> really up for trying to figure it out.
> 
> Cheers,
> -g
> 
> -- 
> Greg Stein, http://www.lyra.org/
>

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Thu, 27 Jan 2000 12:56:35 -0500

I agree with Judy's description of what we want to achieve by saying
DELETE is atomic.  Another way of phrasing it is that avoids the word
"atomic" is to say:

"A DELETE modifies the state of the collection resource containing the
specified binding (namely, by deleting that binding), but MUST NOT
modify the state of any other collection resource as a side effect."

In an implementation where only a single binding to a collection
is supported, then deleting a binding to a collection will result in all
the members of that collection being inaccessible, so having the server
traverse down and mangle all the subcollections is permissible (after all,
the client specifically said it isn't interested in any of them any more).

But in a system where having multiple bindings to collections is
supported (e.g. database and versioning systems), mangling member
collections as a side effect of a delete is unacceptable, since this
mangles resources whose current state may still be significant to the client.

One possible compromise would be to place this restriction only on servers
that support multiple bindings.  In particular, the phrasing could be:

The request "DELETE /pathX/resourceY" MUST remove the binding named
"resourceY" from the collection identified by "/pathX".  If a resource
supports the BIND operation, then the request "DELETE /pathX/resourceY"
MUST NOT remove a collection's binding to that resource unless
"/pathX" identifies that collection and "/pathX/resourceY" identifies
that resource.

Greg, Yaron, as supporters of the "mangle" form of DELETE (:-),
would you find this acceptable?

Cheers,
Geoff

   From: "Slein, Judith A" <[email-masked]>

---

From: "Roy T. Fielding" <[email-masked]>
Date: Thu, 27 Jan 2000 10:35:02 -0800

>modify the state of any other collection resource as a side effect."

No, that is a requirement on the implementation, not the protocol.
Why don't you just use the two paragraphs that Judy listed?

>>resources.  To resurrect an example of Jason's:

This has nothing to do with "atomicity".   It does, however, raise a
problem in that removing the last binding to a non-empty collection might
be unacceptable to the server.  This second case should allow the server
to report an informative error if it requires that the collection be
empty first (this would depend on the nature of the colection resource,
not on some aspect of the protocol).

....Roy

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Thu, 27 Jan 2000 14:14:50 -0500

From: "Roy T. Fielding" <[email-masked]>

I like Judy's two paragraphs, so that's fine with me.

Just for interests sake, since my rewording was intended to be just
state the key point from Judy's two paragraphs, what was wrong with
it?  Doesn't a protocol always defines requirements on the
implementation?  (I'm not disagreeing with you, I just didn't
understand your point.)

   >>resources.  To resurrect an example of Jason's:

   This has nothing to do with "atomicity".

I agree.  The term "atomicity" should not be used in this context.

   It does, however, raise a

Good point.  An appropriate error status should be defined.

Cheers,
Geoff

---

From: "Roy T. Fielding" <[email-masked]>
Date: Thu, 27 Jan 2000 12:02:44 -0800

>implementation?  (I'm not disagreeing with you, I just didn't

A protocol requires that the externally visible behavior of the
component match that expected by the protocol.  The way you phrased
it was specifying the state within the collection component rather
than what was visible to other components.  Consider, for example,
that a hierarchical database implementation of collections might
have dual-linked relations between sister collections, and thus
deletion of one collection would have to effect another collection.

The point being that we don't have to require anything beyond what
the protocol means -- specifying anything beyond that is just overkill
and tends to limit implementations unnecessarily.

....Roy

---

From: Greg Stein <[email-masked]>
Date: Thu, 27 Jan 2000 18:27:35 -0800 (PST)

> confusing.  Here are the results we want (I think):

In the sense that "atomic delete" meant "integrity is retained during the
delete", then mod_dav has a problem.

It appears that you are removing the word "atomic" and replacing it with
more specific language on what "delete" means. This seems fine...

> about removing the binding.

Not a problem *if* the server does not support bindings. As long as it is
understood there can be a race condition during the processing of the
DELETE operation.

> remove the binding to that collection.

Again, not a problem.

> It is not acceptable to walk the
> resources.

And this is the problem for both of the cases above. When bindings are
present, we've got problems. In a standard Unix file system, I can
implement bindings in one of three ways:

1) symbolic (soft) links
2) hard links
3) binding database plus custom URL translation

Note that hard links cannot operate across a "devices" and cannot be used
on directories (collections). These two restrictions pretty well obviate
(2), so we are left with (1) and (3). 

With symbolic links, there is no way to know if another resource is
referring to my "real" resource. If somebody deletes a resource and it is
just a symlink -- no problem. If the resource is an actual file or
directory, then how do I know if another resource is using it? For
scenario (1), I would have to retain a database of backpointers. If a
backpointer exists, then what do I do with the "real" resource? I must
then decide to move/rename the thing (or something).

(3) is simply a pain in the butt. It is essentially implementing a symlink
in the web server. It essentially records the backpointers mentioned in
the previous paragraph, but still doesn't solve the "what happens when the
'real' resource is deleted?"

A final option is to make *all* resources symlinks and put the actual
content somewhere else. This would require a database of reference-counts,
however. Maybe mixing with (3) to do the symlinking and refcounts might
work.

> Does either of these restrictions cause problems for mod_dav?

Only in the presence of bindings. There would be a LOT of work to
correctly handle bindings and deletes.

To make it more easily implementable, I would need one of two items:

1) binding between collections is not allowed (this would allow hard
   links; I could live with the device restriction)

2) it is allowable to leave dangling references (a symlink to a "real"
   resource that has been deleted)

Neither of these are very appealing. As it stands, it appears that the
binding specification *requires* a database that maps URLs to resources
(outside of a standard web server's URL translation system).

If a database was required, then I simply wouldn't implement bindings all
that soon. But it *would* be possible.

[ I'm not suggesting that we punt/restrict features such as binding simply
  because particular filesystems cannot support the feature in question;
  I'm just saying that it will take longer to code... ]

The impossible part is guaranteeing that no race conditions exist during
the processing of the DELETE.

Cheers,
-g

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Fri, 28 Jan 2000 09:25:36 -0500

Thanks for the explanation.  By "state" I just meant "the set of
bindings", but I see how a non-clairvoyant reader would not know
this.  Just to confirm that I understood your point, would this
rewording be acceptable:

"A successful DELETE removes the specified binding from the specified
 collection, but (whether it succeeds or fails) MUST NOT remove any
 other other bindings from the specified collection or any other collection."

Cheers,
Geoff

   ....Roy