Subject: Re: Supporting Partial Replication

From: "John McMeeking" <[email-masked]>
Date: Mon, 10 Dec 2001 08:22:08 -0600

I agree with Ryan on the first part of the note (I haven't gotten through
the flurry of LDUP notes).  But, we may have a problem with update vectors
under partial/fractional replication.

Update vectors are defined per replica and per replication context
(actually, defined per replica, where a replica is a replicated instance of
a replication context).

If R2 is a subtree of R1, separate update vectors are maintained for both
R2 and R1, and the problem Steven describes doesn't occur.  For either S1
or S2 to replicate U1 to S3, replication context R1 must be added to S3,
and the replication context properly initialized on S3 -- either via a full
update replication session, or via some other means (i.e. LDIF).  At that
point, U1 (and the rest of the entries in R1) are present on S3 and
replication continues normally.  Replication of R1 is independent of R2.

If R2 is a sparse/fractional replica of R1, R2 would not be considered a
separate replication context.  In this case, sparse/fractional replication
is an attribute of the replicaSubentry for S3.  If U1 falls within the
attributes and/or entries specified for S3, it will be replicated under the
replication agreements targeting S3 under R1, and the UV for S3 updated
accordingly.

What happens when S3 is a fractional replica, and U1 does not contain any
attributes replicated to S3?  draft-ietf-ldup-model-06, section 8.2,
specifies "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."
This implies that S3 will never see U1, and thus not fully update its
update vector until such time as it receives an update originating at the
same server.  Steven's example described U1 and U2 as successive updates
originating at S2.  Suppose U1 originated at S1 and U2 originated at S2:

Initially, the update vector for S3 (UV3) looks like < Tx#1#0#0, Ty#2#0#0,
null > (latest CSNs from S1 and S2, no updates originating at S3)

At time T15, on server 1, client performs update U1: CSN = T15#1#0#0.

This is replicated to S2, and eventually S2 replicates to S3.  But since no
attributes in U1 are present in S3's fractional entry specification, no
replication occurs.

Update vector for S3 remains < Tx#1#0#0, Ty#2#0#0, null >

At time T16, on server 2, client performs update U2: CSN = T16#2#0#0.

U2 is replicated to S3.

Update vector for S3 is changed to < Tx#1#0#0, T16#2#0#0, null >.  What we
want to see here, though is: < T15#1#0#0, T16#2#0#0, null >

Since T15-1 never appears in the update vector for S3, two things happen:
1) purge vectors never advance to include U1 until a subsequent change on
S1 results in an update vector change for S3
2) Servers replicating to S3 must examine update U1 (possibly similar
updates) at each replication session to determine that it should not be
sent to S3, as it appears that U1 has never been seen by S3.

Solution?

Can the update protocol support replication primitives that, in effect,
contain nothing but the entry UUID and CSN information?  For example, an
"add attribute value primitive" that consist of:
csn=T15-1
type=null
value=null

Or should there be a new primitive that serves only to inform the replica
of a CSN?

John  McMeeking

                      Ryan Moats                                                                                           
                      <rmoats@lemurnetw        To:       Steven Legg <[email-masked]>                           
                      orks.net>                cc:       [email-masked]                                                 
                      Sent by:                 Subject:  Re: Supporting Partial Replication                                
                      owner-ietf-ldup@m                                                                                    
                      ail.imc.org                                                                                          

                      12/07/2001 06:53                                                                                     
                      PM                                                                                                   

On Thu, Dec 06, 2001 at 02:45:14PM +1100, Steven Legg wrote:
|
|
| Folks,
|
| A while ago I promised to write up my thoughts on changes to the LDUP
| architecture to support partial replication. Well this is part one of
| that write up, which discusses changes to the architecture to make it
| more amenable to replication topologies involving partial replicas.
|
|
| Consider the following replication topology:
|
|   S1 ====== S2
|     \      /
|      \    /
|       \  /
|        S3
|
| Servers S1 & S2 hold full copies of replication area R1. S3 holds
| replication area R2, a subset of R1. R2 could be a subtree of R1, a
| sparse replica or a fractional replica. The exact details don't matter
| at this stage. It is enough to recognize that R2 is a subset of the
| information in R1.
|
| Suppose that there are two successive update operations, U1 & U2,
performed
| at S2, where U1 affects information in R1 but wholly outside of R2 and U2
| is wholly within R2 (and thus also within R1). The CSN alloted to U1 is
| less than the CSN alloted to U2.
|
| Suppose S3 and S2 establish replication sessions to exchange updates.
| S3 has no changes to send. S2 will send U2 because it is within the scope
| of the replication agreement S3 has with S2, but will not send U1.
|
| S3 and S1 then establish replication sessions. S1 has no changes to send.
| S3 sends U2 since the CSN for U2 is more recent than the CSN
corresponding
| to S2 in S1's update vector. S1 will set the CSN corresponding to S2 in
| its update vector to be the CSN for U2.
|
| Now, if S2 establishes a replication session with S1 it will send no
| updates. In particular, it won't send U1 because the CSN corresponding to
| S2 in S1's update vector is already greater than the CSN for U1. In fact,
| S1 will never receive U1, so the requirement for all replicas to converge
| will not be satisfied. In general, the current LDUP architecture only
| works if the replication topology has no cycles, or where there are
| cycles, if the replicas in each cycle have replication agreements for
| exactly the same area of replication.
|

Hold on...  I'm deleting the rest of this message because you've lost me
here.  I thought that (a) we had a separate CSN vector for each other
server
and that (b) that CSN vector was to the level of attribute and entry.
Thus,
I don't see the problem.

Ryan

---

From: "Steven Legg" <[email-masked]>
Date: Tue, 18 Dec 2001 15:59:19 +1100

John,

John McMeeking wrote:
> the flurry of LDUP notes).

See my reply to Ryan for corrections and clarifications.

> But, we may have a problem with update vectors

Yes.

> Update vectors are defined per replica and per replication context
(actually,
> defined per replica, where a replica is a replicated instance of a
> replication context).
>
> R2 and R1, and the problem Steven describes doesn't occur.

Yes (doh!).

> For either S1

You're alluding to the flip side of what I'm saying. If the current
architecture can't support a replication topology where the servers
in a cycle hold different replication areas in the same replication
context then the choices are to not replicate, or to force all the
servers in the cycle to have the same replication area(s). Too bad
if I don't want S3 to see stuff in R1.

> attributes and/or entries specified for S3, it will be replicated under
> the replication agreements targeting S3 under R1, and the UV for S3
updated
> same server.

Do you agree that S1 will also never see U1 ?
This breaks eventual convergence.

> Steven's example described U1 and U2 as successive updates
> Initially, the update vector for S3 (UV3) looks like
> < Tx#1#0#0, Ty#2#0#0, null > (latest CSNs from S1 and S2, no updates
> originating at S3)

BTW, you have the second and third components of the CSNs transposed.

> This is replicated to S2, and eventually S2 replicates to S3. But since
> no attributes in U1 are present in S3's fractional entry specification,
> no replication occurs.
>

There are some subtleties in the way that the update vector is maintained
that are not explicitly called out by the architecture draft. The update
U1 at S1 causes the update vector for S1 to be revised, but since the
CSN < T15#1#0#0 > in the update vector for S1 is an attribute value it is
tagged with a CSN! Common sense suggests this CSN should also be < T15#1#0#0
>.
Changes to the update vector are always replicated (as add-attribute-value
primitives), so S3 will receive the change to S1's update vector because
of U1, even though it doesn't receive U1. On receiving the
add-attribute-value primitive for S1's update vector, S3 will change its
copy of S1's update vector. It will also change the CSN for S1 in it's own
update vector to < T15#1#0#0 >, the CSN on the add-attribute-value
primitive.

The update vector for S3 actually becomes < T15#1#0#0, Ty#2#0#0, null >.
The purge point advances in due course.

Regards,
Steven