2 draft-ietf-ldup-urp-02.txt Telstra
8 LDUP Update Reconciliation Procedures
10 Copyright (C) The Internet Society (1999). All Rights Reserved.
15 This document is an Internet-Draft and is in full conformance with
16 all provisions of Section 10 of RFC2026.
18 Internet-Drafts are working documents of the Internet Engineering
19 Task Force (IETF), its areas, and its working groups. Note that
20 other groups may also distribute working documents as Internet-
23 Internet-Drafts are draft documents valid for a maximum of six months
24 and may be updated, replaced, or obsoleted by other documents at any
25 time. It is inappropriate to use Internet-Drafts as reference
26 material or to cite them other than as "work in progress".
28 The list of current Internet-Drafts can be accessed at
29 http://www.ietf.org/ietf/1id-abstracts.txt
31 The list of Internet-Draft Shadow Directories can be accessed at
32 http://www.ietf.org/shadow.html.
34 This draft is published by the IETF LDUP Working Group. Distribution
35 of this document is unlimited. Comments should be sent to the LDUP
36 Replication mailing list <ldup@imc.org> or to the authors.
38 This Internet-Draft expires on 22 April 2000.
42 This document describes the procedures used by directory servers to
43 reconcile updates performed by autonomously operating directory
44 servers in a distributed, replicated directory service.
52 Legg & Payne Expires 22 April 2000 [Page 1]
58 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
64 2. Table of Contents 2
67 4.1 Unique Identifier 3
68 4.2 Timestamps & Existence 3
69 4.3 Replication Primitives 4
71 5. Replication Procedures 6
72 5.1 Processing LDAP, DAP or DSP Operations on the DIT 6
77 5.2 Generating Replication Primitives 9
78 5.3 Processing Replication Primitives on the DIT 11
79 5.3.1 Saving Deletion Records 12
81 5.3.3 Generating Change Sequence Numbers 13
82 5.3.4 Comparison of Attribute Values 14
84 5.3.6 Processing Add Attribute Value Primitive 17
85 5.3.7 Processing Remove Attribute Value Primitive 17
86 5.3.8 Processing Remove Attribute Primitive 19
87 5.3.9 Processing Add Entry Primitive 19
88 5.3.10 Processing Remove Entry Primitive 20
89 5.3.11 Processing Move Entry Primitive 21
90 5.3.12 Processing Rename Entry Primitive 22
91 6. Security Considerations 23
92 7. Acknowledgements 23
94 9. Intellectual Property Notice 23
95 10. Copyright Notice 24
96 11. Authors' Address 25
97 12. Appendix A - Changes From Previous Drafts 25
98 12.1 Changes in Draft 01 25
99 12.2 Changes in Draft 02 26
100 13. Appendix B - Open Issues 26
105 Each DAP, LDAP or DSP operation successfully performed by a DSA is
106 subsequently reported to other DSAs with which it has a replication
107 agreement as a set of one or more simple timestamped replication
108 primitives. These primitives reflect the intended final state of an
112 Legg & Payne Expires 22 April 2000 [Page 2]
118 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
121 update operation rather than the specific changes required to achieve
124 A DSA will receive replication primitives from its various agreement
125 partners according to the agreement schedules. Those primitives must
126 be reconciled with the current DSA contents. In broad outline,
127 received replication primitives are compared to the timestamp
128 information associated with the directory data item being operated
129 on. If the primitive has a more recent timestamp a change in the
130 directory contents is made (which may involve only the revision of
131 the timestamp). If the DSA has other replication agreements then the
132 change will be reflected in primitives sent during replication
133 sessions for those other agreements. If the primitive has an older
134 timestamp it is no longer relevant and is simply ignored.
136 The update reconciliation procedures are designed to produce a
137 consistent outcome at all participating DSAs regardless of the order
138 in which the primitives are received. The primitives can also be
139 safely replayed in the event that an exchange of replication
140 information with another DSA is interrupted. This greatly simplifies
141 the recovery mechanisms required in the replication protocol.
145 This section describes the extensions to the data model required to
146 effect multiple master replication.
148 4.1 Unique Identifier
150 A Unique Identifier is associated with each entry in the global DIT.
151 This Unique Identifier must be globally unique for all time in the
152 Directory. This can be achieved by defining a unique DSA prefix for
153 each DSA and then ensuring that the suffix of the Unique Identifier
156 Some pre-allocated global Unique Identifier values will be used to
157 indicate the X.500 global root entry, and the Lost & Found entry (see
160 4.2 Timestamps & Existence
162 The timestamp for a replication primitive or directory data item is
163 in the form of a Change Sequence Number (CSN). The components of the
164 CSN are, from most significant to least significant, a time in
165 seconds, a change count, a Replica Identifier and a modification
166 number. Notionally a CSN is associated with an entry's Relative
167 Distinguished Name (the Name CSN), the reference to its superior
168 entry (the Parent CSN) and each of its attribute values (including
172 Legg & Payne Expires 22 April 2000 [Page 3]
178 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
181 the distinguished values), to record the time of the most recent
182 action on that part of the entry.
184 The entry itself has a CSN (the Entry CSN) asserting the most recent
185 time at which the entry was added. An entry is permitted to be
186 removed and then re-added at one or more DSAs. In this context re-
187 adding an entry means reusing the Unique Identifier of a removed
188 entry and does not refer to the case of reusing the RDN of a removed
189 entry. The reuse of a Unique Identifier can arise by the explicit
190 action of a directory administrator to restore an entry that was
191 mistakenly removed. The mechanism by which an administrator adds an
192 entry with a reused Unique Identifier is outside the scope of the
193 X.500 and LDAP standards since the Unique Identifier of an entry is
194 not a user modifiable attribute. Note that from the perspective of a
195 consumer DSA of a partial area of replication an entry may appear to
196 be removed and added several times because modifications to the entry
197 change whether the entry satisfies the replication agreement
198 specification for the area of replication.
200 Additionally, a deletion record is kept for each of the recently
201 deleted entries, attributes, or attribute values. The deletion record
202 contains a CSN and asserts that the associated directory object no
203 longer existed at the particular time.
205 4.3 Replication Primitives
207 Each update operation performed on an entry in a part of the DIT
208 subject to one or more replication agreements must be subsequently
209 reported as replication primitives to the replication partner DSAs of
210 those agreements. The collection of primitives sent by a DSA to a
211 replication partner may reflect both the results of locally processed
212 user update requests and also of replicated updates received from
213 other DSAs. A single update operation will decompose in one or more
216 Common to all update primitives is an entry identifier argument, uid,
217 containing the Unique Identifier of the target entry of the change,
218 and a CSN argument, csn, to indicate the time of the change. In the
219 case of adding a new entry, the Unique Identifier for the entry is
220 allocated by the DSA in the course of processing the operation.
221 Additional arguments are present depending on the type of replication
224 The p-add-entry(uid, csn, superior, rdn) primitive is used to add a
225 new entry with minimal contents. The superior argument contains the
226 Unique Identifier of the immediate superior entry of the added entry.
227 The rdn argument contains the Relative Distinguished Name of the
232 Legg & Payne Expires 22 April 2000 [Page 4]
238 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
241 The p-move-entry(uid, csn, superior) primitive is used to change the
242 immediate superior of an entry. The superior argument contains the
243 Unique Identifier of the new superior entry.
245 The p-rename-entry(uid, csn, rdn) primitive is used to change the
246 Relative Distinguished Name of an entry. The rdn argument contains
247 the new RDN for the entry.
249 The p-remove-entry(uid, csn) primitive is used to remove an entry.
251 The p-add-attribute-value(uid, csn, type, value) primitive is used to
252 add a single attribute value to an entry. The type argument contains
253 the attribute type of the value and the value argument contains the
256 The p-remove-attribute-value(uid, csn, type, value) primitive is used
257 to remove a single attribute value from an entry. The type argument
258 contains the attribute type of the value and the value argument
259 contains the attribute value.
261 The p-remove-attribute(uid, csn, type) primitive is used to remove
262 all values of an attribute from an entry. The type argument contains
263 the attribute type to be removed.
265 These primitives reflect the intended final state of an update
266 operation rather than the specific changes required to achieve that
271 Each connected set of mastering DSAs have a Lost & Found entry
272 nominated. As a result of conflicting updates at two or more master
273 DSAs, an entry may be left with a reference to a non-existent
274 superior entry. Such an entry is called an orphaned entry. When this
275 situation arises, the DSA creates a glue entry for the missing
276 superior entry. This glue entry is made a subordinate of the Lost &
277 Found entry and the orphaned entry becomes a subordinate of the glue
278 superior entry (see Section 5.3.2). Entries that exist in the Lost &
279 Found subtree may still be modified by actions of the replication
280 protocol since entries are identified by Unique Identifiers in the
281 protocol, independent of their positioning in the global DIT.
283 Entries will also be explicitly moved to become immediate
284 subordinates of the Lost & Found entry to prevent the formation of a
285 loop in the superior-subordinate relationships in the DIT. This
286 situation can only arise through conflicting move entry operations at
287 two or more master DSAs.
292 Legg & Payne Expires 22 April 2000 [Page 5]
298 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
301 Entries that exist under the Lost & Found entry may be returned to a
302 suitable position in the DIT by an administrator or user with
303 appropriate access rights.
305 5. Replication Procedures
307 The procedures defined in this section ensure the consistent and
308 correct application of the results of DAP, LDAP or DSP operations
309 across all multi-master replication DSAs.
311 5.1 Processing LDAP, DAP or DSP Operations on the DIT
313 A successful DAP, LDAP or DSP operation applied to a part of the DIT
314 subject to a replication agreement will create or replace one or more
315 CSNs on an entry or its contents, and create zero, one or more
316 deletion records referencing the entry or its contents. The CSNs and
317 deletion records generated from an operation are atomic with that
318 operation. That is, either the operation succeeds, the CSNS are
319 revised and the deletion records are stored, or the operation fails,
320 no CSNs are revised and no deletion records are stored. In all
321 cases, all current error conditions (i.e. reasons for rejecting an
322 LDAP, DAP or DSP update operation) remain.
324 At some later time, possibly immediately following the update or
325 concurrently with it, the CSNs on entry contents and deletion records
326 are used to generate the replication primitives that will report the
327 update to other DSAs via a replication session.
329 All the CSNs generated from a single update operation must use the
330 same time, change count and Replica Identifier. The modification
331 number is permitted to vary but must be assigned such that when the
332 CSNs resulting from the operation, including those in the deletion
333 records, are compared to the CSNs resulting from any other operation
334 they are all strictly greater than or all strictly less than those
335 other CSNs (i.e. in a global CSN ordering of the primitives
336 resulting from all operations the primitives of each operation must
337 be contiguous in that ordering). In order for the update to be
338 consistently applied when replicated to other DSAs the CSNs generated
339 during that update must generally be greater than any pre-existing
340 CSNs on the updated entry's contents. It is expected that DSAs will
341 normally use the current time according to their system clocks in
342 generating the CSNs for an operation. However in an environment where
343 DSA clocks are not necessarily synchronized the current time may be
344 older than existing CSNs on entry contents. The constraints the new
345 CSNs must satisfy with respect to pre-existing CSNs on entry data are
346 covered in the sections on each type of update operation. The current
347 LDUP architecture draft [LDUP Model] requires client update
348 operations to be rejected if the current time does not satisfy the
352 Legg & Payne Expires 22 April 2000 [Page 6]
358 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
361 constraints on the generation of the CSNs. As written, URP allows a
362 DSA to generate CSNs in advance of its current time to satisfy the
363 constraints and proceed with the update.
365 The LDUP Update Vector mechanism imposes the additional constraint
366 that the CSN generated for an update operation must also be greater
367 than the highest CSN generated by the DSA that has already been seen
368 by any other DSA. An implementation that generates successively
369 greater CSNs for each operation will satisfy this constraint.
371 The following sections describe the additional actions to support
372 replication carried out in processing each particular type of update
377 The LDAP Add operation or DAP addEntry operation is used to add a
378 leaf entry to the DIT. A successful request will generate a CSN for
379 the entry. The CSN on the entry's RDN, the CSN on the entry's
380 superior reference, and the CSN on each distinguished and non-
381 distinguished value added to the entry by the add entry operation are
382 set to this same value. The affected values include any operational
383 attributes automatically generated by the DSA.
385 The Unique Identifier generated for an entry created by a user
386 request is required to be globally unique for all time, so there
387 cannot be a pre-existing entry deletion record for the same Unique
388 Identifier. However it is recognized that, in practice, Directory
389 administrators may need to restore a deleted entry using its original
390 Unique Identifier (the mechanism used to achieve this is undefined
391 and outside the scope of this specification). In this case the CSN
392 for the entry must be generated such that it is greater than or equal
393 to the CSN of any existing entry, attribute or value deletion records
394 and greater than any of the CSNs contained in an existing glue entry,
395 for the same Unique Identifier.
399 The LDAP Delete operation or DAP removeEntry operation is used to
400 remove a leaf entry from the DIT. If the request succeeds then an
401 entry deletion record is stored containing the Unique Identifier of
402 the removed entry. The CSN for the entry deletion record must be
403 generated such that it is greater than the entry CSN of the removed
408 The LDAP Modify operation (ModifyRequest) or DAP modifyEntry
412 Legg & Payne Expires 22 April 2000 [Page 7]
418 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
421 operation is used to perform a series of one or more modifications to
422 an entry. If the request succeeds then zero, one or more new values
423 with CSNs are added to the entry contents, and zero, one or more
424 value or attribute deletion records are stored.
426 The modifications described by the modification argument of the LDAP
427 ModifyRequest have the following additional effects:
429 a) The add alternative associates a CSN with each of the added
432 b) The delete alternative with no listed values generates an
433 attribute deletion record for the removed attribute type.
435 c) The delete alternative with listed values generates a value
436 deletion record for each of the removed values.
438 d) The replace alternative first generates an attribute deletion
439 record for the removed attribute type. A CSN is then associated
440 with each of the added values.
442 The modifications described by the changes argument of the X.500
443 modifyEntry operation have the following additional effects:
445 a) The addAttribute and addValues alternatives associate a CSN
446 with each of the added attribute values. These two alternatives
447 are equivalent from the point of view of URP since there is no CSN
448 associated specifically with the attribute type.
450 b) The removeAttribute alternative generates an attribute deletion
451 record for the removed attribute type.
453 c) The removeValues alternative generates a value deletion record
454 for each of the removed values.
456 d) The alterValues alternative first generates a value deletion
457 record for each of the old values. Secondly, a CSN is associated
458 with each of the new values.
460 e) The resetValues alternative generates a value deletion record
461 for each value actually removed.
463 The CSNs generated by a modify operation must be greater than the CSN
464 of any pre-existing attribute value that is removed, greater than or
465 equal to the CSN of any pre-existing attribute deletion record or
466 value deletion record applying to an added attribute value, and
467 greater than or equal to the CSN of the entry.
472 Legg & Payne Expires 22 April 2000 [Page 8]
478 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
481 A further constraint applies to the modification number component of
482 the CSNs generated by a single modify operation. The CSN generated
483 for an added attribute value must be greater than or equal to the CSN
484 on any applicable value deletion record or attribute deletion record
485 already created by this same operation. This constraint is satisfied
486 if the same modification number is used in all the CSNs generated by
487 a single modify operation, or if the CSNs generated as the sequence
488 of modifications in the operation are applied in order use
489 monotonically increasing modification numbers. The modification
490 numbers need not be consecutive in this case.
492 Whenever a new value is added to the entry contents any value
493 deletion record for the same entry, attribute type and attribute
494 value may be discarded.
498 The LDAP Modify DN operation and DAP modifyDN operation are used to
499 change the Relative Distinguished Name of an entry and/or to move an
500 entry to a new superior in the DIT. If the entry is moved to a new
501 superior in the DIT then the CSN on the entry's superior reference is
502 replaced. If the entry's RDN is changed then the CSN on the entry's
503 RDN is replaced. A value deletion record is stored for each of the
504 formally distinguished attribute values removed from the entry as a
505 consequence of the deleteOldRDN (modifyDN) flag or deleteoldrdn
506 (ModifyDNRequest) flag being set.
508 If the CSN on the entry's superior reference is revised then the new
509 value must be greater than the previous value. If the CSN on the
510 entry's RDN is revised then the new value must be greater than the
511 previous value of the CSN on the RDN. The CSNs for any value
512 deletion records must be greater than the CSNs on the removed
515 5.2 Generating Replication Primitives
517 Each time a replication session is invoked, the supplier DSA must
518 generate and send replication primitives for updates known to the
519 supplier but not yet known to the consumer DSA. The supplier uses the
520 Update Vector of the consumer to determine what to send.
521 Conceptually, the supplier scans all the glue and non-glue entries
522 and deletion records covered by the replication agreement with the
523 consumer and generates primitives where the CSNs held by the supplier
524 are greater than the CSN for the corresponding identified replica in
525 the consumer's Update Vector.
527 A p-add-entry primitive is generated for each entry whose entry CSN
528 is greater than the Update Vector CSN for the same replica. The
532 Legg & Payne Expires 22 April 2000 [Page 9]
538 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
541 superior argument of the p-add-entry primitive contains the Unique
542 Identifier of the immediate superior entry of the added entry. The
543 rdn argument of the p-add-entry primitive contains the Relative
544 Distinguished Name of the created entry except that the Unique
545 Identifier, if distinguished, is always omitted from the RDN. The
546 superior and rdn arguments are provided even if the CSN on the
547 superior reference or the RDN are greater than the CSN on the entry.
549 A p-add-attribute-value primitive is generated for each distinguished
550 value that has a CSN greater than the Update Vector CSN for the same
551 replica and greater than the CSN on the RDN of its entry, and for
552 each non-distinguished value that has a CSN greater than the Update
553 Vector CSN for the same replica. The p-add-attribute-value primitive
554 uses the CSN of the corresponding value. There are no separate
555 primitives generated for the distinguished values that have the same
556 CSN as the CSN on their entry's RDN.
558 If the CSN on an entry's RDN is greater than the Update Vector CSN
559 for the same replica and greater than the CSN on the entry then a p-
560 rename-entry primitive is generated. The CSN for this primitive is
561 the CSN on the entry's RDN and the rdn argument contains the Relative
562 Distinguished Name of the entry.
564 If the CSN on the entry's superior reference is greater than the
565 Update Vector CSN for the same replica and greater than the CSN on
566 the entry then a p-move-entry primitive is generated. The CSN for
567 this primitive is the CSN on the entry's superior reference and the
568 superior argument of the contains the Unique Identifier of the
569 immediate superior entry.
571 A p-remove-attribute-value primitive is generated for each value
572 deletion record having a CSN greater than the Update Vector CSN for
573 the same replica. The primitive uses exactly the same arguments as
574 the value deletion record.
576 A p-remove-attribute primitive is generated for each attribute
577 deletion record having a CSN greater than the Update Vector CSN for
578 the same replica. The primitive uses exactly the same arguments as
579 the attribute deletion record.
581 A p-remove-entry primitive is generated for each entry deletion
582 record having a CSN greater than the Update Vector CSN for the same
583 replica. The primitive uses exactly the same arguments as the entry
586 Rather than scanning the DIT, an implementation may choose to
587 generate replication primitives as the user update requests are being
588 processed and put these primitives into a replication log in
592 Legg & Payne Expires 22 April 2000 [Page 10]
598 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
601 preparation for sending during the next replication session. Any
602 replication primitives generated from an operation in this way MUST
603 be atomic with that operation. That is, either the operation
604 succeeds, and primitives are added to the replication log, or the
605 operation fails, and no primitives are added to the log. The
606 replication log may be filtered prior to sending to eliminate any
607 primitives that are superseded by later primitives in the log, and
608 any primitives having CSNs less than or equal to the relevant CSNs
609 contained in a consumer DSA's Update Vector.
611 In a log based implementation, the p-add-attribute-value primitive
612 supersedes a p-remove-attribute-value primitive for the same entry,
613 attribute type, attribute value and equal or older CSN. It supersedes
614 another p-add-attribute-value primitive for the same entry, attribute
615 type, attribute value and older CSN.
617 The p-remove-attribute-value primitive supersedes a p-add-attribute-
618 value primitive for the same entry, attribute type, attribute value
619 and older CSN. It supersedes another p-remove-attribute-value
620 primitive for the same entry, attribute type, attribute value and
623 The p-remove-attribute primitive supersedes a p-add-attribute-value
624 primitive for the same entry, attribute type and older CSN. It
625 supersedes a p-remove-attribute-value or another p-remove-attribute
626 primitive for the same entry, attribute type and equal or older CSN.
628 The p-remove-entry primitive supersedes a p-add-attribute-value, p-
629 add-entry, p-move-entry or p-rename-entry primitive for the same
630 entry and older CSN. It supersedes a p-remove-attribute-value or p-
631 remove-attribute or another p-remove-entry primitive for the same
632 entry and equal or older CSN.
634 The p-move-entry primitive supersedes another p-move-entry primitive
635 for the same entry and older CSN.
637 5.3 Processing Replication Primitives on the DIT
639 Each replication primitive received from another DSA during a
640 replication session is processed against the DIT.
642 This section defines some commonly used sub-procedures and the
643 algorithms for processing each of the primitives. Components of
644 primitives, entries, attributes and values are referenced with the .
645 operator. In particular the notation X.csn refers to the CSN of the
646 directory object X. The operators, < and > when applied to CSNs, use
647 the convention of CSNs becoming greater with the progression of time,
648 so older CSNs are less than younger CSNs. In the case where the CSN
652 Legg & Payne Expires 22 April 2000 [Page 11]
658 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
661 for object X has been discarded through the purging mechanism, X.csn
662 is assumed to have the least possible CSN value. In some of the
663 procedures a CSN will be explicitly purged. An implementation may
664 instead keep the CSN but set it to some value that is old enough for
665 it to be eligible for purging (e.g. the least possible CSN value)
666 without affecting the correctness of the procedures.
668 For an entry, E, the notation E.rdn refers to the entry's Relative
669 Distinguished Name, E.dn refers to the entry's Distinguished Name,
670 and E.superior refers to the Unique Identifier of the entry's
674 5.3.1 Saving Deletion Records
676 It is necessary for a DSA to remember that some entry, attribute or
677 attribute value has been deleted, for a period after the processing
678 of the update operation or primitive causing the deletion. These
679 records are called deletion records in the sections that follow and
680 are of three kinds: entry deletion records, attribute deletion
681 records and value deletion records.
683 Value deletion records result from, and have the same parameters as,
684 the p-remove-attribute-value primitive. The StoreValueDeletion
685 procedure creates a value deletion record from the actual arguments
686 and stores it for later access by the various primitive processing
687 procedures. When an attribute value is added to an entry, a value
688 deletion record for the same entry, attribute type and value, and
689 with an older CSN, may be discarded.
691 Attribute deletion records result from, and have the same parameters
692 as, the p-remove-attribute primitive. The StoreAttributeDeletion
693 procedure creates an attribute deletion record from the actual
694 arguments and stores it for later access. When an attribute deletion
695 record is stored any value deletion records for the same entry and
696 attribute type, and with equal or older CSNs, may be discarded.
698 Entry deletion records result from, and have the same parameters as,
699 the p-remove-entry primitive. The StoreEntryDeletion procedure
700 creates an entry deletion record from the actual arguments and stores
701 it for later access. When an entry deletion record is stored any
702 value deletion records and attribute deletion records for the same
703 entry, and with equal or older CSNs, may be discarded.
705 Since the deletion records have the same components as their
706 associated remove primitives an implementation may choose to use the
707 same internal structures for both.
712 Legg & Payne Expires 22 April 2000 [Page 12]
718 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
723 Entries are permitted to be re-added and this can lead to situations
724 where applicable primitives are received in the period after an entry
725 is removed but before the arrival of the notification of it being
726 re-added. In these cases a glue entry is created for the Unique
727 Identifier to preserve relevant updates in the event that a p-add-
728 entry primitive with an older CSN is later received for the same
729 entry. A glue entry is upgraded to a normal entry by a subsequent p-
732 A glue entry with no subordinate entries and containing only CSNs (on
733 itself or its component parts) that are eligible to be purged
734 (according to the Purge Vector in LDUP, or the Oldest Time in DMRP)
735 may be removed. A glue entry is discarded if its contents are
736 completely superseded by another p-remove-entry primitive.
738 The CreateGlueEntry function is called when required to create a glue
739 entry as a subordinate of Lost & Found. CreateGlueEntry takes a
740 single parameter which is the Unique Identifier for the glue entry.
741 The Unique Identifier also becomes the RDN for the glue entry. No
742 CSNs are associated with the entry, the entry's superior reference,
743 or the entry's name (or equivalently they are set to the least
746 5.3.3 Generating Change Sequence Numbers
748 There are circumstances where conflicts arise in the processing of a
749 replication primitive. It is necessary in these cases for the DSA
750 processing the primitives to make corrective changes and emit
751 additional primitives to ensure that all other DSAs reach the same
752 consistent state. The GenerateNextCSN function is used to obtain a
753 CSN for the corrective change. An implementation that generates
754 replication primitives as the user update requests are being
755 processed and puts them into a replication log must take the
756 additional step of creating a primitive to convey the corrective
757 change to other DSAs. Implementations that generate primitives by
758 scanning entries will pick up the corrective change automatically.
760 As is the case for CSNs generated from DAP, DSP or LDAP operations, a
761 CSN is typically generated from the current clock time of the DSA.
762 The conditions imposed for the correct operation of the LDUP Update
763 Vector must also be satisfied.
765 GenerateNextCSN takes a single CSN parameter. In addition to all
766 other conditions the CSN generated by the function must be greater
767 than this parameter. Since the CSN parameter passed to
768 GenerateNextCSN is always an actual CSN from some directory object
772 Legg & Payne Expires 22 April 2000 [Page 13]
778 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
781 stored in the local DSA, an implementation may choose to allocate
782 CSNs from an incrementing internal CSN register that is reset after
783 each replication session to a value greater than the largest CSN seen
784 so far, and thereby be safely able to disregard the parameter to
787 5.3.4 Comparison of Attribute Values
789 Values in primitives, in deletion records or in entries are compared
790 using the equality matching rule for the associated attribute type
791 where that type is permitted to be multi-valued. This means that two
792 values that are considered equal may nonetheless have minor
793 differences. For example, two commonName values may be equal, but use
794 different letter case and have different numbers of leading or
795 trailing spaces. Whenever a CSN for some value is refreshed the value
796 is also refreshed using the exact value from the primitive so that
797 all DSAs use exactly the same representation for the value.
799 Compared values for a single-valued attribute type are all considered
800 to be equal even though they may be significantly different according
801 to that attribute type's equality matching rule. In effect the
802 equality operator, '=', in the following procedures is
803 unconditionally true when used to compare values of a single-valued
804 attribute type. Whenever a CSN for the value of a single-valued
805 attribute is refreshed the value is also refreshed using the value
806 from the primitive. One significant consequence is that an entry
807 whose RDN contains a value of a single-valued attribute type is
808 effectively renamed by a p-add-attribute-value primitive with a more
809 recent value for the attribute type.
811 A value in an entry that is replaced by the exact representation from
812 a primitive retains its distinguished or non-distinguished status.
813 This includes replaced values of single-valued attribute types.
817 Independent changes at two or more DSAs can lead to the situation of
818 two distinct entries having the same name. The procedure,
819 CheckUniqueness(E, S, R), takes an entry and determines whether it is
820 uniquely named. If not, it disambiguates the names of the entries by
821 adding the Unique Identifier of each of the conflicting entries to
824 The procedure CheckUniqueness is called in each circumstance where
825 the Relative Distinguished Name of an entry might conflict with
826 another entry, either because the entry has been renamed or because
827 it has been moved to a new superior. An entry can be renamed
828 directly by a p-rename-entry primitive, or as a side-effect of other
832 Legg & Payne Expires 22 April 2000 [Page 14]
838 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
841 primitives causing changes to distinguished values. While each move
842 or rename of an entry potentially causes a conflict with some other
843 entry already having the new Distinguished Name, it also potentially
844 removes a previous conflict on the old Distinguished Name. The
845 enable the CheckUniqueness function to remove the Unique Identifier
846 from an entry's RDN when it is no longer needed the old name for an
847 entry is passed through the second and third parameters. The
848 parameter, S, is the Unique Identifier of the old superior entry of
849 E, and the parameter, R, is the old RDN of E. CheckUniqueness needs
850 to ignore distinguished UniqueIdentifiers when comparing entry RDNs.
851 The function BaseRDN(rdn) returns its argument minus any
852 distinguished UniqueIdentifiers to support these comparisons.
854 CheckUniqueness(E, S, R)
856 make E.uid non-distinguished
857 IF there exists exactly one subordinate entry, C, of S
858 where BaseRDN(C.rdn) = BaseRDN(R)
859 make C.uid non-distinguished
861 make C.uid distinguished
862 ELSE IF there exists a subordinate entry, C, of E.superior
863 where E <> C AND BaseRDN(C.rdn) = BaseRDN(E.rdn)
865 make C.uid distinguished
866 make E.uid distinguished
870 Because updates are performed in isolation at multiple DSAs in a
871 multimaster configuration it is possible to encounter a situation
872 where there is a request to delete a distinguished value in an entry.
873 The recommended practice in these circumstances is to remove the
874 distinguished value and call CheckUniqueness to correct any resulting
875 name conflicts. An implementation may instead reassert the existence
876 of the distinguished value with a more recent CSN to avoid altering
877 the entry's RDN. This option is only available to updatable replicas.
878 Read-only replicas MUST remove the distinguished value. The function
879 ProtectDistinguished() returns true for an updatable part of the DIT
880 in an DSA that implements this option, and false otherwise. DSAs
881 exercising this option must generate p-add-attribute-value primitive
882 so that other DSAs are guaranteed to also reassert the distinguished
883 value. DSAs that implement the option will correctly interwork with
886 The primitives p-add-entry and p-rename-entry contain common elements
887 that are applied to the Relative Distinguished Name of an entry in
888 the same way. This common processing is described in the RenameEntry
892 Legg & Payne Expires 22 April 2000 [Page 15]
898 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
901 procedure. The parameters to this procedure are the entry, E, and the
902 p-add-entry or p-rename-entry primitive specifying the new RDN. The
903 procedure assumes that the entry does not currently contain any
904 distinguished values. It is the responsibility of the calling
905 procedure to first reset any pre-existing distinguished values to
906 non-distinguished. The procedure then resets the CSNs and sets the
907 distinguished flags for existing values and adds distinguished values
908 if necessary. The CSN for the entry's RDN, as distinct from the CSNs
909 on each of the distinguished values making up the RDN, is also set.
913 FOREACH AttributeTypeAndValue, N, in P.rdn
914 IF there exists an attribute value, V, in E of type N.type
919 replace V with N.value if they are not identical
924 ELSE IF ProtectDistinguished()
927 add V to E as a distinguished value
929 FOREACH attribute deletion record (uid, type, csn)
930 where (uid = P.uid AND type = N.type)
933 FOREACH value deletion record (uid, type, value, csn)
934 where (uid = P.uid AND type = N.type AND value = N.value)
937 V.csn := GenerateNextCSN(V.csn)
939 ELSE IF no attribute deletion record (uid, type, csn) exists
940 where (uid = P.uid AND type = N.type AND csn > P.csn)
941 AND no value deletion record (uid, type, value, csn) exists
942 where (uid = P.uid AND type = N.type AND
943 value = N.value AND csn > P.csn)
946 add V to E as a distinguished value
952 Legg & Payne Expires 22 April 2000 [Page 16]
958 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
965 5.3.6 Processing Add Attribute Value Primitive
967 This section describes the algorithm for processing the p-add-
968 attribute-value (P.uid, P.type, P.value, P.csn) primitive, which is
969 responsible for adding a single attribute value.
971 IF no value deletion record (uid, type, value, csn) exists where
972 (uid = P.uid AND type = P.type
973 AND value = P.value AND csn > P.csn)
974 AND no attribute deletion record (uid, type, csn) exists where
975 (uid = P.uid and type = P.type AND csn > P.csn)
976 AND no entry deletion record (uid, csn) exists where
977 (uid = P.uid AND csn > P.csn)
979 IF entry, E, with uid = P.uid does not exist
980 E := CreateGlueEntry(P.uid)
982 IF attribute value V, of type P.type
983 where V = P.value exists in E
989 replace V with P.value if they are not identical
990 IF V is distinguished
991 AND P.type is a single-valued attribute type
992 CheckUniqueness(E, E.superior, R)
998 Add V to E as a non-distinguished attribute value
1004 5.3.7 Processing Remove Attribute Value Primitive
1006 This section describes the algorithm for processing the p-remove-
1007 attribute-value (P.uid, P. type, P.value, P.csn) primitive, which is
1008 responsible for removing a single attribute value. A value that is
1012 Legg & Payne Expires 22 April 2000 [Page 17]
1018 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1021 distinguished is tagged as distinguished-not-present rather than
1022 being immediately removed. Such a value will be physically removed
1023 when it becomes non-distinguished.
1025 IF no value deletion record (uid, type, value, csn) exists
1026 where (uid = P.uid AND type = P.type AND
1027 value = P.value AND csn >= P.csn)
1029 no attribute deletion record (uid, type, csn) exists
1030 where (uid = P.uid AND type = P.type AND csn >= P.csn)
1032 no entry deletion record (uid, csn) exists
1033 where (uid = P.uid AND csn >= P.csn)
1034 IF entry, E, with uid = P.uid exists
1037 IF attribute value, V, of P.type
1038 where V = P.value, exists in E
1041 IF V is distinguished
1042 IF ProtectDistinguished()
1043 V.csn := GenerateNextCSN(P.csn)
1048 CheckUniqueness(E, E.superior, R)
1049 StoreValueDeletion (P.uid, P.type, P.value, P.csn)
1054 StoreValueDeletion (P.uid, P.type, P.value, P.csn)
1058 StoreValueDeletion (P.uid, P.type, P.value, P.csn)
1061 StoreValueDeletion (P.uid, P.type, P.value, P.csn)
1063 The presence of a younger deletion record for the entry, attribute or
1064 value provides a convenient test for whether the p-remove-attribute-
1065 value primitive needs to be processed at all. If the value exists to
1066 be removed then there cannot be a deletion record affecting it that
1067 has a younger CSN. If there is a younger deletion record than the
1068 primitive then there cannot be an older value to remove.
1072 Legg & Payne Expires 22 April 2000 [Page 18]
1078 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1081 5.3.8 Processing Remove Attribute Primitive
1083 This section describes the algorithm for processing the p-remove-
1084 attribute (P.uid, P.type, P.csn) primitive, which is responsible for
1085 removing all attribute values of P.type. Values that are
1086 distinguished are tagged as distinguished-not-present rather than
1087 being immediately removed. Such values will be physically removed
1088 when they become non-distinguished.
1090 IF no attribute deletion record (uid, type, csn) exists
1091 where (uid = P.uid AND type = P.type AND csn >= P.csn)
1092 AND no entry deletion record (uid, csn) exists where
1093 (uid = P.uid AND csn >= P.csn)
1094 IF entry, E, with uid = P.uid exists
1098 FOREACH attribute value, V, of type P.type in E (if any)
1100 IF V is distinguished
1101 IF ProtectDistinguished()
1102 V.csn := GenerateNextCSN(P.csn)
1107 CheckUniqueness(E, E.superior, R)
1111 StoreAttributeDeletion (P.uid, P.type, P.csn)
1115 StoreAttributeDeletion (P.uid, P.type, P.csn)
1118 5.3.9 Processing Add Entry Primitive
1120 This section describes the algorithm for processing the p-add-entry
1121 (P.uid, P.superior, P.rdn, P.csn) primitive, which is responsible for
1122 adding an entry. The CSN on an entry records the time of the latest
1123 p-add-entry primitive for the Unique Identifier. In normal
1124 circumstances there will only ever be one p-add-entry primitive
1125 associated with an entry. The entry CSN may be discarded when it
1126 becomes eligible to be purged according to the Purge Vector.
1128 IF no entry deletion record (uid, csn) exists where
1132 Legg & Payne Expires 22 April 2000 [Page 19]
1138 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1141 (uid = P.uid AND csn > P.csn)
1142 IF entry, E, with uid = P.uid exists
1147 FOREACH attribute value, V, in E
1150 process P according to
1151 p-rename-entry(P.uid, P.rdn, P.csn)
1152 process P according to
1153 p-move-entry(P.uid, P.superior, P.csn)
1162 IF an entry with uid = P.superior does not exist
1163 CreateGlueEntry(P.superior)
1164 E.superior = P.superior
1165 E.superior.csn := P.csn
1167 CheckUniqueness(E, E.superior, E.rdn)
1171 5.3.10 Processing Remove Entry Primitive
1173 This section describes the algorithm for processing the p-remove-
1174 entry (P.uid, P.csn) primitive, which is responsible for removing an
1175 entry. If the target entry has attribute values with CSNs greater
1176 than the primitive's CSN, a superior reference with a greater CSN, or
1177 if it has any subordinate entries, it becomes a glue entry instead of
1178 being removed. Unless it has a CSN for its superior reference that
1179 is greater than the CSN of the p-remove-entry it is also moved to
1182 IF no entry deletion record (uid, csn) exists
1183 where (uid = P.uid AND csn >= P.csn)
1184 IF entry, E, with uid = P.uid exists
1188 IF E.superior.csn >= P.csn
1192 Legg & Payne Expires 22 April 2000 [Page 20]
1198 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1201 OR any value, V, with csn >= P.csn exists
1202 OR E has subordinates
1208 IF E.superior.csn < P.csn
1210 E.superior := LOST_AND_FOUND
1211 purge E.superior.csn
1213 IF E.rdn.csn < P.csn
1215 FOREACH attribute value, V, in E
1218 CheckUniqueness(E, S, R)
1222 StoreEntryDeletion (P.uid, P.csn)
1226 StoreEntryDeletion (P.uid, P.csn)
1229 5.3.11 Processing Move Entry Primitive
1231 This section describes the algorithm for processing the p-move-entry
1232 (P.uid, P.superior, P.csn) primitive, which is responsible for
1233 moving an entry. If the new superior specified by the primitive does
1234 not exist or is a direct or indirect subordinate of the entry being
1235 moved then the entry is moved to Lost & Found instead.
1237 IF no entry deletion record (uid, csn) exists
1238 where (uid = P.uid AND csn > P.csn)
1240 IF entry, E, with uid = P.uid does not exist
1241 E := CreateGlueEntry(P.uid)
1242 IF P.csn > E.superior.csn
1246 IF entry, S, with uid = P.superior does not exist
1247 S := CreateGlueEntry(P.superior)
1248 IF S is not in the subtree of E
1252 Legg & Payne Expires 22 April 2000 [Page 21]
1258 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1262 E.superior := P.superior
1263 E.superior.csn = P.csn
1267 E.superior := LOST_AND_FOUND;
1268 E.superior.csn := GenerateNextCSN(P.csn)
1270 CheckUniqueness(E, O, R)
1275 5.3.12 Processing Rename Entry Primitive
1277 This section describes the algorithm for processing the p-rename-
1278 entry (P.uid, P.rdn, P.csn) primitive, which changes the Relative
1279 Distinguished Name of an entry. A p-rename-entry primitive that is
1280 older than current name of an entry is not simply ignored since it
1281 may contain attribute values that would have been added to the entry
1282 had the primitives arrived in CSN order. These extra values would
1283 now be non-distinguished.
1285 IF no entry deletion record (uid, csn) exists
1286 where (uid = P.uid AND csn >= P.csn)
1288 IF entry, E, with uid = P.uid does not exist
1289 E := CreateGlueEntry(P.uid)
1290 IF P.csn > E.rdn.csn
1293 FOREACH distinguished attribute value, V, in entry E
1294 make V non-distinguished
1296 CheckUniqueness(E, E.superior, R)
1299 FOREACH AttributeTypeAndValue, N, in P.rdn
1301 IF there exists an attribute value, V, in E of type
1302 N.type AND V = N.value
1306 replace V with N.value if they are not identical
1312 Legg & Payne Expires 22 April 2000 [Page 22]
1318 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1324 IF no value deletion record (uid, type, value, csn)
1325 exists where (uid = P.uid AND type = N.type AND
1326 value = N.value AND csn > P.csn)
1328 no attribute deletion record (uid, type, csn)
1329 exists where (uid = P.uid AND type = N.type AND
1341 6. Security Considerations
1348 The authors would like to thank Suellen Faulks, Tony Robertson and
1349 Mark Ennis from Telstra Research Laboratories who contributed to the
1350 design and verification of the procedures described in this document.
1352 The authors would also like to thank the members of the LDUP
1353 architecture group for their input into the refinement of the design.
1358 [LDUP Model] - E. Reed, "LDUP Replication Architecture", Internet
1359 Draft, draft-merrells-ldup-model-01.txt, November 1998.
1361 [BCP-11] - R. Hovey, S. Bradner, "The Organizations Involved in the
1362 IETF Standards Process", BCP 11, RFC 2028, October 1996.
1365 9. Intellectual Property Notice
1367 The IETF takes no position regarding the validity or scope of any
1368 intellectual property or other rights that might be claimed to
1372 Legg & Payne Expires 22 April 2000 [Page 23]
1378 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1381 pertain to the implementation or use of the technology described in
1382 this document or the extent to which any license under such rights
1383 might or might not be available; neither does it represent that it
1384 has made any effort to identify any such rights. Information on the
1385 IETF's procedures with respect to rights in standards-track and
1386 standards-related documentation can be found in BCP-11. [BCP-11]
1387 Copies of claims of rights made available for publication and any
1388 assurances of licenses to be made available, or the result of an
1389 attempt made to obtain a general license or permission for the use of
1390 such proprietary rights by implementors or users of this
1391 specification can be obtained from the IETF Secretariat.
1393 The IETF invites any interested party to bring to its attention any
1394 copyrights, patents or patent applications, or other proprietary
1395 rights which may cover technology that may be required to practice
1396 this standard. Please address the information to the IETF Executive
1400 10. Copyright Notice
1402 Copyright (C) The Internet Society (1999). All Rights Reserved.
1404 This document and translations of it may be copied and furnished to
1405 others, and derivative works that comment on or otherwise explain it
1406 or assist in its implementation may be prepared, copied, published
1407 and distributed, in whole or in part, without restriction of any
1408 kind, provided that the above copyright notice and this paragraph are
1409 included on all such copies and derivative works. However, this
1410 document itself may not be modified in any way, such as by removing
1411 the copyright notice or references to the Internet Society or other
1412 Internet organizations, except as needed for the purpose of
1413 developing Internet standards in which case the procedures for
1414 copyrights defined in the Internet Standards process must be
1415 followed, or as required to translate it into languages other than
1418 The limited permissions granted above are perpetual and will not be
1419 revoked by the Internet Society or its successors or assigns.
1421 This document and the information contained herein is provided on an
1422 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
1423 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
1424 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
1425 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
1426 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
1432 Legg & Payne Expires 22 April 2000 [Page 24]
1438 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1441 11. Authors' Address
1444 Telstra Research Laboratories
1446 Clayton, Victoria 3168
1449 Phone: +61 3 9253 6771
1450 Fax: +61 3 9253 6485
1451 EMail: s.legg@trl.telstra.com.au
1454 PricewaterhouseCoopers
1455 St Jakobs Strasse 25
1459 Phone: +41-79-458 4177
1460 EMail: alison.b.payne@ch.pwcglobal.com
1462 12. Appendix A - Changes From Previous Drafts
1464 12.1 Changes in Draft 01
1466 Some of the terminology has been changed to better align with the
1467 terminology used in the LDUP architecture draft.
1469 Descriptions on the usage of CSNs have been revised to account for
1470 the extra modification number component.
1472 The semantics of re-added entries has been simplified so that only
1473 changes after the latest re-add are preserved instead of all those
1474 after the earliest re-add. This eliminates the need for Addition CSNs
1475 in the entry. It is anticipated that new replication primitives will
1476 be introduced to manage entries that come and go from partial
1477 replicas instead of using p-add-entry and p-remove-entry.
1479 Orphaned entries are no longer moved directly to Lost & Found.
1480 Instead a glue entry is created in Lost & Found for the missing
1481 superior and the orphaned entry becomes a subordinate of that. This
1482 change eliminates the need for explicit propagated primitives for
1483 moving orphaned entries to Lost & Found.
1485 Glue entries have also been used as the mechanism for saving
1486 primitives. There are no longer any references to saved primitives
1487 though the functionality is still present.
1492 Legg & Payne Expires 22 April 2000 [Page 25]
1498 INTERNET-DRAFT LDUP Update Reconciliation Procedures October 22, 1999
1501 The procedures for processing received replication primitives have
1502 been rearranged to follow a more consistent pattern where the
1503 presence of deletion records is tested first.
1505 12.2 Changes in Draft 02
1507 Multimaster replication has been dropped as a work item for the next
1508 edition of X.500 so references to the proposed X.500 multimaster
1509 replication protocol have been removed.
1511 The treatment of distinguished values has been simplified. Previously
1512 an attempt to remove a distinguished value caused the value to be
1513 tagged distinguished-not-present. Now the distinguished value is
1514 removed, and if necessary, the Unique Identifier is made
1515 distinguished to avoid an empty RDN. Optionally, the value to be
1516 removed can be reasserted by emitting an explicit p-add-attribute-
1519 The current draft is more implementation neutral. A replication log
1520 no longer figures prominently in the specification. The previous
1521 descriptions had the user updates generating replication primitives,
1522 which in turn were used to determine the CSNs and deletion records.
1523 The new descriptions have user updates generating CSNs and deletion
1524 records and the primitives are subsequently generated from them.
1526 13. Appendix B - Open Issues
1528 The precise location of the Lost & Found entry has not yet been
1531 Extensions to the algorithms to properly deal with partial replicas
1532 are still to be decided.
1534 The draft needs some editing to use MAY, MUST, etc, in the proper
1552 Legg & Payne Expires 22 April 2000 [Page 26]