Subject: RE: multi-append
From: "Rubinstein, Dmitry" <[email-masked]>
To: IMAP Extensions WG <[email-masked]>
Date: Tue, 28 Sep 1999 22:36:19 +0300

> From: Barry Leiba [mailto:[email-masked]]
> Sent: Monday, September 27, 1999 3:50 PM
> To: IMAP Extensions WG
> Subject: Re: multi-append
> 
> > IMVHO, all the complexity of streaming commands is on the 
> client side. What
> > am I missing?
> 
> Why would the client do that (that is, what benefit would it 
> get from it)?
> The answer is that the benefit is overlapped execution of 
> commands.  

[explanation of why streaming commands is tricky on the server side is
skipped]

OK, I had to choose the phrasing more carefully. Please, allow me to
rephrase:

What DOES it mean to support streaming commands server side in context of
'streaming APPEND' vs. MULTI-APPEND? In either case the user will probably
be presented with some pop-up message box or some revolving sand clock or
whatever indication to the fact, that the client is currently involved in
time consuming operation. Unless there's a mechanism in MULTIAPPEND for
aborting the transfer? But how?...

In short, streaming commands is tricky. But not always. There's at least one
place where it seems to be OK, and that is multiple APPENDs.

--
Dmitry Rubinstein 

Date: Mon, 27 Sep 1999 09:49:45 -0400
From: Barry Leiba <[email-masked]>
Organization: Internet Messaging Technology; TR2_Xagent=WATSON
To: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Sender: [email-masked]

"Rubinstein, Dmitry" wrote:
> What DOES it mean to support streaming commands server side? I just can't
> see what can be different from non-streaming: you read one command at a time
> (assuming you can tell when a command is over and a new one begins,
> otherwise - goto RFC2060). Once a command is processed, you send a response
> and fetch another command.
> 
> IMVHO, all the complexity of streaming commands is on the client side. What
> am I missing?

Why would the client do that (that is, what benefit would it get from it)?
The answer is that the benefit is overlapped execution of commands.  For 
instance:

c: <user clicks a search dialogue>
c: 001 SEARCH BODY "frobozz"
c: <displays "searching..." indicator somewhere>
s: <accepts SEARCH command and starts searching>
c: <user clicks on message 5272>
c: 002 FETCH 5272 BODY[1]
s: * 5272 FETCH (BODY[1] {386}
...
s: 002 OK fetch done
c: <user reads message, "searching..." indicator is still there>
s: * SEARCH 852 5319 5512
s: 001 OK search done
c: <displays search results to user>

In order for this to be useful, the server must accept and process the FETCH
command before the SEARCH command is completed.  Otherwise, the user is stuck 
watching the "searching..." indicator until the search is done.  And the problem
is that the client has no way to know what will happen when it does this.  Some
clients want to solve that problem by opening a second session for the SEARCH,
but that's a problem with some server configurations, where two sessions can't
select the same mailbox at the same time.

The difficulty on the server side is that it needs to be smart enough not only
to process multiple commands at the same time in the same session (which is
relatively easy, once you set up the multi-threading stuff), but also to know
what commands can safely be multi-threaded, and when something has to wait.
For instance, you can't overlap SEARCH processing, though that would be a lovely 
thing to do, because the client has no way to distinguish the untagged responses.
You can't send a response or any sort while a literal is being transmitted.  Things
like that.  It can be tricky.

Barry Leiba, Internet Messaging Technology  ([email-masked])
http://www.research.ibm.com/people/l/leiba

From: "Rubinstein, Dmitry" <[email-masked]>
To: IMAP Extensions WG <[email-masked]>
Subject: RE: multi-append
Date: Thu, 16 Sep 1999 19:58:46 +0300
Sender: [email-masked]

> From: Barry Leiba [mailto:[email-masked]]
> Sent: Thursday, September 16, 1999 7:01 PM
> To: IMAP Extensions WG
> Subject: Re: multi-append
> 
> 
> Mark Crispin wrote:
> > How many client and server implementations out there 
> implement streaming (as
> > stipulated by RFC 2060) completely and correctly?
> 
> None that I know of.
> What's worse is that there's no way for a client to know 
> whether a server does
> or doesn't (which is where the temptation to do things like 
> potentially long
> SEARCHes in another session comes from).  Perhaps we need to 
> have an extension
> spec that defines explicitly what it means to support 
> streamed commands, and 
> have that spec add a CAPABILITY string that asserts that this 
> server supports
> it.

What DOES it mean to support streaming commands server side? I just can't
see what can be different from non-streaming: you read one command at a time
(assuming you can tell when a command is over and a new one begins,
otherwise - goto RFC2060). Once a command is processed, you send a response
and fetch another command. 

IMVHO, all the complexity of streaming commands is on the client side. What
am I missing?

--
Dmitry Rubinstein 

Date: Thu, 16 Sep 1999 10:08:31 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append
To: Barry Leiba <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Thu, 16 Sep 1999 13:01:06 -0400, Barry Leiba wrote:
> Perhaps we need to have an extension
> spec that defines explicitly what it means to support streamed commands, and

> have that spec add a CAPABILITY string that asserts that this server
> supports it.

I wouldn't oppose this, if it could be explained to me what would be different
if this capability existed.  Off hand, I can't think of a situation where the
client would be better off knowing that the server does not support streaming.

> > Are you certain that you can stream multiple APPEND commands?  It seems to
> > run afoul of the ambiguity rules.
> I don't see why.  Can you explain?

Let's consider an append of three messages.  The second is a godzillagram
which will pop the user's quota (and hence won't succeed in append).  If you
stream the three appends, then the first and third would be appended.

It's therefore ambiguous whether or not the third message is appended after
the second message.

Also, without recourse to the last sentence of the second paragraph of 5.5
(which in itself requires acknowledgement that a forbidden ambiguity exists),
there's no guarantee that the three messages will be appended in the order
sent by the client (reference second sentence of first paragraph of 5.5).

We can define our way out of this mess, but the base specification doesn't do
it for us.

> Multi-append would also
> be trivial for me to implement *IF* I don't have to do rollback.

What if it's a client specified option?

I would probably use the non-rollback form in my client code, but I don't
think that I can justify making non-rollback the only form.

> I think that requiring a UIDPLUS-style response for multi-append, with, say,
> zeroes for the UIDs for those messages that failed, would take care of that
> issue.  Something like this:
>   c: sends multi-append command with 5 messages
>   s: does appends, the fourth and fifth ones fail
>   s: TAG OK [APPENDUID <uidvalidity> 22 23 25 0 0] APPEND completed
>          ^
>   (should this be OK or NO?)

Hmm.  How would be indicate this if the client uses LITERAL+ on a non-UIDPLUS
server?  The answer "that means the client doesn't care" is a valid answer.

> I don't mean to be combative; I know this is a touchy item: what other
> servers support legacy UNIX mailboxes?

At least two other servers that I know of.  However, it doesn't matter.  The
market share of my server, using legacy UNIX mailboxes, easily dwarfs that of
all other servers combined.  I'm not particularly proud about that fact (the
part that they use that format); I wish to proclaim the legacy UNIX mailbox
format dead and buried.  But it ain't gonna happen.

> > Wrong.  The overhead is in locking and unlocking.  You can't keep the
> > mailbox locked between commands.
> You can if you can see that there's already another APPEND command in the
> pipe.

But that only works if the client streams.  And that gets back to the point
that you acknowledged that nobody seems to implement streaming completely or
correctly.

Date: Thu, 16 Sep 1999 13:01:06 -0400
From: Barry Leiba <[email-masked]>
Organization: Internet Messaging Technology; TR2_Xagent=WATSON
To: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Sender: [email-masked]

Mark Crispin wrote:
> How many client and server implementations out there implement streaming (as
> stipulated by RFC 2060) completely and correctly?

None that I know of.
What's worse is that there's no way for a client to know whether a server does
or doesn't (which is where the temptation to do things like potentially long
SEARCHes in another session comes from).  Perhaps we need to have an extension
spec that defines explicitly what it means to support streamed commands, and 
have that spec add a CAPABILITY string that asserts that this server supports
it.

> Are you certain that you can stream multiple APPEND commands?  It seems to run
> afoul of the ambiguity rules.

I don't see why.  Can you explain?

> LITERAL+.  However, I speculate that multi-append is easier to implement than
> LITERAL+.  

For me, LITERAL+ was absolutely trivial to implement; I suppose it depends upon
exactly how your literal-processing code is written.  Multi-append would also
be trivial for me to implement *IF* I don't have to do rollback.  The requirement
for rollback would stop me from bothering, since, as with Lyndon, there's not
very much startup overhead for me in an APPEND command.

I think that requiring a UIDPLUS-style response for multi-append, with, say,
zeroes for the UIDs for those messages that failed, would take care of that
issue.  Something like this:
  c: sends multi-append command with 5 messages
  s: does appends, the fourth and fifth ones fail
  s: TAG OK [APPENDUID <uidvalidity> 22 23 25 0 0] APPEND completed
         ^
  (should this be OK or NO?)

> It is an issue specific to any legacy UNIX mailbox.

I don't mean to be combative; I know this is a touchy item: what other servers
support legacy UNIX mailboxes?

> Wrong.  The overhead is in locking and unlocking.  You can't keep the mailbox
> locked between commands.

You can if you can see that there's already another APPEND command in the pipe.
I agree that this won't be perfect; it's possible that the client has tried to
stream APPEND commands but the next one isn't ready when you go to check.  But
in most cases it will be there, and you can avoid unlocking.  It means that you
have to be able to check for the presence of another command without blocking
if one isn't there.

Barry Leiba, Internet Messaging Technology  ([email-masked])
http://www.research.ibm.com/people/l/leiba

Date: Tue, 14 Sep 1999 13:56:59 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: RE: multi-append
To: "Rubinstein, Dmitry" <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Tue, 14 Sep 1999 10:36:52 +0300, Rubinstein, Dmitry wrote:
> 1) What happens if you just stream multiple messages through the
> conventional APPEND without waiting for the response after each message?

How many client and server implementations out there implement streaming (as
stipulated by RFC 2060) completely and correctly?

Are you certain that you can stream multiple APPEND commands?  It seems to run
afoul of the ambiguity rules.

> Don't you save almost as many RTTs as with MULTIAPPEND (except for RTTs of
> server responses, but that's not your bottleneck)?

Multi-append without LITERAL+ saves as many RTTs as single append with
LITERAL+.  However, I speculate that multi-append is easier to implement than
LITERAL+.  Nor does multi-append have the problem of sending a literal over a
slow link (like radio) that is going to be discarded immediately.

Multi-append combined with LITERAL+ requires just a single RTT, and it doesn't
have the ambiguity issues of streaming APPEND.

> 2) Isn't it an implementation issue specific to your server?

No, it is NOT an implementation issue specific to my server.

It is an issue specific to any legacy UNIX mailbox.

> Perhaps, you
> can cache mailbox until next command (after the APPEND), and if it's again
> an APPEND to the same mailbox - no overhead is needed.

Wrong.  The overhead is in locking and unlocking.  You can't keep the mailbox
locked between commands.

> 3) When would the client want to append multiple messages to the mailbox?
> Where does the need come from?

Any upload of messages, including multi-message save from a mailbox on one
server to another, or simply transfer of mailboxes from one user to another.

Date: Tue, 14 Sep 1999 13:50:51 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append 
To: Lyndon Nerenberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 17:17:38 -0600, Lyndon Nerenberg wrote:
> You want to communicate this failure ASAP, which means sending
> partial completion status between messages, which negates most of
> the benefit (by adding that evil RTT back in).

At worst (with no LITERAL+ since you decided you want the failures ASAP),
multi-append is no better than single APPEND with LITERAL+, but it is no
worse.  However, I suspect that multi-append is easier to implement (in an
implementation starting from scratch) than LITERAL+

Multi-append without LITERAL+ also avoids the sending of the literal, which is
a consideration on slow links -- you don't want to use LITERAL+ with radio!!

Date: Tue, 14 Sep 1999 10:33:12 -0400
From: Cyrus Daboo <[email-masked]>
To: "Rubinstein, Dmitry" <[email-masked]>, IMAP Extensions WG <[email-masked]>
Subject: RE: multi-append
Sender: [email-masked]

--On Tuesday, September 14, 1999 10:36 AM +0300 "Rubinstein, Dmitry"
<[email-masked]> wrote:

> 3) When would the client want to append multiple messages to the mailbox?
> Where does the need come from?

Server-to-server mailbox copies, disconnected operation synchronisation,
conversion of local POP3 mailboxes to IMAP, etc

--
Cyrus

Date: Tue, 14 Sep 1999 09:18:02 +0100
From: John Haxby <[email-masked]>
CC: [email-masked]
Subject: Re: multi-append
Sender: [email-masked]

This is a multi-part message in MIME format.
--------------3AE20F4D527E29374F889916
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

[email-masked] wrote:

> I would like to add an extension called MULTIAPPEND.  This is an upwards
> compatible extension to the RFC 2060 APPEND command.
>

If I recall correctly, this is outside the charter of imap-ext.

However, I don't see the advantage of this over streaming APPEND commands,
unless, as you point out, the server doesn't cache the most recently opened
mailbox.  (And in this case, this is a server performance issue, not a protocol
deficiency issue -- our server does just this caching to avoid re-opening
mailboxes for any reason.)

jch

--------------3AE20F4D527E29374F889916
Content-Type: text/x-vcard; charset=us-ascii;
 name="jch.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for John Haxby
Content-Disposition: attachment;
 filename="jch.vcf"

begin:vcard 
n:Haxby;John
tel;work:+44 1344 763711
x-mozilla-html:FALSE
url:http://www.hp.com/go/OpenMail
org:Hewlett Packard;OpenMail R&D<img src="http://www.ice.hp.com/cyc/om/50/graphics/omlinux.jpg" width=53 height=62 align=top>
adr:;;Nine Mile Ride;Wokingham;Berks;RG40 3LL;England
version:2.1
email;internet:[email-masked]
x-mozilla-cpt:;14976
fn:John Haxby
end:vcard

--------------3AE20F4D527E29374F889916--

From: "Rubinstein, Dmitry" <[email-masked]>
To: IMAP Extensions WG <[email-masked]>
Subject: RE: multi-append
Date: Tue, 14 Sep 1999 10:36:52 +0300
Sender: [email-masked]

> From: Mark Crispin [mailto:[email-masked]]
> 
> I would like to add an extension called MULTIAPPEND.  This is 
> an upwards
> compatible extension to the RFC 2060 APPEND command.

[skip]

> MULTIAPPEND provides the same RTT savings offered by the 
> LITERAL+ extension
> with the current APPEND.  When MULTIAPPEND is used in conjunction with
> LITERAL+, the entire upload is a single RTT.

I have a couple of questions:

1) What happens if you just stream multiple messages through the
conventional APPEND without waiting for the response after each message?
Don't you save almost as many RTTs as with MULTIAPPEND (except for RTTs of
server responses, but that's not your bottleneck)?

> There is another advantage, which is a major win for my 
> server; the procedure
> for opening and closing the destination mailbox only needs to 
> be done once
> instead of per-message.  We've determined that for the 
> standard UNIX format of
> mail, the open/close and lock/unlock overhead is a major part 
> of the overall
> time spent in multiple appends.

2) Isn't it an implementation issue specific to your server? Perhaps, you
can cache mailbox until next command (after the APPEND), and if it's again
an APPEND to the same mailbox - no overhead is needed.

3) When would the client want to append multiple messages to the mailbox?
Where does the need come from?

--
Dmitry Rubinstein 

To: Mark Crispin <[email-masked]>
cc: Lyndon Nerenberg <[email-masked]>, IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append 
Date: Mon, 13 Sep 1999 17:17:38 -0600
From: Lyndon Nerenberg <[email-masked]>
Sender: [email-masked]

>>>>> "Mark" == Mark Crispin <[email-masked]> writes:

    Mark> Actually, it's "ftruncate() the mailbox file back to its old

Yup, sorry, brain in neutral :-P

    Mark> Perhaps have some mechanism to indicate total size of the
    Mark> append?

Maybe; is that 1GB of MULTIAPPEND two 500MB messages, a 1MB message
followed by a 999MB message, or 500 2MB messages? The potential failure
modes are quite different. Without the indidivual message component
sizes, the server can't make an intelligent decision about whether it
can realistically accept the request. And even with sizes, it cannot
bail out halfway through when the disk fills up for reasons outside
the server's control.

    Mark> Don't you have to do various stat()s and/or database
    Mark> lookups/locks to validate the mailbox and plop additional
    Mark> messages down into the mailbox?

Yes, but much of this is cached, so it's not that big of an issue
performance wise.

    Mark> [ ... ] I still think that
    Mark> you can't do a streaming upload without per-message pauses.

But we can make the pauses very short. Again, this is a direct benefit
of the threading (and caching) model we employ.

    Mark> So, what about some sort of additional untagged response to
    Mark> indicate what got appended and what didn't, on the line of
    Mark> the UIDPLUS stuff?

It seems to me that the failure case will almost always be resource
starvation (no disk, inodes, ...) after which your odds of being able
to handle succeeding messages in the multiappend approaches zero (over
the likely time period during which the MULTIAPPEND will try to
complete.)

You want to communicate this failure ASAP, which means sending
partial completion status between messages, which negates most of
the benefit (by adding that evil RTT back in).

Factor the abort processing in with intelligent size handling and
you've engineered APPEND.

So, where I see MULTIAPPEND being a win is for servers that use a single-
file-per-mailbox (or equivelent) format where streamed appends are cheap,
but append transactions aren't. In it's current state, I wouldn't implement
it soley as a protocol performance enhancement, for the reasons I outline
above. I don't see how those issues can be addressed without turning it
back into the existing APPEND. 

--lyndon

Date: Mon, 13 Sep 1999 15:09:34 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append 
To: Cyrus Daboo <[email-masked]>
cc: Mark Crispin <[email-masked]>, Lyndon Nerenberg <[email-masked]>, IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 18:10:20 -0400, Cyrus Daboo wrote:
> It seems to me if the client uses non-synchronising literals to do the
> multi-append then there is no real way to recover from a failure other than
> a NO/BAD to the entire command.

There is another choice.  We could have two flavors of multi-append, one which
does a NO/BAD to the entire command if there is any failure, and the other
which will succeed with appends up to the point of the failure.  It would then
return an untagged response indicating the extent of the partial success, and
then the NO/BAD.

This would make append a rather odd bird as far as IMAP goes.  The likelihood
is high that the server would not buffer up all the messages and then start
appending at the terminating CRLF (which a strict interpretation of IMAP would
mandate), but instead would append as the messages come in (which makes much
more implementation and operational sense).

Where this becomes strange is that a syntactically invalid command could also
have this behavior (hence "NO/BAD" rather than "NO").  I don't think that we
should worry too much about this since bad syntax never happens with the
software we experts write.  ;-) ;-) ;-) ;-) ;-)

> S: a APPEND INBOX {11}+
> C: From: Cyrus
> C:  {0}
> S: + [OK MULTIAPPEND TOTAL 1]
> C:  {10}+
> S: From: Mark
> C:  {0}
> S: + [NO MULTIAPPEND TOTAL 1]
> C: <CRLF>
> S: OK MULTIAPPEND succeeded for 1 message

With synchronized literals:

S: a APPEND INBOX {11}
C: From: Cyrus
C:  {0}
S: + I got that message!
C:  {10}
S: NO [APPEND 1] MULTIAPPEND failed after 1 message due to disk quota exceeded

Date: Mon, 13 Sep 1999 18:10:20 -0400
From: Cyrus Daboo <[email-masked]>
To: Mark Crispin <[email-masked]>, Lyndon Nerenberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append 
Sender: [email-masked]

--On Monday, September 13, 1999 2:29 PM -0700 Mark Crispin
<[email-masked]> wrote:

> Really?  LITERAL+ eliminates 50% of the RTTs and was supposedly a major
> win for those servers which support it.  The combination of MULTIAPPEND
> and LITERAL+ would eliminate all but one RTT.
> 
> So, what about some sort of additional untagged response to indicate what
> got appended and what didn't, on the line of the UIDPLUS stuff?
> 
> I appreciate your expression of non-opposition, but I'd like to see if
> something can be done to make you guys be enthusiastic supporters.

It seems to me if the client uses non-synchronising literals to do the
multi-append then there is no real way to recover from a failure other than
a NO/BAD to the entire command. If the client were prepared to tolerate
this in order to eliminate RTTs that would be fine.

However, if RTTs were not so much of an issue as opposed to the server
overhead of multiple APPEND commands, then its possible to use a
combination of non-non-synchronising literals for the message interpersed
with non-synchronising literals to check with the server to see if the last
append completed:

S: a APPEND INBOX {11}+
C: From: Cyrus
C:  {0}
S: + [OK MULTIAPPEND TOTAL 1]
C:  {10}+
S: From: Mark
C:  {0}
S: + [NO MULTIAPPEND TOTAL 1]
C: <CRLF>
S: OK MULTIAPPEND succeeded for 1 message

--
Cyrus

From: Erik Forsberg <[email-masked]>
To: Mark Crispin <[email-masked]>
Cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Date: Mon, 13 Sep 1999 14:50:37 -0700 (Pacific Daylight Time)
Sender: [email-masked]

Argh, of course it is CRLF (instead of a literal) I am looking for.
Forget my objection. Responded too quickly.

On Mon, 13 Sep 1999 14:11:24 -0700 Mark Crispin <[email-masked]> wrote:

> On Mon, 13 Sep 1999 14:05:42 -0700 (Pacific Daylight Time), Erik Forsberg
> wrote:
> > Implementation difficulty here.
> > It doesnt seem like you can detect the last append_message without reading
> > ahead and detecting that next token is SPACE (instead of what goes in a tag)
> 
> Actually, it's detecting that the next token is a SPACE as opposed to a CRLF
> (marking end of command).  You wouldn't look for a tag until you get to the
> start-of-command portion of your parse loop.
> 
> This isn't the only command which has this characteristic; SEARCH stands out
> in the base specification; and the SORT, THREAD, and extended LIST proposals
> also act in the same way.
> 
> > That causes problems in my server implementation as I make a distinction
> > between waiting for the next IMAP4 command (because the client is idle, you
> > need to check for new mail, flag updates, etc) and simply waiting for the
> > next token within a command.
> 
> Is the issue that you actually enter command execution for APPEND when you
> receive the literal, as opposed to waiting until you get the CRLF to end the
> command?  What happens if the client does
> 	001 APPEND foobar {3}
> 	zap barf
> Do you append "zap" to mailbox foobar then return a BAD for "barf"?  If so,
> that's wrong; foobar should not be affected by this command at all (or if it
> is, it should be reverted to its prior state).
> 
> In any case, MULTIAPPEND is an extension and hence optional; there's no
> requirement that you implement it in your server, and no client will send you
> one unless you advertise it.  So, you could ignore MULTIAPPEND if it presents
> implementation problems and remain fully-compliant.  I don't implement all the
> extensions either.
> 
> Is there something that I'm missing that would cause you problems?
> 

----------------------
Erik Forsberg
[email-masked]

Date: Mon, 13 Sep 1999 14:29:56 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append 
To: Lyndon Nerenberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 15:25:18 -0600, Lyndon Nerenberg wrote:
> This would be my concern as well. For the UW server backing out should be
> easy -- just don't rename the new mailbox file over the old one.

Actually, it's "ftruncate() the mailbox file back to its old size and adjust
the dates."  You can't "rename the new mailbox file over the old one" with the
standard UNIX format; too many mail delivery agents depend upon system call
locking on the mail file (as opposed to .lock files) which mandate that the
inode be preserved.  A *major* hassle.

> It would
> be more of a problem for us as we would have to do additional checkpointing,
> and wrap the whole thing up in a transaction in case we had to do a roll
> back.

Well, let's talk about this.  I'm willing to discuss a mechanism to indicate
"partial success" for multi-append.  It may be a good idea anyway; it seems
wasteful to toss out all that work.

Perhaps have some mechanism to indicate total size of the append?

> Then again, because of how we store our messages, multiple APPEND
> operations are not a performance hit for us.

Don't you have to do various stat()s and/or database lookups/locks to validate
the mailbox and plop additional messages down into the mailbox?  Even if your
format does this faster than standard UNIX format (just about anything is
better than standard UNIX format!!), I still think that you can't do a
streaming upload without per-message pauses.

> The minor increase in
> throughput from eliminating the extra RTTs wouldn't justify the increased
> complexity it would introduce, so it's unlikely we would implement this
> extension in our server.

Really?  LITERAL+ eliminates 50% of the RTTs and was supposedly a major win
for those servers which support it.  The combination of MULTIAPPEND and
LITERAL+ would eliminate all but one RTT.

So, what about some sort of additional untagged response to indicate what got
appended and what didn't, on the line of the UIDPLUS stuff?

I appreciate your expression of non-opposition, but I'd like to see if
something can be done to make you guys be enthusiastic supporters.

To: Mark Crispin <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append 
Date: Mon, 13 Sep 1999 15:25:18 -0600
From: Lyndon Nerenberg <[email-masked]>
Sender: [email-masked]

>>>>> "Mark" == Mark Crispin <[email-masked]> writes:

    Mark> The one issue of contention may be what happens on a partial
    Mark> failure; e.g.  running out of disk quota after several
    Mark> messages but before the last message.  I think that
    Mark> consistancy with the rest of IMAP, as well as the
    Mark> impossibility of the client knowing what succeeded and what
    Mark> failed if LITERAL+ is used with this feature, mandates that
    Mark> the entire APPEND fail and the mailbox be reverted to the
    Mark> state prior to the APPEND.

This would be my concern as well. For the UW server backing out should be
easy -- just don't rename the new mailbox file over the old one.  It would
be more of a problem for us as we would have to do additional checkpointing,
and wrap the whole thing up in a transaction in case we had to do a roll
back.  Then again, because of how we store our messages, multiple APPEND
operations are not a performance hit for us.  The minor increase in
throughput from eliminating the extra RTTs wouldn't justify the increased
complexity it would introduce, so it's unlikely we would implement this
extension in our server.  (Which is not the same as saying I would oppose
the extension.)

--lyndon

Date: Mon, 13 Sep 1999 14:11:24 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append
To: Erik Forsberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 14:05:42 -0700 (Pacific Daylight Time), Erik Forsberg
wrote:
> Implementation difficulty here.
> It doesnt seem like you can detect the last append_message without reading
> ahead and detecting that next token is SPACE (instead of what goes in a tag)

Actually, it's detecting that the next token is a SPACE as opposed to a CRLF
(marking end of command).  You wouldn't look for a tag until you get to the
start-of-command portion of your parse loop.

This isn't the only command which has this characteristic; SEARCH stands out
in the base specification; and the SORT, THREAD, and extended LIST proposals
also act in the same way.

> That causes problems in my server implementation as I make a distinction
> between waiting for the next IMAP4 command (because the client is idle, you
> need to check for new mail, flag updates, etc) and simply waiting for the
> next token within a command.

Is the issue that you actually enter command execution for APPEND when you
receive the literal, as opposed to waiting until you get the CRLF to end the
command?  What happens if the client does
	001 APPEND foobar {3}
	zap barf
Do you append "zap" to mailbox foobar then return a BAD for "barf"?  If so,
that's wrong; foobar should not be affected by this command at all (or if it
is, it should be reverted to its prior state).

In any case, MULTIAPPEND is an extension and hence optional; there's no
requirement that you implement it in your server, and no client will send you
one unless you advertise it.  So, you could ignore MULTIAPPEND if it presents
implementation problems and remain fully-compliant.  I don't implement all the
extensions either.

Is there something that I'm missing that would cause you problems?

From: Erik Forsberg <[email-masked]>
To: Mark Crispin <[email-masked]>
Cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Date: Mon, 13 Sep 1999 14:05:42 -0700 (Pacific Daylight Time)
Sender: [email-masked]

Implementation difficulty here.
It doesnt seem like you can detect the last append_message without reading ahead
and detecting that next token is SPACE (instead of what goes in a tag)
That causes problems in my server implementation as I make a distinction
between waiting for the next IMAP4 command (because the client is idle, you
need to check for new mail, flag updates, etc) and simply waiting for the
next token within a command.

On Mon, 13 Sep 1999 13:15:54 -0700 Mark Crispin <[email-masked]> wrote:

> I would like to add an extension called MULTIAPPEND.  This is an upwards
> compatible extension to the RFC 2060 APPEND command.
> 
> A server which advertises the MULTIAPPEND capability permits more than one
> message in the same append command.  In other words, the APPEND grammar
> becomes:
> 
> append          = "APPEND" SPACE mailbox 1*append_message
> append_message  = [SPACE flag_list] [SPACE date_time] SPACE literal
> 
> MULTIAPPEND provides the same RTT savings offered by the LITERAL+ extension
> with the current APPEND.  When MULTIAPPEND is used in conjunction with
> LITERAL+, the entire upload is a single RTT.
> 
> There is another advantage, which is a major win for my server; the procedure
> for opening and closing the destination mailbox only needs to be done once
> instead of per-message.  We've determined that for the standard UNIX format of
> mail, the open/close and lock/unlock overhead is a major part of the overall
> time spent in multiple appends.
> 
> I believe that this extension should be non-controversial; it is upwards
> compatible and is at least a minor win for everybody (because of RTTs) and can
> potentially be a major win.  Does anyone disagree?  If not, do we have
> concensus to put out an ID and give it accelerated approval in the WG (with
> hopefully minimal discussion) as a Proposed Standard?
> 
> The one issue of contention may be what happens on a partial failure; e.g.
> running out of disk quota after several messages but before the last message.
> I think that consistancy with the rest of IMAP, as well as the impossibility
> of the client knowing what succeeded and what failed if LITERAL+ is used with
> this feature, mandates that the entire APPEND fail and the mailbox be reverted
> to the state prior to the APPEND.
> 

----------------------
Erik Forsberg
[email-masked]

Date: Mon, 13 Sep 1999 13:15:54 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: multi-append
To: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

I would like to add an extension called MULTIAPPEND.  This is an upwards
compatible extension to the RFC 2060 APPEND command.

A server which advertises the MULTIAPPEND capability permits more than one
message in the same append command.  In other words, the APPEND grammar
becomes:

append          = "APPEND" SPACE mailbox 1*append_message
append_message  = [SPACE flag_list] [SPACE date_time] SPACE literal

MULTIAPPEND provides the same RTT savings offered by the LITERAL+ extension
with the current APPEND.  When MULTIAPPEND is used in conjunction with
LITERAL+, the entire upload is a single RTT.

There is another advantage, which is a major win for my server; the procedure
for opening and closing the destination mailbox only needs to be done once
instead of per-message.  We've determined that for the standard UNIX format of
mail, the open/close and lock/unlock overhead is a major part of the overall
time spent in multiple appends.

I believe that this extension should be non-controversial; it is upwards
compatible and is at least a minor win for everybody (because of RTTs) and can
potentially be a major win.  Does anyone disagree?  If not, do we have
concensus to put out an ID and give it accelerated approval in the WG (with
hopefully minimal discussion) as a Proposed Standard?

The one issue of contention may be what happens on a partial failure; e.g.
running out of disk quota after several messages but before the last message.
I think that consistancy with the rest of IMAP, as well as the impossibility
of the client knowing what succeeded and what failed if LITERAL+ is used with
this feature, mandates that the entire APPEND fail and the mailbox be reverted
to the state prior to the APPEND.

From: "Rubinstein, Dmitry" <[email-masked]>
To: IMAP Extensions WG <[email-masked]>
Subject: RE: multi-append
Date: Tue, 28 Sep 1999 22:36:19 +0300
Sender: [email-masked]

> From: Barry Leiba [mailto:[email-masked]]
> Sent: Monday, September 27, 1999 3:50 PM
> To: IMAP Extensions WG
> Subject: Re: multi-append
> 
> > IMVHO, all the complexity of streaming commands is on the 
> client side. What
> > am I missing?
> 
> Why would the client do that (that is, what benefit would it 
> get from it)?
> The answer is that the benefit is overlapped execution of 
> commands.  

[explanation of why streaming commands is tricky on the server side is
skipped]

OK, I had to choose the phrasing more carefully. Please, allow me to
rephrase:

What DOES it mean to support streaming commands server side in context of
'streaming APPEND' vs. MULTI-APPEND? In either case the user will probably
be presented with some pop-up message box or some revolving sand clock or
whatever indication to the fact, that the client is currently involved in
time consuming operation. Unless there's a mechanism in MULTIAPPEND for
aborting the transfer? But how?...

In short, streaming commands is tricky. But not always. There's at least one
place where it seems to be OK, and that is multiple APPENDs.

--
Dmitry Rubinstein 

Date: Mon, 27 Sep 1999 09:49:45 -0400
From: Barry Leiba <[email-masked]>
Organization: Internet Messaging Technology; TR2_Xagent=WATSON
To: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Sender: [email-masked]

"Rubinstein, Dmitry" wrote:
> What DOES it mean to support streaming commands server side? I just can't
> see what can be different from non-streaming: you read one command at a time
> (assuming you can tell when a command is over and a new one begins,
> otherwise - goto RFC2060). Once a command is processed, you send a response
> and fetch another command.
> 
> IMVHO, all the complexity of streaming commands is on the client side. What
> am I missing?

Why would the client do that (that is, what benefit would it get from it)?
The answer is that the benefit is overlapped execution of commands.  For 
instance:

c: <user clicks a search dialogue>
c: 001 SEARCH BODY "frobozz"
c: <displays "searching..." indicator somewhere>
s: <accepts SEARCH command and starts searching>
c: <user clicks on message 5272>
c: 002 FETCH 5272 BODY[1]
s: * 5272 FETCH (BODY[1] {386}
...
s: 002 OK fetch done
c: <user reads message, "searching..." indicator is still there>
s: * SEARCH 852 5319 5512
s: 001 OK search done
c: <displays search results to user>

In order for this to be useful, the server must accept and process the FETCH
command before the SEARCH command is completed.  Otherwise, the user is stuck 
watching the "searching..." indicator until the search is done.  And the problem
is that the client has no way to know what will happen when it does this.  Some
clients want to solve that problem by opening a second session for the SEARCH,
but that's a problem with some server configurations, where two sessions can't
select the same mailbox at the same time.

The difficulty on the server side is that it needs to be smart enough not only
to process multiple commands at the same time in the same session (which is
relatively easy, once you set up the multi-threading stuff), but also to know
what commands can safely be multi-threaded, and when something has to wait.
For instance, you can't overlap SEARCH processing, though that would be a lovely 
thing to do, because the client has no way to distinguish the untagged responses.
You can't send a response or any sort while a literal is being transmitted.  Things
like that.  It can be tricky.

Barry Leiba, Internet Messaging Technology  ([email-masked])
http://www.research.ibm.com/people/l/leiba

From: "Rubinstein, Dmitry" <[email-masked]>
To: IMAP Extensions WG <[email-masked]>
Subject: RE: multi-append
Date: Thu, 16 Sep 1999 19:58:46 +0300
Sender: [email-masked]

> From: Barry Leiba [mailto:[email-masked]]
> Sent: Thursday, September 16, 1999 7:01 PM
> To: IMAP Extensions WG
> Subject: Re: multi-append
> 
> 
> Mark Crispin wrote:
> > How many client and server implementations out there 
> implement streaming (as
> > stipulated by RFC 2060) completely and correctly?
> 
> None that I know of.
> What's worse is that there's no way for a client to know 
> whether a server does
> or doesn't (which is where the temptation to do things like 
> potentially long
> SEARCHes in another session comes from).  Perhaps we need to 
> have an extension
> spec that defines explicitly what it means to support 
> streamed commands, and 
> have that spec add a CAPABILITY string that asserts that this 
> server supports
> it.

What DOES it mean to support streaming commands server side? I just can't
see what can be different from non-streaming: you read one command at a time
(assuming you can tell when a command is over and a new one begins,
otherwise - goto RFC2060). Once a command is processed, you send a response
and fetch another command. 

IMVHO, all the complexity of streaming commands is on the client side. What
am I missing?

--
Dmitry Rubinstein 

Date: Thu, 16 Sep 1999 10:08:31 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append
To: Barry Leiba <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Thu, 16 Sep 1999 13:01:06 -0400, Barry Leiba wrote:
> Perhaps we need to have an extension
> spec that defines explicitly what it means to support streamed commands, and

> have that spec add a CAPABILITY string that asserts that this server
> supports it.

I wouldn't oppose this, if it could be explained to me what would be different
if this capability existed.  Off hand, I can't think of a situation where the
client would be better off knowing that the server does not support streaming.

> > Are you certain that you can stream multiple APPEND commands?  It seems to
> > run afoul of the ambiguity rules.
> I don't see why.  Can you explain?

Let's consider an append of three messages.  The second is a godzillagram
which will pop the user's quota (and hence won't succeed in append).  If you
stream the three appends, then the first and third would be appended.

It's therefore ambiguous whether or not the third message is appended after
the second message.

Also, without recourse to the last sentence of the second paragraph of 5.5
(which in itself requires acknowledgement that a forbidden ambiguity exists),
there's no guarantee that the three messages will be appended in the order
sent by the client (reference second sentence of first paragraph of 5.5).

We can define our way out of this mess, but the base specification doesn't do
it for us.

> Multi-append would also
> be trivial for me to implement *IF* I don't have to do rollback.

What if it's a client specified option?

I would probably use the non-rollback form in my client code, but I don't
think that I can justify making non-rollback the only form.

> I think that requiring a UIDPLUS-style response for multi-append, with, say,
> zeroes for the UIDs for those messages that failed, would take care of that
> issue.  Something like this:
>   c: sends multi-append command with 5 messages
>   s: does appends, the fourth and fifth ones fail
>   s: TAG OK [APPENDUID <uidvalidity> 22 23 25 0 0] APPEND completed
>          ^
>   (should this be OK or NO?)

Hmm.  How would be indicate this if the client uses LITERAL+ on a non-UIDPLUS
server?  The answer "that means the client doesn't care" is a valid answer.

> I don't mean to be combative; I know this is a touchy item: what other
> servers support legacy UNIX mailboxes?

At least two other servers that I know of.  However, it doesn't matter.  The
market share of my server, using legacy UNIX mailboxes, easily dwarfs that of
all other servers combined.  I'm not particularly proud about that fact (the
part that they use that format); I wish to proclaim the legacy UNIX mailbox
format dead and buried.  But it ain't gonna happen.

> > Wrong.  The overhead is in locking and unlocking.  You can't keep the
> > mailbox locked between commands.
> You can if you can see that there's already another APPEND command in the
> pipe.

But that only works if the client streams.  And that gets back to the point
that you acknowledged that nobody seems to implement streaming completely or
correctly.

Date: Thu, 16 Sep 1999 13:01:06 -0400
From: Barry Leiba <[email-masked]>
Organization: Internet Messaging Technology; TR2_Xagent=WATSON
To: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Sender: [email-masked]

Mark Crispin wrote:
> How many client and server implementations out there implement streaming (as
> stipulated by RFC 2060) completely and correctly?

None that I know of.
What's worse is that there's no way for a client to know whether a server does
or doesn't (which is where the temptation to do things like potentially long
SEARCHes in another session comes from).  Perhaps we need to have an extension
spec that defines explicitly what it means to support streamed commands, and 
have that spec add a CAPABILITY string that asserts that this server supports
it.

> Are you certain that you can stream multiple APPEND commands?  It seems to run
> afoul of the ambiguity rules.

I don't see why.  Can you explain?

> LITERAL+.  However, I speculate that multi-append is easier to implement than
> LITERAL+.  

For me, LITERAL+ was absolutely trivial to implement; I suppose it depends upon
exactly how your literal-processing code is written.  Multi-append would also
be trivial for me to implement *IF* I don't have to do rollback.  The requirement
for rollback would stop me from bothering, since, as with Lyndon, there's not
very much startup overhead for me in an APPEND command.

I think that requiring a UIDPLUS-style response for multi-append, with, say,
zeroes for the UIDs for those messages that failed, would take care of that
issue.  Something like this:
  c: sends multi-append command with 5 messages
  s: does appends, the fourth and fifth ones fail
  s: TAG OK [APPENDUID <uidvalidity> 22 23 25 0 0] APPEND completed
         ^
  (should this be OK or NO?)

> It is an issue specific to any legacy UNIX mailbox.

I don't mean to be combative; I know this is a touchy item: what other servers
support legacy UNIX mailboxes?

> Wrong.  The overhead is in locking and unlocking.  You can't keep the mailbox
> locked between commands.

You can if you can see that there's already another APPEND command in the pipe.
I agree that this won't be perfect; it's possible that the client has tried to
stream APPEND commands but the next one isn't ready when you go to check.  But
in most cases it will be there, and you can avoid unlocking.  It means that you
have to be able to check for the presence of another command without blocking
if one isn't there.

Barry Leiba, Internet Messaging Technology  ([email-masked])
http://www.research.ibm.com/people/l/leiba

Date: Tue, 14 Sep 1999 13:56:59 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: RE: multi-append
To: "Rubinstein, Dmitry" <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Tue, 14 Sep 1999 10:36:52 +0300, Rubinstein, Dmitry wrote:
> 1) What happens if you just stream multiple messages through the
> conventional APPEND without waiting for the response after each message?

How many client and server implementations out there implement streaming (as
stipulated by RFC 2060) completely and correctly?

Are you certain that you can stream multiple APPEND commands?  It seems to run
afoul of the ambiguity rules.

> Don't you save almost as many RTTs as with MULTIAPPEND (except for RTTs of
> server responses, but that's not your bottleneck)?

Multi-append without LITERAL+ saves as many RTTs as single append with
LITERAL+.  However, I speculate that multi-append is easier to implement than
LITERAL+.  Nor does multi-append have the problem of sending a literal over a
slow link (like radio) that is going to be discarded immediately.

Multi-append combined with LITERAL+ requires just a single RTT, and it doesn't
have the ambiguity issues of streaming APPEND.

> 2) Isn't it an implementation issue specific to your server?

No, it is NOT an implementation issue specific to my server.

It is an issue specific to any legacy UNIX mailbox.

> Perhaps, you
> can cache mailbox until next command (after the APPEND), and if it's again
> an APPEND to the same mailbox - no overhead is needed.

Wrong.  The overhead is in locking and unlocking.  You can't keep the mailbox
locked between commands.

> 3) When would the client want to append multiple messages to the mailbox?
> Where does the need come from?

Any upload of messages, including multi-message save from a mailbox on one
server to another, or simply transfer of mailboxes from one user to another.

Date: Tue, 14 Sep 1999 13:50:51 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append 
To: Lyndon Nerenberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 17:17:38 -0600, Lyndon Nerenberg wrote:
> You want to communicate this failure ASAP, which means sending
> partial completion status between messages, which negates most of
> the benefit (by adding that evil RTT back in).

At worst (with no LITERAL+ since you decided you want the failures ASAP),
multi-append is no better than single APPEND with LITERAL+, but it is no
worse.  However, I suspect that multi-append is easier to implement (in an
implementation starting from scratch) than LITERAL+

Multi-append without LITERAL+ also avoids the sending of the literal, which is
a consideration on slow links -- you don't want to use LITERAL+ with radio!!

Date: Tue, 14 Sep 1999 10:33:12 -0400
From: Cyrus Daboo <[email-masked]>
To: "Rubinstein, Dmitry" <[email-masked]>, IMAP Extensions WG <[email-masked]>
Subject: RE: multi-append
Sender: [email-masked]

--On Tuesday, September 14, 1999 10:36 AM +0300 "Rubinstein, Dmitry"
<[email-masked]> wrote:

> 3) When would the client want to append multiple messages to the mailbox?
> Where does the need come from?

Server-to-server mailbox copies, disconnected operation synchronisation,
conversion of local POP3 mailboxes to IMAP, etc

--
Cyrus

Date: Tue, 14 Sep 1999 09:18:02 +0100
From: John Haxby <[email-masked]>
CC: [email-masked]
Subject: Re: multi-append
Sender: [email-masked]

This is a multi-part message in MIME format.
--------------3AE20F4D527E29374F889916
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

[email-masked] wrote:

> I would like to add an extension called MULTIAPPEND.  This is an upwards
> compatible extension to the RFC 2060 APPEND command.
>

If I recall correctly, this is outside the charter of imap-ext.

However, I don't see the advantage of this over streaming APPEND commands,
unless, as you point out, the server doesn't cache the most recently opened
mailbox.  (And in this case, this is a server performance issue, not a protocol
deficiency issue -- our server does just this caching to avoid re-opening
mailboxes for any reason.)

jch

--------------3AE20F4D527E29374F889916
Content-Type: text/x-vcard; charset=us-ascii;
 name="jch.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for John Haxby
Content-Disposition: attachment;
 filename="jch.vcf"

begin:vcard 
n:Haxby;John
tel;work:+44 1344 763711
x-mozilla-html:FALSE
url:http://www.hp.com/go/OpenMail
org:Hewlett Packard;OpenMail R&D<img src="http://www.ice.hp.com/cyc/om/50/graphics/omlinux.jpg" width=53 height=62 align=top>
adr:;;Nine Mile Ride;Wokingham;Berks;RG40 3LL;England
version:2.1
email;internet:[email-masked]
x-mozilla-cpt:;14976
fn:John Haxby
end:vcard

--------------3AE20F4D527E29374F889916--

From: "Rubinstein, Dmitry" <[email-masked]>
To: IMAP Extensions WG <[email-masked]>
Subject: RE: multi-append
Date: Tue, 14 Sep 1999 10:36:52 +0300
Sender: [email-masked]

> From: Mark Crispin [mailto:[email-masked]]
> 
> I would like to add an extension called MULTIAPPEND.  This is 
> an upwards
> compatible extension to the RFC 2060 APPEND command.

[skip]

> MULTIAPPEND provides the same RTT savings offered by the 
> LITERAL+ extension
> with the current APPEND.  When MULTIAPPEND is used in conjunction with
> LITERAL+, the entire upload is a single RTT.

I have a couple of questions:

1) What happens if you just stream multiple messages through the
conventional APPEND without waiting for the response after each message?
Don't you save almost as many RTTs as with MULTIAPPEND (except for RTTs of
server responses, but that's not your bottleneck)?

> There is another advantage, which is a major win for my 
> server; the procedure
> for opening and closing the destination mailbox only needs to 
> be done once
> instead of per-message.  We've determined that for the 
> standard UNIX format of
> mail, the open/close and lock/unlock overhead is a major part 
> of the overall
> time spent in multiple appends.

2) Isn't it an implementation issue specific to your server? Perhaps, you
can cache mailbox until next command (after the APPEND), and if it's again
an APPEND to the same mailbox - no overhead is needed.

3) When would the client want to append multiple messages to the mailbox?
Where does the need come from?

--
Dmitry Rubinstein 

To: Mark Crispin <[email-masked]>
cc: Lyndon Nerenberg <[email-masked]>, IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append 
Date: Mon, 13 Sep 1999 17:17:38 -0600
From: Lyndon Nerenberg <[email-masked]>
Sender: [email-masked]

>>>>> "Mark" == Mark Crispin <[email-masked]> writes:

    Mark> Actually, it's "ftruncate() the mailbox file back to its old

Yup, sorry, brain in neutral :-P

    Mark> Perhaps have some mechanism to indicate total size of the
    Mark> append?

Maybe; is that 1GB of MULTIAPPEND two 500MB messages, a 1MB message
followed by a 999MB message, or 500 2MB messages? The potential failure
modes are quite different. Without the indidivual message component
sizes, the server can't make an intelligent decision about whether it
can realistically accept the request. And even with sizes, it cannot
bail out halfway through when the disk fills up for reasons outside
the server's control.

    Mark> Don't you have to do various stat()s and/or database
    Mark> lookups/locks to validate the mailbox and plop additional
    Mark> messages down into the mailbox?

Yes, but much of this is cached, so it's not that big of an issue
performance wise.

    Mark> [ ... ] I still think that
    Mark> you can't do a streaming upload without per-message pauses.

But we can make the pauses very short. Again, this is a direct benefit
of the threading (and caching) model we employ.

    Mark> So, what about some sort of additional untagged response to
    Mark> indicate what got appended and what didn't, on the line of
    Mark> the UIDPLUS stuff?

It seems to me that the failure case will almost always be resource
starvation (no disk, inodes, ...) after which your odds of being able
to handle succeeding messages in the multiappend approaches zero (over
the likely time period during which the MULTIAPPEND will try to
complete.)

You want to communicate this failure ASAP, which means sending
partial completion status between messages, which negates most of
the benefit (by adding that evil RTT back in).

Factor the abort processing in with intelligent size handling and
you've engineered APPEND.

So, where I see MULTIAPPEND being a win is for servers that use a single-
file-per-mailbox (or equivelent) format where streamed appends are cheap,
but append transactions aren't. In it's current state, I wouldn't implement
it soley as a protocol performance enhancement, for the reasons I outline
above. I don't see how those issues can be addressed without turning it
back into the existing APPEND. 

--lyndon

Date: Mon, 13 Sep 1999 15:09:34 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append 
To: Cyrus Daboo <[email-masked]>
cc: Mark Crispin <[email-masked]>, Lyndon Nerenberg <[email-masked]>, IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 18:10:20 -0400, Cyrus Daboo wrote:
> It seems to me if the client uses non-synchronising literals to do the
> multi-append then there is no real way to recover from a failure other than
> a NO/BAD to the entire command.

There is another choice.  We could have two flavors of multi-append, one which
does a NO/BAD to the entire command if there is any failure, and the other
which will succeed with appends up to the point of the failure.  It would then
return an untagged response indicating the extent of the partial success, and
then the NO/BAD.

This would make append a rather odd bird as far as IMAP goes.  The likelihood
is high that the server would not buffer up all the messages and then start
appending at the terminating CRLF (which a strict interpretation of IMAP would
mandate), but instead would append as the messages come in (which makes much
more implementation and operational sense).

Where this becomes strange is that a syntactically invalid command could also
have this behavior (hence "NO/BAD" rather than "NO").  I don't think that we
should worry too much about this since bad syntax never happens with the
software we experts write.  ;-) ;-) ;-) ;-) ;-)

> S: a APPEND INBOX {11}+
> C: From: Cyrus
> C:  {0}
> S: + [OK MULTIAPPEND TOTAL 1]
> C:  {10}+
> S: From: Mark
> C:  {0}
> S: + [NO MULTIAPPEND TOTAL 1]
> C: <CRLF>
> S: OK MULTIAPPEND succeeded for 1 message

With synchronized literals:

S: a APPEND INBOX {11}
C: From: Cyrus
C:  {0}
S: + I got that message!
C:  {10}
S: NO [APPEND 1] MULTIAPPEND failed after 1 message due to disk quota exceeded

Date: Mon, 13 Sep 1999 18:10:20 -0400
From: Cyrus Daboo <[email-masked]>
To: Mark Crispin <[email-masked]>, Lyndon Nerenberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append 
Sender: [email-masked]

--On Monday, September 13, 1999 2:29 PM -0700 Mark Crispin
<[email-masked]> wrote:

> Really?  LITERAL+ eliminates 50% of the RTTs and was supposedly a major
> win for those servers which support it.  The combination of MULTIAPPEND
> and LITERAL+ would eliminate all but one RTT.
> 
> So, what about some sort of additional untagged response to indicate what
> got appended and what didn't, on the line of the UIDPLUS stuff?
> 
> I appreciate your expression of non-opposition, but I'd like to see if
> something can be done to make you guys be enthusiastic supporters.

It seems to me if the client uses non-synchronising literals to do the
multi-append then there is no real way to recover from a failure other than
a NO/BAD to the entire command. If the client were prepared to tolerate
this in order to eliminate RTTs that would be fine.

However, if RTTs were not so much of an issue as opposed to the server
overhead of multiple APPEND commands, then its possible to use a
combination of non-non-synchronising literals for the message interpersed
with non-synchronising literals to check with the server to see if the last
append completed:

S: a APPEND INBOX {11}+
C: From: Cyrus
C:  {0}
S: + [OK MULTIAPPEND TOTAL 1]
C:  {10}+
S: From: Mark
C:  {0}
S: + [NO MULTIAPPEND TOTAL 1]
C: <CRLF>
S: OK MULTIAPPEND succeeded for 1 message

--
Cyrus

From: Erik Forsberg <[email-masked]>
To: Mark Crispin <[email-masked]>
Cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Date: Mon, 13 Sep 1999 14:50:37 -0700 (Pacific Daylight Time)
Sender: [email-masked]

Argh, of course it is CRLF (instead of a literal) I am looking for.
Forget my objection. Responded too quickly.

On Mon, 13 Sep 1999 14:11:24 -0700 Mark Crispin <[email-masked]> wrote:

> On Mon, 13 Sep 1999 14:05:42 -0700 (Pacific Daylight Time), Erik Forsberg
> wrote:
> > Implementation difficulty here.
> > It doesnt seem like you can detect the last append_message without reading
> > ahead and detecting that next token is SPACE (instead of what goes in a tag)
> 
> Actually, it's detecting that the next token is a SPACE as opposed to a CRLF
> (marking end of command).  You wouldn't look for a tag until you get to the
> start-of-command portion of your parse loop.
> 
> This isn't the only command which has this characteristic; SEARCH stands out
> in the base specification; and the SORT, THREAD, and extended LIST proposals
> also act in the same way.
> 
> > That causes problems in my server implementation as I make a distinction
> > between waiting for the next IMAP4 command (because the client is idle, you
> > need to check for new mail, flag updates, etc) and simply waiting for the
> > next token within a command.
> 
> Is the issue that you actually enter command execution for APPEND when you
> receive the literal, as opposed to waiting until you get the CRLF to end the
> command?  What happens if the client does
> 	001 APPEND foobar {3}
> 	zap barf
> Do you append "zap" to mailbox foobar then return a BAD for "barf"?  If so,
> that's wrong; foobar should not be affected by this command at all (or if it
> is, it should be reverted to its prior state).
> 
> In any case, MULTIAPPEND is an extension and hence optional; there's no
> requirement that you implement it in your server, and no client will send you
> one unless you advertise it.  So, you could ignore MULTIAPPEND if it presents
> implementation problems and remain fully-compliant.  I don't implement all the
> extensions either.
> 
> Is there something that I'm missing that would cause you problems?
> 

----------------------
Erik Forsberg
[email-masked]

Date: Mon, 13 Sep 1999 14:29:56 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append 
To: Lyndon Nerenberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 15:25:18 -0600, Lyndon Nerenberg wrote:
> This would be my concern as well. For the UW server backing out should be
> easy -- just don't rename the new mailbox file over the old one.

Actually, it's "ftruncate() the mailbox file back to its old size and adjust
the dates."  You can't "rename the new mailbox file over the old one" with the
standard UNIX format; too many mail delivery agents depend upon system call
locking on the mail file (as opposed to .lock files) which mandate that the
inode be preserved.  A *major* hassle.

> It would
> be more of a problem for us as we would have to do additional checkpointing,
> and wrap the whole thing up in a transaction in case we had to do a roll
> back.

Well, let's talk about this.  I'm willing to discuss a mechanism to indicate
"partial success" for multi-append.  It may be a good idea anyway; it seems
wasteful to toss out all that work.

Perhaps have some mechanism to indicate total size of the append?

> Then again, because of how we store our messages, multiple APPEND
> operations are not a performance hit for us.

Don't you have to do various stat()s and/or database lookups/locks to validate
the mailbox and plop additional messages down into the mailbox?  Even if your
format does this faster than standard UNIX format (just about anything is
better than standard UNIX format!!), I still think that you can't do a
streaming upload without per-message pauses.

> The minor increase in
> throughput from eliminating the extra RTTs wouldn't justify the increased
> complexity it would introduce, so it's unlikely we would implement this
> extension in our server.

Really?  LITERAL+ eliminates 50% of the RTTs and was supposedly a major win
for those servers which support it.  The combination of MULTIAPPEND and
LITERAL+ would eliminate all but one RTT.

So, what about some sort of additional untagged response to indicate what got
appended and what didn't, on the line of the UIDPLUS stuff?

I appreciate your expression of non-opposition, but I'd like to see if
something can be done to make you guys be enthusiastic supporters.

To: Mark Crispin <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append 
Date: Mon, 13 Sep 1999 15:25:18 -0600
From: Lyndon Nerenberg <[email-masked]>
Sender: [email-masked]

>>>>> "Mark" == Mark Crispin <[email-masked]> writes:

    Mark> The one issue of contention may be what happens on a partial
    Mark> failure; e.g.  running out of disk quota after several
    Mark> messages but before the last message.  I think that
    Mark> consistancy with the rest of IMAP, as well as the
    Mark> impossibility of the client knowing what succeeded and what
    Mark> failed if LITERAL+ is used with this feature, mandates that
    Mark> the entire APPEND fail and the mailbox be reverted to the
    Mark> state prior to the APPEND.

This would be my concern as well. For the UW server backing out should be
easy -- just don't rename the new mailbox file over the old one.  It would
be more of a problem for us as we would have to do additional checkpointing,
and wrap the whole thing up in a transaction in case we had to do a roll
back.  Then again, because of how we store our messages, multiple APPEND
operations are not a performance hit for us.  The minor increase in
throughput from eliminating the extra RTTs wouldn't justify the increased
complexity it would introduce, so it's unlikely we would implement this
extension in our server.  (Which is not the same as saying I would oppose
the extension.)

--lyndon

Date: Mon, 13 Sep 1999 14:11:24 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: Re: multi-append
To: Erik Forsberg <[email-masked]>
cc: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

On Mon, 13 Sep 1999 14:05:42 -0700 (Pacific Daylight Time), Erik Forsberg
wrote:
> Implementation difficulty here.
> It doesnt seem like you can detect the last append_message without reading
> ahead and detecting that next token is SPACE (instead of what goes in a tag)

Actually, it's detecting that the next token is a SPACE as opposed to a CRLF
(marking end of command).  You wouldn't look for a tag until you get to the
start-of-command portion of your parse loop.

This isn't the only command which has this characteristic; SEARCH stands out
in the base specification; and the SORT, THREAD, and extended LIST proposals
also act in the same way.

> That causes problems in my server implementation as I make a distinction
> between waiting for the next IMAP4 command (because the client is idle, you
> need to check for new mail, flag updates, etc) and simply waiting for the
> next token within a command.

Is the issue that you actually enter command execution for APPEND when you
receive the literal, as opposed to waiting until you get the CRLF to end the
command?  What happens if the client does
	001 APPEND foobar {3}
	zap barf
Do you append "zap" to mailbox foobar then return a BAD for "barf"?  If so,
that's wrong; foobar should not be affected by this command at all (or if it
is, it should be reverted to its prior state).

In any case, MULTIAPPEND is an extension and hence optional; there's no
requirement that you implement it in your server, and no client will send you
one unless you advertise it.  So, you could ignore MULTIAPPEND if it presents
implementation problems and remain fully-compliant.  I don't implement all the
extensions either.

Is there something that I'm missing that would cause you problems?

From: Erik Forsberg <[email-masked]>
To: Mark Crispin <[email-masked]>
Cc: IMAP Extensions WG <[email-masked]>
Subject: Re: multi-append
Date: Mon, 13 Sep 1999 14:05:42 -0700 (Pacific Daylight Time)
Sender: [email-masked]

Implementation difficulty here.
It doesnt seem like you can detect the last append_message without reading ahead
and detecting that next token is SPACE (instead of what goes in a tag)
That causes problems in my server implementation as I make a distinction
between waiting for the next IMAP4 command (because the client is idle, you
need to check for new mail, flag updates, etc) and simply waiting for the
next token within a command.

On Mon, 13 Sep 1999 13:15:54 -0700 Mark Crispin <[email-masked]> wrote:

> I would like to add an extension called MULTIAPPEND.  This is an upwards
> compatible extension to the RFC 2060 APPEND command.
> 
> A server which advertises the MULTIAPPEND capability permits more than one
> message in the same append command.  In other words, the APPEND grammar
> becomes:
> 
> append          = "APPEND" SPACE mailbox 1*append_message
> append_message  = [SPACE flag_list] [SPACE date_time] SPACE literal
> 
> MULTIAPPEND provides the same RTT savings offered by the LITERAL+ extension
> with the current APPEND.  When MULTIAPPEND is used in conjunction with
> LITERAL+, the entire upload is a single RTT.
> 
> There is another advantage, which is a major win for my server; the procedure
> for opening and closing the destination mailbox only needs to be done once
> instead of per-message.  We've determined that for the standard UNIX format of
> mail, the open/close and lock/unlock overhead is a major part of the overall
> time spent in multiple appends.
> 
> I believe that this extension should be non-controversial; it is upwards
> compatible and is at least a minor win for everybody (because of RTTs) and can
> potentially be a major win.  Does anyone disagree?  If not, do we have
> concensus to put out an ID and give it accelerated approval in the WG (with
> hopefully minimal discussion) as a Proposed Standard?
> 
> The one issue of contention may be what happens on a partial failure; e.g.
> running out of disk quota after several messages but before the last message.
> I think that consistancy with the rest of IMAP, as well as the impossibility
> of the client knowing what succeeded and what failed if LITERAL+ is used with
> this feature, mandates that the entire APPEND fail and the mailbox be reverted
> to the state prior to the APPEND.
> 

----------------------
Erik Forsberg
[email-masked]

Date: Mon, 13 Sep 1999 13:15:54 -0700 (PDT)
From: Mark Crispin <[email-masked]>
Subject: multi-append
To: IMAP Extensions WG <[email-masked]>
Sender: [email-masked]

I would like to add an extension called MULTIAPPEND.  This is an upwards
compatible extension to the RFC 2060 APPEND command.

A server which advertises the MULTIAPPEND capability permits more than one
message in the same append command.  In other words, the APPEND grammar
becomes:

append          = "APPEND" SPACE mailbox 1*append_message
append_message  = [SPACE flag_list] [SPACE date_time] SPACE literal

MULTIAPPEND provides the same RTT savings offered by the LITERAL+ extension
with the current APPEND.  When MULTIAPPEND is used in conjunction with
LITERAL+, the entire upload is a single RTT.

There is another advantage, which is a major win for my server; the procedure
for opening and closing the destination mailbox only needs to be done once
instead of per-message.  We've determined that for the standard UNIX format of
mail, the open/close and lock/unlock overhead is a major part of the overall
time spent in multiple appends.

I believe that this extension should be non-controversial; it is upwards
compatible and is at least a minor win for everybody (because of RTTs) and can
potentially be a major win.  Does anyone disagree?  If not, do we have
concensus to put out an ID and give it accelerated approval in the WG (with
hopefully minimal discussion) as a Proposed Standard?

The one issue of contention may be what happens on a partial failure; e.g.
running out of disk quota after several messages but before the last message.
I think that consistancy with the rest of IMAP, as well as the impossibility
of the client knowing what succeeded and what failed if LITERAL+ is used with
this feature, mandates that the entire APPEND fail and the mailbox be reverted
to the state prior to the APPEND.