RE: Is State-based LDUP needed?

["Ed Reed" <eer@xxxxxxxxxxxxx>]

Hi Steven -

Thanks for the lucid response.  It's quite helpful to me.

The gist of my comments below are that I think your 3rd way
doesn't work for state-based systems that transmit updates
in CSN sequence (reasons below), but it works fine for log-based
systems (which I think are all anyone is planning to build, anyway).

So my base question remains - why bother making a distinction at 
all - let's drop state-based discussion all together and concentrate
on the log based system, instead.

=============

I think that the crux of this difference is that I've not been thinking that
statebased systems transmitted changes in strictly increasing CSN
order (within some other constraints, like sending schema changes first),
and I see that you MIGHT manage to do so.

The statebased systems with which I am familiar (Clearinghouse, NDS)
send for each entry it holds for which there are CSNs for values that
indicate, by the update vector held by the supplier for the consumer, 
the primatives needed to bring the consumer copy of that entry "up to date"
to the supplier's copy of that entry.  The consumer provides the
supplier a fresh snapshot of the consumer's ACTUAL update vector
at the beginning of the replication session so the supplier knows if
the consumer has gotten updates from others.  But the sequence
of changes is
  For each entry
      set of primatives
  end

so that changes for entry A are sent together, meaning that if applied, entry A will
be fully up to date and internally consistent.

But that's not the fully ordered CSN sequence that a log based system will use,
nor one that a statebased system trying to maintain CSN sequence will use.
They will send something more like

     sequence of primatives in time sequence

And, since the "current state" of an entry may very well have CSNs from
multiple replicaIDs.  In this case, if all primatives of each change have
been preserved (as with a log based system), they can be applied
as received and each entry will be "consistent" if not "up to date" (there
may be more primatives that would have been sent "later" in the session
had it not terminated.  But if all primatives of each change have NOT been
preserved, and the session is terminated, the consumer had better not
applied ANY of the changes because to do so would have left it with
SOME changes to the entry but not ALL changes to the entry (later
primatives not-yet-sent which overrode unpreserved primatives
may be needed to preserve entry integrity).

So - I agree that there's no difference in log and state based implementations
behavior in the protocol as long as the statebased system sends primatives
in CSN sequence AND consumers know that they MUST NOT apply the
changes unless ALL the changes in the session can be applied. If the
session is interrupted, NO changes should be applied to the consumer, from
the incomplete set received from the statebased supplier, because to
do so could leave entries with inconsistent states.

The particular case I'm worried about is this one where 3 replicas exist
on 3 different servers of the same replicationArea:

Server 1 (S1) creates entry A, setting two MUST attributes with correct values
Server 2 (S2) receives entry A with the two values
S2 modifies one of the entry A MUST values, but not the other
S2 begins replication session to S3 
   sends the creation of A with the first MUST attribute but not the second (which
     has a later CSN)
   sends other changes
   aborts the transfer without having gotten to the second MUST change for A

S3 now holds an invalid copy of A - it has only one MUST attribute instead of
two (the second would have come if the session had been completed).

S3 MUST NOT create the invalid entry A.  It either needs to hold the changes
from the session in suspense until it can complete the session and get the
rest of the primatives, or it must forget the whole thing.

Your statement "On the other hand, if the updates in a replication session are always
guaranteed to be in CSN order then the consumer can just apply them as
they are received. A state-based implementation can readily provide updates
in CSN order by sorting them in temporary storage before sending them to
the consumer." 

only applies if ALL the updates that apply to each entry are transmitted (not
just those that have not been "masked" by subsequent updates).

In your set of three approaches below, I agree that 1 and 2 work, but not
3.  The statebased system can order updates in CSN order, but it can't
recover the masked changes (if it could, it would be a log based system).

Now - someone may have figured out how to provide for a resumption of
replication sessions with statebased systems, but I don't know how it works.

BUT - the real question was, if no one's doing it, why bother worring about
that 3rd option - it works fine for log-based sytems, and if everyone is
doing log based systems, then there's no sweat.

Ed
      

=================
Ed Reed
Reed-Matthews, Inc.
+1 585 624 2402
http://www.Reed-Matthews.COM
Note:  Area code is 585

>>> "Steven Legg" <steven.legg@xxxxxxxxxxxxx> 01/18/02 12:30AM >>>

Ed,

Ed Reed wrote:
> I asked this question at the ldup meeting on Thursday, and agreed to post
> the question to the distribution list.
>
> Is anyone planning to implement state-based ldup?  If not - that is, if
there
> are not going to be at least two interoperable implementations of the
> proposed specification, should we not remove it from the ldup design now,
> rather than later?

For the most part I see the choice between a state-based implementation
and a log-based implementation as an internal implementation choice and
as such is out of scope for a protocol specification. To the fullest
extent possible we should remove the distinction and concentrate on the
externally visible behaviour of the LDUP servers.

I regard it as an internal choice because about the only place where the
choice of implementation manifests a difference in the external behaviour
of the server is in the ordering of changes in a replication session.
I have more to say about that below.


> The protocol will support it, but there are certainly places in the
> architecture and other documents where the different handling of change
> information required by the state-based scheme adds unnecessary text if
> noone is actually going to use it.

I couldn't find much text in draft-ietf-ldup-model-06.txt that related
specifically to log-based versus state-based implementation, and none
that needed to be in the document in any case.

Section 3.4 isn't needed at all. It doesn't add to the LDUP specification
in any way.

Regarding the last paragraph in 4.5.3:

   "The modifications that made up an LDAP Modify operation are
   presented in a sequence. This must be preserved when the
   resultant changes of this operation are replicated."

This paragraph can be dropped, along with sections 4.5.3.1 and 4.5.3.2.
URP describes how the CSNs are to be assigned such that the net effect
is preserved even if the primitives for the modifications get out of order.

Sections 10.3.1 (except the last paragraph) and 10.3.2 can be dropped.
URP describes these two cases more precisely and more completely.


> This is a pragmatic decision - I personally like state based schemes, even
> though there are things (like transaction replication) that I doubt
they'll
> ever be able to handle well.  Also, all the implementers I know are
focused
> on the log-based scheme, instead.  It seems easier for them to get their
> heads around, for some reason...
>
> So - I don't think it's appropriate for me to be the only one championing
it,
> and have reached the conclusion that if we can't find even two
implementers
> to build it, we should not bother including it in further work.

I agree with Tim here. The requirement is to have two interoperable
implementations of each of the options in the protocol. The internal details
of how an each implementation supports the protocol is irrelevant. We don't
necessarily need two state-based implementation to meet the interoperabiliy
requirements. Aside from the ordering issue I'm not sure there is anything
in the current LDUP specifications that is exclusive to state-based
implementations or exclusive to log-based implementations.

>
> If you're planning to build it, speak up.  If not, silence may well be
taken
> as assent to remove references to it from the various protocol documents.
>
> Best regards,
> Ed

Now for something not so completely different ...

In looking over your coverage matrix I found three cases of perceived
fundamental differences between log-based and state-based implementations.

First of all it is important to recognize that the update vector based
method of update propagation imposes certain unstated, but unavoidable
constraints on the behaviour of state-based implementations, otherwise
eventual consistency cannot be guaranteed.

A state-based implementation is not free to send updates in a totally
random order. For example, if a supplier sends updates with CSNs t1 and
t3, but doesn't yet send an update with CSN t2, the consumer will
nonetheless revise its update vector to the highest CSN seen, i.e. t3,
and consequently will never receive the update with CSN t2. Whether the
LDUP architecture says it or not, with respect to any particular
replica ID, a state-based implementation is obliged to send during a
replication session *all* the updates between the sent update with the
least CSN and the sent update with the highest CSN. Every update sent
must have a CSN greater than the highest CSN of the previous successful
session and less than the least CSN of the next successful session.

However, the update vector propagation method doesn't implicitly constrain
implementations to send updates in CSN order within a replication session
since there are at least three ways to implement a consumer such that
eventual
consistency is still guaranteed, even if the updates within a replication
session aren't necessarily in CSN order. This applies regardless of whether
the consumer is state-based or log based.

The three ways are:

1) The consumer puts the incoming updates from the supplier into temporary
storage without applying them or revising its update vector. Once the final
update in the session has been received, the consumer sorts the updates
into CSN order and then applies them in that order, revising its update
vector along the way. It doesn't matter if there is a service failure
during either the collect/sort phase or in the application phase.

Note: as far as the ordering is concerned, it is only necessary for the
updates
to be in CSN order with respect to each replica ID. Updates originating
from different replicas can be freely intermixed.

2) The consumer processes the entire set of updates from the session as
a single atomic transaction on its internal database. That is, either all
of the updates are applied and the update vector revised accordingly, or,
in the event of some failure during the course of the replication session,
none of the updates are applied and the update vector is not revised,
i.e. all the changes are rolled back. URP ensures that the end result is
the same as if the consumer applied the changes in CSN order.

3) The consumer applies updates as they are received but defers revising
its update vector until the end of the replication session. In this case
the consumer must make sure that it does NOT propagate to any other server
any update it knows about which has a more recent CSN than the relevant
CSN in its update vector. Such an update belongs to an incomplete set of
changes from a failed replication session.

On the other hand, if the updates in a replication session are always
guaranteed to be in CSN order then the consumer can just apply them as
they are received. A state-based implementation can readily provide updates
in CSN order by sorting them in temporary storage before sending them to
the consumer.

The way I see it, it is not that state-based implementations can't meet
certain requirements but rather it comes down to a question of who has
to do the work (e.g. collation) so that the requirements are met.
If we believe that log-based implementations will be more prevalent than
state-based ones then it makes sense to put the load of collating the
updates onto state-based implementations by insisting that updates are
always sent in CSN order with respect to each replica ID.

Now to the coverage matrix ...

------------------------------------------------------------------------
Requirement SM2: The master replica in a Single Master system SHOULD
send all changes to read-only replicas in the order in which the master
applied them.

Comment: Supported for log-based systems, but not state-based systems,
by definition.
------------------------------------------------------------------------

If state-base suppliers always sort updates before sending them then they
will satisfy SM2 directly.

If consumers sort incoming replication updates before applying them,
or apply them in one atomic transaction, then SM2 is effectively satisfied,
whether the supplier is state-based or not.

However if consumers defer revising the update vector until the end
of the session then a failure part way through potentially leaves them
holding some later updates without the earlier updates. The choice to
implement a consumer this way is independent of whether the consumer
is state-based or log-based so whether requirement SM2 is satisfied
depends on how the consumer processing is implemented, rather than
whether it is state-based or log-based.

Disallowing 3) above or insisting that updates are always sent in CSN order
with respect to each replica ID solves that problem.

------------------------------------------------------------------------
Requirement AM6: The sequence of updates to access control information
(ACI) and the data controlled by that ACI MUST be maintained by replication.

Comment: Not supported for State Based replication
------------------------------------------------------------------------

The arguments that apply to SM2 apply to AM6 as well.

------------------------------------------------------------------------
Requirement G2: LDAP Replication SHOULD NOT preclude support for model 1
(Transactional Consistency) in the future.

Comment: ... the authors believe that there is a good chance that at
least the log-based mechanism described in the architecture will be able
to be extended to support replication of transactional information.
We do have our doubts about the ability of any state-based replication
scheme to do so, though.
------------------------------------------------------------------------

Unless people are contemplating a radical departure from the processing
model described in the URP document, the essential difference between
a state-based implementation and a log-based implementation is whether
incoming replication primitives are saved as-is to be propagated later
to other servers, or reconstructed on demand from the state information
on directory data, i.e. the CSNs on entries and values, and deletion
records.
Note that this same state information is present even in a log-based
implementation.

We can think of a state-based implementation as having an effective log
which is notionally constructed from this state information. The effective
log becomes realized either in the supplier or the consumer depending on
whether we require the supplier to do the collation of the updates.

An effective log differs from a real log in two ways:

1) It contains no superseded primitives. Note that this does not make an
effective log unique since a log-based supplier is permitted to strip out
superseded primitives. A state-based implementation just can't avoid
stripping them out.

2) It cannot preserve the exact order in which the supplier itself
received the update primitives. Note that it is not necessarily the case
that a log-based implementation will preserve the order either, e.g. it
might have a separate log for each replica ID.

The information in the logs, i.e. the set of replication primitives,
is otherwise the same.

Any future extension to LDUP will work for both state-based and log-based
implementations if it does not rely on preservation of superseded primitives
or supplier receipt order. Any mechanism that relies on receipt order is
probably broken for log-based implementations anyway since multiple master
servers will inevitably receive the same changes in different orders
(sorted on CSN per replica ID, but not necessarily globally sorted on CSN).

I have previously sketched out separate solutions for providing
transactional
consistency on top of LDUP, and for identifying transaction inconsistencies
in the absence of support for the former. These solutions apply equally well
to log-based or state-based implementations since neither depends on
supplier receipt order or preservation of superseded primitives.

Regards,
Steven