Subject: copying commitment and deadlock

From: Alex Rousskov <[email-masked]>
Date: Tue, 18 Mar 2003 22:58:26 -0700 (MST)

If we are to support copying (per data chunk or per message), we need
to decide when the copying commitment expires. In other words, when
the OPES dispatcher can release data previously sent with the "copied"
flag set.

If the callout server uses "data-have-as-is" message that matches the
entire data block sent by the dispatcher, then the dispatcher can
probably free the data (we do not have to support duplication of data,
I guess; if a byte range has been sent, it is unlikely to be sent
again).

However, what happens if there is a partial match? Should the
dispatcher keep the leftovers until the end of the message? Until
copied data with higher offset is reused? Until wont-need message is
received? A combination of these?

There is also a potential deadlock situation here. If the amount of
dispatcher buffer is limited, the dispatcher may stop sending more
data to the callout server, and the callout server may need more data
to respond (and let OPES dispatcher clear some of the copied chunks).
We may want to address this explicitly instead of relying on
timeouts.

Copying data introduces state and blocking (due to buffer
limitations). We need to find a simple way to support copying in many
environments while keeping the protocol simple enough. I am seeking
suggestions on what to support or where to draw a line. My current
intention is to support "getting out of the loop" for OPES processor
and nothing else, to optimize for the most common case. Comments?

Thanks,

Alex.

---

From: Markus Hofmann <[email-masked]>
Date: Fri, 21 Mar 2003 10:10:48 -0500

> I guess; if a byte range has been sent, it is unlikely to be sent

Yup, I would think so. When the callout server replies with a 
<data-as-is>, the OPES processor starts forwarding the refered to, 
copied data segments and frees the respective buffer as the data is 
forwarded.

> received? A combination of these?

Hm... I would assume until either data with higher offset is reused or 
the end of the message is reached.

In the first case, it's probably safe to assume that data with a lower 
offset has already been handled properly (since we require ordered and 
reliable delivery of callout protocol messages). In the later case, 
the callout transaction is finished and the associated buffers can be 
release (after possibly forwarding copied data).

Even if the callout server sends a <wont-need>  message, the OPES 
processor might prefer to keep a copy, for example to recover from a 
potential failure of the callout server.

> We may want to address this explicitly instead of relying on

Now, this doesn't solve the problem, but I'm just wondering why would 
the OPES processor stop sending more data when its buffer is limited 
or filled up? The OPES processor would still receive data from the 
direction of the content produce/consumer, right? In this case, if the 
OPES processor runs out of buffer, the data would be lost anyway so 
the OPES processor can also keep forwarding it to the callout server...

Thanks,
   Markus

---

From: Alex Rousskov <[email-masked]>
Date: Fri, 21 Mar 2003 09:50:08 -0700 (MST)

On Fri, 21 Mar 2003, Markus Hofmann wrote:

> Hm... I would assume until either data with higher offset is reused
> or the end of the message is reached.
>
> In the first case, it's probably safe to assume that data with a
> lower offset has already been handled properly (since we require
> ordered and reliable delivery of callout protocol messages).

It is not safe in general because there are examples where callout
server might want to reorder message content (e.g., change the parts
order of a multipart e-mail message or move an ad banner to the end of
an HTML page). To make it safe, we would have to explicitly document
this assumption (and, hence, prevent copying optimization in those
rare(?) cases where callout server needs to change the order of
message parts).

> In the later case, the callout transaction is finished and the
> associated buffers can be release (after possibly forwarding copied
> data).

Yes.

> potential failure of the callout server.

Sure. This kind of copying is out of OCP scope.

> > There is also a potential deadlock situation here. If the amount
> > of dispatcher buffer is limited, the dispatcher may stop sending
> > more data to the callout server, and the callout server may need
> > more data to respond (and let OPES dispatcher clear some of the
> > copied chunks). We may want to address this explicitly instead of
> > relying on timeouts.
>

The OPES processor will stop reading incoming data when its buffers
are full. That's how most proxies (and servers) I know work today. One
can always control its input, relying on transport protocol to slow
down the producer (TCP) or to drop packets (UDP).

When deadlock occurs, the OPES processor is not reading incoming data
because its buffers are full, and the callout server is not sending
any data back because it waits for more incoming data to make a
decision.

Note that we can make the callout server aware of the deadlock by
sending a <data-pause> message to it (possibly two messages, the last
one in response to <data-need> message from the callout server).
However, "being aware" does not solve the problem. We need either a
mechanism to break the deadlock or protocol changes to avoid it.
Relying on timeouts is bad in this case because it is not an abnormal
situation.

Suggestions?

Alex.

---

From: Markus Hofmann <[email-masked]>
Date: Mon, 24 Mar 2003 14:13:45 -0500

Alex Rousskov wrote:

> server might want to reorder message content (e.g., change the
> parts order of a multipart e-mail message or move an ad banner to
> the end of an HTML page). To make it safe, we would have to
> explicitly document this assumption (and, hence, prevent copying
> optimization in those rare(?) cases where callout server needs to
> change the order of message parts).

Yup, see your point, agreed.

Question is whether added complexity to deal with such rare(?) cases
is justified, or whether we believe that it might be OK to keep it
less complex. Anyone any thoughts on that?

>  are full. That's how most proxies (and servers) I know work today.
> One can always control its input, relying on transport protocol to
> slow down the producer (TCP) or to drop packets (UDP).
> 
> When deadlock occurs, the OPES processor is not reading incoming
> data because its buffers are full, and the callout server is not
> sending any data back because it waits for more incoming data to
> make a decision.

There are buffers at different levels, and I was *not* refering to TCP
buffers or so, but rather to the buffers that temporarily store the
application message, assuming the OPES processor would still be able
to receive TCP/UDP packets, but just no longer be able to temporarily
store the appliction message (or parts of it). In that case, wouldn't
the current protocol design already include everything that's needed?

Example: The OPES processor starts receiving an application message 
(e.g. from a Web server). Since it still has buffer available, it 
copies the application message and indicates this to the callout 
server by setting the [copied] flag. If the buffer at the OPES 
processor now fills to, let's say, 90%, the OPES processor keeps 
forwarding the received application messages to the callout server, 
but no longer stores them in its local buffer. This is indicated to 
the callout server by *not* setting the copied flag in subsequent 
callout messages. As such, no deadlock occurs. What's missing?

Thanks,
-Markus

---

From: Alex Rousskov <[email-masked]>
Date: Mon, 24 Mar 2003 13:13:02 -0700 (MST)

> less complex. Anyone any thoughts on that?

I suggest that we keep it simple unless somebody argues that
reordering message parts is common/important enough to be optimized
for.

> > The OPES processor will stop reading incoming data when its
> > buffers are full. That's how most proxies (and servers) I know
> > work today. One can always control its input, relying on transport
> > protocol to slow down the producer (TCP) or to drop packets (UDP).
> >

I was referring to the same case. And yes, the deadlock problem does
exist if we want to support "copying commitment" and, hence, support
callout server ability to get out of the loop in its own.

> server by setting the [copied] flag.

If a per-OPES-message [copied] flag is used, then there is no problem
(and no possibility for "getting out of the loop" optimization).
[Copied] flag creates no problems because it applies to the current
OPES data message. That data is either copied or not. There is no
commitment that applies to future data chunks.

Copying _commitment_ (i.e, "I will copy from now on" flag) allows for
"getting out of the loop" optimization but is also subject to
deadlock.

> If the buffer at the OPES processor now fills to, let's say, 90%,
> the OPES processor keeps forwarding the received application
> messages to the callout server, but no longer stores them in its
> local buffer. This is indicated to the callout server by *not*
> setting the copied flag in subsequent callout messages. As such, no
> deadlock occurs. What's missing?

Nothing. You give an example of how [copied] flag works. Your example
is correct, and there is no deadlock problem. Note that the callout
server in your example cannot get out of the loop because at no point
in time it has a guarantee that no data is lost if it does.

Here is a summary:

	- [copied] flag is a simple per-message optimization.
	  We need to decide when the processor can get rid
	  of the copied data. Other than that, there are no
	  significant problems or complications I am aware of.
	  The [copied] flag alone does not, however, let callout
	  servers to get out of the processing loop.

	- [will-always-copy] commitment allows the callout
	  server to get out of the loop. This optimization
	  is needed for efficient processing of large
	  messages (or streams) that turn out to be not
	  interesting to the callout server. This optimization
	  may cause a deadlock if used "as is".

One way to avoid the deadlock is to support the following
confirmation/dialog:

	server: I want to get out of the loop!
	processor: OK, you can get out of the loop after
		processing first N bytes of this application
		message (N could be zero). I will stop
		sending you more data as of now.
	server: here is the data you asked for (could be
		several data messages)
	server: I am out of the loop

Unfortunately, supporting this kind of dialog efficiently requires
dedicated/priority connection: The primary data connection may be
clogged by (yet unprocessed) data messages to the callout server,
preventing the "OK" response from reaching the server fast. If the
"OK" response is slow, there may be little gain from the optimization
because a lot of data messages would be processed by then.

Alex.

---

From: Markus Hofmann <[email-masked]>
Date: Mon, 24 Mar 2003 18:47:03 -0500

Alex Rousskov wrote:

> [...] I suggest that we keep it simple unless somebody argues that 

Agreed! Anyone else, if there are good reasons not to do so, now is
the time to speak up!

> [...] Copying _commitment_ (i.e, "I will copy from now on" flag) 
> allows for "getting out of the loop" optimization but is also 
> subject to deadlock.

Got it, I somehow missed that you were talking about the copying
*commitment*.

 > [...] One way to avoid the deadlock is to support the following
 > confirmation/dialog:
 >
 > "OK" response is slow, there may be little gain from the
 > optimization because a lot of data messages would be processed by
 > then.

OK, let me see whether I understood the scenario correctly: The 
callout server has decided that it has seen enough and wants to get 
out of the loop as quickly as possible. This is signaled to the OPES 
processor and happens at "Time A". After receiving the signal from the 
callout server, the OPES processor sets a specific "end" flag in the 
next outgoing message, indicating to the callout processor the end of 
the specific transaction. This message is received by the callout 
server at "Time B". Between "Time A" and "Time B", the callout server 
can discard any message it receives for this transaction and that has 
the [copied] flag set (doesn't seem to be too much overhed). Messages 
without the [copied] flag set have to be sent back to the OPES 
processor (which has to be done anyway...).

Or are you more concerned about messages that might be stuck in the 
local queues at the OPES processor? But this seems to be more of a 
local implementation issue...

Thanks,
   Markus

---

From: Alex Rousskov <[email-masked]>
Date: Mon, 24 Mar 2003 17:59:04 -0700 (MST)

On Mon, 24 Mar 2003, Markus Hofmann wrote:

>  > Unfortunately, supporting this kind of dialog efficiently
>  > requires dedicated/priority connection: The primary data
>  > connection may be clogged by (yet unprocessed) data messages to
>  > the callout server, preventing the "OK" response from reaching
>  > the server fast. If the "OK" response is slow, there may be
>  > little gain from the optimization because a lot of data messages
>  > would be processed by then.
>
> the specific transaction.

Yes. This message can be sent on a "high priority" connection, but in
that case, it has to tell the callout server if there are any
(possibly queued) data messages _without_ the [copied] flag. The
protocol needs to make sure that no data is lost when the callout
server "disconnects".

If that message is not sent on a "high priority" connection, no
special steps are needed. However, the delay between A and B can be
significant in that case. The longer the delay, the smaller is the
benefit of getting the callout server out of the loop...

> This message is received by the callout server at "Time B". Between
> "Time A" and "Time B", the callout server can discard any message it
> receives for this transaction and that has the [copied] flag set
> (doesn't seem to be too much overhed).

Not exactly. The callout server must send either <data-as-is> or
<data-have> messages until Time B (at least). The server is still in
the loop. Recall that there is no commitment -- some of the [still
queued] data messages from the OPES processor may not have a [copied]
flag; we need to make sure the loop does not break until there are no
such messages. Only the OPES processor knows whether such messages
exist (because it has already sent them). The callout server does not
know (because it has not receive them yet).

Also, "Time B" is not the time when "OK, disconnect" message is
received by the callout server. It is the time when the last uncopied
data is forwarded back to the processor. The information about still
unforwarded data will be present in the "OK, disconnect" message. If
there is no such data (at the time the OK message has been received),
the callout server may disconnect without processing any further
messages.

> Messages without the [copied] flag set have to be sent back to the
> OPES processor (which has to be done anyway...).

Yes.

We could say that <data-as-is> messages are not required in the above
case, but it complicates the protocol (essentially creates multiple
sources of data) without much benefit. <data-as-is> messages as small.
To keep things simple, both <data-as-is> and <data-have> messages need
to be sent, as usual.

> local implementation issue...

I am concerned about messages without the [copied] flag that were
"sent" but has not been "processed" by the callout server yet. These
messages can be in TCP or application buffers on either side. The
above scheme avoids [I-will-always-copy] commitment to prevent
deadlocks. As a side effect, we can never be sure that all unprocessed
messages have [copied] flag. The scheme lets OPES processor inform the
server when it is safe to ignore unprocessed messages (if any). Again,
the processor knows whether there are any data chunks that were sent
to the server without copying and were not sent back.

I am not saying the above scheme is the best solution. It is just an
example that may inspire better schemes.

Here is a simplified version that is almost as "fast":

	server-to-processor: <I-want-to-disconnect-ASAP>
	processor stops sending more data
	processor waits for all pending data up to the last
		uncopied chunk to be forwarded via
		<data-have> or <data-as-is> messages from
		the server
	processor-to-server: <app-message-end reason=disconnect>

There is only one new message needed (<I-want-to-disconnect-ASAP>) as
long as <app-message-end> message can be sent on a "high-priority"
connection (the latter will be done only when there is no pending
uncopied data, of course).

This scheme is simpler because the OPES processor does not have to
tell the server about the last uncopied chunk. On the other hand, this
scheme is slower because the server cannot disconnect until it
receives that <app-message-end> message. The first scheme allowed the
server to disconnect immediately after sending the last uncopied
chunk. The delay difference is one "round trip" time.

Summary:

	0) no [copied] flag does not allow for any optimizations
	   but is very simple

	A) plain [copied] flag alone does not allow for the
	  callout server to get out of the loop (scheme A)

	B) copying commitment is the most efficient optimization
	  but has deadlocks (scheme B)

	C) <I-want-out-of-the-loop> scheme with details about
	  the last uncopied chunk exchanged is more complex
	  than copying commitment (scheme C)

	D) <I-want-out-of-the-loop> scheme without details about
	  the last uncopied chunk exchanged is simpler but
	  slower than scheme C

Thanks,

Alex.

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Mon, 24 Mar 2003 19:38:42 -0700

I started trying to read this thread and I find that I need a summary
of how we got here and what we are trying to accomplish.  I can follow
the details, but cannot tell why we are discussing what seems a fairly
complicated interaction.  I'm uncomfortable about messages that
implied that we are trying to support a layer 7 switch architecture.
If that's at the heart of this, I'm dismayed.  If not, I don't know
what's going on.  I have a lot of trouble understanding the value of
this if there's anything other than "this is a copied stream" and
"this is not a copied stream".

Could someone provide a succinct description of the problem?

Hilarie

---

From: Alex Rousskov <[email-masked]>
Date: Mon, 24 Mar 2003 20:28:11 -0700 (MST)

On Mon, 24 Mar 2003, The Purple Streak, Hilarie Orman wrote:

> I started trying to read this thread and I find that I need a
> summary of how we got here and what we are trying to accomplish.  I
> can follow the details, but cannot tell why we are discussing what
> seems a fairly complicated interaction.

We are discussing this for two reasons (see the first message
on this thread for details):

	- we need to decide when an OPES processor can
	  get rid of the data that was previously marked
	  with a [copied] flag (the semantics of the flag
	  does not imply an efficient end-of-life moment for
	  copies)

	- we need to decide how we can let callout
	  server to get out of the loop without losing any
	  uncopied data (commitment-based schemes are simple and
	  fast but lead to deadlocks, other schemes are more complex
	  and slower)

Both decisions must be documented in the callout protocol specs if
copying-related features are to be supported.

> I'm uncomfortable about messages that implied that we are trying to
> support a layer 7 switch architecture. If that's at the heart of
> this, I'm dismayed.  If not, I don't know what's going on.

IIRC, the only suggestion relevant to L7 switching was that no copying
is necessary at all -- we could say that [the initial version of] the
callout protocol supports "move" and does not support "copy"
operations. L7 switch is just an example of an application-level proxy
that may not support "copy" operations. I have argued that "copy"
optimization is too valuable to get rid of.

> I have a lot of trouble understanding the value of this if there's
> anything other than "this is a copied stream" and "this is not a
> copied stream".

This discussion exists because some of us consider copying
optimizations valuable (worth discussing and implementing) but those
optimizations raise questions that protocol needs to address.

> Could someone provide a succinct description of the problem?

The first message on this thread describes both problems. The above is
a short summary. However, since I wrote both, it would be great if
somebody else can re-describe the problem for Hilarie in better words.
If there are no volunteers, we can just wait for the protocol draft to
be released this week; hopefully, it will clarify the problems.

Thank you,

Alex.

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Tue, 25 Mar 2003 01:00:07 -0700

What's the compelling reason for message by message copy directives?

Hilarie

---

From: Alex Rousskov <[email-masked]>
Date: Tue, 25 Mar 2003 07:27:17 -0700 (MST)

> What's the compelling reason for message by message copy directives?

The reason for per-message [copied] flag is to optimize for the common
case where callout server does not modify the data. OPES processor
will often keep a copy anyway, for many reasons. There is no need to
send the same data back and forth; one direction is enough in this
case.

The reasons for copying commitment or a similar mechanism is to
optimize for the common case where the callout server wants to get out
of the loop because it does not expect any/further modifications.

Alex.

---

From: Markus Hofmann <[email-masked]>
Date: Tue, 25 Mar 2003 11:00:10 -0500

Alex Rousskov wrote:

> such messages. 

You're right, I ignored that the callout server has to send 
<data-as-is> rather than just discarding the messages. I somehow 
assumed the OPES processor would implicitly interpret "gaps" in the 
returned message stream as <data-as-is> (since we've reliable and 
ordered transport). Probably not a good idea...

> the callout server may disconnect without processing any further

Sure, if you assume the "disconnect" signal can be send on a "high 
priority" connection, I assumed it would be send with the same 
priority as the other transaction messages (which might give a smaller 
benefit, as you sated correctly).

> To keep things simple, both <data-as-is> and <data-have> messages need

That's sort of what I had in mind, but I now agree that the overhead 
of <data-as-is> messages is small and that it would probably not 
justify added complexity.

> chunk. The delay difference is one "round trip" time.

Yup, agreed. I'm somehow leaning towards the second, simplified 
alternative - simply for simplicity :) But these are just my 2 cents.

> 	0) no [copied] flag does not allow for any optimizations

I consider the [copied] flag useful enough to keep it!

> 	  the last uncopied chunk exchanged is simpler but

Option (D) seems to be reasonable tradeoff between complexity and 
efficieny...

-Markus

---

From: "The Purple Streak, Hilarie Orman" <[email-masked]>
Date: Tue, 25 Mar 2003 10:32:01 -0700

Then the condition is that a stream is opened in copy mode by the OPES
processor and the callout server needs to signal "copy mode on this
stream will cease."

If the underlying transport is reliable, like TCP, there's no problem
if you adopt the rule that acked data on a copied stream MUST be
copied by the callout server and un-acked data cannot be deleted by the
OPES processor.

If the underlying transport is not reliable, then I submit that the decision
has already been made that it is OK to lose some data.  In that case, there's
no need to have strong commitments - some data might be lost in a transition,
but that's OK.

We need to be careful not to reinvent things already solved at the
transport layer.

Hilarie

---

From: Alex Rousskov <[email-masked]>
Date: Tue, 25 Mar 2003 10:58:59 -0700 (MST)

On Tue, 25 Mar 2003, The Purple Streak, Hilarie Orman wrote:

> Then the condition is that a stream is opened in copy mode by the
> OPES processor and the callout server needs to signal "copy mode on
> this stream will cease."

Yes, but this simple scheme may lead to a deadlock (which is the
subject of this thread, see below for more info).

> copied by the callout server and un-acked data cannot be deleted by the

I am not sure I understand exactly what you are saying (what is acked
data?), but transport protocol does not solve the higher-level
problems we are discussing here. There are two different problems:

The first problem is about OPES processor deleting its copy of the
data (previously marked with a [copied] OCP flag). Here are some of
the related issues:

	- When a copy of the data can be deleted (explicit
	  notification by callout server, implicit order-based
	  guess, other)? We have to keep in mind that the
	  callout server does not care about processor
	  buffering problems so there is a "conflict of interests"
	  here.

	- Do we want to support reordering of copied data by the
	  callout processor?

	- Granularity of <data-as-is> messages (can callout server
	  refer to something other than the exact same data chunk
	  sent by the OPES processor? Do we want to support partial
	  as-is messages?)

The second problem is that a "stream opened in copy mode" may lead to
a deadlock when the OPES processor is waiting for more buffer space
and, hence, is not sending more data to the callout server, and the
callout server is waiting for more data from the OPES processor to
make a modification decision and, hence, is not returning any messages
back, keeping processor buffers full. Again, transport protocol
(reliable or not) does not solve this deadlock. It is a higher-level
problem that is related to OPES processor buffers for copied messages,
not transport.

Hope this clarifies,

Alex.