Subject: RE: Supporting Partial Replication

From: "Steven Legg" <[email-masked]>
Date: Wed, 9 Jan 2002 09:22:11 +1100

John,

John McMeeking wrote:
>
> Updated to add some thoughts on overlapping replication contexts...
>
> John McMeeking
>
>
> Before I go on vacation too...
>
> We seem to be operating on different understandings of LDUP with respect
to
> areas of replication, replication contexts, and update vectors.
>
> You mention a "fourth option", being to maintain "an update vector per
> replication area in a replication context and use the cascade rule to
> maintain the update vectors." As I understand LDUP: an area of replication
> and a replication context are the same thing, with replication context
being
> the current LDUP terminology.

The replication architecture document doesn't define what an area of
replication (or replication area is). The requirements document does define
"area of replication" as the unit of data to be replicated, and allows these
areas to overlap or be nested. Replication contexts are necessarily
non-overlapping, so to my mind a replication context cannot be the same
thing
as an area of replication. I have assumed an area of replication (or
replication area) can be the whole of a replication context or a sparse
and/or fractional portion of a replication context.

> They identify an area of the DIT that is
> replicated -- a replication context has a single root entry and is bounded
> by subordinate replication contexts (ldup-model 3.5 - Terms and
Definitions).
> LDUP already defines a separate update vector per replication context (per
> replica). On the surface at least, your "fourth option" appears to be LDUP
> as currently defined.
>
> For a server to participate in a cycle (which ldup-replica-req now refers
to
> as a "replica group" precisely because of the misunderstanding I had about
> your use of cyle), the server must hold a copy of the replication context.

We still appear to be on different wavelengths.

By inspecting the replication agreements between servers in a replica group
for a specific replication context, one can construct an undirected graph
to represent the replication topology, where the vertices are servers and
the arcs are replication agreements. The cycles I'm talking about are cycles
in that graph. The replication topology for a particular replica group and
replication context may have zero, one or more cycles. The update vector
propagation mechanism fails if the replication agreements corresponding to
arcs making a cycle in the replication topology are not all replicating
the same information (the same area of replication, by my interpretation).
Or, to put it another way, updates are correctly propagated only if none of
the replication agreements corresponding to arcs making a cycle in the
replication topology are sparse or fractional, or if they all use exactly
the same sparse or fractional specification. Many interesting and useful
replication topologies that I can support in X.500 replication don't meet
these criteria.

> And just to make sure my assumptions about what this means are clear:
> - a replica group is defined in the context of a replication context. It
is
> the servers that hold instances of a particular area of replication. A
server
> may be part of several replica-groups.
> - replication agreements are defined in the context of a replication
context.
>
> In your example, with three servers and two replication contexts,
agreements
> between all the servers implies that there are two sets of agreements
> between each server -- a set for each replication context. The existance
of
> a replication agreement in one replication context does not imply a
> corresponding agreement in other replication contexts.

In my example there are three servers and one replication context. There are
two areas of replication within that replication context but these are not
explicitly represented (I think we would be better off if they were) within
the current LDUP model. They are implicit in the replication agreements.
S1 has a replication agreement to replicate the whole of the replication
context to S2, and vice versa. I have described the information within the
scope of these two replication agreements as the replication area R1.
Assume that S1 has a fractional replication agreement to replicate only
some of the attributes to S3 and that S3 has an agreement to replicate the
same set of attributes to S1. S2 has an equivalent arrangement with S3.
Therefore S3 holds a fractional replica of the replication context. I have
described the information in that fractional replica as the replication
area R2. R2 is a subset (but not a subtree) of the information in R1.

>
> I'm going to go out on a limb, and guess that part of our
misunderstandings
> has to do with "overlapping" replication contexts -- you mentioned
> replicating ACL via sparse or fractional replication, while having a full
> replica of some subtree). This may be required by ldup-replica-req
> (mentioned in terminology, but not in specific requirements), but is
> currently listed as a non-objective of ldup-model (section 3.3e). Would it
> be fair to state that you think ldup-model (and friends) needs to address
> overlapping replication contexts?

To be at least as capable as X.500 at single master replication LDUP needs
to deal with overlapping replicated portions of the DIT. Replication
contexts, as a generalization of naming contexts in a multi-master
environment,
are fine as they are. I prefer to think of servers replicating portions
of disjoint replication contexts (by analogy with X.500 where servers
replicate portions of disjoint naming contexts) but it is these portions
(i.e. areas of replication) that potentially overlap.

> My responses have been in the context of
> what ldup-model claims to support, and in that context I seem to be having
> a problem understanding your concerns and properly communicating my
> understanding.

And I find that what the LDUP model currently supports is inadequate so
I'm looking at solutions for improving on it.

> After thinking about overlapping replication contexts a bit more, IF we
are
> going to tackle it, I think we need to address the following:
> 1. How do we define the bounds of a replication context that is not
bounded
> by nested replication contexts? Kurt Zielenga's ldap-subentry draft would
> be useful here (subtree specification).

It is easier to leave the replication contexts as they are and assume that
replication areas are what we are replicating and that they are bounded by
the replication context within which they are contained.

X.500 uses SubtreeSpecification to describe sparse replicated areas in
a naming context. Subtree specifications are already available in the
current LDUP model for us to use in describing sparse portions of a
replication context since the replica and replica agreement subentries
now include the subtreeSpecification operational attribute.

The LDUP model already has the means the specify fractional areas of
replication.

However I suggest that areas of replication be explicitly represented
by their own subentries which replica and replica agreement subentries
can simply reference (or be subordinate to).

> 2. If a client update falls within multiple replication contexts, how
should
> LDUP behave?

I addressed this in my example (where a client update falls within multiple
areas of replication), with an update vector and replica ID per
area of replication, and the cascade rule.

> Let's start with replicating changes under all appropriate
> replication contexts, meaning that the same update will be sent multiple
> times under different replication sessions (they are idempotent, so this
> should be okay).

It will work if each session obtains a different consumer update vector.
However, the cascade rule avoids much of the update duplication.

> This should keep update vectors in the correct state, as an
> update under one replication context may be replicated before earlier
> updates (by CSN) that fall within other overlapping replication contexts.
> 3. Do we allow multiple replication contexts with different bounds to have
> the same root? I'd like to withdraw the question, because I'm sure that
once
> asked, the answer will be "YES!" This makes my head hurt more than I need
> just before Christmas, so I'll leave that for others to gnaw on.

The solution I presented previously works regardless of how areas of
replication overlap or nest. Two areas of replication that have the same
root but different bounds is just one of many ways two areas can overlap.

> John McMeeking

Regards,
Steven

---

From: "Steven Legg" <[email-masked]>
Date: Wed, 9 Jan 2002 09:22:48 +1100

Ed,

Ed Reed wrote:
> John - I think you're onto the right track in determining 
> where the disconnect
> exists.  
> 
> To begin, note that the model only talks about fractional, 
> and not sparse,
> replicas.  
> 
> Fractional replicas are those that hold entries having a subset
> of all the attributes defined on compete replicas holding 
> those entries.  All
> entries of a replication context are present in a fractional 
> replica, but not
> all of their attributes are there.  It is the entries which 
> are fractional.
> 
> Sparse replicas, we agreed, are those where not every entry of the
> replication context are held on the sparse replica.  But every entry
> that IS held is complete.  It is the namespace that is sparse.
> 
> A Sparse and/or Fractional replica (an incomplete replica, in 
> earlier drafts
> of the model) hold some of the entries of the replication 
> context, and they
> may or may not be complete (ie, some entries may be 
> fractional entries).
> In other words, the namespace is sparse and the entries held may be
> fractional.
> 
> We dropped sparse replicas from the Arch Model when we couldn't
> persuade ourselves that we knew how to deal with update vectors and
> purge vectors for sparse replicas.  

That's one of the questions I'm now addressing. It turns out that
fractional replicas (already in the model) and sparse replicas (not
yet in the model) have the same issues with respect to update vectors,
and the same solution.

> 
> Now, I've never contemplated a scenario in which a server holds two
> replicas of same replication context.  There may be utility in
> such a scenario, but it has never occured to me.  Thus, there is one
> update vector for the replication context, on the replicaSubentry.
> 
> The LDUP model in my mind partitions naming contexts with replication
> contexts.  Note that both naming contexts and replication contexts are
> subjects of the DIT, not of any particular DIB.  A replica is a set of
> entries from a naming context held in a particular DIB by a particular
> LDAP server.  There may be multiple replicas of any 
> replication context.
> 
> But as I said, it had never occured to me to consider a DSA holding
> multiple replicas of the same replication context in its DIB.
> 
> Rather, I assumed that a DSA would be considered to hold in its DIB
> all the entries from a replication context that it needed for its own
> purposes, and for the purposes of forwarding updates to other servers
> that it supplies updates to, if any.

I trust that you understand that in advocating an update vector and
replica ID for each area of replication (by which I mean a full or
sparse and/or fractional portion of a replication context) I'm not
suggesting that the data in overlapping areas of replication should
be duplicated. An entry and its attributes are represented only once
in a server even though that entry, or parts of it, may fall within
the scope of more than one area of replication.

> 
> So, subordinate to the replicaSubentry representing the replica in the
> DIB of a DSA, there could be several replicationAgreements - some
> of which place no additional filters on the updates being sent, and 
> some that DO further restrict which attributes (for 
> fractional entries)
> are to be forwarded to the specific other DSA replica pointed to by
> each replicationAgreementSubentry.
> 
> Thus - a replicaSubentry documents the entries held by the DSA and
> whether there are any limits on the attributes held for those entries,
> and replicationAgreementSubentries documents the flow of
> entries (and their attributes, possibly filtered) between a replica
> and another.

There is a degree of redundancy, and therefore scope for consistency
errors, in describing a fractional replica. The same attribute filters
are specified in the replicaSubentry for the fractional replica and in
the replicaAgreementSubentry for propagating updates from the
full replica to the fractional replica. If updateable fractional replicas
are to be allowed then there will also be a replicaAgreementSubentry
for propagating changes from the fractional replica to the full replica,
with the same attribute filters. There would be similar redundancy
for sparse replica specifications.

This redundancy would be removed if areas of replication were explicitly
represented by subentries in a replication context. A replicaSubentry
subordinate to an area of replication subentry indicates that the server
holds the information in that area of replication, and
replicaAgreementSubentries subordinate to the replicaSubentry are assumed
to propagate only changes to the same information. The area of information
subentry is the only place where sparse-ness and fractional-ness needs
to be specified.

> 
> If the set of entries in replication area A held by replica 1 is 
> designated A1 on Server S1, and there is a subset of A held on another
> server S2 designated A2, A1 is a complete replica and A2 is an
> incomplete replica.  It would be redundant to say that A2 and A1
> are both held by S1, though they are, because all the entries of A2
> (being a subset of A) are in A1 (the full set of A).
> 
> Now, A1 on S1 might very well have a replicationAgreement with A2
> on S2 such that A1 only sends what A2 needs because of the filters
> on the replication agreement, or even because of filters on the
> replicaSubentry for A2.
> 
> But the notion that both A1 and A2 would be considered to both
> be on a single server is simply not something I have ever considered.
> I don't know if the model could work in such a scenario or not.
> 
> Ed

Regards,
Steven