RE: Multimaster Algorithm (was: Documentation volunteer (which was: Cluster replication: multiple masters))

["Howard Chu" <hyc@highlandsun.com>]

> -----Original Message-----
> From: owner-openldap-software@OpenLDAP.org
> [mailto:owner-openldap-software@OpenLDAP.org]On Behalf Of Derek Simkowiak

> > So (for the benefit of the archives), it boils down to this:
> >
> >     In theory, LDAP allows multi-mastering, if the conflicts can be
> >     resolved (e.g. timestamps, per NDS).

Timestamps still require well-synchronized clocks (NTP is good for this) but
even then you're limited by system-clock resolution, and servers running on
different architectures may behave differently here.

> 	Here is an algorithm that I have been working on for safe
> multimaster replication.  Timestamps are still unsafe in the
> real world
> for the reasons that have been mentioned.  But I think I have
> a bettter
> solution.

Sounds interesting.

> 	Currently the multimaster code avoids an infinite
> write-update-write-update loop by looking at the update DN that slurpd
> connects with.  Instead of using an update DN, as the current
> "experimental" code does, just use the following rules:
>
> 1. The LDAP master that is being written to should only "broadcast" an
> update to its slaves (which are also all masters) if the
> update the entry
> data being updated is _different than_ the data that was
> already in the
> database.

I found the above sentence to be unparsable. I think I understand what you
mean though.
>
> 	By "different than", I mean the data for the DN update being
> written does not match the data for the DN in ldbm (as per the LDAP
> compare rules).
>
> 	By "broadcast", I mean slurpd connects to all the replica slaves
> listed in the /etc/openldap/slapd.conf and propagates the update.
>
> 	This functionality would fix the infinite update loop issue
> because a master which already has the data -- as would be
> the case after
> the very first iteration of the update loop -- would not continue
> propagating the change.  Thus the loop is broken.

What you have described here is more of a heuristic than an algorithm; it
doesn't necessarily have a well-defined termination point. In particular, it
can/will fail in the case of unsynchronized databases. It will also fail to
terminate in the presence of two simultaneous conflicting updates; the two
conflicting updates will ping-pong between servers infinitely.

> 	But this does not address what happens if two masters
> are written
> to at "the same time".  For that, see rule 2:
>
> 2. When broadcasting updates, an update for a particular DN
> should only be
> immediately broadcast if an update for that DN has not been received
> within the last x milliseconds.  If an update *has* been
> received within
> the last, say, .1 seconds, then wait "a few milliseconds".

This collision avoidance strategy may work. It doesn't solve the problem with
(1) above though, it only slows down the speed of the loop. I haven't through
it fully, but perhaps you can explore it further. What is the behavior when
multiple updates to an entry are received on one server in rapid succession?

  -- Howard Chu
  Chief Architect, Symas Corp.       Director, Highland Sun
  http://www.symas.com               http://highlandsun.com/hyc
  Symas: Premier OpenSource Development and Support