Subject: LCUP show stopper

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Mon, 02 Jun 2003 16:11:08 -0700

To LCUP,

Let us try to describe what we consider to be the primary
show-stopping issue in the draft-ietf-ldup-lcup proposal.  For
convenience, we will refer to this below as LCUP.

LCUP expects server implementations to maintain sufficient history
so that they provide incremental refreshes of content instead of
full reloads on subsequent client requests.  For subsequent client
request, full reloads should be the exception not the norm.  We
argue that full reloads will actually be more of the norm, certainly
not limited to rare exceptions.
 
As you know, we think it is not reasonable to require servers
maintain history information in order to support LCUP.  That forces
a particular design choice which may be counter to other design
factors, such as scalability.  However, we will focus our
discussions on servers which choose to maintain some amount of
historical information. 

We think LCUP misjudges the completeness of history information
that would need to be maintained to avoid reloads in the general
case and the complexity of computing the clients state based upon
that history (in order to determine what "deletes" need to be sent).

Complete history implies that server can compute the client's state
and generate the smallest amount of traffic to converge the client's
state to server's state based upon the information contained in the
cookie.  Of course, if we were to assume complete history, we could
do much better than sending complete copies of entries.
 
Sufficient history implies that the server is able to determine
which entry update and delete messages need to be delivered to the
client to converge its state to that of the server.       
 
Determining which entries need updating requires no history, the
server can simply send all entries presently meeting the search
criteria that have been updated since the previous request (based
upon time stamps).  However, determining which delete messages to
send requires history.

Minimally, the server needs to
  a) maintain history about deleted entries and
  b) track the time each entry was modified and/or renamed,

and send a delete message for each entry deleted or modified since
the previous content was provided.  That is, without additional
history, the server has to assume that all deletes, modifications,
and renames affected entries to leave the result set.  This is 
problematic as the server has to force a reload as a result of
modifications which are not and were not ever of interest to the
application.  That is, when a client is interested in 100 entries
of a 1,000,000 entry context and 10,000 (1%) were modified since
the last refresh, the server would have to prove most of these
10,000 entries were not previously in the result set otherwise
return an error indicating a full reload was required.  This is
because 1 update (1% of 100) and 9,999 delete messages are likely
far more traffic than 100 full entry messages.

Now, a server could maintain additional information about entry
renaming.  Then it could prove which entries could not possibly be
in the search's scope and trim out those "deletes".  However, unless
it maintained history of entry modifications (and other changes in
entry visibility based upon other factors), the server would still
have to send deletes for all modified entries which are in scope
regardless of whether they currently match the search criteria.
 
That is, without entry modification history, if the scope was subtree
covering 10% of the context (as described above), then 9000 of the
deletes could be eliminated.  The server would still have to send
1 update + 999 deletes.  If we assume 1K entry size (common for 
many directories), that's about the same amount of traffic as 
required for a full reload.

As another example, let's look at two general history maintenance
mechanism common in existing servers, tombstones and changelogs.
LDAP servers supporting these mechanisms generally do not maintain
history of old attribute types and values of modified or deleted
entries and, hence, cannot compute after an update operation an
entry's previous state.  If the server cannot compute the entry's
previous state, it cannot generally compute whether that entry was
previously in the LCUP result set.  It must assume that it was.
Hence, even where no or few modified or deleted entries were
previously in the result set, the server is forced to either send
delete messages for all of these entries or cause a full reload.
LCUP does not provide a reasonably efficient solution for the
LDAP servers maintaining history information through common
practices.
 
The first example was intended to be illustrative of one of many
use scenarios.  As a general solution to the client update problem,
we believe LCUP needs to work well in a wide variety of use scenarios
having different characteristics in factors like total number of         
entries, the amount of changes, the percent of in-scope entries,      
the percent of entries in the result set and average entry size.          
The second example was intended to illustrate that history information         
currently maintained in today's LDAP servers is not "sufficient
history" for LCUP purposes.

Basically, LCUP requires vendors to maintain "sufficient history"               
(significantly more than servers currently maintain today for other
purposes) when in many use scenarios that history is ineffective           
in reducing traffic.  And in use scenarios where that history might         
be effective, the protocol doesn't allow the server to fully take           
advantage of that history (because it doesn't support entry change
deltas).
 
It is our opinion that LCUP is generally not more suitable than           
persistent search solutions it was intended to replace, while coming        
at a significantly higher implementation cost (the cost of
maintaining/using "sufficient history").  After 3 years of LCUP
engineering, we don't yet have "running code".  Our (Jong and Kurt's)    
own efforts to develop a LCUP prototype were stopped shortly after    
we concluded LCUP was unsuitable.  We are currently pursuing a            
technical alternative.

Kurt and Jong

---

From: [email-masked]
Date: Mon, 2 Jun 2003 17:18:24 -0700

Kurt, Jong,
	In the section on applicability, the LCUP draft says:

>  1) The server stores some degree of historical state or change
>    information to reduce the amount of wire traffic required for
>    incremental synchronizations.  The optimal balance between server
>    state and wire traffic varies amongst implementations and usage
>    scenarios, and is therefore left in the hands of implementers.
>
	To me, you seem to be arguing below that the
approach (client pull, optimized by some server state) is invalid,
when my reading both of the draft and this text would be that this
approach allows a wide  range of variation in the balance between
optimizing wire traffic by increasing server state and optimizing
server scale by allowing for profligate returns.  While I certainly
respect your sense of the difficulty of implementation this might
pose to existing clients and servers, I'm not sure how this makes
this invalid.  It is an engineering balance between two costs,
and the protocol allows the balance to shift both ways.

	If I'm reading this right, you believe the text in 4.2.7 in particular
poses a problem:

>    Servers SHOULD keep
>    enough information about the attributes in the deleted entries to
>    determine if an entry should be removed from the result set.  Since
>    this may not be possible, the server MAY return an entry as having
>    left the result set even if it is not or never was in the client's
>    result set.  Clients MUST ignore these notifications.
>

	Clearly, maintaining this state does add a burden to the
server implementation and deployment, and servers which do not maintain
state might be compliant but would be  sub-optimal for the clients
using this protocol.  But it also seems clear that this state can be
maintained in a variety of conditions, and that the balance can be
shifted the other way when it cannot.  To me, this looks like
another engineering trade-off, not like a show stopper.

	I appreciate the time and effort you've taken in putting

>advantage of that history (because it doesn't support entry change

	is a good, short precis of your points.  I do see an engineering
disagreement here on how to balance increases in state for
deployed servers vs. the value it presents.  I don't see a show stopper,
though, as the draft acknowledges the possibility that maintaining state
will not be appropriate for all cases and provides other mechanisms for
them.  That those are sub-optimal from a consumption perspective
is not exactly surprising, given the basic design.

	Given my relative newness to this arena, it is entirely possible
that I have missed your point, and I invite your corrections (either privately
or on-list).
		regards,
			Ted Hardie