Subject: Using OPTIONS for optional feature discovery -- advice

From: Lisa Dusseault <[email-masked]>
Date: Tue, 20 Apr 2004 18:21:15 -0700

I am working on the next version of the HTTP PATCH method proposal:
http://www.ietf.org/internet-drafts/draft-dusseault-http-patch-00.txt

We've had some discussions amongst WebDAV people of the best way for 
clients to discover server feature support.  In this case, the client 
wants to discover:
  - if the server supports PATCH at all
  - if so, what delta or diff formats can be used on this resource.

For that purpose, is a new header on OPTIONS still considered to be the 
way to go?  Can a server omit this header on responses to OPTIONS * if 
it only supports the feature in part of its namespace?  (E.g. if a java 
servlet supplies support for this feature only in the namespace hosted 
by that servlet)

Any other comments on the draft are welcome as well.

Thanks,
Lisa Dusseault

---

From: Scott Lawrence <[email-masked]>
Date: Tue, 20 Apr 2004 22:39:02 -0400

> servlet supplies support for this feature only in the namespace hosted 

00>            Partial Document Changes (PATCH Method) for HTTP
00>                     draft-dusseault-http-patch-00

00> 1. Introduction
00>...
00>   Note that byte ranges are already used in HTTP to do partial
00>   downloads (GET method).   However, they are not defined for uploads,
00>   and there are some missing pieces for uploads. For example, the HTTP
00>   specification has no way for the server to send errors if the byte
00>   range in a PUT is invalid. Byte ranges could be made to work in this
00>   specification but they're not the only way to do partial
00>   modifications.  Since reliable and tested patch algorithms already
00>   exist, those are preferred.

Just a comment here... the Range mechanism can (theoretically at least)
operate on units other than bytes, and can do multiple ranges.  I
think that it could be used for the sort of thing you envision, but I
agree that a patch-like mechanism is probably more robust.

00> 2.1 PATCH Method
00>...
00>   PATCH bodies are not cachable.  A cache MAY mark the resource
00>   identified in the Request-URI as stale if it sees a successful
00>   response to the PATCH request.

I think that what you want to say here is that PATCH _request_ bodies
MUST NOT be cached.  Whether or not the response can be cached depends
on the nature of the response, and the server has available ways to
control whether or not it can be cached.

00>   The PATCH request MUST have a body.  [...]
00>                                        The PATCH request MUST also use
00>   one of the standard HTTP/1.1 mechanisms that let the server know when
00>   the request body is done. The PATCH request body length MUST NOT be
00>   indicated only by closing the connection when the body is complete,
00>   because an incomplete PATCH body could conceivably corrupt the target
00>   resource.

That is confusing, and needn't be said at all - it's never valid to
terminate a _request_ body by closing the connection - only a response
body.

00> 2.4 Advertising Support in OPTIONS: Patch header

00>   The server advertises its support for the features described here
00>   with an OPTIONS response header, sent on OPTIONS requests for any
00>   resource.  The Patch header on any OPTIONS response indicates that
00>   the server supports the PATCH method and at least one delta format.
00>   When the OPTIONS request addresses a specific modifiable resource,
00>   the Patch header in the response indicates which delta formats may be
00>   used for this specific resource.  When an OPTIONS request addresses
00>   the server as a whole (Request-URI = "*") the Delta header in the
                                                    ^^^^^ - Patch?
00>   response indicates the union of all delta formats supported by the
00>   server.                             ^^^^^-patch?

There is already a way to advertise support for a method - the 'Allow'
header (rfc2616#14.7), which may be sent on any response.  For an
'OPTIONS' request whose request-uri was '*', the Allow header can
refer only to the server as a whole, which doesn't tell you whether or
not a method in the Allow header will be acceptable for any particular
URI (just as you describe above); for that you need to probe the URI
that you're interested in, either with OPTIONS or some other method.
In a WebDAV context, where multiple requests for the same resource are
common, I would think that there would often be an opportunity to
piggyback this on something else.

I'd also suggest that for clarity you use 'Accept-Patch' as the
response header to indicate what patch types are supported by the
server.

So your first example:

00>   OPTIONS request and response indicating Patch support

00>       [request]

00>       OPTIONS * HTTP/1.1
00>       Host: www.example.com

00>       [response]

00>       HTTP/1.1 200 OK
00>       Patch: application/gdiff, text/xcap+xml

should, I think, be:

          [request]

          OPTIONS * HTTP/1.1
          Host: www.example.com

          [response]

          HTTP/1.1 200 OK
          Allow: PATCH, ...
          Accept-Patch: application/gdiff, text/xcap+xml

and a specific use case:

      [request]

          OPTIONS /foo/bar.xml HTTP/1.1
          Host: www.example.com

      [response]

          HTTP/1.1 200 OK
          Allow: PATCH, GET, HEAD, PUT, OPTIONS, TRACE
          Accept-Patch: text/xcap+xml

and a PUT example showing that the capability can be passed with
another response:

      [request]

          PUT /foo/bar.xml HTTP/1.1
          Host: www.example.com

      [response]

          HTTP/1.1 201 Created
          Allow: PATCH, GET, HEAD, PUT, OPTIONS, TRACE
          Accept-Patch: text/xcap+xml
          Etag: "xi30qkd0a"

-- 
Scott Lawrence        
  Pingtel Corp.   
  sip:slawrence {at} pingtel.com  
  +1.781.938.5306 x162

---

From: Jamie Lokier <[email-masked]>
Date: Wed, 21 Apr 2004 04:39:59 +0100

> agree that a patch-like mechanism is probably more robust.

PUT with a byte range would be useful in another context: "resume upload".

Although PUT with multiple byte ranges could be used for partial
patch-like modifications, that doesn't offer any way to insert or
delete regions so as to move other parts of the file, or to truncae
the file.  The byte range syntax could be extended, but I don't see
the point.

-- Jamie

---

From: Julian Reschke <[email-masked]>
Date: Wed, 21 Apr 2004 10:45:52 +0200

>  - if the server supports PATCH at all

That's "Allow".

>  - if so, what delta or diff formats can be used on this resource.

I think we shouldn't put this into OPTIONS. It can easily be sent back 
as response to a PATCH request with missing content-type. In which case 
there wouldn't be any change at all for OPTIONS.

> Any other comments on the draft are welcome as well.

I don't see how the set of accepted content types can be ever relevant 
for the whole namespace. In practice, clients will never be able to rely 
on all resource on a server to provide the very same feature set, thus 
will have to discover that on the resource being PATCHed anyway.

Julian

-- 
<green/>bytes GmbH -- http://www.greenbytes.de -- tel:+492512807760

---

From: Julian Reschke <[email-masked]>
Date: Wed, 21 Apr 2004 10:48:15 +0200

Lisa Dusseault wrote:

> ...
> ...

The discussion is captured here:

<http://lists.w3.org/Archives/Public/w3c-dist-auth/2003OctDec/0218.html>

Regards, Julian

---

From: Mark Nottingham <[email-masked]>
Date: Mon, 26 Apr 2004 20:51:56 -0700

Just curious - does anyone know of OPTIONS being used "in the wild" at 
all?

If so, how?

On Apr 20, 2004, at 6:21 PM, Lisa Dusseault wrote:

> For that purpose, is a new header on OPTIONS still considered to be 
> the way to go?  Can a server omit this header on responses to OPTIONS 
> * if it only supports the feature in part of its namespace?  (E.g. if 
> a java servlet supplies support for this feature only in the namespace 
> hosted by that servlet)
>

--
Mark Nottingham     http://www.mnot.net/

---

From: Julian Reschke <[email-masked]>
Date: Tue, 27 Apr 2004 09:04:52 +0200

Mark Nottingham wrote:
> 
> Just curious - does anyone know of OPTIONS being used "in the wild" at all?
> 
> If so, how?

OPTIONS is used quite heavily by WebDAV clients for feature discovery. 
They usually use both the Allow header and the DAV-specific "Dav" header 
(<http://greenbytes.de/tech/webdav/rfc2518.html#HEADER_DAV>).

Julian

---

From: Jamie Lokier <[email-masked]>
Date: Tue, 27 Apr 2004 08:42:20 +0100

> (<http://greenbytes.de/tech/webdav/rfc2518.html#HEADER_DAV>).

OPTIONS is also used in principle for "Upgrading to TLS Within
HTTP/1.1" (RFC2817).  I don't know if it's actually deployed.

-- Jamie

---

From: Stefan Eissing <[email-masked]>
Date: Tue, 27 Apr 2004 09:56:20 +0200

> HTTP/1.1" (RFC2817).  I don't know if it's actually deployed.

It is also used when clients have to make a cheap call without side 
effects.
For example in order to trigger authentication before making other 
requests
which are either expensive or cannot be repeated.

Another example is the infamous NTLM authentication scheme which 
requires
at least two requests per new connection.

//Stefan

---

From: Scott Lawrence <[email-masked]>
Date: Tue, 27 Apr 2004 07:02:02 -0400

> HTTP/1.1" (RFC2817).  I don't know if it's actually deployed.

That mechanism is used by many IPP printers for the secure mode.
-- 
Scott Lawrence <[email-masked]>

---

From: Lisa Dusseault <[email-masked]>
Date: Tue, 27 Apr 2004 09:40:43 -0700

At Xythos we sometimes logged the traffic going to Sharemation (a 
WebDAV/Web server) and found a significant number of OPTIONS requests 
-- probably the most common after PROPFIND and GET.

In researching my WebDAV book I found that Microsoft Office (using 
Network Places or the MSDAIPP agent) uses many OPTIONS requests to 
confirm that the server is reachable and supports WebDAV, before 
attempting to PROPFIND in some situations.  Also, "cadaver" uses 
OPTIONS to detect WebDAV support and log the user in before attempting 
PROPFIND.  There are partial traces of these interactions in chapter 8 
of my book.

Lisa

---

From: Justin Chapweske <[email-masked]>
Date: Wed, 28 Apr 2004 16:26:39 -0500

Hello Lisa,

Could you please expound upon the reasons why PUT with a Content-Range
is a dangerous operation?  In your draft you state:

   The PUT method is already defined to overwrite a resource with a
   complete new body, and MUST NOT be reused to do partial changes.
   Otherwise, proxies and caches and even clients and servers may get
   confused as to the result of the operation.

But it is not clear to me why this is a problem.  I would appreciate
your thoughts on this issue, and it may be worthwhile to expound upon it
a bit in your draft.

Thanks,

-Justin

-- 
Justin Chapweske - Founder, Onion Networks
http://onionnetworks.com/
651-340-8787
 
Transfer large files 900% faster than FTP with Onion Networks' WAN
Transport(tm).  http://onionnetworks.com/products_wantransport.php

---

From: Lisa Dusseault <[email-masked]>
Date: Wed, 28 Apr 2004 14:41:51 -0700

I do mention one reason in the draft -- the problem of write-through 
caches.  The cache (if an intermediary) could see a PUT with a body and 
save the body as the new body for the resource, even though the PUT 
request body is only a diff or content range.  Greg Stein expressed 
this better than me: PUT works a certain way, and has been known to 
work a certain way for at least a decade, and it's very difficult to 
change its semantic meaning without breaking things.

Another concern I have is that HTTP servers that allow PUT may ignore 
the Content-Range header since it's not defined as a PUT header.  This 
is even worse -- the authoritative source will then replace the full 
resource with a corrupted, partial resource.  I suspect clients have 
tried this already and found it not to work in practice.  Similarly, 
HTTP servers that support PUT today simply won't understand a new 
header defined in an extension draft.  It *might* work for the client 
to ask the server for support for the header on the specific resource 
that the client would like to alter, before using PUT -- but that 
wouldn't solve the intermediary or cache misunderstanding problems.

Lisa

---

From: Alex Rousskov <[email-masked]>
Date: Wed, 28 Apr 2004 15:49:10 -0600 (MDT)

On Wed, 28 Apr 2004, Lisa Dusseault wrote:

> request body is only a diff or content range.

Does anybody know of any implementation that caches PUT bodies?

Alex.

---

From: Jamie Lokier <[email-masked]>
Date: Wed, 28 Apr 2004 23:16:23 +0100

> Does anybody know of any implementation that caches PUT bodies?

I don't know.
It would be a violation of RFC 2616 (HTTP/1.1) section 13.10 though:

   In this section, the phrase "invalidate an entity" means that the
   cache will either remove all instances of that entity from its
   storage, or will mark these as "invalid" and in need of a mandatory
   revalidation before they can be returned in response to a subsequent
   request.

   Some HTTP methods MUST cause a cache to invalidate an entity. This is
   either the entity referred to by the Request-URI, or by the Location
   or Content-Location headers (if present). These methods are:

      - PUT
      - DELETE
      - POST

RFC 1945 (HTTP/1.0) does not say anything like this.  It does say that
GET and HEAD responses can be cached, and POST responses must not be,
neither must responses with Authorization.  HTTP/1.0 doesn't have
anything explicit to say about the cacheability of PUT, so an
implementation might conceivably have done it.

-- Jamie

---

From: Alex Rousskov <[email-masked]>
Date: Wed, 28 Apr 2004 16:25:45 -0600 (MDT)

> It would be a violation of RFC 2616 (HTTP/1.1) section 13.10 though:

Yes, that is why I have doubts that "ranged PUT" is dangerous for the
reasons cited above. There may be other reasons, of course. And even
if ranged PUT is safe, there may be reasons to use a PATCH method.
Nevertheless, rationale should reflect reality.

Alex.

---

From: Greg Stein <[email-masked]>
Date: Wed, 28 Apr 2004 16:27:47 -0700

> request body is only a diff or content range.  Greg Stein expressed

Right. The intermediaries aren't *supposed* to do that, but if one does...
BAM. You're SOL.

> the Content-Range header since it's not defined as a PUT header.  This

And in fact, a good number of them *do* ignore the header. When the Apple
guys were building their DAV filesystem client, they ran into this
problem. And it is a major pain -- if an app changes a single byte, you
really don't want to have to do a PUT on that entire 3 gig file. I'm not
sure what solution they ended up with, but the general solutions says that
you cannot trust a proper response from the server.

Now, the HTTP spec says that an unhandled and/or not-understood Content-*
header should generate an error response. Most servers don't follow that
requirement, however. IIS/6 and Apache certainly don't. (I just tested the
former against www.microsoft.com, and I already know Apache doesn't)
So... since a server isn't going to punt on an unhandled Content-Range,
then you really can't rely on just sending it and assuming the server will
fail back to you if it doesn't understand it.

> tried this already and found it not to work in practice.  Similarly,

Yep and yep.

> wouldn't solve the intermediary or cache misunderstanding problems.

Agreed, especially given the problems around proper Content-* header
handling. IMO, we simply need a new method designed which explicitly
accounts for these different behaviors (along with definitions for
intermediaries' handling).

Cheers,
-g

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

---

From: Jim Luther <[email-masked]>
Date: Thu, 29 Apr 2004 10:53:24 -0500

On Apr 28, 2004, at 4:41 PM, Lisa Dusseault wrote:

> caches.  The cache (if an intermediary) could see a PUT with a body 
> and save the body as the new body for the resource, even though the 
> PUT request body is only a diff or content range.  Greg Stein 
> expressed this better than me: PUT works a certain way, and has been 
> known to work a certain way for at least a decade, and it's very 
> difficult to change its semantic meaning without breaking things.
>

> you cannot trust a proper response from the server.

<http://lists.w3.org/Archives/Public/ietf-http-wg/1997OctDec/0011.html> 
gives the reason why PUT-RANGE wasn't left in the HTTP 1.1 
specification and 
<http://www.w3.org/Protocols/HTTP/Issues/BeforeLastCall.html#PUT-RANGE> 
is where PUT-RANGE was officially removed from Rev-02 of the HTTP 1.1 
spec.

Yes, Apple's WebDAV file system client still has to deal with the 
performance problems of not having better range operations. When a 
large resource is  opened, modified and closed by a file system client, 
the entire resource has to be downloaded with a GET and then 
re-uploaded to the server with a PUT -- even if just a single byte is 
changed.

I like the PATCH proposal because it provides clients with:

1 - The ability to change the size of a resource independent or in 
addition to changing the data. PUT doesn't do this unless you change 
the current meaning of the byte-content-range-spec passed in a 
Content-Range header so that */100 means "set the length of the 
resource to 100 -- truncate the resource if its current length is more 
than 100, zero extend the resource if its current length is less than 
100".

2 - The ability to change multiple ranges and optionally the size of a 
resource with a single request. On high latency connections, our 
performance problems are often causes by the number of transactions, 
not the amount of data transfered.

---

From: Alex Rousskov <[email-masked]>
Date: Thu, 29 Apr 2004 10:32:03 -0600 (MDT)

> than 100, zero extend the resource if its current length is less than

How does PATCH proposal allow to separate data from its size?

I was always thinking that in HTTP world the "size of the resource"
and "size of [resource] data" are always the same. That is, "size" is
not a property that can be changed without changing resource
content/data. Can you clarify why would you want to separate the two
concepts and would "zero" definition depend on content type or patch
format?

> 2 - The ability to change multiple ranges [...] with a single
> request.

Multi-hunk patches are indeed very useful to support atomic updates.
draft-dusseault-http-patch-01 does not seem to have error codes
related to situations where some of the patch hunks failed while
others succeeded. Are all updates assumed to be atomic (i.e., all or
nothing)? Should this assumption be made explicit? Sorry if I missed
it in the draft.

Thanks,

Alex.

---

From: Lisa Dusseault <[email-masked]>
Date: Thu, 29 Apr 2004 09:38:43 -0700

Updates should be atomic -- the entire patch should be applied or 
entirely failed.  I will make that explicit.  Thanks!

Lisa

---

From: Jim Luther <[email-masked]>
Date: Thu, 29 Apr 2004 12:49:57 -0500

> concepts and would "zero" definition depend on content type or patch

I meant that you could change the size of a resource without resending 
its existing content. For example, to truncate a resource to just the 
first 100 bytes of its current content, this gdiff command could be 
sent:

	0xd1, 0xff, 0xd1, 0xff
	4
	249,0,0,100
	0

Extending a resource without resending its existing content can be 
accomplished with a gdiff copy command (to copy the existing resource 
content) followed by a data command with the new data to be appended.

> nothing)? Should this assumption be made explicit? Sorry if I missed

Yes, I agree that updates should be atomic. On many current HTTP 
servers PUT is not atomic, and so a GET during an in-progress PUT will 
return just the portion of the resource already sent to the server.

---

From: Alex Rousskov <[email-masked]>
Date: Thu, 29 Apr 2004 12:03:56 -0600 (MDT)

On Thu, 29 Apr 2004, Lisa Dusseault wrote:

> entirely failed.  I will make that explicit.

You may want to note in the draft that, in many cases, the atomicity
requirement is expensive because it requires copying the entire
content or "trying to patch" first, before actually patching, while
holding the file lock.

To avoid copying, a special --dry-run feature of the library/program
that supports the given patch format would be needed. In fact, as the
"internal error" part of the example below illustrates, copying may
always be required for safe operation when the patch library/program
does not guarantee atomicity:

	lock
	if patch --dry-run
	then
		if patch
		then
			unlock
			report success
		else
			internal error!
			revert to original content?
			...
		fi
	else
		unlock
		error, report to the client
	fi

Alex.

---

From: Justin Chapweske <[email-masked]>
Date: Thu, 29 Apr 2004 17:08:28 -0500

Related to this, does the gdiff format allow you to succinctly describe
a remote random-access write type operation?

It seems to me that there will be two main ways in which PATCH will be
used:

o The traditional diff/patch approach where complete copies of the old
and new versions of the files are compared to extract a diff.  The diff
is then PATCHed to the HTTP resource.

o Real-time edits and random-access I/O ala NFS.  It should be simple to
express actions such as:

  - Write bytes at a given offset, including scattered writes

  - Append to the end of a file (already covered)

  - Skip beyond the end of the file and write some bytes, leveraging
support for file system "holes" if supported by the server.

  - Truncate the file to a given length, including 0. (already covered)

I would guess that some WebDAV clients that are implemented as file
system drivers may tend to prefer the second approach, especially if
operating over low-latency networks.

This brings up another issue.  With the second style of PATCHing, the
suggestion that "   The server SHOULD provide a MD5 hash of the content
after the delta
   was applied.  " becomes very onerous indeed since a bunch of small
writes to a huge file will result in an unacceptable performance hit.

In any case, I think it is important that the specification recommend a
delta format that can meet the needs of both diff/patch type usage as
well as remote random-access I/O patterns.

Thanks,

-Justin

 
Transfer large files 10x faster than FTP with Onion Networks' WAN
Transport(tm).  http://onionnetworks.com/products_wantransport.php

---

From: Alex Rousskov <[email-masked]>
Date: Thu, 29 Apr 2004 17:15:26 -0600 (MDT)

On Thu, 29 Apr 2004, Justin Chapweske wrote:

> This brings up another issue.  With the second style of PATCHing,
> the suggestion that "  The server SHOULD provide a MD5 hash of the
> content after the delta was applied.  " becomes very onerous indeed
> since a bunch of small writes to a huge file will result in an
> unacceptable performance hit.

Yes, and the performance hit can be unacceptable for the first kind of
patching as well. However, SHOULD level seems appropriate for this
case. The server is free to skip MD5 calculation for large files, for
example.

> In any case, I think it is important that the specification
> recommend a delta format that can meet the needs of both diff/patch
> type usage as well as remote random-access I/O patterns.

I am not sure I agree. Would it be better to provide a different
method for remote random-access I/O patterns? Random I/Os seem to have
different enough priorities and possibly different set of essential
operations to justify the increased complexity of morphing two content
modification methods together.

Thanks,

Alex.

---

From: Alex Rousskov <[email-masked]>
Date: Thu, 29 Apr 2004 17:19:21 -0600 (MDT)

On Thu, 29 Apr 2004, Jim Luther wrote:

> its existing content.

AFAIK, any sane/general diff format allows for that;  that's the key
difference between patching and replacing (and that does not make size
independent from content)!

Thanks,

Alex.

---

From: Lisa Dusseault <[email-masked]>
Date: Thu, 29 Apr 2004 16:22:54 -0700

> modification methods together.
I also have my doubts about random-access I/O support.  The HTTP/WebDAV
model is to do whole-resource operations, and since PATCH is all in one
method that still qualifies.  With WebDAV support, a client would be 
advised
to LOCK the resource and GET it, perform random-access I/O on the local
copy, then PUT/PATCH and UNLOCK the file.  Without WebDAV support,
client should do the same but using ETags rather than locks.

Lisa

---

From: Justin Chapweske <[email-masked]>
Date: Thu, 29 Apr 2004 18:36:48 -0500

> modification methods together.

I doubt that a different method is needed besides PATCH, but perhaps a
simple alternate diff format that can express these random-access I/Os
would be appropriate.

Honestly I don't know what the answer is since I have no expertise on
the specific diff/delta algorithms that are being discussed.  I would
just like to see a base-line format that can express these types of I/O
patterns in an easily implementable manner.

Thanks,

-Justin

---

From: Justin Chapweske <[email-masked]>
Date: Thu, 29 Apr 2004 18:52:10 -0500

> client should do the same but using ETags rather than locks.

The random-access patterns that I am suggesting would still operate as
an atomic whole-resource operation and using ETags could be implemented
very efficiently.

To give a motivating use-case, lets look at a memory and storage
constrained embedded device which wishes to access and modify some
resource that is larger than the available local storage.

This device may access some subset of the resource via Range requests,
and then may perform a number of random-access-style I/Os on the
resource.  

One reasonable implementation might be to keep an I/O log of all of the
operations that were performed on the resource.  Once the device is
finished with its modifications, the PATCH method would be issued with a
payload that is basically a replay of the local I/O log.  This approach
mitigates the need of the embedded device to store any information about
the original state of the file because it need not do a comparison after
the fact.  Additionally, the storage/memory requirements are directly
proportional to the number of new bytes written to the resource and
waiting to be flushed.

Again, I think the PATCH proposal is a good one, I'm just a bit nervous
that there aren't enough diverse use cases to make it applicable to a
large set of problems.

Thanks,

-Justin

---

From: Lisa Dusseault <[email-masked]>
Date: Thu, 29 Apr 2004 17:14:43 -0700

That's great, I see now we're on the same page, except that a new diff 
format ought
to be a completely separate standard from PATCH.  I'd also recommend 
that
somebody who really needs this first investigate to see if the local 
I/O log can
in fact be translated into gdiff (or other existing diff format) -- in 
which case
PATCH could already handle the use case.

Lisa

---

From: Alex Rousskov <[email-masked]>
Date: Thu, 29 Apr 2004 21:41:38 -0600 (MDT)

On Thu, 29 Apr 2004, Justin Chapweske wrote:

> One reasonable implementation might be to keep an I/O log of all of
> the operations that were performed on the resource.  Once the device
> is finished with its modifications, the PATCH method would be issued
> with a payload that is basically a replay of the local I/O log.

I would not call the above "random I/O" pattern because you are doing
a single fetch and a single patch operation as far as protocol is
concerned. The proposed PATCH method and even existing diff formats
seem to support the above use case reasonably well.

Can you think of any reason why PATCH with common diff formats cannot
support the above efficiently?

I was under impression that you are talking about supporting large
volume of micro updates (e.g., remove a single character in the middle
of a 100MB file) that must be committed in real time, one by one.
Doing so efficiently may require mechanisms different than proposed
PATCH.  However, your example seem to be within PATCH scope! Sorry if
I misunderstood the true meaning of the "random access I/O" term.

Thanks,

Alex.

---

From: Julian Reschke <[email-masked]>
Date: Fri, 30 Apr 2004 09:23:04 +0200

> simple alternate diff format that can express these random-access I/Os

Exactly.

It seems to me that the ability to map file operations directly to a 
PATCH format is essential. It will be extremely useful for all WebDAV 
clients that act as filesystem drivers (there are at least three 
different ones for Windows, one for Linux and one for OS/X).

Also, I think we should keep the number of REQUIRED patch formats 
minimal, and the ones that are indeed required should be dead simple tim 
implement. If there isn't a simple format to which file i/o (write 
bytes, seek, truncate) can be mapped, we should specify one.

Such as:

SEEK <bytes> (only positive offsets accepted, seeking beyond end of 
"document" appends zero bytes)
WRITE <bytes> <bytestream>
TRUNCATE

Example:

SEEK 1234<lf>
WRITE 5<lf>
abcde<lf>
TRUNCATE<lf>

would seek by 1234 bytes, write the bytes stream "abcde" (format is 
binary), then truncate at this position.

> patterns in an easily implementable manner.

Yep.

Best regards, Julian

---

From: Jamie Lokier <[email-masked]>
Date: Fri, 30 Apr 2004 09:22:42 +0100

> binary), then truncate at this position.

The gdiff format expressed these operations fairly straightforwardly.

Gdiff is just a sequence of "COPY n bytes from position m of original"
and "insert n DATA bytes b0,b1,...bn-1".

A random access write of n bytes to position p is expressed simply in
gdiff as:

    COPY 0,p
    DATA n,b0,b1,...,bn-1
    COPY p+n,length-p-n

The only difficulty for a filesystem driver is that it needs to know
the length before sending the PATCH command.

If the driver and server are using Etags anyway, to ensure the PATCH
applies to known content, then the driver will know the length.  Same
if it's using WebDAV-style locking.

However, Etags are often based on things like the MD5 of the file's
contents, which we don't want the server to have to recompute each time.

We should bear in mind that if we're trying to design a _good_
read-write file server protocol, a bit more thought needs to go into
the cacheing model.

-- Jamie

---

From: Julian Reschke <[email-masked]>
Date: Fri, 30 Apr 2004 10:52:29 +0200

> read-write file server protocol, a bit more thought needs to go into

Jamie,

my concerns are

- no standards-track documentation of GDIFF (as far as I understand)

and

- it seems to do more than we need.

Therefore the proposal to use a *very* simple format (pick one if it 
exists, otherwise invent one), put it into the PATCH specification and 
make that one (and only that one) mandatory.

Optimally, a reliable implementation of that format should be doable in 
one day.

Regards, Julian

---

From: Julian Reschke <[email-masked]>
Date: Fri, 30 Apr 2004 11:06:31 +0200

> - it seems to do more than we need.

...for instance, GDIFF requires random access to the old file, while a 
simpler format may work on plain streams...

Regards, Julian

---

From: Jamie Lokier <[email-masked]>
Date: Fri, 30 Apr 2004 10:30:24 +0100

> simpler format may work on plain streams...

That was my immediate concern when I read the GDIFF spec too.
On the other hand, the random access allows fragments of the old file
to be reordered.

Note that traditional "diff" and "patch" also require random access,
because their hunks needn't be in order.

I looked at VCDIFF (which is quite a nice principle).  It does the
same thing: random access is required.  Some attempt to reduce that is
done by allowing the patch to specify "windows" from the old file
which are operated on independently, in sequence.

I must admit I don't like that either: Gzip's sliding window with
bounded length seems, on the face of it, like it would be more
effective at compression (due to increased matching opportunities),
while keeping the access pattern requirements of the
patcher/decompressor bounded to a small region of the stream.

(Gzip also breaks the input stream into blocks, in sequence, but they
are much larger than the sliding window, so much larger than the memory
requirements of the decompressor (which would also be the patcher)).

-- Jamie

---

From: Justin Chapweske <[email-masked]>
Date: Fri, 30 Apr 2004 08:53:08 -0500

> support the above efficiently?

I was simply raising this as a possible use-case, and it is encouraging
to hear some initial reports that the existing diff algorithms may be
able to efficiently support these types of operations.

> I misunderstood the true meaning of the "random access I/O" term.

I think large volumes of micro-updates should be efficiently
implementable as well.  One might expect a WebDAV file system driver
operating across a LAN to work in this fashion.  I think as long as you
do without the Content-MD5, and avoid extra copying on the server-side,
you could end up with reasonably efficient large volume micro-updates.

However, semantically speaking, it probably isn't a good idea to PATCH
changes to a file while the file is in an unknown state - so I would
guess something like the write log mechanism might make a lot of sense.

What do the DAV file system driver guys think of this?  Apple?

Thanks,

-Justin

---

From: Jim Luther <[email-masked]>
Date: Fri, 30 Apr 2004 10:22:31 -0500

> What do the DAV file system driver guys think of this?  Apple?

In the current implementation of the Mac OS X WebDAV file system, 
opening a file on a WebDAV file server causes a GET and the resource is 
cached in a file on the root file system. While the file is open, all 
changes are made to the local cache file. The cache file (if changed) 
is pushed to the server with a PUT when the file system receives a 
fsync or close request. So most of the time, there is a single PUT when 
a file is changed on the server. Since the PUT replaces the complete 
resource, a file is always in a consistent state after the PUT is 
complete.

If PATCH were available, I'd have to decide whether to use the existing 
"cache file" model, or use the buffer cache used by the rest of the Mac 
OS X file systems. If I were to stick with the cache file model, then 
I'd keep track of what portions of the cache file have been changed and 
send a single PATCH request to the server when a fsync or close is 
received. If I were to switch to use the buffer cache, I'd send a PATCH 
request whenever memory pressure causes the buffer cache to write a 
file's dirty buffer(s) to the server. That would mean that the resource 
on the server might be in an inconsistent state at times -- this would 
not be different than other network file systems.

- Jim

---

From: Jeffrey Mogul <[email-masked]>
Date: Fri, 30 Apr 2004 15:31:49 -0700

From: Alex Rousskov <[email-masked]>

It would seem to me that, if the problem is the overhead required
for verifying the correct result of a long series of small writes,
then these two steps should be decoupled.

That is, each write could take place without require the generation
of a hash of the whole file, followed by a client-initiated operation
specifically requesting the hash ("now that I'm done with all of
those little writes").

NFS Version 3 did something analogous; instead of the fully
synchronous-to-stable-storage WRITE RPC operation in NFSv2,
NFSv3 allows (but does not require) the client to WRITE a
series of bufferable data to the server, followed by a COMMIT
RPC to force all buffered data (for the specified filehandle)
to stable storage.  This apparently gives big performance gains.

-Jeff