Subject: Interest in standardizing Batch methods?

From: "Jim Whitehead" <[email-masked]>
Date: Fri, 4 Jan 2002 13:11:03 -0800

Long message follows. Executive summary: Exchange 2000 introduces a set of
"Batch" methods. I'm interested in the sense of the working group as to
whether we should work to provide a complete specification and advance it to
Proposed Standard.

-----------

As many of you know, Microsoft's Exchange 2000 email server provides WebDAV
access into its repository. Outlook Web Access uses WebDAV as its
on-the-wire protocol for remotely accessing an Exchange store. The following
white paper provides technical details on Outlook Web Access:

http://www.microsoft.com/exchange/techinfo/outlook/2000/E2K_OWA.doc

Outlook Web Access is among the most sophisticated uses of WebDAV to date, a
significant engineering accomplishment.

It is my understanding, based on discussions with some of the key developers
of Outlook Web Access, that several WebDAV-related performance issues were
encountered during development. In general, the problem was that it took too
long to perform operations such as "delete 50 messages from my inbox" or
"change the status of these 100 messages to 'read'".  Since the typical
hierarchical organization would make each folder a WebDAV collection, and
each email a Web resource, these operations translated into "issue 50
separate DELETE commands" and "issue 100 separate PROPPATCH commands". Depth
operations could not be used, since the operations were being performed on a
subset of a collection.

To address these performance issues, several "Batch" methods were developed
as relatively simple extensions to existing WebDAV methods. Switching
Outlook Web Access to use these methods resulted in approximately an order
of magnitude performance increase (obviously, the performance benefit of
going from N round-trips to 1 round trip depends on N). From the user
perspective, the observed elapsed time for executing an operation went from
multiple seconds down to close to a second (depending on latency, of
course). It was a signficant performance improvement. The batch methods are:

* BCOPY - batch COPY
* BMOVE - batch MOVE
* BDELETE - batch DELETE
* BPROPFIND - batch PROPFIND
* BPROPPATCH - batch PROPPATCH

Documentation on these methods can be found on the MSDN site, at:

http://msdn.microsoft.com/library/en-us/wss/wss/_webdav_methods.asp

You'll also see some methods listed which pertain to receiving event
notifications from the Exchange server. These are based on Josh Cohen's GENA
proposal, which was submitted to the IETF as an Internet-Draft, but was
never advanced to a Proposed Standard (in large part due to the absence of a
working group in the IETF charged with developing an event notification
standard).

http://www.cs.colorado.edu/~grunwald/MobileComputing/Papers/draft-cohen-gena
-p-base-00.txt

As Co-Chair, I certainly do not approve of the fielding of new,
unstandardized methods, since this leads to poor interoperability.  I also
do not approve of how these are labeled as "WebDAV Methods" on the MSDN
site, since it lends these methods an aura of standardization that they do
not, in fact, possess. But, as a pragmatist, I also recognize that in the
time it took me to write these words, several new Exchange 2000 servers came
online. The genie is out of the bottle.

The fact remains that the batch methods work, and they scale. They provide a
significant performance increase for an significant application of WebDAV.
The specificationof these methods, as provided on the MSDN site, is pretty
good (though they omit issues such as how to handle partial
success/failure). It would not surprise me if, in time, other applications
of WebDAV encountered the same performance problem, and desired a similar
solution.

As a result, I am interested in whether the working group has an interest in
working to fully flesh-out the specification of the batch methods, and
advance this specification to Proposed Standard.

- Jim

---

From: Greg Stein <[email-masked]>
Date: Mon, 7 Jan 2002 18:33:16 -0800

On Fri, Jan 04, 2002 at 01:11:03PM -0800, Jim Whitehead wrote:
>...

I wonder whether the performance suffered because the requests were
performed in a request/response fashion, rather than as a series of
pipelined requests. If you can pipeline requests, not waiting for an answer,
then a series of DELETE operations is simply a "larger request" and then you
handle a "larger response". Yes, each request/response has more overhead
than a batched operation.

Personally, I'm going to guess they didn't pipeline requests, so a batch
mechanism was a must to get around deficiencies in their protocol stack.

That said, it is important to recognize the overhead in a sequence of, say,
DELETE requests and their responses, relative to a potential batch
operation. Specifically, you're going to have a lot of duplicate headers on
the requests and responses (there are no bodies in this case). How much does
this pose over a batch delete with a list of URLs? Maybe 3x or 4x in the
number of bytes? Maybe 10x? When you're talking over a modem (which is
typically the case for MSFT's Hotmail servers), then that 10x can be rather
significant.

Ah, it's all a numbers game. Personally, I'm not interested in batch
operations. I would guess that most of their benefit is obviating by
pipelining requests.

Cheers,
-g

ps. yes, this is mostly supposition; I'm not about to sit down and start
measuring byte counts and network traffic; I don't know whether they were or
were not pipelining; but my intuition tells me "no" and that pipelining is
the answer...

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

---

From: "Julian Reschke" <[email-masked]>
Date: Tue, 8 Jan 2002 11:53:27 +0100

Greg,

if I understand you correctly you say that issuing all requests at the same
time (without waiting for the responses) will help to reduce the
communications overhead.

Yet, the *server* will still see separate requests, and at this point it
would be hard to actually detect that all these requests have something in
common and may be internally optimized (for instance by doing just one
instead of many calls to the database).

I think that if there are common operations that involve multiple resources
at once, it makes sense to define the protocol such that the server can
optimize the execution...

Julian

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Greg Stein
> Sent: Tuesday, January 08, 2002 3:33 AM
> To: Jim Whitehead
> Cc: WebDAV
> Subject: Re: Interest in standardizing Batch methods?
>
>

---

From: "Lisa Dusseault" <[email-masked]>
Date: Tue, 8 Jan 2002 21:29:55 -0800

> mechanism was a must to get around deficiencies in their protocol stack.

There's potentially a little more to it than that.
(1) Imagine a client selects a bunch of resources and drags to move them all
to a different folder.  A batch MOVE operation can do those in one
transaction, so that the whole request fails if not all can be moved.  This
becomes rather more important if the client is actually using an API
(MSDAIPP??) that offers large-scope operations, yet how can it guarantee
that operation will work or won't work if it can only send it piecemeal to
the server?

(2) See Yaron's email
(http://lists.w3.org/Archives/Public/w3c-dist-auth/1998OctDec/0303.html)
about why pipelining doesn't always work (can't always be used even when
available).  I don't know to what extent pipelining is realistically
unavailable/unworkable.

That said, it's still not clear batch methods are so necessary they'd
preempt other work we've got to do.

Lisa

---

From: "Lisa Dusseault" <[email-masked]>
Date: Tue, 8 Jan 2002 21:39:06 -0800

> instead of many calls to the database).

The HTTP 1.1 spec (RFC2616) isn't very clear on how servers are supposed to
handle pipelined requests, other than it must return the responses in the
same order as the requests.  However, it would seem very dangerous to try to
detect whether a bunch of pipelined requests can be optimized.  Might that
not have a different end-result than if they were handled one-by-one?  Could
the first PROPPATCH in a pipeline trigger an event which causes a later
PROPPATCH in the same pipeline to behave differently, were it to be handled
independently?  This is not just my worry -- it's also in Krishnamurthy and
Rexford (Web Protocols and Practice).

WP&P also points out that
 - pipelined requests suffer from head-of-line blocking, while multiple
requests over separate cxns does not
 - a closed connection is more severe when pipelining is used because the
client must remember a lot more state to recover from the closed connection

Lisa

---

From: "Julian Reschke" <[email-masked]>
Date: Wed, 9 Jan 2002 09:33:54 +0100

Looking at RFC2616:

"8.1.2.2 Pipelining
A client that supports persistent connections MAY "pipeline" its requests
(i.e., send multiple requests without
waiting for each response). A server MUST send its responses to those
requests in the same order that the requests
were received.
Clients which assume persistent connections and pipeline immediately after
connection establishment SHOULD be
prepared to retry their connection if the first pipelined attempt fails. If
a client does such a retry, it MUST NOT
pipeline before it knows the connection is persistent. Clients MUST also be
prepared to resend their requests if the
server closes the connection before sending all of the corresponding
responses.
Clients SHOULD NOT pipeline requests using non-idempotent methods or
non-idempotent sequences of methods
(see section 9.1.2). Otherwise, a premature termination of the transport
connection could lead to indeterminate
results. A client wishing to send a non-idempotent request SHOULD wait to
send that request until it has received
the response status for the previous request."

So it seems that pipelining wouldn't be allowed for anything except PROPFIND
(MOVE/DELETE/PROPPATCH aren't idempotent), right?

> [mailto:[email-masked]]On Behalf Of Lisa Dusseault
> Sent: Wednesday, January 09, 2002 6:30 AM
> To: Greg Stein; Jim Whitehead
> Cc: WebDAV
> Subject: RE: Interest in standardizing Batch methods?
>
>
>

---

From: "Pill, Juergen" <[email-masked]>
Date: Wed, 9 Jan 2002 17:12:13 +0100

Hello,

We would like to have a BATCH method too, beside possible performance
improvements, we would benefit from transaction handling. The BATCH method
could specify that all requests should be executed within a transaction.
I want to suggest instead of introducing a series of Bxxx methods, to
introduce only a single method named BATCH, which caries a series of WebDAV
methods within his XML body. This would allow to execute a scenario within a
transaction (e.g. lock, put, proppatch, unlock). Multiple delete methods
would be covered by this approach too.
The BATCH XML body would be able to specify headers on a general level
(identical to all contained methods) and specific headers for a single
method only.

This BATCH method would open the door into a BATCH language, e.g. execute
request #2 only if request #1 results in a 200/OK response code.

Best regards,

Juergen Pill

P.S. from the client programming perspective I would prefer the batch
possibility to the pipelining feature due to programming effort.

 -----Original Message-----
From: 	Clemm, Geoff [mailto:[email-masked]] 
Sent:	Wednesday, January 09, 2002 16.17 PM
To:	WebDAV
Subject:	RE: Interest in standardizing Batch methods?

A single MOVE, DELETE, or PROPPATCH request is idempotent
(repeating the same request multiple times produces the
same result as just doing it once).
A sequence of DELETE's is always idempotent.  A sequence of PROPPATCH's
is always idempotent if the same property isn't updated by different
PROPPATCH requests in that sequence.  A sequence of MOVE's is always
idempotent if none of the Destination URLs overlap with any of the
request URL's.

Cheers,
Geoff

-----Original Message-----
From: Julian Reschke [mailto:[email-masked]]
Sent: Wednesday, January 09, 2002 3:34 AM
To: Lisa Dusseault; Greg Stein; Jim Whitehead
Cc: WebDAV
Subject: RE: Interest in standardizing Batch methods?

Looking at RFC2616:

"8.1.2.2 Pipelining
(see section 9.1.2).

---

From: "Matt Timmermans" <[email-masked]>
Date: Wed, 9 Jan 2002 11:58:46 -0500

> [mailto:[email-masked]]On Behalf Of Pill, Juergen
> [...]
> [...]

This is very powerful if you do it properly.  The lack of any transaction
control in WebDAV currently makes it impossible to perform many operations
safely.  If a document has a property that lists its contributing authors,
for example, you can't add a name to that list unless you know that noone
else will be doing the same thing concurrently.

Obviously, you can't allow clients to separately start and stop
transactions, so you have to get them to send the whole transaction in a
batch.  The batch must express the semantics of the transaction, so it's
tempting to include a Turing complete batch language.  That is evil, though,
because then a batch may consume unbounded resources.

I've looked into this somewhat, however, and determined the minimum
functionality required by the batch language to allow any arbitrary
operation to be performed by the client safely.  The minimal requirements
are:

1) any request that can be performed outside of a batch can be sent inside a
batch; and

2) the batch can be aborted if any queried persistent state does not match
some given, expected value.

3) the client is informed when a batch is aborted because of condition (2).

To perform a safe update to the contributors list, for example, a client can
do this:

1) PROPFIND to get the list of contributors (oldlist)

2) BATCH:
PROPFIND to get the list of contributors (oldlist')
ABORT if oldlist' != oldlist
PROPPATCH contributors = oldlist+newname

3) If batch aborted due to the condition, go back to step 1.

---

From: "Julian Reschke" <[email-masked]>
Date: Wed, 9 Jan 2002 18:34:21 +0100

Matt,

I think this is definitively going to be too ambitious.

We really should start collecting the requirements first (as Jim did).

If the problem you're trying to solve is an update of a structured
(multivalued) property, you could do this by LOCKing the resource now.

A lightweight protocol that doesn't need LOCKs could be defines like:

- define a "PTag" (comparable to the ETag) that changes when properties
change,
- extend the request body to PROPPATCH to optionally include the PTag you
have and  only do the PROPPATCH if the PTag is still valid)
- alternatively, extend DAV:set to marshall a reference value to which the
current value is compared before updating the property.

For instance:

<conditional-set xmlns="DAV:">
  <old>oldvalue</old>
  <new>newvalue</new>
</conditional>

Julian

> [mailto:[email-masked]]On Behalf Of Matt Timmermans
> Sent: Wednesday, January 09, 2002 5:59 PM
> To: 'Pill, Juergen'; 'WebDAV'

---

From: Daniel Brotsky <[email-masked]>
Date: Wed, 9 Jan 2002 08:15:30 -0800

At 9:29 PM -0800 1/8/02, Lisa Dusseault wrote:
>... A batch MOVE operation can do those in one

I'm really glad you brought this up, Lisa.  It's basically the 
"transactional server needs transaction boundaries" issue, and it 
points out a common and important difficulty inherent in broad 
standards: if you specify a transactional protocol then it doesn't 
allow for simple implementations (which can be quite useful), but if 
you don't specify a transactional protocol then people who implement 
transactional client/server pairs need extensions that provide 
missing features.

In general, I think you need a layered protocol model (such as what's 
happening with DAV and delta-V) to satisfy both camps. 
Unfortunately, the base DAV protocol wasn't really well-designed to 
have transactions layered on top of it, because even single 
operations (such as DELETE) aren't required to have transactional 
semantics.

I would certainly be interested in working on a transactional 
DAV-based protocol (delta-t ? :^), although I agree with Lisa it 
ranks behind a number of other issues in base DAV (and ACL and 
delta-V) itself.  I wouldn't, however, be interested in adding 
batch-oriented calls to base DAV: while I completely understand 
Microsoft's use of extensions like this, and while Adobe does the 
same kind of thing (e.g., specialized headers to handle the 
difference between "unlock and advance taskflow" versus "unlock but 
don't affect taskflow"), adding batch operations to WebDAV feels much 
more like an appropriate application-specific patch than the basis 
for a good general-purpose transactional extension.

     dan
-- 
Daniel Brotsky, Adobe Systems
tel 408-536-4150, pager 877-704-4062
2-way pager email: <mailto:[email-masked]>

---

From: "Jim Whitehead" <[email-masked]>
Date: Wed, 9 Jan 2002 09:57:44 -0800

> preempt other work we've got to do.

I agree that other work, especially the revision of RFC 2518, has higher
priority than this.  But, since we'll be revising our charter soon, I was
mostly interested to see if it should be added as a charter to-do item.

- Jim

---

From: "Matt Timmermans" <[email-masked]>
Date: Wed, 9 Jan 2002 13:42:41 -0500

> [mailto:[email-masked]]On Behalf Of Julian Reschke
>
> Matt,
>

Possibly, but I believe it's the simplest and least dangerous solution that
allows you to perform arbitrary compound operations with ACID semantics.

> We really should start collecting the requirements first (as Jim did).

Personally, I think it should be a requirement that you can perform
arbitrary operations with ACID semantics.  If you can't, then WebDAV is
unsafe for many applications.  The problem is that it can still be, and will
be, used for those applications.

But, of course, if noone else feels that way, then it's not a requirement,
and we needn't worry about it.

> (multivalued) property, you could do this by LOCKing the resource now.

That was the example, but there are an infinite variety of others that
aren't restricted to a single resource, or just to properties.

Most of these cannot be done with locking.

> current value is compared before updating the property.

Both of these only work for operations on a single resource, and the PTag
can be very expensive to calculate.

It probably is overkill to support a full execute-and-compare-results, but
you can get the same functionality (for WebDAV) with a simple ASSERT method
that only needs to be able to perform a few simple checks -- to confirm that
a given property on a given resource has a given value, to confirm that a
given resource exists or not, to confirm that an entity body hasn't changed
(using etag if available), and to confirm the OPTIONS response of a given
resource.

If we're going to do transactional BATCH, then this is a very small price to
pay to get real transactional semantics.

---

From: Erik Seaberg <[email-masked]>
Date: 09 Jan 2002 10:52:33 -0800

> request #2 only if request #1 results in a 200/OK response code.

RFC 2616 already has a (non-XML) encoding for a series of requests or
responses, and each request could have an ID that dependent requests
can check the state of:

	BATCH * HTTP/1.1
	Host: www.example.com
	Content-Type: application/http
	Transfer-Encoding: chunked
	
	141
	MKCOL /foo HTTP/1.1
	Host: www.example.com
	Request-Id: <cid:[email-masked]>
	Authorization: Digest response="..."
	
	PUT /foo/bar HTTP/1.1
	Host: www.example.com
	Content-Type: text/plain
	Authorization: Digest response="..."
	If: <cid:[email-masked]> (["2xx"])
	
	hello world
	
	0

Microsoft's approach of applying a common request to each of several
resources also handles the basic performance problem and is probably
simpler to implement, though moving it from custom bodies up to HTTP
(for example, use "*" as the Request-URI and put a list of resources
in a "Request-URIs:" header) would make it more reusable.

---

From: Daniel Brotsky <[email-masked]>
Date: Wed, 9 Jan 2002 15:45:48 -0800

>mostly interested to see if it should be added as a charter to-do item.

I would say "yes" if you phrase it in terms of general 
transactionality, not batch operations in particular.

     dan

---

From: "Eric Sedlar" <[email-masked]>
Date: Wed, 9 Jan 2002 17:59:39 -0800

I agree that BATCH methods should be added to the charter.

> [mailto:[email-masked]]On Behalf Of Jim Whitehead
> Sent: Wednesday, January 09, 2002 9:58 AM
> To: WebDAV

---

From: "Clemm, Geoff" <[email-masked]>
Date: Fri, 11 Jan 2002 09:24:55 -0500

I see no evidence of a BATCH method or a Request-Id header in my
copy of 2616.  Could you indicate what sections of 2616 you are
referring to?

Thanks,
Geoff

-----Original Message-----
From: Erik Seaberg [mailto:[email-masked]]
Sent: Wednesday, January 09, 2002 1:53 PM
To: [email-masked]
Subject: Re: Interest in standardizing Batch methods?

	BATCH * HTTP/1.1
	Host: www.example.com
	
	141
	MKCOL /foo HTTP/1.1
	Host: www.example.com
	
	PUT /foo/bar HTTP/1.1
	Host: www.example.com
	Content-Type: text/plain
	
	hello world
	
	0

---

From: Erik Seaberg <[email-masked]>
Date: 11 Jan 2002 10:24:31 -0800

> copy of 2616.  Could you indicate what sections of 2616 you are

Sorry I was unclear.  I only reused 2616's "application/http" media
type, rather than invent a new encoding for a sequence of HTTP
requests.  The BATCH method and Request-Id header I suggested are new
(Content-Id could also be used in a multipart with a "message/http"
body for each request).