RE: Is State-based LDUP needed?

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.

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