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

>
> Regards,
> Tim Hahn
>
> Internet: [email protected]
> 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 protected]>
> Sent by: [email protected]
> 01/18/2002 12:30 AM
> Please respond to steven.legg
>
>         To:        "'Ed Reed'" <[email protected]>
>         cc:        <[email protected]>
>         Subject:        RE: Is State-based LDUP needed?
>
>
>
>
>
>
> 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