Subject: RE: various comments (was Re: What's going on? - Status of Requirements...)

From: "Albert Langer" <[email-masked]>
Date: Tue, 18 Jul 2000 06:45:38 +1000

Steve,

Thanks for the detailed and helpful response a while back.

http://www.imc.org/ietf-ldup/mail-archive/msg00576.html

Looks to me like we've moved into concrete discussion of various issues
between URP and MDCR and their relation to requirements (thanks also to Ryan
for getting this going). Sorry about the long delay responding.

I propose we should discuss each of those issues under separate headings
rather than continuing within a thread that started from a request for
status reports.

I'm planning to chop up your message, re-arranging it within the categories
I perceive and want to respond to, each with a link here from which people
can get the original context. I'm starting now to ensure anyone interested
has time to think about the issues before the Pittsburgh meeting, which I
will be unable to attend. Finishing may still be delayed for a week or so
due to other commitments.

Meanwhile, here's a summary of the issues as I see them, and their relation
to the original request for status reports.

1. "Atomicity and related concepts". Disagreement about definition,
importance and relation to other concepts and requirements. Should be
clarified and resolved by definitions, explanations and requirements in
requirements document before final call.

2. "ModifiersName and other Operational Attributes". Disagreement about
definition, semantics, and implications of URP and MDCR proposals for
handling them. Definition and semantics should be clarified in requirements
document before final call. URP and MDCR handling should be clarified in
further discussion of URP and MDCR. Unclear whether there is a disagreement
about a requirement to handle ModifiersName "correctly", because of lack of
agreed definition of what would be "correct".

3. "Change Reports - ProtocolOps or Primitives". Reference by Steve to
non-LDAP and non-X500 replicating servers may involve clarification of
requirements. Other issues can be clarified in discussion of URP and MDCR
approaches.

4. "Eventual Convergence - Version numbers or timestamps". Agreement that
URP could operate with priority for either version numbers or timestamps. I
maintain that version numbers should have priority, for reasons fully
explained in the Coda file system research. If URP remains the only protocol
under consideration by the WG it can and should be changed to do so. Design
issue, not requirements (though relevant to any requirement for eventual
convergence - see below).

Implicit agreement that in the absence of further changes, all replicas
should converge to the same state and any protocol that does not guarantee
this is unacceptable. Disagreement as to whether each of MDCR and URP meet
that requirement. Steve maintains that MDCR cannot meet that requirement. I
maintain that MDCR can and that URP as currently drafted does not, but that
URP is capable of doing so, provided that version numbers have priority over
timestamps. Although there seems to be no disagreement about requirements on
this between Steve and myself, I cannot resist  pointing out that the
current requirements draft actually "requires" a "flexible" ability to
accommodate both models that guarantee convergence and models that will
diverge.

5. "Oscillation". Implicit agreement that no protocol should oscillate. No
need to state in requirements as both obvious and covered by 4 above. Steve
says he has an example showing that MDCR oscillates. I say that neither MDCR
nor URP oscillates. Unfortunately the margin of this email is too small for
the proof ;-) Fortunately it is short enough to present in another email
rather than leaving the world waiting breathlessly for hundreds of years...
or subjecting it to eyeglazing discussion of examples.

6. "Implementation and Performance Issues". Disagreement as to whether there
is any significant difference in implementation difficulty or performance.

7. "Revocation notices". Implicit agreement that MDCR could add them and
that URP makes no provision for them because it does not revoke anything.
Disagreement as to whether they are useful.

8. "Strong consistency and transactions". Steve has sketched an idea that
Alison and Steve have for adding these to URP. While relevant to the WG, I
don't think they are intended to meet any objections to adoption of URP for
multi-master replication as they do not satisfy the definition of, nor the
requirements for, multi-master replication. I believe this does shed further
light on the requirements draft problem, as by failing to give any
explanation whatever of user needs for multi-master replication, that draft
invites confusion.

Original message below. I am adding comments re item 8 at the end as further
discussion of it has already occurred in this thread. Comments on other 7
will follow under the 7 headings listed.

*******************************
[snip]

> [RM]
> On the subject of the requirements / URP draft:
>
> 1. I still believe the requirements draft should be more
> explicit about atomicity of operations being maintained
> across replication.  In my various re-readings of this
> draft, I have at times found justification for both
> sides (maintain and do not maintain) and I still think
> that maintaining atomicity is necessary.
>
> 2. The URP draft should be explicit in how it maintains
> atomicity of operations across replication.  I'm pretty
> sure from my last perusal it doesn't now.
>
> [AL]
> Understood.
> URP certainly does not maintain atomicity and is explicit
> about that. This
> problem is not in the URP draft, but in the requirements
> draft. If there was
> a requirement to maintain atomicity there would be a
> completely different
> URP (not necessarily MDCR).

Atomicity is not the right concept to be arguing about in a multimaster
replication environment. Consider this example.

At server S1 at time t1 a user modify request on an entry adds attribute
A1 and replaces the existing values of attribute A2. At server S2 at
time t2 (t2 > t1) a user modify request replaces attribute A2. Some time
later the modify from server S1 arrives at S2. If S2 performs this
operation atomically it will replace the newer (time t2) value(s) of
attribute A2 with the older values (time t1). This is clearly the wrong
thing to do. If S2 adds the new attribute A1 but ignores the replacement
of A2 (as URP would do) then it produces the same outcome as the
serial execution of the two modify requests, though the action doesn't
fit the usual definition of "atomic".

If we are going to discuss atomicity in replication then we need a more
meaningful definition. URP makes all the replicas produce an outcome
that is equivalent to the serial atomic execution of all the updates.
That is as atomic as it needs to be.

The real question revolves around the preconditions of a user update
request. If we look at the equivalent serial processing of a collection
of updates performed at two or more multimaster replicas then some of those
updates will be "executed" against a different database state than actually
existed at the time they were really performed by one of the replicas.
The URP philosophy is that most of the time for most applications it doesn't
really matter. The MDCR philosophy is that it is better to completely
disregard the user's update, after the fact, just in case the state of the
entry did matter.

[snip]

> [RM]
> 3. Once URP maintains change atomicity, the "modifiersName"
> issue in my mind goes away.  There may be others that
> still remain...
>
> [AL]
> Agreed. "modifiersName" is impossible without atomicity, and
> easily achieved
> with it (as are many other things).

You seem to be assuming that the DSA maintained operational attributes
are being independently maintained by each replica. The intent in URP is
that the replica executing the user update request will modify the
operational attributes, like modifiersName and modifyTimestamp, as
required, and that these changes will also be reflected in the primitives
sent to the other replicas. Those other replicas will keep the values
of these operational attributes with the highest CSNs, which will
correspond to the latest change to the user attributes. Exactly the
same outcome as a serial execution of the updates in CSN order.

[snip]

> As regards efficient propagation of the tree via the report
> propagation
> protocol I believe the encoding on the wire is as efficient
> and as simple as
> possible by just conveying the actual LDAP protocolOps for
> the changes. The
> only redundancy is for the relatively small proportion of changes that
> affect the Directory Information Tree (DIT), ie add, del and modifyDN,
> rather than just the Directory Information Base (DIT), ie modify (for
> changes to non-distinguished attributes and values).

The replicating servers aren't necessarily LDAP or X.500 DSAs, so the update
protocol operations aren't necessarily just LDAP, DAP or DSP operations.
Also, these protocols are still subject to change so additional operations
may be defined in the future, or existing ones extended. LDAP also has
a means for vendors to define proprietary operations. We can't expect LDUP
implementors to cover all the possibilities.

The original request also doesn't carry the changes to operational
attributes or other vendor specific DSA invoked changes such as might
occur to maintain referential integrity of DNs.

Breaking all update requests into replication primitives gets around these
problems.

[snip]

> Incidentally the MDCR draft also proposes adoption of the Coda report
> propagation protocols  adopted by AD. I believe that would be
> a considerable
> improvement without requiring any substantial change to either the
> requirements or architecture and especially beneficial to the
> existing URP
> design as there is a lot of avoidable complication there
> simply because
> reports are propagated out of sequence by each replica.

Propagating the changes strictly in CSN order wouldn't make much difference.
The "complexity" arises from the requirement to process local changes out
of order with updates reported by other replicas. Whether those remote
changes are reported in order becomes irrelevant.

>
> That is completely independent of the issue of atomicity.
>
> [RM]
> 2. The whole "weeding and summarizing" discussion left me
> confused and therefore worried.  There seems to be an
> unstated assumption that all replicas are "well-connected".
> My concern is that if one or more replicas are
> "sporadically-connected" then the size of the trees could
> become an issue.  Again, I may be missing something in the
> draft, but if so, I'd claim it is buried.  Because the
> whole discussion left me confused, I think some clarification
> in the form of an example would help.
>
> Ryan
>
> [AL] If the WG accepts the draft as being on its agenda for
> discussion I
> think a lot more work will be needed on it, including
> detailed examples (and
> diagrams) for the weeding and summarizing process as you suggest.

I too have some concerns about the "weeding and summarizing" stuff.
In particular it is not possible to guarantee that all replicas will
converge toward the same state. A version of an entry cannot be made
"Durable" until after some unspecified delay to see if any higher version
shows up. For an entry version to become the definitive (durable) version
depends not only on earlier events but also on events that are yet to occur!
If the waiting time is chosen badly the replicas will quickly diverge.
No matter what delay is chosen there is always a chance that a higher
version will pop up immediately afterward.

Also, I can also construct examples where two replicas endlessly flip
back and forth between two competing strands with no entry versions ever
becoming durable.

> A simpler approach to conflict resolution would just resolve
> each conflict
> immediately, at each DUA that encounters a conflicting change, by
> suppressing the change with the lower version number etc and
> propagating
> only 1 survivor (which may itself be suppressed at another
> DUA with the
> survivor propagated from that conflict in turn reaching the
> previous DUA and
> suppressing the previous survivor there).

I don't think this is enough to solve the problems mentioned above.

> This is more or
> less what AD does
> (for attributes).
> URP makes the fatal mistake of splitting
> the operations
> into primitives so as to effectively merge conflicts instead
> of resolve
> them, and adds the serious mistake of giving higher priority
> to timestamps
> than to version numbers.

The LDUP CSNs can be used either way. URP doesn't care, it just sees
a monotonically increasing value.

> This means the "survivor" at each
> DUA separately is
> just the latest, with no actual conflict resolution at all.
>
> The tree is especially important for "sporadically-connected"
> replicas since
> they are the most likely to generate conflicts. In most cases
> the tree would
> be trivial or very small, but if it is not recognized as a tree, that
> "simplification" makes everything else become incredibly complicated.
>
> I don't see a large tree as an implementation problem in itself - the
> overhead is only about 12 bytes of RAM per conflicting change.

You would also need to store enough information to reconstruct the
previous versions of an entry on each strand. To change the current
entry version from one strand to another requires unwinding index changes,
etc, back to the common branching point and then applying the saved
change requests on the new strand. URP never has to go backwards.

[snip]

> The conflicts form a tree in reality, whether it is
> recognized or not. If
> that tree becomes large then URP would produce a high rate of
> "Extraordinary
> States" and "Transient Extraordinary States" while MDCR would
> produce a high
> rate of revocation notices because it has at least recognized
> the reality.
> Neither is appropriate for directory applications. (In my view even an
> extremely low rate of "Extraordinary States" without any
> means except manual
> administration to recover from them is completely unacceptable).

I don't expect many LDAP client application developers will want to
deal with the complexities of out-of-band revocation notices, or deal
with restoring the application context of the original change so it
can be repeated. The enterprising ones will probably just send a series
of spurious changes to an entry after each real change just to "up" the
version number and so increase the chance of the real change sticking.

In effect, what we have done with URP is hardwire a reasonable conflict
resolution mechanism (best effort merge) that is (we think) good enough
for most uses of the directory. But that doesn't leave the remaining uses
out in the cold. Alison and I have previously mentioned in passing that
we have an idea for providing strong consistency and transactions with URP.
This is a good time to sketch out what we mean.

This is the sequence of events for a user update request requiring or
requesting strong consistency:

The receiving replica (let's call it the primary) opens a session with
each of the other replicas and sends a request for all update primitives
up to and including the latest change to the target entry. This is just a
variation on a regular LDUP session. However the other replicas will also
lock the target entry to prevent any local changes to it. Some sort of
deadlock detection will be necessary.

The primary replica applies all the primitives it has received and then
attempts the user request. If it fails with an error the sessions with
the other replicas are closed and they drop the locks on the target entry.
If the request succeeds the primary server sends
the primitives up to and including the ones generated from the current
user request, then closes the sessions causing the locks to be
released. If the primary doesn't send the latest primitives the other
replicas will just import them the next time they action a strong
consistency update on the same entry. Two-phase commit isn't required.

Handling transactions is straightforward. The initial request from the
primary replica specifies a range of affected entries (maybe with
something like a search filter) instead of just the one target entry.
The primary is also allowed to send multiple requests within the same
session since it won't generally know all the entries affected by
a transaction at the beginning.

The above scheme requires all updatable replicas to be available to perform
a strong consistency update but there is a more general scheme that
allows some of the replicas to be unavailable. If there are N replicas
then it is only necessary to contact M (M > N/2) of them to make an update
provided N-M+1 of them are contacted before evaluating any strong
consistency query. The original description was the special case of M = N.

Regards,
Steven

********************************
[AL] (Commenting only on the last item). If DSAs have to contact any other
replica, whether all, a majority or just a few, before applying a change,
they are not providing the benefits of multi-master replication. This is
clearly excluded by the accurate definition of multi-master replication in
the WG charter. The requirements draft should clearly explain that the
reasons for needing multi-master replication standards is to meet user needs
for changes to be available locally to other users of a local DSA, whether
or not that DSA is able to contact other DSAs, and without suffering the
performance and scalability problems of attempting to contact any of them
before applying the change and making it locally available.

Instead, the only scenario in the requirements draft which does involve that
user need, is not identified as being relevant to multi-master replication,
while every single scenario identified as explaining the need for
multi-master replication actually involves no need for multi-master
replication at all - either because it is to do with meta directories rather
than replication, or because it could be achieved just as well by single
master replication.

Once you give up the scalability and performance of local availability of
changes made possible by multi-master replication, I see no advantage in
this proposal over the use of failover single master replication as proposed
earlier by Alan Lloyd. The latter is already covered by standards for single
master replication and by the fact that a DSA need not hold any naming
context or shadow any naming context, but can just be equivalent to a DUA
that speaks DAP. Both ideas are simply irrelevant to the requirements we
ought to be trying to meet. This would be obvious if we actually had a
requirements draft that actually talked about those needs.

Incidentally Coda does provide very closely related ideas for cacheing file
server clients to contact a subset of multi-master replicating file servers
in an enhancement of the Andrew File System for "sometimes disconnected"
use. As mentioned in MDCR, it is worth studying thoroughly for ideas
relevant to LDAP replication and I have attempted to adapt some ideas from
it in the MDCR report propagation protocol, also used by Active Directory.
Needless to say, Coda does not attempt to merge changes made to different
aspects of a file by different clients eg by applying a name change made at
one client to a contents change made concurrently at another. Unfortunately
when the servers are partitioned, Coda has no alternative but to resort to
manual fixups for conflicts, in much the same way that any LDUP protocol
will have to for conflicting create, modifyDN and delete operations.
Nevertheless there is really extensive research there on precisely HOW to
deal with contacting less than all the servers at once. It does center
around revocation notices and priority for version numbers rather than
timestamps.

---

From: "Albert Langer" <[email-masked]>
Date: Tue, 18 Jul 2000 21:17:42 +1000

Steve,

I didn't really understand what you are getting at on this, so it might be
best to restate what point you were actually making afresh.

Nevertheless, here's my response to item 4, which I summarized as:

http://www.imc.org/ietf-ldup/mail-archive/msg00614.html

***
Comments follow the original below.
***

[AL responding to Ryan]
> changes to non-distinguished attributes and values).

[Steven]

[snip]

[Albert]
I do not understand what problems you are referring to or how breaking all
update requests into primitives gets around them.

My understanding was and is that URP breaking all update requests into
primitives is intended to get around the problem that modify operations to
the same entry made concurrently at different replicas cannot all succeed as
a whole (ie "atomically"). URP breaks up the whole operation into its
constituent primitive elements so that they can be merged or "reconciled"
independently regardless of any conflict between them. When more than one
operation includes a primitive element that changes the same single valued
attribute, only the primitive element that happens to have the highest
timestamp will succeed. But if they change different attributes, or add or
delete different values to the same attribute, they can all succeed.

Please confirm whether that understanding is correct, or explain why it is
not.

Conversely, MDCR aims to ensure that each operation can only succeed or fail
as a whole, so it has no need to break it up into "primitives".

I was replying to Ryan raising an issue which I took to be about the
efficiency of protocol encoding on the wire, but may not have been. My point
was that both MDCR and URP carry essentially the same information, although
they treat that information differently ("atomically" vs splitting the
atom).

Now you *seem* to be saying that the use of primitives enables URP to convey
additional protocol information for proprietary non-LDAP and non-X500
directories, which could not be conveyed by MDCR. I do not see any provision
for this in URP and I do not think any such provision is desirable. It could
easily be added to both if it was desirable.

If there is any thought of doing so, I think a clear statement should be
added to the requirements document explicitly ruling this out, as such
additions would guarantee incompatability between different implementations.

On the other hand you might more plausibly have meant to say that the
original protocolOp as received by the originating DSA may include such
non-standardized information, or not be based on a DUA protocolOp at all,
and therefore should or could not just be copied verbatim by MDCR.

If so, I agree. My intention in the MDCR draft was that the encoding should
correspond to a canonicalized "protocolOp" that could have been received
from an LDAP DUA as specified in the LDAP RFCs - explicitly excluding any
"controls". I did not mean to imply that it would always be a verbatim copy
of such a protocolOp (although many implementations will be simplified by
being able to do that). The "protocolOp" ASN specified in the RFCs includes
all the information required by URP except the entryID, which MDCR also
carries separately. Thus MDCR does not omit any information used by URP.

The (marginally) greater efficiency of MDCR "on the wire" results simply
from not repeating the entryID etc for every attribute value that is changed
by a single modify operation. MDCR just transmits this once for each modify
operation and also saves other overhead from multiple protocol elements for
a single operation (both "on the wire" and when processing the protocol).

I also believe it is important not to impede future extensions to the
replication protocol to cover future standardization of additional features
such as "signed operations". URP impedes this by nuking operations so that
the very concept of an operation has been lost once it has been subjected to
atomic fission and its constituent elements sent wandering through the
replication network. MDCR preserves the concept of a "whole" operation (ie
an "atomic" operation), for other reasons, but has the additional benefit of
not impeding future developments such as signed operations.

Finally, in relation to the original point re efficiency on the wire, I
should mention that I said MDCR is only "marginally" more efficient than URP
because the really significant overhead is per replication session, (for
authentication, synchronization etc) not per item within a replication
session. MDCR also carries the full DN of each modify operation within the
protocolOp, which is not strictly necessary for the current draft (00), and
could be omitted as URP does, if the number of bytes was a dominant concern.
However I believe it will be necessary for dealing with potential conflicts
between replication of prescriptive ACI information applying to an entry and
changes to the entry. I do not believe URP is capable of addressing that at
all.

Also, MDCR always propagates every change report to every replica, whether
or not it results in a visible change, whereas URP does not propagate a
primitive further, once it has encountered another for the same attribute
value with a higher CSN. This is important for explaining the difference in
predicability etc of the two alternatives, but not a significant difference
in efficiency "on the wire". In practice most changes are not made
concurrently to the same entry, and for the small proportion that are, those
with earlier CSNs will usually have propagated further than those with later
CSNs, which will therefore be catching up with them rather than preventing
their further propagation.

---

From: "Steven Legg" <[email-masked]>
Date: Wed, 19 Jul 2000 17:47:41 +1000

Albert,

> -----Original Message-----
> From: [email-masked]
> [mailto:[email-masked]]On Behalf Of Albert Langer
> Sent: Tuesday, 18 July 2000 21:18
> To: [email-masked]
> Cc: [email-masked]
> Subject: 3. "Change Reports - ProtocolOps or Primitives"
> 
> 
> Steve,
> 

Perhaps I should have said: Breaking all update requests into replication
primitives for conveying changes in the LDUP protocol (instead of
using the original protocolOp) gets around these problems.

> update requests into primitives gets around them.

The problem is that a list of all the standard LDAP or X.500 update
operations does not describe all the possible update behaviours
exhibited by directory servers.
 
> Please confirm whether that understanding is correct, or 

For the protocol design there was a discussion on whether the user updates
would be conveyed in the replication PDUs in their original form, which
was then broken down in to primitives by each replica to be processed, or
instead as the broken down set of primitives determined by the originating
server. It was a given at that time that the updates would be broken down
into primitives at some point, so it naturally came down to a choice
between LDAP update request or replication primitives in the protocol. 

The replication primitives can describe exactly how a directory server
executed a user update request without regard for the access protocol,
protocol extensions, conformance level, support for operational attributes,
etc. The small set of replication primitives is sufficient to describe a
much larger set of current and future directory server behaviours, as
well as being the basis for reconciling updates.

> directories, which could not be conveyed by MDCR.

The use of primitives allows the *LDUP protocol* to convey the additional
information.

> I do not 
> see any provision
> for this in URP and I do not think any such provision is 
> desirable.

The latest version of the URP document explicitly talks about what to
do with non-LDAP/X.500 update operations.

> It could

The LDUP protocol and URP don't need to change to accommodate other
types of update operations.
 
> additions would guarantee incompatability between different 

It's the reality now, there's no chance of it being ruled out, and it's
not a problem for the current LDUP design.

> and therefore should or could not just be copied verbatim by MDCR.

That's what I was saying.

> carries separately. Thus MDCR does not omit any information 

I think you might be underestimating how difficult it will be to translate
arbitrary extensions, controls and alternative access protocols into
canonical protocolOps. For one thing you will have to be prepared for
a single user update to map into multiple protocolOps affecting multiple
entries. I can think of a number of features in our directory and other
vendor's directories that would require this.

> a single operation (both "on the wire" and when processing 

I regard efficiency on the wire as largely a non-issue for replication.
My experience with X.525/DISP is that supplier DSAs can pump
changes through to consumers at least an order of magnitude faster
than the consumers can process them. A super efficient LDUP protocol
won't make much overall difference.

> not impeding future developments such as signed operations.o

Signed user operations are no more an issue for LDUP than they are
for DISP (i.e. irrelevant). X.500 has signed operations and doesn't
use the original DAP operations in its replication protocol and I've
never found a problem with that. In any case, a canonical MDCR change
report would invalidate the operation signature as surely as breaking
the operation down into primitives. 

> changes to the entry. I do not believe URP is capable of 

It's not obvious to me what sort of conflicts you are talking about.
Changes to prescriptive ACIs are much rarer than changes to entries
and unlikely to be directly linked. If there is a concern then wouldn't
MDCR be in bigger trouble because it is liable to completely discard
one of the linked changes ? Merging has fewer failure modes.

Regards,
Steven

---

From: "Albert Langer" <[email-masked]>
Date: Thu, 20 Jul 2000 22:53:46 +1000

Steve,

I am deferring responses to your replies on items 3 and 5 for now, while
catching up with the rest of my original list:

Done 3,4,5 and 8 so 1,2,6 and 7 still to go.

However I am also starting a separate thread 9 on this issue as it doesn't
really belong with item 3 and should be dealt with fully. Hoping you can
kick off the discussion.

At the end of my item 3 I mentioned in passing that:

> MDCR also carries the full DN of each modify
> operation within the

You responded briefly:

[Steve]

[Albert]
The sort of conflicts I was thinking about and preparing for, but did not
attempt to explain, and have not dealt with in my draft, (nor you in yours),
relate to the interaction between concurrent changes to any entry affected
by changes to prescriptive ACI applicable to entries depending on what the
entry's DN actually is (ie whether or not it is actually in a particular
subtree or subtree refinement regardless of its UUID). I do not think any
solution should attempt to directly link the changes. It is not obvious to
me either, as to exactly what problems there might be - but those are the
sort of problems I worry about most, as potential problems that are clear
are easily dealt with ;-0

Anyway, it is even less obvious what the solutions to unobvious problems
might require, so I didn't want to throw DN away and propagate only entryID.

As you know I have not proposed an alternative to URP's basic approach for
dealing with modifyDN, create and delete operations, but only for modify
operations, since your approach to the former does maintain atomicity.

I have suggested to both of you (via email twice to Alison with no reply)
that we get together again face to face over at least ACI issues, as we are
all in Melbourne. I'd still welcome that if you are interested.

Meanwhile, on the simpler issue of just replicating ACI *at all*, I believe
that MDCR behaves correctly by accepting only one change at a time, and that
the consequences of non-atomicity in URP are vividly illustrated by
considering its impact on simple ACI replication.

Could you please elaborate on your remark that "merging has fewer failure
modes", in this simpler context, with particular reference to the scenarios
that could result from merging concurrent changes to different ACI
attributes and attribute values as currently proposed in:

http://search.ietf.org/internet-drafts/draft-ietf-ldapext-acl-model-06.txt

(BTW as already mentioned I agree with your remark that the number of bytes
is really a "non-issue").

---

From: "Albert Langer" <[email-masked]>
Date: Thu, 20 Jul 2000 23:34:54 +1000

Steve,

Here's the response to item 6, which I summarized as:

***
Comments follow original below.
***

[Steve]

[Albert]
Performance is dominated by the normal case of no concurrent changes. If
concurrent changes are more than a small proportion of updates, the
application is just not suitable for the Directory as configured. Concurrent
changes are just an "unavoidable evil".

Even if the mechanism for dealing with that "unavoidable evil" was highly
inefficient, it would not have much effect on overall performance because it
is rarely used - it is just there to avoid the far more inefficient
alternative of manual intervention by system administrators.

For that reason there is no significant difference in performance between
MDCR and URP.

When there is no conflict, the tree would be trivial and there would be no
"going backwards".

When there is conflict, for the same reasons, performance is dominated by
the case of just 1 conflict. In that case "unwinding ... and then
applying..." is exactly equivalent to replacing the original entry with the
replacement, which happens to be precisely what URP does. The difference
being that MDCR does it based on the actual conflict tree whereas URP uses
roughly equivalent components of the lexical ordering to pretend that
changes occurred on a linear time scale even though they did not. There is
no difference in the complexity of actually implementing either ordering,
just a greater level of abstraction required in visualizing the tree rather
than succumbing to the illusion of sequential changes.

In the very rare cases when there is more than one conflict with a longer
single strand or a branching tree, MDCR actually has to do less work than
URP because URP makes each change visible as it arrives and therefore has to
update indexes (including "unwinding" indexes), whereas MDCR leaves some
arriving changes invisible and stores them only in case they are needed
later, so it does not have to update those indexes.

MDCR does have to store every arriving change report, but this can simply be
appending them to a log file, which can be very efficient for sequential
seeks on a separate log disk spindle since not even random seeks for primary
key indexing is required. Actual details are of course up to the
implementation.

Usually the log records would still be in RAM buffers if they need to be
read back within a reasonably short replication latency, but would normally
have to be written to disk for safety.

The guesstimate of 12 bytes of RAM overhead per tree entry was based on a 32
bit (4 byte) version  number, 2 x 16 bit replica number for up to 16K
replicas per replicated area, and a 32 bit pointer into a log file up to 4GB
long. Note that only these pointers are needed to maintain the shape of the
tree in RAM, the actual contents of the changes required to unwind and wind
forwards can be read back from the pointer into the log file.

An implementation might choose to break down a switch from one part of the
tree to another into "primitives" as you suggest, unwinding the index
entries a step at a time and then rewinding them a step at a time. In this
case that choice would not really matter as the frequency is negligible
anyway. I would of course be more inclined to do it "atomically" ;-) as a
single deletion of the currently visible entry and replacement by the new
visible entry.

In general I think implementing trees etc is not a big issue for software
development. Unfortunately they are harder to describe in standards, which
looks like a bigger problem at the moment.

PS I will deal with your example of a long strand when returning to item 5.

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Fri, 21 Jul 2000 13:06:40 -0700

>operations, since your approach to the former does maintain atomicity.

Does the fact that a modifyDN may change the entry's contents
have any impact upon this discussion?

---

From: "Albert Langer" <[email-masked]>
Date: Sat, 22 Jul 2000 08:09:30 +1000

[Kurt]

[Albert]
Yes, thanks for mentioning that. Whenever modifyDN is not just a move to a
different superior with no change in the RDN, then it changes the contents
as well as the DN (unless it happens to just swap some distinguished and
non-distinguished attribute values and not add or remove any).

Thus there isn't a complete separation between the Directory Information
Base (DIB) aspects that MDCR deals with and the Directory Information Tree
(DIT) aspects that I have just assumed will be handled along the same lines
that URP proposes.

My assumption has really been that URP does handle the DIT aspects
atomically, imprecisely described by me above as also handling modifyDN
atomically, although as you point out, only create and delete are actually
always handled atomically. It is the URP's "basic approach" to DIT issues
that I agree with - eg renaming by adding the entryID as a distinguished
value when there are clashes.

I've just assumed that given both DIT and DIB aspects would be handled
atomically, there wouldn't be any major problem combining them into a single
atomic operation in which they either both eventually succeed or both
eventually fail (whether due to DIT integrity constraints, structure rules,
name forms, object class schema or any kind of access controls). This may in
fact require some of the "distinguished-not-present" complications in URP,
hopefully only when the operation has eventually failed by resulting in a
renaming anyway.

But I haven't attempted to think any of that through at all - just proposing
a method of dealing with DIB changes atomically and leaving DIT issues to be
worked out in detail later, hopefully together with the authors of URP, and
only when and if the WG decides to consider MDCR by adding it to its agenda
as a possible alternative. (I'd certainly rather leave thinking through that
stuff to people who have already thought a lot about it - ie Steve and
Alison).

That overlap may well further complicate handling ACI issues, but I simply
haven't thought about it yet. Do you have any specific thoughts on it?

For now, I think the simplest possible example of what happens when URP
merges independent changes to different attributes or attribute values will
do, without complicating the examples by considering modifyDN. Just changes
to (non-distinguished) ACI attributes for a single entry made at different
replicas will suffice to show this just HAS to be done atomically.

---

From: "Albert Langer" <[email-masked]>
Date: Mon, 31 Jul 2000 04:42:26 +1000

Steve,

Here's the response to item 7, which I summarized as:

***

***

[Albert]

[Steve]

In effect, what we have done with URP is hardwire a reasonable conflict
resolution mechanism (best effort merge) that is (we think) good enough
for most uses of the directory.

[... Remainder already replied to as item 8, at end of URL above]

***

[Albert]
As you mentioned when changing the name from "Conflict Resolution" to
"Update Reconciliation", best effort merge is not a conflict resolution
method at all, because it sees no modify "conflicts".

URP does recognize conflicts when a child is created concurrently with the
parent being deleted, or two entries are given the same DN via concurrent
creates and/or modifyDN operations.

In that situation URP does store all the information necessary for users
to fix the problem without sysadmin intervention, and therefore also does
store all the information necessary to be able to issue revocation notices.

When you publish a draft with a sufficiently robust purge mechanism to
maintain eventual convergence despite clock non-monotonicity and DSAs
crashing and being restored from backups, you will find that you also have
sufficient information to be able to issue confirmation notices (ie notices
that no such naming collision can occur), and should then also be able to
rename just one of the entries in conflict rather than all of them, without
excessive complication. That is necessary avoid entire existing entries, not
just changes, mysteriously disappearing silently and without notification.

Naming conflicts should be much less frequent than modify conflicts
and are immediately obvious. So I have no objection to simply leaving
revocation and confirmation notices about them for possible future
extensions. No obstacle has been placed in the way of doing it later and you
have enabled users to fix the problem themselves (when the renaming is
restricted
to the results of new operations and not also applied to existing entries).

However the trade off for MDCR in avoiding the problems URP has with simple
modify
conflicts is that even a very low rate of concurrent modify operations
eventually
failing after a success response to a DUA, would still be a much higher rate
than is likely for modifyDN and create operations. Also the eventual
suppression of the operation during convergence would be much less obvious
than for naming conflicts.

Far from being "good enough for most uses of the directory" I regard ANY
regular manual sysadmin intervention as completely unacceptable.

As you have mentioned, it is especially unacceptable for suppressed ACI
changes, but there are also many other situations where silently
suppressing a change that has been reported as successful just won't work.

Just after its clear requirement for atomicity, RFC 2251 adds:

   The server will return to the client a single Modify Response
   indicating either the successful completion of the DIT modification,
   or the reason that the modification failed. Note that due to the
   requirement for atomicity in applying the list of modifications in
   the Modify Request, the client may expect that no modifications of
   the DIT have been performed if the Modify Response received indicates
   any sort of error, and that all requested modifications have been
   performed if the Modify Response indicates successful completion of
   the Modify Operation.  If the connection fails, whether the
   modification occurred or not is indeterminate.

(4.6 Modify Operation, p34)

Current client applications ARE designed with that expectation that all
requested modifications have been performed when they get a success
response. Any for which this is absolutely critical will of course also be
aware that servers sometimes crash before being backed up and will be
designed accordingly, but most applications do simply rely on that
expectation.

In a multi-master environment there is no alternative but to either drop
atomicity (and isolation) of operations or have some operations eventually
suppressed during convergence. That is a harsh reality.

In maintaining atomicity and isolation only for naming conflicts, URP
suffers
from the problems discussed elsewhere.

In taking the opposite approach, MDCR has to provide a "best effort" to
deal with the very real problems that result from that opposite approach.

The best that CAN be done is to issue revocation notices. That isn't
difficult
since all the information needed to do so is stored anyway.

LDUP standards HAVE to work with EXISTING LDAP client APIs and applications.
The whole reason LDAP is an important standard is the widespread adoption of
standardized client access.

I can't think of any application that would achieve anything useful to that
application by adding spurious changes to increase the chances of some other
instance of that application being suppressed during a conflict. Developers
doing so would be stupid, not "enterprising". However if I'm wrong about
that,
then it's good the facility is available.

Email revocation notices just ensure users (and sysadmins) know that a
change
was eventually suppressed, so they can do something about it before
something
else breaks as a result.

There is unfortunately nothing better that CAN be done about such conflicts
in a multi-master LDAP environment with existing clients. I can't see many
LDAP application developers dealing with the complexities of automatically
restoring application state either.

There are of course even less who COULD deal with the complexities of
maintaining, let alone restoring, application state based on merging
of unknown and unknowable concurrent changes as in URP.

NOBODY knows how to develop applications in an environment where the data
you
thought you were changing isn't necessarily the data you actually changed.

So to avoid that absurdity, MDCR just has to do the best it can, which is
revocation notices.

Of course the more important mitigation is moving attributes and attribute
values
that can safely be updated concurrently into separate child entries and
providing
a merged view of the parent as a compound family for existing LDAP clients.

Active Directory seems to be getting away with having just one of the
concurrent
additions or deletions to a security group or distribution list overwriting
any
others, but I can't see that scaling to really large organizational
environments,
let alone the global internet environment. So I'm trying to avoid the sort
of
problems that would result from an organization that just doesn't have any
real
concept of enterprise scalability, let alone global internet scalability,
dominating de facto LDAP standards, as currently looks very likely if LDUP
doesn't get its act together.

Once replication and distribution is standardized, LDAP will become even
more
deeply entrenched in internet infrastructure and more complex applications
with
transactional and synchronization requirements will become more common.

The LCUP drafts look like an excellent basis for handling notifications and
I am
quite confident that client APIs for that will become as widespread as
current
LDAP client APIs are now. Even without standardization, client APIs that
handle
three varieties of Microsoft proprietary asynchronous and "out of band"
synchronization notifications are already included in every copy of the
latest
version of the dominant client OS.

The information stored by MDCR anyway for actually resolving conflicts and
implementing weeding and summarizing robustly, can also be used to simplify
implementation of LCUP and servers can combine it with non-email
notifications for
revocation and confirmation.

In that (future) environment it is much more likely that application
developers
will start dealing with the complexities of restoring application context.
It is
already being done in Distributed File System projects for mobile and
disconnected
environments such as Coda, Intermezzo and Bayou and Lotus Notes has been
doing
something similar for many years.

Directory services WILL need to support this, so failing to provide for it
in
standards being developed now would be a mistake.

Incidentally, the same information stored that supports revocation and
confirmation
notices can also support signed operations per RFC 2649 and will be very
useful in
future support of transactions.

---

From: "Albert Langer" <[email-masked]>
Date: Mon, 31 Jul 2000 08:01:07 +1000

Steve,

I believe that I have covered item 2, which I summarized as:

This is covered both below in item 1, and in issue E of:

http://www.imc.org/ietf-ldup/mail-archive/msg00641.html

So this message completes the series of 9 items, except for responding to
your further comments on items 3 and 5, and any further comments you may
make on other items. Please let me know if I have failed to respond to
anything.

Here's the response to item 1, which I summarized as:

***

***
Comments interspersed with original below.
***

[Steven]

[Albert]
The user U1 at S1 wanted to modify the entry (A1,A2) from (-,x) to (y,z).

The user U2 at S2 wanted to modify it from (-,x) to (-,w).

The attributes A1 and A2 are presumably related, since U1 updated them
both at once.

They cannot both do what they want, so URP does something that
neither of them wanted to do. It modifies (-,x) to (y,w).

If U2 had known that the entry was (y,z) instead of just having read that it
was (-,x) he or she might have decided to check with U1 before changing it,
since U1 would be listed as the modifiersName and has recently changed it.

So U1 sees U2 listed as modifiersName for (y,w) and asks U2 "why did you
stuff up my change to (y,z) by changing it to (y,w)?".

U2 replies "I didn't, the entry was (-,x) and I changed THAT to (y,w).

After a few such incidents, one or other of U1 and U2 realize that it is
unlikely that the other is making the same stupid mistake over and
over again and refusing to admit it. So they report the mysterious behaviour
of the application to the Help Desk.

After a few attempts to convince them that they must be hallucinating and/or
pacify them with muzak, the Help Desk accumulates a sufficient range of
credible
reports, or a single report from a more senior user who can't be ignored,
and
passes it on to a sysadmin.

The sysadmin runs a few tests. Every time the sysadmin logs in as two
different
users and makes similar changes they work fine (because they are happening
on
the same replica). So the sysadmin reports "no fault found".

After a few more such incidents the sysadmins that have been called in
notice
that the users have become more hallucinatory than usual and are becoming
"restless".

Eventually the problem escalates to the point where a more senior and
experienced sysadmin is told "FIND it and FIX it NOW".

The experienced sysadmin checks what changed around the time the users
starting to
hallucinate. After investigating the application, the directory software,
the
air-conditioning, the water supply, the operating system and so forth, none
of which have changed, the experienced sysadmin eventually notices that a
very minor configuration change occurred, with two way replication instead
of one way replication between directory servers.

The wise sysadmin has never heard of atomicity but knows exactly what to do.
He or she undoes that minor change, just because it correlates with the
hallucinations.

Everyone lives happily ever after, except perhaps the directory vendor, who
might get sued.

Of course with any luck, one of A1 or A2 will be ldapACI, so a CERT advisory
warning people not to turn on two way replication will go out relatively
quickly,
lower level sysadmins will be more likely to see that, and a great deal of
wasted
time will have been avoided - except of course for the LDUP WG developing
standards
and the vendors silly enough to implement them.

With MDCR the situation is also unsatisfactory, though not as bad. Some time
after
having made the change from (-, x) to (y, z), U1 will get an email
notification
explaining that this change was automatically revoked because another user
changed
the entry at around the same time on a different server.

If that happens too often, somebody will either have to reconfigure the
replication
scheduling or alter the application to separate A1 and A2 into different
child entries.

But the problem will be a clear and easily understood result of using
multi-master
in a situation that is unsuitable for it. Not just a mysterious "something's
broken".

[Steve]

[Albert]
The current requirements draft has a completely meaningless definition:

      Atomic operation - The ability to treat and contain several updates
      or attribute changes as a single operation for replication purposes
      to guarantee that the several updates or attribute changes are
      propagated to a replica as a single unit.

In order to discuss and even think about anything at all, we have to use
the "usual" definitions. The purpose of Orwellian doublespeak is precisely
to prevent discussion and thought.

If URP just had to meet that Orwellian definition, it would pass with flying
colors - every modification in a single operation is elaborately provided
with a sequential modification number, wrapped in a framed operation and
propagated to a replica as a single unit. The only point of doing so seems
to
be to distract attention from the fact that on arrival it is promptly
merged,
with concurrent changes at that replica and those that have arrived from
other replicas, and the merged changes, which are not the result of ANY
LDAP operation, are then elaborately sequenced and packaged to repeat the
charade elsewhere.

This produces a combinatorial explosion of intermediate visible states which
can be read by DUAs and be the basis for other changes. When there are no
such further changes the result eventually converges (leaving aside problems
with timestamps etc) to a MIXTURE of the various concurrent operations.

THIS is "clearly the wrong thing to do". It is less atomic than it needs to
be because it is the precise opposite of atomic. What is needed is for
applications to know that either the whole operation succeeded or the
whole operation failed.

Since they are built on that assumption they will break when it isn't true.

As well as making intermediate partial operations visible to DUAs, URP does
NOT converge to "an outcome that is equivalent to the serial atomic
execution
of all the updates". That can only be done by suppressing changes that are
not
part of a sequence in which each successor could have read the result of its
predecessor - which is the whole point of the tree maintained by MDCR.

For example if two users replace the same attribute value with a different
new
value serially, by deleting the old value and adding the new value, one of
the
atomic operations MUST fail, since it has attempted to delete a value that
isn't there. With URP, both succeed. In fact URP *always* succeeds, whereas
atomicity is all about sometimes failing.

URP will even "succeed" if two users concurrently delete two different
values
from a mandatory attribute that originally held two values. It will
"succeed"
by deleting both and marking it as a schema violation for the sysadmin to
clean
up. What then was the point of the schema?

For LDUP to be "as atomic as it needs to be" it needs to be as atomic as
expected by the existing LDAP applications.

The "usual" definition isn't just some convention, it is a mandatory
standard
for LDAP which MUST be complied with by LDUP standards.

[Steve]

[Albert]
Stop fantasizing about revolving around aspects of reality that are
inconvenient
for URP.

Here's the REAL requirement that LDUP MUST meet. It isn't a question, it is
a command:

  - modification: A list of modifications to be performed on the entry.
     The entire list of entry modifications MUST be performed
     in the order they are listed, as a single atomic operation.  While
     individual modifications may violate the directory schema, the
     resulting entry after the entire list of modifications is performed
     MUST conform to the requirements of the directory schema. The
     values that may be taken on by the 'operation' field in each
     modification construct have the following semantics respectively:

             add: add values listed to the given attribute, creating
             the attribute if necessary;

             delete: delete values listed from the given attribute,
             removing the entire attribute if no values are listed, or
             if all current values of the attribute are listed for
             deletion;

             replace: replace all existing values of the given attribute
             with the new values listed, creating the attribute if it
             did not already exist.  A replace with no value will delete
             the entire attribute if it exists, and is ignored if the
             attribute does not exist.

(RFC 2251 4.6 Modify Operation, p33)

[Steve]

[Albert]
The URP "philosophy" is that existing standards don't matter and that manual
sysadmin fixes for the results of breaking them are acceptable.

You *seem* to be also saying that the state of an entry before it is written
doesn't really matter to the user changing it.

If that was really true ANY of the time, for ANY applications, there
wouldn't
be much point changing it, would there?

MDCR certainly does suppress concurrent changes, "just in case" the state of
the entry did matter. Its "philosophy" is that the state matters or they
wouldn't be changing it.

It does so "after the fact", which WILL cause problems, because there is no
other possibility in a multi-master environment.

But it doesn't "completely disregard" the suppressed update. See item 7 on
Notifications.

Faced with the unpleasant consequences of multi-master, the vital thing is
to get the widest
possible input from people likely to be affected by them, as to what trade
offs should be made.

If MDCR doesn't pass that scrutiny, something better will be worked out.

By failing to present a requirements document that clearly and frankly
explains the issues
and solicits input, the LDUP WG can guarantee that whatever it decides on
will meet vendor
requirements and not have to worry about user requirements.

That is clearly the wrong thing to do.