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

From: "Steven Legg" <[email-masked]>
Date: Tue, 3 Apr 2001 17:04:46 +1000

Ed,

Ed Reed wrote:
> 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.

One conflict detection information (CDI) record is propagated for each
update, not for each entry. Its state vectors are generated from the
entry contents at the time the user update is processed by the
originating replica. If a replica has processed N updates to the same
entry since the last replication session then it will retain, and also
propagate, N CDI records. Each CDI record is distinct. It does not
represent the latest state of some specific directory data item like a
replication primitive does. It cannot be superseded by any other CDI
record, but it can be purged in due course.

> 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.

A start vector is constructed by considering all the CSNs associated
with the updated entry. This includes not only the CSNs on attribute
values, but the EntryCSN, Name CSN, Parent CSN, and the CSNs of relevant
deletion records. All attributes are considered, not just the ones
being modified, so the same start vector is generated regardless of
what kind of update is about to be performed.

It might be possible to construct the start vector by only considering
the CSNs on parts of the entry actually read by the update, but right
now I'm not at all sure this variation would work.

> 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,

The CDI records would propagate around in the same way according to
consumers' update vectors. If the supplier holds a CDI record with
a CSN greater than the consumer's update vector that record will
be sent.

> which
> would include the CSNs for each "updated" attribute/value - 
> so the end vector
> you describe would be implicitly sent.

Typically yes, but the effects of an earlier update can be completely
overwritten by later updates. We need to explicitly include the CSN
representing the end vector in the CDI record so that even if all
the replication primitives for some update get superseded by later
updates and disappear, we still have enough information in the CDI
record (which will continue to propagate until all replicas have
received it) to detect any conflicts involving that update.

> 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.

A CDI record is constructed for each update. The timing of the
replication sessions doesn't come into it.

> 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?  

No. The start vector is a representation of the local state of the entry
immediately prior to an update being performed. An alternative way to
think of the start vector is as a description of the previous updates
that the replica performing the update already knows about when the
update is performed. Which ever way you think of it, the start
vector has no dependency on the replica agreements because the entry
has a single state at the time an update is performed, irrespective
of the replication agreements that exist. Every other replica will
receive exactly the same start vector for any particular update.

> 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?

The originating replica is only concerned with the state of the
entry in its local repository at the time the user update is
performed. The update vectors of eventual recipients of the
resulting CDI record don't apply.

> (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 CDI records from both locally originated updates and propagated
updates need to be kept at least until they become old enough to be
purged. It is sufficient if a replica tests each propagated CDI
record for conflicts against the updates it originated (there is no
need to test propagated CDI records against each other), but it does
need to keep the propagated CDI records until they become purgable,
in case they need to be forwarded to some other replica.

> 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.

Recall that this was one of the candidate approaches going into the
architecture bake-off. It has some serious performance problems with the
constant roll-backs and roll-forwards, as well technical difficulties
with keeping the DNs straight (URP achieves the same outcome without
the performance hit and DN ambiguity). Propagating the updates in
their original form doesn't necessarily lead to a simple way to
detect conflicts.

Some of the arguments against using the original operations in the
replication protocol apply for conflict detection as well. If one
server is using a recently standardized or proprietary extension
that other servers can't execute, the conflict detection breaks down.
What I've proposed for conflict detection doesn't depend on consumer's
of the CDI records knowing anything about the original update. It works
even if some replicas are not capable of performing the original update.

> 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?

Yes, but probably not as aggressively as you first thought. The number
of CDI records a replica has to hold at any point in time will be
roughly proportional to the rate of updates performed between
replication sessions. Any conflict detection scheme will have that
property. The scheme I'm describing is at least an add-on that doesn't
require fundamental re-engineering of state-based implementations.
If the conflict detection is switched off a state-based implementation
will behave the way it always has, with all the benefits that entails.

Regards,
Steven

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

---

From: "Ed Reed" <[email-masked]>
Date: Tue, 03 Apr 2001 17:04:34 -0600

[eer]

Comments inline

[/eer]

>>> "Steven Legg" <[email-masked]> 04/03/01 01:04AM >>>

Ed,

Ed Reed wrote:
[snip]

property. 

[eer] - Well, any scheme attempting to provide protection against
this sort of conflict.  A simpler conflict resolution scheme (last
write wins, with nuances to handle transient inconsistencies in
DN construction and other persistent data constraints) only grows
as entry and value deletion flags accumulate without being purged,
and they do so with the advantage that they typically take less
space than the entries and values they delete (which values may
be purged when the deletion flag with its CSN is recorded).
[/eer]

The scheme I'm describing is at least an add-on that doesn't
require fundamental re-engineering of state-based implementations.
If the conflict detection is switched off a state-based implementation
will behave the way it always has, with all the benefits that entails.

[eer] I think you're right - if such a conflict detection mechanism could
be turned off, the state based scheme could devolve gracefully (or, indeed,
operate correctly if the policy had never been enabled or asserted).  The
policy governing the conflict dection mechanism would need to be
documented at the replicaSubentry, and be supported by all
replicas of the replication area.

Of course, the question still arises whether this feature would be a
desireable one or not.  For the applications I am familiar with, I don't
think it affords a benefit proportional to its additional costs in terms of
processing, storage, network traffic, or complexity in the conflict
resolution algorithm.

Thank you for your clarifications - they were most useful.

Ed
[/eer]
Regards,
Steven