One document matched: draft-ietf-ldup-urp-00.txt
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 <ldup@imc.org> 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]
| PAFTECH AB 2003-2026 | 2026-04-24 02:52:48 |