Subject: RE: Is State-based LDUP needed?

From: "Steven Legg" <[email-masked]>
Date: Fri, 18 Jan 2002 16:30:23 +1100

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

---

From: "Timothy Hahn" <[email-masked]>
Date: Mon, 21 Jan 2002 06:36:13 -0500

Steven,

We're in agreement then.

Regards,
Tim Hahn

Internet: [email-masked]
Internal: Timothy Hahn/Endicott/IBM@IBMUS or IBMUSM00(HAHNT)
phone: 607.752.6388     tie-line: 8/852.6388
fax: 607.752.3681

"Steven Legg" <[email-masked]>
01/20/2002 06:25 PM
Please respond to steven.legg

        To:     Timothy Hahn/Endicott/IBM@IBMUS
        cc:     <[email-masked]>
        Subject:        RE: Is State-based LDUP needed?

Hi Tim,

Timothy Hahn wrote:
> Steven,
>
> I followed you all the way until the end of your note.
>
> I am of the opinion that updates sent during a replication session be 
sent
> in CSN order.  While this may cause "up-front" work for "state-based"
> implementations, I believe that it allows consumer servers to make the
most
> progress possible - even if the communications link is lost before the
> replication session can complete.  URP will take care of the cases where
> the consumer sees a CSN in an update that is "older" when sent by a
> different path through the network.
>
> I couldn't tell in your last two paragraphs what you were asserting be
> done with respect to update send (and thus expected receive) order.

I wasn't so much making a specific proposal as pointing out the technical
issues. Given that there will be few or no state-based implementations
then I am of the opinion that we should make life easier all round by
requiring that, with respect to each replica ID, updates must be sent
in CSN order.

We don't want to require that updates be sent in global CSN order since
that would require even the log-based implementations to sort updates
before sending them.

Regards,
Steven

---

From: "Ed Reed" <[email-masked]>
Date: Sat, 26 Jan 2002 11:45:13 -0700

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" <[email-masked]> 01/18/02 12:30AM >>>

Ed,

there

they'll
focused
it,
implementers

taken

The three ways are:

Regards,
Steven

---

From: "Steven Legg" <[email-masked]>
Date: Tue, 29 Jan 2002 14:50:46 +1100

Ed,

> systems (which I think are all anyone is planning to build, anyway).

It depends on what we mean by "works". Detailed comments below.

> on the log based system, instead.

I think a distinction should be drawn as little as possible in the LDUP
documents. It is mostly an internal implementation issue that rarely needs
to be mentioned (URP is the only place where it is a practical necessity).
The external behaviour that we impose on LDUP implementations does have
fundamental consequences on the style of implementation and we need to
consider and reach consensus on what that behaviour is to be, but most
of the current state-based versus log-based text can be dropped regardless
of the outcome of these discussions.

In the end we just say what LDUP implementations must do, not what
log-based or state-based implementations must do, and if, after due
consideration of the issues, that happens to be hard or impossible
for a state-based approach to achieve then so be it.

More below.

I recognize the problem, but characterize it differently. Inconsistencies
of this kind are a result of superseded primitives being removed from
the set of propagated changes. A pure state-based implementation cannot
avoid removing the superseded primitives, however the current LDUP
documents allow the log-based implementations to remove superseded
primitives as well. Thus I see it as a question of whether we want to
require that superseded primitives will always be sent.

Removing superseded primitives has the advantage of reducing both the
amount of data sent in replication sessions and the workload on the
consumer. However I don't regard this advantage as compelling since I
expect to be using on-change replication agreements most of the time,
which leaves few opportunities for primitives to become superseded
before they are fully propagated.

The disadvantage is that entry internal inconsistencies of the type you
describe can arise, though I don't lose sleep over them since they are
transient and occur only in abnormal situations, e.g. communications
failure. The inconsistencies that arise because we want to allow
independent updates at multiple master servers are more significant,
more prevalent, and unavoidable.

> just those that have not been "masked" by subsequent updates).

It works in the sense that eventual consistency is achieved, but carries
the risk of temporary entry inconsistencies.

> 3.

Note that implementation strategy (1) for consumers has exactly the same
effects and consequences as requiring updates to be sent in CSN order.
A supplier that is interrupted part way through sending an ordered series
of changes, minus the superseded primitives, produces the same effect as
a consumer using strategy (1) that fails part way through applying the
same changes that it has sorted for itself first. Note, I'm assuming that
the sorted list is lost when the consumer fails.

Therefore if requiring updates to the sent in CSN order does not work
(in the sense of not causing temporary entry internal inconsistencies)
then strategy (1) does not work either. This leaves strategy (2) as
the only one that "works", but I would rather live with the temporary
inconsistencies, or always propagate superseded primitives, than require
the whole replication session to be processed as a single transaction,
as per strategy (2).

> The statebased system can order updates in CSN order, but it can't

Agreed. If we insist that superseded primitives shall always be
propagated then we essentially prohibit a state-based implementation
of LDUP.

> replication sessions with statebased systems, but I don't 

I don't know how current state-based implementations do it.
I'm curious to know.

> doing log based systems, then there's no sweat.

I think it boils down to two questions.

Q1: Do we insist that replication primitives are always sent in
CSN order per replica ID ?

Q2: Do we insist that superseded primitives are propagated anyway ?

A "yes" answer to Q1 puts the burden of collation only on state-based
supplier implementations while "no" puts the burden on every consumer
implementation, whether state-based or log-based. I vote "yes" to Q1.

A "yes" answer to Q2 effectively prohibits state-based implementations
while "no" means that temporary entry internal inconsistencies can
occur, if consumers don't process the whole replication session as a
single transaction. I'm not strongly for or against, but if I have to
vote it is "yes".

Regards,
Steven

---

From: "Timothy Hahn" <[email-masked]>
Date: Wed, 30 Jan 2002 18:33:35 -0500

Hi all,

I, as well, have no objections to answers of "yes" to both questions.

Regards,
Tim Hahn

"Steven Legg" <[email-masked]>
Sent by: [email-masked]
01/30/2002 06:05 PM
Please respond to steven.legg

        To:     "'Ed Reed'" <[email-masked]>
        cc:     <[email-masked]>
        Subject:        RE: Is State-based LDUP needed?

Ed,

Ed Reed wrote:
> I'm okay with answering it "yes" to both your questions, and 
> in so doing
> relegating all references state-based replication to the dust bin.
> 
> I would further assert that unless at least two directory 
> service implementors
> object, that the current "concensus" of "yes" to both will 
> prevail.  I don't think
> the plans of only one party to implement the option should 
> result it retaining
> it in the face of the (a) added complexity, and (b) transient 
> inconsistencies
> that would result.

Okay with me. I will wait a week to see if there is any dissent, and
if not, I'll rip out all the references to state-based implementations
from URP.

Cheers,
Steven

> >>> "Steven Legg" <[email-masked]> 01/29/02 05:28PM >>>
> 
> 
> Tim,
> 
> Timothy Hahn wrote:
> > Hi all,
> >
> > Steven Legg wrote:
> >>
> > My opinion on these two questions are:
> >
> > Q1: I vote "yes" to this one.
> >
> > Q2: I could go either way on this.  It would seem we would be "more
> correct,
> > more of the time" if we insisted that superseded primitives are
> propagated -
> > at the expense of a little more information being sent 
> during replication
> > sessions.  However, it would appear that LDUP will work 
> either way (after
> > all, "eventual consistency" is what is required).  Thus, I 
> would allow
> this
> > as an implementation choice - i.e. superseded primitives 
> MAY (or MAY NOT)
> be
> > propagated.  I also think that it is in the best interests 
> of all involved
> if
> > the update reconciliation procedures draft (or the update 
> replication
> > protocol draft) points out the issues involved if 
> superseded primitives
> are
> > NOT sent.  (It seems a shame that this analysis would only 
> be documented
> in
> > the mailing list archives).
> 
> I can expand the section in URP on superseded primitives to 
> point out the
> issues if the consensus on Q2 is "no". If the consensus is 
> "yes" then I
> will instead be taking out all the provisions for state-based
> implementations.
> 
> Regards,
> Steven
> 
> 
>