Subject: Conflict Detection within the Current Architecture, was RE: New LDUP requirements draft

From: "Ed Reed" <[email-masked]>
Date: Fri, 30 Mar 2001 06:22:20 -0700

Thanks for the idea, Steve - let me see if I understand the main points...

1) The ending CSN vector you'd propagate in the update protocol for
each entry would really be the originating replica's CSN for whatever 
set of modifications are being reported (in the state based replication
system) for the entry - if the replica had several updates to the same
entry since the last replication cycle or replication session with another
replica, it would be the CSN assigned to the last of those changes by
the originating replica.

2) The starting CSN vector would be what, the vector of CSNs constructed
by looking at the pre-image version of the entry attribute values being 
modified at the replica where the modification was entered?  Not the
whole entry's CSN, nor the CSN vector constructed from the entire entry,
but a CSN vector constructed by looking at the attributes which were
changed on the entry and using the CSNs of each of those attributes/values.

I can see that (1), if I understand it correctly, is essentially what we call
for in LDUP, now - the state based system sends the entry's attribute/values 
with CSN values later than the CSN in the update CSN vector corresponding
to the replica consuming the replication information for that session, which
would include the CSNs for each "updated" attribute/value - so the end vector
you describe would be implicitly sent.

I'm having some greater trouble getting my head around (2).  The starting
vector you describe sounds like would be constructed from a pre-modification
image of the entry prior to (each? any? all?) modifications subsequent to the
last replication session with the consuming replica.

Some questions about that:

Since the supplier replica may have replica agreements with several other
replicas, the start vector of CSNs for each entry might need to be different for
the modified entry for each replication session with the different replicas, right?  

In other words, if there are three other replicas, the update vector held by 
the the supplier replica for each of the other replicas might indicate that each of the
other three have received a different set of updates with regard to the
supplying replica, and so the supplier would need to be able to construct
a start vector (from a different starting point) for each entry that is correct for 
each consuming replica?

(This is hard to talk about - pictures might be easier).

If that is the case, then it sounds like each entry needs to keep the start vector
constructed from the pre-image view of that entry for each modification
made to the entry (at least for changes originating at this replica - I haven't
figured out whether it will also need start vectors associated with each
replicated modification received, but suspect that it will).

The storage of such start vectors for each modification would provide some
compression of space in comparison to the storage of the actual modification
(storing CSNs instead of CSNs + operations + values).  But one can think of
situations where the storage would not be much less (a group with 10
members has changes (deletes) made to 3 of the members in a single modification
would have one CSN to store with the modification, but could have up to
one CSN per modified value if each of the pre-existing members have
come from different replicas, so as many as 3 CSNs in this case.

It seems like there is some reduction in log storage requirements
versus simply storing the modification itself, but not an order of
magnitude difference.  For a modest improvement, it seems it might
be simpler and more straight forward to simply have logged the modification
in its entirity, and to gain the benefits that a full log-based replication system
would have to offer in terms of being able to completely replay operations
in sequence.

In my mind, the principle benefit a state based replication scheme has to
offer is that the information retention requirements are simply the
values of the data and their last CSNs.  The CSNs add storage requirements
above and beyond those needed for the data alone, but storeage 
increases linearly with the number of entries, attributes, and values, without
regard to the rate of change, the number of changes, or the
length of time elapsed since replication cycles were last completed.  Even
deletions, which can't be purged until the replication cycle is complete with
all other replicas, are limited in their storage requirements.

So, the rational for using a state based replication system is all about
data storage, and sharply bounding the storage requirements in the face
of lots of changes.

Adding the need to hold start vectors of CSNs for entry modifications
seems to re-introduce a possibly unbounded storage requirement, which
is counter to the objective of the state based replication scheme.

Do I understand your proposal, and am I correct in my assumption that
the storage of entry start vectors grows as the number of unreplicated
changes grows?

Regards,
Ed

=================
Ed Reed
Reed-Matthews, Inc.
+1 801 796 7065
http://www.Reed-Matthews.COM

>>> "Steven Legg" <[email-masked]> 03/29/01 12:47AM >>>

Ed,

> I believe the requirement MAY be satisfied IFF log-based replication
> is used to retransmit the update via LDUP as long as no one else
> has gotten to the modified entry first via an update to some other 
> master (i.e, as long as there are no conflicting collisions). 
>  If there
> are conflicting updates, I think the result that Albert would like to
> see is that the update that collides is bounced in some way for
> administrative resolution.
> 
> For state-based replication the requirement is meaningless, since
> state-based replication has as its goal to make all the replicas
> hold the same values, and it never pretends to try to reproduce
> the operations which were entered to get them to that state - 
> it doesn't care, because it is the ultimate state that is important.
> 
> Believers in state-based replication believe the end justifies
> whatever means are necessary to achieve a common view
> of the data.  Believers in log-based replication think getting
> there is most of the fun.
> 
> Thus, my long-held belief that it MAY BE possible to replicate
> transactional semantics of some sort via log-based replication
> schemes (who can record and playback the transactions
> in question), but it will NEVER be possible to do so with
> state-based replication schemes.

I thought about this today and I think I've found a relatively painless
way to add atomicity information and conflict detection to LDUP that is
friendly to state-based implementations.

The conflict detection scheme I'm about to describe relies on comparing
the before and after states of entries being updated. Updates on a single
master will produce a neat sequence where the after state of one update
matches the before state of the next update in the sequence. In the
multimaster case, there will be some updates that share the same before
state and some updates whose before states reflect different incomplete
sequences of updates. These are the updates in conflict.

The before state of an update is described by a start vector, which is mpler and more straight forward to sim
a set of CSNs that is formed by looking at the CSNs on the contents of
the entry being modified. The highest CSN for each replica ID is retained
in the start vector. I started out by just copying the current update
vector but this approach produces more false positive indications of
conflicts.

The after state of an update is described by an end vector that is
formed in the same way as the start vector, except it looks at the
entry after the update has been performed.

I'll collectively refer to start and end vectors as state vectors.
A state vector SV1 "covers" another state vector SV2 if the CSN in
SV1 for each replica ID is greater than or equal to the CSN for the
same replica ID in SV2.

The start vector tells us what updates have been applied prior to
the update of interest, i.e. the previous updates that are "seen".
Two updates are in conflict if neither of them completely sees the
after state of the other. More precisely, two updates U1 and U2 are
not in conflict if and only if the start vector for U1 covers the end
vector for U2 or the start vector for U2 covers the end vector for U1.
If the start vector for U2 covers the end vector for U1 then U2 "sees"
the entry after U1 has been performed, and therefore logically follows
U1 and there is no conflict. Similarly for the reverse case.

In the simplest cases, two updates are in conflict if they modify the
same entry "simultaneously" at different replicas, without regard to
what they are actually doing to the entry. Consequently, some of the
detected conflicting updates might actually turn out to be independent
changes to the same entry.

Time for an example of conflict detection. Let's suppose there are two
replicas R1 and R2, where everything is in a quiescent state. A state
vector would actually use CSNs but it is sufficient for this example to
just use the timestamp component. I'll represent a state vector as a
tuple (x, y) where x is a timestamp (CSN) generated by R1 and y is a
timestamp (CSN) generated by R2.

At time t0, the state vector for the entry E is (t0,t0) at both replicas.
Update U1 on entry E is performed at R1 at time t1. Thus the start vector
for U1 is (t0,t0) and the end vector is (t1,t0). Simultaneously,
update U2 is performed at R2. The start vector for U2 is also (t0,t0)
and the end vector is (t0,t1). At time t2, U1 is propagated to R2. The
effects of U1 and U2 are merged as described by URP giving a new state
vector for E of (t1,t1). Update U3 on entry E is performed at R1 at
time t3. The start vector for U3 is (t1,t0) and the end vector is (t3,t0).
Update U4 on entry E is performed at R2 at time t3. The start vector for
U4 is (t1,t1) and the end vector is (t1,t3).

I'll summarize the start and end vectors to make this easier.

    start      end
U1: (t0,t0) -> (t1,t0)
U2: (t0,t0) -> (t0,t1)
U3: (t1,t0) -> (t3,t0)
U4: (t1,t1) -> (t1,t3)

Using the conflict detection rule above we come up with the following
conflicts:

U1 conflicts with U2.
U2 conflicts with U1 and U3.
U3 conflicts with U2 and U4.
U4 conflicts with U3.

Of particular note, U4 does not conflict with U1 or U2. It sees the
merged output of these conflicting updates but that doesn't make it
"conflicted" itself. We have to draw a line somewhere.

To detect conflicts we need to propagate the start and end vectors of
an update in the protocol, along with the UUID of the relevant entry.
The end vector is just the start vector with the CSN for the
originating replica replaced by the CSN for the update, so we can
condense this to a single CSN, which also serves to uniquely identify
the update. The start vector is a set of CSNs, like an update vector, but
generally shorter since not all replicas will be represented by CSNs
on the entry contents (because they've never made a change to the entry,
or the CSNs on their changes have long since been purged, or these CSNs
are now old enough to be purged).

The CSN on the conflict detection information can be used in the same
way as the CSN on a replication primitive to decide when the information
needs to be propagated. Because the conflict detection information and
the replication primitives for a specific update have the same CSN
they will necessarily propagate around together. State-based
implementations can still propagate only the net state change,
i.e. they can omit superseded replication primitives, because no
information from the primitives is being used to detect conflicts.

The above provides enough information for any replica to detect every
conflict. Given M replicas originating an average of N updates,
that's roughly (M by N) squared comparisons. If we leave it up to the
originating replica to test only for conflicts against its own updates
the number of comparisons can be reduced to N squared by M.

The scheme extends easily to accommodate grouped operations. All the
replication primitives generated from the one set of grouped operations
really need to have the same CSN (ignoring the least significant
modification number component) so one CSN is still enough for the end
vector. The start vector is generated by considering all the entries
targeted by the grouped operations, instead of just one entry.

Transactions can be similarly accommodated, though if searches are
part of the transaction we should drop the UUID and test the vectors
against updates for all entries when looking for conflicts.

We can also tighten up the conflict detection by adding to the conflict
detection information, lists of the attribute types the update reads
and writes. If the read and write sets of two updates are mutually
disjoint they can't be in conflict even if they modify the same entry
at the same time

Comments anyone ?

Regards,
Steven