+
+
+
+
+
+
INTERNET-DRAFT S. Legg
-draft-ietf-ldup-urp-02.txt Telstra
+draft-ietf-ldup-urp-03.txt Adacel Technologies
A. Payne
- PricewaterhouseCoopers
- October 22, 1999
+ Telstra
+ June 29, 2000
LDUP Update Reconciliation Procedures
- Copyright (C) The Internet Society (1999). All Rights Reserved.
+ Copyright (C) The Internet Society (2000). All Rights Reserved.
Status of this Memo
of this document is unlimited. Comments should be sent to the LDUP
Replication mailing list <ldup@imc.org> or to the authors.
- This Internet-Draft expires on 22 April 2000.
+ This Internet-Draft expires on 29 December 2000.
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.
-
-
-
-
+ This document describes the procedures used by LDAP [LDAPv3] or X.500
+ [X500] directory servers to reconcile updates performed by
+ autonomously operating directory servers in a distributed, replicated
+ directory service.
+ The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
+ "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
-Legg & Payne Expires 22 April 2000 [Page 1]
+Legg & Payne Expires 29 December 2000 [Page 1]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ document are to be interpreted as described in RFC 2119 [RFC2119].
2. Table of Contents
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 7
- 5.1.3 Modify Entry 7
- 5.1.4 Modify DN 9
- 5.2 Generating Replication Primitives 9
- 5.3 Processing Replication Primitives on the DIT 11
- 5.3.1 Saving Deletion Records 12
- 5.3.2 Glue Entries 13
- 5.3.3 Generating Change Sequence Numbers 13
- 5.3.4 Comparison of Attribute Values 14
- 5.3.5 Entry Naming 14
- 5.3.6 Processing Add Attribute Value Primitive 17
- 5.3.7 Processing Remove Attribute Value Primitive 17
- 5.3.8 Processing Remove Attribute Primitive 19
- 5.3.9 Processing Add Entry Primitive 19
- 5.3.10 Processing Remove Entry Primitive 20
- 5.3.11 Processing Move Entry Primitive 21
- 5.3.12 Processing Rename Entry Primitive 22
- 6. Security Considerations 23
- 7. Acknowledgements 23
- 8. References 23
- 9. Intellectual Property Notice 23
- 10. Copyright Notice 24
- 11. Authors' Address 25
- 12. Appendix A - Changes From Previous Drafts 25
- 12.1 Changes in Draft 01 25
- 12.2 Changes in Draft 02 26
- 13. Appendix B - Open Issues 26
+ 5.1.2 Remove Entry 8
+ 5.1.3 Modify Entry 8
+ 5.1.4 Modify DN 10
+ 5.2 Generating Replication Primitives 10
+ 5.3 Processing Replication Primitives on the DIT 12
+ 5.3.1 Saving Deletion Records 13
+ 5.3.2 Glue Entries 14
+ 5.3.3 Generating Change Sequence Numbers 14
+ 5.3.4 Comparison of Attribute Values 15
+ 5.3.5 Entry Naming 15
+ 5.3.6 Processing Add Attribute Value Primitive 18
+ 5.3.7 Processing Remove Attribute Value Primitive 19
+ 5.3.8 Processing Remove Attribute Primitive 20
+ 5.3.9 Processing Add Entry Primitive 20
+ 5.3.10 Processing Remove Entry Primitive 21
+ 5.3.11 Processing Move Entry Primitive 22
+ 5.3.12 Processing Rename Entry Primitive 23
+ 6. Security Considerations 24
+ 7. Acknowledgements 25
+ 8. References 25
+ 9. Intellectual Property Notice 26
+ 10. Copyright Notice 26
+ 11. Authors' Addresses 27
3. Introduction
- Each DAP, LDAP or DSP operation successfully performed by a DSA is
- subsequently reported to other DSAs with which it has a replication
- agreement as a set of one or more simple timestamped replication
- primitives. These primitives reflect the intended final state of an
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 2]
+ Each DAP, LDAP or DSP operation successfully performed by a directory
+ server is subsequently reported to other directory servers with which
+ it has a replication agreement as a set of one or more simple
+ timestamped replication primitives. These primitives reflect the
+ intended final state of an update operation rather than the specific
+Legg & Payne Expires 29 December 2000 [Page 2]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ changes required to achieve that state.
+ A directory server will receive replication primitives from its
+ various agreement partners according to the agreement schedules.
+ Those primitives MUST be reconciled with the current directory server
+ contents. 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 (which may
+ involve only the revision of the timestamp). If the directory server
+ has other replication agreements then the change will be reflected in
+ primitives sent during replication sessions for those other
+ agreements. If the primitive has an older timestamp it is no longer
+ relevant and is simply ignored.
- 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. 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 (which may involve only the revision of
- the timestamp). If the DSA has other replication agreements then the
- change will be reflected in primitives sent during replication
- sessions for those other agreements. If the primitive has an older
- timestamp it is no longer relevant and is simply ignored.
-
- 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.
+ The Update Reconciliation Procedures are designed to produce a
+ consistent outcome at all participating directory servers regardless
+ of the order in which the primitives are received and processed. The
+ primitives can also be safely replayed in the event that an exchange
+ of replication information with another directory server 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.
+ effect multi-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.
+ This Unique Identifier MUST be globally unique for all time in the
+ Directory. This can be achieved by defining a unique prefix for each
+ directory server and then ensuring that the suffix of the Unique
+ Identifier is locally unique.
+
+ The Unique Identifier for an entry is held in the entryUUID
+ operational attribute.
- Some pre-allocated global Unique Identifier values will be used to
+ Some pre-allocated global Unique Identifier values are used to
indicate the X.500 global root entry, and the Lost & Found entry (see
Section 4.4).
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
+ 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 Name CSN), the reference to its superior
- entry (the Parent CSN) and each of its attribute values (including
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 3]
+Legg & Payne Expires 29 December 2000 [Page 3]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
- the distinguished values), to record the time of the most recent
- action on that part of the entry.
+ seconds, a change count, a Replica Identifier and a modification
+ number. Notionally a CSN is associated with an entry's Relative
+ Distinguished Name (the Name CSN), the reference to its superior
+ entry (the Parent CSN) and each of its attribute values (including
+ the distinguished values and operational attribute values), to record
+ the time of the most recent action on that part of the entry.
The entry itself has a CSN (the Entry 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
+ removed and then re-added at one or more directory servers. 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.
+ not a user modifiable attribute. Note that from the perspective of a
+ consumer directory server 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.
+ deleted entries (entry deletion records), attributes (attribute
+ deletion records), or attribute values (value deletion records). A
+ deletion record contains a CSN and asserts that the associated
+ directory object no longer existed at the particular time.
4.3 Replication Primitives
Each update operation performed on an entry in a part of the DIT
- subject to one or more replication agreements must be subsequently
- reported as replication primitives to the replication partner DSAs of
- those agreements. The collection of primitives sent by a DSA to a
- replication partner may reflect both the results of locally processed
- user update requests and also of replicated updates received from
- other DSAs. A single update operation will decompose in one or more
- primitives.
+ subject to one or more replication agreements MUST be subsequently
+ reported as replication primitives to the replication partner
+ directory servers of those agreements. The collection of primitives
+ sent by a directory server to a replication partner will reflect both
+ the results of locally processed user update requests and also of
+ replicated updates received from other directory servers. A single
+ update operation will decompose into one or more primitives.
Common to all update primitives is an entry identifier argument, uid,
containing the Unique Identifier of the target entry of the change,
and a CSN argument, csn, to indicate the time of the change. 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.
- Additional arguments are present depending on the type of replication
- primitive.
-
- The p-add-entry(uid, csn, superior, rdn) primitive is used to add a
- new entry with minimal contents. 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.
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 4]
+ allocated by the directory server in the course of processing the
+ operation. Additional arguments are present depending on the type of
+ replication primitive.
+Legg & Payne Expires 29 December 2000 [Page 4]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ The p-add-entry(uid, csn, superior, rdn) primitive is used to
+ describe the addition of a new entry with minimal contents. 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. The superior argument contains the
- Unique Identifier of the new superior entry.
+ The p-move-entry(uid, csn, superior) primitive is used to describe
+ the moving of an entry to a new immediate superior in the DIT. 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. The rdn argument contains
- the new RDN for the entry.
+ The p-rename-entry(uid, csn, rdn) primitive is used to describe a
+ change to the Relative Distinguished Name of an entry. The rdn
+ argument contains the new RDN for the entry.
- The p-remove-entry(uid, csn) primitive is used to remove an entry.
+ The p-remove-entry(uid, csn) primitive is used to describe the
+ removal of an entry.
The p-add-attribute-value(uid, csn, type, value) primitive is used to
- add a single attribute value to an entry. The type argument contains
- the attribute type of the value and the value argument contains the
- attribute value.
+ describe the addition of a single attribute value to an entry. 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. The type argument
- contains the attribute type of the value and the value argument
- contains the attribute value.
+ to describe the removal of a single attribute value from an entry.
+ 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. The type argument contains
- the attribute type to be removed.
+ The p-remove-attribute(uid, csn, type) primitive is used to describe
+ the removal of all values of an attribute from an entry. The type
+ argument contains the removed attribute type.
These primitives reflect the intended final state of an update
operation rather than the specific changes required to achieve that
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.3.2). 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.
-
-
-
+ As a result of conflicting updates at two or more master directory
+ servers, 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 directory server creates a glue entry for
+ the missing superior entry. This glue entry is made a subordinate of
+ the specially nominated Lost & Found entry and the orphaned entry
+ becomes a subordinate of the glue superior entry (see Section 5.3.2).
+ Entries that exist in the Lost & Found subtree can still be modified
+ by actions of the replication protocol since entries are identified
+ by Unique Identifiers in the protocol, independent of their
-Legg & Payne Expires 22 April 2000 [Page 5]
+Legg & Payne Expires 29 December 2000 [Page 5]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ positioning in the global DIT.
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
+ 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 directory servers.
- 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.
+ Entries that exist under the Lost & Found entry are able to 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.
+ across all replicating directory servers.
5.1 Processing LDAP, DAP or DSP Operations on the DIT
CSNs on an entry or its contents, and create zero, one or more
deletion records referencing the entry or its contents. The CSNs and
deletion records generated from an operation are atomic with that
- operation. That is, either the operation succeeds, the CSNS are
+ operation. That is, either the operation succeeds, the CSNs are
revised and the deletion records are stored, or the operation fails,
no CSNs are revised and no deletion records are stored. In all
cases, all current error conditions (i.e. reasons for rejecting an
At some later time, possibly immediately following the update or
concurrently with it, the CSNs on entry contents and deletion records
are used to generate the replication primitives that will report the
- update to other DSAs via a replication session.
+ update to other directory servers via a replication session.
- All the CSNs generated from a single update operation must use the
+ All the CSNs generated from a single update operation MUST use the
same time, change count and Replica Identifier. The modification
- number is permitted to vary but must be assigned such that when the
+ number is permitted to vary but MUST be assigned such that when the
CSNs resulting from the operation, including those in the deletion
records, are compared to the CSNs resulting from any other operation
they are all strictly greater than or all strictly less than those
other CSNs (i.e. in a global CSN ordering of the primitives
- resulting from all operations the primitives of each operation must
+ resulting from all operations the primitives of each operation MUST
be contiguous in that ordering). In order for the update to be
- consistently applied when replicated to other DSAs the CSNs generated
- during that update 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 new
- 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
+ consistently applied when replicated to other directory servers the
+ CSNs generated during that update must generally be greater than any
+ pre-existing CSNs on the updated entry's contents. It is expected
-Legg & Payne Expires 22 April 2000 [Page 6]
+Legg & Payne Expires 29 December 2000 [Page 6]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ that directory servers will normally use the current time according
+ to their system clocks in generating the CSNs for an operation.
+ However in an environment where directory server clocks are not
+ necessarily synchronized the current time may be older than existing
+ CSNs on entry contents. The constraints the new CSNs MUST satisfy
+ with respect to pre-existing CSNs on entry data are covered in the
+ sections on each type of update operation. The Update Reconciliation
+ Procedures allow a directory server 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 additional constraint
+ that the CSN generated for an update operation MUST also be greater
+ than the highest CSN generated by the directory server that has
+ already been seen by any other directory server. An implementation
+ that generates successively greater CSNs for each operation will
+ satisfy this constraint.
+ The following sections describe the additional actions carried out in
+ processing each standard type of update operation in order to support
+ replication. If a directory server implementation supports other
+ non-standard update operations or alternative non-directory update
+ protocols then, in so far as these operations alter replicated
+ directory data, the implementation MUST generate and apply CSNs and
+ deletion records that accurately reflect any change.
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ A directory server implementation may also perform implicit updates
+ in response to user update requests, e.g. to maintain the referential
+ integrity of distinguished names. Appropriate CSNs and deletion
+ records for these changes MUST also be generated.
+ A detailed description of the replication processing for these other
+ types of update is beyond the scope of this document.
- constraints on the generation of the CSNs. As written, URP 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 additional 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.
+ 5.1.1 Add Entry
+
+ The LDAP Add operation [LDAPv3] or DAP addEntry operation [X511] is
+ used to add a leaf entry to the DIT. A successful request will
+ generate a CSN for the entry. The CSN on the entry's RDN, the CSN on
+ the entry's superior reference, and the CSN on each distinguished and
+ non-distinguished value added to the entry by the add entry operation
+ are set to this same value. The affected values include any
+ operational attribute values automatically generated by the directory
+ server, e.g. creatorsName and createTimestamp. Note that the value
+ of the createTimestamp attribute does not necessarily correspond to
+ the time component of the CSN associated with that value.
+
- The following sections describe the additional actions to support
- replication 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. A successful request will generate a CSN for
- the entry. The CSN on the entry's RDN, the CSN on the entry's
- superior reference, and the CSN on each distinguished and non-
- distinguished value added to the entry by the add entry operation are
- set to this same value. The affected values include any operational
- attributes automatically generated by the DSA.
+Legg & Payne Expires 29 December 2000 [Page 7]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
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
+ ought not 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 entry 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.
+ and outside the scope of this specification). In this case the CSN
+ for the entry 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. If the request succeeds then an
- entry deletion record is stored containing the Unique Identifier of
- the removed entry. The CSN for the entry deletion record must be
- generated such that it is greater than the entry CSN of the removed
- entry.
+ The LDAP Delete operation [LDAPv3] or DAP removeEntry operation
+ [X511] is used to remove a leaf entry from the DIT. If the request
+ succeeds then an entry deletion record is stored containing the
+ Unique Identifier of the removed entry. The CSN for the entry
+ deletion record MUST be generated such that it is greater than the
+ entry CSN of the removed entry.
5.1.3 Modify Entry
- The LDAP Modify operation (ModifyRequest) or DAP modifyEntry
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 7]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
- operation is used to perform a series of one or more modifications to
- an entry. If the request succeeds then zero, one or more new values
- with CSNs are added to the entry contents, and zero, one or more
- value or attribute deletion records are stored.
+ The LDAP Modify operation (ModifyRequest) [LDAPv3] or DAP modifyEntry
+ operation [X511] is used to perform a series of one or more
+ modifications to an entry. If the request succeeds then zero, one or
+ more new values with CSNs are added to the entry contents, and zero,
+ one or more value or attribute deletion records are stored.
The modifications described by the modification argument of the LDAP
ModifyRequest have the following additional effects:
The modifications described by the changes argument of the X.500
modifyEntry operation have the following additional effects:
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 8]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
a) The addAttribute and addValues alternatives associate a CSN
- with each of the added attribute values. These two alternatives
+ with each of the added attribute values. These two alternatives
are equivalent from the point of view of URP since there is no CSN
associated specifically with the attribute type.
e) The resetValues alternative generates a value deletion record
for each value actually removed.
- The CSNs generated by a modify operation must be greater than the CSN
+ A successful ModifyRequest or modifyEntry operation will also result
+ in changes to operational attributes of the entry. Like the explicit
+ modifications to user attributes, CSNs are given to new operational
+ attribute values and deletion records are stored for operational
+ attribute values that are removed. The processing in each case
+ depends on the semantics of the particular operational attribute type
+ and can be deduced by considering an equivalent explicit modification
+ request. In particular, the revision of the modifyTimestamp and
+ modifiersName attributes is treated like the ModifyRequest replace
+ alternative. Note that the value of the modifyTimestamp attribute
+ does not necessarily correspond to the time component of the CSN
+ associated with that value. The entryUUID operational attribute
+ SHALL NOT be modified. Consequently attribute and value deletion
+ records for the entryUUID attribute type are never generated.
+
+ The CSNs generated by a modify operation MUST be greater than the CSN
of any pre-existing attribute value that is removed, greater than or
equal to the CSN of any pre-existing attribute deletion record or
value deletion record applying to an added attribute value, and
greater than or equal to the CSN of the entry.
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 8]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
A further constraint applies to the modification number component of
the CSNs generated by a single modify operation. The CSN generated
- for an added attribute value must be greater than or equal to the CSN
+ for an added attribute value MUST be greater than or equal to the CSN
on any applicable value deletion record or attribute deletion record
already created by this same operation. This constraint is satisfied
if the same modification number is used in all the CSNs generated by
a single modify operation, or if the CSNs generated as the sequence
of modifications in the operation are applied in order use
monotonically increasing modification numbers. The modification
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 9]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
numbers need not be consecutive in this case.
Whenever a new value is added to the entry contents any value
deletion record for the same entry, attribute type and attribute
- value may be discarded.
+ value MAY be discarded.
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 the CSN on the entry's superior reference is
- replaced. If the entry's RDN is changed then the CSN on the entry's
- RDN is replaced. A value deletion record is stored 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.
+ The LDAP Modify DN operation [LDAPv3] and DAP modifyDN operation
+ [X511] 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 the CSN on the entry's
+ superior reference is replaced. If the entry's RDN is changed then
+ the CSN on the entry's RDN is replaced. A value deletion record is
+ stored for each of the formally distinguished attribute values
+ removed from the entry as a consequence of the deleteOldRDN parameter
+ (modifyDN) or deleteoldrdn parameter (ModifyDNRequest) being set to
+ true. An entryUUID attribute value that is made non-distinguished
+ SHALL NOT be removed from the entry regardless of the deleteOldRDN or
+ deleteoldrdn flag and SHALL NOT have a corresponding value deletion
+ record.
If the CSN on the entry's superior reference is revised then the new
- value must be greater than the previous value. If the CSN on the
- entry's RDN is revised then the new value must be greater than the
+ value MUST be greater than the previous value. If the CSN on the
+ entry's RDN is revised then the new value MUST be greater than the
previous value of the CSN on the RDN. The CSNs for any value
- deletion records must be greater than the CSNs on the removed
+ deletion records MUST be greater than the CSNs on the removed
attribute values.
5.2 Generating Replication Primitives
- Each time a replication session is invoked, the supplier DSA must
- generate and send replication primitives for updates known to the
- supplier but not yet known to the consumer DSA. The supplier uses the
- Update Vector of the consumer to determine what to send.
- Conceptually, the supplier scans all the glue and non-glue entries
- and deletion records covered by the replication agreement with the
- consumer and generates primitives where the CSNs held by the supplier
- are greater than the CSN for the corresponding identified replica in
- the consumer's Update Vector.
+ Each time a replication session is invoked, the supplier directory
+ server generates and sends replication primitives for updates known
+ to the supplier but not yet known to the consumer directory server.
+ The supplier uses the Update Vector of the consumer to determine what
+ to send. Conceptually, the supplier scans all the glue and non-glue
+ entries and deletion records covered by the replication agreement
+ with the consumer and generates primitives where the CSNs held by the
+ supplier are greater than the CSN for the corresponding identified
+ replica in the consumer's Update Vector. No replication primitives
+ are generated for entries or entry contents that are outside the
+ scope of the replication agreement.
A p-add-entry primitive is generated for each entry whose entry CSN
is greater than the Update Vector CSN for the same replica. The
+ superior argument of the p-add-entry primitive contains the Unique
+ Identifier of the immediate superior entry of the added entry. The
+ rdn argument of the p-add-entry primitive contains the Relative
-Legg & Payne Expires 22 April 2000 [Page 9]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+Legg & Payne Expires 29 December 2000 [Page 10]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
- superior argument of the p-add-entry primitive contains the Unique
- Identifier of the immediate superior entry of the added entry. The
- rdn argument of the p-add-entry primitive contains the Relative
- Distinguished Name of the created entry except that the Unique
- Identifier, if distinguished, is always omitted from the RDN. The
- superior and rdn arguments are provided even if the CSN on the
- superior reference or the RDN are greater than the CSN on the entry.
+ Distinguished Name of the created entry except that the value of the
+ entryUUID attribute, if distinguished, is always omitted from the
+ RDN. The superior and rdn arguments are provided even if the CSN on
+ the superior reference or the RDN are greater than the CSN on the
+ entry.
A p-add-attribute-value primitive is generated for each distinguished
value that has a CSN greater than the Update Vector CSN for the same
- replica and greater than the CSN on the RDN of its entry, and for
- each non-distinguished value that has a CSN greater than the Update
- Vector CSN for the same replica. The p-add-attribute-value primitive
- uses the CSN of the corresponding value. There are no separate
- primitives generated for the distinguished values that have the same
- CSN as the CSN on their entry's RDN.
+ replica and greater than the CSN on the RDN of its entry. A p-add-
+ attribute-value primitive is generated for each non-distinguished
+ value that has a CSN greater than the Update Vector CSN for the same
+ replica. The values of operational attributes are treated in the
+ same way as the values of user attributes. The p-add-attribute-value
+ primitive uses the CSN of the corresponding value. There are no
+ separate primitives generated for the distinguished values that have
+ the same CSN as the CSN on their entry's RDN.
If the CSN on an entry's RDN is greater than the Update Vector CSN
for the same replica and greater than the CSN on the entry then a p-
Update Vector CSN for the same replica and greater than the CSN on
the entry then a p-move-entry primitive is generated. The CSN for
this primitive is the CSN on the entry's superior reference and the
- superior argument of the contains the Unique Identifier of the
- immediate superior entry.
+ superior argument contains the Unique Identifier of the immediate
+ superior entry.
A p-remove-attribute-value primitive is generated for each value
deletion record having a CSN greater than the Update Vector CSN for
replica. The primitive uses exactly the same arguments as the entry
deletion record.
- Rather than scanning the DIT, an implementation may choose to
+ Rather than scanning the DIT, an implementation MAY choose to
generate replication primitives as the user update requests are being
processed and put these primitives into a replication log in
-Legg & Payne Expires 22 April 2000 [Page 10]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+Legg & Payne Expires 29 December 2000 [Page 11]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
preparation for sending during the next replication session. Any
replication primitives generated from an operation in this way MUST
- be atomic with that operation. That is, either the operation
+ be atomic with that operation. That is, either the operation
succeeds, and primitives are added to the replication log, or the
operation fails, and no primitives are added to the log. The
- replication log may be filtered prior to sending to eliminate any
- primitives that are superseded by later primitives in the log, and
- any primitives having CSNs less than or equal to the relevant CSNs
- contained in a consumer DSA's Update Vector.
+ replication log MAY be filtered prior to sending to eliminate any
+ primitives that are superseded by later primitives in the log, and to
+ eliminate any primitives having CSNs less than or equal to the
+ relevant CSNs contained in a consumer directory server's Update
+ Vector.
In a log based implementation, 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 older CSN.
+ 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 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
+ 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
+ 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-
+ 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.
5.3 Processing Replication Primitives on the DIT
- Each replication primitive received from another DSA during a
- replication session is processed against the DIT.
+ Each replication primitive received from another directory server
+ during a replication session that is within the scope of the
+ replication agreement is processed against the DIT. Replication
+ primitives outside the scope of the replication agreement are
+ rejected.
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
-
-
+ algorithms for processing each of the primitives. These algorithms
+ are not intended to be implemented verbatim but instead describe the
-Legg & Payne Expires 22 April 2000 [Page 11]
+Legg & Payne Expires 29 December 2000 [Page 12]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ behaviour an LDUP implementation MUST exhibit externally.
+ Alternative equivalent processing logic is permitted.
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
- 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.
+ 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.
For an entry, E, the notation E.rdn refers to the entry's Relative
Distinguished Name, E.dn refers to the entry's Distinguished Name,
and E.superior refers to the Unique Identifier of the entry's
superior in the DIT.
-
5.3.1 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
- 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.
-
+ It is necessary for a directory server to store deletion records to
+ remember that some entry, attribute or attribute value has been
+ deleted, for a period after the processing of the update operation or
+ replication primitive causing the deletion.
+ Value deletion records 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 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.
-Legg & Payne Expires 22 April 2000 [Page 12]
+ Entry deletion records have the same parameters as the p-remove-entry
+ primitive. The StoreEntryDeletion procedure 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
+Legg & Payne Expires 29 December 2000 [Page 13]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ 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.3.2 Glue Entries
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.
+ 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.
+ itself or its component parts) that are eligible to be purged 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
+ 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).
+ The Unique Identifier, in the form of the entryUUID attribute, 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.3.3 Generating Change Sequence Numbers
There are circumstances where conflicts arise in the processing of a
- replication primitive. It is necessary in these cases for the DSA
- processing the primitives to make corrective changes and emit
- additional primitives to ensure that all other DSAs reach the same
- consistent state. The GenerateNextCSN function is used to obtain a
- CSN for the corrective change. An implementation that generates
- replication primitives as the user update requests are being
- processed and puts them into a replication log must take the
- additional step of creating a primitive to convey the corrective
- change to other DSAs. Implementations that generate primitives by
- scanning entries will pick up the corrective change automatically.
-
- As is the case for CSNs 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 must also be satisfied.
-
- GenerateNextCSN takes a single CSN parameter. In addition to all
- other 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
+ replication primitive. It is necessary in these cases for the
+ directory server processing the primitives to make corrective changes
+ and emit additional primitives to ensure that all other directory
+ servers reach the same consistent state. The GenerateNextCSN
+ function is used to obtain a CSN for the corrective change. An
+ implementation that generates replication primitives as the user
+ update requests are being processed and puts them into a replication
+ log MUST take the additional step of creating a primitive to convey
+ the corrective change to other directory servers. Implementations
+ that generate primitives by scanning entries will pick up the
+ corrective change automatically.
+ As is the case for CSNs generated from DAP, DSP or LDAP operations,
+ the CSN for the corrective change is typically generated from the
+ current clock time of the directory server. The conditions imposed
-Legg & Payne Expires 22 April 2000 [Page 13]
+Legg & Payne Expires 29 December 2000 [Page 14]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ for the correct operation of the LDUP Update Vector MUST also be
+ satisfied.
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
- 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.
+ GenerateNextCSN takes a single CSN parameter. In addition to all
+ other 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 directory server, 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.3.4 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
+ 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.
+ 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 directory servers 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
+ 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
+ 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.
5.3.5 Entry Naming
- Independent changes at two or more DSAs can lead to the situation of
- two distinct entries having the same name. The procedure,
- CheckUniqueness(E, S, R), takes an entry and determines whether it is
- uniquely named. If not, it disambiguates the names of the entries by
- adding the Unique Identifier of each of the conflicting entries to
- their own RDN.
-
- The procedure CheckUniqueness is called in each circumstance where
- the Relative Distinguished Name of an entry might conflict with
- another entry, either because the entry has been renamed or because
- it has been moved to a new superior. An entry can be renamed
- directly by a p-rename-entry primitive, or as a side-effect of other
+ Independent changes at two or more directory servers can lead to the
+ situation of two distinct entries having the same name. The
+ procedure, CheckUniqueness(E, S, R), takes an entry and determines
+ whether it is uniquely named. If not, it disambiguates the names of
-Legg & Payne Expires 22 April 2000 [Page 14]
+Legg & Payne Expires 29 December 2000 [Page 15]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ the entries by adding the Unique Identifier (i.e. the entryUUID
+ attribute) of each of the conflicting entries to their own RDN.
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
+ The procedure CheckUniqueness is called in each circumstance where
+ the Relative Distinguished Name of an entry might conflict with
+ another entry, either because the entry has been renamed or because
+ it has been moved to a new superior. An entry can be renamed
+ directly by a p-rename-entry primitive, or as a side-effect of other
primitives causing changes to distinguished values. While each move
or rename of an entry potentially causes a conflict with some other
entry already having the new Distinguished Name, it also potentially
- removes a previous conflict on the old Distinguished Name. The
- enable the CheckUniqueness function to remove the Unique Identifier
- from an entry's RDN when it is no longer needed the old name for an
- entry is passed through the second and third parameters. The
- parameter, S, is the Unique Identifier of the old superior entry of
- E, and the parameter, R, is the old RDN of E. CheckUniqueness needs
- to ignore distinguished UniqueIdentifiers when comparing entry RDNs.
- The function BaseRDN(rdn) returns its argument minus any
- distinguished UniqueIdentifiers to support these comparisons.
+ removes a previous conflict on the old Distinguished Name. To enable
+ the CheckUniqueness function to remove the Unique Identifier from an
+ entry's RDN when it is no longer needed, the old name for an entry is
+ passed through the second and third parameters. The parameter, S, is
+ the Unique Identifier of the old superior entry of E, and the
+ parameter, R, is the old RDN of E. CheckUniqueness ignores
+ distinguished entryUUID values when comparing entry RDNs. The
+ function BaseRDN(rdn) returns its argument minus any distinguished
+ entryUUID values, to support these comparisons.
CheckUniqueness(E, S, R)
{
}
}
- Because updates are performed in isolation at multiple DSAs in a
- multimaster configuration it is possible to encounter a situation
- where there is a request to delete a distinguished value in an entry.
- The recommended practice in these circumstances is to remove the
- distinguished value and call CheckUniqueness to correct any resulting
- name conflicts. An implementation may instead reassert the existence
- of the distinguished value with a more recent CSN to avoid altering
- the entry's RDN. This option is only available to updatable replicas.
- Read-only replicas MUST remove the distinguished value. The function
- ProtectDistinguished() returns true for an updatable part of the DIT
- in an DSA that implements this option, and false otherwise. DSAs
- exercising this option must generate p-add-attribute-value primitive
- so that other DSAs are guaranteed to also reassert the distinguished
- value. DSAs that implement the option will correctly interwork with
- servers that do not.
-
- 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
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 15]
+ Because updates are performed in isolation at multiple directory
+ servers in a multimaster configuration it is possible to encounter a
+ situation where there is a request to delete a distinguished value in
+ an entry. The recommended practice in these circumstances is to
+ remove the distinguished value and call CheckUniqueness to correct
+ any resulting name conflicts. An implementation MAY instead reassert
+ the existence of the distinguished value with a more recent CSN to
+ avoid altering the entry's RDN. This option is only available to
+ updatable replicas. Read-only replicas MUST remove the distinguished
+ value. The function ProtectDistinguished() returns true for an
+ updatable part of the DIT in a directory server that implements this
+Legg & Payne Expires 29 December 2000 [Page 16]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ option, and false otherwise. directory servers exercising this
+ option MUST generate a p-add-attribute-value primitive so that other
+ directory servers are guaranteed to also reassert the distinguished
+ value. Directory servers that implement the option will correctly
+ interwork with servers that do not.
-
- 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
- distinguished values. It is the responsibility of the calling
+ 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
+ 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
+ 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)
V.csn := GenerateNextCSN(V.csn)
}
ELSE IF no attribute deletion record (uid, type, csn) exists
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 17]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
where (uid = P.uid AND type = N.type AND csn > P.csn)
AND no value deletion record (uid, type, value, csn) exists
where (uid = P.uid AND type = N.type AND
add V to E as a distinguished value
V.csn := P.csn
}
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 16]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
E.rdn.csn := P.csn
}
5.3.6 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.
+ This section details the algorithm for processing the p-add-
+ attribute-value (P.uid, P.type, P.value, P.csn) primitive, which
+ describes the addition of a single attribute value. If P.type is the
+ entryUUID attribute type then the primitive MUST be rejected.
IF no value deletion record (uid, type, value, csn) exists where
(uid = P.uid AND type = P.type
{
V := P.value
Add V to E as a non-distinguished attribute value
- V.csn := P.csn
- }
- }
-
-
- 5.3.7 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
-Legg & Payne Expires 22 April 2000 [Page 17]
-
-
+Legg & Payne Expires 29 December 2000 [Page 18]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ V.csn := P.csn
+ }
+ }
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ 5.3.7 Processing Remove Attribute Value Primitive
- distinguished is tagged as distinguished-not-present rather than
- being immediately removed. Such a value will be physically removed
- when it becomes non-distinguished.
+ This section details the algorithm for processing the p-remove-
+ attribute-value (P.uid, P.type, P.value, P.csn) primitive, which
+ describes the removal of a single attribute value. If P.type is the
+ entryUUID attribute type then the primitive MUST be rejected.
IF no value deletion record (uid, type, value, csn) exists
where (uid = P.uid AND type = P.type AND
StoreValueDeletion (P.uid, P.type, P.value, P.csn)
}
ELSE
- StoreValueDeletion (P.uid, P.type, P.value, P.csn)
-
- 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 22 April 2000 [Page 18]
-
+Legg & Payne Expires 29 December 2000 [Page 19]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ StoreValueDeletion (P.uid, P.type, P.value, P.csn)
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ 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.
5.3.8 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.
+ This section details the algorithm for processing the p-remove-
+ attribute (P.uid, P.type, P.csn) primitive, which describes the
+ removal of all attribute values of P.type. If P.type is the
+ entryUUID attribute type then the primitive MUST be rejected.
IF no attribute deletion record (uid, type, csn) exists
where (uid = P.uid AND type = P.type AND csn >= P.csn)
5.3.9 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. The CSN on an entry records the time of the latest
- p-add-entry primitive for the Unique Identifier. In normal
- circumstances there 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.
-
- IF no entry deletion record (uid, csn) exists where
-
-
+ This section details the algorithm for processing the p-add-entry
-Legg & Payne Expires 22 April 2000 [Page 19]
+Legg & Payne Expires 29 December 2000 [Page 20]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ (P.uid, P.superior, P.rdn, P.csn) primitive, which describes the
+ addition of an entry. The CSN on an entry records the time of the
+ latest p-add-entry primitive for the Unique Identifier. In normal
+ circumstances there 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.
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
+ IF 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
{
+ R := E.rdn
+ S := E.superior
E.csn := P.csn
- FOREACH attribute value, V, in E
- IF V.csn < P.csn
- remove value V
+ FOREACH attribute type, T, in E, except entryUUID
+ FOREACH attribute value, V, of type T
+ IF V.csn < P.csn
+ remove value V
+ CheckUniqueness(E, S, R)
process P according to
p-rename-entry(P.uid, P.rdn, P.csn)
process P according to
5.3.10 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.
+ This section details the algorithm for processing the p-remove-entry
+ (P.uid, P.csn) primitive, which describes the removal of 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
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 21]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
+ has any subordinate entries, it becomes a glue entry instead of being
+ removed. It is also moved to Lost & Found, unless it has a CSN for
+ its superior reference that is greater than the CSN of the p-remove-
+ entry.
IF no entry deletion record (uid, csn) exists
where (uid = P.uid AND csn >= P.csn)
IF P.csn > E.csn
{
IF E.superior.csn >= P.csn
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 20]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
OR any value, V, with csn >= P.csn exists
OR E has subordinates
{
}
IF E.rdn.csn < P.csn
purge E.rdn.csn
- FOREACH attribute value, V, in E
- IF V.csn < P.csn
- remove value V
+ FOREACH attribute type, T, in E, except entryUUID
+ FOREACH attribute value, V, of type T
+ IF V.csn < P.csn
+ remove value V
CheckUniqueness(E, S, R)
}
ELSE
5.3.11 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.
+ This section details the algorithm for processing the p-move-entry
+ (P.uid, P.superior, P.csn) primitive, which describes the moving of
+ an entry to a new immediate superior in the DIT. 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
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 22]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
+ & Found instead.
IF no entry deletion record (uid, csn) exists
where (uid = P.uid AND csn > P.csn)
IF entry, S, with uid = P.superior does not exist
S := CreateGlueEntry(P.superior)
IF S is not in the subtree of E
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 21]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
{
E.superior := P.superior
E.superior.csn = P.csn
5.3.12 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. A p-rename-entry primitive that is
- older than current name of an entry is not simply ignored since it
- may contain attribute values that would have been added to the entry
- had the primitives arrived in CSN order. These extra values would
- now be non-distinguished.
+ This section details the algorithm for processing the p-rename-entry
+ (P.uid, P.rdn, P.csn) primitive, which describes a change to the
+ Relative Distinguished Name of an entry. A p-rename-entry primitive
+ that is older than current name of an entry is not simply ignored
+ since it may contain attribute values that would have been added to
+ the entry had the primitives arrived in CSN order. These extra
+ values would now be non-distinguished.
IF no entry deletion record (uid, csn) exists
where (uid = P.uid AND csn >= P.csn)
R := E.rdn
FOREACH distinguished attribute value, V, in entry E
make V non-distinguished
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 23]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
RenameEntry(E, P)
CheckUniqueness(E, E.superior, R)
}
replace V with N.value if they are not identical
V.csn := P.csn
}
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 22]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
}
ELSE
{
6. Security Considerations
- [To be supplied]
+ The procedures described in this document are not subject to access
+ controls on the directory data items being modified. Specifically,
+ the update primitives received from a peer replica are applied
+ without regard for access controls. This is necessary so that access
+ control information can also be replicated. An LDUP enabled server
+ entering into a multi-master replication agreement with a peer server
+ is enabling joint authority and responsibility for some part of the
+ directory data. A replica must trust that the other replicas are
+ properly enforcing access controls on user update requests, but this
+ trust extends only as far as described by the replication agreements
+ currently in place. The replication agreement acts as a surrogate
+ for access controls between peer replicas. Replication primitives
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 24]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
+ that are outside the scope of the agreement are rejected.
+
+ Authentication of peer replica LDUP sessions and the security of the
+ exchange of replication primitives through the LDUP protocol are
+ outside the scope of this document and are described elsewhere.
+
+ Simultaneous updates at different replicas can result in two entries,
+ corresponding to two different real world entities, having the same
+ distinguished name. The Update Reconciliation Procedures
+ disambiguate these two names by appending the respective Unique
+ Identifiers to the entries' RDNs. This action will disable any
+ access controls based on an entry's specific DN or RDN. Disabling
+ such an access control may have the effect of granting a permission
+ that was explicitly denied. Since a Unique Identifier is required to
+ be globally unique for all time, appending a Unique Identifier to the
+ RDN cannot unintentionally enable access controls applying to a
+ different real world entity.
+
+ It is sufficient when disambiguating entry RDNs to append the UID to
+ only one of a pair of entries ending up with the same name. The
+ Update Reconciliation Procedures require both entries to have their
+ UID appended to minimize the chance that either entry will gain
+ permissions intended for the other. This is based on the assumption
+ that most access controls will grant permissions rather than deny
+ permissions.
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 like to thank Suellen Faulks and Tony Robertson
+ from Telstra and Mark Ennis from Adacel Technologies 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.
-
- [BCP-11] - R. Hovey, S. Bradner, "The Organizations Involved in the
- IETF Standards Process", BCP 11, RFC 2028, October 1996.
-
+ [RFC2119] - S. Bradner, "Key words for use in RFCs to Indicate
+ Requirement Levels", RFC 2119.
- 9. Intellectual Property Notice
+ [LDAPv3] - M. Wahl, S. Kille, T. Howes, "Lightweight Directory Access
+ Protocol (v3)", RFC 2251, December 1997.
- The IETF takes no position regarding the validity or scope of any
- intellectual property or other rights that might be claimed to
+ [X500] - ITU-T Recommendation X.500 (08/97) | ISO/IEC 9594-1:1998,
+ Information Technology - Open Systems Interconnection - The
-Legg & Payne Expires 22 April 2000 [Page 23]
+Legg & Payne Expires 29 December 2000 [Page 25]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+ Directory: Overview of concepts, models and services
+ [X511] - ITU-T Recommendation X.511 (08/97) | ISO/IEC 9594-3:1998,
+ Information Technology - Open Systems Interconnection - The
+ Directory: Abstract service definition
+ [BCP-11] - R. Hovey, S. Bradner, "The Organizations Involved in the
+ IETF Standards Process", BCP 11, RFC 2028, October 1996.
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
+ 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
10. Copyright Notice
- Copyright (C) The Internet Society (1999). All Rights Reserved.
+ Copyright (C) The Internet Society (2000). 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
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
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 26]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
followed, or as required to translate it into languages other than
English.
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 24]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
- 11. Authors' Address
+ 11. Authors' Addresses
Steven Legg
- Telstra Research Laboratories
- 770 Blackburn Road
- Clayton, Victoria 3168
+ Adacel Technologies Ltd.
+ 250 Bay Street
+ Brighton, Victoria 3186
AUSTRALIA
- Phone: +61 3 9253 6771
- Fax: +61 3 9253 6485
- EMail: s.legg@trl.telstra.com.au
+ Phone: +61 3 8530 7808
+ Fax: +61 3 9596 2960
+ EMail: steven.legg@adacel.com.au
Alison Payne
- PricewaterhouseCoopers
- St Jakobs Strasse 25
- CH-4002 Basel
- SWITZERLAND
+ Telstra
+ 21/242 Exhibition Street
+ Melbourne, Victoria 3000
+ AUSTRALIA
- Phone: +41-79-458 4177
- EMail: alison.b.payne@ch.pwcglobal.com
+ Phone: +61 3 9634 4628
+ EMail: alison.payne@team.telstra.com
12. Appendix A - Changes From Previous Drafts
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
+ after the earliest re-add. This eliminates the need for Addition
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 27]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
+ 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
+ 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.
primitives. There are no longer any references to saved primitives
though the functionality is still present.
-
-
-
-Legg & Payne Expires 22 April 2000 [Page 25]
-
-
-
-
-
-INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
-
-
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.
edition of X.500 so references to the proposed X.500 multimaster
replication protocol have been removed.
- The treatment of distinguished values has been simplified. Previously
- an attempt to remove a distinguished value caused the value to be
- tagged distinguished-not-present. Now the distinguished value is
- removed, and if necessary, the Unique Identifier is made
- distinguished to avoid an empty RDN. Optionally, the value to be
+ The treatment of distinguished values has been simplified.
+ Previously an attempt to remove a distinguished value caused the
+ value to be tagged distinguished-not-present. Now the distinguished
+ value is removed, and if necessary, the Unique Identifier is made
+ distinguished to avoid an empty RDN. Optionally, the value to be
removed can be reasserted by emitting an explicit p-add-attribute-
value primitive.
- The current draft is more implementation neutral. A replication log
+ The current draft is more implementation neutral. A replication log
no longer figures prominently in the specification. The previous
descriptions had the user updates generating replication primitives,
which in turn were used to determine the CSNs and deletion records.
The new descriptions have user updates generating CSNs and deletion
records and the primitives are subsequently generated from them.
- 13. Appendix B - Open Issues
+ 12.3 Changes in Draft 03
+
+ The draft has been edited to make use of the key words "MUST",
+ "SHOULD", "MAY", etc.
+
+ The treatment of server maintained operational attributes has been
+ clarified.
+
+ An extra CheckUniqueness call has been added to the procedure for
+
+
+
+Legg & Payne Expires 29 December 2000 [Page 28]
+\f
+INTERNET-DRAFT LDUP Update Reconciliation Procedures June 29, 2000
+
+
+ processing the p-add-entry primitive (Section 5.3.9) to cover the
+ case where an entry is re-added. A loop through all of the values of
+ an entry in the p-add-entry and p-remove-entry processing has been
+ altered to explicitly skip the entryUUID operational attribute. No
+ other changes have been made to the behaviour of the Update
+ Reconciliation Procedures from Draft 02.
+
+ The list of references has been expanded.
+
+ The Security Considerations section has been added.
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
- The precise location of the Lost & Found entry has not yet been
- decided.
- Extensions to the algorithms to properly deal with partial replicas
- are still to be decided.
- The draft needs some editing to use MAY, MUST, etc, in the proper
- way.
-Legg & Payne Expires 22 April 2000 [Page 26]
+Legg & Payne Expires 29 December 2000 [Page 29]
+\f
projects / openldap / blobdiff