RE: Multimaster further work

[Derek Simkowiak <dereks@itsite.com>]

> Certainly, and unfortunately the only way to know that a conflict did
> indeed happen is if both servers identified the time at which the change
> was made such that a conflict could be identified. I'm not sure that
> MAX_LAG_TIME solves that issue, as it is perfectly reasonable for a DN
> to be changed on two servers (perhaps by a cluster of app servers that
> end up connecting to two different masters) sequentially such that one
> change happens after the other, but still within what you would call
> MAX_LAG_TIME. This is not a conflict either, but it is something where
> only knowing the time and sequence of changes would allow the server to
> piece together what really happened.

	Consider that, in your app server example above, which one
actually gets committed first could depend on what the processor loads on
all involved masters would be.  One day, master1 might process its update
first, but on another day, master2 might have slightly less system load
and process its update first.  My point is that you would, in fact, have a
conflict in the above scenario, and which one happens "first" (as far as
the cluster of masters is concerned) is entirely arbitrary.

	My assertion is that the system cannot say which one happened
first, because it is not perfectly "fast".  If there were some fundamental
unit of time in the Universe, and computers/networks were accurate to that
unit of time, then it would be possible to say which one happened first.
But in an asynchronous system where any given master cannot be sure if
there are any conflicting updates en route (that is, if its data is the
"correct" data) there needs to be a bounds on which writes it will
considered "conflicting".

	My MD5 idea is to simply use the MD5 as a means for ordering
conflicting entries, such that the order is uniform across all masters.
Using the MD5 is not special in any way, other than the fact that it's
easy to implement and does not require communication with any of the other
masters.  If the idea of using an MD5 is confusing, just imagine that you
could list the preferred order of masters for "who's right in a conflict"
in the config file.  (But what a sysadmin headache for nothing.)


	Ask yourself: What if every update was propagated with the MD5 as
a "serial number"?  Then, for any DN, we only commit the update if its
"serial number" (MD5 Digest) is larger than the MD5 Digest of the entry we
already have in there.

	Sounds good, for about half a second.  Then you realize, Hell, if
I come back next week to update my entry, and that MD5 just happens to be
a very small numerical value, it won't be committed to the database.
That is why we need MAX_LAG_TIME -- to state how long other masters have
to submit (potentially) conflicting updates against the DN we have just
propagated to all the other masters.


> you assume that something is or is not a conflict doesn't necessarily
> preclude the need for the above.

	Why not?

	Imagine two masters replicating each other.  One of them dies
completely.  Now we get an update from an enduser.

	How long do we wait for the other master before deciding that
there is no conflicting entry en route?  Forever?

	Imagine two masters replicating each other.  One of them gets an
update.  Two years later, the other one gets an update for the same DN.
How do we know that those two entries are not conflicting with each other?

> synchronization while flagging as exceptions changes that happen "very
> close" to one another that affect the same parts of the entry.

	This could be entirely practical, but administrative processes are
expensive.  Training, permissions, and such.

	And as a human, I'd look at the conflicting entries, realize that
Joe and Barbara both clicked their "submit" buttons at pretty much the
same time, and then arbitrarily choose of them to go into the database.
There no reason OpenLDAP couldn't make that arbitrary decision for me.

	But sending an email whenever a conflict is detected sounds like a
great idea.  It would be nice if there was a config file directive that
would execute an arbitrary shell script for every conflict that was
detected, along with which entry was chosen as the "winner".  That way I
could tell Joe that his new address wasn't saved.


> course your boss got his account created and his laptop keeps getting
> stolen within 1 usec of that. ;-)

	Ha!  You haven't met my boss.  :)


> Good goal, but not sure that simply setting an upper bounds is enough
> because of the question of what to do with changes made sequentially to
> separate masters per my example above.

	...and as I mentioned above, those "sequential" changes would not
actually be sequential at all, because which one gets processed first
would depend on system load, network congestion, where the hard drive's
head happened to be located, etc.  That is, within some limit, of course.

	And I have been calling that limit MAX_LAG_TIME.


> I actually meant a sequence number along with an appropriate system
> identifier and timestamp that would both uniquely identify the version
> of the entry as well as serve to help each system know who had the
> latest changes, if necessary.

	Again you are faced with the problem that each of the masters
would think *its* entry was the "latest changes" that should get
committed.  Nothing that any particular server could write out would make
its update seem more or less important to all the other masters than their
own versions of the conflicting data.


> Not sure how MD5 helps determine which entry is correct. It will just
> say that they are different, eh?

	I propose using the MD5 to determine which order they are
committed in, like a "high score" list on a video game.  The topmost entry
gets committed first, etc.  It's a way to make the arbitrary choice of
"which is right" in a conflict, without having to mess with config files,
contact the other masters, etc.


> In many cases this comes down to directory design.

	Well, yes, but then you don't have conflicting entries for the
same DN.  You have non-conflicting entries for different DNs, and you're
not even in the discussion anymore  :)


--Derek