Subject: RE: 10. "Report propagation sequence"

From: Zachary Amsden <[email-masked]>
Date: Wed, 16 Aug 2000 21:43:23 -0700

>> >If changes are applied in delivery order then the update vector must
>> >not be revised with respect to the received changes until 
>> the end of the
>> >replication session. However, the update vector would still 
>> be revised
>> >for each locally executed LDAP update. If the connection fails then
>> >the update vector is what it was at the start of the session except
>> >for the server's own record in the vector, which may have 
>> higher CSNs.

>Option 2 is viable with unordered changes in the way I've described.
>It just requires some care in revising the consumer's Update Vector.

So the consumer doesn't change it's update vector, and ignores duplicate
CSNs which it encounters.  Ok, that works, but seems to violate intuition. 
It seems to me that the update vector is a snapshot of the database sync
state.  Having higher CSNs in the database than the update vector doesn't
fit that model.  Allowing out of sync CSNs in the database seems to be
inviting conflicts, and adding unneeded complexity.

>To guarantee that changes adding a parent arrive before changes
>adding a child, the suppliers would have to send changes in the
>same order they were received or executed locally. It wouldn't be
>enough to send changes in order per replica ID. Implementors with
>state-based servers won't like the extra overhead of preserving
>that order. URP easily handles children that arrive before the
>parent so it's not a serious concern anyway.

If they have no index of changed entries, then they need to walk the entire
database for each replication.  I seriously doubt anyone is going to do
that.  If they do have an index, that can easily be extended to preserve
order.  Actually, all you need are two records: last-change and
first-change.  Each change contains the key of the next change.  Then local
updates update last-change, and replication walks from either first change,
or a per-replica high-water mark.

>> easy recovery from aborted updates, better DSA crash
>> recovery), which make any implementation either easier or more robust.
>
>I don't see a significant difference in implementation either way. It all
>comes down to a question of when the consumer's Update Vector is revised,
>and whether outgoing changes are tested against the current Update Vector.
>There is a difference in the amount of traffic following interrupted
>sessions but I expect those to be rare events, and of no concern where
>the replication agreements specify on-change replication.

I'm not really concerned with traffic either.  I am concerned that sending
unordered changes seriously adds to the complexity of URP, testing and
debugging the whole thing.

>> I'd like to know if we have a concensus that changes, 
>> whatever format they
>> may be transmitted in, should be ordered by delivery order.
>
>There would seem to be four choices:
>1) unordered within session,
>2) ordered on CSN per replica ID,
>3) ordered on CSN,
>4) ordered on supplier receipt order.

If you can order on CSN, how much harder can it be to order on local
receipt order?

>Those vendors wanting unordered transmission should speak up now.
>I'm happy with 1, 2 or 3.

I'm very unhappy with 1, only moderately happy with 2 or 3.

Zach

---

From: "Steven Legg" <[email-masked]>
Date: Mon, 21 Aug 2000 11:03:58 +1000

Zach,

> -----Original Message-----
> From: Zachary Amsden [mailto:[email-masked]]
> Sent: Thursday, 17 August 2000 14:43
> To: [email-masked]
> Cc: 'Zachary Amsden'; [email-masked];
> [email-masked]
> Subject: RE: 10. "Report propagation sequence"
>
>

I look at the update vector as only a change propagation mechanism.
I tells us that the contiguous set of changes from a replica up to
the CSN in the vector have been received. We may have received later
changes but we can't yet guarantee there are no gaps in the sequence
for those.

> or a per-replica high-water mark.

Where ever the information on receipt order is stored it has to be part of
the persistent database state. If it is only in the index then that
index must be part of the persistent database. With options 2 and 3
there is enough information from the data stored anyway for URP processing
to build the index. A state-based implementation could choose to keep
the index in temporary memory and rebuild it on restarts by walking the
database.

> debugging the whole thing.

URP is designed to deal with out-of-order changes from different servers,
which is inevitable for multi-master replication. Handling out-of-order
changes from the one server isn't a significantly different problem.
I can't think of anything in URP that could be simplified by insisting
that changes are in some order.

Insisting on receipt order would prevent children arriving before parents
but that situation is seamlessly handled by the more general support for
orphaned entries and conflicting move operations. No ordering would make
it possible to eliminate the support for orphaned entries and conflicting
moves, so knowing that parents will arrive before children doesn't
change anything.

> If you can order on CSN, how much harder can it be to order on local

I don't like option 4 because it requires extra information (beyond URP)
to be persistently stored in the database, but doesn't provide any real
advantage from doing so.

> I'm very unhappy with 1, only moderately happy with 2 or 3.

Does that mean you are happiest with 4 ?

Regards,
Steven