Subject: reconciliation of mutually exclusive operations

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Tue, 01 Aug 2000 09:26:57 -0400

If the entry (contents trimmed):

	dn: cn=entry, dc=example, dc=net
	cn: entry
	boolean: FALSE

is held by N servers in using multi-master replication and
N independent, properly authorized clients each issuing the
following operation to a different (willing and able) servers:

	dn: cn=entry, dc=example, dc=net
	changetype: modify
	delete: boolean
	boolean: FALSE
	-
	add: boolean
	boolean: TRUE
	-

One client should get a success result code.
N-1 clients should get a non-success result code.

I believe that any replication specification which cannot ensure
this behavior is not acting in accordance with X.500(93) as required
by LDAPv3.

---

From: "Albert Langer" <[email-masked]>
Date: Wed, 2 Aug 2000 02:58:27 +1000

[Kurt]

[Albert]
Correct, but unfortunately the "should" behaviour is not possible with
ANY form of multi-master replication, since it would require contacting
other servers before returning the response code, and by definition,
multi-master does not do that. The only "standard" way to do it, would
be to unilaterally disconnect after making the change, without giving a
response code, since the standard does tell DUAs not to assume anything
in that situation.

I'm not suggesting disconnection would be a good idea, but it is an option.

(The standard does permit reads conflicting with what has just been written,
since that happens with single master too, as users aren't supposed to be
aware of which particular DSA they are asking).

For multi-master, there is NO other way to avoid them all getting a
"success"
response when they all perform the operation around the same time at
different replicas.

There may well be applications which rely on the currently expected
behaviour, eg to ensure that one, and only one, of those N DUAs
performs some action.

MDCR could also follow up with revocation notifications to all but one of
the
DUAs, and a confirmation notification to one, just to inform them of the
conflict. They could wait for the notification before performing the action,
as a sort of delayed response, while other applications would act on the
immediate operation response. But I doubt that would be very useful in
practice,
other than as a reminder that they should not use multi-master in this
situation.

Perhaps it could be useful - for some applications that need high
availability but not necessarily local availability with its longer
convergence delay.
We won't actually know without feedback.

This sort of behaviour contrary to that currently expected certainly
requires at least formal justification (eg in the requirements doc),
but there really isn't much more we can do about it, apart from
warning people not to use multi-master in that way.

If some of the DUAs had attempted to simply delete the attribute "boolean",
(assumed optional), both URP and MDCR would report "success" to both
those that now expect the attribute to be absent and to those which
expect it to be TRUE. But MDCR would at least follow up with a
notification to those which have the wrong expectation as a result, and
an (optional) confirmation to those that have the right expectation. Again
this might not help much, but at least users and administrators would find
out promptly by email that something odd was going on as a result of
inappropriate
use of multi-master, rather than just be left wondering why applications
dependent
on standard behaviour have intermittant failures (dependent on the
replication
schedule and which servers happen to be contacted, and therefore about as
relevant
to users in understanding an intermittant problem as the phase of the moon).

Its rather more serious for a non-boolean attribute. If the current value
of "color" is YELLOW and some try to set it to GREEN and others to RED, by
deleting YELLOW first and then adding GREEN or RED respectively, they
will again all get a "success" response, which confirms the inapplicability
of multi-master replication to traffic control applications ;-)

With MDCR, convergence would eventually be to just GREEN, with a
notification
to those that thought it was now RED, if a GREEN DUA got in first (according
to the clock at that replica), or vice versa. The ordering is essentially
arbitrary since clocks are not synchronized. If all N clocks happened to
be identical (whether or not the "real" time was identical), it would be
the color at the replica with the highest replica number, which is just as
arbitrary, but no more so.

With URP, the same would be true for a single valued color attribute, except
for no notifications.

For a multi-valued color attribute the eventual result of URP would be both
GREEN and
RED, contrary to the expectations of ALL the DUAs. When they try to fix it
by deleting
the color they think shouldn't be there, the result would of course be
empty, and a
schema violation if the color was mandatory, but they would again all be
told "success"
and with no follow up notification.

With the multi-valued attribute ldapACI, which IS used for a sort of
"traffic
control" by the directory itself, it gets rather interesting when DUAs
concurrently
delete an old value and replace it with different new values. I'm looking
forward
to Steve's response to the request for an example in item 9.

These sort of issues and examples should be clearly explained in the
requirements
document to get feedback on how actual existing applications would be
affected.

BTW can anyone do a quick unofficial description of the Pittsburg discussion
outcome,
re requirements document, prior to official minutes?

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Sat, 05 Aug 2000 19:19:23 -0700

I agree that multi-master replication will break any and all
implementations which rely on X.500/LDAP data consistency
properties.  Though I agree multi-master replication is useful
in many applications of the directory, so is tight data consistency.

Minimally, some means must be provided to allow clients to discover
the consistency properties offered.  However, existing clients
which rely on existing consistency properties would have to be
redesigned to use this discovery mechanism.

I believe LDUP WG should specifically address this and related
issues in requirements document.

Kurt

---

From: "Albert Langer" <[email-masked]>
Date: Sun, 6 Aug 2000 15:32:56 +1000

[Kurt]

[Albert]
Needless to say I agree this should be addressed in requirements,
which of course requires addressing the related issue of what the
consistency properties to be discovered actually are ;-)

I would still love to see an unofficial description of how the
discussion on this went, while waiting for the official minutes.

Your minimal requirement is partially met by the existence of
multi-master specific subentries and a pointer to their existence
from the DSA root entry, as this can easily be discovered by clients
that are aware of the need to look.

To add more than that, I guess one could add something to
the bind response. But if the client is already aware of the
possibility, it could just look at the existence of the subentries,
so this would only be a minor performance enhancement, not a solution
to the problem of clients not knowing what they are up against.

For existing clients, any such response MUST NOT cause the client to
fail as a result of not understanding it. Therefore it MUST be ignored
by clients that do not understand it.

So, as you point out, it does not actually help solve the problem.

Since existing clients, by definition, have NOT been redesigned for
multi-master when it is first introduced, I believe the only solution
is to send a notification to the email address of any DUA that is given
a "success response" which turns out to be incorrect after eventual
convergence, unless this has been explicitly turned off (or redirected)
by the client, using either an attribute value in the DUA's entry or a
control in the bind or the operation request.

Note that DUA administrators can turn this off via the DUA entry (and
DUAs users can overide the setting either way with explicit controls in the
bind or in individual change operations). However there is intentionally
NO facility for a replica DSA administrator to turn it off, or not implement
it, for DUAs using that replica generally. That is necessary because DUAs
cannot be assumed to know the replication configuration of DSAs they get
referred to from other DSAs outside a replication area.

This is proposed in MDCR, with the necessary machinery to be able to
retain the information needed for such notifications. It still has the
unsatisfactory result of giving a "success" response that isn't necessarily
correct, but it sends a notice ONLY when there is an actual conflict, which
should be only for a small proportion of writes, which are only for a small
proportion of directory operations. In practice the occurrence of such
notifications only draws attention to the fact that multi-master is being
used inappropriately, but that does meet the "minimal" requirement.

By adding support for confirmations, and integration of non-email
notifications with LCUP, real enhanced support can be given to
future enhanced clients.

With single master, another DUA could of course change the entry immediately
afterwards, or between reading an entry and writing a change to it based on
that read. Also a DSA could crash just after sending a "success" response
and before backup or replication.

Once multi-master does maintain atomicity, the problem is simply that such
conflict between what DUAs write and what they actually get will be more
frequent than with single master, whereas most current applications expect
it to hardly ever happen at all.

I believe the email notification in MDCR is both necessary and sufficient
as a mandatory requirement.

Do you agree?

PS The current vaguely mentioned approach, is for DUAs to use only the
"primary" for operations that require tighter consistency, with no actual
mechanism specified to ensure this. Any such mechanism cannot meet this
requirement unless it also shuts out DUAs attempting to use any other
replica,
since existing DUAs are by definition unaware of the mechanism. Shutting
them
out would of course amount to single master. (There is no concept of DUA
specific
access controls in ACL standards).

I am doubtful that this concept of a "primary" has any value at all (though
it
may help when attempting grouping or transactions for multiple entries). If
and
when a mechanism is actually proposed, it could perhaps be integrated with
the
notifications via options in the controls and DUA settings to generate or
suppress a notification only if the replica was bound to a non-primary.
There
would in fact be no conflicts and therefore no notifications if all the
concurrent
operations affecting an entry were IN FACT directed to a single replica,
*whether
or not* that replica is officially designated as a "primary", so I cannot
see
much actual use for such suppression, but am just mentioning it because it
appears
that *somebody* must believe "primaries" are somehow relevant to these
issues.