Subject: Re: 10. "Report propagation sequence"

From: Zachary Amsden <[email-masked]>
Date: Mon, 7 Aug 2000 11:52:05 -0700

I'm not sure what benefit the high water mark gives you, if
you have separate logs from each supplier, as opposed to logs
from each originator.  To transmit the minimal set of changes,
you need to perform an on the fly merge of each supplier log,
so you need a high water mark for each supplier log.  You
could do this just as easily if the logs were demultiplexed
into separate logs for each replica ID, you just keep a
pointer into each CSN log.

Having the logs muxed by replica ID, and sorted by CSN I think
is easier for purging obsolete changes.  With separate
supplier logs, purging would be much more difficult.  Since
you don't know ahead of time what CSNs are in which list, you
may need to scan every entry just to get rid of the changes.

Zach

>10. "Report propagation sequence"
>
>and appending the whole of that section of the original to
this, so that
>when Steve, Ed or others respond, they can also do so here.
>
>There was no terminology confusion as your explanation
corresponds to
>what I thought your implementation was doing. What I did not
understand
>in the paragraph you responded to, was *why* a log based
>implementation would choose to demultiplex the updates it
>consumes into separate logs for each originator replicaId.
>
>That is clearly not necessary in order to transmit updates in
the
>same sequence that they are received, for each originator
replicaId.
>You have still not explained what advantages it has.

---

From: "Albert Langer" <[email-masked]>
Date: Tue, 8 Aug 2000 08:43:31 +1000

[Zach]

[Albert]
My understanding is that propagation is relatively simple for log
based implementations, but an issue for entry based
implementations. The HighwaterMark is primarily for the benefit
of entry based implementations.

According to the current architecture draft:

10.3.2 State-Based Implementation

         A state-based implementation might consider each entry
         of the replica in turn using the Update Vector of the
         consumer to find all the state changes that need to be
         transferred.

While an implementation "might" do that, it would be grossly
inefficient AND result in transmitting updates out of order,
with the resulting problems we agree about.

The HighwaterMark enables an entry based implementation (whether
"state based" or not) to simply maintain an index in local
record sequence number, and start the scan from the least
of the HighwaterMarks of the consumers it is currently supplying.

I agree that this can be done just as easily without a
HighwaterMark when logs are demultiplexed by originator replicaId.

My point is that for *any* log based implementation, there would
be no difficulty just adding a local record sequence number and
appending to the log(s) in that sequence. The HighwaterMarks
would then be used as a pointer into each log in exactly the
same way that you would use the Updated vector (but would be
equally applicable for a single common log, or logs based on
supplier rather than originator, so there is no need for
demultiplexing by originator for propagation).

Likewise there is no difficulty for *any* entry based
implementation in simply maintaining an index of entries by
local record sequence number.

Therefore I argue that adding a local record sequence number to
enable propagating updates in strict order and using
HighwaterMarks between neighbours should be the architectural
change, rather than only requiring strict ordering within each
originator replicaId.

Do you now agree?

[Zach]

[Albert]
Thanks. That answers my question and I believe I now understand
why a log based implementation might choose to demultiplex logs
based on orginator replica Id - it is useful for purging rather
than propagation.

The local record/message numbers and HighwaterMark I am proposing
are not relevant to purging at all, but only used to speed up
internal processing for propagation.

My impression is that the difficulty you mention is a major problem
for entry based implementations, which may motivate the desire to
impose a non-atomic model on LDUP, and hence on LDAP, so that they
can be "state based" rather than just "entry based", while still
purporting to be LDAP servers. If revised LDUP requirements do not
attempt to change the LDAP/X.500 model to suit their desires (or
if LDUP is rejected as an IETF standard as a result of unsuccessfully
attempting to do so), it will still be necessary to accommodate
more legitimate vendor concerns about the performance impact on
their entry based implementations as far as that can possibly be
done without breaking the existing standardized LDAP/X.500
data model.

My understanding is that a major "advantage" of "state based"
implementations is that they can essentially avoid the issue of
log purging entirely, as they retain only the current entry
state and have no logs to purge. eg Active Directory recommends
a default deleted entry "tombstone" lifetime of something like
60 or 90 days and seems to have no other purge mechanism.

That "advantage" comes at an unacceptable cost of breaking the
LDAP/X.500 data model, so when insisting on retaining the current
data model expected by applications it is necessary to carefully
consider the purging mechanisms.

Any replication protocol that maintains atomicity has to retain
some kind of additional "history" information rather than just
current "state". For log based implementations that is not a
problem.

For entry based implementations, I have tried to show in MDCR
that it would not be a problem either, as only the minimal
pointers into the logs necessary to maintain the tree structured
history would need to be maintained in RAM, with a guesstimated
overhead of only about 12 bytes per concurrent unsummarized update.

"Purging", or weeding and summarizing as in MDCR, can then be
easily done for the disk records in batch mode outside peak periods
without affecting the performance advantages of the multiple worker
threads used with more sophisticated databases in entry based
implementations.