Subject: BINDing using a weak reference

From: "Eric Sedlar" <[email-masked]>
Date: Sat, 04 Dec 1999 11:52:28 -0800

It appears that the authors of the advanced collections spec expect that
BINDing a resource into a new collection will adjust a reference count
on the destination, ensuring that the destination resource persists
until all bindings have been explicitly removed.

The problem with this behavior is dealing with cyclic references.  A
server implementer may allow cyclic BINDings, in which case DELETE
becomes very expensive, since the server must now validate that there is
still a valid path to the destination resource from the root, to avoid
orphaned cycles.  Alternately, a server implementer can disallow cyclic
bindings from being inserted in the first place, which is
computationally much cheaper, but which restricts the usefulness of
BINDings.  (Like the way UNIX restricts hard links to directories).

Has any thought been given to a notion of a "weak" binding, which
doesn't affect persistence?  As long as weak bindings are automatically
deleted when all of the strong bindings are removed, dangling BINDings
(the great evil) are avoided.  Especially when a DAV server is
implementing something like a user space quota, a strong BINDing implies
that the user creating it wants to maintain storage for the object
(implying a quota impact), whereas a weak binding would be more like a
smart bookmark that would follow a web page when moved and disappear if
that page were removed.

--Eric Sedlar
Oracle Corporation
[email-masked]

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Tue, 7 Dec 1999 11:28:11 -0500

From: "Eric Sedlar" <[email-masked]>

As you note below, a mark sweep style algorithm is more appropriate
if you want to do garbage collection (the spec does not require a
server to do any garbage collection).

   The problem with this behavior is dealing with cyclic references.  A
   server implementer may allow cyclic BINDings,

Actually, that wording has been revised to say that a server _must_
implement cycle bindings.

   in which case DELETE
   orphaned cycles.

Note that orphaned cycles are not forbidden by the spec, so there is
no requirement to clean up orphaned cycles immediately (e.g. it could
be a weekly garbage collection run).

   Alternately, a server implementer can disallow cyclic
   bindings from being inserted in the first place, which is
   computationally much cheaper, but which restricts the usefulness of
   BINDings.  (Like the way UNIX restricts hard links to directories).

This is now forbidden by the spec.

Yes, this was one of the variants discussed, but some of the difficulties
encountered are:
- does a server have to delete a weak binding when the last strong
binding goes away, or can it leave it dangling?
- how can a server ensure that it has write access to all weak bindings
that might need to be deleted when the last strong binding is deleted?
- if a weak binding is left dangling, how is this conveyed to a client?
- does the weak binding track the resource as it moves, or does it
just point at a specific URL?
- what happens if you issue a LOCK against a URL that contained a
weak binding?

So we decided that the complexity of defining and supporting a weak binding
outweighed its benefits.

Cheers,
Geoff

---

From: "Eric Sedlar" <[email-masked]>
Date: Tue, 07 Dec 1999 12:54:55 -0800

I've implemented this type of system before, and the costs of mark and sweep
are enormous when you are talking about large sets of documents living on disk
(like in a relational database).  People generally expect unlink/delete on a
file to work quickly, and applications depend on that not eating up a
tremendous amount of cycles or doing a lot of I/O.  Mark and sweep is also much
more expensive than forbidding the insertion of cycles.

If you wait to do garbage collection asynchronously, searches that do not
traverse the hierarchical namespace but that use other indexes (like keyword
searches, for example) will find things that the user has deleted.  Also,
deferring the garbage collection associated with the unlink breaks the
transactional guarantee when people COMMIT their work.

I can give you a perfectly good set of answers about how to deal with weak
links.  Oracle built a system that implements weak links and forbids cycles as
part of the Internet Filesystem product.  My responses to your issues are
included below, marked with <es> </es>.

--Eric Sedlar

> binding goes away, or can it leave it dangling?

<es>delete the weak binding</es>

> that might need to be deleted when the last strong binding is deleted?

<es>run the weak link cleanup as setuid root /system/whatever </es>

> - if a weak binding is left dangling, how is this conveyed to a client?

<es> not an issue>

> just point at a specific URL?

<es> it tracks the resource as it moves </es>

>  - what happens if you issue a LOCK against a URL that contained a

<es> locking a URL locks the namespace, not the resource.  While you have
locked the URL containing a weak binding, nobody else can use that set of names
in their respective collections.  The resource the locked URL points to may
actually be deleted while the URL to it is locked.  In this case the resource
is deleted when the lock is released.  (Think of the lock like an open file
descriptor, or in database terms, a snapshot in a read-only transaction that
was started when the lock was acquired).  This has the same effect as if
someone deleted that resource the instant the lock was released.
</es>

> So we decided that the complexity of defining and supporting a weak binding

<es> My experience on this question that the user benefits of allowing strong
BINDings to form a cycle are minimal if weak BINDings are allowed, and the
performance costs are high.  The distinction between two types of bindings is
useful when you add user quotas.  We call these strong & weak BINDings "saved"
and "unsaved" links--a saved link is a statement by the user that s/he is
willing to pay storage costs for the item linked to, whereas a weak BINDing is
more like a bookmark, useful for categorization and simplifying navigation.
</es>

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Tue, 7 Dec 1999 17:26:16 -0500

This is a classic garbage collection tradeoff.  On one side, you can
let the client define the relationships that it wants, and force the
server to deal with issues like detecting islands of garbage.  On the
other side, you can require that the client only define relationships
that are easy/efficient for the server to garbage collect.

The problem with the latter approach is that there are different
equally valid choices for how to constrain the relationships (the
weak/strong dichotomy you suggest is certainly a very reasonable one).
Reaching agreement on the constraints is very hard, since if your system
was not implemented with those constraints in mind, they do you no good
(and in fact, are probably even harder to implement than the general
form).

For example, the Unix file system also has weak and strong bindings
(symbolic and hard links).  It provides for efficient deletion, but it
made some different choices from the ones you picked.  In particular,
it chose to leave the weak bindings (symbolic links) dangling when the
last strong binding was deleted, and to only have the strong bindings
(hard links) track resource movement.

Trying to simulate in the Unix file system the weak/strong behavior
you describe would be prohibitively expensive.  So although it may be
painful to only support one type of bindings, I believe it has the
advantage that it is simpler to define and "fairer" across the various
existing implementations.

   If you wait to do garbage collection asynchronously, searches that do not
   traverse the hierarchical namespace but that use other indexes (like keyword
   searches, for example) will find things that the user has deleted.

WebDAV only supports searches that traverse the hierarchical namespace,
so although I understand your point, it does not apply to WebDAV as it
is currently defined.  Once the "V" (versioning) is added to WebDAV,
queries across the entire resource space will probably be rare in any case.

   Also,

There is no COMMIT functionality in WebDAV, so this would not be an issue.

The set of answers you provide for the Internet Filesystem product
appear both consistent and very sensible, especially in the context of
an underlying relational database implementation for the WebDAV store.

Just one comment on the locking issue:

   <es> locking a URL locks the namespace, not the resource.

I assume this only applies to weak bindings (i.e. there must be some
way to lock the resource itself, so I assume that is done through a
strong binding?).

   While you have
   locked the URL containing a weak binding, nobody else can use that set of names
   in their respective collections.

This sounds very different from WebDAV locks, which prevents
unauthorized clients from modifying a resource, not from using it.
Or by "use", did you mean "modify"?

By "set of names", did you mean for example the set of names:
{"/a/b/c", "/a/b", "/a"} that are relevant for a binding named "/a/b/c"?

   The resource the locked URL points to may actually be deleted while
   the URL to it is locked.   In this case the resource
   is deleted when the lock is released.  (Think of the lock like an open file
   descriptor, or in database terms, a snapshot in a read-only transaction that
   was started when the lock was acquired).  This has the same effect as if
   someone deleted that resource the instant the lock was released.
   </es>

This could be hard for a server implement if it didn't have underlying
transaction support.

Cheers,
Geoff

---

From: "Eric Sedlar" <[email-masked]>
Date: Tue, 07 Dec 1999 14:58:16 -0800

<introductory paragraphs from Geoff were cut here...>

Are you assuming that WebDAV servers will generally be standalone repositories, or do
expect existing repositories (e.g. ClearCase, MSExchange, Oracle RDBMS) will implement
WebDAV in addition to other protocols they currently use to access information
therein?  Do you expect WebDAV servers to be only used for managing development
content or also to manage production content?  It would seem like you would want the
broadest audience possible, and that would include existing servers and handling both
development and production content.  If you implementing WebDAV on an existing server
breaks their existing guarantees, they won't be able to support WebDAV, which seems
like an undesirable outcome.

> queries across the entire resource space will probably be rare in any case.

It seems to me that the most common type of WebDAV application would be managing
content on a web site, and the most common type of search (as is most common today)
would be the Yahoo-like one box keyword search across the entire resource space, or
perhaps contrained across a certain class of resources, like Amazon's "Search all
books" functionality.  If I want to implement this functionality against a resource
space managed by WebDAV, I'm screwed if I defer garbage collection.

> There is no COMMIT functionality in WebDAV, so this would not be an issue.

Are you assuming that WebDAV can only be implemented against non-transactional content
repositories?  If so, you should state that in the charter for WebDAV.  I think you
would be unnecessarily restricting the number of vendors interested in WebDAV if you
did this.

> way to lock the resource itself, so I assume that is done through a

I'm jumping to conclusions here based on the conversations you have been having with
Yaron Goland.  Given that some applications will want to reserve the entire pathname
when they LOCK it to prevent it from being moved, it seemed like a dichotomy would
have to be introduced where there are two separate types of LOCK operations: one that
locks the name separately from another request that locks the resource it refers to.

> {"/a/b/c", "/a/b", "/a"} that are relevant for a binding named "/a/b/c"?

I meant that the name "a" is reserved in the root collection, the name "b" is reserved
in the "/a" collection, and the name "c" is reserved in the "/a/b" collection.  By
reserved, I meant that no new files could use those names in those collections, nor
rename those names or move those links into another collection.

> This could be hard for a server implement if it didn't have underlying

Well UNIX doesn't go through a lot of hoops to maintain storage for open files.
However, another way to do this is to increase the reference count on the resource by
one for each BINDing and LOCK against the resource.  Why do you think this would be
hard?

> Geoff

--Eric

---

From: "Geoffrey M. Clemm" <[email-masked]>
Date: Tue, 7 Dec 1999 22:47:03 -0500

Before diving in, I'd like to thank Eric for becoming active
in the working group!  Getting this kind of in depth analysis
is of immense value as we try to nail down the spec for last call.

   Are you assuming that WebDAV servers will generally be standalone
   repositories, or do expect existing repositories (e.g. ClearCase,
   MSExchange, Oracle RDBMS) will implement WebDAV in addition to other
   protocols they currently use to access information therein?

The latter.

   Do you
   expect WebDAV servers to be only used for managing development content
   or also to manage production content?

Both.

   It would seem like you would
   want the broadest audience possible, and that would include existing
   servers and handling both development and production content.

Definitely.

   If you
   implementing WebDAV on an existing server breaks their existing
   guarantees, they won't be able to support WebDAV, which seems like an
   undesirable outcome.

The challenge is that different server implementations (e.g. file
systems, relational databases, document mgmt repositories, versioning
repositories) have very different guarantees, so defining a protocol
that allows clients to interoperate with all of them inevitably leads
to choices that are not optimal for any particular existing server.

The example of the Unix file system was intended to illustrate how
your (very reasonable) definition of strong/weak bindings are problematic
when applied to a different server implementation (i.e. the Unix file
system).

   It seems to me that the most common type of WebDAV application would
   be managing content on a web site, and the most common type of search
   (as is most common today) would be the Yahoo-like one box keyword
   search across the entire resource space, or perhaps contrained across
   a certain class of resources, like Amazon's "Search all books"
   functionality.  If I want to implement this functionality against a
   resource space managed by WebDAV, I'm screwed if I defer garbage
   collection.

A WebDAV site will commonly contained the source resources from which
derived resources are computed, as well as historical information
(e.g. previous revisions of existing information).  In the case of
Yahoo-like searches, unless they are constrained to a particular tree
(and in the case of versioning, a particular tree with a particular
target-selector header), many/most of the "hits" will be incorrect.
The "search all resources" approach works when only "deployed"
resources exist at a site ... with WebDAV support, there will be much
more available, and naive searches that don't restrict themselves
to a particular hierarchy will no longer be effective.

   > There is no COMMIT functionality in WebDAV, so this would not be an issue.

   Are you assuming that WebDAV can only be implemented against
   non-transactional content repositories?

No - we are just assuming that WebDAV must be implementable
on either a transactional or a non-transactional server, which
means that no cross-request transactional behavior can be 
assumed or required.

   If so, you should state that
   in the charter for WebDAV.  I think you would be unnecessarily
   restricting the number of vendors interested in WebDAV if you did
   this.

If there is any problem implementing WebDAV on a transactional server,
please flag it!  My point was just that WebDAV cannot assume cross-request
transactional behavior, so an argument based on what is needed to support
cross-request transactions would not apply to the WebDAV protocol.
Perhaps I misunderstood your point about COMMIT?

   > way to lock the resource itself, so I assume that is done through a

   I'm jumping to conclusions here based on the conversations you have
   been having with Yaron Goland.  Given that some applications will want
   to reserve the entire pathname when they LOCK it to prevent it from
   being moved, it seemed like a dichotomy would have to be introduced
   where there are two separate types of LOCK operations: one that locks
   the name separately from another request that locks the resource it
   refers to.

Currently, that is not the case for RFC-2518.  A lock is applied to the
URL and results in both a lock on the resource identified by the URL,
and the protection of the mapping of that URL to that resource.

   > This could be hard for a server implement if it didn't have underlying

   Well UNIX doesn't go through a lot of hoops to maintain storage for
   open files.  However, another way to do this is to increase the
   reference count on the resource by one for each BINDing and LOCK
   against the resource.  Why do you think this would be hard?

Well, the creation of those .nfsxxx files that sometimes don't get
garbage collected properly are some pretty ugly hoops (:-).  But more
to the point, RFC-2518 currently states that a locked resource can
only be deleted by a holder of the lock token, and that if you do hold
the lock token and issue a DELETE, the DELETE applies immediately and
is not deferred until the lock is removed.  So the DELETE semantics
you describe would not be compliant with RFC-2518.

Cheers,
Geoff

---

From: "Eric Sedlar" <[email-masked]>
Date: Wed, 8 Dec 1999 12:57:46 -0800

The reason you give that repository-wide searches are not likely is that you
won't want to search all of the revisions?  Most of the revision selection
mechanisms are not dependent on position in the hierarchy, and so I could do
some simple SQL like:

SELECT ... FROM labels, resources where labels.name = <blah> and
labels.resource-id = resources.resource-id and resources.body
contains(keyword1, keyword2, ...)

This would select all the documents with a particular label with the
keywords requested.  The same type of thing can be done with typical
text-search engines.

Let me ask another question though:

* let's say I create versioned resource /foo/bar.txt.
* I bind another name to that resource, so now we have /werf/bar.txt
pointing to the same resource
* I label the currently selected revision of /foo/bar.txt with some tag

I assume that a revision selection rule specifying that label for
/foo/bar.txt would also apply that selection if it encountered /werf/bar.txt
as well, correct?

From a performance standpoint, I would like to point out that the types of
indexes that work for hierarchy-independent searches tend to be MUCH faster
than traversing hierarchies.  Database indexes (or should I say indices?) as
well as text-search engines will both see a significant performance slowdown
if you force queries to traverse the URL hierarchy for all access.  Plus you
will have to do a bunch of development on all of these search engines to
handle the join with the hierarchical information.  I STRONGLY recommend not
REQUIRING hierarchical access to WebDAV-managed content.  You will break
most of the search technology currently in use on the web.  I can tell you
that if most Oracle customers are offered the choice of having a bunch of
great neat content management functionality at the price of decreasing
search performance, they will stick with the search performance.  Nothing
irritates users more than waiting for search results.

For this reason alone, I think it is worth adding the concept of weak
BINDings to the Advanced Collections spec, since I think a lot of server
implementors will want to avoid dealing with cyclic references that impact
object persistence and avoid garbage collection.

--Eric

---

From: Greg Stein <[email-masked]>
Date: Sat, 11 Dec 1999 04:37:10 -0800 (PST)

On Tue, 7 Dec 1999, Geoffrey M. Clemm wrote:
>...

Already demonstrated.

mod_dav ships with the Unix filesystem for a repository. However, there
are two (private builds) of mod_dav: one that works against ClearCase (and
is experimenting with the versioning spec!), and one that delegates the
back-end services through CORBA. There have been some rumblings about
using PHP scripting to back-end mod_dav, but nothing has been completed
there, yet (that I know of).

Cheers,
-g

-- 
Greg Stein, http://www.lyra.org/