Subject: RE: 10. "Report propagation sequence"

From: Zachary Amsden <[email-masked]>
Date: Tue, 8 Aug 2000 15:35:47 -0700

>[Albert]

>However you still maintain that it is sufficient
>to require that the originator sequence numbers for each
>replicaId be maintained in order, while I maintain that the
>record numbers of updates should be assigned by the consumer
>as the local sequence numbers as the updates are received,
>and then used as the message numbers of updates that are
>supplied to neighbour consumers, so that the *exact* sequence
>is preserved. 
>
>I also maintain that the originator and local sequence number
>(identical) for any local changes should be assigned from the
>same sequence number generator, so that local changes are
>also interleaved into the *exact* propagation sequence.

>The obvious global properties include maintaining the
>sequence within each originator replicaId and also ensuring
>that parents are created before children (even though
>children may be created at a different replica). Both of
>these can be achieved without the *exact* sequence I am
>proposing, although the second may be simplified by it.

>The less obvious global property that I am aiming for is
>that a DSA crash can never result in other DSAs receiving
>later updates that have been applied to an entry, without
>also receiving any earlier changes that those later changes
>were dependent on. I am using "earlier" and "later" in the
>the context of the version number tree maintained by MDCR,
>and ensuring a global property of the report propagation
>sequence that substitutes for the *illusion* of a uniform
>flow of time reflected in CSNs as used in the current
>architecture.

[Zach]

Ok, using the ordering we discussed does guarantee those
properties.  Almost (more below).  But with the in-order by
replicaID ordering you didn't need a DSA crash for property
two to be violated - it could happen naturally due to
scheduling or network availability.

You can only guarantee either one of these properties if
clients are well behaved.  If a client converses with multiple
masters, and assumes that each master has an identical state,
both properties can be violated.  Not that I really think
clients would be doing that, but sending an update referral
worries me.  Say a disk crash causes a DSA failure, and a
total update is required.  Meanwhile, a client who had been
conversing with this DSA now gets a referral to another DSA,
which may not have the same state.

[Albert]
>A DSA that crashes will normally have local changes that have
not
>been backed up, some of which will have been replicated to
some
>neighbours, and others of which will not have been replicated
to
>any. When it is restored from local backups to an earlier
state,
>it could attempt to resynchronize with its neigbours by a
partial
>replication, but this may fail for any of its own changes
that
>are outside the time window allowed for purging, as a result
of
>a substantial delay before restoration. Thus a full
replication
>to resynchronize becomes necessary, with a consequent
bandwidth
>spike, despite having an available local backup that could
have
>been used to allow a partial replication if the report
propagation
>architecture was not broken.

Yes.  True for any architecture that allows purging of
changes.  I don't see this as a problem.

>Even if a partial replication to resynchronize is possible,
any
>local changes that were not replicated before the crash, but
were
>backed up, may not replicate to other DSAs, preventing
convergence.

I think it MUST be a requirement that convergence can be
reached even if one replica master goes permanently kaput.  Of
course that convergence will not include any changes generated
locally at that replica that were not propogated.  I believe
that this is inline with your scheme, but I'm not 100% sure
what you meant by par 2, pg 11, of MDCR

    If a failed replica is restored from backups any reports
    it holds that have already been propagated will not be
    requested by its neighbours and any that have not been
    propagated will have also prevented the propagation of
    later reports from the same originator that have a higher
    originatorRSN.

Of course you can't reach global convergence if this replica
was a tie point (new definition: tie point is a non-leaf
replica whose linkages are not redundant), since you will have
two isolated clusters of masters.  But with redundant
replication agreements, I think it MUST be possible to reach
convergence despite failure of individual DSAs.  You may
diverge again if the DSAs come back on line and replicate
conflicting changes.

>These complex issues were dealt with in the Coda research
adopted
>by Active Directory which I am proposing should be adopted as
the
>basis for report propagation by this WG.
>
>Their solution does require *exact* ordering and I seriously
doubt
>that anybody will come up with a better one that does not.
>
>Until somebody does, since we are both agreed that exact
ordering
>would not be a problem for either log based or entry based
>implementations, can we also agree that it should be
tentatively
>adopted as the design, pending some other alternative that
can also
>be proved to guarantee eventual convergence under *all*
circumstances?

Yes, I like the ordering idea in the MDCR draft.  However, I'm
a bit confused by the versioning scheme:

"
Updates are not changes and do not increment the version. 
Updates do replace the version with a version that is not
smaller, ...  The replacement version from an update is
usually, but not always larger.  Successive versions of an
entry are not always consecutive but are always monotonically
increasing.  The lexical ordering of version, modifyTimestamp
and originator of an entry is always strictly monotonically
increasing.
"

This is very open to interpretation.  They could actually all
be interpreted as mutually exclusive.

>[Albert]
>BTW, by replicating operations rather than primitives, MDCR
does
>carry enough information to be able to reverse changes.

[Zach]
Disagree.  How does an LDAP modify operation carry enough
information to reverse changes?

However, reverting is not necessary with MDCR, since you are
always guaranteed a known database state.  This is the problem
I was trying to correct in the current propagation scheme.

Zach