RE: LDUP Working Group Agenda - Summary of objections to requirements draft

["Steven Legg" <steven.legg@adacel.com.au>]

Albert,

> -----Original Message-----
> From: owner-ietf-ldup@mail.imc.org
> [mailto:owner-ietf-ldup@mail.imc.org]On Behalf Of Albert Langer
> Sent: Saturday, 29 July 2000 7:24
> To: steven.legg@adacel.com.au
> Cc: ietf-ldup@imc.org; ietf-ldapext@netscape.com
> Subject: RE: LDUP Working Group Agenda - Summary of objections to
> requirements draft

[snip]

> Work is proceeding, outside LDUP, but within LDAPEXT, on how to group
> updates and/or do transactions in a standardized manner.
> 
> Some applications already use existing directory services to add their
> own non-standardized transactional semantics, relying only on the
> LDAP/X.500 data model which *does* support atomic operations on a
> single entry, but does not provide any means for locking a set of
> entries or performing an operation atomically on that set.
> 
> Methods include writing transaction identifiers to special
> attributes in each of the set of entries, then checking that nobody
> else did so, to any of them, after updating all the entries. 
> This requires
> that only DUAs cooperating in a transactional application have write
> access to all relevant attributes of the entries.
> 
> This sort of thing can work in a single master environment, 
> but becomes
> more complex in a multi-master environment. It is still possible
> provided attributes as a whole are replicated atomically, even
> though updates to different attributes of a single entry may be
> merged - as shown by the fact that Active Directory applications can
> do this, clumsily, using "consistency guids" and "child counts".
> 
> However it becomes much more difficult, and perhaps impossible, with
> URP, because even concurrent changes to individual attribute values of
> a single attribute may be merged.

If the required behaviour is for only one or the other of two
concurrent updates to an attribute to be retained, instead of the
values being merged, then this can be achieved by using the replace
attribute alternative in an LDAP modify or by defining the attribute
in question to be single-valued.

[snip]

> [Issue C - Convergence]
> > SUMMARY OF OBJECTIONS TO REQUIREMENTS DRAFT
> >
> > The three key points are:
> >
> > 1) There is no requirement for convergence or "eventual 
> consistency".
> >
> > This looks like just poor expression, but in fact the LDUP
> > architecture and
> > Update Reconciliation Procedures do specify proposed standards that
> > guarantee long term divergence by relying on timestamps
> 
> [Steve]
> The timestamp in the CSN is just a version number that happens
> to increment without visible update activity. A version number
> scheme that leaves gaps in the runs of version numbers isn't
> broken as long as the version numbers from a server are
> monotonically increasing. The LDUP CSN is monotonically 
> increasing too.
> The only difference with the LDUP CSN is that the gaps just happen
> to have a correlation to elapsed time.
> 
> > and
> > allowing DSAs to
> > transmit changes out of order and drop changes when clocks
> > are out of sync.
> > This is easily fixed, once a requirement to fix it is agreed on.
> >
> > Details on how to fix it based on the Coda replication 
> protocols also
> > adopted by Active Directory, and a semi-formal proof that the
> > fix would be
> > robust in the face of DSAs crashing and being restored from
> > backups, network
> > partitioning etc etc, is included in my draft below.
> 
> Your proof neglects the effects of the purging mechanism. Restoring
> a crashed DSA from a backup works if no change information is ever
> removed. However if a backup restores a DSA to a state prior to the
> purge point of any of the other replicas there exists the possibility
> that the other DSAs have forgotten changes that the restored DSA
> needs to bring it up to date and consistent with the others.
> 
> I have a procedure for solving the replica consistency problems of
> restored replicas and rejoined partitions but it is written in terms
> of a log-based implementation using a different purging mechanism.
> I'm still in the process of recasting it in state-based terms with
> an update vector.
> 
> [snip]
> 
> [Albert]
> My reference to "relying on timestamps and allowing DSAs to
> transmit changes out of order and drop changes when clocks are out
> of sync" should be read as a single sentence. Clocks are not
> necessarily even monotonically increasing because they sometimes
> jump around when administrators make mistakes, eg with time zone
> and daylight savings settings.

You should read section 5.1 of draft-ietf-ldup-urp-03.txt again.
The CSNs aren't always generated straight from the system clock.
URP imposes constraints on the generation of CSNs so that they are
monotonically increasing from replication session to replication session
despite a system clock that isn't.

The references in the architecture draft to rejecting update operations
need a bit of work. There is some confusion and ambiguity there about
whether client updates or replication updates or both are being rejected.
Eventual consistency can't be guaranteed if any replication updates are
just arbitrarily dropped. We can reject a whole replication session if
there are seriously different CSNs appearing provided no Update Vectors are
revised, and provided we have an administrative procedure for repairing
the situation. In effect the rogue server is shunned and the purge point
stops advancing until corrective action is taken. The action to be
taken would need to covered in the draft on replica administration.  

Servers are only permitted to send changes from a particular server
out of order within the same replication session. All changes from that
server in earlier sessions must have had lower CSNs and all changes
reported in later sessions must have higher CSNs. Some LDUPers didn't
want to require in order sending within a session and I'm okay with that
since we can allow for it without breaking consistency. Any of the
following replication consumer strategies will ensure eventual consistency.

1) Receive the primitives into temporary storage, sort them, then start
applying them in order, progressively updating the Update Vector, and
committing to the database after each group of primitives with the same
CSN (i.e. each operation). Send the final Update Vector back to the
supplier at the end. If there is a failure part way through the consumer
will start from where it got up to, on the next replication session.

2) Run the replication session as a single local transaction. Apply
the primitives as they arrive, but don't commit the transaction until
the end. The new Update Vector is committed as part of the transaction
before being sent back to the supplier. If there is a failure part way
through, the transaction is rolled back (or not recovered on restart).
The consumer will start from the same point as the previous (failed)
session, on the next replication session.

3) Apply the primitives as they arrive, committing after each operation
group, but don't change the Update Vector until the end. If there is
a failure part way through, the consumer's Update Vector won't have
changed, so the supplier will send the same set of primitives on the next
replication session. URP handles primitives that are repeated or out of
sequence so the correct final outcome will be reached. The consumer must
not send any primitives from a failed session to any other server but that
is easy to prevent. These primitives will have CSNs greater than the
current local Update Vector.

4) Receive the primitives into persistent temporary storage and return a
revised Update Vector straight away. The consumer then applies the
primitives to the DIB at its leisure. In any subsequent replication
session where it acts as the supplier the server would have to be able
to send primitives still residing only in the temporary store.

[snip]
 
> My proposal, based on a similar vector to the current LDUP drafts,
> does take account of the purging mechanism - it
> prevents a purge at *any* replica until after *every* replica has
> received the change. It does so, precisely for the reason you 
> mentioned.

But if you restore any server from an old backup then the correctness
of the purging mechanism is compromised because you have introduced
a server that appears as though it hasn't received changes that the
other servers were previously told it had.

Suppose some entry E is at version 1 when I take backups of a set
of replicas. As time passes, entry E is progressively updated and
successive versions eventually become durable. Let's suppose that
the durable version of E is version 53 when one of the replicas dies,
forcing a restore. In its restored database, entry E has the version 1.
The restored server will now receive changes referencing version 54+.
I could see nothing in MDCR that would allow the restored server to
bridge the gap between version 1 and version 53 of entry E. The sequence
of changes up to version 53 have been lost to purging.

> 
> The solution I proposed is based on existing implementations
> (Coda and AD) that have been thoroughly researched and tested
> and are known to work and to have a number of advantages. For
> marketing purposes, AD also describes that as "state based"
> rather than "log based", by coyly calling the log an "index". I prefer
> to stick to the technical necessities and leave marketing doubletalk
> to others.
> 
> That proposal separates report propagation from update 
> processing and so
> would be equally applicable to URP or MDCR. It also enables a natural
> transition from single master to multi-master implementations 
> instead of
> attempting to force implementation of multi-master as the current LDUP
> proposals do.
> 
> The Coda mechanism relies on the fact that change reports are 
> transmitted
> in order and relies on version numbers rather than timestamps.
> 
> If it used timestamps it would not work because clocks cannot be
> guaranteed monotonic.
> 
> If you have some other mechanism that can also be proved to 
> work, but is
> somehow able to do it using timestamps and changes 
> transmitted in random
> order,
> that's quite an achievement as the Coda research was quite a 
> major project.
> I look forward to reading the draft but repeat my 
> recommendation that you
> study the Coda research.
> 
> As already stated, I do not believe this is a fundamental problem
> inherent in URP, since URP need not rely on timestamps.
> 
> There may well be other and better ways to do it, as long as we are
> agreed that it MUST be done. My description was certainly incomplete,
> as a protocol for determining which replicas are currently active
> and which are excluded is necessary for any method. I wrote it
> because in the current proposals the mechanism was not merely
> incomplete but absent, and there was explicit language about
> dropping updates. When I checked back to the requirements I found
> that what I thought was common ground in assuming a requirement for
> eventual convergence, was so vague that simply dropping updates
> and leaving replicas with different states for the same entries
> could arguably be consistent with the stated requirements.

[snip]

> The current wording says the scope includes two models, "Eventual
> Consistency" and "Limited Effort Eventual Consistency", defining the
> latter as "where replicas may purge updates therefore dropping
> propagation changes when some replica time boundary is exceeded, thus
> leaving some changes replicated to a portion of the replica topology".
> 
> Instead of ruling out the second, it explicitly says "LADP replication
> should be flexible enough to cover the above range of capabilities".
> The actual current drafts do "purge updates therefore 
> dropping propagation
> changes when some replica time boundary is exceeded, thus leaving some
> changes replicated to a portion of the replica topology."
> 
> A requirement "to be flexible enough to cover this" is "simply
> absurd". That is really an understatement.
> 
> Are we agreed that the final requirements draft should unambiguously
> require eventual convergence under ALL circumstances?

I agree. It's been my working assumption from the beginning.

[snip]

> [Issue E - modifiersName]

[snip]
 
> You've over estimated the utility of the modifiersName attribute.
> It only tells you who last changed something, not what they changed.
> 
> [snip]
> 
> [Albert]
> On a single master system, "modifiersName" tells you that what they
> changed is what was in the entry immediately before the change and
> what they could have read before making that change. If it wasn't
> broken before, then it broke because of that change by that DUA.

Not necessarily. There could have been any number of updates prior
to the latest one identifying the modifiersName. Any one of these
could be responsible for "breaking" the entry.

[snip]

Regards,
Steven