Re: Supporting Partial Replication

Ryan,

Please disregard my previous reply to you (which didn't make it to the 
mailing list).
More below.

Ryan Moats wrote:
>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 tosend.
>| S3 sends U2 since the CSN for U2 is more recent than the CSNcorresponding
>| 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.

Sorry. I was operating under a false assumption that a server can have only 
one replication
context and therefore only one update vector. I'll correct that shortly to 
remove some
of the confusion.

>I thought that (a) we had a separate CSN vector for each other
>server

You're thinking of the purge vector. In the current architecture, each 
replication
context a server maintains contains a replica subentry that holds a single
CSN vector which is its own update vector. There is also a replica subentry
for each other server, which holds a copy of the other server's update 
vector
in the same replication context.

The combination of a server's own update vector and the update vectors
received from all the other servers constitute the purge vector for that 
replication
context. The purge vector tells a server which of the CSNs it holds are old
enough to be discarded, but plays no part in deciding which updates are 
propagated.

>and that (b) that CSN vector was to the level of attribute and entry.

A CSN in an update vector is a replication context wide value. It is the CSN 
of
the most recent update in the associated replication context received from 
the
corresponding server .

>Thus,
>I don't see the problem.

The critical bit I missed was that in the case where R2 is a complete 
subordinate
subtree of R1 the current architecture avoids losing updates by making R2 a 
separate
replication context. However, R2 can also be a fractional replica or, in 
future, a sparse
replica (although the latest version of the information model effectively 
allows sparse
replicas by allowing non-trivial subtree specifications).

If R2 is a fractional replica then R1 and R2 share the same replication 
context and
therefore there is only one update vector for each of S1, S2 and S3 in my 
example.
Consider the example again, but assume R2 is a fractional replica of  R1.
I've appended the example with corrections as required.

Steven

=======================================================

Consider the following replication topology:

  S1 ====== S2
    \      /
     \    /
      \  /
       S3

Servers S1 & S2 hold full copies of replication area R1, which can be 
considered
to be the entire contents of a particular replication context. S3 holds
replication area R2, a subset of R1, in the same replication context.
R2 could be 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, and that both are in the same replication context.

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 with respect to a particular replication
context has no cycles, or where there are cycles, if the replicas in each
cycle have replication agreements for exactly the same area of replication.

However we can get around this restriction by maintaining an update vector
and replica ID per replication area (per replication context) for which a 
server
has a replication agreement, instead of a single update vector and single
replica ID per replication context per server.

A single replication context is assumed in what follows.
Let UV(S,R) be a reference to the update vector maintained by
server S for replication area R. It becomes convenient at this point to
have global unique identifiers for replication areas, e.g. R.
ASIDE: It also makes sense to have replication area descriptions as distinct
managed objects, and for replication agreement objects to just reference
a replication area by its unique identifier, instead of itself describing
the information to be replicated.

Suppose there is a server, S, with replication agreements for replication
area, R. We require a replica ID to uniquely identify the copy of the
information in R maintained by S. It is convenient for the purposes of
this discussion to use the notation S.R for that replica ID.

Let T be some other server and let Q be a replication area maintained by T.
An element in UV(S,R) for replica T.Q with the CSN value, C, is an assertion
that S has received from T.Q all updates to R with CSNs less than or equal
to C.

If all such updates have been received then it is also true that S has
received from T.Q all updates (with CSNs less than or equal to C) to
every replication area P, where P is a subset of R.

All the client updates processed by T.Q must be within replication area Q,
so if Q is a subset of, or the same as, R then S has received from T.Q all
updates (with CSNs less than or equal to C) to every replication area P,
where P is a superset of R.

We can use these results to obtain the following rule for maintaining
multiple update vectors in the one server, which for the sake of argument
I will call the update vector cascade rule:

  Given that S is receiving updates for replication area R, when S
  receives an update with a CSN containing a replica ID of T.Q it shall
  revise the CSN corresponding to T.Q in UV(S,R) and in every UV(S,P)
  where P is a subset of R. If Q is a subset of, or the same as, R then
  S shall revise the CSN corresponding to T.Q in every UV(S,P) where P
  is a superset of R.

For each update we need to be able to determine the replication area to
which it has been applied. Provided the replica and replication area
administrative objects are available then a lookup using the replica ID
in the CSN associated with update can give us the replication area. We also
need to be able to determine the supersets and subsets of the replication
area. This can be precalculated and cached from examination of the
replication area objects.

Now I'll show how the new architecture supports the topology of the
original example. Conceptually, S1 will now hold two replicas S1.R1 and
S1.R2, and two update vectors UV(S1,R1) and UV(S1,R2). S2 will now hold
two replicas S2.R1 and S2.R2, and two update vectors UV(S2,R1) and
UV(S2,R2). S3 holds only one replica S3.R2 and one update vector UV(S3,R2).

The update U1 is within R1 but outside R2 so this update is necessarily
applied to the replica S2.R1. The replica ID in the CSN for U1 will be
S2.R1.

In applying the update U2, S2 has a choice between replicas S2.R1 and
S2.R2 since U2 is within both R1 and R2. The detailed steps following
each choice are different, but the final outcome is always the same.
Note that S2 doesn't hold duplicates of all the entries and attributes
in R2. U2 acts on the same instance of the target entry and its attributes
regardless of the selected replica. The only material difference is the
replica ID that goes into the CSN generated for U2.

Firstly, I'll run through what happens if S2 chooses to apply U2 within R2.
The replica ID in the CSN for U2 will be S2.R2. S2 will set the CSN
corresponding to S2.R2 in UV(S2,R2) to be the CSN for U2. It will also
set the CSN corresponding to S2.R2 in UV(S2,R1) to be the CSN for U2.
This is the result of S2 applying the cascade rule to itself (R = Q = R2,
S = T = S2).

S3 and S2 establish replication sessions to exchange updates to replication
area R2. As before, S3 has no changes to send, and S2 will send U2 but
will not send U1. S3 sets the CSN corresponding to S2.R2 in UV(S3,R2) to
the CSN for U2.

S3 and S1 establish replication sessions to exchange updates to replication
area R2. S1 has no changes to send, as before. S3 sends U2 since the CSN
on U2 is more recent than the CSN corresponding to S2.R2 in UV(S1,R2).
S1 will set the CSN corresponding to S2.R2 in UV(S1,R2) to be the CSN for
U2. S1 will also set the CSN corresponding to S2.R2 in UV(S1,R1) by
application of the cascade rule (S = S1, T = S2, R = Q = R2).

If S2 establishes a replication session with S1 to send updates to
replication area R1 it will obtain UV(S1,R1). S2 will send U1 to S1 since
the CSN for U1 is greater than the CSN corresponding to S2.R1 in UV(S1,R1).
It won't send U2 since the CSN corresponding to S2.R2 in UV(S1,R1) already
has the value of the CSN for U2.

So S3 gets U2 and S1 gets both U1 and U2, exactly as it should be.

Now, I'll run through what happens if S2 chooses to apply U2 within R1.
The replica ID in the CSN for U2 will be S2.R1. S2 will set the CSN
corresponding to S2.R1 in UV(S2,R1) to be the CSN for U2. It will also
set the CSN corresponding to S2.R1 in UV(S2,R2) to be the CSN for U2.
This is the result of S2 applying the cascade rule to itself (R = Q = R1,
S = T = S2).

S3 and S2 establish replication sessions to exchange updates to replication
area R2. As before, S3 has no changes to send, and S2 will send U2 but
will not send U1. S3 sets the CSN corresponding to S2.R1 in UV(S3,R2) to
the CSN for U2.

S3 and S1 establish replication sessions to exchange updates to replication
area R2. S1 has no changes to send, as before. S3 sends U2 since the CSN
on U2 is more recent than the CSN corresponding to S2.R1 in UV(S1,R2).
S1 will set the CSN corresponding to S2.R1 in UV(S1,R2) to be the CSN for
U2. Application of the cascade rule (S = S1, T = S2, R = R2, Q = R1)
results in NO changes to UV(S1,R1). We now have the situation that U2 is
notionally present in the replica S1.R2 but not in the replica S1.R1. As
I indicated earlier, a server doesn't hold duplicates of entries and
attributes that are in multiple replication areas. If S1 engages in any
replication sessions with other servers for the replication area R1 it
must exclude any changes with CSNs greater than the relevant CSN in
UV(S1,R1). This includes U2 when it has been originally applied within R1
and so far only received via S3.

If S2 establishes a replication session with S1 to send updates to
replication area R1 it will obtain UV(S1,R1). S2 will send both U1 and U2
to S1 since the CSNs for U1 and U2 are greater than the CSN corresponding
to S2.R1 in UV(S1,R1). S1 will receive U2 twice but URP will quickly
ignore the duplicate. Importantly, S1 will set the CSN corresponding to
S2.R1 in UV(S1,R1) to be the CSN for U2.

We can avoid the duplication if we arrange for S2 to obtain both UV(S1,R1)
and UV(S1,R2) (in general, any UV(S1,P) where P is a subset of R1) at the
start of the replication session, but we must still make some provision
for UV(S1,R1) to be revised correctly. It will be easier to just accept
that there may be some harmless duplication.

This example is too simple and narrow to show it but in general, applying
an update to the smallest subset replication area (e.g. R2 instead of R1)
allows it to propagate through more paths, more quickly and with less
duplication.

The following topology is more interesting but I'll leave example
walkthroughs as an exercise for the reader.

       S0
      /  \
     /    \
    /      \
  S1        S2
    \      /
     \    /
      \  /
       S3

Servers S0, S1 and S2 hold full copies of replication area R1 in some 
replication context.
S3 holds replication area R2, a subset of R1, in the same replication 
context.

In this situation S0 only has replication agreements for R1 and therefore
only needs to maintain one update vector UV(S0,R1). It doesn't need to
bother with R2. This is a particularly useful result because it means that
a server, having entered into a replication agreement with some peer
server, isn't signficantly affected by the replication agreements the peer
server might make with yet other servers.


The extended architecture described here also provides a mechanism for
supporting expedited changes, which aren't possible in the current
architecture. The information, changes to which are to be expedited, is
set up as a subset replication area. Additional replication agreements
are established with the peer servers for this subset replication area,
presumably with on-change replication schedules. Updates to the subset
area get propagated immediately, while other updates propagate less
frequently, but eventually all updates get through.

The extended architecture can also handle replication areas that are
subordinate subtrees in a replication context without needing to make
the subordinate subtree a separate replication context.




_________________________________________________________________
Get your FREE download of MSN Explorer at http://explorer.msn.com/intl.asp.