INTERNET-DRAFT S. Legg draft-legg-ldup-urp-00.txt Telstra Corporation February 16, 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 or to the author. This Internet-Draft expires on 16 August 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 Expires 16 August 1999 [Page 1] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 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 5 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.4 Modify DN 10 5.2 Processing Replication Primitives on the DIT 11 5.2.1 Propagating Primitives 12 5.2.2 Saving Deletion Records 13 5.2.3 Saving Primitives 13 5.2.4 Generating Commit Sequence Numbers 14 5.2.5 Comparison of Attribute Values 16 5.2.6 Renaming Entries 16 5.2.7 Name Conflict Resolution 16 5.2.8 Processing Add Attribute Value Primitive 17 5.2.9 Processing Remove Attribute Value Primitive 18 5.2.10 Processing Remove Attribute Primitive 19 5.2.11 Processing Add Entry Primitive 20 5.2.12 Processing Remove Entry Primitive 21 5.2.13 Processing Move Entry Primitive 23 5.2.14 Processing Rename Entry Primitive 24 6. Security Considerations 25 7. Acknowledgements 25 8. References 26 9. Intellectual Property Notice 26 10. Copyright Notice 26 11. Author's Address 27 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 update operation rather than the specific changes required to achieve that state. A DSA will receive replication primitives from its various agreement Legg Expires 16 August 1999 [Page 2] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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 (which 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 Commit Sequence Number (CSN). The components of the CSN are, from most significant to least significant, a time in seconds, a version number and a DSA identifier. 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 the time of the most recent action on that part of the entry. The entry itself has an optional Creation CSN and zero or more Addition CSNs asserting the time(s) at which the entry was added. The Legg Expires 16 August 1999 [Page 3] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 entry may have more than one of these CSNs if it has been removed and then re-added at several 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 in two circumstances. Firstly, by the explicit action of a directory administrator to restore an entry which 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. Secondly, 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 which 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. Note: DMRP exchanges the primitives generated from a DAP, LDAP or DSP operation. Whether LDUP exchanges primitives or the original update is yet to be defined. 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. Common to all update primitives is an entry identifier argument, uid, Legg Expires 16 August 1999 [Page 4] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 which 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. 4.4 Lost & Found Legg Expires 16 August 1999 [Page 5] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 Each connected set of mastering DSAs have a Lost & Found entry nominated. The Unique Identifier of this entry will be pre-allocated. Its name may be implementation dependent, but whatever name is used, the Lost & Found entry itself is never renamed or moved. This entry will become the superior of any entry which has been orphaned as a result of conflicting updates, even if only temporarily. Entries which exist in the Lost & Found area may still be modified by operations, since entries are identified by Unique Identifiers in the replication protocol, independent of positioning in the global DIT. Entries which 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. If the outcome of the processing of a primitive is dependent on the local DIT (e.g. renaming an entry to an existing name, or moving an entry to a non-existent superior), it is necessary to inject the local change into the replication log to ensure the consistency of the information held across DSAs. A variation to the Lost & Found scheme presented in this document is under consideration. The variant scheme creates a glue entry for the missing superior as a direct subordinate of the Lost & Found entry. The orphaned entry then does not need to be modified by an implicit move to Lost & Found because its nominated superior exists. The move operation of the current scheme is considered undesirable because it causes an orphaned entry to be forcibly moved to Lost & Found even if the reason for it being orphaned is only transitory (e.g. an artifact of the particular order in which primitives are received). 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. Legg Expires 16 August 1999 [Page 6] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 A single CSN is associated with an update operation and all the primitives generated from the update operation must use this CSN as their csn argument. In order for the update to be consistently applied when replicated to other DSAs the CSN 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 CSN 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 operation CSN 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 CSN. DMRP allows a DSA to generate a CSN 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 which has already been seen by any other DSA. An implementation which 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 clock. 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 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. 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 Legg Expires 16 August 1999 [Page 7] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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 operation CSN becomes the Creation CSN for the entry and initializes the entry's set of Addition CSNs. Each distinguished and non-distinguished value added to the entry is timestamped with the CSN of the operation. 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 operation must be generated such that it is greater than or equal to the CSN of any existing entry deletion records and greater than the CSN of any saved primitives (see Section 5.2.3), 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 operation must be generated such that it is greater than all the Addition CSNs of the target entry, greater than the CSN of any saved primitives for the entry, and greater than or equal to the CSN of any value or attribute deletion records for the 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- value, p-remove-attribute-value or p-remove-attribute primitives are Legg Expires 16 August 1999 [Page 8] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 generated and placed in the replication log. Unlike the changes argument of modifyEntry or the modification argument of ModifyRequest the primitives generated from the request 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 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 Legg Expires 16 August 1999 [Page 9] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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 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 which 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 all the Addition CSNs of the entry. Each attribute value added to the entry is timestamped with the CSN of the operation. 5.1.4 Modify DN Legg Expires 16 August 1999 [Page 10] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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 operation must be greater than the previous CSN for the entry's superior reference. The entry's superior reference is timestamped with the operation 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 operation must be greater than the previous CSN for the entry's RDN. The entry's RDN is timestamped with the operation 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. When present in an entry, the Creation CSN records the time of the first p-add-entry primitive for the Unique Identifier or the first p-add-entry primitive following an earlier p-remove-entry primitive. The times of any subsequent p-add-entry primitives are recorded as Addition CSNs. The Creation CSN and Addition CSNs may be discarded when they become eligible to be purged (in DMRP, when they are older than the Oldest Time). An entry without a Creation CSN is assumed to have been created earlier than the Oldest Time. The notation E.creation will be used to refer to the Creation CSN of the entry E. In the case where the Creation CSN for E has been discarded E.creation is assumed to have the least possible CSN value. The notation E.addition will be used to refer to the set of Addition CSNs for the entry E. 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 Legg Expires 16 August 1999 [Page 11] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 greater with the progression of time, so older CSNs are less than younger CSNs 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 which has the same DSA 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 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- Legg Expires 16 August 1999 [Page 12] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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 which 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. A distinction is made here to avoid confusion with replication log primitives and saved primitives. 5.2.3 Saving Primitives 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 it is re-added. The Save procedure stores a primitive for later processing in the event that a p-add-entry Legg Expires 16 August 1999 [Page 13] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 primitive with an older CSN is received for the same entry. A saved primitive is either removed from the store when it is applied, is discarded when it becomes eligible to be purged (in DMRP, when the Oldest Time becomes younger than the CSN on the saved primitive), or is discarded when it is superseded by another saved primitive or a deletion record. A saved primitive supersedes previously saved primitives under the same rules that apply to primitives added to the replication log. A value deletion record supersedes a saved p-add-attribute-value primitive for the same entry, attribute type, attribute value and older CSN. An attribute deletion record supersedes a saved p-add-attribute-value primitive for the same entry, attribute type and older CSN. An entry deletion record supersedes a saved p-add-attribute-value, p-move-entry or p-rename-entry primitive for the same entry and older CSN. A saved p-add-attribute-value primitive supersedes a value deletion record for the same entry, attribute type, attribute value and equal or older CSN. 5.2.4 Generating Commit 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 the 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 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 which is reset after each replication session to a value greater than the largest CSN seen Legg Expires 16 August 1999 [Page 14] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 so far, and thereby 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 which 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 which 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 which 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 resets the CSNs and 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 AND V = N.value Legg Expires 16 August 1999 [Page 15] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 { 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 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, Legg Expires 16 August 1999 [Page 16] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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 entry, E, with uid = P.uid exists IF attribute value V, of type P.type where V = P.value exists in E { IF P.csn > V.csn { V.csn := P.csn replace V with P.value if they are not identical IF V is distinguished-not-present set V to distinguished-present IF V is distinguished AND P.type is a single-valued attribute type CheckUniqueness(E) Propagate(P) } } Legg Expires 16 August 1999 [Page 17] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 ELSE { 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 P.csn < E.creation { IF no saved primitive p-add-attribute-value (uid, type, value, csn) exists where (uid = P.uid AND type = P.type AND value = P.value AND csn >= P.csn) { Save(P) Propagate(P) } } ELSE { V := P.value Add V to E as a non-distinguished attribute value V.csn := P.csn Propagate(P) } } ELSE /* entry, E, with uid = P.uid does not exist */ IF no saved primitive p-add-attribute-value (uid, type, value, csn) exists where (uid = P.uid AND type = P.type AND value = P.value AND csn >= P.csn) { Save(P) 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 which is distinguished is tagged as distinguished-not-present rather than being immediately removed. Such a value will be physically removed Legg Expires 16 August 1999 [Page 18] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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) { StoreValueDeletion (P.uid, P.type, P.value, P.csn) IF entry, E, with uid = P.uid exists AND 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 } 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 which has a younger CSN. If there is a younger deletion record than the primitive then there cannot be an older value to remove. 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 which are distinguished are tagged as distinguished-not-present rather than being immediately removed. Such values will be physically removed Legg Expires 16 August 1999 [Page 19] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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) { StoreAttributeDeletion (P.uid, P.type, P.csn) IF entry, E, with uid = P.uid exists { 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 } } 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 (uid = P.uid AND csn > P.csn) IF entry, E, with uid = P.uid exists { IF P.csn is not a member of E.addition { add P.csn to E.addition IF P.csn < E.creation E.creation := P.csn process P according to p-rename-entry(P.uid, P.rdn, P.csn) except do not propagate P Legg Expires 16 August 1999 [Page 20] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 process P according to p-move-entry(P.uid, P.superior, P.csn) except do not propagate P Propagate(P) } } ELSE { create entry E Add P.csn to E.addition E.creation := P.csn E.uid := P.uid E.uid.csn :=P.csn E.rdn.csn :=P.csn RenameEntry(E, P) /* Check and set superior reference */ IF entry, S, with uid = P.superior exists { E.superior = P.superior E.superior.csn := P.csn } ELSE /* entry, S, with uid = P.superior doesn't exist */ { 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) Apply any saved primitives where uid = P.uid AND csn >= P.csn Propagate(P) } *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.12 Processing Remove Entry Primitive Legg Expires 16 August 1999 [Page 21] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 This section describes the algorithm for processing the p-remove- entry (P.uid, P.csn) primitive, which is responsible for removing an entry. An entry may have more than one Addition CSN and it is only physically removed if the CSN on the p-remove-entry is greater than all the Addition CSNs. Otherwise the remove primitive will remove only any older addition CSNs, and any older attribute values. Attribute values with CSNs younger than the primitive's CSN but older than the creation CSN are removed and converted into saved primitives. These saved primitives are potentially reapplied to the entry if a p-add-entry primitive is subsequently received. If an entry with subordinates is removed the subordinates are moved to Lost & Found. IF no entry deletion record (uid, csn) exists where (uid = P.uid AND csn >= P.csn) { StoreEntryDeletion (P.uid, P.csn) IF entry, E, with uid = P.uid exists IF P.csn > greatest member of E.addition { FOREACH subordinate, S, of E { S.superior = LOST_AND_FOUND S.superior.csn = GenerateNextCSN(S.superior.csn) make p-move-entry(S.uid, LOST_AND_FOUND, S.superior.csn) CheckUniqueness(S) } FOREACH attribute, A, in E FOREACH attribute value, V, in A IF V.csn >= P.csn Save(p-add-attribute-value(E.uid, A.type, V, V.csn)) IF E.superior.csn >= P.csn Save(p-move-entry(E.uid, E.superior, E.superior.csn)) IF E.rdn.csn >= P.csn Save(p-rename-entry(E.uid, E.rdn, E.rdn.csn) remove entry E } ELSE { FOREACH csn in E.addition IF csn < P.csn Legg Expires 16 August 1999 [Page 22] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 remove csn from E.addition E.creation := least member of E.addition FOREACH attribute, A, in E FOREACH attribute value, V, in A IF V.csn < P.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 /* V is non-distinguished */ remove value V } ELSE IF V.csn < E.creation Save(p-add-attribute-value(E.uid, A.type, V, V.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 entry, E, with uid = P.uid exists { IF P.csn > E.superior.csn { IF new superior with uid = P.superior exists AND new superior 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) Legg Expires 16 August 1999 [Page 23] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 } CheckUniqueness(E) } } ELSE IF no entry deletion record (uid, csn) exists where (uid = P.uid AND csn > P.csn) AND no saved primitive p-move-entry(uid, superior, csn) exists where (uid = P.uid AND superior = P.superior AND csn >= P.csn) { Save(P) Propagate(P) } 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 exists { IF P.csn > E.rdn.csn /* Entry has a new name */ { /* 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) } ELSE /* P.csn < E.rdn.csn */ /* This primitive is older than the current name, but may contain implicit add attribute values */ { Legg Expires 16 August 1999 [Page 24] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 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 which 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) } } ELSE /* entry, E, with uid = P.uid does not exist */ IF no saved primitive p-rename-entry(uid, rdn, csn) exists where (uid = P.uid AND rdn = P.rdn AND csn >= P.csn) { Save(P) Propagate(P) } } Legg Expires 16 August 1999 [Page 25] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 6. Security Considerations [To be supplied] 7. Acknowledgements The author would like to thank the staff from Telstra Research Laboratories who contributed to the design and verification of the procedures described in this document, including Alison Payne, Suellen Faulks and Tony Robertson. The author 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. Legg Expires 16 August 1999 [Page 26] INTERNET-DRAFT LDUP Update Reconciliation Procedures February 16, 1999 10. Copyright Notice Copyright (C) The Internet Society (1999). All Rights Reserved. This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 11. Author's 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 Legg Expires 16 August 1999 [Page 27]