Subject: Applicability of LDAP Content Sync to loosely coupled replica sets

From: "Jeff Parham" <[email-masked]>
Date: Thu, 5 Jun 2003 10:45:15 -0700

As a server implementer, LDAP Content Sync has some very desirable
properties.  I lean heavily towards state-based designs myself, and the
idea that one could design client sync based purely on server state and
a small amount of client-persisted cookie information is attractive.
However, I have a question about how the general model applies to highly
available, loosely coupled replica sets:

The requirement for high availability of writes encourages adoption of
multi-master replication between DSAs, and geographic data distribution
and other factors tend to encourage models in which these DSAs are
loosely coupled - e.g., an update can be mastered on one DSA, even if
other DSAs in the replica set can't be simultaneously contacted.

This environment leads to "distribution of truth," where no single DSA
can assert the complete, current state of the system - i.e., no single
DSA necessarily holds the results of all updates previously committed to
all DSAs.  The multi-master replication in effect between DSAs in the
replica set continually brings each DSA more up-to-date with respect to
updates made on other replicas, but barring a cessation of updates, any
given DSA can't be asserted to be completely up-to-date.

High availability of DSAs from which clients can synchronize is very
desirable in these environments: if the DSA that a client last
synchronized from is unavailable, the client would like to synchronize
from an alternate DSA.  In doing so, the client very much wishes to
avoid a full reload - to minimize client resource consumption, to
maximize DSA scalability, and to minimize the latency of obtaining the
incremental updates the client desires.

Is LDAP Content Sync intended to be applicable in this case?

Here it does not appear possible for any given DSA to guarantee that its
notion of the "complete" set of objects matching some given criteria is
identical to the set asserted by another DSA.  Given LDAP Content Sync's
method for declaring the set of objects currently matching the client's
scope (by explicitly enumerating their entryUUIDs), might that then mean
that a new object successfully synchronized from DSA1 could be removed
in a subsequent incremental sync from DSA2, where DSA2 has not yet
replicated the new object from DSA1, because DSA2 does not return the
entryUUID for the new object?  If so, how is the client ensured to
eventually converge to a state in which it holds the new object?  (E.g.,
what if the next sync sources from DSA1?)  Does convergence require a
(DSA-indicated) reload?  How would DSA1 otherwise realize and repair the
loss of client state caused by the client's communication with DSA2?

LCUP appears to be immune to this phenomenon.  Objects can be removed
from the client only upon an LCUP full reload, which we believe will be
exceedingly rare.

Thanks,
-J

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Thu, 05 Jun 2003 13:00:44 -0700

At 10:45 AM 6/5/2003, Jeff Parham wrote:
>Is LDAP Content Sync intended to be applicable in this [multi-master
>replication] case?

No, draft-zeilenga-ldup-sync-02.txt:
  Possible uses include:
    ...
    - Lightweight master-slave replication between heterogeneous
      directory servers.  For example, the Sync operation can
      be used by a slave server to maintain a shadow copy of a
      DIT fragment.

This use has the same basic content synchronization requirements
as what draft-ietf-ldup-lcup-05.txt describes as:
   Applications intending to synchronize heterogeneous data stores.

Kurt

---

From: "Jeff Parham" <[email-masked]>
Date: Thu, 5 Jun 2003 14:26:51 -0700

> From: Kurt D. Zeilenga [mailto:[email-masked]]
> 

My question isn't whether LDAP Content Sync can be used to perform
multi-master replication, it's whether LDAP Content Sync can be used for
a client to synchronize from a store where the store is made up of a set
of nodes that perform multi-master replication amongst themselves.  This
cuts across the various usage scenarios -- e.g., a mail client may wish
to synchronize an address book (as a slave) from a set of multi-mastered
DSAs.

-J

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Thu, 05 Jun 2003 16:01:43 -0700

Jeff Parham wrote:
>of nodes that perform multi-master replication amongst themselves. 

Thanks for the clarification.

We did consider impacts of replication, mostly looking at
single-master environments as this is what we are most familiar
with and what LDAP models currently supports.  However, I
believe that single-master environments have many of the same
client update issues found in multi-master environments (when
you consider issues between slaves which converge at different
rates to their master).

I do think it would be appropriate for each I-D to discuss
replication issues.

>Is LDAP Content Sync intended to be applicable in this case?

Likely (but I'd have to think about it more).  I note that since
LDAP Sync supports both updates+present and update+delete
incremental synchronization mechanisms, if LCUP is applicable
then likely so is LDAP Sync.

Kurt

---

From: "Jeff Parham" <[email-masked]>
Date: Thu, 5 Jun 2003 18:36:41 -0700

Kurt D. Zeilenga wrote:
> with and what LDAP models currently supports.

Maybe just a nit, but there do exist very widely deployed LDAP
directories that support loosely coupled DSAs tied together with
multi-master replication -- Active Directory and eDirectory, for two.  I
guess this issue has beaten into the ground on the list already, though.

> However, I

Agreed -- I suppose I could have left the single- vs. multi-master part
out of my question, and simply stuck with "loosely coupled".

> then likely so is LDAP Sync.

I'm not sure I agree there.  The key difference between LCUP and LDAP
Content Sync is the ability to assert the "member objects" without
forcing a reload.  The implication is that an incremental sync can force
the client to drop previous knowledge, which seems to be the heart of
the problematic example I illustrated.  LCUP doesn't have such a
mechanism; knowledge is lost only on a full reload.

If it were determined that dropping knowledge on incremental LDAP
Content Sync was too problematic (I don't know if this is true -- just
hypothetical) and dropped from the draft, then it seems to me that the
result would essentially be the same as LCUP.  Is that an overly
simplified viewpoint?

Thanks,
-J

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Fri, 06 Jun 2003 10:29:19 -0700

>mechanism; knowledge is lost only on a full reload.

LCUP not only support an incremental sync mechanism (updates+deletes)
to drop previous knowledge, servers are to use those mechanism to ensure
eventual convergence.  If they cannot ensure eventual convergence, they
are to force a reload.

LDAP Sync provides two incremental sync mechanisms (updates+deletes
and update+present), but has the same eventual convergence requirements.

>result would essentially be the same as LCUP.  Is that an overly

I think the WG long ago determined that not providing eventual
convergence was problematic.  To provide eventual convergence,
you not only need mechanism(s) to drop that knowledge, you need
guarantees that the mechanism(s) will be used appropriately to
ensure inconsistencies that might occur are transient.

Kurt

---

From: "Jeff Parham" <[email-masked]>
Date: Fri, 6 Jun 2003 12:52:08 -0700

> -----Original Message-----
> Sent: Friday, June 06, 2003 10:29 AM
> To: Jeff Parham
> Cc: [email-masked]
> Subject: RE: Applicability of LDAP Content Sync to loosely coupled
replica
> sets

By "lost knowledge", I'm referring to knowledge the client did have and
should have in the future, but now does not.  In the example in
http://www.imc.org/ietf-ldup/mail-archive/msg01792.html, a client that
should in the fullness of time have a copy of the new object created on
DSA1 first gets that object from DSA1, then is forced to drop it after
performing an LDAP Content Sync against DSA2.  This is what I refer to
as "lost knowledge", as opposed to the case where synchronization
indicates to the client that an object that the client synced in the
past e.g. has moved out of the subtree being synchronized by the client.

How does LDAP Content Sync detect and recover from this lost knowledge
phenomenon?  If it does so by discouraging or eliminating the mechanism
that diffs the full set of objects by entryUUID, then LDAP Content Sync
essentially becomes the same proposal as LCUP.

In short, I would love to see a solution that requires little or no
history information on the DSA and simultaneously guarantees
convergence, but I'm having trouble seeing how the differences in LDAP
Content Sync over LCUP actually enable this in loosely coupled
deployments.

Thanks,
-J

---

From: "Kurt D. Zeilenga" <[email-masked]>
Date: Sat, 07 Jun 2003 04:35:03 -0700

Jeff,

An LCUP server, in the case you describe, likely has to require
a full reload.  The problem is that the entry in question may,
after changes are reconciled between the DSAs, be no longer in
the result set and that reconciliation may be done in manner to
which DSA2 never knows the entry was ever in the result set
and, hence, never is able to send the necessary delete message
for the entry.  For example, the entry could have been deleted
from DSA1 shortly the client disconnected from DSA1 and yet
before the entry's creation was replicated to DSA2.

I don't see how LDAP-Sync is any worse off here.

Kurt

---

From: "Jeff Parham" <[email-masked]>
Date: Sat, 7 Jun 2003 09:07:06 -0700

Thanks for your responses, Kurt -- I think this is a very valuable
thread.

> Sent: Saturday, June 07, 2003 4:35 AM
> To: Jeff Parham
> Cc: [email-masked]
replica
> before the entry's creation was replicated to DSA2.

Sufficient replicated history information could rectify that without
requiring a reload.  Or if the DSA wasn't sure if the client had
previously synced the object, it could send the deletion anyway.  Or it
might choose to force a reload.  LCUP leaves this design decision in the
hands of implementers.

> I don't see how LDAP-Sync is any worse off here.

If LDAP Sync employs the set-diff by entryUUID method, it always
requires a reload in this case.  How does the DSA know to force a
reload?  Apparently any time the client's last sync was from a different
source DSA from the replica set.  That would seem to make LDAP Sync (or
an LCUP implementation that always requires reloads in such a case)
unsuitable for loosely coupled environments in which high availability
is achieved through replication -- environments in which a client may
frequently choose alternate DSAs to sync from.

If LDAP Sync does not employ the set-diff by entryUUID method, then
you're right: LDAP Sync is no worse than LCUP, but it's also no better
-- they're essentially the same.

What I'm getting at here is the ultimate viability of set-diff by
entryUUID.  If it's not viable in this common scenario -- and
unfortunately I don't believe it is (I very much liked its promise of
"no history required") -- then there's really only one proposal for
client synchronization on the table.

Thanks,
-J

---

From: Jonghyuk Choi <[email-masked]>
Date: Mon, 9 Jun 2003 10:52:12 -0400

Jeff,

>might choose to force a reload.  LCUP leaves this design decision in the

When full reload is chosen, LCUP has the same problem.
The client sees the entry added to DSA1 when it synced with DSA1,
but will not see the entry after it syncs with DSA2 via full reload.

If it is not allowed to lose forward progress in consistency,
a possible approach would be to not remove entries previously
not seen from a DSA when a client syncs with the DSA.
For example, the client does not delete the newly added entry in DSA1 
when it syncs with DSA2, because it never received the entry from DSA2.

This can be used both for LDAP-Sync and for LCUP in the full reload mode.

- Jong

"Jeff Parham" <[email-masked]>
Sent by: [email-masked]
06/07/2003 12:07 PM

        To:     "Kurt D. Zeilenga" <[email-masked]>
        cc:     <[email-masked]>
        Subject:        RE: Applicability of LDAP Content Sync to loosely coupled    replica sets

replica

Thanks,
-J