Subject: URP, Replication Update Protocol, and atomic changes

From: "John McGarvey" <[email-masked]>
Date: Mon, 5 Mar 2001 14:50:32 -0500

Applications sometimes need to make atomic changes to an entry.  One
example is a simple counter, a single valued attribute that is incremented
by replacing the current value with the incremented value.  This works fine
in a single master case.  It does not work in a multimaster case using URP,
because the value may be incremented, say from 4 to 5, on one of the
servers and then, before that change has been propagated via replication,
the counter might be incremented on a different server, also from 4 to 5.
The value after replication would remain 5, but the desired result is 6.
The problem of atomic changes to entries has been thoroughly discussed on
the list.

URP does not provide any application workaround for this problem.  This is
troubling.  I would like to suggest a workaround for use in URP.  Suppose,
for any replication context, one server is defined as the master for any
changes requiring atomicity.  We would have to define a means to advertise
the location of the master.  If application needs, say, to increment a
counter, it should be written make that change on the atomicity master for
that replication context.  If that master is unavailable, the change must
not proceed.  Changes not requiring atomicity -- probably the great
majority of writes to the directory -- could proceed on any peer master.
Of course, this approach to atomicity does not guarantee that conflicting
changes do not occur concurrently on other servers, because some
applications may fail to use the mechanism.  But, for applications that do
exploit this approach consistently, reliable counters and other data
requiring atomic change could be stored in the directory.

This approach could be extended to make an atomic change to a collection of
entries, so as to offer simple transactional semantics without 2 phase
commit:

[control to begin atomic change] operation operation operation [control to
end atomic change]

If all of these grouped operations are on directory entries within
replication contexts for which a single server is the atomicity master,
that master evaluates the collection of changes, applying all or none of
them.  If the current server is not the atomicity master for all of the
affected entries, it rejects, or possibly redirects, the group of
operations. Of course, as for a single entry, conflicting changes may occur
concurrently on other servers, if applications fail to use the mechanism.

When changes corresponding to a group of operations are replicated, they
should be applied as a unit, so that an application reading data from the
directory is not returned data corresponding to an intermediate state in
which some but not all entries affected by the group of operations have
been updated.  LDUP Replication Update Protocol currently groups changes to
a single entry, so that such changes can be applied as a unit, but it does
not provide a means of grouping changes to a collection of entries.
Perhaps the protocol should be extended to support this kind of grouping.

This suggestion would require two changes to the current LDUP drafts: (1) a
means of identifying the atomicity master for a given replication context,
and (2) a change to the replication update protocol to permit grouping of
changes to multiple entries so that they can be treated as a unit.

-- John McGarvey

---

From: "Albert Langer" <[email-masked]>
Date: Wed, 7 Mar 2001 02:53:16 +1100

[John M]
[...]

[Albert]
I've omitted your discussion of a "workaround" in view of the current
requirements:

P7.  The protocol MUST preserve atomicity of LDAP operations as defined
in RFC2251 [RFC2251].

MM5.  Multi-master replication MUST NOT lose information during
replication.  If conflict resolution would result in the loss of
directory information, the replication process MUST store that
information, notify the administrator of the nature of the conflict and
the information that was lost, and provide a mechanism for possible
override by the administrator.

They will either be accepted, rejected or modified. In my view
discussion of that is needed before discussion of workarounds.
I'll be happy to join in discussion of that, but meanwhile am
not interested in discussion of workarounds.

I am however interested in multi-master at least not impeding work on
grouped operations so I would like to discuss that part of your
message.

The way I see it confining grouped operations to a single server
("atomicity master") doesn't solve the problem of how to avoid impeding
work on grouped operations, but just avoids the issue. Calling a single
master an "atomicity master" does not enable it to provide any of the
benefits of fault tolerance and local changeable copies that
multi-master is supposed to provide.

At present grouped operations are not part of the X.500/LDAP model for
reasons that have nothing to do with multi-master or lack of atomicity.
X.500 and LDAP currently assume a single master environment and they
require atomicity whether it is single master or not. The problem is
that the directory service is intended to be globally scalable with
applications referring to entries by their directory names,
without having to know what server will actually respond to queries
or perform updates. The directory is distributed globally among
many servers holding many Naming Contexts. A referral can be given
to any server without the application needing to know about what
servers hold what Naming Contexts, let alone whether a server is
part of a replicated area or is a single master or a slave or an
"atomicity master". You can't even rely on a set of direct children
of a single parent being on the same DSA, let alone an arbitrary
group of entries that are not siblings.

Ignore that and you are designing a not very good local substitute
for a DBMS rather than part of a global directory service.

Why not just use ODBC as the client server protocol instead
of LDAP? You'd get ACID transactions and a full query language with
selects, joins, insert, update etc - not just atomicity and queries
with filter scopes restricted to simple subtrees and changes to
a predefined group of entries (1 at present, some larger
predefined set with grouped operatons).

The point of the *limitations* of LDAP is to work in that globally
scalable *distributed* environment. Anything that doesn't need
that can just use a DBMS.

A grouped operation can of course be restricted to work only within
a single Naming Context (hence a single server for single master).
This is necessary for the new parent option of modifyDN because it
hasn't been shown to be globally scalable to coordinate moves
between two independent servers that are designed to each just
look after their own parts of a global namespace rather than be
able to establish secure bilateral relations with any other DSA.
(It may become feasible with widely deployed directory based
Public Key certificate Infrastructure).

At present it isn't even clear how LDUP proposes to deal with
modifyDN operations within a Naming Context that has several
replicated areas. Version 5 of the architecture is the first
that actually recognized the distinction but it still hasn't
linked it to handling modifyDN within a Naming Context rather
than just within a replicated area (which leaves a Naming
Context somewhat useless for namespace management).

But whatever LDUP does to allow grouped operations to work in a
replicated area (or, harder, within a Naming Context), has to
be based on not impeding work done on grouped operations for
*distributed* single master. Anything done for a single server
environment should be standardized in LDAPEXT if it really needs
LDAP at all and anything done across distributed DSAs holding
different Naming Contexts likewise should be standardized in
LDAPEXT. We just have to make sure that when an area is
replicated instead of held by a single DSA it breaks as
little as possible and impedes as little as possible in
return for the benefits of doing so (fault tolerance and
local changeable copies).

So I don't see much point in trying to tackle the problem
here. The best we can do is just avoid getting in the way.

That can be done by ensuring we at least do support the
current data model so that multi-master servers aren't
getting in the way of attempts to extend it.

At present we have a proposed requirement for doing that,
but no proposed architecture or conflict resolution
procedures that meet the requirement. Let's focus on how
to actually implement that requirement for single entries
before worrying about how to extend it to multiple
entries. It just doesn't make sense to me to be
simultaneously looking for a "workaround" instead of
implementing atomicity at the level of entries, while
in the very same message proposing to solve the harder
problem of atomicity extending over multiple entries.

[John M]

-- John McGarvey

[Albert]
There's been no problem specifying a transfer protocol that will carry all
parts
of an operation as a unit. In fact the LDAP protocolOp syntax did exactly
that
without any help from LDUP. All that's needed is *not* splitting it into
sub-atomic primitives by just leaving it alone.

Wrapping that into a sequence of grouped operations is no harder. That's all
you need "so that such changes *can* be applied as a unit". What's needed
now
is a multi-master architecture that *does* apply them as a unit (and doesn't
lose information etc). Calling a server an "atomicity server" instead of
just
a plain ordinary DSA does not give it any enhanced capabilities whatsoever
beyond what LDAP had before LDUP started work. A simple label "not broken"
would suffice. Step 1 apply the changes to a single entry as a unit. Step
2 check what LDAPEXT is doing about applying grouped changes to multiple
entries as a unit and make sure we aren't impeding it. Step 3 try to
actually
implement grouped changes it in a multi-master context. After 2 years we
still haven't actually started work on step 1, but only started to recognize
that we might have to.

There are lots of ways applications can build their own grouped operations
on
top of a directory service that does support atomicity, without any support
from the directory service. It can even be done with a directory that breaks
atomicity at the entry level but at least maintains it at the attribute
level.
eg I have the impression that some Active Directory applicatins use a UUID
to
identify all changes made as a group. If a DUA following that application
convention reads back the same UUID on all the changes it made, then it
knows
that no other DUA following the same convention interfered with those
changes
(provided a full replication across the replication network has occurred).
Otherwise it needs to rollback those parts of the change that weren't
interfered with and leave it the other DUAs to rollback their bits that
they regard as having been interfered with, because they also see that their
UUIDs did not stick. There are various other tricks such as hashes and
child counts. Extending DSA support for them such as cleaning up if DUAs
fail to do their rollbacks could be useful one day - but not until after
we have simple entry level atomicity actually in place.

The UUID trick doesn't work when atomicity is broken at the attribute
value level, as with URP, because you just end up with the groupedUUID
attribute containing UUIDs from each of the conflicting grouped operations
with no way to tell which of the changes made to other attributes was made
by which grouped operation. You can't even tell which DUA made the change,
let alone which grouped operation by that DUA the change corresponds to,
because even modifiersName doesn't work without atomicity.

Let's fix it and *then* move on, not proudly label DSAs that have not
been broken by LDUP as "atomicity masters". They already have a name -
LDAP servers.