RE: Is State-based LDUP needed?

Ed,

Ed Reed wrote:
> 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).

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

> 
> 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 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 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).

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.

> 
> 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).

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

> 
> In your set of three approaches below, I agree that 1 and 2 
> work, but not
> 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
> recover the masked changes (if it could, it would be a log 
> based system).

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

> 
> 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.

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

> 
> 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.

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

> 
> Ed
>       
> 
> =================
> Ed Reed
> Reed-Matthews, Inc.
> +1 585 624 2402
> http://www.Reed-Matthews.COM
> Note:  Area code is 585
> 
> >>> "Steven Legg" <[email protected]> 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
> 
>