One document matched: draft-ietf-ldup-urp-01.txt
Differences from draft-ietf-ldup-urp-00.txt
INTERNET-DRAFT S. Legg
draft-ietf-ldup-urp-01.txt Telstra
A. Payne
PricewaterhouseCoopers
June 25, 1999
LDUP Update Reconciliation Procedures
Copyright (C) The Internet Society (1999). All Rights Reserved.
Status of this Memo
This document is an Internet-Draft and is in full conformance with
all provisions of Section 10 of RFC2026.
Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF), its areas, and its working groups. Note that
other groups may also distribute working documents as Internet-
Drafts.
Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress".
The list of current Internet-Drafts can be accessed at
http://www.ietf.org/ietf/1id-abstracts.txt
The list of Internet-Draft Shadow Directories can be accessed at
http://www.ietf.org/shadow.html.
This draft is published by the IETF LDUP Working Group. Distribution
of this document is unlimited. Comments should be sent to the LDUP
Replication mailing list <ldup@imc.org> or to the author.
This Internet-Draft expires on 25 December 1999.
1. Abstract
This document describes the procedures used by directory servers to
reconcile updates performed by autonomously operating directory
servers in a distributed, replicated directory service.
These procedures are a joint development of the IETF and ITU-T for
use in LDAP directory replication (LDUP), and the X.500 Directory
Multi-master Replication Protocol (DMRP) [N11034].
Legg & Payne Expires 25 December 1999 [Page 1]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
2. Table of Contents
1. Abstract 1
2. Table of Contents 2
3. Introduction 2
4. Model Extensions 3
4.1 Unique Identifier 3
4.2 Timestamps & Existence 3
4.3 Replication Log 4
4.4 Lost & Found 6
5. Replication Procedures 6
5.1 Processing LDAP, DAP or DSP Operations on the DIT 6
5.1.1 Add Entry 7
5.1.2 Remove Entry 8
5.1.3 Modify Entry 8
5.1.3.1 Ascending Modification Numbers 9
5.1.3.2 Fixed Modification Numbers 10
5.1.4 Modify DN 12
5.2 Processing Replication Primitives on the DIT 12
5.2.1 Propagating Primitives 13
5.2.2 Saving Deletion Records 14
5.2.3 Glue Entries 15
5.2.4 Generating Change Sequence Numbers 15
5.2.5 Comparison of Attribute Values 16
5.2.6 Renaming Entries 16
5.2.7 Name Conflict Resolution 18
5.2.8 Processing Add Attribute Value Primitive 18
5.2.9 Processing Remove Attribute Value Primitive 19
5.2.10 Processing Remove Attribute Primitive 21
5.2.11 Processing Add Entry Primitive 21
5.2.12 Processing Remove Entry Primitive 22
5.2.13 Processing Move Entry Primitive 23
5.2.14 Processing Rename Entry Primitive 24
6. Security Considerations 25
7. Acknowledgements 26
8. References 26
9. Intellectual Property Notice 26
10. Copyright Notice 26
11. Authors' Address 27
12. Appendix A - Changes From Previous Draft 27
13. Appendix B - Open Issues 28
3. Introduction
Each DAP, LDAP or DSP operation successfully performed by a DSA is
decomposed into one or more simple timestamped replication
primitives. These primitives reflect the intended final state of an
Legg & Payne Expires 25 December 1999 [Page 2]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
update operation rather than the specific changes required to achieve
that state.
A DSA will receive replication primitives from its various agreement
partners according to the agreement schedules. Those primitives must
be reconciled with the current DSA contents and any previously
received primitives. In broad outline, received replication
primitives are compared to the timestamp information associated with
the directory data item being operated on. If the primitive has a
more recent timestamp a change in the directory contents is made
(that may involve only the revision of a timestamp). If the DSA has
other replication agreements then the primitive is retained for
forwarding at the appropriate time. If the primitive has an older
timestamp it is no longer relevant and is simply discarded.
The update reconciliation procedures are designed to produce a
consistent outcome at all participating DSAs regardless of the order
in which the primitives are received. The primitives can also be
safely replayed in the event that an exchange of replication
information with another DSA is interrupted. This greatly simplifies
the recovery mechanisms required in the replication protocol.
4. Model Extensions
This section describes the extensions to the data model required to
effect multiple master replication.
4.1 Unique Identifier
A Unique Identifier is associated with each entry in the global DIT.
This Unique Identifier must be globally unique for all time in the
Directory. This can be achieved by defining a unique DSA prefix for
each DSA and then ensuring that the suffix of the Unique Identifier
is locally unique.
Some pre-allocated global Unique Identifier values will be used to
indicate the root entry (eg. the value 0), and the Lost & Found
entry.
4.2 Timestamps & Existence
The timestamp for a replication primitive or directory data item is
in the form of a Change Sequence Number (CSN). The components of the
CSN are, from most significant to least significant, a time in
seconds, a change count, a Replica Identifier and a modification
number. Notionally a CSN is associated with an entry's Relative
Distinguished Name, the reference to its superior entry and each of
its attribute values (including the distinguished values), to record
Legg & Payne Expires 25 December 1999 [Page 3]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
the time of the most recent action on that part of the entry.
The entry itself has a CSN asserting the most recent time at which
the entry was added. An entry is permitted to be removed and then
re-added at one or more DSAs. In this context re-adding an entry
means reusing the Unique Identifier of a removed entry and does not
refer to the case of reusing the RDN of a removed entry. The reuse of
a Unique Identifier can arise by the explicit action of a directory
administrator to restore an entry that was mistakenly removed. The
mechanism by which an administrator adds an entry with a reused
Unique Identifier is outside the scope of the X.500 and LDAP
standards since the Unique Identifier of an entry is not a user
modifiable attribute. Note that from the perspective of a consumer
DSA of a partial area of replication an entry may appear to be
removed and added several times because modifications to the entry
change whether the entry satisfies the replication agreement
specification for the area of replication.
Additionally, a deletion record is kept for each of the recently
deleted entries, attributes, or attribute values. The deletion record
contains a CSN and asserts that the associated directory object no
longer existed at the particular time.
Each distinguished value may be in one of two states, present or not
present. The not present state comes about because a primitive has
attempted to remove the attribute value while it is distinguished.
The value remains pinned, i.e. not present, until the value becomes
non-distinguished by a later rename, when it will be removed.
4.3 Replication Log
Each DSA maintains a replication log that records the results of both
updates which occur locally due to update operations and also of
replication exchanges with other DSAs.
The replication log consists of a number of primitives. A single
update operation will result in one or more primitives being added to
the log. A replication exchange may result in many primitives being
added to the log.
DMRP has two categories of replication primitives: update primitives
and history primitives. The update primitives carry the changes
resulting from user updates to Directory data. The history primitives
are used when establishing new replication agreements and are
described in Section 5.4. At this time LDUP uses only the update
primitives. The representation of these primitives in LDUP
replication protocol exchanges is undefined at the time of writing.
Legg & Payne Expires 25 December 1999 [Page 4]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
Common to all update primitives is an entry identifier argument, uid,
that contains the Unique Identifier of the target entry of the
change, and a CSN argument, csn, to indicate the time of the change.
Additional arguments are present depending on the type of update
primitive.
The p-add-entry(uid, csn, superior, rdn) primitive is used to add a
new entry with minimal contents. It is represented in DMRP as the
addEntry choice within the UpdatePrimitive ASN.1 type. The superior
argument contains the Unique Identifier of the immediate superior
entry of the added entry. The rdn argument contains the Relative
Distinguished Name of the added entry.
The p-move-entry(uid, csn, superior) primitive is used to change the
immediate superior of an entry. It is represented in DMRP as the
moveEntry choice within UpdatePrimitive. The superior argument
contains the Unique Identifier of the new superior entry.
The p-rename-entry(uid, csn, rdn) primitive is used to change the
Relative Distinguished Name of an entry. It is represented in DMRP as
the renameEntry choice within UpdatePrimitive. The rdn argument
contains the new RDN for the entry.
The p-remove-entry(uid, csn) primitive is used to remove an entry. It
is represented in DMRP as the removeEntry choice within
UpdatePrimitive.
The p-add-attribute-value(uid, csn, type, value) primitive is used to
add a single attribute value to an entry. It is represented in DMRP
as the addValue choice within UpdatePrimitive. The type argument
contains the attribute type of the value and the value argument
contains the attribute value.
The p-remove-attribute-value(uid, csn, type, value) primitive is used
to remove a single attribute value from an entry. It is represented
in DMRP as the removeValue choice within UpdatePrimitive. The type
argument contains the attribute type of the value and the value
argument contains the attribute value.
The p-remove-attribute(uid, csn, type) primitive is used to remove
all values of an attribute from an entry. It is represented in DMRP
as the removeAttribute choice within UpdatePrimitive. The type
argument contains the attribute type to be removed.
These primitives reflect the intended final state of an update
operation rather than the specific changes required to achieve that
state.
Legg & Payne Expires 25 December 1999 [Page 5]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
4.4 Lost & Found
Each connected set of mastering DSAs have a Lost & Found entry
nominated. As a result of conflicting updates at two or more master
DSAs, an entry may be left with a reference to a non-existent
superior entry. Such an entry is called an orphaned entry. When this
situation arises, the DSA creates a glue entry for the missing
superior entry. This glue entry is made a subordinate of the Lost &
Found entry and the orphaned entry becomes a subordinate of the glue
superior entry (see Section 5.2.3). Entries that exist in the Lost &
Found subtree may still be modified by actions of the replication
protocol since entries are identified by Unique Identifiers in the
protocol, independent of their positioning in the global DIT.
Entries will also be explicitly moved to become immediate
subordinates of the Lost & Found entry to prevent the formation of a
loop in the superior-subordinate relationships in the DIT. This
situation can only arise through conflicting move entry operations at
two or more master DSAs.
Entries that exist under the Lost & Found entry may be returned to a
suitable position in the DIT by an administrator or user with
appropriate access rights.
5. Replication Procedures
The procedures defined in this section ensure the consistent and
correct application of the results of DAP, LDAP or DSP operations
across all multi-master replication DSAs.
5.1 Processing LDAP, DAP or DSP Operations on the DIT
A successful DAP, LDAP or DSP operation applied to a part of the DIT
subject to a replication agreement will produce one or more
replication primitives and zero, one or more deletion records. The
primitives and deletion records generated from an operation are
atomic with that operation. That is, either the operation succeeds,
primitives are added to the replication log and deletion records are
stored, or the operation fails, no primitives are added to the log
and no deletion records are stored. In all cases, all current error
conditions (i.e. reasons for rejecting an LDAP, DAP or DSP update
operation) remain.
All the primitives generated from an update operation must use the
same time, change count and Replica Identifier in their csn argument.
The modification number is permitted to vary but must be assigned
such that when the CSNs of the primitives of the operation are
compared to the CSNs of the primitives of any other operation they
Legg & Payne Expires 25 December 1999 [Page 6]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
are all strictly greater than or all strictly less than those other
CSNs (i.e. in a global CSN ordering of the primitives of all
operations the primitives of each operation must be contiguous in
that ordering). In order for the update to be consistently applied In
order for the update to be consistently applied when replicated to
other DSAs the CSNs on the corresponding primitives must generally be
greater than any pre-existing CSNs on the updated entry's contents.
It is expected that DSAs will normally use the current time according
to their system clocks in generating the CSNs for an operation.
However in an environment where DSA clocks are not necessarily
synchronized the current time may be older than existing CSNs on
entry contents. The constraints the primitives' CSNs must satisfy
with respect to pre-existing CSNs on entry data are covered in the
sections on each type of update operation. The current LDUP
architecture draft [LDUP Model] requires client update operations to
be rejected if the current time does not satisfy the contraints on
the generation of the CSNs. DMRP allows a DSA to generate CSNs in
advance of its current time to satisfy the constraints and proceed
with the update.
The LDUP Update Vector mechanism imposes the constraint that the CSN
generated for an update operation must also be greater than the
highest CSN generated by the DSA that has already been seen by any
other DSA. An implementation that generates successively greater CSNs
for each operation will satisfy this constraint.
DMRP imposes the constraint that the CSN generated for an update
operation must also be greater than or equal to the current Local
Oldest Time at the DSA processing the update. Note that the Local
Oldest Time is always equal to or older than the current system clock
time.
The uid argument of each of the primitives generated from an update
operation contains the Unique Identifier of the target entry of the
operation. In the case of adding a new entry, the Unique Identifier
for the entry is allocated by the DSA in the course of processing the
operation.
The following sections describe the actions carried out in processing
each particular type of update operation.
5.1.1 Add Entry
The LDAP Add operation or DAP addEntry operation is used to add a
leaf entry to the DIT. Should the request succeed, a Unique
Identifier will have been generated for the created entry, and a p-
add-entry primitive and zero, one or more p-add-attribute-value
primitives will be generated and placed in the replication log.
Legg & Payne Expires 25 December 1999 [Page 7]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
The immediate superior entry for the added entry is determined during
name resolution for the add operation. The superior argument of the
p-add-entry primitive contains the Unique Identifier of this
immediate superior entry.
The rdn argument of the p-add-entry primitive contains the Relative
Distinguished Name of the created entry. There are no separate
primitives generated for the distinguished values of the entry. A
p-add-attribute-value primitive is generated for each of the non-
distinguished attribute values contained in the created entry. This
includes any operational attributes automatically generated by the
DSA.
The CSN generated for the p-add-entry primitive becomes the CSN for
the entry. Each distinguished and non-distinguished value added to
the entry by the add entry operation is timestamped with this same
CSN.
The Unique Identifier generated for an entry created by a user
request is required to be globally unique for all time so there
cannot be a pre-existing entry deletion record for the same Unique
Identifier. However it is recognized that, in practice, Directory
administrators may need to restore a deleted entry using its original
Unique Identifier (the mechanism used to achieve this is undefined
and outside the scope of this specification). In this case the CSN
for the p-add-entry primitive must be generated such that it is
greater than or equal to the CSN of any existing entry, attribute or
value deletion records and greater than any of the CSNs contained in
an existing glue entry for the same Unique Identifier.
5.1.2 Remove Entry
The LDAP Delete operation or DAP removeEntry operation is used to
remove a leaf entry from the DIT. Should the request succeed, a p-
remove-entry primitive is generated and placed in the replication
log.
An entry deletion record is stored with the same Unique Identifier
and CSN as the p-remove-entry primitive.
The CSN for the p-remove-entry primitive must be generated such that
it is greater than the CSN of the target entry.
5.1.3 Modify Entry
The LDAP Modify operation (ModifyRequest) or DAP modifyEntry
operation is used to perform a series of one or more modifications to
an entry. Should the request succeed, one or more p-add-attribute-
Legg & Payne Expires 25 December 1999 [Page 8]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
value, p-remove-attribute-value or p-remove-attribute primitives are
generated and placed in the replication log.
There are two approaches to generating CSNs corresponding to each
element of the changes argument of modifyEntry or modification
argument of ModifyRequest
5.1.3.1 Ascending Modification Numbers
As the sequence of modifications in the modify operation are applied
in order, the primitives they generate are assigned CSNs with
monotonically increasing modification numbers. The modification
numbers need not be consecutive.
The modifications described by the changes argument of the
modifyEntry operation have the following effects:
a) The addAttribute and addValues alternatives generate a p-add-
attribute-value primitive for each of the added attribute values.
b) The removeAttribute alternative generates a p-remove-attribute
primitive for the removed attribute type.
c) The removeValues alternative generates a p-remove-attribute-
value primitive for each of the removed values.
d) The alterValues alternative first generates a p-remove-
attribute-value primitive for each of the old values. Secondly, a
p-add-attribute-value primitive is generated for each of the new
values.
e) The resetValues alternative generates a p-remove-attribute-
value primitive for each value actually removed.
The modifications described by the modification argument of the LDAP
ModifyRequest have the following effects:
a) The add alternative generates a p-add-attribute-value primitive
for each of the added attribute values.
b) The delete alternative with no listed values generates a p-
remove-attribute primitive for the removed attribute type.
c) The delete alternative with listed values generates a p-
remove-attribute-value primitive for each of the removed values.
d) The replace alternative first generates a p-remove-attribute
primitive for the removed attribute type. A p-add-attribute-value
Legg & Payne Expires 25 December 1999 [Page 9]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
primitive is then generated for each of the added values.
In each case the generated primitives are added to the replication
log. Additionally, a value deletion record is stored for each p-
remove-attribute-value primitive and an attribute deletion record is
stored for each p-remove-attribute primitive.
The CSN for the operation must be generated such that it is greater
than the CSN of any pre-existing attribute value that is removed,
greater than or equal to the CSN of any pre-existing deletion record
relevant to an added attribute value and greater than or equal to the
CSN of the entry. Each attribute value added to the entry is
timestamped with the same CSN as the associated p-add-attribute-value
primitive.
5.1.3.2 Fixed Modification Numbers
Unlike the changes argument of modifyEntry or the modification
argument of ModifyRequest the primitives generated from the request
under the fixed modification number scheme are not ordered. Instead
they reflect the net change to the entry being modified.
As the sequence of modifications in the modify operation are applied
in order, the collection of primitives for the operation is
progressively revised. Initially the set of primitives is empty.
Primitives will be added to the collection, but not immediately to
the replication log, and may be removed by later modifications in the
sequence of modifications for the operation.
The modifications described by the changes argument of the
modifyEntry operation have the following effects on the collection of
primitives:
a) The addAttribute and addValues alternatives generate a p-add-
attribute-value primitive for each of the added attribute values.
Any p-remove-attribute-value primitive generated so far with the
same attribute type and value as one of these p-add-attribute-
value primitives is discarded.
b) The removeAttribute alternative generates a p-remove-attribute
primitive for the removed attribute type. Any p-add-attribute-
value, p-remove-attribute-value or p-remove-attribute primitives
generated so far for the same attribute type are discarded.
c) The removeValues alternative generates a p-remove-attribute-
value primitive for each of the removed values. Any p-add-
attribute-value primitive generated so far with the same attribute
type and value as one of these p-remove-attribute-value primitives
Legg & Payne Expires 25 December 1999 [Page 10]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
is discarded.
d) The alterValues alternative first generates a p-remove-
attribute-value primitive for each of the old values. Any p-add-
attribute-value primitive generated so far with the same attribute
type and value as one of these p-remove-attribute-value primitives
is discarded. Secondly, a p-add-attribute-value primitive is
generated for each of the new values. Any p-remove-attribute-value
primitive generated so far (including those generated in the first
step) with the same attribute type and value as one of these p-
add-attribute-value primitives is discarded.
e) The resetValues alternative generates a p-remove-attribute-
value primitive for each value actually removed. Any p-add-
attribute-value primitive generated so far with the same attribute
type and value as one of these p-remove-attribute-value primitives
is discarded.
The modifications described by the modification argument of the LDAP
ModifyRequest have the following effects on the collection of
primitives:
a) The add alternative generates a p-add-attribute-value primitive
for each of the added attribute values. Any p-remove-attribute-
value primitive generated so far with the same attribute type and
value as one of these p-add-attribute-value primitives is
discarded.
b) The delete alternative with no listed values generates a p-
remove-attribute primitive for the removed attribute type. Any p-
add-attribute-value, p-remove-attribute-value or p-remove-
attribute primitives generated so far for the same attribute type
are discarded.
c) The delete alternative with listed values generates a p-
remove-attribute-value primitive for each of the removed values.
Any p-add-attribute-value primitive generated so far with the same
attribute type and value as one of these p-remove-attribute-value
primitives is discarded.
d) The replace alternative first generates a p-remove-attribute
primitive for the removed attribute type, and any p-add-
attribute-value, p-remove-attribute-value or p-remove-attribute
primitives generated so far for the same attribute type are
discarded. A p-add-attribute-value primitive is then generated for
each of the added values.
After all the modifications of the operation are applied to the
Legg & Payne Expires 25 December 1999 [Page 11]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
entry, all of the remaining primitives are added to the replication
log. Additionally, a value deletion record is stored for each
remaining p-remove-attribute-value primitive and an attribute
deletion record is stored for each remaining p-remove-attribute
primitive. Each p-add-attribute-value supersedes a value deletion
record (see Section 5.2.2) for the same entry, attribute type and
attribute value.
The CSN for the operation must be generated such that it is greater
than the CSN of any pre-existing attribute value that is removed,
greater than or equal to the CSN of any pre-existing deletion record
relevant to an added attribute value and greater than or equal to the
CSN of the entry. Each attribute value added to the entry is
timestamped with the CSN of the operation.
5.1.4 Modify DN
The LDAP Modify DN operation and DAP modifyDN operation are used to
change the Relative Distinguished Name of an entry and/or to move an
entry to a new superior in the DIT.
If the entry is moved to a new superior in the DIT then a p-move-
entry primitive is generated and added to the replication log. The
superior argument of the p-move-entry primitive contains the Unique
Identifier of the new superior entry. The CSN generated for the p-
move-entry primitive must be greater than the previous CSN for the
entry's superior reference. The entry's superior reference is
timestamped with the primitive's CSN.
If the entry's RDN is changed then a p-rename-entry primitive is
generated and added to the replication log. The rdn argument contains
the new RDN of the entry. The CSN generated for the p-rename-entry
primitive must be greater than the previous CSN for the entry's RDN.
The entry's RDN is timestamped with the primitive's CSN.
A p-remove-attribute-value primitive is generated for each of the
formally distinguished attribute values removed from the entry as a
consequence of the deleteOldRDN (modifyDN) flag or deleteoldrdn
(ModifyDNRequest) flag being set. A value deletion record is stored
for each removed value.
5.2 Processing Replication Primitives on the DIT
Each replication primitive received from another DSA is processed
against the DIT.
The CSN on an entry records the time of the latest p-add-entry
primitive for the Unique Identifier. In normal circumstances there
Legg & Payne Expires 25 December 1999 [Page 12]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
will only ever be one p-add-entry primitive associated with an entry.
The entry CSN may be discarded when it becomes eligible to be purged
(according to the Purge Vector in LDUP, or the Oldest Time in DMRP).
The remainder of this section defines some commonly used sub-
procedures and the algorithms for processing each of the primitives.
Components of primitives, entries, attributes and values are
referenced with the . operator. In particular the notation X.csn
refers to the CSN of the directory object X. The operators, < and >
when applied to CSNs, use the convention of CSNs becoming greater
with the progression of time, so older CSNs are less than younger
CSNs. In the case where the CSN for object X has been discarded
through the purging mechanism, X.csn is assumed to have the least
possible CSN value. In some of the procedures a CSN will be
explicitly purged. An implementation may instead keep the CSN but set
it to some value that is old enough for it to be eligible for purging
(e.g. the least possible CSN value) without affecting the correctness
of the procedures.
5.2.1 Propagating Primitives
Under DMRP, if the processing of a primitive causes some local change
to the directory data that primitive must be propagated to other
DSAs. The Propagate procedure is called where necessary to place such
a primitive into the replication log so that it will be sent to other
DSAs. The propagated primitive does not need to be sent back to the
DSA from which it was received, nor does it need to be sent to a DSA
that has the same Replica Identifier as the primitive's CSN. If this
leaves no other DSAs to which the primitive must be sent then the
primitive is discarded.
Under LDUP, all received primitives are put in the replication log
and the Update Vector from the consumer DSA is used to decide what
primitives are to be propagated. The Propagate procedure is ignored
in this case.
The single parameter to the Propagate procedure is the primitive to
be propagated.
Any primitive placed in the replication log to be sent to some other
DSA potentially supersedes (obsoletes) other unsent primitives
already in the log. An implementation may choose to remove some or
all of the superseded primitives.
The p-add-attribute-value primitive supersedes a p-remove-attribute-
value primitive for the same entry, attribute type, attribute value
and equal or older CSN. It supersedes another p-add-attribute-value
primitive for the same entry, attribute type, attribute value and
Legg & Payne Expires 25 December 1999 [Page 13]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
older CSN.
The p-remove-attribute-value primitive supersedes a p-add-attribute-
value primitive for the same entry, attribute type, attribute value
and older CSN. It supersedes another p-remove-attribute-value
primitive for the same entry, attribute type, attribute value and
equal or older CSN.
The p-remove-attribute primitive supersedes a p-add-attribute-value
primitive for the same entry, attribute type and older CSN. It
supersedes a p-remove-attribute-value or another p-remove-attribute
primitive for the same entry, attribute type and equal or older CSN.
The p-remove-entry primitive supersedes a p-add-attribute-value, p-
add-entry, p-move-entry or p-rename-entry primitive for the same
entry and older CSN. It supersedes a p-remove-attribute-value or p-
remove-attribute or another p-remove-entry primitive for the same
entry and equal or older CSN.
The p-move-entry primitive supersedes another p-move-entry primitive
for the same entry and older CSN.
5.2.2 Saving Deletion Records
It is necessary for a DSA to remember that some entry, attribute or
attribute value has been deleted, for a period after the processing
of the update operation or primitive causing the deletion. These
records are called deletion records in the sections that follow and
are of three kinds: entry deletion records, attribute deletion
records and value deletion records.
Value deletion records result from, and have the same parameters as,
the p-remove-attribute-value primitive. The StoreValueDeletion
procedure creates a value deletion record from the actual arguments
and stores it for later access by the various primitive processing
procedures. When an attribute value is added to an entry, a value
deletion record for the same entry, attribute type and value, and
with an older CSN, may be discarded.
Attribute deletion records result from, and have the same parameters
as, the p-remove-attribute primitive. The StoreAttributeDeletion
procedure creates an attribute deletion record from the actual
arguments and stores it for later access. When an attribute deletion
record is stored any value deletion records for the same entry and
attribute type, and with equal or older CSNs, may be discarded.
Entry deletion records result from, and have the same parameters as,
the p-remove-entry primitive. The StoreEntryDeletion procedure
Legg & Payne Expires 25 December 1999 [Page 14]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
creates an entry deletion record from the actual arguments and stores
it for later access. When an entry deletion record is stored any
value deletion records and attribute deletion records for the same
entry, and with equal or older CSNs, may be discarded.
Since the deletion records have the same components as their
associated remove primitives an implementation may choose to use the
same internal structures for both.
5.2.3 Glue Entries
Entries are permitted to be re-added and this can lead to situations
where applicable primitives are received in the period after an entry
is removed but before the arrival of the notification of it being
re-added. In these cases a glue entry is created for the Unique
Identifier to preserve relevant updates in the event that a p-add-
entry primitive with an older CSN is later received for the same
entry. A glue entry is upgraded to a normal entry by a subsequent p-
add-entry primitive.
A glue entry with no subordinate entries and containing only CSNs (on
itself or its component parts) that are eligible to be purged
(according to the Purge Vector in LDUP, or the Oldest Time in DMRP)
may be removed. A glue entry is discarded if its contents are
completely superseded by another p-remove-entry primitive.
The CreateGlueEntry function is called when required to create a glue
entry as a subordinate of Lost & Found. CreateGlueEntry takes a
single parameter which is the Unique Identifier for the glue entry.
The Unique Identifier also becomes the RDN for the glue entry. No
CSNs are associated with the entry, the entry's superior reference,
or the entry's name (or equivalently they are set to the least
possible CSN value).
5.2.4 Generating Change Sequence Numbers
There are a number of circumstances where conflicts arise in the
processing of a replication primitive. It is necessary in these cases
for the DSA processing the primitives to emit additional primitives
to ensure that all other DSAs reach the same consistent state. The
GenerateNextCSN function is used to obtain a CSN for one of these
additional primitives.
As is the case for primitives generated from DAP, DSP or LDAP
operations a CSN is typically generated from the current clock time
of the DSA. The conditions imposed for the correct operation of the
LDUP Update Vector or DMRP Oldest Time mechanism must be satisified.
For DMRP, the generated CSN must be greater than the current Local
Legg & Payne Expires 25 December 1999 [Page 15]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
Oldest Time for the DSA.
GenerateNextCSN takes a single CSN parameter. In addition to the
preceding conditions the CSN generated by the function must be
greater than this parameter. Since the CSN parameter passed to
GenerateNextCSN is always an actual CSN from some directory object
stored in the local DSA, an implementation may choose to allocate
CSNs from an incrementing internal CSN register that is reset after
each replication session to a value greater than the largest CSN seen
so far, and thereby be safely able to disregard the parameter to
GenerateNextCSN.
5.2.5 Comparison of Attribute Values
Values in primitives, in deletion records or in entries are compared
using the equality matching rule for the associated attribute type
where that type is permitted to be multi-valued. This means that two
values that are considered equal may nonetheless have minor
differences. For example, two commonName values may be equal, but use
different letter case and have different numbers of leading or
trailing spaces. Whenever a CSN for some value is refreshed the value
is also refreshed using the exact value from the primitive so that
all DSAs use exactly the same representation for the value.
Compared values for a single-valued attribute type are all considered
to be equal even though they may be significantly different according
to that attribute type's equality matching rule. In effect the
equality operator, '=', in the following procedures is
unconditionally true when used to compare values of a single-valued
attribute type. Whenever a CSN for the value of a single-valued
attribute is refreshed the value is also refreshed using the value
from the primitive. One significant consequence is that an entry
whose RDN contains a value of a single-valued attribute type is
effectively renamed by a p-add-attribute-value primitive with a more
recent value for the attribute type.
A value in an entry that is replaced by the exact representation from
a primitive retains its distinguished or non-distinguished status.
This includes replaced values of single-valued attribute types.
5.2.6 Renaming Entries
The primitives p-add-entry and p-rename-entry contain common elements
that are applied to the Relative Distinguished Name of an entry in
the same way. This common processing is described in the RenameEntry
procedure. The parameters to this procedure are the entry, E, and the
p-add-entry or p-rename-entry primitive specifying the new RDN. The
procedure assumes that the entry does not currently contain any
Legg & Payne Expires 25 December 1999 [Page 16]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
distinguished values. It is the responsibility of the calling
procedure to first reset any pre-existing distinguished values to
non-distinguished. The procedure then resets the CSNs and sets the
distinguished flags for existing values and adds distinguished values
if necessary. The CSN for the entry's RDN, as distinct from the CSNs
on each of the distinguished values making up the RDN, is also set.
RenameEntry(E, P)
{
FOREACH AttributeTypeAndValue, N, in P.rdn
IF there exists an attribute value, V, in E of type N.type
where V = N.value
{
IF P.csn > V.csn
{
replace V with N.value if they are not identical
V.csn := P.csn
}
set V to distinguished-present
}
ELSE
{
V := N.value
add V to E
IF a value deletion record (uid, type, value, csn1) exists
where (uid = P.uid AND type = N.type AND
value = N.value AND csn1 > P.csn)
{
IF an attribute deletion record (uid, type, csn2) exists
where (uid = P.uid AND type = N.type AND
csn2 > P.csn AND csn2 > csn1)
V.csn := csn2
ELSE
V.csn := csn1
set V to distinguished-not-present
}
ELSE
{
IF an attribute deletion record (uid, type, csn2) exists
where (uid = P.uid AND type = N.type AND
csn2 > P.csn)
{
V.csn := csn2
set V to distinguished-not-present
}
ELSE
{
V.csn := P.csn
Legg & Payne Expires 25 December 1999 [Page 17]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
set V to distinguished-present
}
}
}
E.rdn.csn := P.csn
}
5.2.7 Name Conflict Resolution
Independent changes at two or more DSAs can lead to the situation of
two distinct entries having the same name. The procedure,
CheckUniqueness(E) takes an entry and determines whether it is
uniquely named. If not, it disambiguates the entries by adding the
Unique Identifier of each of the conflicting entries to their own
RDN.
CheckUniqueness(E)
{
IF the Distinguished Name of E is not unique
FOREACH entry, C, with the same DN as E, including E itself
{
C.rdn.csn := GenerateNextCSN(C.rdn.csn)
set C.uid to distinguished-present
FOREACH distinguished attribute value, V, in C
IF C.rdn.csn >= V.csn
{
V.csn := C.rdn.csn
IF V is distinguished-not-present
set V to distinguished-present
}
make p-rename-entry(C.uid, C.rdn, C.rdn.csn)
}
}
5.2.8 Processing Add Attribute Value Primitive
This section describes the algorithm for processing the p-add-
attribute-value (P.uid, P.type, P.value, P.csn) primitive, which is
responsible for adding a single attribute value.
IF no value deletion record (uid, type, value, csn) exists where
(uid = P.uid AND type = P.type
AND value = P.value AND csn > P.csn)
AND no attribute deletion record (uid, type, csn) exists where
Legg & Payne Expires 25 December 1999 [Page 18]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
(uid = P.uid and type = P.type AND csn > P.csn)
AND no entry deletion record (uid, csn) exists where
(uid = P.uid AND csn > P.csn)
{
IF entry, E, with uid = P.uid does not exist
E := CreateGlueEntry(P.uid)
IF P.csn >= E.csn
IF attribute value V, of type P.type
where V = P.value exists in E
{
IF V is distinguished-not-present
{
IF P.csn >= V.csn
{
V.csn := P.csn
replace V with P.value if they are not identical
set V to distinguished-present
IF P.type is a single-valued attribute type
CheckUniqueness(E)
Propagate(P)
}
}
ELSE IF P.csn > V.csn
{
V.csn := P.csn
replace V with P.value if they are not identical
IF V is distinguished
AND P.type is a single-valued attribute type
CheckUniqueness(E)
Propagate(P)
}
}
ELSE
{
V := P.value
Add V to E as a non-distinguished attribute value
V.csn := P.csn
Propagate(P)
}
}
5.2.9 Processing Remove Attribute Value Primitive
This section describes the algorithm for processing the p-remove-
attribute-value (P.uid, P. type, P.value, P.csn) primitive, which is
responsible for removing a single attribute value. A value that is
distinguished is tagged as distinguished-not-present rather than
Legg & Payne Expires 25 December 1999 [Page 19]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
being immediately removed. Such a value will be physically removed
when it becomes non-distinguished.
IF no value deletion record (uid, type, value, csn) exists
where (uid = P.uid AND type = P.type AND
value = P.value AND csn >= P.csn)
AND
no attribute deletion record (uid, type, csn) exists
where (uid = P.uid AND type = P.type AND csn >= P.csn)
AND
no entry deletion record (uid, csn) exists
where (uid = P.uid AND csn >= P.csn)
IF entry, E, with uid = P.uid exists
{
IF P.csn > E.csn
{
IF attribute value, V, of P.type
where V = P.value, exists in E
{
IF P.csn > V.csn
IF V is distinguished-present
{
set V to distinguished-not-present
V.csn := P.csn
}
ELSE IF V is distinguished-not-present
V.csn := P.csn
ELSE
remove value V
}
StoreValueDeletion (P.uid, P.type, P.value, P.csn)
Propagate(P)
}
}
ELSE
{
StoreValueDeletion (P.uid, P.type, P.value, P.csn)
Propagate(P)
}
The presence of a younger deletion record for the entry, attribute or
value provides a convenient test for whether the p-remove-attribute-
value primitive needs to be processed at all. If the value exists to
be removed then there cannot be a deletion record affecting it that
has a younger CSN. If there is a younger deletion record than the
primitive then there cannot be an older value to remove.
Legg & Payne Expires 25 December 1999 [Page 20]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
5.2.10 Processing Remove Attribute Primitive
This section describes the algorithm for processing the p-remove-
attribute (P.uid, P.type, P.csn) primitive, which is responsible for
removing all attribute values of P.type. Values that are
distinguished are tagged as distinguished-not-present rather than
being immediately removed. Such values will be physically removed
when they become non-distinguished.
IF no attribute deletion record (uid, type, csn) exists
where (uid = P.uid AND type = P.type AND csn >= P.csn)
AND no entry deletion record (uid, csn) exists where
(uid = P.uid AND csn >= P.csn)
IF entry, E, with uid = P.uid exists
{
IF P.csn > E.csn
{
FOREACH attribute value, V, of type P.type in E (if any)
IF P.csn > V.csn
{
IF V is distinguished-present
{
set V to distinguished-not-present
V.csn := P.csn
}
ELSE IF V is distinguished-not-present
V.csn := P.csn
ELSE
remove value V
}
StoreAttributeDeletion (P.uid, P.type, P.csn)
Propagate(P)
}
}
ELSE
{
StoreAttributeDeletion (P.uid, P.type, P.csn)
Propagate(P)
}
5.2.11 Processing Add Entry Primitive
This section describes the algorithm for processing the p-add-entry
(P.uid, P.superior, P.rdn, P.csn) primitive, which is responsible for
adding an entry.
IF no entry deletion record (uid, csn) exists where
Legg & Payne Expires 25 December 1999 [Page 21]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
(uid = P.uid AND csn > P.csn)
IF entry, E, with uid = P.uid exists
{
IF P.csn > E.csn
{
E.csn := P.csn
FOREACH attribute value, V, in E
IF V.csn < P.csn
remove value V
process P according to
p-rename-entry(P.uid, P.rdn, P.csn)
except do not propagate P
process P according to
p-move-entry(P.uid, P.superior, P.csn)
except do not propagate P
Propagate(P)
}
}
ELSE
{
create entry E
E.csn := P.csn
E.uid := P.uid
E.uid.csn :=P.csn
E.rdn.csn :=P.csn
RenameEntry(E, P)
IF an entry with uid = P.superior does not exist
CreateGlueEntry(P.superior)
E.superior = P.superior
E.superior.csn := P.csn
CheckUniqueness(E)
Propagate(P)
}
5.2.12 Processing Remove Entry Primitive
This section describes the algorithm for processing the p-remove-
entry (P.uid, P.csn) primitive, which is responsible for removing an
entry. If the target entry has attribute values with CSNs greater
than the primitive's CSN, a superior reference with a greater CSN, or
if it has any subordinate entries, it becomes a glue entry instead of
being removed. Unless it has a CSN for its superior reference that
is greater than the CSN of the p-remove-entry it is also moved to
Lost & Found.
IF no entry deletion record (uid, csn) exists
where (uid = P.uid AND csn >= P.csn)
Legg & Payne Expires 25 December 1999 [Page 22]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
IF entry, E, with uid = P.uid exists
{
IF P.csn > E.csn
{
IF E.superior.csn >= P.csn
OR any value, V, with csn >= P.csn exists
OR E has subordinates
{
make E a glue entry
purge E.csn
IF E.superior.csn < P.csn
{
E.superior := LOST_AND_FOUND
purge E.superior.csn
}
IF E.rdn.csn < P.csn
purge E.rdn.csn
FOREACH attribute value, V, in E
IF V.csn < P.csn
remove value V
CheckUniqueness(E)
}
ELSE
remove entry E
StoreEntryDeletion (P.uid, P.csn)
Propagate(P)
}
}
ELSE
{
StoreEntryDeletion (P.uid, P.csn)
Propagate(P)
}
5.2.13 Processing Move Entry Primitive
This section describes the algorithm for processing the p-move-entry
(P.uid, P.superior, P.csn) primitive, which is responsible for
moving an entry. If the new superior specified by the primitive does
not exist or is a direct or indirect subordinate of the entry being
moved then the entry is moved to Lost & Found instead.
IF no entry deletion record (uid, csn) exists
where (uid = P.uid AND csn > P.csn)
{
IF entry, E, with uid = P.uid does not exist
E := CreateGlueEntry(P.uid)
Legg & Payne Expires 25 December 1999 [Page 23]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
IF P.csn > E.superior.csn
{
IF entry, S, with uid = P.superior does not exist
S := CreateGlueEntry(P.superior)
IF S is not a subordinate of E
{
E.superior := P.superior
E.superior.csn = P.csn
Propagate(P)
}
ELSE
{
E.superior := LOST_AND_FOUND;
E.superior.csn := GenerateNextCSN(P.csn)
make p-move-entry(P.uid, LOST_AND_FOUND, E.superior.csn)
(*Note 1)
}
CheckUniqueness(E)
}
}
*Note 1 : making a primitive means to create a new primitive which
then needs to be propagated to all DSAs directly connected to this
DSA via a replication agreement.
5.2.14 Processing Rename Entry Primitive
This section describes the algorithm for processing the p-rename-
entry (P.uid, P.rdn, P.csn) primitive, which changes the Relative
Distinguished Name of an entry.
IF no entry deletion record (uid, csn) exists
where (uid = P.uid AND csn >= P.csn)
{
IF entry, E, with uid = P.uid does not exist
E := CreateGlueEntry(P.uid)
IF P.csn > E.rdn.csn
{
/* Clearing previously distinguished values */
FOREACH distinguished attribute value, V, in entry E
IF V is distinguished-not-present
remove value V
ELSE
set V to non-distinguished
RenameEntry(E, P)
CheckUniqueness(E)
Propagate(P)
Legg & Payne Expires 25 December 1999 [Page 24]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
}
ELSE
/* This primitive is older than the current name,
but may contain implicit add attribute values */
{
altered := false
FOREACH AttributeTypeAndValue, N, in P.rdn
{
IF there exists an attribute value, V, in E of type
N.type AND V = N.value
{
IF P.csn > V.csn
{
replace V with N.value if they are not identical
V.csn := P.csn
altered := true
}
}
ELSE
/* If the primitive had arrived in correct time order,
it would have caused a value to be added that would
now be non-distinguished */
{
IF no value deletion record (uid, type, value, csn)
exists where (uid = P.uid AND type = N.type AND
value = N.value AND csn > P.csn)
AND
no attribute deletion record (uid, type, csn)
exists where (uid = P.uid AND type = N.type AND
csn > P.csn)
{
V := N.value
Add V to E
V.csn := P.csn
altered := true
}
}
}
IF altered is true
Propagate(P)
}
}
6. Security Considerations
[To be supplied]
Legg & Payne Expires 25 December 1999 [Page 25]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
7. Acknowledgements
The authors would like to thank Suellen Faulks, Tony Robertson and
Mark Ennis from Telstra Research Laboratories who contributed to the
design and verification of the procedures described in this document.
The authors would also like to thank the members of the LDUP
architecture group for their input into the refinement of the design.
8. References
[LDUP Model] - E. Reed, "LDUP Replication Architecture", Internet
Draft, draft-merrells-ldup-model-01.txt, November 1998.
[N11034] - ITU-T SC6 Working document N11034.
[BCP-11] - R. Hovey, S. Bradner, "The Organizations Involved in the
IETF Standards Process", BCP 11, RFC 2028, October 1996.
9. Intellectual Property Notice
The IETF takes no position regarding the validity or scope of any
intellectual property or other rights that might be claimed to
pertain to the implementation or use of the technology described in
this document or the extent to which any license under such rights
might or might not be available; neither does it represent that it
has made any effort to identify any such rights. Information on the
IETF's procedures with respect to rights in standards-track and
standards-related documentation can be found in BCP-11. [BCP-11]
Copies of claims of rights made available for publication and any
assurances of licenses to be made available, or the result of an
attempt made to obtain a general license or permission for the use of
such proprietary rights by implementors or users of this
specification can be obtained from the IETF Secretariat.
The IETF invites any interested party to bring to its attention any
copyrights, patents or patent applications, or other proprietary
rights which may cover technology that may be required to practice
this standard. Please address the information to the IETF Executive
Director.
10. Copyright Notice
Copyright (C) The Internet Society (1999). All Rights Reserved.
Legg & Payne Expires 25 December 1999 [Page 26]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
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.
11. Authors' Address
Steven Legg
Telstra Research Laboratories
770 Blackburn Road
Clayton, Victoria 3168
AUSTRALIA
Phone: +61 3 9253 6771
Fax: +61 3 9253 6485
EMail: s.legg@trl.telstra.com.au
Alison Payne
PricewaterhouseCoopers
St Jakobs Strasse 25
CH-4002 Basel
SWITZERLAND
Phone: +41-79-458 4177
EMail: alison.b.payne@ch.pwcglobal.com
12. Appendix A - Changes From Previous Draft
Legg & Payne Expires 25 December 1999 [Page 27]
INTERNET-DRAFT LDUP Update Reconciliation Procedures June 25, 1999
Some of the terminology has been changed to better align with the
terminology used in the LDUP architecture draft.
Descriptions on the usage of CSNs have been revised to account for
the extra modification number component.
The semantics of re-added entries has been simplified so that only
changes after the latest re-add are preserved instead of all those
after the earliest re-add. This eliminates the need for Addition CSNs
in the entry. It is anticipated that new replication primitives will
be introduced to manage entries that come and go from partial
replicas instead of using p-add-entry and p-remove-entry.
Orphaned entries are no longer moved directly to Lost & Found.
Instead a glue entry is created in Lost & Found for the missing
superior and the orphaned entry becomes a subordinate of that. This
change eliminates the need for explicit propagated primitives for
moving orphaned entries to Lost & Found.
Glue entries have also been used as the mechanism for saving
primitives. There are no longer any references to saved primitives
though the functionality is still present.
The procedures for processing received replication primitives have
been rearranged to follow a more consistent pattern where the
presence of deletion records is tested first.
13. Appendix B - Open Issues
References to a "replication log" remain in the draft. The relevant
sections will eventually be rewritten in a manner that does not
prejudice either state-based or log-based implementations.
The precise location of the Lost & Found entry has not yet been
decided.
Extensions to the alogorithms to properly deal with partial replicas
are still to be decided.
Legg & Payne Expires 25 December 1999 [Page 28]
| PAFTECH AB 2003-2026 | 2026-04-24 02:51:56 |