[Date Prev][Date Next]
[Chronological]
[Thread]
[Top]
draft-ietf-ldup-model-05.txt resend
Don't know why this isn't getting through the ldup mailing exploder...so we're forwarding it to the ldapext list to try to cover the ldupers who lurk on both lists.
The attached document won't actually be published by the internet drafts editors because the folks running the show have actually instituted an automated cut-off that bounces anything you submit after their deadline telling you you can simply amuse yourself until after December 10th. How amusing.
This document has been reved and edited. The information model will be revised in line with this document.
We've changed the term for the partition of the directory namespace from Naming Context, which has conventionally meant something about portitions of the namespace held on a server, to Replication Context, several of which may make up the Naming Context on a given server.
Sorry I missed the deadline, folks.
Ed
INTERNET-DRAFT
draft-ietf-ldup-model-05.txt
John Merrells
Netscape Communications Corp.
Ed Reed
Reed-Matthews, Inc.
Uppili Srinivasan
Oracle, Inc.
December 11, 2000
Copyright (C) The Internet Society (1998,1999,2000). All
Rights Reserved.
LDAP Replication Architecture
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 made obsolete 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, file name draft-ietf-ldup-model-04.txt, is
intended to be become a Proposed Standard RFC, to be
published by the IETF Working Group LDUP. Distribution of
this document is unlimited. Comments should be sent to the
LDUP Replication mailing list <ldup@imc.org> or to the
authors.
This Internet-Draft expires on 11 June 2001
Merrells, Reed, Srinivasan [Page 1]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
1. Abstract
This architectural document outlines a suite of schema and
protocol extensions to LDAPv3 that enables the robust,
reliable, server-to-server exchange of directory content and
changes.
The key words "MUST", "MUST NOT", "REQUIRED", "SHALL",
"SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY",
and "OPTIONAL" in this document are to be interpreted as
described in RFC 2119 [RFC2119]. The sections below
reiterate these definitions and include some additional
ones.
Merrells, Reed, Srinivasan [Page 2]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
2. Table of Contents
1. ABSTRACT ........................................................2
2. TABLE OF CONTENTS ...............................................3
3. INTRODUCTION ....................................................6
3.1 SCOPE .........................................................6
3.2 DOCUMENT OBJECTIVES ...........................................7
3.3 DOCUMENT NON-OBJECTIVES .......................................7
3.4 EXISTING IMPLEMENTATIONS ......................................8
3.4.1 Replication Log Implementations ............................9
3.4.2 State-Based Implementations ................................9
3.5 TERMS AND DEFINITIONS .........................................9
3.6 CONSISTENCY MODELS ...........................................11
3.7 LDAP CONSTRAINTS .............................................12
4. DIRECTORY MODEL ................................................13
4.1 REPLICA TYPE .................................................13
4.1.1 Primary Replica ...........................................13
4.1.2 Updateable Replica ........................................13
4.1.3 Read-Only Replica .........................................13
4.1.4 Fractional Replicas .......................................14
4.2 SUB-ENTRIES ..................................................14
4.3 GLUE ENTRIES .................................................14
4.4 UNIQUE IDENTIFIERS ...........................................14
4.5 CHANGE SEQUENCE NUMBER .......................................14
4.5.1 CSN Composition ...........................................15
4.5.2 CSN Representation ........................................15
4.5.3 CSN Generation ............................................16
4.6 STATE CHANGE INFORMATION .....................................16
4.6.1 Entry Change State Storage and Representation .............17
4.6.2 Attribute Change State Storage ............................18
4.6.3 Attribute Value Change State Storage ......................18
4.7 LDAP UPDATE OPERATIONS .......................................18
5. INFORMATION MODEL ..............................................19
5.1 ENTRIES, SEMANTICS AND RELATIONSHIPS .........................19
5.2 ROOT DSE ATTRIBUTES ..........................................20
5.3 REPLICATION CONTEXT AUXILIARY OBJECT CLASS AND ENTRIES .......21
Merrells, Reed, Srinivasan [Page 3]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
5.4 REPLICA OBJECT CLASS AND ENTRIES .............................21
5.5 LOST AND FOUND ENTRY .........................................21
5.6 REPLICATION AGREEMENT OBJECT CLASS AND ENTRIES ...............22
5.6.1 Replication Schedule ......................................23
6. REPLICATION OF DIRECTORY ADMINISTRATIVE POLICY INFORMATION .....23
6.1 SCHEMA KNOWLEDGE .............................................24
7. LDUP UPDATE TRANSFER PROTOCOL FRAMEWORK ........................25
7.1 REPLICATION SESSION INITIATION ...............................25
7.1.1 Authentication ............................................25
7.1.2 Consumer Initiated ........................................26
7.1.3 Supplier Initiated ........................................26
7.2 START REPLICATION SESSION ....................................26
7.2.1 Start Replication Request .................................26
7.2.2 Start Replication Response ................................26
7.3 UPDATE TRANSFER ..............................................27
7.4 END REPLICATION SESSION ......................................27
7.5 INTEGRITY & CONFIDENTIALITY ..................................27
8. LDUP UPDATE PROTOCOLS ..........................................28
8.1 REPLICATION UPDATES AND UPDATE PRIMITIVES ....................28
8.2 FRACTIONAL UPDATES ...........................................28
9. LDUP FULL UPDATE TRANSFER PROTOCOL .............................29
9.1 FULL UPDATE TRANSFER .........................................29
9.2 REPLICATION UPDATE GENERATION ................................29
9.3 REPLICATION UPDATE CONSUMPTION ...............................29
9.4 FULL UPDATE, END REPLICATION SESSION .........................29
9.5 INTERRUPTED TRANSMISSION .....................................30
10. LDUP INCREMENTAL UPDATE TRANSFER PROTOCOL .....................30
10.1 UPDATE VECTOR ..............................................30
10.2 SUPPLIER INITIATED, INCREMENTAL UPDATE, START REPLICATION
SESSION ...........................................................32
10.3 REPLICATION UPDATE GENERATION ..............................32
10.3.1 Replication Log Implementation ..........................32
10.3.2 State-Based Implementation ..............................32
10.4 REPLICATION UPDATE CONSUMPTION .............................33
10.5 UPDATE RESOLUTION PROCEDURES ...............................33
10.5.1 URP: Distinguished Names ................................34
10.5.2 URP: Orphaned Entries ...................................34
10.5.3 URP: Schema - Single Valued Attributes ..................34
Merrells, Reed, Srinivasan [Page 4]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
10.5.4 URP: Schema - Required Attributes .......................34
10.5.5 URP: Schema - Extra Attributes ..........................35
10.5.6 URP: Duplicate Attribute Values .........................35
10.5.7 URP: Ancestry Graph Cycle ...............................35
10.6 INCREMENTAL UPDATE, END REPLICATION SESSION ................35
10.7 INTERRUPTED TRANSMISSION ...................................36
11. PURGING STATE INFORMATION .....................................36
11.1 PURGE VECTOR ...............................................37
11.2 PURGING DELETED ENTRIES, ATTRIBUTES, AND ATTRIBUTE VALUES ..37
12. REPLICATION CONFIGURATION AND MANAGEMENT ......................37
13. TIME ..........................................................39
14. SECURITY CONSIDERATIONS .......................................40
15. ACKNOWLEDGEMENTS ..............................................41
16. REFERENCES ....................................................41
17. INTELLECTUAL PROPERTY NOTICE ..................................42
18. COPYRIGHT NOTICE ..............................................42
19. AUTHORS' ADDRESS ..............................................43
20. APPENDIX A _ LDAP CONSTRAINTS .................................44
20.1 LDAP CONSTRAINTS CLAUSES ...................................44
20.2 LDAP DATA MODEL CONSTRAINTS ................................46
20.3 LDAP OPERATION BEHAVIOUR CONSTRAINTS .......................46
20.4 NEW LDAP CONSTRAINTS .......................................48
20.4.1 New LDAP Data Model Constraints .........................48
20.4.2 New LDAP Operation Behaviour Constraints ................48
Merrells, Reed, Srinivasan [Page 5]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
3. Introduction
3.1 Scope
This architectural document provides an outline of an LDAP
based replication scheme. Further detailed design documents
will draw guidance from here.
The design proceeds from prior work in the industry,
including concepts from the ITU-T Recommendation X.525
(1993, 1997) Directory Information Shadowing Protocol (DISP)
[X525], experience with widely deployed distributed
directories in network operating systems, electronic mail
address books, and other database technologies. The
emphasis of the design is on:
1. Simplicity of operation.
2. Flexibility of configuration.
3. Manageability of replica operations among mixed
heterogeneous vendor LDAP servers under common
administration.
4. Security of content and configuration information when
LDAP servers from more than one administrative authority
are interconnected.
A range of deployment scenarios is supported, including
multi-master and single-master topologies. Replication
networks may include transitive and redundant relationships
between LDAP servers.
The controlling framework used to define the relationships,
types, and state of replicas of the directory content is
defined. In this way the directory content can itself be
used to monitor and control the replication network. The
directory schema is extended to define object classes,
auxiliary classes, and attributes that describe areas of the
namespace which are replicated, LDAP servers which hold
replicas of various types for the various partitions
(_Replication Contexts_) of the namespace, LDAP Access
Points (network addresses) where such LDAP servers may be
contacted, which namespace replicas are held on given LDAP
servers, and the progress of replication operations. Among
other things, this knowledge of where directory content is
Merrells, Reed, Srinivasan [Page 6]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
located could serve as the basis for dynamic generation of
LDAP referrals.
An update transfer protocol, which actually brings a replica
up to date with respect to changes in directory content at
another replica, is defined using LDAPv3 protocol
extensions. The representation of directory content and
changes will be defined by the LDAP Replication Update
Transfer Protocol sub-team. Incremental and full update
transfer mechanisms are described. Replication protocols
are required to include initial population, change updates,
and removal of directory content.
Security information, including access control policy will
be treated as directory content by the replication
protocols. Confidentiality and integrity of replication
information is required to be provided by lower-level
transport/session protocols such as IPSEC and/or TLS.
3.2 Document Objectives
The objectives of this document are:
a) To define the architectural foundations for LDAP
Replication, so that further detailed design documents
may be written. For instance, the Information Model,
Update Transfer Protocol, and Update Resolution
Procedures documents.
b) To provide an architectural solution for each clause of
the requirements document [LDUP Requirements].
c) To preserve the LDAP Data Model and Operational Behavior
constraints defined for LDAP in RFC 2251 [See Appendix
A].
d) To avoid tying the LDUP working group to the schedule of
any other working group.
e) Not to infringe upon known registered intellectual
property rights.
3.3 Document Non-Objectives
This document does not address the following issues, as they
are considered beyond the scope of the Working Group.
Merrells, Reed, Srinivasan [Page 7]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
a) How LDAP becomes a distributed directory. There are many
issues beyond replication that should be considered. Such
as, support for external references, algorithms for
computing referrals from the distributed directory
knowledge, etc.
b) Specifying management protocols to create Replication
Contexts or new Replicas. LDAP may be sufficient for
this. The document describes how new Replication Contexts
and Replicas are represented, in the directory, as
entries, attributes, and attribute values.
c) How transactions will be replicated. However, the
architecture should not knowingly prevent or impede them,
given the Working Group's incomplete understanding of the
issues at this time.
d) The mapping or merging of disparate Schema definitions.
e) Support of overlapping replicated regions.
f) The case where separate attributes of an entry may be
mastered by different LDAP servers. This might be termed
a 'Split Primary'. Replica roles are defined in section
4.1.
g) The specification of a replication system that supports
Sparse Replication. A Sparse Replica contains a subset of
the entries defined by a Replication Context, identified
by an Entry Selection Filter criteria associated with the
replica. An Entry Selection Filter is an LDAP filter
expression that describes the entries to be replicated.
The design and implementation of this functionality is
not yet well enough understood to specify here.
3.4 Existing Implementations
In order to define a standard replication scheme that may be
readily implemented we must consider the architectures of
current LDAP server implementations. Existing systems
currently support proprietary replication schemes based on
one of two general approaches: log-based or state-based.
Some sections of this text may specifically address the
concerns of one approach. They will be clearly marked.
Merrells, Reed, Srinivasan [Page 8]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
3.4.1 Replication Log Implementations
Implementations based on the original University of Michigan
LDAP server code record LDAP operations to a operation log.
During a replication session operations are replayed from
this log to bring the Consumer replica up to date. Example
implementations of this type at this time are the Innosoft,
Netscape, and Open LDAP Directory Servers.
3.4.2 State-Based Implementations
Directory Server implementations from Novell and Microsoft
at this time do not replay LDAP operations from a operation
log. When a replication session occurs each entry in the
Replicated Area is considered in turn, compared against the
update state of the Consumer, and any resultant changes
transmitted. These changes are a set of assertions about the
presence or absence of entries, attributes, and their
values.
3.5 Terms and Definitions
The definitions from the Replication Requirements document
have been copied here and extended.
For brevity, an LDAP server implementation is referred to
throughout as 'the server'.
The LDAP update operations; Add, Delete, Modify, Modify RDN
(LDAPv2) and Modify DN (LDAPv3), are collectively referred
to as LDAP Update Operations.
A Naming Context is a subtree of entries in the Directory
Information Tree (DIT). There may be multiple Naming
Contexts stored on a single server. Naming Contexts are
defined in section 17 of [X501].
A _Replication Context_ represents a section of DIT defining
a unit of administration for replication. A Replication
Context is based at an entry identified as its root and
includes all its subordinate entries down the tree to its
leaves, or until another Replication Context is encountered.
A Naming Context held by a server may be made up of one or
more non-overlapping Replication Contexts. Non-replicated
portions of a Naming Context may not be explicitly
identified as a Replication Context, although implicitly
Merrells, Reed, Srinivasan [Page 9]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
they are part of a primary Replica with no Replication
Agreements.
A Replica is a replicated instance of a _Replication
Context_. .
A _Replication Context_ is said to be single-mastered if
there is only one Replica where it may be updated, and
multi-mastered if there is more than one Replica where it
may be updated.
A Replication Relationship is established between two or
more Replicas that are hosted on servers that cooperate to
service a common area (the Replication Context) of the DIT.
A Replication Agreement is defined between two parties of a
Replication Relationship. A Replication Agreement is
associated with a set of replicas and defines properties
such as the Update Transfer Protocol to be used, and the
Replication Schedule of a Replication Session.
A Replication Session is an LDAP session between the two
servers identified by a replication agreement. Interactions
occur between the two servers, resulting in the transfer of
updates from the supplier replica to the consumer replica.
The Initiator of a Replication Session is the initiating
server.
A Responder server responds to the replication initiation
request from the Initiator server.
A Supplier server is the source of the updates to be
transferred.
A Consumer server is the recipient of the update sequence.
The Update Transfer Protocol is the means by which the
Replication Session proceeds. It defines the protocol for
exchanging updates between the Replication Relationship
partners.
A Replication Update is an LDAP Extended Operation that
contains updates to be applied to the DIT. The Update
Transfer Protocol carries a sequence of these messages from
the Supplier to the Consumer.
Merrells, Reed, Srinivasan [Page 10]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
The Update Resolution Procedures repair constraint
violations that occur when updates to a multi-mastered
Replica collide.
A Fractional Entry Specification is a list of entry
attributes to be included, or a list of attributes to be
excluded in a replica. An empty specification implies that
all entry attributes are included.
A Fractional Entry is an entry that contains only a subset
of its original attributes. It results from the replication
of changes governed by a Fractional Entry Specification.
A Fractional Replica is a replica that holds Fractional
Entries of its Replication Context.
3.6 Consistency Models
This replication architecture supports a loose consistency
model between replicas of a naming context. It does not
attempt to provide the appearance of a single copy of a
replica. The contents of each replica may be different, but
over time they will be converging towards the same state.
This architecture is not intended to support LDAP Clients
that require a tight consistency model, where the state of
all replicas is always equivalent.
Three levels of consistency are available to LDAP Clients,
which are characterized by their deployment topologies.
Single-Server, where there is just the Replication Context
and no replicas. Single-master, where there are replicas,
but only one may be updated. And, multi-master, where there
is more than one replica to which LDAP update operations may
be directed. The consistency properties of each model are
rooted in their serialization of read and write operations.
1) A single-server deployment of a Replication Context
provides tight consistency to LDAP applications. LDAP
Clients have no choice but to direct all their operations to
a single server, serializing both read and write operations.
2) A single-mastered deployment of a Replication Context
provides both tight and loose consistency to LDAP
applications. LDAP Clients must direct all write operations
to the single updateable replica, but may direct their reads
to any of the replicas. A client experiences tight
consistency by directing all its operations to the single
Merrells, Reed, Srinivasan [Page 11]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
updateable replica, and loose consistency by directing any
read operations to any other replica.
3) A multi-mastered deployment of a Replication Context can
provide only loose consistency to LDAP applications. Across
the system writes and reads are not serialized. An LDAP
Client could direct their read and write operations to a
single updateable replica, but they will not receive tight
consistency as interleaved writes could be occurring at
another replica.
Tight consistency can be achieved in a multi-master
deployment for a particular LDAP application if and only if
all instances of its client are directed towards the same
updateable replica, and the application data is not updated
by any other LDAP application. Introducing these constraints
to an application ensures that writes are serialized
providing tight consistency for the application.
Future work could make use of the architecture proposed in
this document as a basis for allowing clients to request
session guarantees from a server when establishing a
connection.
3.7 LDAP Constraints
The LDAP-v3 Internet RFC [LDAPv3] defines a set of Data
Model and Operation Behavior constraints that a compliant
LDAP server must enforce. The server must reject an LDAP
Update Operation if its application to the target entry
would violate any one of these LDAP Constraints. [Appendix A
contains the original text clauses from RFC 2251, and also a
summary.]
In the case of a single-server or single-mastered
Replication Context all LDAP Constraints are immediately
enforced at the single updateable replica. An error result
code is returned to an LDAP Client that presents an
operation that would violate the constraints.
In the case of a multi-mastered Replication Context not all
LDAP Constraints can be immediately enforced at the
updateable replica to which the LDAP Update Operation is
applied. This loosely consistent replication architecture
ensures that at each replica all constraints are imposed,
but as updates are replicated constraint violations arise
that cannot be reported to the appropriate client. Any
Merrells, Reed, Srinivasan [Page 12]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
constraint violations that occur are repaired by a set of
update resolution procedures.
Any LDAP client that has been implemented to expect
immediate enforcement of all LDAP Constraints may not behave
as expected against a multi-mastered Replication Context.
4. Directory Model
This section describes extensions to the LDAP Directory
Model that are required by this replication architecture.
4.1 Replica Type
Each Replica is characterized with a replica type. This may
be Primary, Updateable, or Read-Only. A Read-Only Replica
may be further defined as being Fractional.
4.1.1 Primary Replica
The Primary Replica is a full copy of the Replica, to which
all applications that require tight consistency should
direct their LDAP Operations. There can be only one Primary
Replica within the set of Replicas of a given Replication
Context. It is also permissible for none of the Replicas to
be designated the Primary. The Primary Replica MUST NOT be a
Fractional Replica.
4.1.2 Updateable Replica
An Updateable Replica is a Replica that accepts all the LDAP
Update Operations, but is not the Primary Replica. There
could be none, one, or many Updateable Replicas within the
set of Replicas of a given Replication Context. An
Updateable Replica MUST NOT be a Fractional Replica.
4.1.3 Read-Only Replica
A Read-Only Replica will accept only non-modifying LDAP
operations. All modification operations shall be referred
to an updateable Replica. The server referred to would
usually be a Supplier of this Replica.
Merrells, Reed, Srinivasan [Page 13]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
4.1.4 Fractional Replicas
Fractional Replicas must always be Read-Only. All LDAP
Update Operations must be referred to an Updateable Replica.
The server referred to would usually be a Supplier of this
Fractional Replica.
4.2 Sub-Entries
Replication management entries are to be stored at the base
of the Replication Context. They will be of a
`ldapSubentry' objectclass to exclude them from regular
searches. Entries with the objectclass ldapSubentry are not
returned as the result of a search unless a control is
included in the request to make them visible, or the filter
component "(objectclass=`ldapSubentry')" is included in the
search filter.
4.3 Glue Entries
A glue entry is an entry that contains knowledge of its name
only. No other information is held with it. Such glue
entries will be distinguished through a special object class
defined for that purpose. Glue entries may be created during
a replication session to repair a constraint violation.
4.4 Unique Identifiers
Distinguished names can change, so are therefore unreliable
as identifiers. A Unique Identifier must therefore be
assigned to each entry as it is created. This identifier
will be stored as an operational attribute of the entry,
named `entryUUID'. The entryUUID attribute is single valued.
A consistent algorithm for generating such unique
identifiers should be defined for use in the LDUP standards
documents that detail the LDUP information model and LDUP
protocols.
4.5 Change Sequence Number
Change Sequence Numbers (CSNs) are used to impose a total
ordering upon the causal sequence of updates applied to all
the replicas of a Replication Context. Every LDAP Update
Operation is assigned at least one CSN. A Modify operation
MUST be assigned one CSN per modification.
Merrells, Reed, Srinivasan [Page 14]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
4.5.1 CSN Composition
A CSN is formed of four components. In order of
significance they are; the time, a change count, a Replica
Identifier, and a modification number. The CSN is composed
thus to ensure the uniqueness of every generated CSN. When
CSNs are compared to determine their ordering they are
compared component by component: first the time, then the
change count, then the replica identifier, and finally the
modification number.
The time component is a year-2000-safe representation of the
real world time, with a granularity of one second.
Because many LDAP Update Operations, at a single replica,
may be applied to the same data in a single second, the
change count component of the CSN is provided to further
order the changes. Each replica maintains a count of LDAP
update operations applied against it. It is reset to zero at
the start of each second, and is monotonically increasing
within that second, incremented for each and every update
operation. Should LDAP Update Operations occur at different
replicas, to the same data, within the same single second,
and happen to be assigned the same change count number, then
the Replica Identifier is used to further order the changes.
The Replica Identifier is the value of the RDN attribute on
the Replica Subentry that represents the Replica. The
Replica Identifier could be assigned programmatically or
administratively, in either case short values are advised to
minimize resource usage. The IA5CaseIgnoreString syntax is
used to compare and order Replica Identifier values.
The fourth and final CSN component, the modification number,
is used for ordering the modifications within an LDAP Modify
operation.
4.5.2 CSN Representation
The preferred CSN representation is: yyyy mm dd hh:mi:ssz #
0xSSSS # replica id # 0xssss
The `z' in the time stipulates that the time is expressed in
GMT without any daylight savings time offsets permitted, and
the 0xssss represents the hexadecimal representation of an
unsigned integer. Implementations must support 16 bit change
counts and should support longer ones (32, 64, or 128 bits).
Merrells, Reed, Srinivasan [Page 15]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
An example CSN would be " 1998081018:44:31z#0x000F#1#0x0000
". The update assigned this CSN would have been applied at
time 1998081018:44:31z happened to be the 16th operation
which was applied in that second, was made against the
replica with identifier `1', and was the first modification
of the operation that caused the change.
4.5.3 CSN Generation
Because Change Sequence Numbers are primarily based on
timestamps, clock differences between servers can cause
unexpected change ordering. The synchronization of server
clocks is not required, though it is preferable that clocks
are accurate. If timestamps are not accurate, and a server
consistently produces timestamps that are significantly
older than those of other servers, its updates will not have
effect and the real world time ordering of updates will not
be maintained.
However, an implementation may choose to require clock
synchronization. The Network Time Protocol [NTP] [SNTP]
offers a protocol means by which heterogeneous server hosts
may be time synchronized.
The modifications that made up an LDAP Modify operation are
presented in a sequence. This must be preserved when the
resultant changes of this operation are replicated.
4.5.3.1 CSN Generation _ Log Based Implementation
The modification number component may not be required, since
the ordering of the modifications within an LDAP Modify
operation have been preserved in the operation log.
4.5.3.2 CSN Generation _ State Based Implementation
The modification number component may be needed to ensure
that the order of the modifications within an LDAP Modify
operation is faithfully replicated.
4.6 State Change Information
State changes can be introduced via either LDAP Update
Operations or via Replication Updates. A CSN is included
Merrells, Reed, Srinivasan [Page 16]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
with all changes made to an entry, its attributes, and
attribute values. This state information must be recorded
for the entry to enable a total ordering of updates. The CSN
recorded is the CSN assigned to the state change at the
server where the state change was first made. CSNs are only
assigned to state changes that originate from LDAP Update
Operations.
Each of the LDAP Update Operations changes their target
entry in different ways, and record the CSN of the change
differently. The state information for the resultant state
changes is recorded at three levels. The entry level,
attribute level, and attribute value level. The state change
may be shown through:
1) The creation of a deletion CSN for the entry, an
attribute, or an attribute value.
2) In the addition of a new entry, attribute or attribute
value, and its existence CSN.
3) An update to an existing attribute, attribute value,
entry distinguished name, or entry superior name, and its
update CSN.
4.6.1 Entry Change State Storage and Representation
When an entry is created, with the LDAP Add operation, the
CSN of the change is added to the entry as the value of an
operational attribute named 'createdEntryCSN', of syntax
type LDAPChangeSequenceNumber.
createdEntryCSN ::= csn
Deleted entries are marked as deleted by the addition of the
object class 'deletedEntry'. The attribute
'deletedEntryCSN', of syntax type LDAP Change Sequence
Number, is added to record where and when the entry was
deleted. Deleted entries are not visible to LDAP clients -
they may not be read, they don't appear in lists or search
results, and they may not be changed once deleted. Names of
deleted entries are available for reuse by new entries
immediately after the deleted entry is so marked. It may be
desirable to allow deleted entries to be accessed and
manipulated by management and data recovery applications,
but that is outside the scope of this document.
Merrells, Reed, Srinivasan [Page 17]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
deletedEntryCSN ::= csn
A CSN is recorded for both the RDN, and the Superior DN of
the entry.
4.6.2 Attribute Change State Storage
When all values of an attribute have been deleted, the
attribute is marked as deleted and the CSN of the deletion
is recorded. The deleted state and CSN are stored by the
server, but have no representation on the entry, and may not
be the subject of a search operation. This state information
must be stored to enable the Update Resolution Procedures to
be performed. It may be desirable to allow the deleted
state and CNS information to be accessed and manipulated by
management and data recovery applications, but that is
outside the scope of this document.
4.6.3 Attribute Value Change State Storage
The Modification CSN for each value is to be set by the
server when it accepts a modification request to the value,
or when a new value with a later Modification CSN is
received via Replication. The modified value and the
Modification CSN changes are required to be atomic, so that
the value and its Modification CSN cannot be out of synch on
a given server. The server stores the state information,
but it has no representation on the entry, and may not be
the subject of a search operation. It may be desirable to
allow the state information to be accessed and manipulated
by management and data recovery applications, but that is
outside the scope of this document.
When the value of an attribute is deleted the state of its
deletion must be recorded, with the CSN of the modifying
change. It must be stored to enable the Update Resolution
Procedures to be performed.
4.7 LDAP Update Operations
The server must reject LDAP client update operations with a
CSN that is older than the state information that would be
replaced if the operation were performed. This could occur
in a replication topology where the difference between the
clocks of updateable replicas was too large.
Merrells, Reed, Srinivasan [Page 18]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
5. Information Model
This section describes the object classes of the entries
that represent the replication topology. The operational
information for replication is administered through these
entries. The LDUP Working Group will work towards defining
an Internet standard to fully detail all these schema
elements.
5.1 Entries, Semantics and Relationships
This section defines the organization of operational data
for directory replication in terms of the relative placement
of the entries that represent Replication Contexts, its
Replicas, and their associated Replication agreements. This
section also describes the purpose of these objects and
abstractly describes their content.
Merrells, Reed, Srinivasan [Page 19]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
A Replication Context defines an area of DIT with
independent replication policies. There are many mechanisms
available to identify the set of Replication Contexts in a
Directory, including through special auxiliary classes or
through operational attributes in root DSE pointing to such
entries. The LDUP information model standards will detail an
appropriate mechanism.
Entries representing the set of Replicas associated with a
Replication Context are created immediately below (children)
the Replication Context entries. Replica entries are defined
as subentries and are intended to hold attributes that
identify the Replica's LDAP Access
Point, its Replica Type, and if it is a Fractional Replica,
the attributes it does or does not hold. The attribute value
of the entry's Relative Distinguished Name (RDN) is termed
the Replica Identifier and is used as a component of each
CSN associated with the replica.
Immediately subordinate to each Replica Subentry are the
entries representing the Replication Agreements between this
replica and another replica on some other server in the
network. A Replication Agreement entry is associated with
exactly one remote replica.
These entries are defined to hold attributes identifying the
remote Replica associated with this agreement, the
scheduling policy for replication operations, including
times when replication is to be performed, when it is not to
be performed, or the policies governing event-driven
replication initiation another Replica, the scheduling
policy for replication operations, including times when
replication is to be performed, when it is not to be
performed, or the policies governing event-driven
replication initiation.
5.2 Root DSE Attributes
LDUP information model will define Root DSE attributes to
identify the set of Replication Contexts and replicas
present in an LDAP server.
Merrells, Reed, Srinivasan [Page 20]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
5.3 Replication Context Auxiliary Object Class and Entries
Each Replication Context contains attributes that hold
common configuration and policy information for all replicas
of the Replication Context.
A Replication Context Creation attribute records when and
where the Replication Context was created.
The Replication Context is based at the entry given the
auxiliary class, and continues down the tree until leaf
entries or another Replication Context is encountered.
5.4 Replica Object Class and Entries
A replica type characterizes each Replica. This may be
Primary, Updateable, or Read-Only. The latter two types may
be further defined as being Fractional. The Replica entry
will include a Fractional Entry Specification for a
Fractional Replica.
There is a need to represent network addresses of servers
holding replicas involved in Replication Agreements. For
this, the LDUP information model will define an attribute
with an appropriate syntax to represent an LDAP server
addresses with which to contact replicas.
An Update Vector describes the point to which the Replica
has been updated, in respect to all the other Replicas of
the Replication Context. The vector is used at the
initiation of a replication session to determine the
sequence of updates that should be transferred.
Enabling LDAP to be a fully distributed service is not an
objective for the design of LDUP information model, though
the information stored in replica entries could facilitate
certain distributed operations.
5.5 Lost and Found Entry
When replicating operations between servers, conflicts may
arise that cause a parent entry to be removed causing its
child entries to become orphaned. In this case the Update
Merrells, Reed, Srinivasan [Page 21]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
Resolution Procedures will make the Lost and Found Entry the
child's new superior.
Each Replica Entry names its Lost and Found Entry, which
would usually be an entry below the Replica Entry itself.
This well-known place allows administrators, and their
tools, to find and repair abandoned entries.
5.6 Replication Agreement Object Class and Entries
The Replication Agreement defines:
1. The schedule for Replication Sessions initiation.
2. The server that initiates the Replication Session, either
the Consumer or the Supplier.
3. The authentication credentials that will be presented
between servers.
4. The network/transport security scheme that will be
employed in order to ensure data confidentiality.
5. The replication protocols and relevant protocol
parameters to be used for Full and Incremental updates.
An OID is used to identify the update transfer protocol,
thus allowing for future extensions or bilaterally agreed
upon alternatives.
6. If the Replica is Fractional, the Fractional Entry
Specification, for the attributes to be included or
excluded
Permission to participate in replication sessions will be
controlled, at least in part, by the presence and content of
replica agreements.
The Supplier must be subject to the access control policy
enforced by the Consumer. Since the access control policy
information is stored and replicated as directory content,
the access control imposed on the Supplier by the Consumer
must be stored in the Consumer's Replication Agreement.
Merrells, Reed, Srinivasan [Page 22]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
5.6.1 Replication Schedule
There are two broad mechanisms for initiating replication
sessions: (1) scheduled event driven and (2) change event
driven. The mechanism used to schedule replication
operations between two servers is determined by the Schedule
information that is part of the Replication Agreement
governing the Replicas on those two servers. Because each
Replication Agreement describes the policy for one direction
of the relationship, it is possible that events propagate
via scheduled events in one direction, and by change events
in the other.
Change event driven replication sessions are, by their
nature, initiated by suppliers of change information. The
server that the change is made against schedules a
replication session in response to the change itself, so
that notification of the change is passed on to other
Replicas.
Either consumers or suppliers of change information can
initiate scheduled event driven replication sessions. The
schedule defines a calendar of time periods during which
Replication Sessions should be initiated.
Schedule information may include both scheduled and change
event driven mechanisms. For instance, one such policy may
be to begin replication within 15 seconds of any change
event, or every 30 minutes if no change events are received.
6. Replication of Directory Administrative Policy
Information
Administrative policy information governs the behavior of
the directory server. Schema, access control, and
replication all involve administrative policy information.
This policy information (irrespective of how it is
represented in the directory as sub-entries, attributes, or
attribute values) should be consistently known and enforced
by servers managing any replica. Normally, policy
information present within a Replication Context is
replicated in the same manner as any other directory
information. But applicable policy information could reside
outside a Replication Context.
Merrells, Reed, Srinivasan [Page 23]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
Administrative policy information associated with directory
replication lies within the replication context to which it
applies. Hence, fortunately, any replica will also contain
(include) all of its applicable replication policy data. On
the other hand, some administrative boundaries
(administrative areas) for other services might extend to
subordinate Replication Contexts. For instance, some
prescriptive access control policy applicable to entries in
a Replication Context could be represented by an entry that
is an ancestor of the root of the Replication Context. For
access control policies to be faithfully enforced by a
server hosting a replica of such a Replication Context, all
applicable prescriptive policy information must also be
available within that server. Following potential models are
identified for accomplishing this:
(1) The administration model for specific services (such as
access controls) could define mechanisms for representing
and transmitting policy information as if it were an
element of the root of the Replication Contexts contained
within their respective administrative areas.
(2) Directory administrators could establish one or more
explicit agreements to cover all applicable entries
within superior Replication Contexts that hold
administrative policy information.
(3) A replication agreement could implicitly include all
administrative entries (and their associated sub-entries)
that are ancestors of the Replication Context defined by
these agreements. LDUP replication protocol could choose
to define this mechanism as the standard, if its
implementation is assessed to be relatively less complex.
6.1 Schema Knowledge
Given the strict ordering of replication events, schema
modifications will normally be replicated prior to entry
operations that use them, and subsequent to data deletions
that eliminate references to schema elements to be deleted.
In a multi-master environment with multiple suppliers, the
order of arrival at a consumer node of such changes cannot
be guaranteed. The LDUP standards for reconciliation should
define procedures for handling such scenarios.
Merrells, Reed, Srinivasan [Page 24]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
7. LDUP Update Transfer Protocol Framework
A Replication Session occurs between a Supplier server and
Consumer server over an LDAP connection. This section
describes the process by which a Replication Session is
initiated, started and stopped.
The session initiator, termed the Initiator, could be either
the Supplier or Consumer. The Initiator sends an LDAP
extended operation to the Responder identifying the
replication agreement being acted on. The Supplier then
sends a sequence of updates to the Consumer.
All transfers are in one direction only. A two-way exchange
requires two replication sessions - one session in each
direction.
7.1 Replication Session Initiation
The Initiator starts the Replication Session by opening an
LDAP connection to its Responder. The Initiator binds using
the authentication credentials provided in the Replication
Agreement. The LDUP Update Transfer Protocol will define
the LDAP extended operation the Initiator should perform to
initialize an LDUP session. For the sake of convenience,
this extended LDAP operation for initializing a replication
session is referred to as the _Start Replication_ operation.
Among other things, this operation will identify the role
each server will perform, and what type of replication is to
be performed. One server is to be the Consumer, the other
the Supplier, and the replication may be either Full or
Incremental.
7.1.1 Authentication
The initiation of a Replication Session is to be restricted
to privileged clients. The identity and the credentials for
the client eligible for initiating a replication session
will be specified as attributes within Replication
Agreements.
Merrells, Reed, Srinivasan [Page 25]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
7.1.2 Consumer Initiated
The Consumer binds to the Supplier using the authentication
credentials specified in the Replication Agreement. The
Consumer sends the Start Replication extended request to
begin the Replication Session. The Supplier returns a Start
Replication extended response containing a response code.
The Consumer then disconnects from the Supplier. If the
Supplier has agreed to the replication session initiation,
it binds to the Consumer and behaves just as if the Supplier
initiated the replication.
7.1.3 Supplier Initiated
The Supplier binds to the Consumer using the authentication
credentials provided in the Replication Agreement. The
Supplier sends the _Start Replication_ extended request to
begin the Replication Session. The Consumer returns a _Start
Replication_ extended response containing a response code,
and possibly its Update Vector. If the Consumer has agreed
to the Replication Session initiation, then the transfer
protocol begins.
7.2 Start Replication Session
7.2.1 Start Replication Request
The LDUP Update Transfer Protocol would define an LDAP
Extended Request, referred to in this document as _Start
Replication Request_, that is sent from the Initiator to
Responder. The parameters of the _Start Replication Request_
would identify the Replication Agreement associated with the
session, the Update Transfer Protocol associated with
the replication session, and other state information
necessary to initiate a replication session between the two
servers.
7.2.2 Start Replication Response
The LDUP Update Transfer Protocol would define an LDAP
Extended Response, _Start Replication Response_, sent in
reply to a Start Replication Request, from the Responder to
Merrells, Reed, Srinivasan [Page 26]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
the Initiator. The parameters of the Start Replication
Response include a response code, and an optional Update
Vector.
7.3 Update Transfer
Each Update Transfer Protocol is identified by an OID. An
LDUP conformant server implementation must support those
update protocols that are defined as mandatory in the Update
Transfer Protocol standard, and may support many others. A
server will advertise its protocols in the Root DSE multi-
valued attribute 'supportedReplicationProtocols'.
The Update Transfer Protocol would define the mechanisms for
a Consumer to receive a complete (full) update or
incremental update based on the current state of replication
represented in the Update Vector. A full update is necessary
for initializing a consumer replica upon establishment of
replication agreements.
7.4 End Replication Session
The _End Replication Request_ initiated by the supplier
terminates a Replication Session. The purpose of this
request and response is to secure the state of the Update
Vector associated with the two replicas that participated in
replication. This is necessary for proper resumption of
replication during subsequent LDUP sessions.
7.5 Integrity & Confidentiality
Data integrity (i.e., protection from unintended changes)
and confidentiality (i.e., protection from unintended
disclosure to eavesdroppers) SHOULD be provided by
appropriate selection of underlying transports, for instance
TLS, or IPSEC. Replication MUST be supported across TLS
LDAP connections. Servers MAY be configured to refuse
replication connections over unprotected TCP connections.
Merrells, Reed, Srinivasan [Page 27]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
8. LDUP Update Protocols
This Internet-Draft defines two transfer protocols for the
supplier to push changes to the consumer. Other protocols
could be defined to transfer changes, including those that
pull changes from the supplier to the consumer, but those
are left for future work.
8.1 Replication Updates and Update Primitives
Both LDUP Update Protocols define how Replication Updates
are transferred from the Supplier to the Consumer. Each
Replication Update consists of a set of Update Primitives
that describe the state changes that have been made to a
single entry. Each Replication Update is associated with a
single entry identified by its UUID.
The Update Transfer Protocol would define a set of Update
Primitives each of which codifies an assertion about the
state change of an entry that resulted from a directory
update operation. The primitives will include sufficient
data to allow recreation of corresponding state changes on
the consumer's replica. An assertion-based approach has been
chosen in such a way that the Primitives are idempotent,
meaning that re-application of a Primitive to an Entry will
cause no change to the entry. This is desirable as it
provides some resilience against some kinds of system
failures.
Each Update Primitive contains a CSN that represents an
ordering among all such primitives generated anywhere in the
network. The consumer uses this ordering information to
reconcile among those primitives that lead to consistency
violation.
8.2 Fractional Updates
When fully populating or incrementally bringing up to date a
Fractional Replica each of the Replication Updates must only
contain updates to the attributes in the Fractional Entry
Specification.
Merrells, Reed, Srinivasan [Page 28]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
9. LDUP Full Update Transfer Protocol
9.1 Full Update Transfer
This Full Update Protocol provides a bulk transfer of the
replica contents for the initial population of new replicas,
and the refreshing of existing replicas. The LDUP Update
Transfer protocol standard will define the ways for this
transfer is initiated. The Consumer must replace its entire
replica contents with that sent from the Supplier.
The Consumer MUST NOT service any requests for this Naming
Context whilst the full update is in progress. The Consumer
could instead return a referral to another replica, possibly
the supplier. [REF]
9.2 Replication Update Generation
The entire state of a Replicated Area can be mapped onto a
sequence of Replication Updates, each of which contains a
sequence of Update Primitives that describe the entire state
of a single entry.
The sequence of Replication Updates must be ordered such
that no entry is created before its parent.
9.3 Replication Update Consumption
A Consumer will receive the Replication Updates, extract the
sequence of Update Primitives, and must apply them to the
DIB in the order provided.
9.4 Full Update, End Replication Session
A Full Update should also result in the replication of all
appropriate LDUP meta-data (which are part of the
Replication Context), such as the sub-entry representing the
Replica being updated and the Update Vector associated with
it. The Supplier could be accepting updates whilst the
update is in progress. Once the Full Update has completed,
an Incremental Update should be performed to transfer these
changes.
Merrells, Reed, Srinivasan [Page 29]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
9.5 Interrupted Transmission
If the Replication Session terminates before the End
Replication Request is sent, then the Replica could be in an
inconsistent state. Until the replica is restored to a
consistent state, the consumer MUST NOT permit LDAP Clients
to access the incomplete replica. The Consumer could refer
the Client to the Supplier Replica, or return an error
result code.
10. LDUP Incremental Update Transfer Protocol
For efficiency, the Incremental Update Protocol transmits
only those changes that have been made to the Supplier
replica that the Consumer has not already received. In a
replication topology with transitive redundant replication
agreements, changes may propagate through the replica
network via different routes.
The Consumer must not support multiple concurrent
replication sessions with more than one Supplier for the
same Replication Context. A Supplier that attempts to
initiate a Replication Session with a Consumer already
participating as a Consumer in another Replication Session
will receive the appropriate error..
10.1 Update Vector
The Supplier uses the Consumer's Update Vector to determine
the sequence of updates that should be sent to the Consumer.
Each Replica entry includes an Update Vector to record the
point to which the replica has been updated. The vector is
a set of CSN values, one value for each known updateable
Replica. Each CSN value in the vector corresponds to the
most recent change known locally that occurred in the
updateable replica that this Update Vector value represents.
For example, consider two updateable replicas of a
Replication Context, one is assigned replica identifier
`1', the other replica identifier `2'. Each is responsible
for maintaining its own update vector, which will contain
Merrells, Reed, Srinivasan [Page 30]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
two CSNs, one for each replica. So, if both replicas are
identical they will have equivalent update vectors.
Both Update Vectors =
{1998081018:44:31z#0x000F#1#0x0000,
1998081018:51:20z#0x0001#2#0x0000}
Subsequently, at 7pm, an update is applied to replica `2',
so its update vector is updated.
Replica `1' Update Vector =
{1998081018:44:31z#0x000F#1#0x0000,
1998081018:51:20z#0x0001#2#0x0000}
Replica `2' Update Vector =
{1998081018:44:31z#0x000F#1#0x0000,
1998081019:00:00z#0x0000#2#0x0000}
Since the Update Vector records the state to which the
replica has been updated, a supplier server, during
Replication Session initiation, can determine the sequence
of updates that should be sent to the consumer. From the
example above no updates need to be sent from replica `1' to
replica `2', but there is at least one update pending from
replica `2' to replica `1'.
Because the Update Vector embodies knowledge of updates made
at all known replicas it supports replication topologies
that include transitive and redundant connections between
replicas. It ensures that changes are not transferred to a
consumer multiple times even though redundant replication
agreements may exist. It also ensures that updates are
passed across the replication network between replicas that
are not directly linked to each other.
It may be the case that a CSN for a given replica is absent,
for one of two reasons.
1. CSNs for Read-Only replicas might be absent because no
changes will have ever been applied to that Replica, so
there are no changes to replicate.
2. CSNs for newly created replicas may be absent because no
changes to that replica have yet been propagated.
Merrells, Reed, Srinivasan [Page 31]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
An Update Vector might also contain a CSN for a replica that
no longer exists. The replica may have been temporarily
taken out of service, or may have been removed from the
replication topology permanently. An implementation may
choose to retire a CSN after some configurable time period.
10.2 Supplier Initiated, Incremental Update, Start
Replication Session
The Consumer Responder must return its Update Vector to the
Supplier Initiator. The Supplier uses this to determine the
sequence of Replication Updates that need to be sent to the
Consumer.
10.3 Replication Update Generation
The Supplier generates a sequence of Replication Updates to
be sent to the consumer. To enforce LDAP Constraint 20.1.6,
that the LDAP Modify must be applied atomically, each
Replication Update must contain the entire sequence of
Update Primitives for all the LDAP Operations for which the
Replication Update contains Update Primitives. Stated less
formally, for each primitive the update contains, it must
also contain all the other primitives that came from the
same operation.
10.3.1 Replication Log Implementation
A log-based implementation might take the approach of
mapping LDAP Operations onto an equivalent sequence of
Update Primitives. A systematic procedure for achieving this
will be fully described in the standard document defining
Update Reconciliation Procedures.
The Consumer Update Vector is used to determine the sequence
of LDAP Operations in the operation log that the Consumer
has not yet seen.
10.3.2 State-Based Implementation
A state-based implementation might consider each entry of
the replica in turn using the Update Vector of the consumer
to find all the state changes that need to be transferred.
Each state change (entry, attribute, or value - creation,
Merrells, Reed, Srinivasan [Page 32]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
deletion, or update) is mapped onto the equivalent Update
Primitive. All the Update Primitives for a single entry
might be collected into a single Replication Update.
Consequently, it could contain the resultant primitives of
many LDAP operations.
10.4 Replication Update Consumption
A Consumer will receive Replication Updates, extract the
sequence of Update Primitives, and must apply them to the
DIB in the order provided. LDAP Constraint 20.1.6 states
that the modifications within an LDAP Modify operation must
be applied in the sequence provided.
Those Update Primitives must be reconciled with the current
replica contents and any previously received updates. In
short, updates are compared to the state information
associated with the item being operated on. If the change
has a more recent CSN, then it is applied to the directory
contents. If the change has an older CSN it is no longer
relevant and its change must not be effected.
If the consumer acts as a supplier to other replicas then
the updates are retained for forwarding.
10.5 Update Resolution Procedures
The LDAP Update Operations must abide by the constraints
imposed by the LDAP Data Model and LDAP Operational
Behavior, Appendix A. An operation that would violate at
least one of these constraints is rejected with an error
result code.
The loose consistency model of this replication architecture
and its support for multiple updateable replicas of a
Replication Context means that LDAP Update Operations could
be valid at one replica, but not in another. At the time of
acceptance, the accepting replica may not have received
other updates that would cause a constraint to be violated,
and the operation to be rejected.
Replication Updates must never be rejected because of a
violation of an LDAP Constraint. If the result of applying
the Replication Update causes a constraint violation to
occur, then some remedial action must be taken to satisfy
the constraint. These Update Resolution Procedures are
Merrells, Reed, Srinivasan [Page 33]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
introduced here, and fully described in These Update
Resolution Procedures are introduced here will be fully
defined within LDUP Update Resolution Procedures.
10.5.1 URP: Distinguished Names
LDAP Constraints 20.1.1 and 20.1.10 ensure that each entry
in the replicated area has a unique DN. A Replication Update
could violate this constraint producing two entries, with
different unique identifiers, but with the same DN. The
resolution procedure is to rename the both entries so that
its RDN includes its own unique identifier. This ensures
that the DN of both the entries shall be unique.
10.5.2 URP: Orphaned Entries
LDAP Constraints 20.1.11 ensures that every entry must have
a parent entry. A Replication Update could violate this
constraint producing an entry with (as yet) no parent entry.
The resolution procedure is to create a Glue Entry to take
the place of the absent parent. The Glue Entry's superior
will be the Lost and Found Entry. This well-known place
allows administrators and their tools (including subsequent
Replication Sessions) to find and repair orphaned entries.
10.5.3 URP: Schema - Single Valued Attributes
LDAP Constraint 20.1.7 enforces the single-valued attribute
schema restriction. A Replication Update could violate this
constraint creating a multi-value single-valued attribute.
The resolution procedure is to replace the earlier value of
a single-valued attribute with the newer value. In this way
the most recently added value will be retained, and the
older one discarded.
10.5.4 URP: Schema - Required Attributes
LDAP Constraint 20.1.7 enforces the schema objectclass
definitions on an entry. A Replication Update could violate
this constraint creating an entry that does not have
attribute values for required attributes. The resolution
procedure is to ignore the schema violation and mark the
entry as a glue entry for administrative repair or
correction in a subsequent replication session.
Merrells, Reed, Srinivasan [Page 34]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
10.5.5 URP: Schema - Extra Attributes
LDAP Constraint 20.1.3 and 20.1.7 enforces the schema
objectclass definitions on an entry. A Replication Update
could violate this constraint creating an entry that has
attribute values not allowed by the objectclass values of
the entry. The resolution procedure is to ignore the schema
violation and mark the entry as a glue entry for
administrative repair or correction in a subsequent
replication session.
10.5.6 URP: Duplicate Attribute Values
LDAP Constraint 20.1.5 ensures that the values of an
attribute constitute a set of unique values. A Replication
Update could violate this constraint. The resolution
procedure is to enforce this constraint, recording the most
recently assigned CSN with the value.
10.5.7 URP: Ancestry Graph Cycle
LDAP Constraint 20.4.2.1 prevents against a cycle in the
DIT. A Replication Update could violate this constraint
causing an entry to become it's own parent, or for it to
appear even higher in it's ancestry graph. The resolution
procedure is to break the cycle by changing the parent of
the entry closest to be the lost and found entry.
10.6 Incremental Update, End Replication Session
If the Supplier sent none of its own updates to the
Consumer, then the Supplier's CSN within the Supplier's
update vector should be updated with the earliest possible
CSN that it could generate, to record the time of the last
successful replication session. The Consumer will have
received the Supplier's Update Vector in the replica sub-
entry it holds for the Supplier replica.
The Consumer's resultant Update Vector CSN values will be at
least as great as the Supplier's Update Vector.
The Supplier may request that the Consumer return its
resultant Update Vector so that the Supplier can update its
replica sub-entry for the Consumer Replica. The Supplier
requests this by setting a flag in the End Replication
Merrells, Reed, Srinivasan [Page 35]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
Request. The default flag value is TRUE meaning the Consumer
Update Vector must be returned.
10.7 Interrupted Transmission
If the Replication Session terminates before the End
Replication Request is sent then the Consumer's Update
Vector may or may not be updated to reflect the updates
received. The Start Replication request includes a
Replication Update Ordering flag that states whether the
updates were sent in CSN order per replica.
If updates are sent in CSN order per replica then it is
possible to update the Consumer Update Vector to reflect
that some portion of the updates to have been sent have been
received and successfully applied. The next Incremental
Replication Session will pick up where the failed session
left off.
If updates are not sent in CSN order per replica then the
Consumer Update cannot be updated. The next Incremental
Replication Session will begin where the failed session
began. Some updates will be replayed, but because the
application of Replication Updates is idempotent they will
not cause any state changes.
11. Purging State Information
The state information stored with each entry need not be
stored indefinitely. A server implementation may choose to
periodically, or continuously, remove state information that
is no longer required. The mechanism is implementation-
dependent, but to ensure interoperability between
implementations, the state information must not be purged
until all known replicas have received and acknowledged the
change associated with a CSN. This is determined from the
Purge Vector [11.1].
All the CSNs stored that are lower than the Purge Vector may
be purged, because no changes with older CSNs can be
replicated to this replica.
Merrells, Reed, Srinivasan [Page 36]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
11.1 Purge Vector
The Purge Vector is an Update Vector constructed from the
Update Vectors of all known replicas. Below the root of a
Replication Context is one sub-entry for each known replica
of that Replication Context. Each of those entries contains
the last known update vector for that replica. The lowest
CSN for each replica are taken from these update vectors to
form the Purge Vector. The Purge Vector is used to determine
when state information and updates need no longer be stored.
11.2 Purging Deleted Entries, Attributes, and Attribute
Values
The following conditions must hold before an item can be
deleted from the Directory Information Base.
1) The LDAP delete operation has been propagated to all
replication agreement partners.
2) All the CSNs in other replica Update Vectors representing
changes to be sent to the server holding the deleted entry
have advanced beyond the CSN on the deletion (similarly for
deleted attributes and attribute values).
3) The CSN generator of the other Replicas must have
advanced beyond the deletion CSN of the deleted entry.
Otherwise, it is possible for one of those Replicas to
generate operations with CSNs earlier than the deleted
entry.
12. Replication Configuration and Management
Replication management entries, such as replica or
replication agreement entries can be altered on any
updateable replica. These entries are implicitly included in
the directory entries governed by any agreement associated
with this Replication Context. As a result, all servers
with a replica of a Replication Context will have access to
information about all other replicas and associated
agreements.
The deployment and maintenance of a replicated directory
network involves the creation and management of all the
replicas of a Replication Context and replication agreements
Merrells, Reed, Srinivasan [Page 37]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
among these replicas. This section outlines, through an
example, the administrative actions necessary to create a
new replica and establish replication agreements.
Typically, administrative tools will guide the administrator
and facilitate these actions. The objective of this example
is to illustrate the architectural relationship among
various replication related operational information.
A copy of an agreement should exist on both the supplier and
consumer side for the replication update transfer protocol
to be able to start. For this purpose, the root of the
Replication Context, replica objects and the replication
agreement objects are created first on one of the servers.
A copy of these objects is then manually created on the
second server associated with the agreement.
The scenario below starts with a server (named DSA1) that
holds an updateable replica of a Replication Context, RC1.
Procedures to establish an updateable replica of the
Replication Context on a second server (DSA2) are outlined.
Note that when entries are created on two or more separate
servers in the operations described below, they need to be
created with the same entry UUIDs so that they don't collide
with one another when replication of their information
actually occurs. This may be done through some
administrative control that allows the entry UUID to be set
by the create entry operation.
1. On DSA1: Add RC1's context prefix to the value of Root
DSE attribute 'replicaRoot'.
2. On DSA1: Alter the 'ObjectClass' attribute of the root
entry of RC1 to include the "replicationContext"
auxiliary class.
3. On DSA1: Create a replica object, RC1-R1, (as a child of
the root of RC1) to represent the replica on DSA1. The
attributes include replica type (updateable, read-only
etc.) and DSA1 access point information.
4. On DSA2: Add RC1's context prefix to the value of Root
DSE attribute 'replicaRoot'.
5. On DSA2: Create a copy of the root entry of RC1 as a copy
of the one in DSA1 (including the replicationContext
auxiliary class)
Merrells, Reed, Srinivasan [Page 38]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
6. On DSA2: Create a copy of the replica object RC1-R1
7. On DSA2: Create a second replica object, RC1-R2 (as a
sibling of RC1-R1) to represent the replica on DSA2.
8. On DSA1: Create a copy of the replica object RC1-R2
9. On DSA1: Create a replication agreement object, RC1-R1-R2
to represent update transfer from RC1-R1 to RC1-R2. This
object is a child of RC1-R1.
10.On DSA2: Create a copy of the replication agreement, RC1-
R1-R2.
11.On DSA2: Create a replication agreement, RC1-R2-R1, to
represent update transfer from RC1-R2 to RC1-R1. This
object is a child of RC1-R2.
12.ON-DSA1: Create a copy of the replication agreement, RC1-
R2-R1.
After these actions update transfer to satisfy either of the
two agreements can commence.
If data already existed in one of the replicas, the update
transfer protocol should perform a complete update of the
data associated with the agreement before normal replication
begins.
13. Time
The server assigns a CSN for every LDAP update operation it
receives. Since the CSN is principally based on time, the
CSN is susceptible to the Replica clocks drifting in
relation to each other (either forwards or backwards).
The server must never assign a CSN older than or equal to
the last CSN it assigned.
The server must reject update operations, from any source,
which would result in setting a CSN on an entry or a value
that is earlier than possible. The error code
Merrells, Reed, Srinivasan [Page 39]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
serverClocksOutOfSync (72) should be returned if it is clear
that the update is not simply an old one that should be
silently ignored. In particular, additions or modifications
with CSNs prior to those on the servers Purge Vector should
be rejected.
14. Security Considerations
The preceding architecture discussion covers the server
authentication, session confidentiality, and session
integrity in sections 7.1.1 and 7.5.
The IETF draft "Authentication Methods" for LDAP, provides a
detailed LDAP security discussion. Its introductory passage
is paraphrased below. [AUTH]
A Replication Session can be protected with the following
security mechanisms.
1) Authentication by means of the SASL mechanism set,
possibly backed by the TLS credentials exchange
mechanism,
2) Authorization by means of access control based on the
Initiators authenticated identity,
3) Data integrity protection by means of the TLS protocol or
data-integrity SASL mechanisms,
4) Protection against snooping by means of the TLS protocol
or data-encrypting SASL mechanisms,
The configuration entries that represent Replication
Agreements may contain authentication information. This
information must never be replicated between replicas.
Updates to a multi-mastered entry may collide causing the
Update Resolution Procedures [10.5] to reject or reverse one
of the changes to the entry. The URP algorithms resolve
conflicts by using the total ordering of updates imposed by
the assignment of CSNs for every operation. As a consequence
updates originating from system administrators have no
priority over updates originating from regular system users.
Merrells, Reed, Srinivasan [Page 40]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
15. Acknowledgements
This document is a product of the LDUP Working Group of the
IETF. The contribution of its members is greatly
appreciated.
16. References
[AUTH] _ M. Wahl, H. Alvestrand, J. Hodges, RL "Bob" Morgan,
"Authentication Methods for LDAP", Internet Draft, draft-
ietf-ldapext-authmeth-02.txt, June 1998.
[BCP-11] _ R. Hovey, S. Bradner, "The Organizations Involved
in the IETF Standards Process", BCP 11, RFC 2028, October
1996.
[LDAPv3] _ M. Wahl, S. Kille, T. Howes, "Lightweight
Directory Access Protocol (v3)", RFC 2251, December1997.
[LDUP Requirements] - R. Weiser, E. Stokes 'LDAP
Replication Requirements', Internet Draft, draft-weiser-
replica-req-02.txt, October, 1999.
[NTP] _ D. L. Mills, "Network Time Protocol (Version 3)",
RFC 1305, March, 1992.
[RFC2119] _ S. Bradner, "Key words for use in RFCs to
Indicate Requirement Levels", RFC 2119.
[RFC2252] _ M. Wahl, A. Coulbeck, T. Howes, S. Kille,
_Lightweight Directory Access Protocol (v3): Attribute
Syntax Definitions_, RFC 2252, December 1997.
[SNTP] _ D. L. Mills, "Simple Network Time Protocol (SNTP)
Version 4 for IPv4, IPv6 and OSI", RFC 2030, University of
Delaware, October 1996.
[TLS] _ J. Hodges, R. L. "Bob" Morgan, M. Wahl,
"Lightweight Directory Access Protocol (v3):
Extension for Transport Layer Security", Internet draft,
draft-ietf-ldapext-ldapv3-tls-01.txt, June 1998.
Merrells, Reed, Srinivasan [Page 41]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
[X501] _ ITU-T Recommendation X.501 (1993), ) | ISO/IEC
9594-2:1993, Information Technology _ Open Systems
Interconnection _ The Directory: Models
[X680] _ ITU-T Recommendation X.680 (1994) | ISO/IEC 8824-
1:1995, Information technology _ Abstract Syntax Notation
One (ASN.1): Specification of Basic Notation
[X525] _ ITU-T Recommendation X.525 (1997) | ISO/IEC 9594-
9:1997, Information Technology _ Open Systems
Interconnection _ The Directory: Replication
17. 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 implementers 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 that may cover technology that may
be required to practice this standard. Please address the
information to the IETF Executive Director.
18. Copyright Notice
Copyright (C) The Internet Society (1998,1999,2000). All
Rights Reserved.
This document and translations of it may be copied and
furnished to others, and derivative works that comment on or
otherwise explain it or assist in its implementation may be
Merrells, Reed, Srinivasan [Page 42]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
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.
19. Authors' Address
John Merrells
Netscape Communications, Inc.
501 East Middlefield Road
Mountain View
CA 94043
E-mail: merrells@netscape.com
Phone: +1 650-937-5739
Edwards E. Reed
Reed-Matthews, Inc.
1064 East 140 North
Lindon
UT 84042
E-mail: eer@oncalldba.com
Phone: +1 801-796-7065
Merrells, Reed, Srinivasan [Page 43]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
Uppili Srinivasan
Oracle, Inc.
Redwood Shores
E-mail: usriniva@us.oracle.com
Phone: +1 650 506 3039
LDUP Engineering Mailing List: ldup-
repl@external.cisco.com
LDUP Working Group Mailing List: ietf-ldup@imc.org
20. Appendix A _ LDAP Constraints
20.1 LDAP Constraints Clauses
This is an enumeration of the Data Model and Operation
Behaviour constraint clauses defined in RFC 2251. [LDAPv3]
1) Data Model - Entries have names: one or more attribute
values from the entry form its relative distinguished
name (RDN), which MUST be unique among all its siblings.
(p5)
2) Data Model - Attributes of Entries - Each entry MUST have
an objectClass attribute. (p6)
3) Data Model - Attributes of Entries - Servers MUST NOT
permit clients to add attributes to an entry unless those
attributes are permitted by the object class definitions.
(p6)
4) Relationship to X.500 - This document defines LDAP in
terms of X.500 as an X.500 access mechanism. An LDAP
server MUST act in accordance with the X.500 (1993)
series of ITU recommendations when providing the service.
However, it is not required that an LDAP server make use
of any X.500 protocols in providing this service, e.g.
LDAP can be mapped onto any other directory system so
long as the X.500 data and service model as used in LDAP
is not violated in the LDAP interface. (p8)
Merrells, Reed, Srinivasan [Page 44]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
5) Elements of Protocol - Common Elements - Attribute - Each
attribute value is distinct in the set (no duplicates).
(p14)
6) Elements of Protocol - Modify Operation - The entire list
of entry modifications MUST be performed in the order
they are listed, as a single atomic operation. (p33)
7) Elements of Protocol - Modify Operation - While
individual modifications may violate the directory
schema, the resulting entry after the entire list of
modifications is performed MUST conform to the
requirements of the directory schema. (p33)
8) Elements of Protocol - Modify Operation - The Modify
Operation cannot be used to remove from an entry any of
its distinguished values, those values which form the
entry's relative distinguished name. (p34)
9) Elements of Protocol - Add Operation - Clients MUST
include distinguished values (those forming the entry's
own RDN) in this list, the objectClass attribute, and
values of any mandatory attributes of the listed object
classes. (p35)
10) Elements of Protocol - Add Operation - The entry named
in the entry field of the AddRequest MUST NOT exist for
the AddRequest to succeed. (p35)
11) Elements of Protocol - Add Operation - The parent of the
entry to be added MUST exist. (p35)
12) Elements of Protocol - Delete Operation - ... only leaf
entries (those with no subordinate entries) can be
deleted with this operation. (p35)
13) Elements of Protocol - Modify DN Operation - If there
was already an entry with that name [the new DN], the
operation would fail. (p36)
14) Elements of Protocol - Modify DN Operation - The server
may not perform the operation and return an error code if
the setting of the deleteoldrdn parameter would cause a
schema inconsistency in the entry. (p36)
Merrells, Reed, Srinivasan [Page 45]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
20.2 LDAP Data Model Constraints
The LDAP Data Model Constraint clauses as written in RFC
2251 [LDAPv3] may be summarised as follows.
a) The parent of an entry must exist. (LDAP Constraint 11 &
12.)
b) The RDN of an entry is unique among all its siblings.
(LDAP Constraint 1.)
c) The components of the RDN must appear as attribute values
of the entry. (LDAP Constraint 8 & 9.)
d) An entry must have an objectclass attribute. (LDAP
Constraint 2 & 9.)
e) An entry must conform to the schema constraints. (LDAP
Constraint 3 & 7.)
f) Duplicate attribute values are not permitted. (LDAP
Constraint 5.)
20.3 LDAP Operation Behaviour Constraints
The LDAP Operation Behaviour Constraint clauses as written
in RFC 2251 [LDAPv3] may be summarised as follows.
A) The Add Operation will fail if an entry with the target
DN already exists. (LDAP Constraint 10.)
B) The Add Operation will fail if the entry violates data
constraints:
a - The parent of the entry does not exist. (LDAP
Constraint 11.)
b - The entry already exists. (LDAP Constraint 10.)
c - The entry RDN components appear as attribute values
on the entry. (LDAP Constraint 9.)
d - The entry has an objectclass attribute. (LDAP
Constraint 9.)
e - The entry conforms to the schema constraints. (LDAP
Constraint 9.)
Merrells, Reed, Srinivasan [Page 46]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
f - The entry has no duplicated attribute values. (LDAP
Constraint 5.)
C) The modifications of a Modify Operation are applied in
the order presented. (LDAP Constraint 6.)
D) The modifications of a Modify Operation are applied
atomically. (LDAP Constraint 6.)
E) A Modify Operation will fail if it results in an entry
that violates data constraints:
c - If it attempts to remove distinguished attribute
values. (LDAP Constraint 8.)
d - If it removes the objectclass attribute. (LDAP
Constraint 2.)
e - If it violates the schema constraints. (LDAP
Constraint 7.)
f - If it creates duplicate attribute values. (LDAP
Constraint 5.)
F) The Delete Operation will fail if it would result in a
DIT that violates data constraints:
a - The deleted entry must not have any children. (LDAP
Constraint 12.)
G) The ModDN Operation will fail if it would result in a DIT
or entry that violates data constraints:
b - The new Superior entry must exist. (Derived LDAP
Data Model Constraint A)
c - An entry with the new DN must not already exist.
(LDAP Constraint 13.)
c - The new RDN components do not appear as attribute
values on the entry. (LDAP Constraint 1.)
d - If it removes the objectclass attribute. (LDAP
Constraint 2.)
e - It is permitted for the operation to result in an
entry that violates the schema constraints. (LDAP
Constraint 14.)
Merrells, Reed, Srinivasan [Page 47]
INTERNET-DRAFT LDAP Replication Architecture December 11, 2000
20.4 New LDAP Constraints
The introduction of support for multi-mastered entries, by
the replication scheme presented in this document,
necessitates the imposition of new constraints upon the Data
Model and LDAP Operation Behaviour.
20.4.1 New LDAP Data Model Constraints
1) Each entry shall have a unique identifier generated by
the UUID algorithm available through the `entryUUID'
operational attribute. The entryUUID attribute is single
valued.
20.4.2 New LDAP Operation Behaviour Constraints
1) The LDAP Data Model Constraints do not prevent cycles in
the ancestry graph. Existing constraints Data Model
Constraint _ 20.4.1 _ (a) and Operation Constraint _
20.4.2 _ (B) would prevent this in the single master
case, but not in the presence of multiple masters.
2) The LDAP Data Model Constraints state that only the LDAP
Modify Operation is atomic. All other LDAP Update
Operations are also considered to be atomically applied
to the DIB.
Merrells, Reed, Srinivasan [Page 48]