RE: Multimaster further work

["Clayton Donley" <clayton.donley@octetstring.com>]

Hi. Comments embedded below.


> 	If I make a change today, and you make a differing 
> change to the same DN next week sometime, is that a conflict? 
>  Of course not.  But what if there are two masters, with 
> supposedly-sync'd data, where it takes one week for updates 
> from one to be replicated to the other?  Then we could indeed 
> have a conflict.

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.

> 	Timestamps are a good idea, but have the limitation 
> that your masters need to have their clocks in sync.  If they 
> are off, then I could make a change now, you could make a 
> change later, but your computer's clock is set ahead so your 
> change would get replicated as being the "first" one entered. 
>  Now, the master I'm sitting next to has already committed my 
> change; am I supposed to "undo" my previously-committed 
> entry, then commit your entry, then re-commit my entry?  Are 
> you supposed to commit my entry as being the "latest and 
> greatest" data to commit to the database (even though your 
> data was the latest to be entered)?  What if a master gets a 
> replication with a timestamp set in the future?  Many 
> hardware clocks have a resolution of only 10usecs ; if we're 
> talking about a cluster on a Gigabit network, with large 
> volumes of data being replicated, that is a significant limitation.

Certainly difficult problems (I'm not going to rehash LDUP discussions
on conflict resolution, as that would take all day and we still wouldn't
agree :-) ), but simply setting arbitrary timeouts before/after which
you assume that something is or is not a conflict doesn't necessarily
preclude the need for the above.

> 	Granted, in the real world, conflicts don't come up 
> very frequently (I've never experienced one myself).  But 
> what I'm after is a sound theoretical solution that lets us 
> know _without doubt_ that masters can keep their dbm files in sync.

A worthy goal. Keep in mind that if you're concerned about time to the
usec level and you get very few conflicts in the first place, a
poor-man's implementation might simply require basic time
synchronization while flagging as exceptions changes that happen "very
close" to one another that affect the same parts of the entry. If very
few of those exceptions happen in the first place, some type of
administrative process might not be the end of the world. Unless of
course your boss got his account created and his laptop keeps getting
stolen within 1 usec of that. ;-)

> 
> > MAX_LAG_TIME seems to add additional complexity while not really 
> > helping the servers server figure out the actual order of changes, 
> > etc...
> 
> 	Could you elaborate on this point?

I think my first answer above goes to this point, but let me know if
it's not clear.

[snip]

> 
> 	My goal is to eliminate "unresolvable conflicts" 
> altogether, by specifying an upper limit on how much time any 
> one of the masters has to submit (potentially) conflicting data.

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.

> 	The problem is that all masters are supposed to store 
> identical data.  So what happens when two conflicting changes 
> occur faster than those changes can be replicated?  Whose 
> "change sequence number or such" is correct?


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.


> 	I propose that neither is "more correct" than the 
> other, that they are both equally correct to the time 
> resolution of the system, and that MAX_LAG_TIME lets you 
> specify that time resolution of the system.  Using MD5s is 
> just a useful way to arbitrarily pick one of the entries to 
> be correct, and to have that pick be uniform across all masters.

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

> 	But being able to safely deploy multiple masters across 
> the globe is a desirable goal for large companies.  That 
> means bigger lag times, with more users in front of different 
> masters, with conflicts being more likely to occur.  The 9-11 
> event has also brought fear as a motivating factor, and 
> personally, I think the global economy and corporate 
> internationalization will bring a need within the next few 
> years.  It would be cool if OpenLDAP could say, without 
> doubt, that any conflict will be uniformely resolved across 
> all masters.

In many cases this comes down to directory design. While it's certainly
not been popular these days to add much hierarchy to directories, there
is a case to be made for doing so to a point that would allow some
localization of information in a way that eliminates a single point of
failure and allows local changes to be made even when network or other
factors might otherwise make such changes difficult.

> 	Thank you for the great feedback!  This is fun stuff.

Sure. An interesting discussion.

Clayton