Whichever change arrives first, requirement MM6 says that the values
from replica A must be those in place on all replicas at the end of
the replication cycle. Requirement MM5 states that the system cannot
quietly ignore the values from replica B.
The values from replica B might be logged with some notice to the
administrators, or they might be added to the DIT with a machine
generated DN (again with notice to the administrators). If they are
stored with a machine generated DN, the same DN must be used on all
servers in the replica-group (otherwise requirement M3 would be
violated). Note that in the case where the entry in question is a
container, storage with a machine generated DN provides a place where
descendent entries may be stored if any descendents were generated
before the replication cycle was completed.
In any case, some mechanism must be provided to allow the
administrator to reverse the conflict resolution algorithm and force
the values originally created on B into place on all replicas if
desired.
B.5.2. Rename-Rename
On replica A, an entry with distinguished name DN1 is renamed to DN.
At the same time on replica B, an entry with distinguished name DN2
is renamed to DN.
In the single-server case, one rename operation would occur before
the other and the second would fail since the target name already
exists.
In the multi-master case, each rename was successful on its
originating server. Assuming that the change on A has priority in
the conflict resolution sense, DN will be left with the values from
DN1 in all replicas and DN1 will no longer exist in any replica. The
question is what happens to DN2 and its original values.
Requirement MM5 states that these values must be stored somewhere.
They might be logged, they might be left in the DIT as the values of
DN2, or they might be left in the DIT as the values of some machine
generated DN. Leaving them as the values of DN2 is attractive since
it is the same as the single-server case, but if a new DN2 has
already been created before the replica cycle finishes, there are
some very complex cases to resolve. Any of the solutions described
in this paragraph would be consistent with requirement MM5.
B.5.3. Locking Based on Atomicity of ModifyRequest
There is an entry with distinguished name DN that contains attributes
X, Y, and Z. The value of X is 1. On replica A, a ModifyRequest is
processed which includes modifications to change that value of X from
1 to 0 and to set the value of Y to "USER1". At the same time,
replica B processes a ModifyRequest which includes modifications to
change the value of X from 1 to 0 and to set the value of Y to
"USER2" and the value of Z to 42. The application in this case is
using X as a lock and is depending on the atomic nature of
ModifyRequests to provide mutual exclusion for lock access.
In the single-server case, the two operations would have occurred
sequentially. Since a ModifyRequest is atomic, the entire first
operation would succeed. The second ModifyRequest would fail, since
the value of X would be 0 when it was attempted, and the modification
changing X from 1 to 0 would thus fail. The atomicity rule would
cause all other modifications in the ModifyRequest to fail as well.
In the multi-master case, it is inevitable that at least some of the
changes will be reversed despite the use of the lock. Assuming the
changes from A have priority per the conflict resolution algorithm,
the value of X should be 0 and the value of Y should be "USER1" The
interesting question is the value of Z at the end of the replication
cycle. If it is 42, the atomicity constraint on the change from B
has been violated. But for it to revert to its previous value,
grouping information must be retained and it is not clear when that
information can be safely discarded. Thus, requirement G6 may be
violated.
B.5.4. General Principles
With multi-master replication there are a number of cases where a
user or application will complete a sequence of operations with a
server but those actions are later "undone" because someone else
completed a conflicting set of operations at another server.
To some extent, this can happen in any multi-user system. If a user
changes the value of an attribute and later reads it back,
intervening operations by another user may have changed the value.
In the multi-master case, the problem is worsened, since techniques
used to resolve the problem in the single-server case won't work as
shown in the examples above.
The major question here is one of intended use. In LDAP standards
work, it has long been said that replication provides "loose
consistency" among replicas. At several IETF meetings and on the
mailing list, usage examples from finance where locking is required
have been declared poor uses for LDAP. Requirement G1 is consistent
with this history. But if loose consistency is the goal, the locking
example above is an inappropriate use of LDAP, at least in a
replicated environment.
B.5.5. Avoiding the Problem
The examples above discuss some of the most difficult problems that
can arise in multi-master replication. While they can be dealt with,
dealing with them is difficult and can lead to situations that are
quite confusing to the application and to users.
The common characteristics of the examples are:
- Several directory users/applications are changing the same data.
- They are changing the data before previous changes have replicated.
- They are using different directory servers to make these changes.
- They are changing data that are parts of a distinguished name or
they are using ModifyRequest to both read and write a given
attribute value in a single atomic request.
If any one of these conditions is reversed, the types of problems
described above will not occur. There are many useful applications
of multi-master directories where at least one of the above
conditions does not occur. For cases where all four do occur,
application designers should be aware of the possible consequences.
B.6. Data Confidentiality and Data Integrity During Replication
Directories will frequently hold proprietary information. Policy
information, name and address information, and customer lists can be
quite proprietary and are likely to be stored in directories. Such
data must be protected against intercept or modification during
replication.
In some cases, the network environment (e.g., a private network) may
provide sufficient data confidentiality and integrity for the
application. In other cases, the data in the directory may be public
and not require protection. For these reasons data confidentiality
and integrity were not made requirements for all replication
sessions. But there are a substantial number of applications that
will need data confidentiality and integrity for replication, so
there is a requirement (S4) that the protocol allow for data
confidentiality and integrity in those cases where they are needed.
Typically, the policy on the use of confidentiality and integrity
measures would be held in the replication agreement per requirement
M7.
This leaves the question of what mechanism(s) to use. While this is
ultimately a design/implementation decision, replication across
different vendors' directory products is an important goal of the
LDAP replication work at the IETF. If different vendors choose to
support different data confidentiality and integrity mechanisms, the
advantages of a standard replication protocol would be lost. Thus
there is a requirement (S6) for mandatory-to-implement data
confidentiality and integrity mechanisms.
Anonymous replication (requirement S3) is supported since it may be
useful in the same sorts of situations where data integrity and data
confidentiality protection are not needed.
B.7. Failover in Single-Master Systems
In a single-master system, all modifications must originate at the
master. The master is therefore a single point of failure for
modifications. This can cause concern when high availability is a
requirement for the directory system.
One way to reduce the problem is to provide a failover process that
converts a slave replica to master when the original master fails.
The time required to execute the failover process then becomes a
major factor in availability of the system as a whole.
Factors that designers and implementors should consider when working
on failover include:
- If the master replica contains control information or meta-data
that is not part of the slave replica(s), this information will
have to be inserted into the slave that is being "promoted" to
master as part of the failover process. Since the old master is
presumably unavailable at this point, it may be difficult to obtain
this data. For example, if the master holds the status information
of all replicas, but each slave replica only holds its own status
information, failover would require that the new master get the
status of all existing replicas, presumably from those replicas.
Similar issues could arise for replication agreements if the master
is the only system that holds a complete set.
- If data privacy mechanisms (e.g., encryption) are in use during
replication, the new master would need to have the necessary key
information to talk to all of the slave replicas.
- It is not only the new master that needs to be reconfigured. The
slaves also need to have their configurations updated so they know
where updates should come from and where they should refer
modifications.
- The failover mechanism should be able to handle a situation where
the old master is "broken" but not "dead". The slave replicas
should ignore updates from the old master after failover is
initiated.
- The old master will eventually be repaired and returned to the
replica-group. It might join the group as a slave and pick up the
changes it has "missed" from the new master, or there might be some
mechanism to bring it into sync with the new master and then let it
take over as master. Some resynchronization mechanism will be
needed.
- Availability would be maximized if the whole failover process could
be automated (e.g., failover is initiated by an external system
when it determines that the original master is not functioning
properly).
B.8. Including Operational Attributes in Atomic Operations
LDAPv3 [RFC2251] declares that some operations are atomic (e.g., all
of the modifications in a single ModifyRequest). It also defines
several operational attributes that store information about when
changes are made to the directory (createTimestamp, etc.) and which
ID was responsible for a given change (modifiersName, etc.).
Currently, there is no statement in RFC2251 requiring that changes to
these operational attributes be atomic with the changes to the data.
It is RECOMMENDED that this requirement be added during the revision
of RFC2251. In the interim, replication SHOULD treat these
operations as though such a requirement were in place.
Authors' Addresses
Russel F. Weiser
Digital Signature Trust Co.
1095 East 2100 South
Suite #201
Salt Lake City, UT 84106
Phone: +1 801 326 5421
Fax: +1 801 326 5421
EMail: rweiser@trustdst.com
Ellen J. Stokes
IBM
11400 Burnet Rd.
Austin, TX 78758
Phone: +1 512 436 9098
Fax: +1 512 436 1193
EMail: stokese@us.ibm.com
Ryan D. Moats
Lemur Networks
15621 Drexel Circle
Omaha, NE 68135
Phone: +1 402 894 9456
EMail: rmoats@lemurnetworks.net
Richard V. Huber
Room C3-3B30
AT&T Laboratories
200 Laurel Avenue South
Middletown, NJ 07748
Phone: +1 732 420 2632
Fax: +1 732 368 1690
EMail: rvh@att.com
Full Copyright Statement
Copyright (C) The Internet Society (2002). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
Acknowledgement
Funding for the RFCEditor function is currently provided by the
Internet Society.